論文の概要: Agnostic Sample Compression Schemes for Regression
- arxiv url: http://arxiv.org/abs/1810.01864v2
- Date: Sat, 3 Feb 2024 21:49:19 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-07 21:50:03.978956
- Title: Agnostic Sample Compression Schemes for Regression
- Title（参考訳）: 回帰のための非依存サンプル圧縮方式
- Authors: Idan Attias, Steve Hanneke, Aryeh Kontorovich, Menachem Sadigurschi
- Abstract要約: 他のすべての$ell_p$損失に対して、$pin (1,infty)$に対して、有界サイズの正確な圧縮スキームは存在しないことを示す。
$ell$ロスの場合、すべての関数クラスは、脂肪散乱次元における大きさの近似的な圧縮スキームを許容するだろうか?
- 参考スコア（独自算出の注目度）: 30.539063844697772
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We obtain the first positive results for bounded sample compression in the
agnostic regression setting with the $\ell_p$ loss, where $p\in [1,\infty]$. We
construct a generic approximate sample compression scheme for real-valued
function classes exhibiting exponential size in the fat-shattering dimension
but independent of the sample size. Notably, for linear regression, an
approximate compression of size linear in the dimension is constructed.
Moreover, for $\ell_1$ and $\ell_\infty$ losses, we can even exhibit an
efficient exact sample compression scheme of size linear in the dimension. We
further show that for every other $\ell_p$ loss, $p\in (1,\infty)$, there does
not exist an exact agnostic compression scheme of bounded size. This refines
and generalizes a negative result of David, Moran, and Yehudayoff for the
$\ell_2$ loss. We close by posing general open questions: for agnostic
regression with $\ell_1$ loss, does every function class admits an exact
compression scheme of size equal to its pseudo-dimension? For the $\ell_2$
loss, does every function class admit an approximate compression scheme of
polynomial size in the fat-shattering dimension? These questions generalize
Warmuth's classic sample compression conjecture for realizable-case
classification.
- Abstract（参考訳）: 我々は、$\ell_p$損失を持つ非依存回帰設定において、有界なサンプル圧縮に対する最初の正の値を得る。
ファットシャッタリング次元では指数的サイズを示すが,サンプルサイズには依存しない実数値関数クラスの汎用近似サンプル圧縮スキームを構築した。
特に線形回帰では、次元で線形な大きさの近似圧縮が構築される。
さらに、$\ell_1$ と $\ell_\infty$ の損失に対して、次元の線形の大きさの効率的な正確なサンプル圧縮スキームも示せる。
さらに、$\ell_p$ の損失、$p\in (1,\infty)$ に対して、有界サイズの正確な非依存な圧縮スキームは存在しないことを示す。
これにより、 david, moran, yehudayoff の $\ell_2$ の損失に対する負の結果が洗練され一般化される。
agnostic regression with $\ell_1$ loss に対して、すべての関数クラスは、その擬次元と同じ大きさの正確な圧縮スキームを認めますか?
$\ell_2$ の損失に対して、すべての関数クラスは、脂肪粉砕次元における多項式サイズの近似圧縮スキームを許すか?
これらの質問は、実現可能なケース分類のためのwarmuthの古典的なサンプル圧縮予想を一般化する。
関連論文リスト
- Sample Compression Scheme Reductions [17.389446817000945]
本稿では,多クラス分類,回帰,対向的頑健な学習環境におけるサンプル圧縮方式の新たな削減について述べる。
我々は、逆向きに頑健な学習のための同様の結果を確立し、また、頑健に学習できるが、境界サイズの圧縮スキームを持たない概念クラスの例を示す。
論文 参考訳（メタデータ） (2024-10-16T20:14:02Z) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳（メタデータ） (2023-09-25T17:54:19Z) - Effective Minkowski Dimension of Deep Nonparametric Regression: Function
Approximation and Statistical Theories [70.90012822736988]
ディープ非パラメトリック回帰に関する既存の理論は、入力データが低次元多様体上にある場合、ディープニューラルネットワークは本質的なデータ構造に適応できることを示した。
本稿では,$mathcalS$で表される$mathbbRd$のサブセットに入力データが集中するという緩和された仮定を導入する。
論文 参考訳（メタデータ） (2023-06-26T17:13:31Z) - Optimal Sketching Bounds for Sparse Linear Regression [116.30196615349226]
我々は、$ell_p$ノルムや広範なヒンジ様損失関数のクラスから、様々な損失関数の下で、$k$スパース線形回帰の難読スケッチを研究する。
スパース$ell$varepsレグレッションの場合、$Theta(klog(d/k)/varepsilon2)$ rowsでスケッチの上に曖昧な分布が存在し、これは定数要素に固執することを示している。
また、$O(mu2 klog(mun d/varepsilon)/varのスケッチも示します。
論文 参考訳（メタデータ） (2023-04-05T07:24:19Z) - The Geometry of Mixability [8.873449722727026]
二項および多項の場合の混合性に関する簡易な幾何学的特徴付けを提供する。
我々のアプローチは、損失関数に関するいくつかの概念を'コーディネートフリー'な方法で扱う方法を提供する。
論文 参考訳（メタデータ） (2023-02-23T10:25:38Z) - A Labelled Sample Compression Scheme of Size at Most Quadratic in the VC
Dimension [6.522952386973185]
本稿では,任意の有限概念クラスに対して,サイズ$O(VCD2)$の固有かつ安定なラベル付きサンプル圧縮スキームを構築する。
論文 参考訳（メタデータ） (2022-12-24T01:56:02Z) - Private Isotonic Regression [54.32252900997422]
部分順序集合 (poset) $mathcalX$ と任意のリプシッツ損失関数に対する等調回帰の問題を考察する。
約$mathrmwidth(mathcalX) cdot log|mathcalX| / n$, ここで$mathrmwidth(mathcalX)$はポーズの幅である。
上記の境界は本質的に最良であることを示す。
論文 参考訳（メタデータ） (2022-10-27T05:08:07Z) - 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) - 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) - On Biased Compression for Distributed Learning [55.89300593805943]
バイアス圧縮機が単一ノードと分散設定の両方において線形収束率をもたらすことを初めて示す。
理論的保証と実用性能を期待できる新しいバイアス圧縮機を提案する。
論文 参考訳（メタデータ） (2020-02-27T19:52:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。