Metraipolis › archive › dc_386cd232dd12

Optimistic Rates for Multiclass PAC Learning — arXiv:2608.10869

Source: arXiv (en)
Original: https://arxiv.org/abs/2608.10869
License (as archived): CC0-1.0
Archived: 2026-10-19T06:19:29.154Z
SHA-256 of the archived text: fa9cf1c92dc2ddb0e4ae0a2d5685162f6a0c558439bbcf660d2829417c4eb316
Stable URL of this page: https://metraipolis.com/documento/dc_386cd232dd12

How to cite

Optimistic Rates for Multiclass PAC Learning — arXiv:2608.10869 — arXiv (en), https://arxiv.org/abs/2608.10869 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_386cd232dd12 (Metraipolis archive dc_386cd232dd12, sha256 fa9cf1c92dc2ddb0e4ae0a2d5685162f6a0c558439bbcf660d2829417c4eb316)

BibTeX

@misc{dc386cd232dd12,
  title = {Optimistic Rates for Multiclass PAC Learning — arXiv:2608.10869},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.10869},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_386cd232dd12; sha256 fa9cf1c92dc2ddb0e4ae0a2d5685162f6a0c558439bbcf660d2829417c4eb316},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.10869. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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^\star$, the optimal excess risk is $\widetilde{\Theta}(\sqrt{L^\star d_N/n}+d_{DS}/n)$, uniformly in the alphabet size, attained by a learner that knows neither $L^\star$ 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)\Gamma}+\Gamma)$ with $\Gamma=(k\log n+\log(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^\star$, by a pair-Assouad scheme calibrated to $L^\star$ 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.

Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-08-12 in cs.LG).
Categorie arXiv: Machine Learning (cs.LG) ; Machine Learning (stat.ML).
Pagina del lavoro: https://arxiv.org/abs/2608.10869 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-19T06:11:45.098Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-08-12?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).