mlsanityData to 7 Oct 2026

Distribution-Independent PAC Learning of Halfspaces with Massart Noise

arXiv 1906.10075 ↗First posted 24 Jun 2019cs.LG cs.DS math.STcited by 54

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 14; 2022: 9; 2023: 9; 2024: 5; 2025: 10; 2026: 7.

54 papers.

Sort:

  1. 2021Smoothed Analysis with Adaptive Adversariescited by 57
  2. 2021Learning General Halfspaces with General Massart Noise under the Gaussian Distributioncited by 27
  3. 2022Cryptographic Hardness of Learning Halfspaces with Massart Noisecited by 25
  4. 2021Self-training Converts Weak Learners to Strong Learners in Mixture Modelscited by 19
  5. 2021Improved Algorithms for Efficient Active Learning Halfspaces with Massart and Tsybakov noisecited by 18
  6. 2022Semi-Random Sparse Recovery in Nearly-Linear Timecited by 18
  7. 2023An Efficient Tester-Learner for Halfspacescited by 18
  8. 2021Provable Generalization of SGD-trained Neural Networks of Any Width in the Presence of Adversarial Label Noisecited by 17
  9. 2021Forster Decomposition and Learning Halfspaces with Noisecited by 16
  10. 2022Optimal SQ Lower Bounds for Learning Halfspaces with Massart Noisecited by 14
  11. 2021Sample-Optimal PAC Learning of Halfspaces with Malicious Noisecited by 11
  12. 2022A Strongly Polynomial Algorithm for Approximate Forster Transforms and its Application to Halfspace Learningcited by 11
38 more
  1. 2024Smoothed Analysis for Learning Concepts with Low Intrinsic Dimensioncited by 11
  2. 2021Boosting in the Presence of Massart Noisecited by 10
  3. 2021ReLU Regression with Massart Noisecited by 10
  4. 2023SLaM: Student-Label Mixing for Distillation with Unlabeled Examplescited by 9
  5. 2023Reliable learning in challenging environmentscited by 9
  6. 2023Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noisecited by 9
  7. 2022Clustering with Queries under Semi-Random Noisecited by 8
  8. 2025Robust Learning of Multi-index Models via Iterative Subspace Approximationcited by 8
  9. 2023Dueling Optimization with a Monotone Adversarycited by 7
  10. 2022Robust and Sparse Estimation of Linear Regression Coefficients with Heavy-tailed Noises and Covariatescited by 6
  11. 2025A Near-optimal Algorithm for Learning Margin Halfspaces with Massart Noisecited by 6
  12. 2022SQ Lower Bounds for Learning Single Neurons with Massart Noisecited by 5
  13. 2024On the Growth of Mistakes in Differentially Private Online Learning: A Lower Bound Perspectivecited by 5
  14. 2024Efficient PAC Learning of Halfspaces with Constant Malicious Noise Ratecited by 5
  15. 2025Learning Noisy Halfspaces with a Margin: Massart is No Harder than Randomcited by 5
  16. 2021Semi-verified PAC Learning from the Crowdcited by 4
  17. 2022Outlier Robust and Sparse Estimation of Linear Regression Coefficientscited by 4
  18. 2025Testing Noise Assumptions of Learning Algorithmscited by 4
  19. 2021Approximate Maximum Halfspace Discrepancycited by 3
  20. 2025A General Framework for Estimating Preferences Using Response Time Datacited by 3
  21. 2021Exponential Weights Algorithms for Selective Learningcited by 2
  22. 2022Agnostic Learnability of Halfspaces via Logistic Losscited by 2
  23. 2023Learning to Abstain From Uninformative Datacited by 2
  24. 2025Conservative classifiers do consistently well with improving agents: characterizing statistical and online learningcited by 2
  25. 2025Smoothed Agnostic Learning of Halfspaces over the Hypercubecited by 2
  26. 2021Self-Training of Halfspaces with Generalization Guarantees under Massart Mislabeling Noise Modelcited by 1
  27. 2023Correcting Underrepresentation and Intersectional Bias for Classificationcited by 1
  28. 2023Efficient Active Learning Halfspaces with Tsybakov Noise: A Non-convex Optimization Approachcited by 1
  29. 2024Online Learning of Halfspaces with Massart Noisecited by 1
  30. 2025Reweighting Improves Conditional Risk Boundscited by 1
  31. 2025Learning from Interval Targetscited by 1
  32. 2026Is Multi-Distribution Learning as Easy as PAC Learning: Sharp Rates with Bounded Label Noisecited by 1
  33. 2026Hardness of High-Dimensional Linear Classificationcited by 1
  34. 2021On Agnostic PAC Learning using L2-polynomial Regression and Fourier-based Algorithmscited by 0
  35. 2023Agnostic PAC Learning of k-juntas Using L2-Polynomial Regressioncited by 0
  36. 2024Adversarially-Robust Inference on Trees via Belief Propagationcited by 0
  37. 2025Adapting to Linear Separable Subsets with Large-Margin in Differentially Private Learningcited by 0
  38. 2026Robust Learning of a Group DRO Neuroncited by 0

50 most cited of 54 All 54 (JSON)