Optimal Anytime Algorithms for Online Convex Optimization with Adversarial Constraints
Dhruv Sarkar, Abhishek Sinha · 2025
Read Optimal Anytime Algorithms for Online Convex Optimization with Adversarial Constraints by Dhruv Sarkar, Abhishek Sinha (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-22579.txt.
Introduction
Learning step by step against changing costs, while also respecting changing limits, is the setting studied by Dhruv Sarkar and Abhishek Sinha in 2025. Their online convex optimization problem has an adversary choosing both costs and constraints, and the learner never knows when the sequence will end.
Their anytime algorithm gives a real guarantee at every step, without the restart trick older methods used. Time varying Lyapunov functions, which track how badly limits are being broken, are the core device. The authors prove regret and total violation both grow only like the square root of time. Results also extend to targets that move over time.
Catalog record
| CREATOR | Dhruv Sarkar, Abhishek Sinha |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 68 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-22579
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Optimal Anytime Algorithms for Online Convex Optimization with Adversarial Constraints Dhruv Sarkar, Abhishek Sinha Abstract 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 t without requiring prior knowledge of the length of the entire time horizon T 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 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 ) O(\sqrt{t}) regret and O ~ ( t ) \tilde{O}(\sqrt{t}) cumulative constraint violation bounds for any t ≥ 1 t\geq 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. 1 Introduction We consider a natural generalization of the standard Online Convex Optimization (OCO) problem, called C onstrained O nline C onvex O ptimization (COCO), where in addition to a convex cost function, a convex constraint function is revealed to the learner after it chooses its action at each round for a horizon of T rounds. The goal is to design an online algorithm which achieves a small regret (w.r.t. the cost functions) while ensuring a small cumulative constraint violation or CCV (w.r.t. the constraint functions) for all rounds t\geq 1 . The COCO problem arises in many practical settings, including safety-aware contextual bandits ( Sun et al. 2017 ) , autonomous driving ( Gao et al. 2024 ) , budget-constrained bandits ( Immorlica et al. 2022 ) , and learning safety constraints in LLMs ( Chen et al. 2025 ) . The COCO problem has been extensively studied in the literature over the past decade ( Guo et al. 2022 ; Yi et al. 2023 ; Neely and Yu 2017 ) . Recent work by Sinha and Vaze 2024 introduced a simple algorithm which yields O(\sqrt{T}) regret and \tilde{O}(\sqrt{T}) CCV guarantees, which are also shown to be tight when the horizon length T is known. These results are established by leveraging a Lyapunov function-based technique that constructs a surrogate cost function by linearly combining the cost and constraint functions at each round, and then passes it on to a standard OCO algorithm. The analysis is also refreshingly elegant in stark contrast to prior works that rely on primal-dual-based approaches and achieve only suboptimal guarantees ( Guo et al. 2022 ; Yi et al. 2021 ; Yi et al. 2023 ; Sun et al. 2017 ) . However, a major drawback of their result is that their proposed algorithm is not anytime as it needs to know the length of the horizon T a priori . In particular, although their algorithm achieves O(\sqrt{t}) regret for any t\geq 1, the CCV guaranteed by their algorithm is not time-uniform as it only achieves a CCV of \tilde{O}(\sqrt{T}) for any time t\geq 1 , however small ( Sinha and Vaze 2024 , Theorem 1) . This raises a natural and important question - is it possible to design a COCO algorithm which simultaneously achieves O(\sqrt{t}) regret and \tilde{O}(\sqrt{t}) CCV for any t\geq 1? In this paper, we affirmatively answer this question by introducing a sequence of time-varying Lyapunov functions \{\Phi_{t}(\cdot)\}_{t\geq 1}, which replace the fixed, horizon-dependent Lyapunov function \Phi(\cdot) employed by Sinha and Vaze 2024 . Their analysis crucially utilized the monotone non-decreasing property of the \{\Phi(Q(t))\}_{t\geq 1} sequence, where Q(t) is the CCV up to round t . Unfortunately, it turns out that with the new Lyapunov functions, \Phi_{t}(x) is actually monotonically decreasing pointwise in t , and hence, the previous arguments do not apply. The key technical novelty in our analysis is in ensuring that the sequence \{\Phi_{t}(Q(t))\}_{t\geq 1} remains monotonically non-decreasing even though \Phi_{t}(x)<\Phi_{t-1}(x),\forall x . This is achieved by defining Q(t) to be a suitable upper bound to the current CCV while adequately exploiting the exponential form of the Lyapunov functions (see Eqn. ( 6 )). In summary, we make the following contributions in the paper: • We propose a simple anytime algorithm for COCO that achieves O(\sqrt{t}) regret and \tilde{O}(\sqrt{t}) CCV for any t\geq 1. Our algorithm does not need multiple restarts and completely avoids the impractical doubling trick (see section A for more details). • The above results are obtained by introducing a sequence of time-varying Lyapunov functions in both our algorithms and their analysis. Compared to the prior works, which use time-invariant Lyapunov functions, time-varying Lyapunov functions pose non-trivial technical challenges, as the key monotonicity property is lost. We address this challenge by working with a suitable upper bound to CCV and appropriately tuning the parameters of the Lyapunov functions. • We show that our techniques extend naturally to the dynamic regret and optimistic settings. In particular, we design algorithms with performance bounds that adapt to unknown parameters, such as the total path length \mathcal{P}_{T} or the total prediction error \mathcal{E}_{T}, without resorting to the practically unwieldy doubling trick. • Finally, we demonstrate the superiority of our algorithm through a number of numerical experiments. 2 Related Works Online learning with long-term constraints was first studied by Mannor et al. 2009 . In the context of two-player infinite-horizon stochastic games, they established a fundamental impossibility result: it is not possible to simultaneously achieve sublinear bounds for both regret as well as cumulative constraint violation (CCV) against the best fixed offline action that satisfies the long-term constraint over the entire horizon. This negative result motivated subsequent works to consider a weaker benchmark, in which the benchmark satisfies the constraints at every round ( Mahdavi et al. 2012 ; Neely and Yu 2017 ; Guo et al. 2022 ) . The goal in this line of work is to obtain the tightest regret and CCV bounds under this assumption. For time-invariant constraints, Mahdavi et al. 2012 were the first to use Online Gradient Descent (OGD) and mirror prox-based online policies to obtain sublinear regret and sublinear CCV guarantees. Later, Castiglioni et al. 2022 proposed a unified meta-algorithm that achieves \mathcal{O}(T^{\nicefrac{{3}}{{4}}}) bounds for both approximate regret and CCV in the non-convex setting with long-term constraints. However, they made an additional Slater’s condition (strict feasibility) assumption and the assumption that the constraint functions change no faster than O(T^{-\nicefrac{{1}}{{4}}}) . Guo et al. 2022 studied the problem with adversarial constraints, and achieved O(\sqrt{T}) regret and O(T^{\nicefrac{{3}}{{4}}}) CCV in the general setting without assuming Slater’s condition.