PaperlayerView exact revision on arXiv

Source-linked AI summary

Minimax Alternating Regret for the Experts Problem and Online Convex Optimization

Mengxiao Zhang

arXiv:2608.25182v1stat.MLcs.LG

TL;DR

The paper asks for minimax alternating-regret rates in the expert problem and general OCO, where existing bounds were not known to be optimal. It proves matching bounds using corrected-potential algorithms and corresponding discrete or geometric lower-bound constructions, obtaining Θ(log d) for experts and Θ(d log(1 + T/d)) for general OCO.

  • Problem

    The minimax alternating-regret rate remained unknown for the expert problem and general OCO, including whether polynomial dependence on T was unavoidable even for experts.

  • Method

    The paper combines corrected-potential upper bounds with halving and multiscale geometric lower-bound constructions, extending the expert algorithm to continuous action sets.

  • Results

    Θ(log d) is the minimax alternating regret for d experts, independent of T, while general d-dimensional OCO has worst-case minimax rate Θ(d log(1 + T/d)).

  • Takeaways & Limitations

    The results resolve the minimax rates in both settings and yield faster convergence guarantees for alternating learning dynamics in games.

  • Takeaways & Limitations

    The OCO protocol assumes the learner chooses x_t before observing f_t and chooses x_T+1 after observing f_T.

Abstract

from arXiv · show

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.

1 Introduction

The paper resolves the open minimax alternating-regret question for experts and general OCO with matching lower and upper bounds. It obtains Θ(log d) for d experts, independent of T, and Θ(d log(1 + T/d)) for d-dimensional compact convex OCO.

  • Motivation: Alternating regret evaluates each loss at both the learner’s current action and its next action after observing that loss.The measure is motivated by alternating learning dynamics in two-player games.
  • Open problem: Existing bounds were not known to be minimax optimal, leaving open whether polynomial dependence on T was unavoidable even for experts.The paper contrasts this gap with well-understood classical-regret minimax rates.
  • Contributions: Θ(d log(1 + T/d)) is the worst-case minimax alternating regret for general OCO over a d-dimensional compact convex set.The lower bound uses a multiscale geometric construction, and the upper bound extends the corrected-potential argument to continuous action sets.
  • Contributions: Θ(log d) is the minimax alternating regret for the d-expert problem, independent of the horizon T.The matching lower bound uses halving, while a corrected Hedge variant supplies the upper bound.
  • Lower-bound method: The expert lower bound repeatedly eliminates half of the candidate experts, while the OCO lower bound replaces discrete elimination with a multiscale construction on the unit disk.These constructions produce the matching lower bounds in their respective settings.
  • Upper-bound method: The corrected Hedge algorithm modifies the played distribution with linear and quadratic correction terms that cancel unfavorable curvature in the analysis.The resulting potential argument telescopes without accumulating dependence on T.

2 Preliminaries

The preliminaries define the alternating-regret OCO protocol, its filtration and bounded-loss assumptions, and the expert problem as a simplex-based linear specialization. They also introduce effective losses that combine consecutive loss functions.

  • Notation: The notation defines probability simplices, densities over compact domains, exponential-weights distributions, Bregman divergences, and suppressed logarithmic factors.For a score vector or function R, q[R] denotes the corresponding exponential-weights distribution or density.
  • Problem setting: The OCO domain X is a d-dimensional compact convex set, and the learner selects x_t before observing the revealed convex loss f_t.The interaction lasts T rounds, with an additional x_T+1 chosen after f_T is observed.
  • Information structure: The learner’s action x_t must be F_t−1-measurable, while the adversary commits to f_t independently of the learner’s fresh round-t randomness.The filtration records the initial information, learner randomness, and previously revealed losses.
  • Alternating regret: Alternating regret is defined against a comparator u ∈ X under the paper’s performance criterion.The endpoint convention f_0(x)=f_T+1(x)=0 supports the effective-loss representation.
  • Assumptions: Losses satisfy f_t ∈ [−1, 1] without assumed Lipschitzness or smoothness.This states the bounded-loss scope used in the OCO setting.
  • Expert problem: In the expert problem, X=∆^d and each loss is linear, f_t(p)=⟨p,ℓ_t⟩ for ℓ_t∈[−1,1]^d.The effective loss vector is z_t=ℓ_t−1+ℓ_t, so h_t(p)=⟨p,z_t⟩.

3 Alternating Regret in the Expert Problem

The expert problem admits matching logarithmic lower and upper bounds for alternating regret, independent of the horizon. The upper bound uses corrected exponential weights, while the lower bound repeatedly halves candidate experts.

  • 3.1 Lower bound: Θ(log d) is the minimax alternating regret for the d-expert problem when T ≥ log2 d.The lower bound holds even against an oblivious adversary, and the matching upper bound applies to adaptive loss sequences.
  • 3.1 Lower bound: The lower-bound construction retains a uniformly random half of the candidate experts at each active round until one expert remains.After m = floor(log2 d) cuts, the learner places only half its current mass on the retained half in expectation, yielding at least one unit of alternating regret per active round.
  • 3.1 Lower bound: The adversary can be made oblivious by sampling the nested candidate sets, or equivalently a permutation, before interaction begins.All later losses are zero, and averaging over the randomized construction yields a fixed loss sequence with the same expected lower bound for some permutation.
  • 3.2 Upper bound: The corrected AltHedge algorithm modifies exponential weights with linear and quadratic correction terms to cancel the unfavorable curvature in the alternating-regret analysis.It maintains score vectors and exponential-weights distributions, uses the signed auxiliary loss y_t = (-1)^t ℓ_t, and updates with the effective loss ℓ_t−1 + ℓ_t.
  • 3.2 Upper bound: The uncorrected post-update analysis incurs a Bregman-divergence stability cost that can scale as ηT, whereas the corrected potential telescopes to a logarithmic bound.The ideal post-update distribution is unavailable before observing the current loss, so the corrections enable a predictable played distribution to achieve the target one-step inequality.
  • 3.2 Upper bound: The resulting guarantee is Reg_alt,exp^T ≤ 10 log d, establishing the first horizon-independent alternating-regret bound for the expert problem.Combined with the Ω(log d) lower bound, it proves the minimax rate Θ(log d) and improves the prior O(T^1/3 log^2/3 d) upper bound.

4 Alternating Regret for Online Convex Optimization

The OCO section develops a multiscale lower bound and a continuous corrected-potential algorithm, establishing matching minimax alternating-regret rates for compact convex domains.

  • Lower bound: The lower bound adapts expert elimination geometrically: epochs use decreasing spatial scales on the unit disk, then a direct product extends the construction to dimension d.Each epoch creates a constant expected gap while later movements remain small enough for comparison with one fixed comparator.
  • Lower bound: Ω(log T) alternating regret arises in two dimensions, and the product construction yields the corresponding dimension-dependent lower bound for general OCO.The horizon contains Θ(log T) geometric scales, while separate disk factors are assigned to coordinate pairs.
  • Upper bound: Algorithm 2 replaces finite exponential weights by a density over X while retaining the two correction terms from the expert algorithm.Scores become functions, distributions become densities, and sums and expectations become integrals.
  • Algorithmic choices: Option I plays the corrected density’s mean for deterministic guarantees, whereas Option II samples from it and guarantees regret only in expectation.The mean lies in X but requires integration; sampling avoids that computation.
  • Results: Theorem 4.2 establishes the matching minimax rate for every d-dimensional compact convex set and adaptive bounded convex-loss sequence.The result significantly improves the previous e O(d2/3T1/3) guarantee and yields improved convergence rates in convex games.
  • Upper bound: The continuous corrected-potential inequality controls loss averaged under the corrected density and supplies the matching upper-bound analysis.The proof uses the continuous analogue of the expert one-step inequality, with differentiation under the integral as the additional analytic step.

5 Conclusion

The paper resolves minimax alternating regret for experts and general OCO using matching lower and upper bounds, with corrected-potential methods and specialized lower-bound constructions.

  • Conclusion: Θ(log d) is the minimax alternating regret for the d-expert problem, independent of the horizon T.The upper and lower bounds use corrected Hedge and halving, respectively.
  • Conclusion: Θ(d log(1 + T/d)) is the worst-case minimax alternating regret for d-dimensional OCO with bounded convex losses.The upper bound uses a continuous corrected potential, while the lower bound uses a multiscale geometric construction.
  • Conclusion: The results improve previous T1/3-dependent upper bounds and resolve the minimax rates in both settings.The paper also identifies efficient implementation under partial-information feedback as an open direction.

A Omitted details in Section 3

The appendix verifies that the corrected expert distribution is valid and establishes the curvature properties underlying the corrected-potential proof.

  • Validity of the corrected distribution: For η = 1/10, the corrected vector pt belongs to the probability simplex because its coordinates are nonnegative and sum to one.The multiplicative correction factor is at least 3/25, while both correction terms are centered under qt−1.
  • Curvature calculation: The corrected potential combines the log-partition term with a variance correction along an interpolation between the previous score and the effective loss.The parametric potential is Uα(R, y) = F(R) − αη Varq[ηR](y).
  • Curvature calculation: At η = 1/10 and α = 2, the second derivative has a negative coefficient, so the corrected potential is concave along the alternating path.The coefficient is −67/500.
  • Endpoint identity: The left derivative of the corrected potential at the interpolation endpoint equals the negative loss evaluated at the played distribution.This endpoint identity connects the potential decrease to the learner’s played action.

B Omitted details in Section 4.1

The appendix proves the OCO lower bound through geometric epochs on the unit disk, showing constant per-epoch gaps that accumulate against one fixed comparator.

  • Single-comparator comparison: Geometrically decreasing scales keep later reference-point movements from substantially increasing earlier-epoch losses, allowing comparison with one fixed final comparator.The epoch lengths grow geometrically, so Θ(log T) scales fit within horizon T.
  • Two-dimensional lower bound: The two-dimensional disk construction proves an Ω(log T) lower bound for every learner under an oblivious distribution of convex losses.The lower-bound lemma applies for every T ≥ 5.
  • Multiscale construction: Each epoch samples convex losses around a boundary point and rotates the reference point when the movement-favoring loss appears.The construction inserts zero-loss separators between epochs and can be sampled before interaction, making the environment oblivious.
  • Per-epoch gap: Every epoch gives the learner a universal constant expected paired-loss disadvantage relative to its reference point.This is the local gap that the multiscale construction later aggregates.
  • Dimension lift: A direct-product construction places independent disk instances on coordinate pairs, decomposing alternating regret across segments and lifting the lower bound to dimension d.For odd d, the unused final coordinate is set to zero.
  • From distributions to sequences: Averaging over deterministic sequences yields one oblivious loss sequence whose expected alternating regret is at least the distributional lower bound.The argument also covers randomized learners by including their internal randomness in the expectation.

C Omitted details in Section 4.2

The appendix extends the corrected-potential proof to continuous action sets, verifies the corrected density and sampling procedure, and handles comparator approximation using scaled domain copies.

  • Density verification and sampling: The corrected density pt is a valid probability density because its correction factor satisfies 3/25 ≤ Γt(x) ≤ 91/50 < 2.These bounds use |Zt−1(x)| ≤ 2, Ht−1 ≤ 1, and η = 1/10.
  • Density verification and sampling: Exact sampling from pt uses rejection sampling from qt−1 with acceptance probability Γt(X)/2 and requires two proposals in expectation.The overall acceptance probability is 1/2, and accepted samples have density pt.
  • Continuous corrected-potential argument: The continuous corrected-potential calculation follows Proposition A.2 after replacing finite objects with functions, densities, integrals, and centered quantities.The proof relies on the moving-expectation identity, differentiation of affine interpolation, and centered-quantity algebra.
  • Continuous corrected-potential argument: α = 2 and η = 1/10 make G2 concave, while the interpolation satisfies the required endpoint identities.The proof obtains G′′2(θ) ≤ −(67/500) Varqθ(ht) ≤ 0 and verifies the endpoints, including the T + 1 convention.
  • Comparator approximation: A single comparator is replaced by the scaled set Au = (1 − δ)u + δX, whose volume is δ^d vol(X).Convexity and ft ∈ [−1, 1] imply RT+1(x) ≥ RT+1(u) − 4Tδ throughout Au, enabling comparison through a positive-volume neighborhood.
Loading 2608.25182v1…