Optimal Multiclass Online Regret with Arbitrary Label Spaces
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…
- 用途
- 原典で確認
- 難易度の目安
- Hard
- 実装コストの目安
- Medium
概要
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.
参考リンク
リンク先のライセンス・再現性・データ条件をご確認ください。自動分類や実装の目安は保証ではありません。
実装を始めるプロンプト
参考リンクを確認したうえで、次の内容をコピーして利用できます。
# 論文・記事 Optimal Multiclass Online Regret with Arbitrary Label Spaces # 概要 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… # 原典 https://arxiv.org/abs/2610.32339 上記の手法を実装してください。実行前に依存関係とライセンスを確認してください。