# On the Power of Localized Perceptron for Label-Optimal Learning of Halfspaces with Adversarial Noise

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Dec 2020.

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

- [Sample-Optimal PAC Learning of Halfspaces with Malicious Noise](https://mlsanity.com/paper/2102.06247/) (2021)
- [Active Learning of General Halfspaces: Label Queries vs Membership Queries](https://mlsanity.com/paper/2501.00508/) (2024)
- [Efficient PAC Learning of Halfspaces with Constant Malicious Noise Rate](https://mlsanity.com/paper/2410.01186/) (2024)
- [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)
- [Metric-Fair Prompting: Treating Similar Samples Similarly](https://mlsanity.com/paper/2512.07608/) (2025)
- [Attribute-Efficient PAC Learning of Sparse Halfspaces with Constant Malicious Noise Rate](https://mlsanity.com/paper/2505.21430/) (2025)
- [On the Convergence of Loss and Uncertainty-based Active Learning Algorithms](https://mlsanity.com/paper/2312.13927/) (2023)
- [Towards Efficient Contrastive PAC Learning](https://mlsanity.com/paper/2502.15962/) (2025)
- [Robust Regression of General ReLUs with Queries](https://mlsanity.com/paper/2606.11130/) (2026)
- [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)

We study em online active learning of homogeneous halfspaces in ℝd with adversarial noise where the overall probability of a noisy label is constrained to be at most nu. Our main contribution is a Perceptron-like online active learning algorithm that runs in polynomial time, and under the conditions that the marginal distribution is isotropic log-concave and nu = Omega(ε), where ε ∈ (0, 1) is the target error rate, our algorithm PAC learns the underlying halfspace with near-optimal label complexity of tildeObig(d · polylog(frac1ε)big) and sample complexity of tildeObig(fracdε big). Prior to this work, existing online algorithms designed for tolerating the adversarial noise are subject to either label complexity polynomial in frac1ε, or suboptimal noise tolerance, or restrictive marginal distributions. With the additional prior knowledge that the underlying halfspace is s-sparse, we obtain attribute-efficient label complexity of tildeObig( s · polylog(d, frac1ε) big) and sample complexity of tildeObig(fracsε · polylog(d) big). As an immediate corollary, we show that under the agnostic model where no assumption is made on the noise rate nu, our active learner achieves an error rate of O(OPT) + ε with the same running time and label and sample complexity, where OPT is the best possible error rate achievable by any homogeneous halfspace.