A Note on Non-Negative L_1-Approximating Polynomials

arXiv:2605.08072v1 Announce Type: cross 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 extit{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 Gamma under the standard Gaussian admits degree-k non-negative polynomials that eps-approximate its indicator functions in L_1-norm, for k=ilde{O}(Gamma^2/arepsilon^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.

Source: arXiv cs.LG | 2026-05-11