# Online Convex Optimization with Unbounded Memory

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 67 references that are in the map.
- First posted on arXiv 18 Oct 2022.

## Builds on (most cited first, 30 of 31)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [CVXPY: A Python-Embedded Modeling Language for Convex Optimization](https://mlsanity.com/paper/1603.00943/) (2016)
- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Performative Prediction](https://mlsanity.com/paper/2002.06673/) (2020)
- [A Rewriting System for Convex Optimization Problems](https://mlsanity.com/paper/1709.04494/) (2017)
- [Naive Exploration is Optimal for Online LQR](https://mlsanity.com/paper/2001.09576/) (2020)
- [Outside the Echo Chamber: Optimizing the Performative Risk](https://mlsanity.com/paper/2102.08570/) (2021)
- [Stochastic Optimization for Performative Prediction](https://mlsanity.com/paper/2006.06887/) (2020)
- [Online Control with Adversarial Disturbances](https://mlsanity.com/paper/1902.08721/) (2019)
- [Performative Prediction in a Stateful World](https://mlsanity.com/paper/2011.03885/) (2020)
- [Regret Bounds for Robust Adaptive Control of the Linear Quadratic Regulator](https://mlsanity.com/paper/1805.09388/) (2018)
- [Kernel-based methods for bandit convex optimization](https://mlsanity.com/paper/1607.03084/) (2016)
- [The Nonstochastic Control Problem](https://mlsanity.com/paper/1911.12178/) (2019)
- [Bandit Convex Optimization in Non-stationary Environments](https://mlsanity.com/paper/1907.12340/) (2019)
- [Logarithmic Regret for Adversarial Online Control](https://mlsanity.com/paper/2003.00189/) (2020)
- [Regret Minimization with Performative Feedback](https://mlsanity.com/paper/2202.00628/) (2022)
- [Logarithmic Regret for Online Control](https://mlsanity.com/paper/1909.05062/) (2019)
- [Non-stationary Online Learning with Memory and Non-stochastic Control](https://mlsanity.com/paper/2102.03758/) (2021)
- [Online Non-Convex Learning: Following the Perturbed Leader is Optimal](https://mlsanity.com/paper/1903.08110/) (2019)
- [Decision-Dependent Risk Minimization in Geometrically Decaying Dynamic Environments](https://mlsanity.com/paper/2204.08281/) (2022)
- [Online learning over a finite action set with limited switching](https://mlsanity.com/paper/1803.01548/) (2018)
- [An optimal algorithm for bandit convex optimization](https://mlsanity.com/paper/1603.04350/) (2016)
- [Online Optimal Control with Affine Constraints](https://mlsanity.com/paper/2010.04891/) (2020)
- [Minimax Regret of Switching-Constrained Online Convex Optimization: No Phase Transition](https://mlsanity.com/paper/1910.10873/) (2019)
- [Non-Stochastic Control with Bandit Feedback](https://mlsanity.com/paper/2008.05523/) (2020)
- [Online Control of Unknown Time-Varying Dynamical Systems](https://mlsanity.com/paper/2202.07890/) (2022)
- [Bandit Linear Control](https://mlsanity.com/paper/2007.00759/) (2020)
- [A System Level Approach to Controller Synthesis](https://mlsanity.com/paper/1610.04815/) (2016)
- [Online learning with dynamics: A minimax perspective](https://mlsanity.com/paper/2012.01705/) (2020)

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

- [Explore-then-Commit for Nonstationary Linear Bandits with Latent Dynamics](https://mlsanity.com/paper/2510.16208/) (2025)
- [Stochastic Contextual Bandits with Long Horizon Rewards](https://mlsanity.com/paper/2302.00814/) (2023)
- [Capacity Provisioning Motivated Online Non-Convex Optimization Problem with Memory and Switching Cost](https://mlsanity.com/paper/2403.17480/) (2024)
- [Online Convex Optimization with Memory and Limited Predictions](https://mlsanity.com/paper/2410.23574/) (2024)
- [Online Multi-Agent Control with Adversarial Disturbances](https://mlsanity.com/paper/2506.18814/) (2025)
- [Smoothed Online Optimization for Target Tracking: Robust and Learning-Augmented Algorithms](https://mlsanity.com/paper/2509.05930/) (2025)

## Abstract (arXiv)

Online convex optimization (OCO) is a widely used framework in online learning. In each round, the learner chooses a decision in a convex set and an adversary chooses a convex loss function, and then the learner suffers the loss associated with their current decision. However, in many applications the learner's loss depends not only on the current decision but on the entire history of decisions until that point. The OCO framework and its existing generalizations do not capture this, and they can only be applied to many settings of interest after a long series of approximation arguments. They also leave open the question of whether the dependence on memory is tight because there are no non-trivial lower bounds. In this work we introduce a generalization of the OCO framework, "Online Convex Optimization with Unbounded Memory", that captures long-term dependence on past decisions. We introduce the notion of p-effective memory capacity, Hp, that quantifies the maximum influence of past decisions on present losses. We prove an O(√Hp T) upper bound on the policy regret and a matching (worst-case) lower bound. As a special case, we prove the first non-trivial lower bound for OCO with finite memory citepanavaHM2015online, which could be of independent interest, and also improve existing upper bounds. We demonstrate the broad applicability of our framework by using it to derive regret bounds, and to improve and simplify existing regret bound derivations, for a variety of online learning problems including online linear control and an online variant of performative prediction.