# Optimal Anytime Algorithms for Online Convex Optimization with Adversarial Constraints

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 24 references that are in the map.
- First posted on arXiv 26 Oct 2025.

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

- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Adversarial Bandits with Knapsacks](https://mlsanity.com/paper/1811.11881/) (2018)
- [What Doubling Tricks Can and Can't Do for Multi-Armed Bandits](https://mlsanity.com/paper/1803.06971/) (2018)
- [Online Convex Optimization with Time-Varying Constraints](https://mlsanity.com/paper/1702.04783/) (2017)
- [A Unifying Framework for Online Optimization with Long-Term Constraints](https://mlsanity.com/paper/2209.07454/) (2022)
- [Regret and Cumulative Constraint Violation Analysis for Online Convex Optimization with Long Term Constraints](https://mlsanity.com/paper/2106.05135/) (2021)
- [Optimal Algorithms for Online Convex Optimization with Adversarial Constraints](https://mlsanity.com/paper/2310.18955/) (2023)
- [Distributed Online Convex Optimization with Adversarial Constraints: Reduced Cumulative Constraint Violation Bounds under Slater's Condition](https://mlsanity.com/paper/2306.00149/) (2023)
- [A continuous-time approach to online optimization](https://mlsanity.com/paper/1401.6956/) (2014)
- [Learning Safety Constraints for Large Language Models](https://mlsanity.com/paper/2505.24445/) (2025)
- [An Optimistic Algorithm for Online Convex Optimization with Adversarial Constraints](https://mlsanity.com/paper/2412.08060/) (2024)
- [Improving Adaptive Online Learning Using Refined Discretization](https://mlsanity.com/paper/2309.16044/) (2023)
- [Projection-free Algorithms for Online Convex Optimization with Adversarial Constraints](https://mlsanity.com/paper/2501.16919/) (2025)
- [Towards Minimax Online Learning with Unknown Time Horizon](https://mlsanity.com/paper/1307.8187/) (2013)
- [Universal Dynamic Regret and Constraint Violation Bounds for Constrained Online Convex Optimization](https://mlsanity.com/paper/2510.01867/) (2025)

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

- [Constrained Online Convex Optimization without Slater's Condition](https://mlsanity.com/paper/2606.31480/) (2026)

## Abstract (arXiv)

We propose an anytime online algorithm for the problem of learning a sequence of adversarial convex cost functions while approximately satisfying another sequence of adversarial online convex constraints. A sequential algorithm is called anytime if it provides a non-trivial performance guarantee for any intermediate timestep t without requiring prior knowledge of the length of the entire time horizon T. Our proposed algorithm achieves optimal performance bounds without resorting to the standard doubling trick, which has poor practical performance due to multiple restarts. Our core technical contribution is the use of time-varying Lyapunov functions to keep track of constraint violations. This must be contrasted with prior works that used a fixed Lyapunov function tuned to the known horizon length T. The use of time-varying Lyapunov function poses unique analytical challenges as properties, such as monotonicity, on which the prior proofs rest, no longer hold. By introducing a new analytical technique, we show that our algorithm achieves O(√t) regret and tildeO(√t) cumulative constraint violation bounds for any t≥ 1. We extend our results to the dynamic regret setting, achieving bounds that adapt to the path length of the comparator sequence without prior knowledge of its total length. We also present an adaptive algorithm in the optimistic setting, whose performance gracefully scales with the cumulative prediction error. We demonstrate the practical utility of our algorithm through numerical experiments involving the online shortest path problem.