# Lazy OCO: Online Convex Optimization on a Switching Budget

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 63 references that are in the map.
- First posted on arXiv 7 Feb 2021.

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

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [How to Escape Saddle Points Efficiently](https://mlsanity.com/paper/1703.00887/) (2017)
- [Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition](https://mlsanity.com/paper/1503.02101/) (2015)
- [Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysis](https://mlsanity.com/paper/1702.03849/) (2017)
- [Theoretical guarantees for approximate sampling from smooth and log-concave densities](https://mlsanity.com/paper/1412.7392/) (2014)
- [Underdamped Langevin MCMC: A non-asymptotic analysis](https://mlsanity.com/paper/1707.03663/) (2017)
- [Non-convex Optimization for Machine Learning](https://mlsanity.com/paper/1712.07897/) (2017)
- [Online Control with Adversarial Disturbances](https://mlsanity.com/paper/1902.08721/) (2019)
- [Learning Linear-Quadratic Regulators Efficiently with only √T Regret](https://mlsanity.com/paper/1902.06223/) (2019)
- [Online Learning with Switching Costs and Other Adaptive Adversaries](https://mlsanity.com/paper/1302.4387/) (2013)
- [Online Linear Quadratic Control](https://mlsanity.com/paper/1806.07104/) (2018)
- [Sampling from a log-concave distribution with Projected Langevin Monte Carlo](https://mlsanity.com/paper/1507.02564/) (2015)
- [The Price of Differential Privacy For Online Learning](https://mlsanity.com/paper/1701.07953/) (2017)
- [Logarithmic Regret for Adversarial Online Control](https://mlsanity.com/paper/2003.00189/) (2020)
- [Bandits with Switching Costs: T^{2/3} Regret](https://mlsanity.com/paper/1310.2997/) (2013)
- [Logarithmic Regret for Online Control](https://mlsanity.com/paper/1909.05062/) (2019)
- [Smoothed Online Convex Optimization in High Dimensions via Online Balanced Descent](https://mlsanity.com/paper/1803.10366/) (2018)
- [Beyond Online Balanced Descent: An Optimal Algorithm for Smoothed Online Optimization](https://mlsanity.com/paper/1905.12776/) (2019)
- [Online learning over a finite action set with limited switching](https://mlsanity.com/paper/1803.01548/) (2018)
- [A Tale of Two Metrics: Simultaneous Bounds on Competitiveness and Regret](https://mlsanity.com/paper/1508.03769/) (2015)
- [Minimax Regret of Switching-Constrained Online Convex Optimization: No Phase Transition](https://mlsanity.com/paper/1910.10873/) (2019)
- [Prediction by Random-Walk Perturbation](https://mlsanity.com/paper/1302.5797/) (2013)
- [Bandits with Movement Costs and Adaptive Pricing](https://mlsanity.com/paper/1702.07444/) (2017)
- [Multi-Armed Bandits with Metric Movement Costs](https://mlsanity.com/paper/1710.08997/) (2017)

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

- [Private Online Prediction from Experts: Separations and Faster Rates](https://mlsanity.com/paper/2210.13537/) (2022)
- [Optimal Comparator Adaptive Online Learning with Switching Cost](https://mlsanity.com/paper/2205.06846/) (2022)
- [Online Convex Optimization with Continuous Switching Constraint](https://mlsanity.com/paper/2103.11370/) (2021)
- [Online Decision Making for Trading Wind Energy](https://mlsanity.com/paper/2209.02009/) (2022)
- [Improved Differentially Private and Lazy Online Convex Optimization](https://mlsanity.com/paper/2312.11534/) (2023)
- [Private Online Learning via Lazy Algorithms](https://mlsanity.com/paper/2406.03620/) (2024)
- [Partially Lazy Gradient Descent for Smoothed Online Learning](https://mlsanity.com/paper/2601.15984/) (2026)
- [No-Regret Learning in Two-Echelon Supply Chain with Unknown Demand Distribution](https://mlsanity.com/paper/2210.12663/) (2022)
- [Federated Online Prediction from Experts with Differential Privacy: Separations and Regret Speed-ups](https://mlsanity.com/paper/2409.19092/) (2024)
- [Allocating Divisible Resources on Arms with Unknown and Random Rewards](https://mlsanity.com/paper/2306.16578/) (2023)
- [Fairness-Regularized Online Optimization with Switching Costs](https://mlsanity.com/paper/2512.11131/) (2025)
- [Provably Optimal Learning Algorithms for Assistance Games](https://mlsanity.com/paper/2607.08012/) (2026)
- [Beyond Binary: Continuous State Optimization with Graph-Structured Objectives](https://mlsanity.com/paper/2608.09366/) (2026)
- [Dynamic Regret in Online Convex Optimization with Indicator Switching Costs](https://mlsanity.com/paper/2609.30556/) (2026)

## Abstract (arXiv)

We study a variant of online convex optimization where the player is permitted to switch decisions at most S times in expectation throughout T rounds. Similar problems have been addressed in prior work for the discrete decision set setting, and more recently in the continuous setting but only with an adaptive adversary. In this work, we aim to fill the gap and present computationally efficient algorithms in the more prevalent oblivious setting, establishing a regret bound of O(T/S) for general convex losses and widetilde O(T/S2) for strongly convex losses. In addition, for stochastic i.i.d.~losses, we present a simple algorithm that performs log T switches with only a multiplicative log T factor overhead in its regret in both the general and strongly convex settings. Finally, we complement our algorithms with lower bounds that match our upper bounds in some of the cases we consider.