# Online Convex Optimization with Continuous Switching Constraint

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 53 references that are in the map.
- First posted on arXiv 21 Mar 2021.

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

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Adaptive Online Learning in Dynamic Environments](https://mlsanity.com/paper/1810.10815/) (2018)
- [A Second-order Bound with Excess Losses](https://mlsanity.com/paper/1402.2044/) (2014)
- [Online Convex Optimization with Stochastic Constraints](https://mlsanity.com/paper/1708.03741/) (2017)
- [Adaptive Algorithms for Online Convex Optimization with Long-term Constraints](https://mlsanity.com/paper/1512.07422/) (2015)
- [Thinking Fast and Slow: Optimization Decomposition Across Timescales](https://mlsanity.com/paper/1704.07785/) (2017)
- [Online Convex Optimization with Time-Varying Constraints](https://mlsanity.com/paper/1702.04783/) (2017)
- [Linear Bandits with Limited Adaptivity and Learning Distributional Optimal Design](https://mlsanity.com/paper/2007.01980/) (2020)
- [MetaGrad: Multiple Learning Rates in Online Learning](https://mlsanity.com/paper/1604.08740/) (2016)
- [Bandits with Switching Costs: T^{2/3} Regret](https://mlsanity.com/paper/1310.2997/) (2013)
- [Lipschitz Adaptivity with Multiple Learning Rates in Online Learning](https://mlsanity.com/paper/1902.10797/) (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)
- [Revisiting Smoothed Online Learning](https://mlsanity.com/paper/2102.06933/) (2021)
- [Distributed Online Convex Optimization with Time-Varying Coupled Inequality Constraints](https://mlsanity.com/paper/1903.04277/) (2019)
- [Smoothed Online Optimization for Regression and Control](https://mlsanity.com/paper/1810.10132/) (2018)
- [Adaptive Regret of Convex and Smooth Functions](https://mlsanity.com/paper/1904.11681/) (2019)
- [Online learning over a finite action set with limited switching](https://mlsanity.com/paper/1803.01548/) (2018)
- [Minimax Regret of Switching-Constrained Online Convex Optimization: No Phase Transition](https://mlsanity.com/paper/1910.10873/) (2019)
- [Online Convex Optimization Using Predictions](https://mlsanity.com/paper/1504.06681/) (2015)
- [Adaptivity and Optimality: A Universal Algorithm for Online Convex Optimization](https://mlsanity.com/paper/1905.05917/) (2019)
- [Dual Adaptivity: A Universal Algorithm for Minimizing the Adaptive Regret of Convex Functions](https://mlsanity.com/paper/1906.10851/) (2019)
- [Lazy OCO: Online Convex Optimization on a Switching Budget](https://mlsanity.com/paper/2102.03803/) (2021)
- [Online Learning for Changing Environments using Coin Betting](https://mlsanity.com/paper/1711.02545/) (2017)
- [Online Convex Optimization with Perturbed Constraints](https://mlsanity.com/paper/1906.00049/) (2019)
- [Multinomial Logit Bandit with Low Switching Cost](https://mlsanity.com/paper/2007.04876/) (2020)

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

- [Optimal Comparator Adaptive Online Learning with Switching Cost](https://mlsanity.com/paper/2205.06846/) (2022)
- [A Survey on Distributed Online Optimization and Game](https://mlsanity.com/paper/2205.00473/) (2022)
- [Online Decision Making with History-Average Dependent Costs (Extended)](https://mlsanity.com/paper/2312.06641/) (2023)
- [Fairness-Regularized Online Optimization with Switching Costs](https://mlsanity.com/paper/2512.11131/) (2025)
- [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)

In many sequential decision making applications, the change of decision would bring an additional cost, such as the wear-and-tear cost associated with changing server status. To control the switching cost, we introduce the problem of online convex optimization with continuous switching constraint, where the goal is to achieve a small regret given a budget on the overall switching cost. We first investigate the hardness of the problem, and provide a lower bound of order Omega(√T) when the switching cost budget S=Omega(√T), and Omega(minfracTS,T) when S=O(√T), where T is the time horizon. The essential idea is to carefully design an adaptive adversary, who can adjust the loss function according to the cumulative switching cost of the player incurred so far based on the orthogonal technique. We then develop a simple gradient-based algorithm which enjoys the minimax optimal regret bound. Finally, we show that, for strongly convex functions, the regret bound can be improved to O(log T) for S=Omega(log T), and O(minT/exp(S)+S,T) for S=O(log T).