論文の概要: Bandit Multiclass PAC Learning: Corrected Lower Bounds, Exact Families, and a Confidence Direct-Sum Phenomenon

• arxiv url: http://arxiv.org/abs/2609.29694v1
• Date: Mon, 31 Aug 2026 05:23:35 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-28 05:09:56.111474
• Title: Bandit Multiclass PAC Learning: Corrected Lower Bounds, Exact Families, and a Confidence Direct-Sum Phenomenon
• Title（参考訳）: Bandit Multiclass PAC Learning: 修正下界, 厳密な家族, 信頼直接現象
• Abstract要約: 我々は,帯域幅フィードバックを用いて,実現可能な多クラスPAC学習について検討する。 我々は、新しいアンカー次元$mathrmaBDSlemathrmBDS$に関する下界理論を修復する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study realizable multiclass PAC learning with bandit feedback: the learner observes an i.i.d. instance, predicts one of $K$ labels, and learns only whether the prediction was correct. Hanneke, Meng, Moran, and Shaeiri (arXiv:2605.25678) characterized the optimal sample complexity via the bandit DS dimension $\mathrm{BDS}$ up to logarithmic factors, and asked whether every class admits sample complexity $O((\mathrm{BDS}+\log(1/δ))/ε)$. First, we show that the published lower bound $Ω((\mathrm{BDS}+\log(1/δ))/ε)$ is incorrect as stated: we exhibit explicit classes with $\mathrm{BDS}=K-1$ whose sample complexity is exponentially smaller, and locate two independent gaps in its proof. We repair the lower-bound theory around a new anchored dimension $\mathrm{aBDS}\le\mathrm{BDS}$, proving a constant-free three-part lower bound. On the upper-bound side we remove the ambient label count $K$ entirely, proving $O((B\log^3 B+B\log(1/δ))/ε)$ for $B=\mathrm{BDS}$, plus a constant-confidence bound via a new fiberization lemma; for two natural families we determine the sample complexity up to constant factors. Finally, we answer the open question in the negative under its uniform-constant reading, and show the failure is intrinsic: for an explicit affine multiplexer class we establish the full confidence profile $Θ((n\min{n,\log(1/δ)}+\log(1/δ))/ε)$, a confidence direct-sum regime where a multiplicative $\log(1/δ)$ cost is information-theoretically necessary, followed by a rank-saturation phase transition. Two classes with identical dimension profiles can have polynomially different sample complexities, so no characterization by these dimensions alone is accurate to polylogarithmic factors. We also show these results are consistent with additive-confidence list-PAC guarantees via the ListCascade bridge.
• Abstract（参考訳）: 学習者はi.i.d.を観測し、K$ラベルの1つを予測し、その予測が正しいかどうかのみを学習する。 Hanneke, Meng, Moran, and Shaeiri (arXiv:2605.25678) は、バンドイットDS次元$\mathrm{BDS}$から対数因子までの最適なサンプル複雑性を特徴付け、全てのクラスがサンプル複雑性$O((\mathrm{BDS}+\log(1/δ))/ε)$を許容するかどうかを問うた。 まず、公表された下界 $Ω((\mathrm{BDS}+\log(1/δ))/ε)$ が不正確であることを示す。 我々は、新しいアンカー次元 $\mathrm{aBDS}\le\mathrm{BDS}$ に関する下界理論を修復し、定数自由な三部分下界を証明した。 上行側では、周囲のラベル数$K$を完全に取り除き、$O((B\log^3 B+B\log(1/δ))/ε)$ for $B=\mathrm{BDS}$、および新しいファイバー化補題によって束縛された定数自信を証明します。 明示的なアフィン多重化クラスでは、全信頼プロファイル $ ((n\min{n,\log(1/δ)}+\log(1/δ))/ε)$、乗法的な$\log(1/δ)$コストが情報理論的に必要であり、次いでランク飽和相転移(英語版)が成立する。 同一次元プロファイルを持つ2つのクラスは多項式的に異なるサンプル複素数を持つことができるので、これらの次元のみによる特徴づけは多元数因子に正確である。 また、これらの結果はListCascadeブリッジを介して追加信頼リスト-PAC保証と一致していることを示す。

関連論文リスト

• Gap Entropy and Almost Instance-Wise Optimal Best-Arm Identification [10.999442451351385]
  順序公約のインスタンス右下界が$ (H(I)[log(1/)+Ent(I)])であることが示される。 また、期待されるサンプル複雑性を持つ単一の$$-correctアルゴリズムを、O(H(I)[log(e+log(e+D))),D=_[2]-2,$に対して、そのギャップを事前に知ることなく与える。 我々の下限は、以前の作業のdyadic-gapとmonotonicity制限を取り除き、上限は追加の多対数性を取り除きます。
  論文  参考訳（メタデータ） (2026-09-12T04:31:38Z)
• Optimal Rates for Learning with Monotone Adversaries [7.053805156684374]
  モノトン対向は、i.i.d.ラベル付きサンプルを観察し、その選択の有限個の例を付加する。 すべてのサンプルは正しくラベル付けされているが、挿入はクリーンサンプルに依存するため、組み合わせたサンプルは交換できない。 このモデルを導入したLarsen、Pabbaraju、およびShettyは、VC次元$d$のクラスに対して、経験的リスク最小化が予測誤差$O((d/n)log(n/d))$に達することを示した。
  論文  参考訳（メタデータ） (2026-08-06T17:45:32Z)
• Sample Complexity of Multicalibration for Multilevel Properties [52.27687531970317]
  我々は、前のプロパティが固定されたときに各プロパティが識別可能な$k$プロパティの列に対する多重校正について検討する。 多対数的に多くの二元群が存在するにもかかわらず、多重校正誤差$varepsilon$を達成するには$widetilde(varepsilon-(k+2))$サンプルが必要である。
  論文  参考訳（メタデータ） (2026-08-04T23:38:54Z)
• High-accuracy sampling for diffusion models and log-concave distributions [70.90863485771405]
  本稿では,$mathrmpolylog (1/)$のステップで$$-errorを求める拡散モデルサンプリングアルゴリズムを提案する。 我々の手法は、一般的なログ凹凸分布に対する最初の$mathrmpolylog (1/)$ complexity samplerをもたらす。
  論文  参考訳（メタデータ） (2026-02-01T17:05:31Z)
• Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
  以前の$mathRd上の分布に関する民間推定者は、次元性の呪いに苦しむ。 本稿では,サンプルの複雑さが次元依存性を改善したアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-11-01T17:59:53Z)
• Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
  我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。 我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
  論文  参考訳（メタデータ） (2024-06-18T08:54:04Z)
• The Sample Complexity of Simple Binary Hypothesis Testing [7.127829790714167]
  単純な二項仮説テストのサンプルの複雑さは、いずれの設定でも$p$と$q$の2つの分布を区別するのに必要となる最小のi.d.サンプルである。 i) all $0 le alpha, beta le 1/8$ in the pre-free set, and (ii) all $delta le pi/4$ in the Bayesian set。
  論文  参考訳（メタデータ） (2024-03-25T17:42:32Z)
• Tight Bounds on the Hardness of Learning Simple Nonparametric Mixtures [9.053430799456587]
  有限混合系における非パラメトリック分布の学習問題について検討する。 このようなモデルにおける成分分布を学習するために、サンプルの複雑さに厳密な境界を定めている。
  論文  参考訳（メタデータ） (2022-03-28T23:53:48Z)
• The Sample Complexity of Robust Covariance Testing [56.98280399449707]
  i. i. d. 形式 $Z = (1-epsilon) X + epsilon B$ の分布からのサンプル。ここで $X$ はゼロ平均で未知の共分散である Gaussian $mathcalN(0, Sigma)$ である。 汚染がない場合、事前の研究は、$O(d)$サンプルを使用するこの仮説テストタスクの単純なテスターを与えた。 サンプル複雑性の上限が $omega(d2)$ for $epsilon$ an arbitrarily small constant and $gamma であることを証明します。
  論文  参考訳（メタデータ） (2020-12-31T18:24:41Z)
• 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)

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

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