Optimistic Rates for Multiclass PAC Learning

This paper resolves the open problem of optimistic rates for multiclass PAC learning, closing the gap between the known realizable rate and agnostic rate. The central result is an optimal excess-risk bound that interpolates between these two regimes according to the oracle risk level.

Main Result. For a class with Natarajan dimension d N and Daniely–Shalev-Shwartz dimension d DS, the paper proves that at every fixed oracle risk L*, the optimal excess risk is

(sqrt L* d N over n + d DS over n)

uniformly in the alphabet size. This is attained by a learner that knows neither L* nor the confidence level. The upper bound (Theorem 3.1) states that with probability at least 1-delta,

L D(RMC(S)) at most L* + C (sqrt L*(d N 3(en) + (1/delta)) over n + d N 3(en) + d DS 2(en) + (1/delta) over n).

The lower bound (Theorem 4.1) constructs, for every pair (d N, d DS), a single class and distribution at every fixed L* forcing both terms simultaneously:

E[L D(A(S))] - L* at least 1 over 12 sqrt L* d N over n 1L* at least d N/n + 1 over 15 d DS over n, 1 over 4.

Key technical contributions:

1. Relative compression theorem (Theorem 3.3): A comparator-facing compression bound showing that if a size- k compression rule empirically dominates a comparator h, then its population risk satisfies

L D(A(S)) at most L D(h) + 12 sqrt L D(h) + 20

with = ((k+1) (N+1) + (4/delta))/N, without any stability assumption. This preserves coefficient one on the comparator risk and makes the fluctuation scale with that same risk.

2. Selective-menu decomposition (Lemma 2.4): An exact identity separating the two error sources: L D(g) - L D(h) at most L mu(g) - L mu(h) + alpha mu(h), where alpha mu(h) = P(h(X) = Y, Y mu(X)) is the coverage failure paid by d DS, and the inside-menu term is controlled by d N.

3. Three-block architecture: The learner splits the sample into three blocks: (1) a compression cover reducing the class to a finite family of size O(d DS squared n), (2) a menu learning phase covering correct labels of a canonical witness with miss probability O(d DS squared n/n), and (3) a fixed-menu compression phase with description length O(d N squared n).

4. Lower bound construction: A product class combining a noisy Natarajan cube (for the localized fluctuation term) with a Natarajan-free pseudo-cube from [BCD+22] (for the coverage term). The construction uses a pair-Assouad scheme calibrated to L* and a fiber argument on pseudo-cubes.

Extension to list learning. The paper extends both theorems to list learners (outputting r labels per point). Against the best r-tuple of hypotheses, the same architecture yields an optimistic rate with fluctuation sqrt L r* r d N/n and coverage r d DS/n, with a matching lower bound forcing both terms. A byproduct (Corollary 5.3) removes the factor r from the known realizable list lower bound of [HMZ24].

Key insights:

• The binary proof's Boolean-cube geometry does not lift to multiclass; only its comparison principle transfers.

• The two dimensions have different statistical roles: d DS controls correct-label coverage (realizable-order, 1/n), while d N controls localized fluctuations inside the learned menu (scaled by sqrt L*).

• The lower bound certifies this division of labor is intrinsic, not an artifact of analysis.

• The main theorems are machine-checked in Lean 4 (about 4,500 lines, no axioms beyond standard ones).

Based on this paper, I can improve AI systems in the following specific ways:

1. Optimistic Risk-Aware Learning: Build a learning algorithm that automatically interpolates between fast (realizable) and slow (agnostic) convergence rates based on the observed oracle error rate, without needing to know the true noise level in advance. The improved system would achieve the optimal excess risk bound (sqrt L* d N/n + d DS/n) for any fixed label noise level, adapting its sample complexity dynamically.

2. Comparator-Relative Compression: Implement a compression-based learning rule that bounds excess risk relative to any given comparator hypothesis, with the fluctuation term scaling with that comparator's risk (coefficient one). This enables the AI to certify performance guarantees against a reference model, even when the reference is imperfect, without requiring stability assumptions.

3. Selective-Menu Decomposition: Design a two-stage predictor that first learns a small menu of plausible labels per input (controlling coverage errors via the Daniely–Shalev-Shwartz dimension) and then selects within that menu using a Natarajan-dimension-controlled rule. The improved system can explicitly separate and optimize two error sources: missing the correct label entirely vs. picking the wrong label from a correct set.

4. Three-Block Sample Splitting: Use a three-phase training protocol: (a) compress the hypothesis class to a finite cover, (b) learn a per-point label menu with high coverage, (c) run a fixed-menu compression learner. This yields a practical algorithm with provable guarantees that works for large alphabets and unknown noise levels, and is verified in Lean 4 for correctness.

5. List-Learning Extension: Extend the system to output multiple labels per input (e.g., top- r predictions). The improved AI can achieve optimistic rates sqrt L r* r d N/n + r d DS/n against the best r-tuple of hypotheses, making it suitable for high-recall applications like medical diagnosis or recommendation systems where multiple plausible answers are acceptable.

6. Dimension-Aware Regularization: Use the two distinct complexity measures (d N for within-menu discrimination, d DS for label coverage) to guide architecture design or feature selection. The system can allocate capacity separately: one module to ensure the correct label is in the candidate set, another to rank within that set—matching the lower bound's proof that this division is intrinsic.

7. Machine-Checked Guarantees: Adopt the Lean 4 formal verification approach to certify the learning bounds and algorithmic invariants in production AI systems, reducing the risk of subtle implementation bugs in the adaptive rate control or menu construction.

What the improved AI system can do: It can perform multiclass classification with near-optimal sample efficiency across all noise regimes, automatically switching from O(d DS/n) behavior in clean settings to O(sqrt L* d N/n) in noisy ones, while providing formal guarantees on its excess risk. It can also output ranked lists with provable coverage and precision trade-offs, and it can be audited for correctness via machine-checked proofs.

Worst-case multiclass bounds do not become smaller when the best classifier is already nearly correct: what is missing is an optimistic rate, a guarantee whose fluctuation scales with the oracle risk itself. For a class of Natarajan dimension d N and Daniely-Shalev-Shwartz dimension d DS, the optimal excess risk is known at the two endpoints (d DS/n realizable, sqrt d N/n +d DS/n agnostic [HMZ24, CEH+26, Pab26]) and open in between. We close the gap: at every fixed oracle risk L, the optimal excess risk is (sqrt L d N/n +d DS/n), uniformly in the alphabet size, attained by a learner that knows neither L nor the confidence level. The upper bound composes the cover-menu-compression architecture of [CEH+26], at the realizable rate of [Pab26], with a new comparator-facing relative compression theorem: a size- k compression rule that empirically dominates a comparator h has population risk at most L(h)+O(sqrt L(h) +) with =(k n+ (1/delta))/n, without stability; this transfers the comparison principle of the sharp binary theory [MQZ26] while discarding its Boolean-cube geometry, which does not lift to multiclass labels. The lower bound forces both terms using one class and one distribution at every fixed L, by a pair-Assouad scheme calibrated to L and a fiber argument on the pseudo-cubes underlying the Natarajan-versus-DS separation of [BCD+22]. Both theorems extend to list learning: against the best r-tuple of hypotheses, the same architecture and the same two engines yield an optimistic rate and a lower bound of the same shape, forcing the fluctuation term that [Pab26] expected to be necessary against list comparators, and removing the factor r from the known realizable list lower bound.