# Online Optimization with Predictions and Switching Costs: Fast Algorithms and the Fundamental Limit

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

## Key facts

- Cited by 27 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Jan 2018.

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

- [Chasing Convex Bodies and Functions with Black-Box Advice](https://mlsanity.com/paper/2206.11780/) (2022)
- [A Near-Optimal Algorithm for Safe Reinforcement Learning Under Instantaneous Hard Constraints](https://mlsanity.com/paper/2302.04375/) (2023)
- [Optimal Comparator Adaptive Online Learning with Switching Cost](https://mlsanity.com/paper/2205.06846/) (2022)
- [Sequential Strategic Screening](https://mlsanity.com/paper/2301.13397/) (2023)
- [Expert-Calibrated Learning for Online Optimization with Switching Costs](https://mlsanity.com/paper/2204.08572/) (2022)
- [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)
- [Near-Optimal Adversarial Reinforcement Learning with Switching Costs](https://mlsanity.com/paper/2302.04374/) (2023)
- [Robustified Learning for Online Optimization with Memory Costs](https://mlsanity.com/paper/2305.00677/) (2023)
- [Online Control-Informed Learning](https://mlsanity.com/paper/2410.03924/) (2024)
- [Online Convex Optimization with Switching Cost and Delayed Gradients](https://mlsanity.com/paper/2310.11880/) (2023)
- [Robust Learning for Smoothed Online Convex Optimization with Feedback Delay](https://mlsanity.com/paper/2310.20098/) (2023)
- [Reinforcement Learning with Imperfect Transition Predictions: A Bellman-Jensen Approach](https://mlsanity.com/paper/2510.18687/) (2025)
- [Parameter-free Dynamic Regret: Time-varying Movement Costs, Delayed Feedback, and Memory](https://mlsanity.com/paper/2602.06902/) (2026)
- [Active View Selection with Perturbed Gaussian Ensemble for Tomographic Reconstruction](https://mlsanity.com/paper/2603.06852/) (2026)
- [AC3S: Adaptive Conditioning for 3D-Aware Synthetic Data Generation](https://mlsanity.com/paper/2606.31204/) (2026)
- [OpReg-Boost: Learning to Accelerate Online Algorithms with Operator Regression](https://mlsanity.com/paper/2105.13271/) (2021)
- [Personalized incentives as feedback design in generalized Nash equilibrium problems](https://mlsanity.com/paper/2203.12948/) (2022)
- [A Survey on Distributed Online Optimization and Game](https://mlsanity.com/paper/2205.00473/) (2022)
- [RASteer: Retain-Aware Activation Steering for Concept Erasure in Diffusion Models](https://mlsanity.com/paper/2610.01969/) (2026)
- [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)
- [Online Convex Optimization with Memory and Limited Predictions](https://mlsanity.com/paper/2410.23574/) (2024)
- [A Hybrid Stochastic Gradient Tracking Method for Distributed Online Optimization Over Time-Varying Directed Networks](https://mlsanity.com/paper/2508.20645/) (2025)
- [Bi-Level Online Provisioning and Scheduling with Switching Costs and Cross-Level Constraints](https://mlsanity.com/paper/2601.18936/) (2026)
- [AlphaWiSE: Adaptive Weight Interpolation for Continual Multimodal Representation Learning](https://mlsanity.com/paper/2607.15094/) (2026)
- [Continual Concept Erasure in Diffusion Models by Suppressing Cross-Edit Interference](https://mlsanity.com/paper/2610.01989/) (2026)

## Abstract (arXiv)

This paper studies an online optimization problem with a finite prediction window of cost functions and additional switching costs on decisions. We propose two gradient-based online algorithms: Receding Horizon Gradient Descent (RHGD), and Receding Horizon Accelerated Gradient (RHAG). Both algorithms only require a finite number of projected gradient evaluations at each stage. We provide upper bounds on the dynamic regrets of the proposed algorithms and show that the regret upper bounds decay exponentially with the length of the prediction window. Moreover, we study the fundamental lower bound on the dynamic regret for a broad class of deterministic online algorithms. The lower bound is close to RHAG's regret upper bound, indicating that our gradient-based RHAG is a near-optimal online algorithm. Finally, we conduct numerical experiments to complement our theoretical analysis.