# Online Convex Optimization with Perturbed Constraints

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 May 2019.

## Built on by (most cited first, 12 of 12)

- [Online Caching with Optimistic Learning](https://mlsanity.com/paper/2202.10590/) (2022)
- [Online Convex Optimization with Continuous Switching Constraint](https://mlsanity.com/paper/2103.11370/) (2021)
- [Lazy Lagrangians with Predictions for Online Learning](https://mlsanity.com/paper/2201.02890/) (2022)
- [Online Caching with no Regret: Optimistic Learning via Recommendations](https://mlsanity.com/paper/2204.09345/) (2022)
- [Stochastic Online Fisher Markets: Static Pricing Limits and Adaptive Enhancements](https://mlsanity.com/paper/2205.00825/) (2022)
- [Projection-Free Online Convex Optimization with Stochastic Constraints](https://mlsanity.com/paper/2305.01333/) (2023)
- [Online Convex Optimization with Stochastic Constraints: Zero Constraint Violation and Bandit Feedback](https://mlsanity.com/paper/2301.11267/) (2023)
- [Penalised FTRL With Time-Varying Constraints](https://mlsanity.com/paper/2204.02197/) (2022)
- [Optimistic Learning for Communication Networks](https://mlsanity.com/paper/2504.03499/) (2025)
- [Bandits in Flux: Adversarial Constraints in Dynamic Environments](https://mlsanity.com/paper/2601.19867/) (2026)
- [Constrained Online Convex Optimization with Memory and Predictions](https://mlsanity.com/paper/2603.21375/) (2026)
- [Real-Time Hard Peak Age-of-Information Safety with No-Regret Learning](https://mlsanity.com/paper/2607.27626/) (2026)

## Abstract (arXiv)

This paper addresses Online Convex Optimization (OCO) problems where the constraints have additive perturbations that (i) vary over time and (ii) are not known at the time to make a decision. Perturbations may not be i.i.d. generated and can be used to model a time-varying budget or commodity in resource allocation problems. The problem is to design a policy that obtains sublinear regret while ensuring that the constraints are satisfied on average. To solve this problem, we present a primal-dual proximal gradient algorithm that has O(Tε vee T1-ε) regret and O(Tε) constraint violation, where ε ∈ [0,1) is a parameter in the learning rate. Our results match the bounds of previous work on OCO with time-varying constraints when ε = 1/2; however, we (i) define the regret using a time-varying set of best fixed decisions; (ii) can balance between regret and constraint violation; and (iii) use an adaptive learning rate that allows us to run the algorithm for any time horizon.