論文の概要: The Optimal Sample Complexity of Multiclass and List Learning

• arxiv url: http://arxiv.org/abs/2604.24749v1
• Date: Mon, 27 Apr 2026 17:54:12 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-28 17:12:08.358124
• Title: The Optimal Sample Complexity of Multiclass and List Learning
• Title（参考訳）: マルチクラス・リスト学習における最適サンプル複雑度
• Authors: Chirag Pabbaraju,
• Abstract要約: 任意の多クラス仮説クラスの最大ハイパーグラフ密度はそのDS次元によって上界にあることを示す。 また,多クラスおよびリスト学習におけるDS次元に対するサンプルの複雑さの最適依存性についても検討する。
• 参考スコア（独自算出の注目度）: 7.0223797053352
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: While the optimal sample complexity of binary classification in terms of the VC dimension is well-established, determining the optimal sample complexity of multiclass classification has remained open. The appropriate complexity parameter for multiclass classification is the DS dimension, and despite significant efforts, a gap of $\sqrt{\text{DS}}$ has persisted between the upper and lower bounds on sample complexity. Recent work by Hanneke et al. (2026) shows a novel algebraic characterization of multiclass hypothesis classes in terms of their DS dimension. Building up on this, we show that the maximum hypergraph density of any multiclass hypothesis class is upper-bounded by its DS dimension. This proves a longstanding conjecture of Daniely and Shalev-Shwartz (2014). As a consequence, we determine the optimal dependence of the sample complexity on the DS dimension for multiclass as well as list learning.
• Abstract（参考訳）: VC次元における二項分類の最適サンプル複雑性は十分に確立されているが、多項分類の最適サンプル複雑性は未解決のままである。 多クラス分類の適切な複雑性パラメータはDS次元であり、大きな努力にもかかわらず、$\sqrt{\text{DS}}$のギャップはサンプルの複雑さの上下の境界に持続している。 Hanneke et al (2026) による最近の研究は、DS次元の観点で、多クラス仮説クラスの新しい代数的特徴を示している。 これに基づいて、任意の多クラス仮説クラスの最大ハイパーグラフ密度がDS次元によって上界であることが示される。 これはダニエルとシャレフ=シュワルツ(2014)の長年の予想を証明している。 その結果,多クラスおよびリスト学習におけるDS次元に対するサンプルの複雑さの最適依存性を決定する。

関連論文リスト

• Sample Complexity of Agnostic Multiclass Classification: Natarajan Dimension Strikes Back [84.81507553557556]
  マルチクラスPACサンプルの複雑さは2つの異なる次元に支配されていることを示す。 バイナリ分類やオンライン分類とは異なり、マルチクラス学習は本質的に2つの構造パラメータを含む。 ラベル空間削減を行う自己適応型乗算重み付けアルゴリズムに基づく新規なオンライン手続きである。
  論文  参考訳（メタデータ） (2025-11-16T15:47:47Z)
• Optimal Multi-Distribution Learning [88.3008613028333]
  マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。 本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-12-08T16:06:29Z)
• Comparative Learning: A Sample Complexity Theory for Two Hypothesis Classes [5.194264506657145]
  比較学習は、PAC学習における実現可能な設定と不可知な設定の組み合わせとして導入する。 たとえ$S$と$B$が無限のVC次元を持つとしても、比較学習の複雑さは小さい。 比較学習のサンプルの複雑さは、相互VC次元$mathsfVC(S,B)$によって特徴づけられる。
  論文  参考訳（メタデータ） (2022-11-16T18:38:24Z)
• Approximation and generalization properties of the random projection classification method [0.4604003661048266]
  ランダムな一次元特徴を閾値付けした低複素度分類器群について検討する。 特定の分類問題(例えば、大きな羅生門比を持つもの)に対して、ランダムにパラメータを選択することにより、一般化特性において潜在的に大きな利得がある。
  論文  参考訳（メタデータ） (2021-08-11T23:14:46Z)
• Bilinear Classes: A Structural Framework for Provable Generalization in RL [119.42509700822484]
  Bilinear Classesは強化学習の一般化を可能にする新しい構造フレームワークである。 このフレームワークは、サンプルの複雑さが達成可能な、ほとんどすべての既存のモデルを取り込んでいる。 我々の主な成果は、双線形クラスのためのサンプル複雑性を持つRLアルゴリズムである。
  論文  参考訳（メタデータ） (2021-03-19T16:34:20Z)

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

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