k 進アルファベット上の最適なソーヤーの補題

arXiv cs.LG / 2026/4/15

📰 ニュースIdeas & Deep AnalysisModels & Research

共有:

要点

本論文は、k 進アルファベット上での多クラス分類およびリスト予測に対して、鋭いソーヤー型不等式を証明し、特に k>2 の場合に既知となっていた劣った（非最適な）境界を扱います。
Natarajan 次元に依存するのではなく、Daniely–Shalev-Shwartz（DS）次元と、そのリスト版 DS 拡張を用いて結果を定式化します。これにより、多クラスおよびリストの PAC 学習可能性をより適切に特徴付けます。
新しい境界は、アルファベットサイズ k、リストサイズ ℓ、次元の値のすべてに対してタイトです。Natarajan に基づく境界に見られた ℓ に対する指数的な依存を、最適な多項式依存に置き換え、さらに k への依存も改善します。
証明は多項式法を用い、DS 設定では古典的な VC の場合と異なり、純粋に組合せ論的な証明は現時点では知られていないことを指摘しています。
応用として、本研究はリスト PAC 学習に対する改良されたサンプル複雑度および一様収束の境界を導出し、STOC 2023、COLT 2024、NeurIPS 2024 での最近の結果をさらに鋭くします。

要旨: Sauer-Shelah-Perlesの補題は、組合せ論および学習理論の礎であり、Vapnik-Chervonenkis（VC）次元の観点から二値仮説クラスの大きさを上界付けします。 $k$ -値アルファベット上の関数クラス、すなわち多クラス設定では、Natarajan次元が長らくVC次元の類似物として用いられてきましたが、対応するSauer型の境界は、 $k>2$ のアルファベットサイズに対しては劣っています。
本研究では、多クラスおよびリスト予測に対する鋭いSauer不等式を確立します。我々の境界は Daniely--Shalev-Shwartz（DS）次元により表現され、さらに一般には、その拡張である list-DS 次元、すなわち多クラスおよびリストのPAC学習可能性を特徴づける組合せパラメータにより表されます。この境界は、あらゆるアルファベットサイズ $k$ 、リストサイズ $l$ 、および次元値に対して鋭く、Natarajanに基づく境界における $l$ に対する指数的な依存を、最適な多項式的な依存に置き換えるとともに、 $k$ に対する依存も改善します。我々の証明は多項式法を用います。VCの場合には、いくつかの直接的な組合せ論的証明が知られているのに対し、DS設定において純粋に組合せ論的な証明は存在することを我々は把握していません。これは、将来の研究のいくつかの方向性を動機づけるものであり、本論文で議論します。
結果として、リストPAC学習とリスト予測子の一様収束に関する、改良されたサンプル複雑性の上界を得ます。これにより、Charikarら~(STOC~2023)、Hannekeら~(COLT~2024)、およびBrukhimら~(NeurIPS~2024) の最近の結果を鋭くします。