mlsanityData to 14 Oct 2026

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

arXiv 2501.09851 ↗First posted 16 Jan 2025cs.LG cs.DScited by 5

Not on the map. Why?

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.

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

23 of 53 references.

References · 23

  1. 2017A Hitting Time Analysis of Stochastic Gradient Langevin Dynamicscited by 71
  2. 2019Distribution-Independent PAC Learning of Halfspaces with Massart Noisecited by 54
  3. 2015Complexity Theoretic Limitations on Learning Halfspacescited by 50
  4. 2017Learning Geometric Concepts with Nasty Noisecited by 46
  5. 2020Learning Halfspaces with Massart Noise Under Structured Distributionscited by 45
  6. 2015Efficient Learning of Linear Separators under Bounded Noisecited by 36
  7. 2020Non-Convex SGD Learns Halfspaces with Adversarial Label Noisecited by 30
  8. 2021Learning General Halfspaces with General Massart Noise under the Gaussian Distributioncited by 27
  9. 2021Improved Algorithms for Efficient Active Learning Halfspaces with Massart and Tsybakov noisecited by 18
  10. 2022Semi-Random Sparse Recovery in Nearly-Linear Timecited by 18
  11. 2020Noise-tolerant, Reliable Active Classification with Comparison Queriescited by 17
  12. 2021Forster Decomposition and Learning Halfspaces with Noisecited by 16
11 more
  1. 2023Agnostically Learning Single-Index Models using Omnipredictorscited by 16
  2. 2020Learning Halfspaces with Tsybakov Noisecited by 15
  3. 2022Optimal SQ Lower Bounds for Learning Halfspaces with Massart Noisecited by 14
  4. 2020A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noisecited by 13
  5. 2024Robustly Learning Single-Index Models via Alignment Sharpnesscited by 11
  6. 2023SLaM: Student-Label Mixing for Distillation with Unlabeled Examplescited by 10
  7. 2018Non-Convex Matrix Completion Against a Semi-Random Adversarycited by 9
  8. 2023Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noisecited by 9
  9. 2019Nearly Tight Bounds for Robust Proper Learning of Halfspaces with a Margincited by 8
  10. 2023Dueling Optimization with a Monotone Adversarycited by 8
  11. 2023Structured Semidefinite Programming for Recovering Structured Preconditionerscited by 5

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 3; 2026: 2.

5 papers.

  1. 2025A General Framework for Estimating Preferences Using Response Time Datacited by 3
  2. 2025Conservative classifiers do consistently well with improving agents: characterizing statistical and online learningcited by 2
  3. 2025Adapting to Linear Separable Subsets with Large-Margin in Differentially Private Learningcited by 0
  4. 2026Combinatorial Sparse PCA Beyond the Spiked Identity Modelcited by 0
  5. 2026Efficiently Learning Drifting Halfspaces with Massart Noisecited by 0