Tracking a Small Set of Experts in Online Convex Optimization

Angelos Assos; Anand Brahmbhatt; Elad Hazan

cs.LGOct 14, 2026

Tracking a Small Set of Experts in Online Convex Optimization

Authors: Angelos Assos, Anand Brahmbhatt, Elad Hazan

Organizations: Princeton University · Google DeepMind Princeton

Abstract

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.

Figures & tables

Loss class	Information-theoretic lower bound	Polynomial-time upper bound	Computational lower bound
Convex	$\Omega(\sqrt{kT})$ [ 20 ] 1 1 1 Partition the horizon into $k+1$ equal blocks and use independent random linear losses on each block. Each block contributes $\Omega(\sqrt{T/k})$ regret, with its best comparator in $\{-1,1\}$ , yielding $\Omega(\sqrt{kT})$ .	$O(\sqrt{kT})$ [ 20 ]	–
Strongly convex	$\Omega(k)$ 2 2 2 On block $j$ , use $f_{t}(x)=(x-\sigma_{j})^{2}$ with independent uniform $\sigma_{j}\in\{-1,1\}$ . The first round of each block incurs constant expected regret, yielding $\Omega(k)$ .	$\widetilde{O}(k)$ [Thm. 4.3 ]	–
Exp-concave	$\widetilde{\Omega}(d+k)$ [ 2 ]	$\widetilde{O}(dk)$ [Thm. 4.4 ]	$(k\sqrt{d})^{1-o(1)}$ [Thm. 5.2 ]

Table 1: Regret bounds for constant

m\geq 2

and

k\geq 1

, with loss and domain parameters fixed.

Figure 1: Regret exponents for

k=\Theta(d^{\theta})

(fixed rational

\theta>0

), ignoring logarithmic factors. Theorem 5.2 conditionally rules out every fixed exponent below the dashed line. Shading marks the computational separation for

\theta>1/2

Figure 2: An active block

(i,j)\in C_{1}\times C_{2}

. Each cell

(\ell,v)

is one round with loss

f_{ij\ell v}(x)=\frac{1}{8}(x_{\ell}-Y_{ij\ell v})^{2}

. The planted clique forces

+1

labels on

C_{3}\times C_{4}

; the remaining labels are independent fair signs conditional on the clique. The fixed comparator vector (right) predicts

\gamma

C_{3}

coordinates and zero elsewhere throughout the block. Hidden clique rows and columns are grouped only for visualization. See Figure 3 in Appendix C for the full hypergraph-to-loss construction.

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

\widehat{p}_{t+1}^{(i)}\leftarrow\frac{p_{t}^{(i)}e^{-\alpha f_{t}(x_{t}^{(i)})}}{\sum_{j\in S_{t}}p_{t}^{(j)}e^{-\alpha f_{t}(x_{t}^{(j)})}}.

Appendix

Algorithm 1 Pruned Follow-the-Leading-History (FLH)

Figure 3: From a hypergraph to a loss sequence. Blue outlines link one queried four-vertex hyperedge to its cell in an OCO block. Orange vertices belong to the hidden clique, forcing

+1

labels on

C_{3}\times C_{4}

; all remaining cells contain independent fair signs conditional on the clique. The comparator predicts

\gamma

C_{3}

rows throughout the block. Only one hyperedge is drawn. Clique membership is shown for explanation, and the schematic grid groups clique rows and columns for visualization.

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

Minimax Alternating Regret for the Experts Problem and Online Convex Optimization
Aug 25, 2026Mengxiao ZhangOnline Convex Optimization Minimax Regret
University of Iowa
Online Convex Optimization with Sublinear Noisy Probes
Jun 12, 2026Simone Di Gregorio, Anupam Gupta, Stefano Leonardi +1Online Convex Optimization Online Learning
Sapienza University of Rome, Italy · New York University, USA · EPFL, Switzerland
Polyhedral Instability Governs Regret in Online Learning
May 13, 2026Yuetai Li, Fengqing Jiang, Yichen Feng +6Online Convex Optimization Combinatorial Optimization
♣University of Washington · ♢Western Washington University · ♠King Abdulaziz City for Science and Technology ♡HUMAIN

Aug 25, 2026J/K move · Enter open · S save

Minimax Alternating Regret for the Experts Problem and Online Convex Optimization

Mengxiao Zhang

University of Iowa

Online Convex Optimization Minimax Regret

Open paper AskPDF arXiv

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.

Abstract

Online Convex Optimization

Explore similar work

Minimax Alternating Regret for the Experts Problem and Online Convex Optimization

Online Convex Optimization with Sublinear Noisy Probes

Polyhedral Instability Governs Regret in Online Learning