Papers › Optimistic Rates for Multiclass PAC Learning
Optimistic Rates for Multiclass PAC Learning
Xiaoyu Li, Andi Han, Jiaojiao Jiang, Junbin Gao
Title, abstract, authors and date from arXiv's metadata (CC0); this paper is not in the Papers with Code archive (frozen 2025-07-28).
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, √(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 (√(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(√(L(h)Γ)+Γ) with Γ=(klogn+log(1/δ))/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.
In Syntology Open this paper in Syntology's Atlas, the map of the papers in Syntology's graph and their citations.
Code
Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Syntology holds the repository link but has not harvested or run code from it.
Results from the paper
The Papers with Code archive ends with its 2025-07-28 snapshot. This paper's arXiv identifier, 2608.10869, was issued in August 2026, after that date, so the archive has no leaderboard rows for it.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections