mlsanityData to 7 Oct 2026

Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals

arXiv 2006.16200 ↗First posted 29 Jun 2020cs.LG cs.DS math.STcited by 57

Not on the map. Why?

Abstract (arXiv)

We study the fundamental problems of agnostically learning halfspaces and ReLUs under Gaussian marginals. In the former problem, given labeled examples (x, y) from an unknown distribution on ℝd × ± 1, whose marginal distribution on x is the standard Gaussian and the labels y can be arbitrary, the goal is to output a hypothesis with 0-1 loss OPT+ε, where OPT is the 0-1 loss of the best-fitting halfspace. In the latter problem, given labeled examples (x, y) from an unknown distribution on ℝd × ℝ, whose marginal distribution on x is the standard Gaussian and the labels y can be arbitrary, the goal is to output a hypothesis with square loss OPT+ε, where OPT is the square loss of the best-fitting ReLU. We prove Statistical Query (SQ) lower bounds of dpoly(1/ε) for both of these problems. Our SQ lower bounds provide strong evidence that current upper bounds for these tasks are essentially best possible.

Key facts. Cited by 57 papers in the map (data through 7 Oct 2026). First posted on arXiv 29 Jun 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

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

57 papers.

Sort:

  1. 2021The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginalscited by 52
  2. 2023Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces and ReLU Regression under Gaussian Marginalscited by 31
  3. 2022Testing distributional assumptions of learning algorithmscited by 30
  4. 2021Learning General Halfspaces with General Massart Noise under the Gaussian Distributioncited by 27
  5. 2022Hardness of Noise-Free Learning for Two-Hidden-Layer Neural Networkscited by 27
  6. 2022A Moment-Matching Approach to Testable Learning and a New Characterization of Rademacher Complexitycited by 27
  7. 2021Lattice-Based Methods Surpass Sum-of-Squares in Clusteringcited by 25
  8. 2021From Local Pseudorandom Generators to Hardness of Learningcited by 24
  9. 2021Agnostic Proper Learning of Halfspaces under Gaussian Marginalscited by 21
  10. 2021Efficient Algorithms for Learning from Coarse Labelscited by 21
  11. 2022Learning a Single Neuron with Adversarial Label Noise via Gradient Descentcited by 20
  12. 2023Efficient Testable Learning of Halfspaces with Adversarial Label Noisecited by 19
38 more
  1. 2021Improved Algorithms for Efficient Active Learning Halfspaces with Massart and Tsybakov noisecited by 18
  2. 2023An Efficient Tester-Learner for Halfspacescited by 18
  3. 2023Tester-Learners for Halfspaces: Universal Algorithmscited by 17
  4. 2023Agnostically Learning Single-Index Models using Omnipredictorscited by 16
  5. 2021Non-Gaussian Component Analysis via Lattice Basis Reductioncited by 14
  6. 2024SQ Lower Bounds for Non-Gaussian Component Analysis with Weaker Assumptionscited by 13
  7. 2022Active Learning for Single Neuron Models with Lipschitz Non-Linearitiescited by 12
  8. 2023Robustly Learning a Single Neuron via Sharpnesscited by 12
  9. 2021Sample-Optimal PAC Learning of Halfspaces with Malicious Noisecited by 11
  10. 2021ReLU Regression with Massart Noisecited by 10
  11. 2023Computational Complexity of Learning Neural Networks: Smoothness and Degeneracycited by 10
  12. 2022Learning (Very) Simple Generative Models Is Hardcited by 9
  13. 2024Statistical Query Lower Bounds for Learning Truncated Gaussianscited by 6
  14. 2024Learning Linear Utility Functions From Pairwise Comparison Queriescited by 6
  15. 2024Sum-of-squares lower bounds for Non-Gaussian Component Analysiscited by 6
  16. 2024Active Learning of General Halfspaces: Label Queries vs Membership Queriescited by 6
  17. 2022Learning ReLU networks to high uniform accuracy is intractablecited by 5
  18. 2024Agnostic Learning of Arbitrary ReLU Activation under Gaussian Marginalscited by 5
  19. 2022Optimal SQ Lower Bounds for Robustly Learning Discrete Product Distributions and Ising Modelscited by 4
  20. 2023Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomialscited by 4
  21. 2024Sample and Computationally Efficient Robust Learning of Gaussian Single-Index Modelscited by 4
  22. 2025Testing Noise Assumptions of Learning Algorithmscited by 4
  23. 2025Learning Neural Networks with Distribution Shift: Efficiently Certifiable Guaranteescited by 4
  24. 2021Approximate Maximum Halfspace Discrepancycited by 3
  25. 2023What Distributions are Robust to Indiscriminate Poisoning Attacks for Linear Learners?cited by 3
  26. 2024Cryptographic Hardness of Score Estimationcited by 3
  27. 2024Sample-Efficient Agnostic Boostingcited by 3
  28. 2022Agnostic Learnability of Halfspaces via Logistic Losscited by 2
  29. 2024Learning a Single Neuron Robustly to Distributional Shifts and Adversarial Label Noisecited by 2
  30. 2025Robustly Learning Monotone Single-Index Modelscited by 2
  31. 2025On the Statistical Query Complexity of Learning Semiautomata: a Random Walk Approachcited by 2
  32. 2025Learning and Testing Convex Functionscited by 2
  33. 2023Distribution-Independent Regression for Generalized Linear Models with Oblivious Corruptionscited by 1
  34. 2023Efficient Active Learning Halfspaces with Tsybakov Noise: A Non-convex Optimization Approachcited by 1
  35. 2024Reliable Learning of Halfspaces under Gaussian Marginalscited by 1
  36. 2026Statistical Query Lower Bounds for Smoothed Agnostic Learningcited by 1
  37. 2023SQ Lower Bounds for Learning Bounded Covariance GMMscited by 0
  38. 2024Efficient Testable Learning of General Halfspaces with Adversarial Label Noisecited by 0

50 most cited of 57 All 57 (JSON)