# Agnostic learning in (almost) optimal time via Gaussian surface area

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 30 references that are in the map.
- First posted on arXiv 6 Mar 2026.

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

- [The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals](https://mlsanity.com/paper/2102.04401/) (2021)
- [Complexity Theoretic Limitations on Learning Halfspaces](https://mlsanity.com/paper/1505.05800/) (2015)
- [Learning Geometric Concepts with Nasty Noise](https://mlsanity.com/paper/1707.01242/) (2017)
- [Non-Convex SGD Learns Halfspaces with Adversarial Label Noise](https://mlsanity.com/paper/2006.06742/) (2020)
- [A PTAS for Agnostically Learning Halfspaces](https://mlsanity.com/paper/1410.7050/) (2014)
- [Hardness of Agnostically Learning Halfspaces from Worst-Case Lattice Problems](https://mlsanity.com/paper/2207.14030/) (2022)
- [A Mysterious Connection Between Tolerant Junta Testing and Agnostically Learning Conjunctions](https://mlsanity.com/paper/2504.16065/) (2025)

## Built on by (most cited first, 2 of 2)

- [A Note on Non-Negative L1-Approximating Polynomials](https://mlsanity.com/paper/2605.08072/) (2026)
- [Proper Agnostic Learning of Functions of Halfspaces under Gaussian Marginals](https://mlsanity.com/paper/2605.27594/) (2026)

## Abstract (arXiv)

The complexity of learning a concept class under Gaussian marginals in the difficult agnostic model is closely related to its L1-approximability by low-degree polynomials. For any concept class with Gaussian surface area at most Gamma, Klivans et al. (2008) show that degree d = O(Gamma2 / varepsilon4) suffices to achieve an varepsilon-approximation. This leads to the best-known bounds on the complexity of learning a variety of concept classes. In this note, we improve their analysis by showing that degree d = tilde O (Gamma2 / varepsilon2) is enough. In light of lower bounds due to Diakonikolas et al. (2021), this yields (near) optimal bounds on the complexity of agnostically learning polynomial threshold functions in the statistical query model. Our proof relies on a direct analogue of a construction of Feldman et al. (2020), who considered L1-approximation on the Boolean hypercube.