# Online Convex Optimization with Switching Cost and Delayed Gradients

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 34 references that are in the map.
- First posted on arXiv 18 Oct 2023.

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

- [Non-stationary Stochastic Optimization](https://mlsanity.com/paper/1307.5449/) (2013)
- [Online Optimization : Competing with Dynamic Comparators](https://mlsanity.com/paper/1501.06225/) (2015)
- [Tracking Slowly Moving Clairvoyant: Optimal Dynamic Regret of Online Learning with True and Noisy Gradient](https://mlsanity.com/paper/1605.04638/) (2016)
- [Improved Dynamic Regret for Non-degenerate Functions](https://mlsanity.com/paper/1608.03933/) (2016)
- [Dynamical Models and Tracking Regret in Online Convex Programming](https://mlsanity.com/paper/1301.1254/) (2013)
- [Bandit Convex Optimization in Non-stationary Environments](https://mlsanity.com/paper/1907.12340/) (2019)
- [Smoothed Online Convex Optimization in High Dimensions via Online Balanced Descent](https://mlsanity.com/paper/1803.10366/) (2018)
- [Improved Analysis for Dynamic Regret of Strongly Convex and Smooth Functions](https://mlsanity.com/paper/2006.05876/) (2020)
- [Beyond Online Balanced Descent: An Optimal Algorithm for Smoothed Online Optimization](https://mlsanity.com/paper/1905.12776/) (2019)
- [Minimizing Dynamic Regret and Adaptive Regret Simultaneously](https://mlsanity.com/paper/2002.02085/) (2020)
- [Revisiting Smoothed Online Learning](https://mlsanity.com/paper/2102.06933/) (2021)
- [Online Optimization with Predictions and Switching Costs: Fast Algorithms and the Fundamental Limit](https://mlsanity.com/paper/1801.07780/) (2018)
- [Smoothed Online Optimization for Regression and Control](https://mlsanity.com/paper/1810.10132/) (2018)
- [Bandit Convex Optimization for Scalable and Dynamic IoT Management](https://mlsanity.com/paper/1707.09060/) (2017)
- [A Tale of Two Metrics: Simultaneous Bounds on Competitiveness and Regret](https://mlsanity.com/paper/1508.03769/) (2015)
- [Simultaneously Achieving Sublinear Regret and Constraint Violations for Online Convex Optimization with Time-varying Constraints](https://mlsanity.com/paper/2111.07707/) (2021)
- [Dimension-Free Bounds on Chasing Convex Functions](https://mlsanity.com/paper/2005.14058/) (2020)
- [Optimal Algorithms for Right-Sizing Data Centers- Extended Version](https://mlsanity.com/paper/1807.05112/) (2018)
- [On Dynamic Regret and Constraint Violations in Constrained Online Convex Optimization](https://mlsanity.com/paper/2301.09808/) (2023)

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

- [Online Convex Optimization with Switching Cost with Only One Single Gradient Evaluation](https://mlsanity.com/paper/2507.04133/) (2025)
- [Capacity Provisioning Motivated Online Non-Convex Optimization Problem with Memory and Switching Cost](https://mlsanity.com/paper/2403.17480/) (2024)
- [SCaLE: Switching Cost aware Learning and Exploration](https://mlsanity.com/paper/2601.09042/) (2026)

## Abstract (arXiv)

We consider the online convex optimization (OCO) problem with quadratic and linear switching cost in the limited information setting, where an online algorithm can choose its action using only gradient information about the previous objective function. For L-smooth and μ-strongly convex objective functions, we propose an online multiple gradient descent (OMGD) algorithm and show that its competitive ratio for the OCO problem with quadratic switching cost is at most 4(L + 5) + frac16(L + 5)μ. The competitive ratio upper bound for OMGD is also shown to be order-wise tight in terms of L,μ. In addition, we show that the competitive ratio of any online algorithm is maxOmega(L), Omega(fracL√μ) in the limited information setting when the switching cost is quadratic. We also show that the OMGD algorithm achieves the optimal (order-wise) dynamic regret in the limited information setting. For the linear switching cost, the competitive ratio upper bound of the OMGD algorithm is shown to depend on both the path length and the squared path length of the problem instance, in addition to L, μ, and is shown to be order-wise, the best competitive ratio any online algorithm can achieve. Consequently, we conclude that the optimal competitive ratio for the quadratic and linear switching costs are fundamentally different in the limited information setting.