# A Note on Non-Negative L1-Approximating Polynomials

arXiv: https://arxiv.org/abs/2605.08072 · HTML: https://mlsanity.com/paper/2605.08072/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 13 references that are in the map.
- First posted on arXiv 8 May 2026.

## Builds on (most cited first, 7 of 7)

- [Testing distributional assumptions of learning algorithms](https://mlsanity.com/paper/2204.07196/) (2022)
- [A Moment-Matching Approach to Testable Learning and a New Characterization of Rademacher Complexity](https://mlsanity.com/paper/2211.13312/) (2022)
- [Testable Learning with Distribution Shift](https://mlsanity.com/paper/2311.15142/) (2023)
- [Distribution-Independent Reliable Learning](https://mlsanity.com/paper/1402.5164/) (2014)
- [Smoothed Analysis of Learning from Positive Samples](https://mlsanity.com/paper/2504.10428/) (2025)
- [Sandwiching Polynomials for Geometric Concepts with Low Intrinsic Dimension](https://mlsanity.com/paper/2602.24178/) (2026)
- [Agnostic learning in (almost) optimal time via Gaussian surface area](https://mlsanity.com/paper/2603.06027/) (2026)

## Abstract (arXiv)

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 textitnon-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 Gamma under the standard Gaussian admits degree-k non-negative polynomials that eps-approximate its indicator functions in L1-norm, for k=tildeO(Gamma2/varepsilon2). Equivalently, finite GSA implies L1-approximation with the stronger pointwise guarantee that the approximating polynomial has range contained in [0,∞). Up to a constant-factor, this matches the degree of the best currently known Gaussian L1-approximation degree bound without the non-negativity constraint.