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

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

## Key facts

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

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

- [Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixtures](https://mlsanity.com/paper/1611.03473/) (2016)
- [Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals](https://mlsanity.com/paper/2006.16200/) (2020)
- [Learning ReLUs via Gradient Descent](https://mlsanity.com/paper/1705.04591/) (2017)
- [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)
- [Statistical-Query Lower Bounds via Functional Gradients](https://mlsanity.com/paper/2006.15812/) (2020)
- [Learning Geometric Concepts with Nasty Noise](https://mlsanity.com/paper/1707.01242/) (2017)
- [Agnostic Learning of a Single Neuron with Gradient Descent](https://mlsanity.com/paper/2005.14426/) (2020)
- [Continuous LWE](https://mlsanity.com/paper/2005.09595/) (2020)
- [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)
- [Near-Optimal Statistical Query Hardness of Learning Halfspaces with Massart Noise](https://mlsanity.com/paper/2012.09720/) (2020)
- [Continuous LWE is as Hard as LWE & Applications to Learning Gaussian Mixtures](https://mlsanity.com/paper/2204.02550/) (2022)
- [Cryptographic Hardness of Learning Halfspaces with Massart Noise](https://mlsanity.com/paper/2207.14266/) (2022)
- [A PTAS for Agnostically Learning Halfspaces](https://mlsanity.com/paper/1410.7050/) (2014)
- [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)
- [Approximate resilience, monotonicity, and the complexity of agnostic learning](https://mlsanity.com/paper/1405.5268/) (2014)
- [Hardness of Agnostically Learning Halfspaces from Worst-Case Lattice Problems](https://mlsanity.com/paper/2207.14030/) (2022)
- [Agnostic Learning of General ReLU Activation Using Gradient Descent](https://mlsanity.com/paper/2208.02711/) (2022)
- [Slide Reduction, Revisited---Filling the Gaps in SVP Approximation](https://mlsanity.com/paper/1908.03724/) (2019)

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

- [Efficient Testable Learning of Halfspaces with Adversarial Label Noise](https://mlsanity.com/paper/2303.05485/) (2023)
- [Tester-Learners for Halfspaces: Universal Algorithms](https://mlsanity.com/paper/2305.11765/) (2023)
- [Robustly Learning a Single Neuron via Sharpness](https://mlsanity.com/paper/2306.07892/) (2023)
- [Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise](https://mlsanity.com/paper/2306.16352/) (2023)
- [Robust Learning of Multi-index Models via Iterative Subspace Approximation](https://mlsanity.com/paper/2502.09525/) (2025)
- [Omnipredicting Single-Index Models with Multi-Index Models](https://mlsanity.com/paper/2411.13083/) (2024)
- [Improved Hardness Results for Learning Intersections of Halfspaces](https://mlsanity.com/paper/2402.15995/) (2024)
- [Active Learning of General Halfspaces: Label Queries vs Membership Queries](https://mlsanity.com/paper/2501.00508/) (2024)
- [Agnostic Learning of Arbitrary ReLU Activation under Gaussian Marginals](https://mlsanity.com/paper/2411.14349/) (2024)
- [Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials](https://mlsanity.com/paper/2307.12840/) (2023)
- [Distribution-Specific Auditing For Subgroup Fairness](https://mlsanity.com/paper/2401.16439/) (2024)
- [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)
- [Super Non-singular Decompositions of Polynomials and their Application to Robustly Learning Low-degree PTFs](https://mlsanity.com/paper/2404.00529/) (2024)
- [Cryptographic Hardness of Score Estimation](https://mlsanity.com/paper/2404.03272/) (2024)
- [Collaborative Learning with Different Labeling Functions](https://mlsanity.com/paper/2402.10445/) (2024)
- [Learning a Single Neuron Robustly to Distributional Shifts and Adversarial Label Noise](https://mlsanity.com/paper/2411.06697/) (2024)
- [Statistical Query Hardness of Multiclass Linear Classification with Random Classification Noise](https://mlsanity.com/paper/2502.11413/) (2025)
- [Robustly Learning Monotone Single-Index Models](https://mlsanity.com/paper/2508.04670/) (2025)
- [Distribution-Independent Regression for Generalized Linear Models with Oblivious Corruptions](https://mlsanity.com/paper/2309.11657/) (2023)
- [Reliable Learning of Halfspaces under Gaussian Marginals](https://mlsanity.com/paper/2411.11238/) (2024)
- [Personalized Prediction By Learning Halfspace Reference Classes Under Well-Behaved Distribution](https://mlsanity.com/paper/2509.15592/) (2025)
- [Statistical Query Lower Bounds for Smoothed Agnostic Learning](https://mlsanity.com/paper/2602.21191/) (2026)
- [Efficient and Noise-Tolerant PAC Learning of Multiclass Linear Classifiers](https://mlsanity.com/paper/2605.18662/) (2026)
- [Efficient Testable Learning of General Halfspaces with Adversarial Label Noise](https://mlsanity.com/paper/2408.17165/) (2024)
- [Robust Learning of a Group DRO Neuron](https://mlsanity.com/paper/2601.18115/) (2026)
- [Near-Optimal Cryptographic Hardness of Learning With Homogeneous Halfspaces Under Gaussian Marginals](https://mlsanity.com/paper/2604.26446/) (2026)
- [A Near-optimal SQ Lower Bound for Smoothed Agnostic Learning of Boolean Halfspaces](https://mlsanity.com/paper/2605.02350/) (2026)
- [Polynomial-Time Robust Multiclass Linear Classification under Gaussian Marginals](https://mlsanity.com/paper/2605.21428/) (2026)
- [Proper Agnostic Learning of Functions of Halfspaces under Gaussian Marginals](https://mlsanity.com/paper/2605.27594/) (2026)

## 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.