# Agnostic Proper Learning of Halfspaces under Gaussian Marginals

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 37 references that are in the map.
- First posted on arXiv 10 Feb 2021.

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

- [Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals](https://mlsanity.com/paper/2006.16200/) (2020)
- [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)
- [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)
- [Approximation Schemes for ReLU Regression](https://mlsanity.com/paper/2005.12844/) (2020)
- [Non-Convex SGD Learns Halfspaces with Adversarial Label Noise](https://mlsanity.com/paper/2006.06742/) (2020)
- [Efficient Truncated Statistics with Unknown Truncation](https://mlsanity.com/paper/1908.01034/) (2019)
- [A PTAS for Agnostically Learning Halfspaces](https://mlsanity.com/paper/1410.7050/) (2014)

## Built on by (most cited first, 21 of 21)

- [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)
- [Efficient Testable Learning of Halfspaces with Adversarial Label Noise](https://mlsanity.com/paper/2303.05485/) (2023)
- [Smoothed Analysis for Learning Concepts with Low Intrinsic Dimension](https://mlsanity.com/paper/2407.00966/) (2024)
- [Agnostic Learning of Arbitrary ReLU Activation under Gaussian Marginals](https://mlsanity.com/paper/2411.14349/) (2024)
- [Semi-verified PAC Learning from the Crowd](https://mlsanity.com/paper/2106.07080/) (2021)
- [Distribution-Specific Auditing For Subgroup Fairness](https://mlsanity.com/paper/2401.16439/) (2024)
- [Testing Noise Assumptions of Learning Algorithms](https://mlsanity.com/paper/2501.09189/) (2025)
- [Approximate Maximum Halfspace Discrepancy](https://mlsanity.com/paper/2106.13851/) (2021)
- [Robust learning of halfspaces under log-concave marginals](https://mlsanity.com/paper/2505.13708/) (2025)
- [Learning and Testing Convex Functions](https://mlsanity.com/paper/2511.11498/) (2025)
- [Online Learning of Halfspaces with Massart Noise](https://mlsanity.com/paper/2405.12958/) (2024)
- [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)
- [A Fully Polynomial-Time Algorithm for Robustly Learning Halfspaces over the Hypercube](https://mlsanity.com/paper/2511.07244/) (2025)
- [Statistical Query Lower Bounds for Smoothed Agnostic Learning](https://mlsanity.com/paper/2602.21191/) (2026)
- [Efficient Testable Learning of General Halfspaces with Adversarial Label Noise](https://mlsanity.com/paper/2408.17165/) (2024)
- [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)
- [Proper Agnostic Learning of Functions of Halfspaces under Gaussian Marginals](https://mlsanity.com/paper/2605.27594/) (2026)

## Abstract (arXiv)

We study the problem of agnostically learning halfspaces under the Gaussian distribution. Our main result is the em first proper learning algorithm for this problem whose sample complexity and computational complexity qualitatively match those of the best known improper agnostic learner. Building on this result, we also obtain the first proper polynomial-time approximation scheme (PTAS) for agnostically learning homogeneous halfspaces. Our techniques naturally extend to agnostically learning linear models with respect to other non-linear activations, yielding in particular the first proper agnostic algorithm for ReLU regression.