# Online Convex Optimization with Time-Varying Constraints

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

## Key facts

- Cited by 56 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Feb 2017.

## Built on by (most cited first, 30 of 56)

- [Regret and Cumulative Constraint Violation Analysis for Online Convex Optimization with Long Term Constraints](https://mlsanity.com/paper/2106.05135/) (2021)
- [DOPE: Doubly Optimistic and Pessimistic Exploration for Safe Reinforcement Learning](https://mlsanity.com/paper/2112.00885/) (2021)
- [Optimal Algorithms for Online Convex Optimization with Adversarial Constraints](https://mlsanity.com/paper/2310.18955/) (2023)
- [Non-stationary Bandits with Knapsacks](https://mlsanity.com/paper/2205.12427/) (2022)
- [Regret and Cumulative Constraint Violation Analysis for Distributed Online Constrained Convex Optimization](https://mlsanity.com/paper/2105.00321/) (2021)
- [Towards Better Statistical Understanding of Watermarking LLMs](https://mlsanity.com/paper/2403.13027/) (2024)
- [Distributed Online Convex Optimization with Adversarial Constraints: Reduced Cumulative Constraint Violation Bounds under Slater's Condition](https://mlsanity.com/paper/2306.00149/) (2023)
- [Safe Online Convex Optimization with Unknown Linear Safety Constraints](https://mlsanity.com/paper/2111.07430/) (2021)
- [Learning to Persuade on the Fly: Robustness Against Ignorance](https://mlsanity.com/paper/2102.10156/) (2021)
- [An Optimistic Algorithm for Online Convex Optimization with Adversarial Constraints](https://mlsanity.com/paper/2412.08060/) (2024)
- [Rectified Pessimistic-Optimistic Learning for Stochastic Continuum-armed Bandit with Constraints](https://mlsanity.com/paper/2211.14720/) (2022)
- [Online Convex Optimization with Continuous Switching Constraint](https://mlsanity.com/paper/2103.11370/) (2021)
- [BanditQ: Fair Bandits with Guaranteed Rewards](https://mlsanity.com/paper/2304.05219/) (2023)
- [Online Learning under Adversarial Nonlinear Constraints](https://mlsanity.com/paper/2306.03655/) (2023)
- [Online Learning under Budget and ROI Constraints via Weak Adaptivity](https://mlsanity.com/paper/2302.01203/) (2023)
- [Online Nonstochastic Control with Adversarial and Static Constraints](https://mlsanity.com/paper/2302.02426/) (2023)
- [Projection-Free Online Convex Optimization with Time-Varying Constraints](https://mlsanity.com/paper/2402.08799/) (2024)
- [Revisiting Projection-Free Online Learning with Time-Varying Constraints](https://mlsanity.com/paper/2501.16046/) (2025)
- [A Geometric Approach to Constrained Online Learning](https://mlsanity.com/paper/2605.21107/) (2026)
- [Best of Many Worlds Guarantees for Online Learning with Knapsacks](https://mlsanity.com/paper/2202.13710/) (2022)
- [Dynamic Regret Analysis of Safe Distributed Online Optimization for Convex and Non-convex Problems](https://mlsanity.com/paper/2302.12320/) (2023)
- [Universal Dynamic Regret and Constraint Violation Bounds for Constrained Online Convex Optimization](https://mlsanity.com/paper/2510.01867/) (2025)
- [Convex Optimization with Nested Evolving Feasible Sets](https://mlsanity.com/paper/2605.07386/) (2026)
- [A New Benchmark for Online Learning with Budget-Balancing Constraints](https://mlsanity.com/paper/2503.14796/) (2025)
- [Breaking the O(√T) Cumulative Constraint Violation Barrier while Achieving O(√T) Static Regret in Constrained Online Convex Optimization](https://mlsanity.com/paper/2603.20671/) (2026)
- [Projection-Free Online Convex Optimization with Stochastic Constraints](https://mlsanity.com/paper/2305.01333/) (2023)
- [Online Learning with Unknown Constraints](https://mlsanity.com/paper/2403.04033/) (2024)
- [Online Omniprediction with Long-Term Constraints](https://mlsanity.com/paper/2509.11357/) (2025)
- [Noise-Adaptive High-Probability Regret Bounds for Online Convex Optimization](https://mlsanity.com/paper/2606.08028/) (2026)
- [Constrained Online Convex Optimization without Slater's Condition](https://mlsanity.com/paper/2606.31480/) (2026)

## Abstract (arXiv)

This paper considers online convex optimization with time-varying constraint functions. Specifically, we have a sequence of convex objective functions ft(x)t=0∞ and convex constraint functions gt,i(x)t=0∞ for i ∈ 1, ..., k. The functions are gradually revealed over time. For a given ε>0, the goal is to choose points xt every step t, without knowing the ft and gt,i functions on that step, to achieve a time average at most ε worse than the best fixed-decision that could be chosen with hindsight, subject to the time average of the constraint functions being nonpositive. It is known that this goal is generally impossible. This paper develops an online algorithm that solves the problem with O(1/ε2) convergence time in the special case when all constraint functions are nonpositive over a common subset of ℝn. Similar performance is shown in an expected sense when the common subset assumption is removed but the constraint functions are assumed to vary according to a random process that is independent and identically distributed (i.i.d.) over time slots t ∈ 0, 1, 2, ldots. Finally, in the special case when both the constraint and objective functions are i.i.d. over time slots t, the algorithm is shown to come within ε of optimality with respect to the best (possibly time-varying) causal policy that knows the full probability distribution.