A Note on Non-Negative $L_1$-Approximating Polynomials

• URL: http://arxiv.org/abs/2605.08072v1
• Date: Fri, 08 May 2026 17:55:39 GMT
• Title: A Note on Non-Negative $L_1$-Approximating Polynomials
• Abstract summary: We study the existence of textitnon-negative $L$-approximations with respect to Gaussian distributions.<n>These non-negative approxingimats have recently found uses in smoothed learning from positive-only examples.
• Score: 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.

Related papers

• Tight $L_\infty$ Sample Complexity for Low-Degree and Sparse Boolean Polynomials [2.5199066832791535]
  We study the problem of learning surrogates over the Boolean hypercube.<n>We require uniform $L_infty$-error guarantees rather than the usual $L$-type guarantees.<n>Our results provide a tight proof of the sample complexity of learning optimization-safe surrogates.
  arXiv  Detail & Related papers  (2026-06-15T22:00:03Z)
• Optimal Dimension-Free Sampling for Regularized Classification [56.72526267755301]
  We prove optimal sampling bounds achieving $(1pmvarepsilon)$-relative error for a broad class of Lipschitz continuous classification loss functions.<n>This includes important functions such as logistic and sigmoid loss, hinge loss, and ReLU loss, as prominent and popular representative examples.
  arXiv  Detail & Related papers  (2026-05-22T15:05:33Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  We establish new exponential in dimension lower bounds for the Maximum Halfspace Discrepancy problem.<n>Both are fundamental problems in computational geometry and machine learning in their exact and approximate forms.
  arXiv  Detail & Related papers  (2026-03-19T15:53:41Z)
• Agnostic learning in (almost) optimal time via Gaussian surface area [2.797422854005701]
  Klivans, Klivans (2008) show that degree $d = O(2 / varepsilon4)$ suffices to achieve an $varepsilon$-approximation.<n>In light of lower bounds due to Diakonikolas, we show that degree $d = tilde O (2 / varepsilon2)$ is enough.
  arXiv  Detail & Related papers  (2026-03-06T08:22:59Z)
• Robust Learning of Multi-index Models via Iterative Subspace Approximation [36.138661719725626]
  We study the task of learning Multi-Index Models (MIMs) with label noise under the Gaussian distribution.<n>We focus on well-behaved MIMs with finite ranges that satisfy certain regularity properties.<n>We show that in the presence of random classification noise, the complexity of our algorithm scales agnosticly with $1/epsilon$.
  arXiv  Detail & Related papers  (2025-02-13T17:37:42Z)
• Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit [75.4661041626338]
  We study the problem of gradient descent learning of a single-index target function $f_*(boldsymbolx) = textstylesigma_*left(langleboldsymbolx,boldsymbolthetarangleright)$<n>We prove that a two-layer neural network optimized by an SGD-based algorithm learns $f_*$ with a complexity that is not governed by information exponents.
  arXiv  Detail & Related papers  (2024-06-03T17:56:58Z)
• Dimension-free discretizations of the uniform norm by small product sets [45.85600902330814]
  A classical inequality of Bernstein compares the supremum norm of $f$ over the unit circle to its supremum norm over the sampling set of the $K$-th roots of unity.<n>We show that dimension-free discretizations are possible with sampling sets whose cardinality is independent of $deg(f)$ and is instead governed by the maximum individual degree of $f$.
  arXiv  Detail & Related papers  (2023-10-11T22:46:09Z)
• Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials [93.59919600451487]
  "Statistical-computational gaps" occur in many statistical inference tasks. We consider a model for random order-3 decomposition where one component is slightly larger in norm than the rest. We show that tensor entries can accurately estimate the largest component when $ll n3/2$ but fail to do so when $rgg n3/2$.
  arXiv  Detail & Related papers  (2022-11-10T00:40:37Z)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  We prove that any (deterministic or randomized) algorithm which learns $mathscrF_nd$ with $L$-accuracy $varepsilon$ requires at least $Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon) satisfies the two-sided estimate $$c (1-varepsilon)2dlog
  arXiv  Detail & Related papers  (2022-03-17T23:52:08Z)
• TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  One of its most powerful and successful modalities approximates every distribution to an $ell$ distance essentially at most a constant times larger than its closest $t$-piece degree-$d_$. We provide a method that estimates this number near-optimally, hence helps approach the best possible approximation.
  arXiv  Detail & Related papers  (2022-02-15T03:49:28Z)
• Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
  We show that there exists an $epsilon$-cover for $S$ of cardinality $M = (k/epsilon)O_d(k1/d)$. Building on our structural result, we obtain significantly improved learning algorithms for several fundamental high-dimensional probabilistic models hidden variables.
  arXiv  Detail & Related papers  (2020-12-14T18:14:08Z)
• Learning sums of powers of low-degree polynomials in the non-degenerate case [2.6109033135086777]
  We give a learning algorithm for an arithmetic circuit model from a lower bound for the same model, provided certain non-degeneracy conditions hold. Our algorithm is based on a scheme for obtaining a learning algorithm for an arithmetic circuit model from a lower bound for the same model.
  arXiv  Detail & Related papers  (2020-04-15T06:18:41Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.