論文の概要: An Agnostic Sample Compression Scheme for Squared Loss of Near-Linear Size in the Fat-Shattering Dimension

• arxiv url: http://arxiv.org/abs/2609.29696v1
• Date: Mon, 31 Aug 2026 05:41:34 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-28 05:09:56.112516
• Title: An Agnostic Sample Compression Scheme for Squared Loss of Near-Linear Size in the Fat-Shattering Dimension
• Title（参考訳）: ファットシェイタリング次元における近接線径の正方形損失に対する非依存的サンプル圧縮方式
• Abstract要約: 経験的二乗損失に対する非依存的なサンプル圧縮方式を提案する。 このスキームは最大$O(mathrmfat(mathcalF,c')cdotlog3(2/)$オリジナルのラベル付き例と補助ビットを格納する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We construct, for every function class $\mathcal{F}\subseteq[0,1]^{\mathcal{X}}$ and every accuracy $0<α\le 1$, an agnostic sample compression scheme for the empirical squared loss: for every finite sample $S\in(\mathcal{X}\times[0,1])^m$ with arbitrary (noisy) labels, the scheme stores at most $O(\mathrm{fat}(\mathcal{F},c'α)\cdot\log^3(2/α))$ original labeled examples and auxiliary bits, independent of the sample size $m$, and reconstructs a function $\hat f$ with $L_2(\hat f,S)\le\inf_{f\in\mathcal{F}}L_2(f,S)+α$. This resolves, in the positive, the open problem of Attias, Hanneke, Kontorovich, and Sadigurschi (ICML 2024, Section 5), which asks for an agnostic $\ell_2$ compression scheme of size $\mathrm{fat}(\mathcal{F},cα)\cdot\mathrm{polylog}(c/α)$. All previously known bounded-size constructions, agnostic and even realizable, incur a multiplicative dual fat-shattering factor, which can be exponentially larger than the primal dimension; our scheme removes the dual factor entirely, including in the realizable case. The dual factor in prior work enters solely through a sparsification step that forces uniform approximation on the sample. By targeting only a $(1-ε)$-fraction of sample points, which suffices for an average-loss guarantee over a bounded range, K'egl's boosting margin bound yields $O(\log(1/ε))$ rounds independent of $m$, and sparsification is never needed. The booster's synthetic target labels (values of a near-optimal $f^*\in\mathcal{F}$) are transmitted through quantized side-information bits attached to stored original examples, and the cross term of the squared loss forces the weak-learning scale $Θ(α)$, matching the same-scale form of the open problem.
• Abstract（参考訳）: すべての関数クラスに対して、$\mathcal{F}\subseteq[0,1]^{\mathcal{X}}$およびすべての精度$0<α\le 1$に対して、経験的二乗損失に対する非依存的なサンプル圧縮スキーム: すべての有限サンプル$S\in(\mathcal{X}\times[0,1])^m$に対して、任意の(ノイズ)ラベルを持つスキームストアは、最大$O(\mathcal{F},c'α)\cdot\log^3(2/α))$ で、サンプルサイズ$m$とは独立に、元のラベル付き例と補助ビットで、サンプルサイズ$m$$0<α\le 1$ と、サンプルサイズ$L_2(\hat,fS\inf_{f}+\inf_{F}}+α+S2+S2+α)で構成し、関数 $\hat f$$(\hatf(\hat,f,f)+\inf(+α)$を再構成する。 このことは、Attias, Hanneke, Kontorovich, and Sadigurschi (ICML 2024, Section 5) の開問題において、サイズ$\ell_2$圧縮スキームに$\mathrm{fat}(\mathcal{F},cα)\cdot\mathrm{polylog}(c/α)$を求める。 既知の有界サイズ構造はすべて、非依存的かつ実現可能であり、原始次元よりも指数関数的に大きい乗法的二重脂肪散乱因子を生じる。 先行作業における二重因子は、サンプルに一様近似を強制するスパーシフィケーションステップによってのみ入力される。 1-ε(英語版)$-fraction(英語版)のサンプル点のみを目標とし、これは有界範囲における平均余剰保証のために十分であるので、K'eglのブースティングマージン境界は$O(\log(1/ε))$ rounds of $m$とは独立であり、スパース化は不要である。 ブースターの合成目標ラベル(準最適$f^*\in\mathcal{F}$の値)は、記憶された元の例に付随する量子化された側情報ビットを介して送信され、正方形損失のクロス項は弱学習スケールの99(α)$となり、開問題の同じスケールの形式に一致する。

関連論文リスト

• Scale-Sensitive Shattering: Learnability and Evaluability at Optimal Scale [54.65053906803857]
  実数値関数クラスが一様収束と学習可能性を示す最適尺度について検討する。 本研究の主な成果は,PAC学習の基本定理のスケール敏感な一般化である。 また、定量的サンプルの複雑さと評価可能性に関するオープンな質問をいくつか取り上げる。
  論文  参考訳（メタデータ） (2026-05-13T15:41:30Z)
• Hardness Amplification for (Sparse) LPN [5.1105538244022135]
  雑音を学習するパリティ(mathsfLPN$)とそのスパース変種に対する新しい硬度増幅結果を示す。 で$mathsfLPN$を解くアルゴリズムは、"ほとんどすべてのインスタンス"で$mathsfLPN$を解くアルゴリズムに変換することができる。 同じ増幅アプローチを$mathsfLPN$ over $mathbbF_q$とSparse-$mathsfLPN$に拡張します。
  論文  参考訳（メタデータ） (2026-05-11T06:34:37Z)
• Algorithmic contiguity from low-degree conjecture and applications in correlated random graphs [0.0]
  2つの問題に対して計算硬度を示す。 我々の証明の主な要素の1つは、2つの確率測度の間の近位関係を導出することである。 このフレームワークは、異なるタスク間のリダクションを実行するための便利なツールを提供する。
  論文  参考訳（メタデータ） (2025-02-14T00:24:51Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。 本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。 また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
  論文  参考訳（メタデータ） (2023-09-25T17:54:19Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。 学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
  論文  参考訳（メタデータ） (2022-06-17T17:55:43Z)
• Tight Bounds on the Hardness of Learning Simple Nonparametric Mixtures [9.053430799456587]
  有限混合系における非パラメトリック分布の学習問題について検討する。 このようなモデルにおける成分分布を学習するために、サンプルの複雑さに厳密な境界を定めている。
  論文  参考訳（メタデータ） (2022-03-28T23:53:48Z)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
  論文  参考訳（メタデータ） (2022-03-17T23:52:08Z)
• Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals [49.60752558064027]
  ガウス境界の下では、半空間とReLUを不可知的に学習する基本的な問題について検討する。 我々の下限は、これらのタスクの現在の上限が本質的に最良のものであるという強い証拠を与える。
  論文  参考訳（メタデータ） (2020-06-29T17:10:10Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。