# Online Convex Optimisation: The Optimal Switching Regret for all Segmentations Simultaneously

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 13 references that are in the map.
- First posted on arXiv 31 May 2024.

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

- [Adaptive Online Learning in Dynamic Environments](https://mlsanity.com/paper/1810.10815/) (2018)
- [Strongly Adaptive Online Learning](https://mlsanity.com/paper/1502.07073/) (2015)
- [Improved Strongly Adaptive Online Learning using Coin Betting](https://mlsanity.com/paper/1610.04578/) (2016)

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

- [Online Learning with Gradient-Variation Interval Regret](https://mlsanity.com/paper/2606.03831/) (2026)
- [From Switching to Dynamic Regret: A Simple Reduction via Unbiased Random Sequences](https://mlsanity.com/paper/2609.20968/) (2026)
- [Score-based change point detection via tracking the best of infinitely many experts](https://mlsanity.com/paper/2408.14073/) (2024)
- [Bayesian Ensembling: Insights from Online Optimization and Empirical Bayes](https://mlsanity.com/paper/2505.15638/) (2025)
- [Dimension-Optimal Dynamic Regret in Exp-Concave Online Learning](https://mlsanity.com/paper/2610.20187/) (2026)
- [Tracking a Small Set of Experts in Online Convex Optimization](https://mlsanity.com/paper/2610.20416/) (2026)

## Abstract (arXiv)

We consider the classic problem of online convex optimisation. Whereas the notion of static regret is relevant for stationary problems, the notion of switching regret is more appropriate for non-stationary problems. A switching regret is defined relative to any segmentation of the trial sequence, and is equal to the sum of the static regrets of each segment. In this paper we show that, perhaps surprisingly, we can achieve the asymptotically optimal switching regret on every possible segmentation simultaneously. Our algorithm for doing so is very efficient: having a space and per-trial time complexity that is logarithmic in the time-horizon. Our algorithm also obtains novel bounds on its dynamic regret: being adaptive to variations in the rate of change of the comparator sequence.