PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimal Multiclass Online Regret with Arbitrary Label Spaces

Sajad Ashkezari, Shai Ben-David

arXiv:2610.32339v1cs.LGstat.ML

TL;DR

A logarithmic gap remained between the known regret upper and lower bounds for agnostic multiclass online learning with arbitrary label spaces. The paper strengthens a one-sided expert cover and uses minimax duality to obtain disagreement control for chaining. It establishes the optimal regret bound, matching the known lower bound.

  • Problem

    For arbitrary label spaces, the known upper bound for finite Littlestone dimension still had a logarithmic gap to the lower bound, leaving open whether the optimal regret is Θ(sqrt(dT)).

    Source: §1 · p. 1

  • Method

    The proof strengthens the one-sided expert family to a fractional cover and uses minimax duality on a finite expert game, whose best-response rewards control disagreements for chaining.

    Source: §1 · p. 2

  • Results

    The paper establishes the optimal regret for agnostic multiclass online learning with arbitrary, possibly infinite, label spaces, matching the known lower bound.

    Source: §1 · p. 1

  • Takeaways & Limitations

    The result answers whether the optimal regret bound extends beyond binary classification to arbitrary multiclass label spaces.

    Source: §1 · p. 1

    The concentration argument is formulated for stochastic trees with instances, label distributions, and expert predictions measurable from the previous rounds.

    Source: §7.1 · p. 12

Abstract

from arXiv · show

We determine the optimal regret in agnostic multiclass online learning with arbitrary, possibly infinite, label spaces. For every hypothesis class of multiclass Littlestone dimension $d<\infty$, we prove a regret upper bound of $O(\min\{T,\sqrt{dT}\})$ over $T$ rounds, matching the known lower bound. This resolves a question of Hanneke et al. (2023) and extends the optimal binary regret bound of Alon et al. (2021). Our proof strengthens the one-sided expert cover of Hanneke et al. (2023) to a fractional cover. We combine this cover with a minimax reduction to a finite expert game, whose best-response rewards provide the disagreement bounds needed for chaining.

1 Introduction

The introduction asks whether finite multiclass Littlestone dimension yields optimal agnostic regret for arbitrary label spaces. It answers affirmatively and explains how a fractional cover and minimax best responses supply the disagreement control needed for chaining.

1 Introduction

  • Hanneke et al.'s label-space-independent upper bound left a logarithmic gap to the known lower bound.Their result established agnostic online learnability for finite Littlestone dimension, but left open whether the optimal regret is Θ(sqrt(dT)).Source: §1 · p. 1
  • The paper establishes the optimal regret for agnostic multiclass online learning with arbitrary, possibly infinite, label spaces, matching the known lower bound.The introduction identifies this as an affirmative answer to the question of whether the optimal regret is Θ(sqrt(dT)), as in binary classification.Source: §1 · p. 1
  • The multiclass expert family gives a one-sided guarantee on rounds where the hypothesis is correct, but does not ensure experts are close enough for chaining.The guarantee leaves unrestricted rounds where an expert is correct and the hypothesis is wrong; those extra correct predictions can make their correctness sequences differ.Source: §1 · p. 2
  • Reducing to the binary loss class is insufficient in general because its sequential graph dimension can be infinite even when the multiclass dimension is 1.The resulting regret bound can depend on label-space size for finite label spaces.Source: §1 · p. 2
  • The proof strengthens Hanneke et al.'s expert family to a fractional cover and uses minimax duality to form a finite expert game.The finite family permits the minimax step without topological assumptions on the hypothesis class.Source: §1 · p. 2
  • Best-response rewards control experts' extra correct predictions, providing the disagreement bounds that the one-sided cover alone lacks.Those bounds enable chaining and lead to the optimal regret bound.Source: §1 · p. 2

2 Model and main result

The section sets up online agnostic classification over arbitrary instance and label sets and states a main regret theorem for classes of finite multiclass Littlestone dimension. It also specifies the adversarial sequence-based regret setting and notes that the bound requires no measurability assumptions.

2 Model and main result

  • The model allows arbitrary nonempty instance and label sets, and defines regret by comparison with the best hypothesis on each labeled sequence.The adversary may choose labels adaptively based on earlier play.Source: §2 · p. 3
  • Theorem 2.2 gives an online algorithm with finitely supported prediction distributions for every nonempty class of finite multiclass Littlestone dimension.The theorem applies at every horizon T ≥ 1.Source: §2 · p. 3
  • The regret bound holds on every labeled sequence and requires no measurability assumptions.Source: §2 · p. 4

3 Preliminaries: SOA and finite expert covers

The preliminaries establish how SOA uses Littlestone dimension to control mistakes, then build a finite expert family and strengthen its one-sided guarantee into fractional covers at multiple scales.

3.1 Version spaces and SOA

  • A mistake by SOA from a nonempty version space reduces its Littlestone dimension, so on realizable sequences it makes at most Ldim(V) mistakes.The version space remains nonempty on realizable data.Source: §3.1 · p. 4

3.2 A finite family of experts

  • The finite family E indexes SOA experts by update sets of at most d rounds, and for every h and labeled sequence some expert has deficit at most d.The family’s standard expert-advice bound depends on its size, while remaining independent of |Y|.Source: §3.2 · pp. 4–5

3.3 New component: one-sided fractional covers

  • The paper extends Hanneke et al.’s one-sided cover to a fractional cover measured by deficit Fh(v), with prior mass at least γ^-1 on experts whose deficit is at most s.For each scale s in [d,T], a prior on the same family has size at most (2eT/s)^d; the deficit bound alone leaves extra correct predictions uncontrolled.Source: §3.3 · pp. 5–6

4 Proof overview

The proof constructs scale-dependent one-sided fractional covers, reduces the learner’s mixtures over a finite expert family to a dual game, and bounds that game by chaining. The resulting regret is O(√(dT)).

Step 1: construction of one-sided fractional covers

  • The proof’s scale-dependent priors provide experts with deficit at most s and sufficient mass for the chaining argument.The construction uses a weighted update-set tree; its leaf experts have deficit at most s and total prior mass at least (s/(2eT))^d.Source: §4 · p. 6

Step 2: the finite-expert dual game

  • Minimax duality converts the finite-expert mixture game into one where the adversary selects a label distribution and the learner’s best response is the expert most likely to be correct.Finiteness of E makes the learner’s simplex compact and convex, enabling the minimax step without topological assumptions on H.Source: §4 · pp. 6–7

Step 3: bounding the dual value by chaining

  • Chaining across progressively finer scales controls differences between expert martingale sums, while fractional-cover masses and concentration yield a common event on which suitable chains exist.The proof uses scales sj = T4^-j, ending with d ≤ sJ < 4d.Source: §4 · p. 7
  • The dual value is bounded by O(√(dT)) uniformly over dual trees, completing the regret proof.The increment bounds use correctness distances between adjacent experts, which are controlled through the benchmark’s correctness disagreements.Source: §4 · pp. 7–8

5 One-sided fractional covers for Littlestone classes

The section constructs sequence-independent priors on the finite expert family that cover experts with bounded deficit. A weighted tree of SOA update sets establishes the required mass at each scale.

5 One-sided fractional covers for Littlestone classes

  • At each scale s in [d,T], a prior νs on the same expert family is independent of the sequence and h and gives sufficient mass to experts with deficit at most s.For integer m, update-set experts receive mass proportional to m^-|I|, with normalizer Zm ≤ (eT/(dm))^d.Source: §5 · pp. 8–9
  • The construction grows a tree of update times, adding m children at nodes with at least m deficit rounds; each selected update preserves h and drops the version-space dimension.Each branch has at most d updates, and after d updates the version space is {h}, so no further deficits occur.Source: §5 · p. 8
  • Every leaf expert has deficit at most dm, and the uniform child choices assign leaf I probability m^-|I|, yielding total good-expert prior mass at least (dm/(eT))^d.For general s, choosing m = floor(s/d) gives s/2 ≤ dm ≤ s.Source: §5 · pp. 8–9

6 A finite-expert minimax reduction

This section reduces regret for a finite family of experts to a stochastic-tree game and uses minimax duality to characterize its value. The resulting value is achievable by a deterministic mixture rule on every labeled sequence.

6 A finite-expert minimax reduction

  • The learner mixes predictions from a finite indexed family of deterministic experts, inducing a label distribution supported on at most the family’s size.The mixture rule assigns expert weights before the next label is drawn.Source: §6 · pp. 9–10
  • A stochastic tree selects instances and finite-support label distributions from the preceding label history; expectations use its induced finite probability law.At each round, the benchmark reward is compared with the largest expected correctness reward among the experts.Source: §6 · p. 10
  • The finite-expert game value equals the supremum over stochastic trees, and a deterministic mixture rule attains that value on every labeled sequence.The recursive minimax proof establishes both the value identity and attainment.Source: §6 · pp. 10, 12
  • The proof applies a one-round minimax identity recursively, with bounded continuation values, to obtain the stochastic-tree representation of the game.The argument verifies minimax and attainment for arbitrary label spaces using a finite expert family.Source: §6 · pp. 9–11

7 Bounding the dual game by localized chaining

The section bounds the dual game by chaining experts selected at multiple scales. Simultaneous concentration controls make the chains valid for every hypothesis, while correctness-disagreement bounds yield the regret guarantee.

7 Bounding the dual game by localized chaining

  • The chaining argument controls centered correctness increments using the benchmark and bounds disagreements between successive experts.The fixed-expert and expert-pair concentration estimates support selecting chains whose increments can be summed.Source: §7 · p. 12, §7.1 · p. 13, §7.2 · p. 16

7.1 Concentration and simultaneous chain selection

  • On one high-probability event, every hypothesis admits a chain of experts across scales satisfying the simultaneous concentration conditions.Conditioning priors on experts with small deficit yields a chain with positive probability, without a union bound over the hypothesis class.Source: §7.1 · pp. 13–14

7.2 Controlling disagreements and completing the bound

  • The selected chains bound the dual-game value uniformly over stochastic trees, and the finite-expert duality result transfers this bound to regret on every labeled sequence.The proof integrates the tail bound and applies the deterministic mixture guarantee.Source: §7.2 · pp. 16–17
  • O(min{T, sqrt(dT)}) regret holds for finite multiclass Littlestone dimension d, including d=0 and d>T.For d=0 a single-function class has zero regret; for d>T regret is at most T.Source: §7.2 · p. 17

AI disclosure

The authors disclose that GPT-6 Astra produced the proof forming the basis of the paper, which they subsequently checked, summarized, and rewrote. They also used AI to assist with manuscript writing and editing and take responsibility for the paper’s content and correctness.

AI disclosure

  • GPT-6 Astra produced the proof forming the basis of the paper, which the authors later checked, summarized, and rewrote.They also report using AI to assist with writing and editing the manuscript.Source: AI disclosure · p. 17
  • The authors state that they take full responsibility for the paper’s content and correctness.Source: AI disclosure · p. 17
  • The authors describe the proof-generation process as building on their study of Hanneke et al. and Alon et al. and a request to develop a fractional one-sided cover.Source: AI disclosure · p. 17

A Expected sampled regret

This appendix relates expected sampled regret to the algorithm’s regret and states when the correspondence holds. It samples predictions with fresh randomness after the adversary chooses the current label.

A Expected sampled regret

  • The adversary may choose the current label using prior sampled predictions but cannot observe the current sampled prediction.Each prediction is sampled from the algorithm’s distribution with fresh randomness after the label is chosen.Source: A Expected sampled regret · p. 19
  • Conditioned on the information available before sampling, the probability of an incorrect sampled prediction is one minus the algorithm’s probability assigned to the chosen label.Source: A Expected sampled regret · p. 19
  • Expected sampled regret equals the algorithm’s regret under the lemma’s assumptions.The reverse direction follows because any fixed labeled sequence can be played by an adversary, for which expected sampled regret equals sequence regret.Source: A Expected sampled regret · p. 19

B Proof of the concentration lemma

The proof derives concentration bounds by applying conditional Hoeffding and Markov’s inequality across rounds. A second supermartingale argument keeps the realized distance inside the exponential while fixing the parameter λ.

B Proof of the concentration lemma

  • For any fixed v ∈ E and u > 0, conditional Hoeffding bounds for Bernoulli C_t(v), iterated over T rounds and combined with Markov’s inequality at θ = 4u/T, yield P{Mv > u} ≤ e^(-2u^2/T).Source: B Proof of the concentration lemma · p. 20
  • The distance D(v, v′) remains inside the exponential throughout the second-bound argument, with λ held fixed.The proof explicitly distinguishes the realized distance from the fixed parameter λ.Source: B Proof of the concentration lemma · p. 20
  • A nonnegative supermartingale and Markov’s inequality establish the second concentration bound, (7.4).The argument applies the stated elementary inequality to λXt, using |Xt| ≤ 1.Source: B Proof of the concentration lemma · p. 20

C Estimating the chain sum

The chain-sum estimate controls scale-dependent terms and verifies that the powers of J + 1 do not add a logarithmic factor. Its scale terms include a geometrically decreasing contribution and individual disagreement bounds.

C Estimating the chain sum

  • For d ≤ T and τ ≥ 0, the final estimate uses the bound √(1 + τ) and (1 + τ)^3/4 ≤ 1 + τ.The passage states that this yields a universal-constant bound from (C.1), but the bound’s full expression is not present.Source: C Estimating the chain sum · pp. 20–21
  • The auxiliary quantities aj and j are bounded by 8(d + τ)(j + 1), using d ≥ 1 and log 2 < 3/4.The second bound applies for j ≥ 1.Source: C Estimating the chain sum · p. 21
  • The second chain-sum term decreases geometrically with scale, while the first comes from individual bounds Bj for correctness disagreements and has power T^1/4.These terms are distinguished in the estimate of the chain sum.Source: C Estimating the chain sum · p. 21
  • For r = T/d ≥ 1, the proof bounds J + 1 by 1 + log r and shows the resulting r-dependent factors are uniformly bounded.The factors are continuous and tend to zero as r → ∞, so the powers of J + 1 introduce no extra logarithmic factor.Source: C Estimating the chain sum · p. 21
Loading 2610.32339v1…