Metraipolis › archive › dc_72c42867da8b
Optimal Multiclass Online Regret with Arbitrary Label Spaces — arXiv:2610.32339
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.32339
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-26T20:12:01.214Z
- SHA-256 of the archived text
ae48a4b12409ac00af1353b04f2a4dfe01211824b6abbba9f72e7064187a6505- Stable URL of this page
https://metraipolis.com/documento/dc_72c42867da8b
How to cite
Optimal Multiclass Online Regret with Arbitrary Label Spaces — arXiv:2610.32339 — arXiv (en), https://arxiv.org/abs/2610.32339 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_72c42867da8b (Metraipolis archive dc_72c42867da8b, sha256 ae48a4b12409ac00af1353b04f2a4dfe01211824b6abbba9f72e7064187a6505)
BibTeX
@misc{dc72c42867da8b,
title = {Optimal Multiclass Online Regret with Arbitrary Label Spaces — arXiv:2610.32339},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.32339},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_72c42867da8b; sha256 ae48a4b12409ac00af1353b04f2a4dfe01211824b6abbba9f72e7064187a6505},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.32339. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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.
Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.LG, nuovi lavori del giorno).
Categorie arXiv: Machine Learning (cs.LG) ; Machine Learning (stat.ML).
Pagina del lavoro: https://arxiv.org/abs/2610.32339 — 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-26T19:49:03.396Z dalla pagina https://arxiv.org/list/cs.LG/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).