# Online Convex Optimization with Memory and Limited Predictions

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 19 of its 43 references that are in the map.
- First posted on arXiv 31 Oct 2024.

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

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedback](https://mlsanity.com/paper/1507.08752/) (2015)
- [Online Optimization : Competing with Dynamic Comparators](https://mlsanity.com/paper/1501.06225/) (2015)
- [Online Control with Adversarial Disturbances](https://mlsanity.com/paper/1902.08721/) (2019)
- [Improper Learning for Non-Stochastic Control](https://mlsanity.com/paper/2001.09254/) (2020)
- [A Theoretical and Empirical Comparison of Gradient Approximations in Derivative-Free Optimization](https://mlsanity.com/paper/1905.01332/) (2019)
- [Tracking Slowly Moving Clairvoyant: Optimal Dynamic Regret of Online Learning with True and Noisy Gradient](https://mlsanity.com/paper/1605.04638/) (2016)
- [Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2209.05045/) (2022)
- [Bandit Convex Optimization in Non-stationary Environments](https://mlsanity.com/paper/1907.12340/) (2019)
- [Online Optimal Control with Linear Dynamics and Predictions: Algorithms and Regret Analysis](https://mlsanity.com/paper/1906.11378/) (2019)
- [Non-stationary Online Learning with Memory and Non-stochastic Control](https://mlsanity.com/paper/2102.03758/) (2021)
- [Online Optimization with Predictions and Switching Costs: Fast Algorithms and the Fundamental Limit](https://mlsanity.com/paper/1801.07780/) (2018)
- [An optimal algorithm for bandit convex optimization](https://mlsanity.com/paper/1603.04350/) (2016)
- [Online Convex Optimization Using Predictions](https://mlsanity.com/paper/1504.06681/) (2015)
- [Online Convex Optimization with Unbounded Memory](https://mlsanity.com/paper/2210.09903/) (2022)
- [Efficient Online Learning with Memory via Frank-Wolfe Optimization: Algorithms with Bounded Dynamic Regret and Applications to Control](https://mlsanity.com/paper/2301.00497/) (2023)
- [Online Actuator Selection and Controller Design for Linear Quadratic Regulation with Unknown System Model](https://mlsanity.com/paper/2201.10197/) (2022)
- [Learning Decentralized Linear Quadratic Regulators with √T Regret](https://mlsanity.com/paper/2210.08886/) (2022)

## Abstract (arXiv)

This paper addresses an online convex optimization problem where the cost function at each step depends on a history of past decisions (i.e., memory), and the decision maker has access to limited predictions of future cost values within a finite window. The goal is to design an algorithm that minimizes the dynamic regret against the optimal sequence of decisions in hindsight. To this end, we propose a novel predictive algorithm and establish strong theoretical guarantees for its performance. We show that the algorithm's dynamic regret decays exponentially with the length of the prediction window. Our algorithm comprises two general subroutines of independent interest. The first subroutine solves online convex optimization with memory and bandit feedback, achieving a √TVT-dynamic regret, where VT measures the variation of the optimal decision sequence. The second is a zeroth-order method that attains a linear convergence rate for general convex optimization, matching the best achievable rate of first-order methods. The key to our algorithm is a novel truncated Gaussian smoothing technique when querying the decision points to obtain the predictions. We validate our theoretical results with numerical experiments.