# Dynamic Regret in Online Convex Optimization with Indicator Switching Costs

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 26 references that are in the map.
- First posted on arXiv 24 Sep 2026.

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

- [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)
- [Strongly Adaptive Online Learning](https://mlsanity.com/paper/1502.07073/) (2015)
- [Online Learning with Switching Costs and Other Adaptive Adversaries](https://mlsanity.com/paper/1302.4387/) (2013)
- [Parameter-free Mirror Descent](https://mlsanity.com/paper/2203.00444/) (2022)
- [Smoothed Online Convex Optimization in High Dimensions via Online Balanced Descent](https://mlsanity.com/paper/1803.10366/) (2018)
- [Revisiting Smoothed Online Learning](https://mlsanity.com/paper/2102.06933/) (2021)
- [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)
- [Lazy OCO: Online Convex Optimization on a Switching Budget](https://mlsanity.com/paper/2102.03803/) (2021)
- [Optimal Comparator Adaptive Online Learning with Switching Cost](https://mlsanity.com/paper/2205.06846/) (2022)
- [Understand Dynamic Regret with Switching Cost for Online Decision Making](https://mlsanity.com/paper/1911.12595/) (2019)
- [Online Convex Optimization with Continuous Switching Constraint](https://mlsanity.com/paper/2103.11370/) (2021)
- [Smoothed Online Convex Optimization Based on Discounted-Normal-Predictor](https://mlsanity.com/paper/2205.00741/) (2022)
- [On the Dynamic Regret of Following the Regularized Leader: Optimism with History Pruning](https://mlsanity.com/paper/2505.22899/) (2025)
- [Partially Lazy Gradient Descent for Smoothed Online Learning](https://mlsanity.com/paper/2601.15984/) (2026)
- [Parameter-free Dynamic Regret: Time-varying Movement Costs, Delayed Feedback, and Memory](https://mlsanity.com/paper/2602.06902/) (2026)

## Abstract (arXiv)

We study dynamic regret in online convex optimization with an indicator switching cost: a fixed penalty incurred whenever two consecutive decisions differ. This captures startup overheads such as server activation, model deployment, and cache updates, and on a bounded domain it recovers norm-based movement costs as a special case. Existing guarantees for indicator costs handle only static comparators. We show that a direct extension of these techniques to dynamic regret provably fails, motivating a different approach. We propose a meta-learning framework: a set of randomized lazy FTRL base learners restarted at dyadic time scales, aggregated by a movement-aware master that mixes their proposal densities and samples actions via maximal coupling of consecutive mixtures. The resulting algorithm satisfies, in expectation, R1T ≤ tildeO(min√T(ST+1),T2/3(PT+1)1/3), where R1T is the dynamic regret plus the cumulative indicator switching cost, ST counts comparator switches, and PT is the comparator path length. The bound holds simultaneously for all sequences and requires no prior knowledge of ST or PT: it is minimax-optimal (up to logarithmic factors) for tracking piecewise-constant comparators, and also captures frequently moving comparators with small total path length.