論文の概要: Optimal Multiclass Online Regret with Arbitrary Label Spaces
- arxiv url: http://arxiv.org/abs/2610.32339v1
- Date: Fri, 23 Oct 2026 08:32:10 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-27 01:38:06.437076
- Title: Optimal Multiclass Online Regret with Arbitrary Label Spaces
- Title（参考訳）: 任意ラベル空間を用いた最適マルチクラスオンラインレグレット
- Abstract要約: 我々は、既知の下界と一致する、$O(minT,sqrtdT)$オーバーな$T$ラウンドの後悔の上限を証明する。
我々の証明は、Hanneke et al. (2023) の片面のエキスパートカバーを分数被覆に強化する。
我々は、このカバーとミニマックスの還元を有限の専門家ゲームに組み合わせ、最も応答性の高い報酬は連鎖に必要な不一致境界を与える。
- 参考スコア（独自算出の注目度）: 4.299934797034146
- License: http://creativecommons.org/licenses/by/4.0/
- 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<\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.
- Abstract（参考訳）: 任意の、おそらく無限のラベル空間を持つ、無知なオンライン学習における最適の後悔を判断する。
多級リトルストーン次元$d<\infty$の任意の仮説クラスに対して、既知の下界と一致する$O(\min\{T,\sqrt{dT}\})$ over $T$ラウンドの後悔の上界を証明する。
これは、Hanneke et al (2023) の問題を解き、Alon et al (2021) の最適二項後悔境界を拡張する。
我々の証明は、Hanneke et al (2023) の片面のエキスパートカバーを分数被覆に強化する。
我々はこのカバーとミニマックスの還元を有限の専門家ゲームに組み合わせ、最も応答性の高い報酬は連鎖に必要な不一致境界を与える。
関連論文リスト
- Bandits with Multiple Optimal Arms: Minimax Regret and Non-Adaptivity [54.77408659142336]
我々は,複数の最適な腕を持つマルチアーム・バンディット(MAB)について検討し,実際的な意思決定問題の多くが複数の正解を許容しているという事実に動機づけられた。
たとえば$tildeOBig(fracK-AsqrtKAsqrtT Big)$ minimax regret, where $T$ is the total number of interaction and $tilde O(cdot)$ drops all constant and logarithmic factors。
論文 参考訳（メタデータ） (2026-09-29T23:33:10Z) - Sharp Oracle-Regret Tradeoffs for Projection-Free Online Convex Optimization [55.29259818039367]
我々は, オンライン凸最適化において, 実現可能な集合へのアクセスが正確な線形最適化オラクルに制限された場合に達成可能な後悔を特徴づける。
コンベックス$G$-Lipschitzの損失に対して、直径は最大$D$、合計$Q$オークルコールは$Q$、厳格な制限はラウンド当たり$B$である。
論文 参考訳（メタデータ） (2026-09-23T22:25:52Z) - Minimax Alternating Regret for the Experts Problem and Online Convex Optimization [13.08870048693199]
ミニマックスの交互後悔は地平線から独立して$(log d)$であることを示す。
さらに、この結果を$d$次元コンパクト凸集合上で一般のOCOに拡張する。
論文 参考訳（メタデータ） (2026-08-25T21:56:20Z) - A Tight Lower Bound for Non-stochastic Multi-armed Bandits with Expert Advice [28.32015131406357]
古典的非確率的マルチアームバンディットにおけるミニマックス最適後悔を専門的助言問題で決定する。
ここで、$K$は腕の数、$N$は専門家の数、$T$は時間軸である。
論文 参考訳（メタデータ） (2025-10-31T21:01:53Z) - Multiclass Transductive Online Learning [14.093228102168872]
本稿では,ラベルの数が無制限である場合のオンライン学習の帰納的課題について考察する。
レベル制約されたリトルストーン次元と呼ばれる新しい次元は、この設定におけるオンライン学習可能性の特徴である。
ラベル空間が非有界である場合でも、期待されるミス回数の最小値の3分法が保たれることを示す。
論文 参考訳（メタデータ） (2024-11-03T16:57:13Z) - The Real Price of Bandit Information in Multiclass Classification [73.17969992976501]
バンディットフィードバックを用いた複数クラス分類の古典的問題を再考する。
我々は, 後悔すべき$smashwidetildeO(|H|+sqrtT)$を保証する新しい帯域分類アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-05-16T12:11:09Z) - Multiclass Online Learning and Uniform Convergence [34.21248304961989]
対戦型オンライン学習環境におけるマルチクラス分類について検討する。
任意のマルチクラスの概念クラスが、そのリトルストーン次元が有限である場合に限り、不可知的に学習可能であることを証明する。
論文 参考訳（メタデータ） (2023-03-30T21:35:48Z) - Near Optimal Memory-Regret Tradeoff for Online Learning [14.50671354550329]
約$sqrtn$Memoryは必要であり、また、$o(T)$ regretを取得するのに十分であることを示す。
また、エージェントが選択した過去の専門家を観察できる適応的な敵についても検討する。
論文 参考訳（メタデータ） (2023-03-03T02:24:06Z) - Complete Policy Regret Bounds for Tallying Bandits [51.039677652803675]
政策後悔は、適応的な敵に対してオンライン学習アルゴリズムのパフォーマンスを測定するという、よく確立された概念である。
我々は,不完全な政策後悔を効果的に最小化できる敵の制限について検討する。
我々は、$tildemathcalO(mKsqrtT)$の完全なポリシーを後悔するアルゴリズムを提供し、$tildemathcalO$表記は対数要素だけを隠す。
論文 参考訳（メタデータ） (2022-04-24T03:10:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。