# Simultaneously Achieving Sublinear Regret and Constraint Violations for Online Convex Optimization with Time-varying Constraints

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 35 references that are in the map.
- First posted on arXiv 15 Nov 2021.

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

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Adaptive Online Learning in Dynamic Environments](https://mlsanity.com/paper/1810.10815/) (2018)
- [Online Convex Optimization with Stochastic Constraints](https://mlsanity.com/paper/1708.03741/) (2017)
- [Dynamic Regret of Convex and Smooth Functions](https://mlsanity.com/paper/2007.03479/) (2020)
- [Adaptive Algorithms for Online Convex Optimization with Long-term Constraints](https://mlsanity.com/paper/1512.07422/) (2015)
- [Online convex optimization for cumulative constraints](https://mlsanity.com/paper/1802.06472/) (2018)
- [An Online Convex Optimization Approach to Dynamic Network Resource Allocation](https://mlsanity.com/paper/1701.03974/) (2017)
- [Bandit Convex Optimization for Scalable and Dynamic IoT Management](https://mlsanity.com/paper/1707.09060/) (2017)
- [Online mirror descent and dual averaging: keeping pace in the dynamic case](https://mlsanity.com/paper/2006.02585/) (2020)
- [Distributed Bandit Online Convex Optimization with Time-Varying Coupled Inequality Constraints](https://mlsanity.com/paper/1912.03719/) (2019)
- [On Distributed Online Convex Optimization with Sublinear Dynamic Regret and Fit](https://mlsanity.com/paper/2001.03166/) (2020)
- [The Power of Online Learning in Stochastic Network Optimization](https://mlsanity.com/paper/1404.1592/) (2014)
- [Peak-Aware Online Economic Dispatching for Microgrids](https://mlsanity.com/paper/1508.03996/) (2015)
- [Proximal Online Gradient is Optimum for Dynamic Regret](https://mlsanity.com/paper/1810.03594/) (2018)

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

- [Optimal Algorithms for Online Convex Optimization with Adversarial Constraints](https://mlsanity.com/paper/2310.18955/) (2023)
- [Online Learning under Adversarial Nonlinear Constraints](https://mlsanity.com/paper/2306.03655/) (2023)
- [On Dynamic Regret and Constraint Violations in Constrained Online Convex Optimization](https://mlsanity.com/paper/2301.09808/) (2023)
- [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)
- [Online Convex Optimization with Switching Cost and Delayed Gradients](https://mlsanity.com/paper/2310.11880/) (2023)
- [Safety in the Face of Adversity: Achieving Zero Constraint Violation in Online Learning with Slowly Changing Constraints](https://mlsanity.com/paper/2505.00398/) (2025)
- [An Online Feasible Point Method for Benign Generalized Nash Equilibrium Problems](https://mlsanity.com/paper/2410.02400/) (2024)
- [Dynamic Regret Bounds for Online Omniprediction with Long Term Constraints](https://mlsanity.com/paper/2510.07266/) (2025)
- [Multi-Objective textitmin-max Online Convex Optimization](https://mlsanity.com/paper/2510.13560/) (2025)
- [Structure-Dependent Regret and Constraint Violation Bounds for Online Convex Optimization with Time-Varying Constraints](https://mlsanity.com/paper/2603.14319/) (2026)
- [Constrained Online Learning with Noisy Constraint Values](https://mlsanity.com/paper/2609.06921/) (2026)

## Abstract (arXiv)

In this paper, we develop a novel virtual-queue-based online algorithm for online convex optimization (OCO) problems with long-term and time-varying constraints and conduct a performance analysis with respect to the dynamic regret and constraint violations. We design a new update rule of dual variables and a new way of incorporating time-varying constraint functions into the dual variables. To the best of our knowledge, our algorithm is the first parameter-free algorithm to simultaneously achieve sublinear dynamic regret and constraint violations. Our proposed algorithm also outperforms the state-of-the-art results in many aspects, e.g., our algorithm does not require the Slater condition. Meanwhile, for a group of practical and widely-studied constrained OCO problems in which the variation of consecutive constraints is smooth enough across time, our algorithm achieves O(1) constraint violations. Furthermore, we extend our algorithm and analysis to the case when the time horizon T is unknown. Finally, numerical experiments are conducted to validate the theoretical guarantees of our algorithm, and some applications of our proposed framework will be outlined.