# Constrained Online Convex Optimization with Memory and Predictions

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 20 of its 35 references that are in the map.
- First posted on arXiv 22 Mar 2026.

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

- [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)
- [Online convex optimization for cumulative constraints](https://mlsanity.com/paper/1802.06472/) (2018)
- [Online Optimal Control with Linear Dynamics and Predictions: Algorithms and Regret Analysis](https://mlsanity.com/paper/1906.11378/) (2019)
- [Optimal Algorithms for Online Convex Optimization with Adversarial Constraints](https://mlsanity.com/paper/2310.18955/) (2023)
- [Online Learning with Optimism and Delay](https://mlsanity.com/paper/2106.06885/) (2021)
- [The Power of Predictions in Online Control](https://mlsanity.com/paper/2006.07569/) (2020)
- [On the Regret Analysis of Online LQR Control with Predictions](https://mlsanity.com/paper/2102.01309/) (2021)
- [Online Optimal Control with Affine Constraints](https://mlsanity.com/paper/2010.04891/) (2020)
- [Robustness and Consistency in Linear Quadratic Control with Untrusted Predictions](https://mlsanity.com/paper/2106.09659/) (2021)
- [Safe Online Convex Optimization with Unknown Linear Safety Constraints](https://mlsanity.com/paper/2111.07430/) (2021)
- [Online Convex Optimization with Perturbed Constraints](https://mlsanity.com/paper/1906.00049/) (2019)
- [An Optimistic Algorithm for Online Convex Optimization with Adversarial Constraints](https://mlsanity.com/paper/2412.08060/) (2024)
- [Competitive Control with Delayed Imperfect Information](https://mlsanity.com/paper/2010.11637/) (2020)
- [Gradient-Variation Bound for Online Convex Optimization with Constraints](https://mlsanity.com/paper/2006.12455/) (2020)
- [Online Nonstochastic Control with Adversarial and Static Constraints](https://mlsanity.com/paper/2302.02426/) (2023)
- [Revisiting Projection-Free Online Learning with Time-Varying Constraints](https://mlsanity.com/paper/2501.16046/) (2025)
- [An online convex optimization algorithm for controlling linear systems with state and input constraints](https://mlsanity.com/paper/2005.11308/) (2020)
- [Optimistic Online Non-stochastic Control via FTRL](https://mlsanity.com/paper/2404.03309/) (2024)
- [Doubly-Bounded Queue for Constrained Online Learning: Keeping Pace with Dynamics of Both Loss and Constraint](https://mlsanity.com/paper/2412.10703/) (2024)

## Abstract (arXiv)

We study Constrained Online Convex Optimization with Memory (COCO-M), where both the loss and the constraints depend on a finite window of past decisions made by the learner. This setting extends the previously studied unconstrained online optimization with memory framework and captures practical problems such as the control of constrained dynamical systems and scheduling with reconfiguration budgets. For this problem, we propose the first algorithms that achieve sublinear regret and sublinear cumulative constraint violation under time-varying constraints, both with and without predictions of future loss and constraint functions. Without predictions, we introduce an adaptive penalty approach that guarantees sublinear regret and constraint violation. When short-horizon and potentially unreliable predictions are available, we reinterpret the problem as online learning with delayed feedback and design an optimistic algorithm whose performance improves as prediction accuracy improves, while remaining robust when predictions are inaccurate. Our results bridge the gap between classical constrained online convex optimization and memory-dependent settings, and provide a versatile learning toolbox with diverse applications.