# Distribution-Independent PAC Learning of Halfspaces with Massart Noise

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

## Key facts

- Cited by 54 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Jun 2019.

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

- [Smoothed Analysis with Adaptive Adversaries](https://mlsanity.com/paper/2102.08446/) (2021)
- [Learning General Halfspaces with General Massart Noise under the Gaussian Distribution](https://mlsanity.com/paper/2108.08767/) (2021)
- [Cryptographic Hardness of Learning Halfspaces with Massart Noise](https://mlsanity.com/paper/2207.14266/) (2022)
- [Self-training Converts Weak Learners to Strong Learners in Mixture Models](https://mlsanity.com/paper/2106.13805/) (2021)
- [Improved Algorithms for Efficient Active Learning Halfspaces with Massart and Tsybakov noise](https://mlsanity.com/paper/2102.05312/) (2021)
- [Semi-Random Sparse Recovery in Nearly-Linear Time](https://mlsanity.com/paper/2203.04002/) (2022)
- [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)
- [Forster Decomposition and Learning Halfspaces with Noise](https://mlsanity.com/paper/2107.05582/) (2021)
- [Optimal SQ Lower Bounds for Learning Halfspaces with Massart Noise](https://mlsanity.com/paper/2201.09818/) (2022)
- [Sample-Optimal PAC Learning of Halfspaces with Malicious Noise](https://mlsanity.com/paper/2102.06247/) (2021)
- [A Strongly Polynomial Algorithm for Approximate Forster Transforms and its Application to Halfspace Learning](https://mlsanity.com/paper/2212.03008/) (2022)
- [Smoothed Analysis for Learning Concepts with Low Intrinsic Dimension](https://mlsanity.com/paper/2407.00966/) (2024)
- [Boosting in the Presence of Massart Noise](https://mlsanity.com/paper/2106.07779/) (2021)
- [ReLU Regression with Massart Noise](https://mlsanity.com/paper/2109.04623/) (2021)
- [SLaM: Student-Label Mixing for Distillation with Unlabeled Examples](https://mlsanity.com/paper/2302.03806/) (2023)
- [Reliable learning in challenging environments](https://mlsanity.com/paper/2304.03370/) (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)
- [Clustering with Queries under Semi-Random Noise](https://mlsanity.com/paper/2206.04583/) (2022)
- [Dueling Optimization with a Monotone Adversary](https://mlsanity.com/paper/2311.11185/) (2023)
- [Robust and Sparse Estimation of Linear Regression Coefficients with Heavy-tailed Noises and Covariates](https://mlsanity.com/paper/2206.07594/) (2022)
- [A Near-optimal Algorithm for Learning Margin Halfspaces with Massart Noise](https://mlsanity.com/paper/2501.09691/) (2025)
- [SQ Lower Bounds for Learning Single Neurons with Massart Noise](https://mlsanity.com/paper/2210.09949/) (2022)
- [On the Growth of Mistakes in Differentially Private Online Learning: A Lower Bound Perspective](https://mlsanity.com/paper/2402.16778/) (2024)
- [Efficient PAC Learning of Halfspaces with Constant Malicious Noise Rate](https://mlsanity.com/paper/2410.01186/) (2024)
- [Learning Noisy Halfspaces with a Margin: Massart is No Harder than Random](https://mlsanity.com/paper/2501.09851/) (2025)
- [Semi-verified PAC Learning from the Crowd](https://mlsanity.com/paper/2106.07080/) (2021)
- [Outlier Robust and Sparse Estimation of Linear Regression Coefficients](https://mlsanity.com/paper/2208.11592/) (2022)
- [Testing Noise Assumptions of Learning Algorithms](https://mlsanity.com/paper/2501.09189/) (2025)

## Abstract (arXiv)

We study the problem of em distribution-independent PAC learning of halfspaces in the presence of Massart noise. Specifically, we are given a set of labeled examples (x, y) drawn from a distribution D on ℝd+1 such that the marginal distribution on the unlabeled points x is arbitrary and the labels y are generated by an unknown halfspace corrupted with Massart noise at noise rate η<1/2. The goal is to find a hypothesis h that minimizes the misclassification error Pr(x, y) ~ D left[ h(x) neq y right]. We give a polyleft(d, 1/ε right) time algorithm for this problem with misclassification error η+ε. We also provide evidence that improving on the error guarantee of our algorithm might be computationally hard. Prior to our work, no efficient weak (distribution-independent) learner was known in this model, even for the class of disjunctions. The existence of such an algorithm for halfspaces (or even disjunctions) has been posed as an open question in various works, starting with Sloan (1988), Cohen (1997), and was most recently highlighted in Avrim Blum's FOCS 2003 tutorial.