論文の概要: PAC Learning with Bandit Feedback: Sharp Sample Complexity in the Realizable Setting

• arxiv url: http://arxiv.org/abs/2605.25678v2
• Date: Tue, 26 May 2026 08:08:44 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-27 17:51:41.164812
• Title: PAC Learning with Bandit Feedback: Sharp Sample Complexity in the Realizable Setting
• Title（参考訳）: 帯域フィードバックによるPAC学習: 実現可能な設定におけるシャープサンプル複雑さ
• Authors: Steve Hanneke, Qinglin Meng, Shay Moran, Amirreza Shaeiri,
• Abstract要約: 本研究では,マルチクラスPAC学習における帯域幅フィードバックによる課題について検討する。 このフレームワークでは、インスタンススペース$mathcalX$とラベルスペース$mathcalY$に未知のデータ分散があります。 我々は、この問題の最適サンプルの一般的な特徴を与え、すべての概念クラスを複雑さまで鋭くする。
• 参考スコア（独自算出の注目度）: 46.089126569274676
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of multiclass PAC learning with bandit feedback in the realizable setting. In this framework, there is an unknown data distribution over an instance space $\mathcal{X}$ and a label space $\mathcal{Y}$, as in classical multiclass PAC learning, but the learner does not observe the labels of the i.i.d. training examples. Instead, in each round, it receives an unlabeled instance, predicts its label, and receives bandit feedback indicating only whether the prediction is correct. Despite this restriction, the goal remains the same as in classical PAC learning. We provide a general characterization of the optimal sample complexity of this problem, sharp for every concept class up to logarithmic factors. Our characterization is based on a new combinatorial dimension, termed the bandit $\mathrm{DS}$ dimension, defined via generalized combinatorial structures we call pseudo-boxes. These extend the pseudo-cubes underlying the $\mathrm{DS}$ dimension by allowing a different number of neighbors in each coordinate. In contrast to the $\mathrm{DS}$ dimension, which governs the full-information setting by counting the number of coordinates in the pseudo-cube, the bandit $\mathrm{DS}$ dimension aggregates the number of neighbors across coordinates, leading to a characterization in which the sample complexity scales with the total number of neighbors. We also propose a general learning algorithm achieving the upper bound, based on an algorithmic principle called ListCascade, which connects bandit learning to list learning and may be of independent interest.
• Abstract（参考訳）: 本研究では,マルチクラスPAC学習における帯域幅フィードバックによる課題について検討する。 このフレームワークでは、古典的なマルチクラスPAC学習のように、インスタンス空間$\mathcal{X}$とラベル空間$\mathcal{Y}$に未知のデータ分布があるが、学習者はi.d.トレーニング例のラベルを観察しない。 その代わりに、各ラウンドでラベルなしのインスタンスを受け取り、ラベルを予測し、予測が正しいかどうかのみを示す帯域幅フィードバックを受け取る。 この制限にもかかわらず、ゴールは古典的なPAC学習と同じである。 この問題の最適サンプル複雑性の一般的な特徴として、対数的因子まですべての概念クラスに鋭いものを挙げる。 我々の特徴付けは、擬箱と呼ばれる一般化された組合せ構造を通して定義されるbandit $\mathrm{DS}$ dimensionと呼ばれる新しい組合せ次元に基づいている。 これらは、各座標において異なる数の近傍を許容することにより、$\mathrm{DS}$次元の擬キューブを拡張する。 擬キューブ内の座標数を数えて全情報設定を管理する$\mathrm{DS}$ dimensionとは対照的に、bandit $\mathrm{DS}$ dimension は座標をまたいだ隣人の数を集約し、サンプルの複雑さが隣人の総数と共にスケールする特徴を与える。 また,帯域学習とリスト学習を結びつけるアルゴリズムであるListCascadeをベースとして,上位境界を達成するための一般学習アルゴリズムを提案する。

関連論文リスト

• Learning Conditional Averages [52.361762722359366]
  本稿では,PACフレームワークにおける条件平均学習の問題を紹介する。 ターゲットのコンセプトそのものを学ぶのではなく、各インスタンスの平均ラベルをその周辺で予測することが目標だ。 より一般的には、PAC学習をいくつかのドメインで発生する学習タスクをキャプチャする設定に拡張する。
  論文  参考訳（メタデータ） (2026-02-12T13:20:29Z)
• From Contextual Combinatorial Semi-Bandits to Bandit List Classification: Improved Sample Complexity with Sparse Rewards [26.147671458980117]
  我々は、入力コンテキストを、可能なアクションの集合の$m$のサブセットにマッピングするコンテキスト半帯域の問題を研究する。 文脈的包帯の原型的応用により、我々は$s$スパース体制に焦点をあてる。 本フレームワークは,二項報酬ベクトルの特別な場合として,帯域フィードバックを用いたリスト多クラス分類問題を一般化する。
  論文  参考訳（メタデータ） (2025-02-13T12:13:25Z)
• 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)
• A Fast Algorithm for the Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit [55.2480439325792]
  多武装バンディット(R-CPE-MAB)の真価純探査問題について検討する。 本稿では,差分に基づく探索法 (CombGapE) アルゴリズムを提案する。 我々は,CombGapEアルゴリズムが,合成データセットと実世界のデータセットの両方において,既存の手法を大幅に上回っていることを数値的に示す。
  論文  参考訳（メタデータ） (2023-06-15T15:37:31Z)
• Statistical learning on measures: an application to persistence diagrams [0.0]
  有限次元ユークリッド空間にデータを持つ代わりに、コンパクト空間 $mathcalX$ の測度を観測するバイナリ教師付き学習分類問題を考える。 当社のフレームワークは,私たちが対処可能な入力データに対して,より柔軟性と多様性を実現しています。 このようなフレームワークは多くの可能なアプリケーションを持っていますが、この作業は永続図と呼ばれるトポロジ的記述子によるデータの分類に強く重点を置いています。
  論文  参考訳（メタデータ） (2023-03-15T09:01:37Z)
• 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)

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

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