# Penalised FTRL With Time-Varying Constraints

arXiv: https://arxiv.org/abs/2204.02197 · HTML: https://mlsanity.com/paper/2204.02197/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 14 references that are in the map.
- First posted on arXiv 5 Apr 2022.

## Builds on (most cited first, 6 of 6)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Online Convex Optimization with Stochastic Constraints](https://mlsanity.com/paper/1708.03741/) (2017)
- [Adaptive Algorithms for Online Convex Optimization with Long-term Constraints](https://mlsanity.com/paper/1512.07422/) (2015)
- [An Online Convex Optimization Approach to Dynamic Network Resource Allocation](https://mlsanity.com/paper/1701.03974/) (2017)
- [Distributed Online Convex Optimization with Time-Varying Coupled Inequality Constraints](https://mlsanity.com/paper/1903.04277/) (2019)
- [Online Convex Optimization with Perturbed Constraints](https://mlsanity.com/paper/1906.00049/) (2019)

## Abstract (arXiv)

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(√t) regret and violation with respect to strong benchmark hatXmaxt. 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(√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(√t) regret and violation performance is achievable.