論文の概要: An Optimal Sauer Lemma Over $k$-ary Alphabets

• arxiv url: http://arxiv.org/abs/2604.12952v1
• Date: Tue, 14 Apr 2026 16:50:38 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-15 19:11:32.569566
• Title: An Optimal Sauer Lemma Over $k$-ary Alphabets
• Title（参考訳）: Alphabetから$kで買収されたSauer Lemma
• Authors: Steve Hanneke, Qinglin Meng, Shay Moran, Amirreza Shaeiri,
• Abstract要約: Sauer-Shelah-Perles Lemma 境界は、アルファベットサイズが $k>2$ であることを示す。 私たちのバウンダリは、すべてのサイズ$k$、リストサイズ$ell$、次元値に対して厳格であり、Natarajanベースのバウンダリにおける$ell$に対する指数的依存を置き換えます。 古典的ケースとは対照的に、DS設定における純粋に証明を意識していない。
• 参考スコア（独自算出の注目度）: 46.089126569274676
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Sauer-Shelah-Perles Lemma is a cornerstone of combinatorics and learning theory, bounding the size of a binary hypothesis class in terms of its Vapnik-Chervonenkis (VC) dimension. For classes of functions over a $k$-ary alphabet, namely the multiclass setting, the Natarajan dimension has long served as an analogue of VC dimension, yet the corresponding Sauer-type bounds are suboptimal for alphabet sizes $k>2$. In this work, we establish a sharp Sauer inequality for multiclass and list prediction. Our bound is expressed in terms of the Daniely--Shalev-Shwartz (DS) dimension, and more generally with its extension, the list-DS dimension -- the combinatorial parameters that characterize multiclass and list PAC learnability. Our bound is tight for every alphabet size $k$, list size $\ell$, and dimension value, replacing the exponential dependence on $\ell$ in the Natarajan-based bound by the optimal polynomial dependence, and improving the dependence on $k$ as well. Our proof uses the polynomial method. In contrast to the classical VC case, where several direct combinatorial proofs are known, we are not aware of any purely combinatorial proof in the DS setting. This motivates several directions for future research, which are discussed in the paper. As consequences, we obtain improved sample complexity upper bounds for list PAC learning and for uniform convergence of list predictors, sharpening the recent results of Charikar et al.~(STOC~2023), Hanneke et al.~(COLT~2024), and Brukhim et al.~(NeurIPS~2024).
• Abstract（参考訳）: Sauer-Shelah-Perles Lemma は組合せ論と学習理論の基礎であり、Vapnik-Chervonenkis(VC)次元で二項仮説のクラスのサイズを境界にしている。 k$-aryアルファベット上の関数のクラス、すなわちマルチクラス設定では、ナタラジャン次元は長い間VC次元の類似体として機能してきたが、対応するソーア型境界は、アルファベットサイズ$k>2$に対して最適である。 本研究では,マルチクラスおよびリスト予測のためのシャープなSauer不等式を確立する。 我々の境界はDaniely--Shalev-Shwartz (DS)次元で表され、より一般的には、リスト-DS次元 -- マルチクラスを特徴付ける組合せパラメータとPAC学習可能性を示す。 我々の境界は、すべてのアルファベットサイズ$k$、リストサイズ$\ell$、次元値に対して厳密であり、最適多項式依存によってナタラジャンベース境界の$\ell$に対する指数的依存を置き換え、$k$への依存も改善する。 我々の証明は多項式法を用いる。 いくつかの直接組合せ証明が知られている古典的なVCの場合とは対照的に、DS設定における純粋組合せ証明は認識していない。 このことは今後の研究へのいくつかの方向性を動機付け、論文で論じる。 その結果、リストPAC学習とリスト予測器の一様収束のためのサンプル複雑性上限が向上し、Charikar et al ~(STOC~2023)、Hanneke et al ~(COLT~2024)、Brukhim et al ~(NeurIPS~2024)の最近の結果が向上した。

関連論文リスト

• Sample Complexity of Agnostic Multiclass Classification: Natarajan Dimension Strikes Back [84.81507553557556]
  マルチクラスPACサンプルの複雑さは2つの異なる次元に支配されていることを示す。 バイナリ分類やオンライン分類とは異なり、マルチクラス学習は本質的に2つの構造パラメータを含む。 ラベル空間削減を行う自己適応型乗算重み付けアルゴリズムに基づく新規なオンライン手続きである。
  論文  参考訳（メタデータ） (2025-11-16T15:47:47Z)
• Private List Learnability vs. Online List Learnability [26.86418374191696]
  この研究は、PACリスト学習の文脈において、差分プライバシー(DP)とオンライン学習の関連について考察する。 有限$k$-モノトーン次元は、有限$k$-リトルストーン次元とともにDP$k$-list学習可能性の別の必要条件であることを示す。
  論文  参考訳（メタデータ） (2025-06-15T14:10:46Z)
• Learning and Computation of $Φ$-Equilibria at the Frontier of Tractability [85.07238533644636]
  $Phi$-equilibriaは、オンライン学習とゲーム理論の中心にある、強力で柔軟なフレームワークだ。 効率的なオンラインアルゴリズムは、$textpoly(d, k)/epsilon2$ラウンドを使用して、平均$Phi$-regretを最大$epsilon$で生成することを示す。 また、オンライン設定において、ほぼ一致した下限を示し、その結果、$Phi$-regretの学習可能性を取得する偏差の族が初めて得られる。
  論文  参考訳（メタデータ） (2025-02-25T19:08:26Z)
• Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
  我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。 我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
  論文  参考訳（メタデータ） (2024-06-18T08:54:04Z)
• A Characterization of List Learnability [15.368858716555888]
  我々は、$k$の予測リストを出力することを目標とするPAC学習について検討する。 最近のマルチクラス学習可能性の特徴を一般化すると、仮説クラスが$k$-list学習可能であることと、$k$-DS次元が有限であることは同値である。
  論文  参考訳（メタデータ） (2022-11-07T21:28:05Z)
• Unlabelled Sample Compression Schemes for Intersection-Closed Classes and Extremal Classes [16.684376456880642]
  私たちは、VC次元のすべてのクラスが$O(d)$の非競合圧縮スキームを許容していることを示します。 また、VC次元が$d$のすべての交叉閉クラスは、少なくとも$11d$の圧縮スキームを許容することを証明している。
  論文  参考訳（メタデータ） (2022-10-11T13:54:41Z)
• Sample-efficient proper PAC learning with approximate differential privacy [51.09425023771246]
  近似微分プライバシーを持つリトルストーン次元のクラスを適切に学習するサンプル複雑性が$tilde o(d6)$であることを証明し、プライバシーパラメータと精度パラメータを無視する。 この結果は Bun et al の質問に答えます。 (FOCS 2020) サンプルの複雑さに$2O(d)$の上限で改善することによって。
  論文  参考訳（メタデータ） (2020-12-07T18:17:46Z)

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

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