論文の概要: Sample Complexity of Agnostic Multiclass Classification: Natarajan Dimension Strikes Back

• arxiv url: http://arxiv.org/abs/2511.12659v1
• Date: Sun, 16 Nov 2025 15:47:47 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-18 14:36:24.430587
• Title: Sample Complexity of Agnostic Multiclass Classification: Natarajan Dimension Strikes Back
• Title（参考訳）: アグノースティック・マルチクラス分類のサンプル複雑さ:ナタラジャン次元が逆転する
• Authors: Alon Cohen, Liad Erez, Steve Hanneke, Tomer Koren, Yishay Mansour, Shay Moran, Qian Zhang,
• Abstract要約: マルチクラスPACサンプルの複雑さは2つの異なる次元に支配されていることを示す。 バイナリ分類やオンライン分類とは異なり、マルチクラス学習は本質的に2つの構造パラメータを含む。 ラベル空間削減を行う自己適応型乗算重み付けアルゴリズムに基づく新規なオンライン手続きである。
• 参考スコア（独自算出の注目度）: 84.81507553557556
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The fundamental theorem of statistical learning states that binary PAC learning is governed by a single parameter -- the Vapnik-Chervonenkis (VC) dimension -- which determines both learnability and sample complexity. Extending this to multiclass classification has long been challenging, since Natarajan's work in the late 80s proposing the Natarajan dimension (Nat) as a natural analogue of VC. Daniely and Shalev-Shwartz (2014) introduced the DS dimension, later shown by Brukhim et al. (2022) to characterize multiclass learnability. Brukhim et al. also showed that Nat and DS can diverge arbitrarily, suggesting that multiclass learning is governed by DS rather than Nat. We show that agnostic multiclass PAC sample complexity is in fact governed by two distinct dimensions. Specifically, we prove nearly tight agnostic sample complexity bounds that, up to log factors, take the form $\frac{DS^{1.5}}ε + \frac{Nat}{ε^2}$ where $ε$ is the excess risk. This bound is tight up to a $\sqrt{DS}$ factor in the first term, nearly matching known $Nat/ε^2$ and $DS/ε$ lower bounds. The first term reflects the DS-controlled regime, while the second shows that the Natarajan dimension still dictates asymptotic behavior for small $ε$. Thus, unlike binary or online classification -- where a single dimension (VC or Littlestone) controls both phenomena -- multiclass learning inherently involves two structural parameters. Our technical approach departs from traditional agnostic learning methods based on uniform convergence or reductions to realizable cases. A key ingredient is a novel online procedure based on a self-adaptive multiplicative-weights algorithm performing a label-space reduction, which may be of independent interest.
• Abstract（参考訳）: 統計学習の基本的な定理は、バイナリPAC学習は単一のパラメータ(Vapnik-Chervonenkis(VC)次元)で制御され、学習可能性とサンプルの複雑さの両方を決定する。 ナタラジャンの80年代後半の研究は、ナタラジャン次元(Nat)をVCの自然な類似体として提唱した。 Daniely と Shalev-Shwartz (2014) はDS次元を導入し、後に Brukhim et al (2022) によって示され、多クラス学習性の特徴付けを行った。 Brukhimらはまた、NatとDSが任意に分岐できることを示し、マルチクラス学習はNatではなくDSによって管理されていることを示唆している。 本研究は, Agnostic Multiclass PAC sample complexity が2つの異なる次元に支配されていることを示す。 具体的には、ログ因子に限り、$\frac{DS^{1.5}}ε + \frac{Nat}{ε^2}$とすると、ε$は余剰リスクである。 この境界は、最初の項で$\sqrt{DS}$因子に強くなり、既知の$Nat/ε^2$と$DS/ε$の下界にほぼ一致する。 第1項はDS制御体制を反映し、第2項はナタラジャン次元が依然として小さな$ε$の漸近挙動を定めていることを示している。 したがって、単一の次元(VCまたはリトルストーン)が両方の現象を制御するバイナリやオンライン分類とは異なり、マルチクラス学習は本質的に2つの構造パラメータを含む。 我々の技術的アプローチは、一様収束や縮小に基づく従来の不可知学習法から逸脱し、実現可能なケースへと移行する。 鍵となる要素は、ラベル空間還元を行う自己適応型乗算重み付けアルゴリズムに基づく新しいオンライン手続きであり、これは独立した関心を持つ可能性がある。

関連論文リスト

• Learning Intersections of Two Margin Halfspaces under Factorizable Distributions [56.51474048985742]
  ハーフスペースの交叉学習は計算学習理論における中心的な問題である。 たった2つのハーフスペースであっても、学習が時間内に可能かどうかという大きな疑問が残る。 本稿ではCSQ硬度障壁を確実に回避する新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-11-13T00:28:24Z)
• On Reductions and Representations of Learning Problems in Euclidean Spaces [15.07787640047213]
  多くの実用的な予測アルゴリズムはユークリッド空間における入力を表現し、離散的な0/1分類損失を真の自明な代理損失に置き換える。 我々は古典的トポロジカルアプローチと凸性を考慮したボルスク・ウラム理論の一般化を開発する。 また、ランダム性を利用して、より小さな次元で表現できる自然な分類タスクも提示する。
  論文  参考訳（メタデータ） (2024-11-16T12:09:37Z)
• Is Transductive Learning Equivalent to PAC Learning? [0.9012198585960443]
  PACモデルとトランスダクティブモデルは、本質的には非依存のバイナリ分類に等価であることを示す。 我々は,2番目の結果が2進分類を超えて拡張可能かどうかという興味深い疑問を残して,トランスダクティブモデルとPACモデルがより広範に等価であることを示す。
  論文  参考訳（メタデータ） (2024-05-08T16:26:49Z)
• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。 本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
  論文  参考訳（メタデータ） (2024-04-29T15:04:07Z)
• When is Agnostic Reinforcement Learning Statistically Tractable? [76.1408672715773]
  エンフスパンニング容量と呼ばれる新しい複雑性測度は、設定された$Pi$にのみ依存し、MDPダイナミクスとは独立である。 我々は、学習するためにスーパーポリノミカルな数のサンプルを必要とする制限付きスパンリング能力を持つポリシークラス$Pi$が存在することを示した。 これにより、生成的アクセスとオンラインアクセスモデルの間の学習可能性の驚くほどの分離が明らかになる。
  論文  参考訳（メタデータ） (2023-10-09T19:40:54Z)
• Lower Bounds for Learning in Revealing POMDPs [88.23337313766355]
  本稿では, 難易度の高い環境下での強化学習(RL)の基本的限界について検討する。 Emphmulti-steping POMDPs に対して、潜伏状態空間依存はサンプル複雑性において少なくとも$Omega(S1.5)$であることを示す。
  論文  参考訳（メタデータ） (2023-02-02T18:59:30Z)
• A Characterization of List Learnability [15.368858716555888]
  我々は、$k$の予測リストを出力することを目標とするPAC学習について検討する。 最近のマルチクラス学習可能性の特徴を一般化すると、仮説クラスが$k$-list学習可能であることと、$k$-DS次元が有限であることは同値である。
  論文  参考訳（メタデータ） (2022-11-07T21:28:05Z)
• A Characterization of Multiclass Learnability [18.38631912121182]
  DS次元はDanielyとShalev-Shwartz 2014によって定義された次元である。 リスト学習設定では、与えられた未知の入力に対して単一の結果を予測する代わりに、予測の短いメニューを提供することが目標である。 2つ目の主な成果は、多クラス学習の可能性を特徴づける中心的な候補であるナタラジャン次元に関するものである。
  論文  参考訳（メタデータ） (2022-03-03T07:41:54Z)

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

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