# Efficient Learning of Linear Separators under Bounded Noise

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

## Key facts

- Cited by 36 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Mar 2015.

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

- [Smoothed Analysis with Adaptive Adversaries](https://mlsanity.com/paper/2102.08446/) (2021)
- [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)
- [Robustly-reliable learners under poisoning attacks](https://mlsanity.com/paper/2203.04160/) (2022)
- [Improved Algorithms for Efficient Active Learning Halfspaces with Massart and Tsybakov noise](https://mlsanity.com/paper/2102.05312/) (2021)
- [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)
- [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)
- [Reliable learning in challenging environments](https://mlsanity.com/paper/2304.03370/) (2023)
- [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)
- [Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise](https://mlsanity.com/paper/2307.08438/) (2023)
- [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)
- [Testing Noise Assumptions of Learning Algorithms](https://mlsanity.com/paper/2501.09189/) (2025)
- [Smoothed Agnostic Learning of Halfspaces over the Hypercube](https://mlsanity.com/paper/2511.17782/) (2025)
- [Agnostic Learnability of Halfspaces via Logistic Loss](https://mlsanity.com/paper/2201.13419/) (2022)
- [Learning to Abstain From Uninformative Data](https://mlsanity.com/paper/2309.14240/) (2023)
- [Conservative classifiers do consistently well with improving agents: characterizing statistical and online learning](https://mlsanity.com/paper/2506.05252/) (2025)
- [The Active and Noise-Tolerant Strategic Perceptron](https://mlsanity.com/paper/2512.01783/) (2025)
- [On PAC Learning Halfspaces in Non-interactive Local Privacy Model with Public Unlabeled Data](https://mlsanity.com/paper/2209.08319/) (2022)
- [Self-Directed Linear Classification](https://mlsanity.com/paper/2308.03142/) (2023)
- [Efficient Active Learning Halfspaces with Tsybakov Noise: A Non-convex Optimization Approach](https://mlsanity.com/paper/2310.15411/) (2023)
- [Online Learning of Halfspaces with Massart Noise](https://mlsanity.com/paper/2405.12958/) (2024)
- [Solving 0-1 Integer Programs with Unknown Knapsack Constraints Using Membership Oracles](https://mlsanity.com/paper/2405.14090/) (2024)
- [Reliable Learning of Halfspaces under Gaussian Marginals](https://mlsanity.com/paper/2411.11238/) (2024)

## Abstract (arXiv)

We study the learnability of linear separators in Red in the presence of bounded (a.k.a Massart) noise. This is a realistic generalization of the random classification noise model, where the adversary can flip each example x with probability η(x) ≤ η. We provide the first polynomial time algorithm that can learn linear separators to arbitrarily small excess error in this noise model under the uniform distribution over the unit ball in Red, for some constant value of η. While widely studied in the statistical learning theory community in the context of getting faster convergence rates, computationally efficient algorithms in this model had remained elusive. Our work provides the first evidence that one can indeed design algorithms achieving arbitrarily small excess error in polynomial time under this realistic noise model and thus opens up a new and exciting line of research. We additionally provide lower bounds showing that popular algorithms such as hinge loss minimization and averaging cannot lead to arbitrarily small excess error under Massart noise, even under the uniform distribution. Our work instead, makes use of a margin based technique developed in the context of active learning. As a result, our algorithm is also an active learning algorithm with label complexity that is only a logarithmic the desired excess error ε.