論文の概要: Dual VC Dimension Obstructs Sample Compression by Embeddings
- arxiv url: http://arxiv.org/abs/2405.17120v1
- Date: Mon, 27 May 2024 12:38:25 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-28 15:22:54.667291
- Title: Dual VC Dimension Obstructs Sample Compression by Embeddings
- Title（参考訳）: 二重VC次元は埋め込みによるサンプル圧縮を妨害する
- Authors: Zachary Chase, Bogdan Chornomaz, Steve Hanneke, Shay Moran, Amir Yehudayoff,
- Abstract要約: 本研究は、特に極端クラスに焦点を当てた、良好なVCクラスに任意のVCクラスを組み込むことについて研究する。
すべての$d$に対して、$d$の指数よりも小さい任意の極端なVC次元のクラスに組み込むことができないVC次元の$d$を持つクラスが存在することを証明している。
この結果は学習理論において重要な意味を持ち、長期にわたるサンプル圧縮予想に対処するための最も広範囲に研究されたアプローチの1つの基本的限界を明らかにする。
- 参考スコア（独自算出の注目度）: 25.63430474763066
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: This work studies embedding of arbitrary VC classes in well-behaved VC classes, focusing particularly on extremal classes. Our main result expresses an impossibility: such embeddings necessarily require a significant increase in dimension. In particular, we prove that for every $d$ there is a class with VC dimension $d$ that cannot be embedded in any extremal class of VC dimension smaller than exponential in $d$. In addition to its independent interest, this result has an important implication in learning theory, as it reveals a fundamental limitation of one of the most extensively studied approaches to tackling the long-standing sample compression conjecture. Concretely, the approach proposed by Floyd and Warmuth entails embedding any given VC class into an extremal class of a comparable dimension, and then applying an optimal sample compression scheme for extremal classes. However, our results imply that this strategy would in some cases result in a sample compression scheme at least exponentially larger than what is predicted by the sample compression conjecture. The above implications follow from a general result we prove: any extremal class with VC dimension $d$ has dual VC dimension at most $2d+1$. This bound is exponentially smaller than the classical bound $2^{d+1}-1$ of Assouad, which applies to general concept classes (and is known to be unimprovable for some classes). We in fact prove a stronger result, establishing that $2d+1$ upper bounds the dual Radon number of extremal classes. This theorem represents an abstraction of the classical Radon theorem for convex sets, extending its applicability to a wider combinatorial framework, without relying on the specifics of Euclidean convexity. The proof utilizes the topological method and is primarily based on variants of the Topological Radon Theorem.
- Abstract（参考訳）: 本研究は、特に極端クラスに焦点を当てた、良好なVCクラスに任意のVCクラスを組み込むことについて研究する。
このような埋め込みは必然的に次元を大きく増やす必要がある。
特に、すべての$d$に対して、$d$の指数よりも小さい任意の極端なVC次元のクラスに組み込むことができないVC次元の$d$を持つクラスが存在することを証明している。
独立性に加えて、この結果は学習理論に重要な意味を持ち、長年にわたって行われたサンプル圧縮予想に対処する最も広範囲に研究されたアプローチの1つの基本的限界が明らかになる。
具体的には、Floyd と Warmuth が提案したアプローチは、任意のVCクラスを同じ次元の極端クラスに埋め込み、次に極端クラスに対して最適なサンプル圧縮スキームを適用する。
しかし,本研究の結果から,この手法がサンプル圧縮予測よりも少なくとも指数関数的に大きい結果をもたらす可能性が示唆された。
VC次元が$d$の任意の極値類は、二元VC次元が少なくとも2d+1$である。
この境界は古典的有界なアスードの 2^{d+1}-1$ よりも指数関数的に小さく、一般概念クラスに適用できる(いくつかのクラスでは不可能であることが知られている)。
実際、より強い結果が証明され、2d+1$上界が極値クラスの双対ラドン数であることが証明される。
この定理は、凸集合に対する古典的ラドンの定理の抽象化を表し、ユークリッド凸性の特異性に頼ることなく、より広い組合せの枠組みにその適用性を拡張する。
この証明はトポロジカルな方法を利用しており、主にトポロジカルなラドン理論の変種に基づいている。
関連論文リスト
- On Reductions and Representations of Learning Problems in Euclidean Spaces [15.07787640047213]
多くの実用的な予測アルゴリズムはユークリッド空間における入力を表現し、離散的な0/1分類損失を真の自明な代理損失に置き換える。
我々は古典的トポロジカルアプローチと凸性を考慮したボルスク・ウラム理論の一般化を開発する。
また、ランダム性を利用して、より小さな次元で表現できる自然な分類タスクも提示する。
論文 参考訳（メタデータ） (2024-11-16T12:09:37Z) - Multiclass Learnability Does Not Imply Sample Compression [5.257719744958368]
仮説クラスはサンプル圧縮スキームを認め、もしクラスから仮説によってラベル付けされた全てのサンプルに対して、小さなサブサンプルのみを保持することができる。
サンプル圧縮に関する類似文は、多クラス仮説クラスには当てはまらないことを示す。
論文 参考訳（メタデータ） (2023-08-12T00:26:08Z) - Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。
我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
論文 参考訳（メタデータ） (2023-02-03T03:19:14Z) - A Labelled Sample Compression Scheme of Size at Most Quadratic in the VC
Dimension [6.522952386973185]
本稿では,任意の有限概念クラスに対して,サイズ$O(VCD2)$の固有かつ安定なラベル付きサンプル圧縮スキームを構築する。
論文 参考訳（メタデータ） (2022-12-24T01:56:02Z) - Differentially-Private Bayes Consistency [70.92545332158217]
差分プライバシー(DP)を満たすベイズ一貫した学習ルールを構築する。
ほぼ最適なサンプル複雑性を持つ半教師付き環境で,任意のVCクラスをプライベートに学習できることを実証する。
論文 参考訳（メタデータ） (2022-12-08T11:57:30Z) - Unlabelled Sample Compression Schemes for Intersection-Closed Classes
and Extremal Classes [16.684376456880642]
私たちは、VC次元のすべてのクラスが$O(d)$の非競合圧縮スキームを許容していることを示します。
また、VC次元が$d$のすべての交叉閉クラスは、少なくとも$11d$の圧縮スキームを許容することを証明している。
論文 参考訳（メタデータ） (2022-10-11T13:54:41Z) - Max-Margin Works while Large Margin Fails: Generalization without
Uniform Convergence [55.26547500184405]
既存のツールでは、テストの損失がトレーニングの損失に近いことを保証し、候補モデルのクラスを均一に制御するエム統一コンバージェンス(UC)に依存している。
Nagarajan と Kolter は、ある単純な線形および神経ネットワークの設定において、任意の一様収束境界は空であり、UC が失敗する環境での一般化の証明方法に関する疑問を解き放つことを示している。
我々は、ある信号対雑音のしきい値を超えると、これらの2つの設定でほぼテスト損失が得られないことを示す新しいタイプのマージン境界を証明した。
論文 参考訳（メタデータ） (2022-06-16T02:46:26Z) - First-Order Regret in Reinforcement Learning with Linear Function
Approximation: A Robust Estimation Approach [57.570201404222935]
我々は,大規模状態空間を用いた強化学習において,$mathcalO(sqrtV_1star K)$として,後悔のスケーリングが得られることを示す。
この結果を得るためには,少なくとも2乗推定に基づく既存手法は不十分であることを示す。
論文 参考訳（メタデータ） (2021-12-07T00:29:57Z) - 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) - Learning Halfspaces with Tsybakov Noise [50.659479930171585]
テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。
真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
論文 参考訳（メタデータ） (2020-06-11T14:25:02Z) - Proper Learning, Helly Number, and an Optimal SVM Bound [29.35254938542589]
適切な学習アルゴリズムにより最適なサンプル複雑性を達成できるクラスを特徴付ける。
双対ヘリー数が有界であることと、$epsilon$ と $delta$ に適切な合同依存が存在することを示せる。
論文 参考訳（メタデータ） (2020-05-24T18:11:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。