# Non-Convex SGD Learns Halfspaces with Adversarial Label Noise

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

## Key facts

- Cited by 30 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Jun 2020.

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

- [The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals](https://mlsanity.com/paper/2102.04401/) (2021)
- [Testing distributional assumptions of learning algorithms](https://mlsanity.com/paper/2204.07196/) (2022)
- [Agnostic Proper Learning of Halfspaces under Gaussian Marginals](https://mlsanity.com/paper/2102.05629/) (2021)
- [Streaming Algorithms for High-Dimensional Robust Statistics](https://mlsanity.com/paper/2204.12399/) (2022)
- [Learning a Single Neuron with Adversarial Label Noise via Gradient Descent](https://mlsanity.com/paper/2206.08918/) (2022)
- [Self-training Converts Weak Learners to Strong Learners in Mixture Models](https://mlsanity.com/paper/2106.13805/) (2021)
- [Efficient Testable Learning of Halfspaces with Adversarial Label Noise](https://mlsanity.com/paper/2303.05485/) (2023)
- [An Efficient Tester-Learner for Halfspaces](https://mlsanity.com/paper/2302.14853/) (2023)
- [Provable Generalization of SGD-trained Neural Networks of Any Width in the Presence of Adversarial Label Noise](https://mlsanity.com/paper/2101.01152/) (2021)
- [Tester-Learners for Halfspaces: Universal Algorithms](https://mlsanity.com/paper/2305.11765/) (2023)
- [Agnostically Learning Single-Index Models using Omnipredictors](https://mlsanity.com/paper/2306.10615/) (2023)
- [Provable Robustness of Adversarial Training for Learning Halfspaces with Noise](https://mlsanity.com/paper/2104.09437/) (2021)
- [Robust Learning of Multi-index Models via Iterative Subspace Approximation](https://mlsanity.com/paper/2502.09525/) (2025)
- [The Power of Iterative Filtering for Supervised Learning with (Heavy) Contamination](https://mlsanity.com/paper/2505.20177/) (2025)
- [Learning Noisy Halfspaces with a Margin: Massart is No Harder than Random](https://mlsanity.com/paper/2501.09851/) (2025)
- [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)
- [AdaBoost and robust one-bit compressed sensing](https://mlsanity.com/paper/2105.02083/) (2021)
- [Agnostic Learnability of Halfspaces via Logistic Loss](https://mlsanity.com/paper/2201.13419/) (2022)
- [Attribute-Efficient PAC Learning of Sparse Halfspaces with Constant Malicious Noise Rate](https://mlsanity.com/paper/2505.21430/) (2025)
- [Agnostic learning in (almost) optimal time via Gaussian surface area](https://mlsanity.com/paper/2603.06027/) (2026)
- [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)
- [Testable Learning of General Halfspaces under Massart Noise](https://mlsanity.com/paper/2602.22300/) (2026)
- [Near-Optimal Cryptographic Hardness of Learning With Homogeneous Halfspaces Under Gaussian Marginals](https://mlsanity.com/paper/2604.26446/) (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 problem of agnostically learning homogeneous halfspaces in the distribution-specific PAC model. For a broad family of structured distributions, including log-concave distributions, we show that non-convex SGD efficiently converges to a solution with misclassification error O(opt)+eps, where opt is the misclassification error of the best-fitting halfspace. In sharp contrast, we show that optimizing any convex surrogate inherently leads to misclassification error of ω(opt), even under Gaussian marginals.