mlsanityData to 14 Oct 2026

The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals

arXiv 2102.04401 ↗First posted 8 Feb 2021cs.LG cs.DS math.STcited by 52

Not on the map. Why?

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.

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

16 of 51 references.

References · 16

  1. 2016Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixturescited by 115
  2. 2020Superpolynomial Lower Bounds for Learning One-Layer Neural Networks using Gradient Descentcited by 58
  3. 2020Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginalscited by 57
  4. 2015Complexity Theoretic Limitations on Learning Halfspacescited by 50
  5. 2020Statistical-Query Lower Bounds via Functional Gradientscited by 50
  6. 2020Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networkscited by 49
  7. 2017Learning Geometric Concepts with Nasty Noisecited by 46
  8. 2015Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimizationcited by 41
  9. 2016Reliably Learning the ReLU in Polynomial Timecited by 36
  10. 2020Approximation Schemes for ReLU Regressioncited by 34
  11. 2019Time/Accuracy Tradeoffs for Learning a ReLU with respect to Gaussian Marginalscited by 32
  12. 2020Non-Convex SGD Learns Halfspaces with Adversarial Label Noisecited by 30
4 more
  1. 2016A General Characterization of the Statistical Query Complexitycited by 27
  2. 2014A PTAS for Agnostically Learning Halfspacescited by 21
  3. 2014Approximate resilience, monotonicity, and the complexity of agnostic learningcited by 16
  4. 2013On the Complexity of Random Satisfiability Problems with Planted Solutionscited by 14

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 5; 2022: 6; 2023: 10; 2024: 12; 2025: 8; 2026: 11.

52 papers.

Sort:

  1. 2023Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces and ReLU Regression under Gaussian Marginalscited by 31
  2. 2022Testing distributional assumptions of learning algorithmscited by 30
  3. 2021Learning General Halfspaces with General Massart Noise under the Gaussian Distributioncited by 27
  4. 2022A Moment-Matching Approach to Testable Learning and a New Characterization of Rademacher Complexitycited by 27
  5. 2021Lattice-Based Methods Surpass Sum-of-Squares in Clusteringcited by 25
  6. 2021Agnostic Proper Learning of Halfspaces under Gaussian Marginalscited by 21
  7. 2022Learning a Single Neuron with Adversarial Label Noise via Gradient Descentcited by 20
  8. 2023Efficient Testable Learning of Halfspaces with Adversarial Label Noisecited by 19
  9. 2023An Efficient Tester-Learner for Halfspacescited by 18
  10. 2023Tester-Learners for Halfspaces: Universal Algorithmscited by 17
  11. 2022Hardness of Agnostically Learning Halfspaces from Worst-Case Lattice Problemscited by 16
  12. 2023Agnostically Learning Single-Index Models using Omnipredictorscited by 16
38 more
  1. 2021Non-Gaussian Component Analysis via Lattice Basis Reductioncited by 14
  2. 2024SQ Lower Bounds for Non-Gaussian Component Analysis with Weaker Assumptionscited by 13
  3. 2023Robustly Learning a Single Neuron via Sharpnesscited by 12
  4. 2021ReLU Regression with Massart Noisecited by 10
  5. 2024Adaptive and oblivious statistical adversaries are equivalentcited by 9
  6. 2025Robust Learning of Multi-index Models via Iterative Subspace Approximationcited by 9
  7. 2025The Power of Iterative Filtering for Supervised Learning with (Heavy) Contaminationcited by 7
  8. 2022Near-Optimal Statistical Query Lower Bounds for Agnostically Learning Intersections of Halfspaces with Gaussian Marginalscited by 6
  9. 2024Statistical Query Lower Bounds for Learning Truncated Gaussianscited by 6
  10. 2024Sum-of-squares lower bounds for Non-Gaussian Component Analysiscited by 6
  11. 2024Active Learning of General Halfspaces: Label Queries vs Membership Queriescited by 6
  12. 2024Efficient PAC Learning of Halfspaces with Constant Malicious Noise Ratecited by 5
  13. 2024Agnostic Learning of Arbitrary ReLU Activation under Gaussian Marginalscited by 5
  14. 2022Optimal SQ Lower Bounds for Robustly Learning Discrete Product Distributions and Ising Modelscited by 4
  15. 2023Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomialscited by 4
  16. 2023SQ Lower Bounds for Learning Mixtures of Linear Classifierscited by 4
  17. 2024Sample and Computationally Efficient Robust Learning of Gaussian Single-Index Modelscited by 4
  18. 2025Testing Noise Assumptions of Learning Algorithmscited by 4
  19. 2024Super Non-singular Decompositions of Polynomials and their Application to Robustly Learning Low-degree PTFscited by 3
  20. 2026Sandwiching Polynomials for Geometric Concepts with Low Intrinsic Dimensioncited by 3
  21. 2024Learning a Single Neuron Robustly to Distributional Shifts and Adversarial Label Noisecited by 2
  22. 2025Statistical Query Hardness of Multiclass Linear Classification with Random Classification Noisecited by 2
  23. 2025Robust learning of halfspaces under log-concave marginalscited by 2
  24. 2025Robustly Learning Monotone Single-Index Modelscited by 2
  25. 2025PTF Testing Lower Bounds for Non-Gaussian Component Analysiscited by 2
  26. 2026Agnostic learning in (almost) optimal time via Gaussian surface areacited by 2
  27. 2023Distribution-Independent Regression for Generalized Linear Models with Oblivious Corruptionscited by 1
  28. 2024Reliable Learning of Halfspaces under Gaussian Marginalscited by 1
  29. 2026Statistical Query Lower Bounds for Smoothed Agnostic Learningcited by 1
  30. 2026Efficient and Noise-Tolerant PAC Learning of Multiclass Linear Classifierscited by 1
  31. 2023SQ Lower Bounds for Learning Bounded Covariance GMMscited by 0
  32. 2024Efficient Testable Learning of General Halfspaces with Adversarial Label Noisecited by 0
  33. 2025Faster Algorithms for Agnostically Learning Disjunctions and their Implicationscited by 0
  34. 2026Robust Learning of a Group DRO Neuroncited by 0
  35. 2026The Quantum Learning Menagerie (A survey on Quantum learning for Classical concepts)cited by 0
  36. 2026Testable Learning of General Halfspaces under Massart Noisecited by 0
  37. 2026A Near-optimal SQ Lower Bound for Smoothed Agnostic Learning of Boolean Halfspacescited by 0
  38. 2026Proper Agnostic Learning of Functions of Halfspaces under Gaussian Marginalscited by 0

50 most cited of 52 All 52 (JSON)