# Minimax Regret of Switching-Constrained Online Convex Optimization: No Phase Transition

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Oct 2019.

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

- [Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraints](https://mlsanity.com/paper/2101.02195/) (2021)
- [Exponential Bellman Equation and Improved Regret Bounds for Risk-Sensitive Reinforcement Learning](https://mlsanity.com/paper/2111.03947/) (2021)
- [Non-stationary Online Learning with Memory and Non-stochastic Control](https://mlsanity.com/paper/2102.03758/) (2021)
- [Revisiting Smoothed Online Learning](https://mlsanity.com/paper/2102.06933/) (2021)
- [Batched Neural Bandits](https://mlsanity.com/paper/2102.13028/) (2021)
- [Parallelizing Thompson Sampling](https://mlsanity.com/paper/2106.01420/) (2021)
- [Private Online Prediction from Experts: Separations and Faster Rates](https://mlsanity.com/paper/2210.13537/) (2022)
- [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)
- [Online Convex Optimization with Continuous Switching Constraint](https://mlsanity.com/paper/2103.11370/) (2021)
- [Online Convex Optimization with Unbounded Memory](https://mlsanity.com/paper/2210.09903/) (2022)
- [Multi-armed Bandit Learning on a Graph](https://mlsanity.com/paper/2209.09419/) (2022)
- [Private Online Learning via Lazy Algorithms](https://mlsanity.com/paper/2406.03620/) (2024)
- [Universal Caching](https://mlsanity.com/paper/2205.04860/) (2022)
- [Partially Lazy Gradient Descent for Smoothed Online Learning](https://mlsanity.com/paper/2601.15984/) (2026)
- [Federated Online Prediction from Experts with Differential Privacy: Separations and Regret Speed-ups](https://mlsanity.com/paper/2409.19092/) (2024)
- [Dynamic Regret in Online Convex Optimization with Indicator Switching Costs](https://mlsanity.com/paper/2609.30556/) (2026)

## Abstract (arXiv)

We study the problem of switching-constrained online convex optimization (OCO), where the player has a limited number of opportunities to change her action. While the discrete analog of this online learning task has been studied extensively, previous work in the continuous setting has neither established the minimax rate nor algorithmically achieved it. In this paper, we show that  T -round switching-constrained OCO with fewer than  K  switches has a minimax regret of  Theta(fracT√K) . In particular, it is at least  fracT√2K  for one dimension and at least  fracT√K  for higher dimensions. The lower bound in higher dimensions is attained by an orthogonal subspace argument. In one dimension, a novel adversarial strategy yields the lower bound of O(fracT√K), but a precise minimax analysis including constants is more involved. To establish the tighter one-dimensional result, we introduce the fugal game relaxation, whose minimax regret lower bounds that of switching-constrained OCO. We show that the minimax regret of the fugal game is at least  fracT√2K  and thereby establish the optimal minimax lower bound in one dimension. To establish the dimension-independent upper bound, we next show that a mini-batching algorithm provides an  O(fracT√K)  upper bound, and therefore conclude that the minimax regret of switching-constrained OCO is  Theta(fracT√K)  for any K. This is in sharp contrast to its discrete counterpart, the switching-constrained prediction-from-experts problem, which exhibits a phase transition in minimax regret between the low-switching and high-switching regimes.