論文の概要: Unlabelled Sample Compression Schemes for Intersection-Closed Classes
and Extremal Classes
- arxiv url: http://arxiv.org/abs/2210.05455v1
- Date: Tue, 11 Oct 2022 13:54:41 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-12 17:39:54.327204
- Title: Unlabelled Sample Compression Schemes for Intersection-Closed Classes
and Extremal Classes
- Title(参考訳): 交叉閉クラスと極値クラスに対するラベルなしサンプル圧縮スキーム
- Authors: J. Hyam Rubinstein and Benjamin I. P. Rubinstein
- Abstract要約: 私たちは、VC次元のすべてのクラスが$O(d)$の非競合圧縮スキームを許容していることを示します。
また、VC次元が$d$のすべての交叉閉クラスは、少なくとも$11d$の圧縮スキームを許容することを証明している。
- 参考スコア(独自算出の注目度): 16.684376456880642
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The sample compressibility of concept classes plays an important role in
learning theory, as a sufficient condition for PAC learnability, and more
recently as an avenue for robust generalisation in adaptive data analysis.
Whether compression schemes of size $O(d)$ must necessarily exist for all
classes of VC dimension $d$ is unknown, but conjectured to be true by Warmuth.
Recently Chalopin, Chepoi, Moran, and Warmuth (2018) gave a beautiful
unlabelled sample compression scheme of size VC dimension for all maximum
classes: classes that meet the Sauer-Shelah-Perles Lemma with equality. They
also offered a counterexample to compression schemes based on a promising
approach known as corner peeling. In this paper we simplify and extend their
proof technique to deal with so-called extremal classes of VC dimension $d$
which contain maximum classes of VC dimension $d-1$. A criterion is given which
would imply that all extremal classes admit unlabelled compression schemes of
size $d$. We also prove that all intersection-closed classes with VC dimension
$d$ admit unlabelled compression schemes of size at most $11d$.
- Abstract(参考訳): 概念クラスのサンプル圧縮性は、PAC学習可能性の十分な条件として、そして最近では適応データ解析における堅牢な一般化の道として、学習理論において重要な役割を果たす。
サイズ$O(d)$の圧縮スキームが、VC次元$d$のすべてのクラスに必ず存在するかどうかは不明だが、Warmuthによって推測される。
最近、chalopin, chepoi, moran, and warmuth (2018) は、全ての最大クラスのvc次元の大きさのラベルなしのサンプル圧縮スキームを美しいものにした: sauer-shelah-perles lemma に等しく一致するクラス。
彼らはまた、コーナー剥離と呼ばれる有望なアプローチに基づく圧縮スキームに対する反例を提供した。
本稿では,VC次元が$d-1$の最大クラスを含むいわゆるVC次元が$d$の極限クラスを扱うために,それらの証明手法を簡素化し拡張する。
条件は、すべての極端クラスが$d$の非ラベリング圧縮スキームを許容することを意味する。
また、VC次元が$d$のすべての交叉閉クラスは、少なくとも$11d$の圧縮スキームを許容する。
関連論文リスト
- Multiclass Learnability Does Not Imply Sample Compression [5.257719744958368]
仮説クラスはサンプル圧縮スキームを認め、もしクラスから仮説によってラベル付けされた全てのサンプルに対して、小さなサブサンプルのみを保持することができる。
サンプル圧縮に関する類似文は、多クラス仮説クラスには当てはまらないことを示す。
論文 参考訳(メタデータ) (2023-08-12T00:26:08Z) - A General Framework for Sequential Decision-Making under Adaptivity
Constraints [112.79808969568253]
適応性制約(まれなポリシースイッチ)とバッチ学習(バッチ学習)という2つの制約の下で、一般的なシーケンシャルな意思決定について検討する。
稀なポリシースイッチの制約に対して、バッチ数で$widetildemathcalO(sqrtK+K/B)$ regretを達成するアルゴリズムを提供する。
バッチ学習制約に対して、バッチ数で$widetildemathcalO(sqrtK+K/B)$ regretを提供するアルゴリズムを提供する。
論文 参考訳(メタデータ) (2023-06-26T07:20:25Z) - Uniform-PAC Guarantees for Model-Based RL with Bounded Eluder Dimension [86.3584476711976]
一般関数クラスと有界エリューダを用いた非線形帯域幅とモデルベースエピソードRLのアルゴリズムを提案する。
達成された一様PACサンプルの複雑性は、最先端の後悔境界や、線形ケースに還元された場合のサンプルの複雑さを保証するという意味で厳密である。
論文 参考訳(メタデータ) (2023-05-15T05:07:45Z) - A Labelled Sample Compression Scheme of Size at Most Quadratic in the VC
Dimension [6.522952386973185]
本稿では,任意の有限概念クラスに対して,サイズ$O(VCD2)$の固有かつ安定なラベル付きサンプル圧縮スキームを構築する。
論文 参考訳(メタデータ) (2022-12-24T01:56:02Z) - Algebraic Aspects of Boundaries in the Kitaev Quantum Double Model [77.34726150561087]
我々は、Ksubseteq G$ の部分群に基づく境界の体系的な扱いを、バルクの Kokuev 量子倍 D(G)$ モデルで提供する。
境界サイトは$*$-subalgebra $Xisubseteq D(G)$の表現であり、その構造を強い$*$-準ホップ代数として説明する。
治療の応用として、水平方向の$K=G$と垂直方向の$K=e$に基づく境界付きパッチを調査し、量子コンピュータでどのように使用できるかを示す。
論文 参考訳(メタデータ) (2022-08-12T15:05:07Z) - Optimally compressing VC classes [0.0]
Littlestone と Warmuth の予想を解くと、VC-dimension $d$ の任意の概念クラスは、サンプル圧縮スキームが$d$ であることを示す。
論文 参考訳(メタデータ) (2022-01-11T18:56:08Z) - Eluder Dimension and Generalized Rank [48.27338656415236]
eluder次元は$sigma$-rankよりも指数関数的に大きいことが分かる。
sigma$ が $mathrmrelu$ の活性化であるとき、 eluder 次元は $sigma$-rank よりも指数関数的に大きいことが示される。
論文 参考訳(メタデータ) (2021-04-14T16:53:13Z) - Small Covers for Near-Zero Sets of Polynomials and Learning Latent
Variable Models [56.98280399449707]
我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。
構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
論文 参考訳(メタデータ) (2020-12-14T18:14:08Z) - 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) - Proper Learning, Helly Number, and an Optimal SVM Bound [29.35254938542589]
適切な学習アルゴリズムにより最適なサンプル複雑性を達成できるクラスを特徴付ける。
双対ヘリー数が有界であることと、$epsilon$ と $delta$ に適切な合同依存が存在することを示せる。
論文 参考訳(メタデータ) (2020-05-24T18:11:57Z) - Agnostic Sample Compression Schemes for Regression [30.539063844697772]
他のすべての$ell_p$損失に対して、$pin (1,infty)$に対して、有界サイズの正確な圧縮スキームは存在しないことを示す。
$ell$ロスの場合、すべての関数クラスは、脂肪散乱次元における大きさの近似的な圧縮スキームを許容するだろうか?
論文 参考訳(メタデータ) (2018-10-03T11:46:59Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。