PreprintCC BY 4.0arXiv
Optimal Multiclass Online Regret with Arbitrary Label Spaces
Abstract
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<∞, we prove a regret upper bound of O(min{T,√(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.
Related
- Optimal Regret for Online Storage Control via Cumulative Policies
- Near-Optimal √K-Regret for Online Learning in Uninformed Markov Games
- Dimension-Optimal Dynamic Regret in Exp-Concave Online Learning
- Gradient descent reaches arbitrary accuracy in a fixed number of large steps on multiclass logistic regression
- Dec-BFTRL: Squre-Root Regret for Decentralized Online Upper-Linearizable Optimization under Separation Access with Application to Continuous Submodular Maximization
BibTeX
@misc{ashkezari2026optimal,
title = {{Optimal Multiclass Online Regret with Arbitrary Label Spaces}},
author = {Sajad Ashkezari and Shai Ben-David},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.32339},
eprint = {2610.32339},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.32339},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Optimal Multiclass Online Regret with Arbitrary Label Spaces
AU - Sajad Ashkezari
AU - Shai Ben-David
PY - 2026
DA - 2026/10/23
PB - arXiv
DO - 10.48550/arxiv.2610.32339
UR - https://arxiv.org/abs/2610.32339
AB - 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<∞, we prove a regret upper bound of O(min{T,√(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.
ER -