Minimax Alternating Regret for the Experts Problem and Online Convex Optimization

Mengxiao Zhang

stat.MLAug 25, 2026

Minimax Alternating Regret for the Experts Problem and Online Convex Optimization

Authors: Mengxiao Zhang

Organizations: University of Iowa

Abstract

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 alternating regret is $Θ(\log d)$ , independent of the horizon $T$ . This significantly improves upon the best-known $\mathcal{O}(T^{1/3}\log^{2/3} d)$ established by Hait et al. [2025]. We further extend our results to general OCO over a $d$ -dimensional compact convex set and prove that the worst-case minimax alternating regret is $Θ\left(d\log \left(1+\frac{T}{d}\right)\right)$ , also significantly improving upon the best-known $\mathcal{O}((d\log T)^{2/3}T^{1/3})$ upper bound and resolving the open problem posed by Cevher et al. [2023], Hait et al. [2025]. Technically, our upper bound for the expert problem is achieved by a corrected variant of Hedge, in which carefully designed correction terms cancel the unfavorable curvature arising in the alternating-regret analysis. We extend the same corrected-potential argument to continuous action sets to obtain the optimal alternating-regret rate for OCO. For the lower bounds, the expert construction repeatedly eliminates half of the candidate experts, while the OCO lower bound instance construction replaces this discrete elimination by a more involved multiscale construction on the unit disk.

Figures & tables

\mu_{t-1}=\mathbb{E}_{i\sim q_{t-1}}[y_{t-1,i}],\qquad Z_{t-1,i}=y_{t-1,i}-\mu_{t-1},\qquad H_{t-1}=\mathbb{E}_{i\sim q_{t-1}}[Z_{t-1,i}^{2}].

Algorithm 1 Corrected AltHedge

	$\displaystyle\mu_{t-1}$	$\displaystyle\triangleq\int_{\mathcal{X}}y_{t-1}(x)q_{t-1}(x)\,dx,$
	$\displaystyle Z_{t-1}(x)$	$\displaystyle\triangleq y_{t-1}(x)-\mu_{t-1},$
	$\displaystyle H_{t-1}$	$\displaystyle\triangleq\int_{\mathcal{X}}Z_{t-1}(x)^{2}q_{t-1}(x)\,dx.$

Algorithm 2 Continuous Corrected AltHedge

Online Convex Optimization

Online Convex Optimization studies sequential decisions under changing convex losses, seeking low regret with limited feedback and constraints.

See all 59 papers

Aug 25, 2026

Optimal Alternating Regret for Online Learning and Games

We settle the minimax-optimal alternating regret, a regret notion motivated by alternating learning dynamics in games, for both online linear optimization (OLO) and online convex optimization (OCO). For OLO over the probability simplex

Δ_d

, we give an algorithm with

O(\log d)

alternating regret that remains a constant for any time horizon

T

, and a matching lower bound. Our constant regret bound significantly improves previous results with

O(\log ^{2/3}d \cdot T^{1/3})

regret [Cevher, Cutkosky, Kavis, Piliouras, Skoulakis, Viano, NeurIPS 2023, Hait, Li, Luo, Zhang, COLT 2025]. As a result, we obtain alternating learning dynamics with

O(\log d /T)

convergence to Nash equilibria in two-player zero-sum games and

O(\log d /T)

convergence to coarse correlated equilibria in two-player general-sum games. This is the first uncoupled learning dynamics with

O(1/T)

convergence to CCE in two-player general-sum games, while all prior works suffer additional

\log T

factors. For general OCO over a

d

-dimensional compact convex set, we give an algorithm with

O(d\log (1+T/d))

alternating regret, improving the previous best of

\widetilde{O}(d^{2/3}T^{1/3})

. We also prove a matching lower bound of

Ω(d\log (1+T/d))

, showing that the

Ω(\log T)

factor is unavoidable.

Yixin Tao, Weiqiang Zheng

ITCS, Key Laboratory of Interdisciplinary Research of Computation and Economics, Shanghai University of Finance and Economics · Yale University

Online Convex Optimization Nash Equilibrium Computation

Ask PDF

Oct 14, 2026

Tracking a Small Set of Experts in Online Convex Optimization

For the fundamental problem of prediction from expert advice, Freund asked whether one could compete with a comparator that switches

k

times among only

m

experts. For a discrete set of experts, this problem was resolved by Bousquet and Warmuth (2020), who gave an efficient algorithm with optimal regret matching the information-theoretic limit. We study the analogous problem in online convex optimization, where the action space is continuous. An inefficient algorithm can be derived by discretizing the action space and applying the Bousquet--Warmuth algorithm, giving regret of

\widetilde{O}(md+k)

, while the best known efficient algorithm for this problem has regret

\widetilde{O}(dk)

. We show that this computational inefficiency is inherent, establishing a separation between the information-theoretic and polynomial-time regret achievable for this problem. Specifically, under the hypergraphic planted-clique conjecture, we show that for every polynomial-time algorithm there exist instances for which it incurs at least

(k\sqrt d)^{1-o(1)}

regret.

Angelos Assos, Anand Brahmbhatt, Elad Hazan

Princeton University · Google DeepMind Princeton

Online Convex Optimization

Ask PDF

Oct 18, 2026

Decentralized Online Exp-Concave Optimization

Decentralized Online Convex Optimization (D-OCO) is a fundamental framework in which a set of local agents aims to minimize a sequence of global loss functions using only local computations and communications. While recent work has established near-optimal regret guarantees for convex and strongly convex losses, the case of exp-concave losses remains an open challenge: specifically, whether logarithmic regret is achievable. In this paper, we answer this question affirmatively by proposing Decentralized Online Newton Step (D-ONS), which adapts the idea of blocking and accelerated gossip to the Online Newton Step algorithm in a non-trivial manner. Concretely, our algorithm achieves a regret bound of

O\left(Nd(1-σ_2)^{-1/2}\,\log^2(T) \right)

where

N

is the number of agents,

d

is the dimension,

T

is the horizon, and

1-σ_2

represents the spectral gap of the network. To our knowledge, this is the first logarithmic regret bound for decentralized online exp-concave optimization. We further establish a nearly matching lower bound of

Ω\left(Nd (1-σ_2)^{-1/2}\,\log(T/N) \right)

showing the near optimality of our upper bound. Finally, we extend our algorithm to decentralized online linear regression in which the feasible domain is unbounded and features and labels are locally observed. By gossiping covariance and label-feature statistics, we also achieve logarithmic regret.

Hao Qiu, Mengxiao Zhang, Yuanyu Wan

National University of Singapore, Singapore · Department of Business Analytics, Tippie College of Business, University of Iowa, USA · School of Software Technology, Zhejiang University, Ningbo, China +1

Decentralized Optimization Online Convex Optimization

Ask PDF

Abstract

Online Convex Optimization

Explore similar work

Optimal Alternating Regret for Online Learning and Games

Tracking a Small Set of Experts in Online Convex Optimization

Decentralized Online Exp-Concave Optimization