# Efficient PAC Learning of Halfspaces with Constant Malicious Noise Rate

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

## Key facts

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

## Builds on (most cited first, 30 of 33)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Robust Estimators in High Dimensions without the Computational Intractability](https://mlsanity.com/paper/1604.06443/) (2016)
- [Agnostic Estimation of Mean and Covariance](https://mlsanity.com/paper/1604.06968/) (2016)
- [Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixtures](https://mlsanity.com/paper/1611.03473/) (2016)
- [Robust Estimation via Robust Gradient Estimation](https://mlsanity.com/paper/1802.06485/) (2018)
- [Distribution-Independent PAC Learning of Halfspaces with Massart Noise](https://mlsanity.com/paper/1906.10075/) (2019)
- [The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals](https://mlsanity.com/paper/2102.04401/) (2021)
- [Complexity Theoretic Limitations on Learning Halfspaces](https://mlsanity.com/paper/1505.05800/) (2015)
- [Learning Geometric Concepts with Nasty Noise](https://mlsanity.com/paper/1707.01242/) (2017)
- [Learning Halfspaces with Massart Noise Under Structured Distributions](https://mlsanity.com/paper/2002.05632/) (2020)
- [Robust and Heavy-Tailed Mean Estimation Made Simple, via Regret Minimization](https://mlsanity.com/paper/2007.15839/) (2020)
- [Quantum Entropy Scoring for Fast Robust Mean Estimation and Improved Outlier Detection](https://mlsanity.com/paper/1906.11366/) (2019)
- [High-Dimensional Robust Mean Estimation in Nearly-Linear Time](https://mlsanity.com/paper/1811.09380/) (2018)
- [Efficient Learning of Linear Separators under Bounded Noise](https://mlsanity.com/paper/1503.03594/) (2015)
- [Efficient active learning of sparse halfspaces with arbitrary bounded noise](https://mlsanity.com/paper/2002.04840/) (2020)
- [Learning General Halfspaces with General Massart Noise under the Gaussian Distribution](https://mlsanity.com/paper/2108.08767/) (2021)
- [Robust Sparse Mean Estimation via Sum of Squares](https://mlsanity.com/paper/2206.03441/) (2022)
- [Outlier-Robust High-Dimensional Sparse Estimation via Iterative Filtering](https://mlsanity.com/paper/1911.08085/) (2019)
- [Learning a Single Neuron with Adversarial Label Noise via Gradient Descent](https://mlsanity.com/paper/2206.08918/) (2022)
- [Improved Algorithms for Efficient Active Learning Halfspaces with Massart and Tsybakov noise](https://mlsanity.com/paper/2102.05312/) (2021)
- [Learning Halfspaces with Tsybakov Noise](https://mlsanity.com/paper/2006.06467/) (2020)
- [Attribute-Efficient Learning of Halfspaces with Malicious Noise: Near-Optimal Label Complexity and Noise Tolerance](https://mlsanity.com/paper/2006.03781/) (2020)
- [On the Power of Localized Perceptron for Label-Optimal Learning of Halfspaces with Adversarial Noise](https://mlsanity.com/paper/2012.10793/) (2020)
- [Sample-Optimal PAC Learning of Halfspaces with Malicious Noise](https://mlsanity.com/paper/2102.06247/) (2021)
- [List-Decodable Sparse Mean Estimation](https://mlsanity.com/paper/2205.14337/) (2022)
- [Efficient PAC Learning from the Crowd with Pairwise Comparisons](https://mlsanity.com/paper/2011.01104/) (2020)
- [On the Error Resistance of Hinge Loss Minimization](https://mlsanity.com/paper/2012.00989/) (2020)
- [Semi-verified PAC Learning from the Crowd](https://mlsanity.com/paper/2106.07080/) (2021)
- [Attribute-Efficient PAC Learning of Low-Degree Polynomial Threshold Functions with Nasty Noise](https://mlsanity.com/paper/2306.00673/) (2023)
- [Online Robust Mean Estimation](https://mlsanity.com/paper/2310.15932/) (2023)

## Built on by (most cited first, 5 of 5)

- [The Power of Iterative Filtering for Supervised Learning with (Heavy) Contamination](https://mlsanity.com/paper/2505.20177/) (2025)
- [Attribute-Efficient PAC Learning of Sparse Halfspaces with Constant Malicious Noise Rate](https://mlsanity.com/paper/2505.21430/) (2025)
- [Efficient and Noise-Tolerant PAC Learning of Multiclass Linear Classifiers](https://mlsanity.com/paper/2605.18662/) (2026)
- [Towards Efficient Contrastive PAC Learning](https://mlsanity.com/paper/2502.15962/) (2025)
- [Sum-of-Squares Degree Barriers for the Reweighted-Hinge Method in Robust Halfspace Learning: A Christoffel-Function Characterization](https://mlsanity.com/paper/2606.17215/) (2026)

## 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.