# Online Convex Optimization with Switching Cost with Only One Single Gradient Evaluation

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 13 references that are in the map.
- First posted on arXiv 5 Jul 2025.

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

- [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)
- [Smoothed Online Optimization for Regression and Control](https://mlsanity.com/paper/1810.10132/) (2018)
- [A Tale of Two Metrics: Simultaneous Bounds on Competitiveness and Regret](https://mlsanity.com/paper/1508.03769/) (2015)
- [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)
- [Chasing Convex Functions with Long-term Constraints](https://mlsanity.com/paper/2402.14012/) (2024)
- [Online Convex Optimization with Switching Cost and Delayed Gradients](https://mlsanity.com/paper/2310.11880/) (2023)

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

- [SCaLE: Switching Cost aware Learning and Exploration](https://mlsanity.com/paper/2601.09042/) (2026)

## Abstract (arXiv)

Online convex optimization with switching cost is considered under the frugal information setting where at time t, before action xt is taken, only a single function evaluation and a single gradient is available at the previously chosen action xt-1 for either the current cost function ft or the most recent cost function ft-1. When the switching cost is linear, online algorithms with optimal order-wise competitive ratios are derived for the frugal setting. When the gradient information is noisy, an online algorithm whose competitive ratio grows quadratically with the noise magnitude is derived.