論文の概要: A Note on Non-Negative $L_1$-Approximating Polynomials

• arxiv url: http://arxiv.org/abs/2605.08072v1
• Date: Fri, 08 May 2026 17:55:39 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-11 19:43:39.258607
• Title: A Note on Non-Negative $L_1$-Approximating Polynomials
• Title（参考訳）: 非負の$L_1$-近似多項式についての一考察
• Authors: Jane H. Lee, Anay Mehrotra, Manolis Zampetakis,
• Abstract要約: ガウス分布に関して,textitnon- negative $L$-approximationsの存在について検討する。 これらの非負の近似は、最近、正のみの例からスムーズな学習に使われていることを発見した。
• 参考スコア（独自算出の注目度）: 10.871533496245716
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: $L_1$-Approximating polynomials, i.e., polynomials that approximate indicator functions in $L_1$-norm under certain distributions, are widely used in computational learning theory. We study the existence of \textit{non-negative} $L_1$-approximating polynomials with respect to Gaussian distributions. This is a stronger requirement than $L_1$-approximation but weaker than sandwiching polynomials (which themselves have many applications). These non-negative approximating polynomials have recently found uses in smoothed learning from positive-only examples. In this short note, we prove that every class of sets with Gaussian surface area (GSA) at most $Γ$ under the standard Gaussian admits degree-$k$ non-negative polynomials that $\eps$-approximate its indicator functions in $L_1$-norm, for $k=\tilde{O}(Γ^2/\varepsilon^2)$. Equivalently, finite GSA implies $L_1$-approximation with the stronger pointwise guarantee that the approximating polynomial has range contained in $[0,\infty)$. Up to a constant-factor, this matches the degree of the best currently known Gaussian $L_1$-approximation degree bound without the non-negativity constraint.
• Abstract（参考訳）: L_1$-近似多項式(英: $L_1$- Approximating polynomial)とは、計算学習理論において広く用いられる多項式である。 ガウス分布に関して, {textit{non- negative} $L_1$-approximating polynomials の存在について検討する。 これは$L_1$-approximationよりも強い要件であるが、サンドイッチ多項式よりも弱い(多くの応用がある)。 これらの非負近似多項式は、最近、正のみの例から滑らかな学習に使われている。 ここでは、ガウス曲面面積 (GSA) を持つ集合のクラスが、標準ガウス多項式の下では、次数-$k$非負多項式(英語版)($\eps$-approximate its indicator function in $L_1$-norm, for $k=\tilde{O}(a^2/\varepsilon^2)$)を許容する。 同様に、有限 GSA は$L_1$-近似を意味し、近似多項式が$[0,\infty)$に含まれることをより強い点的に保証する。 定数因子まで、これは非負性制約なしで有界なガウスの$L_1$-近似次数の次数と一致する。

関連論文リスト

• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。 どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
  論文  参考訳（メタデータ） (2026-03-19T15:53:41Z)
• Agnostic learning in (almost) optimal time via Gaussian surface area [2.797422854005701]
  Klivans, Klivans (2008) は、$d = O(2 / varepsilon4)$ suffices が $varepsilon$-approximation を達成することを示している。 ダイアコニコラスによる下界に照らして、次数$d = tilde O (2 / varepsilon2)$が十分であることを示す。
  論文  参考訳（メタデータ） (2026-03-06T08:22:59Z)
• Robust Learning of Multi-index Models via Iterative Subspace Approximation [36.138661719725626]
  ガウス分布下でラベルノイズを伴うマルチインデックスモデル(MIM)の学習課題について検討する。 一定の正則性特性を満たす有限範囲の良好なMIMに着目する。 ランダムな分類ノイズが存在する場合、我々のアルゴリズムの複雑さは1/epsilon$と不可知的にスケールする。
  論文  参考訳（メタデータ） (2025-02-13T17:37:42Z)
• Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit [75.4661041626338]
  単一インデックス対象関数 $f_*(boldsymbolx) = textstylesigma_*left(langleboldsymbolx,boldsymbolthetarangleright)$ の勾配勾配勾配学習問題について検討する。 SGDに基づくアルゴリズムにより最適化された2層ニューラルネットワークは、情報指数に支配されない複雑さで$f_*$を学習する。
  論文  参考訳（メタデータ） (2024-06-03T17:56:58Z)
• Dimension-free discretizations of the uniform norm by small product sets [45.85600902330814]
  ベルンシュタインの古典的不等式は、単位円上の最高ノルムの$f$と、その最高ノルムの$K$-階根のサンプリング集合上の最高ノルムと比較する。 次元自由離散化は、濃度が$deg(f)$とは独立なサンプリング集合で可能であり、代わりに$f$の最大個人次数によって支配されることを示す。
  論文  参考訳（メタデータ） (2023-10-11T22:46:09Z)
• 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)
• TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。 本稿では,この数値をほぼ最適に推定する手法を提案する。
  論文  参考訳（メタデータ） (2022-02-15T03:49:28Z)
• 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)
• Learning sums of powers of low-degree polynomials in the non-degenerate case [2.6109033135086777]
  我々は、ある非退化条件が成立すれば、同じモデルに対する下界から算術回路モデルの学習アルゴリズムを与える。 本アルゴリズムは,同じモデルに対する下界から算術回路モデルの学習アルゴリズムを得るためのスキームに基づいている。
  論文  参考訳（メタデータ） (2020-04-15T06:18:41Z)

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

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