SOURCE-LINKED INTELLIGENCE

Minimax Alternating Regret for the Experts Problem and Online Convex Optimization

arXiv · AI, language, vision and robotics · article · Aug 25, 2026 · UTC

In this paper, we study alternating regret in online convex optimization (OCO), motivated by the success of alternating learning dynamics in two-player games. Although previous works have shown that $o(\sqrt{T})$ alternating regret is achievable under various assumptions on the loss functions and feasible domains, the minimax regret rate has remained open even for the expert problem. In this paper, we resolve this question by showing matching lower and upper bounds for both the expert problem and general OCO. Somewhat surprisingly, for the $d$-expert problem, we show that the minimax alternati

Read original source ↗ Open in workspace

recordType

paper

region

Global