mlsanityData to 7 Oct 2026

Learning Halfspaces with Massart Noise Under Structured Distributions

arXiv 2002.05632 ↗First posted 13 Feb 2020cs.LG cs.DS math.STcited by 45

Not on the map. Why?

Abstract (arXiv)

We study the problem of learning halfspaces with Massart noise in the distribution-specific PAC model. We give the first computationally efficient algorithm for this problem with respect to a broad family of distributions, including log-concave distributions. This resolves an open question posed in a number of prior works. Our approach is extremely simple: We identify a smooth em non-convex surrogate loss with the property that any approximate stationary point of this loss defines a halfspace that is close to the target halfspace. Given this structural result, we can use SGD to solve the underlying learning problem.

Key facts. Cited by 45 papers in the map (data through 7 Oct 2026). First posted on arXiv 13 Feb 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

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

45 papers.

Sort:

  1. 2022Random Feature Amplification: Feature Learning and Generalization in Neural Networkscited by 33
  2. 2021Learning General Halfspaces with General Massart Noise under the Gaussian Distributioncited by 27
  3. 2022Learning a Single Neuron with Adversarial Label Noise via Gradient Descentcited by 20
  4. 2021Self-training Converts Weak Learners to Strong Learners in Mixture Modelscited by 19
  5. 2023Efficient Testable Learning of Halfspaces with Adversarial Label Noisecited by 19
  6. 2021Improved Algorithms for Efficient Active Learning Halfspaces with Massart and Tsybakov noisecited by 18
  7. 2022Semi-Random Sparse Recovery in Nearly-Linear Timecited by 18
  8. 2023An Efficient Tester-Learner for Halfspacescited by 18
  9. 2021Provable Generalization of SGD-trained Neural Networks of Any Width in the Presence of Adversarial Label Noisecited by 17
  10. 2023Tester-Learners for Halfspaces: Universal Algorithmscited by 17
  11. 2021Forster Decomposition and Learning Halfspaces with Noisecited by 16
  12. 2022Optimal SQ Lower Bounds for Learning Halfspaces with Massart Noisecited by 14
33 more
  1. 2021Sample-Optimal PAC Learning of Halfspaces with Malicious Noisecited by 11
  2. 2022List-Decodable Sparse Mean Estimationcited by 11
  3. 2024Smoothed Analysis for Learning Concepts with Low Intrinsic Dimensioncited by 11
  4. 2021Provable Robustness of Adversarial Training for Learning Halfspaces with Noisecited by 10
  5. 2021Boosting in the Presence of Massart Noisecited by 10
  6. 2021ReLU Regression with Massart Noisecited by 10
  7. 2023Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noisecited by 9
  8. 2025Robust Learning of Multi-index Models via Iterative Subspace Approximationcited by 8
  9. 2025The Power of Iterative Filtering for Supervised Learning with (Heavy) Contaminationcited 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. 2023Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noisecited by 5
  14. 2024A Separation in Heavy-Tailed Sampling: Gaussian vs. Stable Oracles for Proximal Samplerscited by 5
  15. 2024Efficient PAC Learning of Halfspaces with Constant Malicious Noise Ratecited by 5
  16. 2025Learning Noisy Halfspaces with a Margin: Massart is No Harder than Randomcited by 5
  17. 2021Semi-verified PAC Learning from the Crowdcited by 4
  18. 2022Outlier Robust and Sparse Estimation of Linear Regression Coefficientscited by 4
  19. 2023Mean-Square Analysis of Discretized Ito Diffusions for Heavy-tailed Samplingcited by 4
  20. 2025Testing Noise Assumptions of Learning Algorithmscited by 4
  21. 2022Agnostic Learnability of Halfspaces via Logistic Losscited by 2
  22. 2023Learning to Abstain From Uninformative Datacited by 2
  23. 2025Smoothed Agnostic Learning of Halfspaces over the Hypercubecited by 2
  24. 2022On PAC Learning Halfspaces in Non-interactive Local Privacy Model with Public Unlabeled Datacited by 1
  25. 2023Efficient Active Learning Halfspaces with Tsybakov Noise: A Non-convex Optimization Approachcited by 1
  26. 2024Reliable Learning of Halfspaces under Gaussian Marginalscited by 1
  27. 2025Personalized Prediction By Learning Halfspace Reference Classes Under Well-Behaved Distributioncited by 1
  28. 2025A Fully Polynomial-Time Algorithm for Robustly Learning Halfspaces over the Hypercubecited by 1
  29. 2024Adversarially-Robust Inference on Trees via Belief Propagationcited by 0
  30. 2025Towards Efficient Contrastive PAC Learningcited by 0
  31. 2026The Quantum Learning Menagerie (A survey on Quantum learning for Classical concepts)cited by 0
  32. 2026Testable Learning of General Halfspaces under Massart Noisecited by 0
  33. 2026Optimal Learning Under Tsybakov Noisecited by 0