# Learning Noisy Halfspaces with a Margin: Massart is No Harder than Random

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 53 references that are in the map.
- First posted on arXiv 16 Jan 2025.

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

- [A Hitting Time Analysis of Stochastic Gradient Langevin Dynamics](https://mlsanity.com/paper/1702.05575/) (2017)
- [Distribution-Independent PAC Learning of Halfspaces with Massart Noise](https://mlsanity.com/paper/1906.10075/) (2019)
- [Complexity Theoretic Limitations on Learning Halfspaces](https://mlsanity.com/paper/1505.05800/) (2015)
- [Learning Geometric Concepts with Nasty Noise](https://mlsanity.com/paper/1707.01242/) (2017)
- [Learning Halfspaces with Massart Noise Under Structured Distributions](https://mlsanity.com/paper/2002.05632/) (2020)
- [Efficient Learning of Linear Separators under Bounded Noise](https://mlsanity.com/paper/1503.03594/) (2015)
- [Non-Convex SGD Learns Halfspaces with Adversarial Label Noise](https://mlsanity.com/paper/2006.06742/) (2020)
- [Learning General Halfspaces with General Massart Noise under the Gaussian Distribution](https://mlsanity.com/paper/2108.08767/) (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)
- [Noise-tolerant, Reliable Active Classification with Comparison Queries](https://mlsanity.com/paper/2001.05497/) (2020)
- [Forster Decomposition and Learning Halfspaces with Noise](https://mlsanity.com/paper/2107.05582/) (2021)
- [Agnostically Learning Single-Index Models using Omnipredictors](https://mlsanity.com/paper/2306.10615/) (2023)
- [Learning Halfspaces with Tsybakov Noise](https://mlsanity.com/paper/2006.06467/) (2020)
- [Optimal SQ Lower Bounds for Learning Halfspaces with Massart Noise](https://mlsanity.com/paper/2201.09818/) (2022)
- [A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise](https://mlsanity.com/paper/2010.01705/) (2020)
- [Robustly Learning Single-Index Models via Alignment Sharpness](https://mlsanity.com/paper/2402.17756/) (2024)
- [SLaM: Student-Label Mixing for Distillation with Unlabeled Examples](https://mlsanity.com/paper/2302.03806/) (2023)
- [Non-Convex Matrix Completion Against a Semi-Random Adversary](https://mlsanity.com/paper/1803.10846/) (2018)
- [Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise](https://mlsanity.com/paper/2306.16352/) (2023)
- [Nearly Tight Bounds for Robust Proper Learning of Halfspaces with a Margin](https://mlsanity.com/paper/1908.11335/) (2019)
- [Dueling Optimization with a Monotone Adversary](https://mlsanity.com/paper/2311.11185/) (2023)
- [Structured Semidefinite Programming for Recovering Structured Preconditioners](https://mlsanity.com/paper/2310.18265/) (2023)

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

- [A General Framework for Estimating Preferences Using Response Time Data](https://mlsanity.com/paper/2507.20403/) (2025)
- [Conservative classifiers do consistently well with improving agents: characterizing statistical and online learning](https://mlsanity.com/paper/2506.05252/) (2025)
- [Adapting to Linear Separable Subsets with Large-Margin in Differentially Private Learning](https://mlsanity.com/paper/2505.24737/) (2025)
- [Combinatorial Sparse PCA Beyond the Spiked Identity Model](https://mlsanity.com/paper/2603.02607/) (2026)
- [Efficiently Learning Drifting Halfspaces with Massart Noise](https://mlsanity.com/paper/2606.11149/) (2026)

## Abstract (arXiv)

We study the problem of PAC learning γ-margin halfspaces with Massart noise. We propose a simple proper learning algorithm, the Perspectron, that has sample complexity widetildeO((εγ)-2) and achieves classification error at most η+ε where η is the Massart noise rate. Prior works [DGT19,CKMY20] came with worse sample complexity guarantees (in both ε and γ) or could only handle random classification noise [DDK+23,KIT+23] -- a much milder noise assumption. We also show that our results extend to the more challenging setting of learning generalized linear models with a known link function under Massart noise, achieving a similar sample complexity to the halfspace case. This significantly improves upon the prior state-of-the-art in this setting due to [CKMY20], who introduced this model.