ArXiv

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

2026-05-08 · 17:55 UTC ·Jane H. Lee, Anay Mehrotra, Manolis Zampetakis ·1 min read
Authors
Jane H. Lee, Anay Mehrotra, Manolis Zampetakis
Categories
stat.ML, cs.DS, cs.LG, math.ST
arXiv
https://arxiv.org/abs/2605.08072v1
PDF
https://arxiv.org/pdf/2605.08072v1

Brief

The note proves that finite Gaussian surface area Γ implies existence of non-negative degree-k polynomials that ε-approximate indicator functions in L1 under the standard Gaussian, with k = ~O(Γ^2/ε^2). This adds a pointwise non-negativity guarantee (range [0,∞)), sits between plain L1-approximation and sandwiching polynomials, matches prior degree bounds up to constants, and targets smoothed positive-only learning. Only the abstract was available for this summary.

Why it matters

Lee, Mehrotra, and Zampetakis (arXiv 2026-05-08) prove that every class of sets with Gaussian surface area ≤ Γ admits non-negative degree-k polynomials that ε-approximate its indicator function in L1 under the standard Gaussian, with k = ~O(Γ^2/ε^2).

Key details

  • The approximants have range contained in [0,∞) (a stronger pointwise guarantee than ordinary L1-approximation but weaker than sandwiching polynomials), match the best known Gaussian L1-approximation degree up to constant factors, and are motivated by applications to smoothed learning from positive-only examples.
Source evidence

Abstract

$L1$-Approximating polynomials, i.e., polynomials that approximate indicator functions in $L1$-norm under certain distributions, are widely used in computational learning theory. We study the existence of \textit{non-negative} $L1$-approximating polynomials with respect to Gaussian distributions. This is a stronger requirement than $L1$-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 $L1$-norm, for $k=\tilde{O}(Γ^2/\varepsilon^2)$. Equivalently, finite GSA implies $L1$-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.