English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study the problem of switching-constrained online convex optimization(OCO), where the player has a limited number of opportunities to change heraction. While the discrete analog of this online learning task has been studiedextensively, previous work in the continuous setting has neither establishedthe minimax rate nor algorithmically achieved it. In this paper, we show that $T $-round switching-constrained OCO with fewer than $ K $ switches has aminimax 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 anorthogonal subspace argument. In one dimension, a novel adversarial strategyyields the lower bound of $O(\frac{T}{\sqrt{K}})$, but a precise minimaxanalysis including constants is more involved. To establish the tighterone-dimensional result, we introduce the \emph{fugal game} relaxation, whoseminimax regret lower bounds that of switching-constrained OCO. We show that theminimax regret of the fugal game is at least $ \frac{T}{\sqrt{2K}} $ andthereby establish the optimal minimax lower bound in one dimension. Toestablish the dimension-independent upper bound, we next show that amini-batching algorithm provides an $ O(\frac{T}{\sqrt{K}}) $ upper bound, andtherefore conclude that the minimax regret of switching-constrained OCO is $\Theta(\frac{T}{\sqrt{K}}) $ for any $K$. This is in sharp contrast to itsdiscrete counterpart, the switching-constrained prediction-from-expertsproblem, which exhibits a phase transition in minimax regret between thelow-switching and high-switching regimes.

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