論文の概要: The Real Price of Bandit Information in Multiclass Classification

• arxiv url: http://arxiv.org/abs/2405.10027v2
• Date: Wed, 19 Jun 2024 09:20:04 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-22 03:59:12.484239
• Title: The Real Price of Bandit Information in Multiclass Classification
• Title（参考訳）: マルチクラス分類における帯域情報の真価
• Authors: Liad Erez, Alon Cohen, Tomer Koren, Yishay Mansour, Shay Moran,
• Abstract要約: バンディットフィードバックを用いた複数クラス分類の古典的問題を再考する。 我々は, 後悔すべき$smashwidetildeO(|H|+sqrtT)$を保証する新しい帯域分類アルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 73.17969992976501
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We revisit the classical problem of multiclass classification with bandit feedback (Kakade, Shalev-Shwartz and Tewari, 2008), where each input classifies to one of $K$ possible labels and feedback is restricted to whether the predicted label is correct or not. Our primary inquiry is with regard to the dependency on the number of labels $K$, and whether $T$-step regret bounds in this setting can be improved beyond the $\smash{\sqrt{KT}}$ dependence exhibited by existing algorithms. Our main contribution is in showing that the minimax regret of bandit multiclass is in fact more nuanced, and is of the form $\smash{\widetilde{\Theta}\left(\min \left\{|H| + \sqrt{T}, \sqrt{KT \log |H|} \right\} \right) }$, where $H$ is the underlying (finite) hypothesis class. In particular, we present a new bandit classification algorithm that guarantees regret $\smash{\widetilde{O}(|H|+\sqrt{T})}$, improving over classical algorithms for moderately-sized hypothesis classes, and give a matching lower bound establishing tightness of the upper bounds (up to log-factors) in all parameter regimes.
• Abstract（参考訳）: 我々は,帯域幅フィードバック(Kakade,Shalev-Shwartz,Tewari,2008)によるマルチクラス分類の古典的問題を再検討し,各入力がK$可能なラベルの1つに分類し,予測されたラベルが正しいか否かに限定する。 我々の第一の質問は、ラベルの数への依存についてであり、既存のアルゴリズムが示す$\smash{\sqrt{KT}}$依存を超えて、この設定における$T$-stepの後悔境界を改善することができるかどうかである。 我々の主な貢献は、バンディット・マルチクラスのミニマックス後悔は、実際にはよりニュアンスなものであり、$\smash{\widetilde{\Theta}\left(\min \left\{|H| + \sqrt{T}, \sqrt{KT \log |H|} \right\} \right) }$の形のものであることを示すことである。 特に、後悔の$\smash{\widetilde{O}(|H|+\sqrt{T})}$を保証し、中等度な仮説クラスに対する古典的アルゴリズムを改良し、全てのパラメータ体系における上限(対数要素まで)の整合性に一致する下界を与える新しいバンド分類アルゴリズムを提案する。

関連論文リスト

• Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
  我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。 我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
  論文  参考訳（メタデータ） (2024-06-18T08:54:04Z)
• Communication-Constrained Bandits under Additive Gaussian Noise [111.06688156723018]
  クライアントが学習者にコミュニケーション制約のあるフィードバックを提供する分散マルチアームバンディットについて検討する。 我々は、この下限を小さな加法係数にマッチさせるマルチフェーズ帯域幅アルゴリズム、$mathtUEtext-UCB++$を提案する。
  論文  参考訳（メタデータ） (2023-04-25T09:31:20Z)
• The Best of Both Worlds: Reinforcement Learning with Logarithmic Regret and Policy Switches [84.54669549718075]
  漸進的強化学習(RL)における後悔の最小化問題について検討する。 一般関数クラスと一般モデルクラスで学ぶことに集中する。 対数的後悔境界は$O(log T)$スイッチングコストのアルゴリズムによって実現可能であることを示す。
  論文  参考訳（メタデータ） (2022-03-03T02:55:55Z)
• Beyond Bandit Feedback in Online Multiclass Classification [17.07011090727996]
  学習者のフィードバックが任意の有向グラフによって決定されるような環境で,オンライン多クラス分類の問題について検討する。 任意のフィードバックグラフで動作する,初のオンラインマルチクラスアルゴリズムであるGappletronを紹介する。
  論文  参考訳（メタデータ） (2021-06-07T13:22:30Z)
• Impact of Representation Learning in Linear Bandits [83.17684841392754]
  本研究では,表現学習が帯域幅問題の効率性を向上させる方法について検討する。 我々は,$widetildeO(TsqrtkN + sqrtdkNT)$ regretを達成する新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-10-13T16:35:30Z)
• Exploiting the Surrogate Gap in Online Multiclass Classification [13.452510519858995]
  Gaptronは、オンラインのマルチクラス分類のためのランダム化された一階述語アルゴリズムである。 その結果,ロジスティックな損失,ヒンジの損失,スムーズなヒンジの損失に対して,常に後悔する結果が得られた。 ゼロワン損失とサロゲート損失のギャップを利用した新しい証明手法を提案する。
  論文  参考訳（メタデータ） (2020-07-24T16:19:02Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)
• A Multiclass Classification Approach to Label Ranking [2.6905021039717987]
  マルチクラスの分類において、目標は、$mathcalY=1,; ldots,; K $ with $Kgeq 3$で値を値するランダムラベル$Y$の予測方法を学ぶことである。 本稿では,多クラス分類と後続確率推定の中間点である,この統計的学習問題の解析に焦点をあてる。
  論文  参考訳（メタデータ） (2020-02-21T17:12:43Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。