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

Abstract

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 (\frac{T}{\sqrt{K}})$. In particular, it is at least $\frac{T}{\sqrt{2K}}$ for one dimension and at least $\frac{T}{\sqrt{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(\frac{T}{\sqrt{K}})$, but a precise minimax analysis including constants is more involved. To establish the tighter one-dimensional result, we introduce the \emph{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 $\frac{T}{\sqrt{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(\frac{T}{\sqrt{K}})$ upper bound, and therefore conclude that the minimax regret of switching-constrained OCO is $\Theta (\frac{T}{\sqrt{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.

arXiv commentFirst two authors contributed equally. Accepted to NeurIPS 2020

References in corpus (6)

• Optimal Distributed Online Prediction using Mini-Batches
• Online Bandit Learning against an Adaptive Adversary: from Regret to Policy Regret
• Online Learning with Switching Costs and Other Adaptive Adversaries
• Online Optimization with Predictions and Switching Costs: Fast Algorithms and the Fundamental Limit
• Prediction by Random-Walk Perturbation
• A Stochastic View of Optimal Regret through Minimax Duality

Cited by in corpus (5)

• Making Non-Stochastic Control (Almost) as Easy as Stochastic
• Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraints
• Revisiting Smoothed Online Learning
• Online Convex Optimization with Continuous Switching Constraint
• Lazy OCO: Online Convex Optimization on a Switching Budget