mlsanityData to 7 Oct 2026

Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces and ReLU Regression under Gaussian Marginals

arXiv 2302.06512 ↗First posted 13 Feb 2023cs.LG cs.CC cs.DScited by 31

Not on the map. Why?

Abstract (arXiv)

We study the task of agnostically learning halfspaces under the Gaussian distribution. Specifically, given labeled examples (x,y) from an unknown distribution on ℝn × ± 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. We prove a near-optimal computational hardness result for this task, under the widely believed sub-exponential time hardness of the Learning with Errors (LWE) problem. Prior hardness results are either qualitatively suboptimal or apply to restricted families of algorithms. Our techniques extend to yield near-optimal lower bounds for related problems, including ReLU regression.

Key facts. Cited by 31 papers in the map (data through 7 Oct 2026). Builds on 22 of its 53 references that are in the map. First posted on arXiv 13 Feb 2023.

Builds on

22 of 53 references.

References · 22

  1. 2016Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixturescited by 114
  2. 2020Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginalscited by 57
  3. 2017Learning ReLUs via Gradient Descentcited by 54
  4. 2021The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginalscited by 52
  5. 2015Complexity Theoretic Limitations on Learning Halfspacescited by 50
  6. 2020Statistical-Query Lower Bounds via Functional Gradientscited by 50
  7. 2017Learning Geometric Concepts with Nasty Noisecited by 46
  8. 2020Agnostic Learning of a Single Neuron with Gradient Descentcited by 46
  9. 2020Continuous LWEcited by 37
  10. 2016Reliably Learning the ReLU in Polynomial Timecited by 36
  11. 2020Approximation Schemes for ReLU Regressioncited by 34
  12. 2019Time/Accuracy Tradeoffs for Learning a ReLU with respect to Gaussian Marginalscited by 32
10 more
  1. 2020Near-Optimal Statistical Query Hardness of Learning Halfspaces with Massart Noisecited by 30
  2. 2022Continuous LWE is as Hard as LWE & Applications to Learning Gaussian Mixturescited by 26
  3. 2022Cryptographic Hardness of Learning Halfspaces with Massart Noisecited by 25
  4. 2014A PTAS for Agnostically Learning Halfspacescited by 21
  5. 2021Agnostic Proper Learning of Halfspaces under Gaussian Marginalscited by 21
  6. 2022Learning a Single Neuron with Adversarial Label Noise via Gradient Descentcited by 20
  7. 2014Approximate resilience, monotonicity, and the complexity of agnostic learningcited by 16
  8. 2022Hardness of Agnostically Learning Halfspaces from Worst-Case Lattice Problemscited by 16
  9. 2022Agnostic Learning of General ReLU Activation Using Gradient Descentcited by 12
  10. 2019Slide Reduction, Revisited---Filling the Gaps in SVP Approximationcited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 6; 2024: 12; 2025: 5; 2026: 8.

31 papers.

Sort:

  1. 2023Efficient Testable Learning of Halfspaces with Adversarial Label Noisecited by 19
  2. 2023Tester-Learners for Halfspaces: Universal Algorithmscited by 17
  3. 2023Robustly Learning a Single Neuron via Sharpnesscited by 12
  4. 2023Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noisecited by 9
  5. 2025Robust Learning of Multi-index Models via Iterative Subspace Approximationcited by 8
  6. 2024Omnipredicting Single-Index Models with Multi-Index Modelscited by 7
  7. 2024Improved Hardness Results for Learning Intersections of Halfspacescited by 6
  8. 2024Active Learning of General Halfspaces: Label Queries vs Membership Queriescited by 6
  9. 2024Agnostic Learning of Arbitrary ReLU Activation under Gaussian Marginalscited by 5
  10. 2023Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomialscited by 4
  11. 2024Distribution-Specific Auditing For Subgroup Fairnesscited by 4
  12. 2024Sample and Computationally Efficient Robust Learning of Gaussian Single-Index Modelscited by 4
19 more
  1. 2025Testing Noise Assumptions of Learning Algorithmscited by 4
  2. 2024Super Non-singular Decompositions of Polynomials and their Application to Robustly Learning Low-degree PTFscited by 3
  3. 2024Cryptographic Hardness of Score Estimationcited by 3
  4. 2024Collaborative Learning with Different Labeling Functionscited by 2
  5. 2024Learning a Single Neuron Robustly to Distributional Shifts and Adversarial Label Noisecited by 2
  6. 2025Statistical Query Hardness of Multiclass Linear Classification with Random Classification Noisecited by 2
  7. 2025Robustly Learning Monotone Single-Index Modelscited by 2
  8. 2023Distribution-Independent Regression for Generalized Linear Models with Oblivious Corruptionscited by 1
  9. 2024Reliable Learning of Halfspaces under Gaussian Marginalscited by 1
  10. 2025Personalized Prediction By Learning Halfspace Reference Classes Under Well-Behaved Distributioncited by 1
  11. 2026Statistical Query Lower Bounds for Smoothed Agnostic Learningcited by 1
  12. 2026Efficient and Noise-Tolerant PAC Learning of Multiclass Linear Classifierscited by 1
  13. 2024Efficient Testable Learning of General Halfspaces with Adversarial Label Noisecited by 0
  14. 2026Robust Learning of a Group DRO Neuroncited by 0
  15. 2026Near-Optimal Cryptographic Hardness of Learning With Homogeneous Halfspaces Under Gaussian Marginalscited by 0
  16. 2026A Near-optimal SQ Lower Bound for Smoothed Agnostic Learning of Boolean Halfspacescited by 0
  17. 2026Polynomial-Time Robust Multiclass Linear Classification under Gaussian Marginalscited by 0
  18. 2026Proper Agnostic Learning of Functions of Halfspaces under Gaussian Marginalscited by 0
  19. 2026Robust Regression of General ReLUs with Queriescited by 0