Penalised FTRL With Time-Varying Constraints
This work addresses online optimization challenges for scenarios with dynamic constraints, offering a more general solution than existing primal-dual methods, though it is incremental in extending classical FTRL.
The paper tackles the problem of online optimization with time-varying constraints by extending the Follow-The-Regularized-Leader (FTRL) algorithm with adaptive penalization, achieving O(√t) regret and violation against a strong benchmark without prior knowledge of constraints.
In this paper we extend the classical Follow-The-Regularized-Leader (FTRL) algorithm to encompass time-varying constraints, through adaptive penalization. We establish sufficient conditions for the proposed Penalized FTRL algorithm to achieve $O(\sqrt{t})$ regret and violation with respect to strong benchmark $\hat{X}^{max}_t$. Lacking prior knowledge of the constraints, this is probably the largest benchmark set that we can reasonably hope for. Our sufficient conditions are necessary in the sense that when they are violated there exist examples where $O(\sqrt{t})$ regret and violation is not achieved. Compared to the best existing primal-dual algorithms, Penalized FTRL substantially extends the class of problems for which $O(\sqrt{t})$ regret and violation performance is achievable.