論文の概要: Bandit Multiclass List Classification

• arxiv url: http://arxiv.org/abs/2502.09257v2
• Date: Thu, 05 Jun 2025 07:39:15 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-06 19:24:15.932625
• Title: Bandit Multiclass List Classification
• Title（参考訳）: Bandit Multiclass List 分類
• Authors: Liad Erez, Tomer Koren,
• Abstract要約: 入力例を$K$のラベル集合のサブセットにマッピングする(セミバンドフィードバック)マルチクラスリスト分類の問題について検討する。 この結果は,より単純な単一ラベル設定(Erez et al. '24)における先行作業の一般化と拡張であり,より一般的には$s$スパース報酬を伴う文脈的半帯域問題に適用される。
• 参考スコア（独自算出の注目度）: 28.483435983018616
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of multiclass list classification with (semi-)bandit feedback, where input examples are mapped into subsets of size $m$ of a collection of $K$ possible labels. In each round of the interaction, the learner observes feedback consisting of the predicted labels which lie in some underlying set of ground truth labels associated with the given example. Our main result is for the $(\varepsilon,\delta)$-PAC variant of the problem for which we design an algorithm that returns an $\varepsilon$-optimal hypothesis with high probability using a sample complexity of $\widetilde{O} \big( (\mathrm{poly}(K/m) + sm / \varepsilon^2) \log (|H|/\delta) \big)$ where $H$ is the underlying (finite) hypothesis class and $s$ is an upper bound on the number of true labels for a given example. This bound improves upon known bounds for combinatorial semi-bandits whenever $s \ll K$. Moreover, in the regime where $s = O(1)$ the leading terms in our bound match the corresponding full-information rates, implying that bandit feedback essentially comes at no cost. Our PAC learning algorithm is also computationally efficient given access to an ERM oracle for $H$. In the special case of single-label classification corresponding to $s=m=1$, we prove a sample complexity bound of $O \big((K^7 + 1/\varepsilon^2)\log (|H|/\delta)\big)$ which improves upon recent results in this scenario (Erez et al. '24). Additionally, we consider the regret minimization setting where data can be generated adversarially, and establish a regret bound of $\widetilde O(|H| + \sqrt{smT \log |H|})$. Our results generalize and extend prior work in the simpler single-label setting (Erez et al. '24), and apply more generally to contextual combinatorial semi-bandit problems with $s$-sparse rewards.
• Abstract（参考訳）: 入力例を$K$のラベル集合のサブセットにマッピングする(セミバンドフィードバック)マルチクラスリスト分類の問題について検討する。 対話の各ラウンドにおいて、学習者は、与えられた例に関連する基礎となる真実のラベルのセットに含まれる予測されたラベルからなるフィードバックを観察する。 我々の主な成果は、$(\varepsilon,\delta)$-PAC 変種である。 $\widetilde{O} \big((\mathrm{poly}(K/m) + sm / \varepsilon^2) \log (|H|/\delta) \big)$ ここで、$H$ は基礎となる(有限)仮説クラスであり、$s$ は実ラベルの上限である。 この境界は、$s \ll K$ のとき、組合せ半バンドの既知の境界を改善する。 さらに、"$s = O(1)$"の条件が対応する全情報レートと一致している状況では、バンドリットフィードバックは本質的にコストがかからないことを意味します。 当社のPAC学習アルゴリズムは,ERMオラクルへのアクセスを$H$で計算的に効率よく行うことができる。 単ラベル分類が$s=m=1$に対応する特別な場合、このシナリオにおける最近の結果を改善する$O \big((K^7 + 1/\varepsilon^2)\log (|H|/\delta)\big)$のサンプル複雑性境界を証明する(Erez et al '24)。 さらに、データを逆向きに生成できる後悔最小化設定を考慮し、$\widetilde O(|H| + \sqrt{smT \log |H|})$の後悔境界を確立する。 より単純な単一ラベル設定(Erez et al '24)における先行作業の一般化と拡張を行い、より一般的には$s$スパース報酬を伴う文脈組合せ半帯域問題に適用する。

関連論文リスト

• Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
  我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。 我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
  論文  参考訳（メタデータ） (2024-06-18T08:54:04Z)
• The Real Price of Bandit Information in Multiclass Classification [73.17969992976501]
  バンディットフィードバックを用いた複数クラス分類の古典的問題を再考する。 我々は, 後悔すべき$smashwidetildeO(|H|+sqrtT)$を保証する新しい帯域分類アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-05-16T12:11:09Z)
• Context-lumpable stochastic bandits [49.024050919419366]
  我々は、$S$コンテキストと$K$アクションによる文脈的盗賊問題を考える。 我々は,最大$widetilde O(r (S +K )/epsilon2)$サンプルを用いて,$epsilon$-optimal Policyを出力するアルゴリズムを提案する。 後悔の設定では、T$までの累積後悔を$widetilde O(sqrtr3(S+K)T)$で束縛するアルゴリズムを与える。
  論文  参考訳（メタデータ） (2023-06-22T17:20:30Z)
• List-Decodable Sparse Mean Estimation via Difference-of-Pairs Filtering [42.526664955704746]
  そこで我々は,リストデコダブルなスパース平均推定のための,新しい,概念的にシンプルな手法を開発した。 特に、$k$-sparse方向の「確実に有界な」$t-thモーメントを持つ分布の場合、このアルゴリズムは、サンプル複雑性$m = (klog(n))O(t)/alpha(mnt)$の誤差を1/alpha(O (1/t)$で達成する。 Gaussian inliers の特別な場合、我々のアルゴリズムは $Theta (sqrtlog) の最適誤差を保証する。
  論文  参考訳（メタデータ） (2022-06-10T17:38:18Z)
• Self-training Converts Weak Learners to Strong Learners in Mixture Models [86.7137362125503]
  擬似ラベルの $boldsymbolbeta_mathrmpl$ が,最大$C_mathrmerr$ の分類誤差を達成可能であることを示す。 さらに、ロジスティックな損失に対して勾配降下を実行することで、ラベル付き例のみを使用して、分類誤差が$C_mathrmerr$で擬ラベルの $boldsymbolbeta_mathrmpl$ が得られることを示す。
  論文  参考訳（メタデータ） (2021-06-25T17:59:16Z)
• Semi-supervised Active Regression [21.51757844385258]
  本稿では,学習課題における偏りのある部分ラベル付きデータの利用について検討する。 学習者は、追加のラベルクエリをほとんど行わずに、mathbbRd | X min_beta in mathbbRd | X beta - Y |2 end2 方程式でデータセット $X にアクセスすることができる。
  論文  参考訳（メタデータ） (2021-06-12T03:28:43Z)
• Active Local Learning [22.823171570933397]
  クエリポイント$x$とラベルなしのトレーニングセット$S$へのアクティブアクセスを与えられた場合、H$でほぼ最適な$hの予測$h(x)$を出力します。 特にラベルクエリの数は$H$の複雑さとは無関係でなければならないし、関数$h$は$x$とは無関係に明確に定義されるべきである。 これはまた、すぐに距離推定のアルゴリズムを示唆している: ほぼ最適の$hを実際に学習するのに必要となる多くのラベルから$opt(H)$を推定する。
  論文  参考訳（メタデータ） (2020-08-31T05:39:35Z)
• $Q$-learning with Logarithmic Regret [60.24952657636464]
  楽観的な$Q$は$mathcalOleft(fracSAcdot mathrmpolyleft(Hright)Delta_minlogleft(SATright)right)$ cumulative regret bound, where $S$ is the number of state, $A$ is the number of action, $H$ is the planning horizon, $T$ is the total number of steps, $Delta_min$ is the least sub-Optitimality gap。
  論文  参考訳（メタデータ） (2020-06-16T13:01:33Z)
• 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)
• A Multiclass Classification Approach to Label Ranking [2.6905021039717987]
  マルチクラスの分類において、目標は、$mathcalY=1,; ldots,; K $ with $Kgeq 3$で値を値するランダムラベル$Y$の予測方法を学ぶことである。 本稿では,多クラス分類と後続確率推定の中間点である,この統計的学習問題の解析に焦点をあてる。
  論文  参考訳（メタデータ） (2020-02-21T17:12:43Z)

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

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