論文の概要: Sample Compression Scheme Reductions
- arxiv url: http://arxiv.org/abs/2410.13012v1
- Date: Wed, 16 Oct 2024 20:14:02 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-10-18 13:21:45.519508
- Title: Sample Compression Scheme Reductions
- Title（参考訳）: サンプル圧縮方式の削減
- Authors: Idan Attias, Steve Hanneke, Arvind Ramaswami,
- Abstract要約: 本稿では,多クラス分類,回帰,対向的頑健な学習環境におけるサンプル圧縮方式の新たな削減について述べる。
我々は、逆向きに頑健な学習のための同様の結果を確立し、また、頑健に学習できるが、境界サイズの圧縮スキームを持たない概念クラスの例を示す。
- 参考スコア（独自算出の注目度）: 17.389446817000945
- License:
- Abstract: We present novel reductions from sample compression schemes in multiclass classification, regression, and adversarially robust learning settings to binary sample compression schemes. Assuming we have a compression scheme for binary classes of size $f(d_\mathrm{VC})$, where $d_\mathrm{VC}$ is the VC dimension, then we have the following results: (1) If the binary compression scheme is a majority-vote or a stable compression scheme, then there exists a multiclass compression scheme of size $O(f(d_\mathrm{G}))$, where $d_\mathrm{G}$ is the graph dimension. Moreover, for general binary compression schemes, we obtain a compression of size $O(f(d_\mathrm{G})\log|Y|)$, where $Y$ is the label space. (2) If the binary compression scheme is a majority-vote or a stable compression scheme, then there exists an $\epsilon$-approximate compression scheme for regression over $[0,1]$-valued functions of size $O(f(d_\mathrm{P}))$, where $d_\mathrm{P}$ is the pseudo-dimension. For general binary compression schemes, we obtain a compression of size $O(f(d_\mathrm{P})\log(1/\epsilon))$. These results would have significant implications if the sample compression conjecture, which posits that any binary concept class with a finite VC dimension admits a binary compression scheme of size $O(d_\mathrm{VC})$, is resolved (Littlestone and Warmuth, 1986; Floyd and Warmuth, 1995; Warmuth, 2003). Our results would then extend the proof of the conjecture immediately to other settings. We establish similar results for adversarially robust learning and also provide an example of a concept class that is robustly learnable but has no bounded-size compression scheme, demonstrating that learnability is not equivalent to having a compression scheme independent of the sample size, unlike in binary classification, where compression of size $2^{O(d_\mathrm{VC})}$ is attainable (Moran and Yehudayoff, 2016).
- Abstract（参考訳）: 本稿では,多クラス分類,回帰,対角的に頑健な学習設定におけるサンプル圧縮スキームから2値のサンプル圧縮スキームへの新たな削減について述べる。
サイズ $f(d_\mathrm{VC})$, $d_\mathrm{VC}$ のバイナリクラスに対する圧縮スキームがVC次元であると仮定すると、次の結果が得られる: (1) バイナリ圧縮スキームが多数投票または安定な圧縮スキームであれば、$O(f(d_\mathrm{G}))$, $d_\mathrm{G}$ のマルチクラス圧縮スキームが存在し、$d_\mathrm{G}$ はグラフ次元である。
さらに、一般のバイナリ圧縮スキームに対して、$O(f(d_\mathrm{G})\log|Y|)$の圧縮を得る。
2) 2値圧縮スキームが多数決または安定な圧縮スキームである場合、$[0,1]$値の値関数が$O(f(d_\mathrm{P}))$で、$d_\mathrm{P}$が擬次元であるような回帰のための$\epsilon$-approximate圧縮スキームが存在する。
一般のバイナリ圧縮スキームに対しては、$O(f(d_\mathrm{P})\log(1/\epsilon))$である。
これらの結果は、有限VC次元の任意のバイナリ概念クラスがサイズ$O(d_\mathrm{VC})$のバイナリ圧縮スキームを許容すると仮定するサンプル圧縮予想が解決される(Littlestone and Warmuth, 1986; Floyd and Warmuth, 1995; Warmuth, 2003)。
我々の結果は、予想の証明をすぐに他の設定に拡張する。
逆向きに頑健な学習のための同様の結果を確立し、また、頑健に学習できるが有界な圧縮スキームを持たない概念クラスの例を示し、学習容易性はサンプルサイズに依存しない圧縮スキームと等価ではないことを示した。
関連論文リスト
- Matrix Compression via Randomized Low Rank and Low Precision
Factorization [47.902465710511485]
現代の行列は数十億の要素を巻き込み、そのストレージと処理は計算資源とメモリ使用量の観点から非常に要求される。
この構造を利用して任意の行列 $mathbfA$ as $mathbfLmathbfR$ の低階分解を求めるアルゴリズムを提案する。
LlaMa-7$bの層を圧縮し,画像圧縮におけるアルゴリズムの有効性を実証的に実証した。
論文 参考訳（メタデータ） (2023-10-17T06:56:57Z) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳（メタデータ） (2023-09-25T17:54:19Z) - A Labelled Sample Compression Scheme of Size at Most Quadratic in the VC
Dimension [6.522952386973185]
本稿では,任意の有限概念クラスに対して,サイズ$O(VCD2)$の固有かつ安定なラベル付きサンプル圧縮スキームを構築する。
論文 参考訳（メタデータ） (2022-12-24T01:56:02Z) - 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 compression schemes for balls in graphs [0.049932093784950796]
機械学習におけるオープンな問題の1つは、VC次元$d$のセットファミリーが、サイズ$O(d)$のサンプル圧縮スキームを認めるかどうかである。
本稿では,グラフ内の球に対するこの問題について検討する。
任意の半径$r$の球に対して、木に2ドル、サイクルに3ドル、インターバルグラフに4ドル、サイクルに6ドル、キューブのない中央値グラフに22ドルという適切なラベル付きサンプル圧縮スキームを設計する。
論文 参考訳（メタデータ） (2022-06-27T12:39:36Z) - Optimally compressing VC classes [0.0]
Littlestone と Warmuth の予想を解くと、VC-dimension $d$ の任意の概念クラスは、サンプル圧縮スキームが$d$ であることを示す。
論文 参考訳（メタデータ） (2022-01-11T18:56:08Z) - Partition and Code: learning how to compress graphs [50.29024357495154]
まず、分割アルゴリズムがグラフを基本構造に分解し、これらを確率分布を学習する小さな辞書の要素にマッピングし、エントロピーエンコーダが表現をビットに変換する。
提案アルゴリズムは,非パラメトリックおよびパラメトリックグラフ圧縮器の異なるファミリーに対して,多種多様な実世界のネットワーク上で定量的に評価し,大幅な性能向上を実現している。
論文 参考訳（メタデータ） (2021-07-05T11:41:16Z) - Learning Scalable $\ell_\infty$-constrained Near-lossless Image
Compression via Joint Lossy Image and Residual Compression [118.89112502350177]
本稿では,$ell_infty$-constrained near-lossless image compressionを学習するための新しいフレームワークを提案する。
元の残差の学習確率モデルを定量化し、量子化残差の確率モデルを導出する。
論文 参考訳（メタデータ） (2021-03-31T11:53:36Z) - Taking a hint: How to leverage loss predictors in contextual bandits? [63.546913998407405]
我々は,損失予測の助けを借りて,文脈的包帯における学習を研究する。
最適な後悔は$mathcalO(minsqrtT, sqrtmathcalETfrac13)$である。
論文 参考訳（メタデータ） (2020-03-04T07:36:38Z) - On Biased Compression for Distributed Learning [55.89300593805943]
バイアス圧縮機が単一ノードと分散設定の両方において線形収束率をもたらすことを初めて示す。
理論的保証と実用性能を期待できる新しいバイアス圧縮機を提案する。
論文 参考訳（メタデータ） (2020-02-27T19:52:24Z) - Agnostic Sample Compression Schemes for Regression [30.539063844697772]
他のすべての$ell_p$損失に対して、$pin (1,infty)$に対して、有界サイズの正確な圧縮スキームは存在しないことを示す。
$ell$ロスの場合、すべての関数クラスは、脂肪散乱次元における大きさの近似的な圧縮スキームを許容するだろうか?
論文 参考訳（メタデータ） (2018-10-03T11:46:59Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。