# An Optimistic Algorithm for Online Convex Optimization with Adversarial Constraints

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 33 references that are in the map.
- First posted on arXiv 11 Dec 2024.

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

- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Optimization, Learning, and Games with Predictable Sequences](https://mlsanity.com/paper/1311.1869/) (2013)
- [Fast Convergence of Regularized Learning in Games](https://mlsanity.com/paper/1507.00407/) (2015)
- [Adaptive Online Learning in Dynamic Environments](https://mlsanity.com/paper/1810.10815/) (2018)
- [Online Optimization : Competing with Dynamic Comparators](https://mlsanity.com/paper/1501.06225/) (2015)
- [Dynamic Regret of Convex and Smooth Functions](https://mlsanity.com/paper/2007.03479/) (2020)
- [Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization](https://mlsanity.com/paper/2112.14368/) (2021)
- [Adaptive Algorithms for Online Convex Optimization with Long-term Constraints](https://mlsanity.com/paper/1512.07422/) (2015)
- [Online Convex Optimization with Time-Varying Constraints](https://mlsanity.com/paper/1702.04783/) (2017)
- [Online Learning with Imperfect Hints](https://mlsanity.com/paper/2002.04726/) (2020)
- [Optimal Algorithms for Online Convex Optimization with Adversarial Constraints](https://mlsanity.com/paper/2310.18955/) (2023)
- [A Modular Analysis of Adaptive (Non-)Convex Optimization: Optimism, Composite Objectives, and Variational Bounds](https://mlsanity.com/paper/1709.02726/) (2017)
- [Taking a hint: How to leverage loss predictors in contextual bandits?](https://mlsanity.com/paper/2003.01922/) (2020)
- [Distributed Online Convex Optimization with Adversarial Constraints: Reduced Cumulative Constraint Violation Bounds under Slater's Condition](https://mlsanity.com/paper/2306.00149/) (2023)
- [Gradient-Variation Bound for Online Convex Optimization with Constraints](https://mlsanity.com/paper/2006.12455/) (2020)
- [Adaptive Composite Online Optimization: Predictions in Static and Dynamic Environments](https://mlsanity.com/paper/2205.00446/) (2022)
- [Lazy Lagrangians with Predictions for Online Learning](https://mlsanity.com/paper/2201.02890/) (2022)
- [Optimistic and Adaptive Lagrangian Hedging](https://mlsanity.com/paper/2101.09603/) (2021)
- [Online Convex Optimization with Long Term Constraints for Predictable Sequences](https://mlsanity.com/paper/2210.16735/) (2022)

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

- [An Optimistic Algorithm for online CMDPS with Anytime Adversarial Constraints](https://mlsanity.com/paper/2505.21841/) (2025)
- [Universal Dynamic Regret and Constraint Violation Bounds for Constrained Online Convex Optimization](https://mlsanity.com/paper/2510.01867/) (2025)
- [Online Omniprediction with Long-Term Constraints](https://mlsanity.com/paper/2509.11357/) (2025)
- [Online Learning with Gradient-Variation Interval Regret](https://mlsanity.com/paper/2606.03831/) (2026)
- [Constrained Online Convex Optimization without Slater's Condition](https://mlsanity.com/paper/2606.31480/) (2026)
- [Optimal Anytime Algorithms for Online Convex Optimization with Adversarial Constraints](https://mlsanity.com/paper/2510.22579/) (2025)
- [Optimal Bounds for Adversarial Constrained Online Convex Optimization](https://mlsanity.com/paper/2503.13366/) (2025)
- [Optimistic Learning for Communication Networks](https://mlsanity.com/paper/2504.03499/) (2025)
- [Dynamic Regret Bounds for Online Omniprediction with Long Term Constraints](https://mlsanity.com/paper/2510.07266/) (2025)
- [Constrained Online Convex Optimization with Memory and Predictions](https://mlsanity.com/paper/2603.21375/) (2026)
- [Constrained Online Learning with Noisy Constraint Values](https://mlsanity.com/paper/2609.06921/) (2026)

## Abstract (arXiv)

We study Online Convex Optimization (OCO) with adversarial constraints, where an online algorithm must make sequential decisions to minimize both convex loss functions and cumulative constraint violations. We focus on a setting where the algorithm has access to predictions of the loss and constraint functions. Our results show that we can improve the current best bounds of  O(√T)  regret and  tildeO(√T)  cumulative constraint violations to  O(√ET(f))  and  tildeO(√ET(g^+)) , respectively, where  ET(f)  and ET(g^+) represent the cumulative prediction errors of the loss and constraint functions. In the worst case, where ET(f) = O(T)  and  ET(g^+) = O(T)  (assuming bounded gradients of the loss and constraint functions), our rates match the prior  O(√T)  results. However, when the loss and constraint predictions are accurate, our approach yields significantly smaller regret and cumulative constraint violations. Finally, we apply this to the setting of adversarial contextual bandits with sequential risk constraints, obtaining optimistic bounds O (√ET(f) T1/3) regret and O(√ET(g^+) T1/3) constraints violation, yielding better performance than existing results when prediction quality is sufficiently high.