# The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals

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

## Key facts

- Cited by 52 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 51 references that are in the map.
- First posted on arXiv 8 Feb 2021.

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

- [Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixtures](https://mlsanity.com/paper/1611.03473/) (2016)
- [Superpolynomial Lower Bounds for Learning One-Layer Neural Networks using Gradient Descent](https://mlsanity.com/paper/2006.12011/) (2020)
- [Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals](https://mlsanity.com/paper/2006.16200/) (2020)
- [Complexity Theoretic Limitations on Learning Halfspaces](https://mlsanity.com/paper/1505.05800/) (2015)
- [Statistical-Query Lower Bounds via Functional Gradients](https://mlsanity.com/paper/2006.15812/) (2020)
- [Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks](https://mlsanity.com/paper/2006.12476/) (2020)
- [Learning Geometric Concepts with Nasty Noise](https://mlsanity.com/paper/1707.01242/) (2017)
- [Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization](https://mlsanity.com/paper/1512.09170/) (2015)
- [Reliably Learning the ReLU in Polynomial Time](https://mlsanity.com/paper/1611.10258/) (2016)
- [Approximation Schemes for ReLU Regression](https://mlsanity.com/paper/2005.12844/) (2020)
- [Time/Accuracy Tradeoffs for Learning a ReLU with respect to Gaussian Marginals](https://mlsanity.com/paper/1911.01462/) (2019)
- [Non-Convex SGD Learns Halfspaces with Adversarial Label Noise](https://mlsanity.com/paper/2006.06742/) (2020)
- [A General Characterization of the Statistical Query Complexity](https://mlsanity.com/paper/1608.02198/) (2016)
- [A PTAS for Agnostically Learning Halfspaces](https://mlsanity.com/paper/1410.7050/) (2014)
- [Approximate resilience, monotonicity, and the complexity of agnostic learning](https://mlsanity.com/paper/1405.5268/) (2014)
- [On the Complexity of Random Satisfiability Problems with Planted Solutions](https://mlsanity.com/paper/1311.4821/) (2013)

## Built on by (most cited first, 30 of 52)

- [Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces and ReLU Regression under Gaussian Marginals](https://mlsanity.com/paper/2302.06512/) (2023)
- [Testing distributional assumptions of learning algorithms](https://mlsanity.com/paper/2204.07196/) (2022)
- [Learning General Halfspaces with General Massart Noise under the Gaussian Distribution](https://mlsanity.com/paper/2108.08767/) (2021)
- [A Moment-Matching Approach to Testable Learning and a New Characterization of Rademacher Complexity](https://mlsanity.com/paper/2211.13312/) (2022)
- [Lattice-Based Methods Surpass Sum-of-Squares in Clustering](https://mlsanity.com/paper/2112.03898/) (2021)
- [Agnostic Proper Learning of Halfspaces under Gaussian Marginals](https://mlsanity.com/paper/2102.05629/) (2021)
- [Learning a Single Neuron with Adversarial Label Noise via Gradient Descent](https://mlsanity.com/paper/2206.08918/) (2022)
- [Efficient Testable Learning of Halfspaces with Adversarial Label Noise](https://mlsanity.com/paper/2303.05485/) (2023)
- [An Efficient Tester-Learner for Halfspaces](https://mlsanity.com/paper/2302.14853/) (2023)
- [Tester-Learners for Halfspaces: Universal Algorithms](https://mlsanity.com/paper/2305.11765/) (2023)
- [Hardness of Agnostically Learning Halfspaces from Worst-Case Lattice Problems](https://mlsanity.com/paper/2207.14030/) (2022)
- [Agnostically Learning Single-Index Models using Omnipredictors](https://mlsanity.com/paper/2306.10615/) (2023)
- [Non-Gaussian Component Analysis via Lattice Basis Reduction](https://mlsanity.com/paper/2112.09104/) (2021)
- [SQ Lower Bounds for Non-Gaussian Component Analysis with Weaker Assumptions](https://mlsanity.com/paper/2403.04744/) (2024)
- [Robustly Learning a Single Neuron via Sharpness](https://mlsanity.com/paper/2306.07892/) (2023)
- [ReLU Regression with Massart Noise](https://mlsanity.com/paper/2109.04623/) (2021)
- [Adaptive and oblivious statistical adversaries are equivalent](https://mlsanity.com/paper/2410.13548/) (2024)
- [Robust Learning of Multi-index Models via Iterative Subspace Approximation](https://mlsanity.com/paper/2502.09525/) (2025)
- [The Power of Iterative Filtering for Supervised Learning with (Heavy) Contamination](https://mlsanity.com/paper/2505.20177/) (2025)
- [Near-Optimal Statistical Query Lower Bounds for Agnostically Learning Intersections of Halfspaces with Gaussian Marginals](https://mlsanity.com/paper/2202.05096/) (2022)
- [Statistical Query Lower Bounds for Learning Truncated Gaussians](https://mlsanity.com/paper/2403.02300/) (2024)
- [Sum-of-squares lower bounds for Non-Gaussian Component Analysis](https://mlsanity.com/paper/2410.21426/) (2024)
- [Active Learning of General Halfspaces: Label Queries vs Membership Queries](https://mlsanity.com/paper/2501.00508/) (2024)
- [Efficient PAC Learning of Halfspaces with Constant Malicious Noise Rate](https://mlsanity.com/paper/2410.01186/) (2024)
- [Agnostic Learning of Arbitrary ReLU Activation under Gaussian Marginals](https://mlsanity.com/paper/2411.14349/) (2024)
- [Optimal SQ Lower Bounds for Robustly Learning Discrete Product Distributions and Ising Models](https://mlsanity.com/paper/2206.04589/) (2022)
- [Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials](https://mlsanity.com/paper/2307.12840/) (2023)
- [SQ Lower Bounds for Learning Mixtures of Linear Classifiers](https://mlsanity.com/paper/2310.11876/) (2023)
- [Sample and Computationally Efficient Robust Learning of Gaussian Single-Index Models](https://mlsanity.com/paper/2411.05708/) (2024)
- [Testing Noise Assumptions of Learning Algorithms](https://mlsanity.com/paper/2501.09189/) (2025)

## Abstract (arXiv)

We study the problem of agnostic learning under the Gaussian distribution. We develop a method for finding hard families of examples for a wide class of problems by using LP duality. For Boolean-valued concept classes, we show that the L1-regression algorithm is essentially best possible, and therefore that the computational difficulty of agnostically learning a concept class is closely related to the polynomial degree required to approximate any function from the class in L1-norm. Using this characterization along with additional analytic tools, we obtain optimal SQ lower bounds for agnostically learning linear threshold functions and the first non-trivial SQ lower bounds for polynomial threshold functions and intersections of halfspaces. We also develop an analogous theory for agnostically learning real-valued functions, and as an application prove near-optimal SQ lower bounds for agnostically learning ReLUs and sigmoids.