論文の概要: PAC Learning with Query Feedback

• arxiv url: http://arxiv.org/abs/2610.24332v1
• Date: Fri, 16 Oct 2026 23:56:34 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-26 02:20:20.15131
• Title: PAC Learning with Query Feedback
• Title（参考訳）: クエリフィードバックによるPAC学習
• Abstract要約: 我々は、クエリフィードバックを用いて、実現可能なマルチクラスPAC学習を研究し、各トレーニング例は、単一のバイナリ応答を提供する。 私たちの主な貢献はクエリの次元であり、仮説クラスの構造とラベルを区別する利用可能なクエリの能力の両方をキャプチャするパラメータです。 サンプル複雑度下限の$(D/varepsilon)$,上限の$widetildeO(D2/varepsilon)$を確立し,ラベル数と失敗確率の多変数性を抑制する。
• 参考スコア（独自算出の注目度）: 8.952242119335638
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: We study realizable multiclass PAC learning with query feedback, where each training example provides a single binary response indicating whether its true label belongs to a chosen subset from a fixed query family. Our main contribution is the query dimension, a combinatorial parameter that captures both the structure of the hypothesis class and the ability of the available queries to distinguish labels. This parameter generalizes the bandit DS dimension, which it recovers under singleton queries. We establish a sample-complexity lower bound of $Ω(D/\varepsilon)$ and an upper bound of $\widetilde{O}(D^2/\varepsilon)$, suppressing factors polylogarithmic in the number of labels and the failure probability. When the available queries can split every candidate set into two parts of comparable size, we improve the upper bound to $\widetilde{O}(D/\varepsilon)$, yielding a characterization up to logarithmic factors.
• Abstract（参考訳）: そこで,各学習例は,その真のラベルが固定されたクエリファミリから選択されたサブセットに属するかどうかを示す単一のバイナリ応答を提供する。 我々の主な貢献はクエリの次元であり、仮説クラスの構造とラベルを区別する利用可能なクエリの能力の両方をキャプチャする組合せパラメータである。 このパラメータは、シングルトンクエリで回復するバンドDS次元を一般化する。 我々は、$Ω(D/\varepsilon)$と$\widetilde{O}(D^2/\varepsilon)$のサンプル複素度下界を確立し、ラベルの数と失敗確率の多元性を抑制する。 利用可能なクエリがすべての候補セットを、同等の大きさの2つの部分に分割できる場合、上限を$\widetilde{O}(D/\varepsilon)$に改善し、対数係数まで特徴づける。

関連論文リスト

• Sample Complexity of Multicalibration for Multilevel Properties [52.27687531970317]
  我々は、前のプロパティが固定されたときに各プロパティが識別可能な$k$プロパティの列に対する多重校正について検討する。 多対数的に多くの二元群が存在するにもかかわらず、多重校正誤差$varepsilon$を達成するには$widetilde(varepsilon-(k+2))$サンプルが必要である。
  論文  参考訳（メタデータ） (2026-08-04T23:38:54Z)
• From Contextual Combinatorial Semi-Bandits to Bandit List Classification: Improved Sample Complexity with Sparse Rewards [26.147671458980117]
  我々は、入力コンテキストを、可能なアクションの集合の$m$のサブセットにマッピングするコンテキスト半帯域の問題を研究する。 文脈的包帯の原型的応用により、我々は$s$スパース体制に焦点をあてる。 本フレームワークは,二項報酬ベクトルの特別な場合として,帯域フィードバックを用いたリスト多クラス分類問題を一般化する。
  論文  参考訳（メタデータ） (2025-02-13T12:13:25Z)
• Ehrenfeucht-Haussler Rank and Chain of Thought [51.33559894954108]
  本稿では、よく知られたトランスフォーマーアーキテクチャを基盤とした、ランクの新たな特徴付けについて述べる。 関数 $f$ のランクは、単一層変換器が要求する思考ステップの EmphChain の最小値に対応していることを示す。 また、マルチヘッド単一層トランスをキャプチャするマルチヘッドランクの概念を導入し、有界なマルチヘッドランクを持つ関数クラスのPAC学習性の解析を行う。
  論文  参考訳（メタデータ） (2025-01-22T16:30:58Z)
• Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
  我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。 我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
  論文  参考訳（メタデータ） (2024-06-18T08:54:04Z)
• How to Query An Oracle? Efficient Strategies to Label Data [59.89900843097016]
  機械学習におけるデータセットのラベル付けに専門家の託宣を照会する際の基本的な問題について考察する。 本稿では,サンプルをラベル付けするために,ラウンド・バイ・ラウンドでランダム化されたバッチアルゴリズムを提案し,クエリレートが$O(fracNk2)$であることを示す。 さらに,適応型グリージークエリ方式を提案し,三重項クエリを用いたサンプルあたり平均$approx 0.2N$クエリを実現する。
  論文  参考訳（メタデータ） (2021-10-05T20:15:35Z)
• 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)
• Faster PAC Learning and Smaller Coresets via Smoothed Analysis [25.358415142404752]
  PAC学習は通常、$n$アイテムから小さなサブセット(varepsilon$-sample/net)を計算することを目的としています。 スムーズな解析から着想を得て、クエリに対する強調誤差(最悪のケースではなく)を近似する自然な一般化を提案する。
  論文  参考訳（メタデータ） (2020-06-09T18:25:34Z)
• Binary Classification with XOR Queries: Fundamental Limits and An Efficient Algorithm [15.127728811011245]
  未知ラベルのバイナリ分類のための問合せに基づくデータ取得問題を考える。 我々は、選択したオブジェクトのサブセットの「グループ属性」を問う効果的なクエリタイプを考える。 雑音パラメータが未知であっても,この制限を実現する効率的な推論アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-01-31T11:23:02Z)

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

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