論文の概要: Fast Rates for Bandit PAC Multiclass Classification

• arxiv url: http://arxiv.org/abs/2406.12406v1
• Date: Tue, 18 Jun 2024 08:54:04 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-19 19:56:37.291220
• Title: Fast Rates for Bandit PAC Multiclass Classification
• Title（参考訳）: Bandit PAC Multiclass 分類の高速化
• Authors: Liad Erez, Alon Cohen, Tomer Koren, Yishay Mansour, Shay Moran,
• Abstract要約: 我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。 我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
• 参考スコア（独自算出の注目度）: 73.17969992976501
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study multiclass PAC learning with bandit feedback, where inputs are classified into one of $K$ possible labels and feedback is limited to whether or not the predicted labels are correct. Our main contribution is in designing a novel learning algorithm for the agnostic $(\varepsilon,\delta)$-PAC version of the problem, with sample complexity of $O\big( (\operatorname{poly}(K) + 1 / \varepsilon^2) \log (|H| / \delta) \big)$ for any finite hypothesis class $H$. In terms of the leading dependence on $\varepsilon$, this improves upon existing bounds for the problem, that are of the form $O(K/\varepsilon^2)$. We also provide an extension of this result to general classes and establish similar sample complexity bounds in which $\log |H|$ is replaced by the Natarajan dimension. This matches the optimal rate in the full-information version of the problem and resolves an open question studied by Daniely, Sabato, Ben-David, and Shalev-Shwartz (2011) who demonstrated that the multiplicative price of bandit feedback in realizable PAC learning is $\Theta(K)$. We complement this by revealing a stark contrast with the agnostic case, where the price of bandit feedback is only $O(1)$ as $\varepsilon \to 0$. Our algorithm utilizes a stochastic optimization technique to minimize a log-barrier potential based on Frank-Wolfe updates for computing a low-variance exploration distribution over the hypotheses, and is made computationally efficient provided access to an ERM oracle over $H$.
• Abstract（参考訳）: 我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。 我々の主な貢献は、問題の非依存的な$(\varepsilon,\delta)$-PACバージョンのための新しい学習アルゴリズムを設計することであり、サンプル複雑性は$O\big( (\operatorname{poly}(K) + 1 / \varepsilon^2) \log (|H| / \delta) \big)$ である。 $\varepsilon$ への主要な依存に関して、この問題に対する既存の境界、すなわち $O(K/\varepsilon^2)$ の形式により改善される。 また、この結果の一般クラスへの拡張を提供し、$\log |H|$ をナタラジャン次元に置き換える類似のサンプル複雑性境界を確立する。 これは問題の完全情報版における最適率と一致し、Daniely, Sabato, Ben-David, Shalev-Shwartz (2011) が研究したオープンな疑問を解決し、実現可能なPAC学習における帯域幅フィードバックの乗算価格が$\Theta(K)$であることを示した。 ここでは、バンドイットフィードバックの価格は、$O(1)$ as $\varepsilon \to 0$ である。 提案アルゴリズムは, 確率的最適化手法を用いて, 仮説上の低分散探索分布を計算するためのFrank-Wolfe更新に基づく対数バリアポテンシャルを最小化する。

関連論文リスト

• Almost Minimax Optimal Best Arm Identification in Piecewise Stationary Linear Bandits [55.957560311008926]
  そこで本研究では,各文脈の平均値によって腕の質を計測するPSLBモデルを提案する。 PS$varepsilon$BAI$+$は、$varepsilon$-optimal armを、確率$ge 1-delta$と最小限のサンプルで識別することが保証される。
  論文  参考訳（メタデータ） (2024-10-10T06:15:42Z)
• Beyond Minimax Rates in Group Distributionally Robust Optimization via a Novel Notion of Sparsity [14.396304498754688]
  私たちは、$(lambda, beta)$-sparsityをダブした、空白という新しい概念を示します。 また、最適な$(lambda, beta)$-sparsity条件に適応する適応アルゴリズムを示す。
  論文  参考訳（メタデータ） (2024-10-01T13:45:55Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• Asymptotically Optimal Pure Exploration for Infinite-Armed Bandits [4.811176167998627]
  我々は、未知の分布から生じる無限に多くのバンドイットアームを用いて純粋探索を研究する。 私たちのゴールは、平均的な報酬が1-delta$の1つの高品質なアームを、最高の$eta$-fraction of armsの1つとして$varepsilon$内で効率的に選択することにあります。
  論文  参考訳（メタデータ） (2023-06-03T04:00:47Z)
• Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP [58.13930707612128]
  この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。 我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
  論文  参考訳（メタデータ） (2022-12-01T15:57:58Z)
• Instance-optimal PAC Algorithms for Contextual Bandits [20.176752818200438]
  この作業では、$(epsilon,delta)$-$textitPAC$設定における帯域幅の問題に焦点を当てます。 最良腕識別のための最小限の後悔最小化とインスタンス依存のPACを同時に行うアルゴリズムは存在しないことを示す。
  論文  参考訳（メタデータ） (2022-07-05T23:19:43Z)
• Cascading Bandit under Differential Privacy [21.936577816668944]
  本研究では,カスケードバンドにおける自己差分プライバシー(DP)と局所差分プライバシー(LDP)について検討する。 DPでは,$epsilon$-indistinguishability を保証し,$mathcalO(fraclog3 Tepsilon)$を任意の小さな$xi$に対して後悔するアルゴリズムを提案する。 Epsilon$,$delta$)-LDPの下では、プライバシの予算とエラー確率のトレードオフを通じて、K2$依存を緩和します。
  論文  参考訳（メタデータ） (2021-05-24T07:19:01Z)
• Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks [48.32532049640782]
  ガウス境界の下で, 1層ReLUネットワークを$k$の隠れ単位で学習する問題をmathbbRd$で研究する。 正の係数の場合、この学習問題の初回アルゴリズムを$k$から$tildeOOmega(sqrtlog d)$まで与える。
  論文  参考訳（メタデータ） (2020-06-22T17:53:54Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)
• Nearly Optimal Regret for Stochastic Linear Bandits with Heavy-Tailed Payoffs [35.988644745703645]
  我々は、リニアバンディットをヘビーテールのペイオフで分析し、そこではペイオフは1+epsilon$のモーメントしか持たない。 本稿では,$widetildeO(dfrac12Tfrac11+epsilon)$のサブ線形後悔境界を満足する2つの新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-04-28T13:01:38Z)

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

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