Optimistic Rates for Multiclass PAC Learning

Technical Summary: Optimistic Rates for Multiclass PAC Learning

Problem Statement
The paper addresses the statistical difficulty of multiclass classification in the PAC learning framework. Existing worst-case bounds for multiclass learning depend on two capacity parameters: the Natarajan dimension ($d_N$) and the Daniely–Shalev-Shwartz (DS) dimension ($d_{DS}$). While the optimal rates are known at the two extremes—realizable learning ($L^\star = 0$) and fully agnostic learning ($L^\star$ constant)—the behavior in between remains unresolved. Specifically, current worst-case agnostic bounds scale as $\sqrt{d_N/n} + d_{DS}/n$, failing to reflect the fact that if the best classifier is nearly correct (small oracle risk $L^\star$), the learning problem should be easier. The goal is to establish an "optimistic rate" where the fluctuation term scales with $L^\star$, interpolating between the fast realizable rate and the slow agnostic rate.

Methodology
The authors propose a learner, RMC (Relative Menu Compression), which achieves this interpolation without prior knowledge of $L^\star$ or the confidence level $\delta$. The proof architecture relies on a three-block sample splitting strategy, adapting the "cover–menu–compression" reduction from [CEH+26] but introducing a novel statistical interface.

1. Block 1 (Cover): A deterministic compressor reduces the infinite hypothesis class to a finite family $\hat{\mathcal{F}}$ of size roughly $d_{DS} \log^2 n$. This step ensures that for any comparator $h$, there exists a "canonical witness" in $\hat{\mathcal{F}}$ that agrees with $h$ on the region where $h$ is correct.
2. Block 2 (Menu): A multiplicative-weights algorithm learns a "menu" $\mu$ (a set of candidate labels for each input) that covers the labels of the canonical witness on the oracle's correct region. This step controls the probability that a correct label is missing from the menu, a failure mode governed by $d_{DS}$.
3. Block 3 (Compression): Once the menu is fixed, the problem reduces to binary classification within the menu. The learner applies a compression rule that empirically dominates a fixed comparator.

The core technical innovation is a Comparator-Facing Relative Compression Theorem (Theorem 3.3). Unlike standard compression bounds that compare the learner's population risk to its empirical risk (yielding a $\sqrt{k/n}$ fluctuation), this theorem compares the learner's population risk directly to a fixed comparator's population risk $L(h)$. It establishes that if a compression rule of size $k$ has no larger empirical loss than $h$, then:
$$L(A(S)) \leq L(h) + O\left(\sqrt{L(h) \frac{k \log n}{n}} + \frac{k \log n}{n}\right)$$
Crucially, the coefficient of $L(h)$ is exactly 1, and the fluctuation scales with $\sqrt{L(h)}$. This is achieved using ordered descriptions with repeated indices and one-sided Bernstein inequalities, without requiring stability assumptions.

Key Contributions

1. Optimal Multiclass Optimistic Rate: The paper proves that for a class with Natarajan dimension $d_N$ and DS dimension $d_{DS}$, the optimal excess risk is:
   $$\tilde{\Theta}\left( \sqrt{\frac{L^\star d_N}{n}} + \frac{d_{DS}}{n} \right)$$
   This result holds uniformly in the alphabet size. The $d_N$ term localizes to the oracle risk $L^\star$, while the $d_{DS}$ term remains a realizable-order remainder.
2. Matching Lower Bound: The authors construct a single hypothesis class and a single distribution for any fixed $L^\star$ that forces both terms of the upper bound simultaneously. This confirms that the separation of roles—$d_{DS}$ controlling label coverage and $d_N$ controlling fluctuations within the menu—is intrinsic to the problem, not an artifact of the analysis.
3. Extension to List Learning: The architecture is extended to list learning (outputting $r$ labels). The authors derive optimistic rates against the best $r$-tuple of hypotheses, localizing the fluctuation at the oracle list risk. This resolves an expectation from [Pab26] regarding the necessity of an $r$-ary Natarajan fluctuation term and improves the known realizable list lower bound by removing a factor of $r$.
4. Formal Verification: The main theorems and their proofs are machine-checked in Lean 4, ensuring the correctness of constants and logical dependencies.

Results

• Upper Bound (Theorem 3.1): The RMC learner achieves the rate $\tilde{O}(\sqrt{L^\star d_N/n} + d_{DS}/n)$ with probability $1-\delta$. The learner is parameter-free (independent of $L^\star$ and $\delta$).
• Lower Bound (Theorem 4.1): For any $1 \leq d_N \leq d_{DS}$, there exists a class and distribution where any learner incurs an expected excess risk of at least $\Omega(\sqrt{L^\star d_N/n} + d_{DS}/n)$. The construction uses a product of a noisy Natarajan cube and a pseudo-cube (derived from [BCD+22]) to separate the two dimensions.
• List Learning (Theorems 5.1 & 5.2): The optimistic rate extends to list learners against the best $r$-tuple, with a lower bound confirming the necessity of the fluctuation term. Additionally, a new lower bound for realizable list learning removes the factor $r$ present in previous results [HMZ24].

Significance and Claims
The paper claims to close the gap between the known realizable and agnostic multiclass rates, providing the first distribution-free, parameter-free optimistic rate for multiclass learning.

• Theoretical Unification: It demonstrates that the "coefficient-one" comparison principle, previously established for binary classification via Boolean cube geometry [MQZ26], can be lifted to multiclass settings by decoupling the label geometry (handled by the menu/cover) from the stochastic fluctuation (handled by relative compression).
• Intrinsic Separation: The lower bound certifies that the two capacity parameters ($d_N$ and $d_{DS}$) play distinct, non-interchangeable roles: $d_{DS}$ dictates whether correct labels are visible (coverage), while $d_N$ dictates the difficulty of selecting among visible labels (fluctuation).
• Limitations: The authors note that logarithmic factors in the upper bound are not optimized, and the learner is information-theoretic (not necessarily computationally efficient). The results assume a finite label alphabet, though the bound is uniform in its cardinality.

The work is presented as a resolution to the interpolation question in multiclass PAC learning, establishing that the statistical difficulty indeed depends on the level of realizability, and providing the precise rate at which this difficulty degrades.