mlsanityData to 7 Oct 2026

Efficient PAC Learning of Halfspaces with Constant Malicious Noise Rate

arXiv 2410.01186 ↗First posted 2 Oct 2024cs.LG cs.DS stat.MLcited by 5

Not on the map. Why?

Abstract (arXiv)

Understanding noise tolerance of machine learning algorithms is a central quest in learning theory. In this work, we study the problem of computationally efficient PAC learning of halfspaces in the presence of malicious noise, where an adversary can corrupt both instances and labels of training samples. The best-known noise tolerance either depends on a target error rate under distributional assumptions or on a margin parameter under large-margin conditions. In this work, we show that when both types of conditions are satisfied, it is possible to achieve constant noise tolerance by minimizing a reweighted hinge loss. Our key ingredients include: 1) an efficient algorithm that finds weights to control the gradient deterioration from corrupted samples, and 2) a new analysis on the robustness of the hinge loss equipped with such weights.

Key facts. Cited by 5 papers in the map (data through 7 Oct 2026). Builds on 33 of its 78 references that are in the map. First posted on arXiv 2 Oct 2024.

Builds on

33 of 78 references.

References · 33

  1. 2021Convex optimizationcited by 2,479
  2. 2016Robust Estimators in High Dimensions without the Computational Intractabilitycited by 209
  3. 2016Agnostic Estimation of Mean and Covariancecited by 131
  4. 2016Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixturescited by 114
  5. 2018Robust Estimation via Robust Gradient Estimationcited by 76
  6. 2019Distribution-Independent PAC Learning of Halfspaces with Massart Noisecited by 54
  7. 2021The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginalscited by 52
  8. 2015Complexity Theoretic Limitations on Learning Halfspacescited by 50
  9. 2017Learning Geometric Concepts with Nasty Noisecited by 46
  10. 2020Learning Halfspaces with Massart Noise Under Structured Distributionscited by 45
  11. 2020Robust and Heavy-Tailed Mean Estimation Made Simple, via Regret Minimizationcited by 44
  12. 2019Quantum Entropy Scoring for Fast Robust Mean Estimation and Improved Outlier Detectioncited by 41
21 more
  1. 2018High-Dimensional Robust Mean Estimation in Nearly-Linear Timecited by 39
  2. 2015Efficient Learning of Linear Separators under Bounded Noisecited by 36
  3. 2020Efficient active learning of sparse halfspaces with arbitrary bounded noisecited by 29
  4. 2021Learning General Halfspaces with General Massart Noise under the Gaussian Distributioncited by 27
  5. 2019Outlier-Robust High-Dimensional Sparse Estimation via Iterative Filteringcited by 23
  6. 2022Robust Sparse Mean Estimation via Sum of Squarescited by 23
  7. 2022Learning a Single Neuron with Adversarial Label Noise via Gradient Descentcited by 20
  8. 2021Improved Algorithms for Efficient Active Learning Halfspaces with Massart and Tsybakov noisecited by 18
  9. 2020Learning Halfspaces with Tsybakov Noisecited by 15
  10. 2020Attribute-Efficient Learning of Halfspaces with Malicious Noise: Near-Optimal Label Complexity and Noise Tolerancecited by 12
  11. 2020On the Power of Localized Perceptron for Label-Optimal Learning of Halfspaces with Adversarial Noisecited by 11
  12. 2021Sample-Optimal PAC Learning of Halfspaces with Malicious Noisecited by 11
  13. 2022List-Decodable Sparse Mean Estimationcited by 11
  14. 2020Efficient PAC Learning from the Crowd with Pairwise Comparisonscited by 7
  15. 2020On the Error Resistance of Hinge Loss Minimizationcited by 5
  16. 2021Semi-verified PAC Learning from the Crowdcited by 4
  17. 2023Attribute-Efficient PAC Learning of Low-Degree Polynomial Threshold Functions with Nasty Noisecited by 3
  18. 2023Online Robust Mean Estimationcited by 3
  19. 2024Super Non-singular Decompositions of Polynomials and their Application to Robustly Learning Low-degree PTFscited by 3
  20. 2024The Sample Complexity of Smooth Boosting and the Tightness of the Hardcore Theoremcited by 2
  21. 2023Efficient Active Learning Halfspaces with Tsybakov Noise: A Non-convex Optimization Approachcited by 1

Built on by

Cited by year (2026 to 7 Oct)

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

5 papers.

  1. 2025The Power of Iterative Filtering for Supervised Learning with (Heavy) Contaminationcited by 7
  2. 2025Attribute-Efficient PAC Learning of Sparse Halfspaces with Constant Malicious Noise Ratecited by 2
  3. 2026Efficient and Noise-Tolerant PAC Learning of Multiclass Linear Classifierscited by 1
  4. 2025Towards Efficient Contrastive PAC Learningcited by 0
  5. 2026Sum-of-Squares Degree Barriers for the Reweighted-Hinge Method in Robust Halfspace Learning: A Christoffel-Function Characterizationcited by 0