# Online Convex Optimization Using Predictions

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Apr 2015.

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

- [Revisiting Smoothed Online Learning](https://mlsanity.com/paper/2102.06933/) (2021)
- [Adversarial Tracking Control via Strongly Adaptive Online Learning with Memory](https://mlsanity.com/paper/2102.01623/) (2021)
- [Smoothed Online Optimization with Unreliable Predictions](https://mlsanity.com/paper/2202.03519/) (2022)
- [Online Convex Optimization with Continuous Switching Constraint](https://mlsanity.com/paper/2103.11370/) (2021)
- [Adaptive Composite Online Optimization: Predictions in Static and Dynamic Environments](https://mlsanity.com/paper/2205.00446/) (2022)
- [Online Optimization with Feedback Delay and Nonlinear Switching Cost](https://mlsanity.com/paper/2111.00095/) (2021)
- [Lazy Lagrangians with Predictions for Online Learning](https://mlsanity.com/paper/2201.02890/) (2022)
- [Adaptive Online Non-stochastic Control](https://mlsanity.com/paper/2310.02261/) (2023)
- [Optimistic Online Non-stochastic Control via FTRL](https://mlsanity.com/paper/2404.03309/) (2024)
- [Reinforcement Learning with Imperfect Transition Predictions: A Bellman-Jensen Approach](https://mlsanity.com/paper/2510.18687/) (2025)
- [Balancing Forecast Accuracy and Switching Costs in Online Optimization of Energy Management Systems](https://mlsanity.com/paper/2407.03368/) (2024)
- [Online Optimization and Ambiguity-based Learning of Distributionally Uncertain Dynamic Systems](https://mlsanity.com/paper/2102.09111/) (2021)
- [Smoothed Online Combinatorial Optimization Using Imperfect Predictions](https://mlsanity.com/paper/2204.10979/) (2022)
- [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)
- [Smoothed Online Optimization for Target Tracking: Robust and Learning-Augmented Algorithms](https://mlsanity.com/paper/2509.05930/) (2025)

## Abstract (arXiv)

Making use of predictions is a crucial, but under-explored, area of online algorithms. This paper studies a class of online optimization problems where we have external noisy predictions available. We propose a stochastic prediction error model that generalizes prior models in the learning and stochastic control communities, incorporates correlation among prediction errors, and captures the fact that predictions improve as time passes. We prove that achieving sublinear regret and constant competitive ratio for online algorithms requires the use of an unbounded prediction window in adversarial settings, but that under more realistic stochastic prediction error models it is possible to use Averaging Fixed Horizon Control (AFHC) to simultaneously achieve sublinear regret and constant competitive ratio in expectation using only a constant-sized prediction window. Furthermore, we show that the performance of AFHC is tightly concentrated around its mean.