# Attribute-Efficient Learning of Halfspaces with Malicious Noise: Near-Optimal Label Complexity and Noise Tolerance

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Jun 2020.

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

- [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 of Halfspaces with Constant Malicious Noise Rate](https://mlsanity.com/paper/2410.01186/) (2024)
- [Learning Constant-Depth Circuits in Malicious Noise Models](https://mlsanity.com/paper/2411.03570/) (2024)
- [Attribute-Efficient PAC Learning of Low-Degree Polynomial Threshold Functions with Nasty Noise](https://mlsanity.com/paper/2306.00673/) (2023)
- [Agnostic Learnability of Halfspaces via Logistic Loss](https://mlsanity.com/paper/2201.13419/) (2022)
- [Attribute-Efficient PAC Learning of Sparse Halfspaces with Constant Malicious Noise Rate](https://mlsanity.com/paper/2505.21430/) (2025)
- [Immunological Density Shapes Recovery Trajectories in Long COVID](https://mlsanity.com/paper/2601.07854/) (2026)
- [Robust Learning with Optimal Error](https://mlsanity.com/paper/2604.02555/) (2026)
- [Towards Efficient Contrastive PAC Learning](https://mlsanity.com/paper/2502.15962/) (2025)
- [Optimal Budgeted Adaptation of Large Language Models](https://mlsanity.com/paper/2602.00952/) (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)

This paper is concerned with computationally efficient learning of homogeneous sparse halfspaces in ℝd under noise. Though recent works have established attribute-efficient learning algorithms under various types of label noise (e.g. bounded noise), it remains an open question when and how s-sparse halfspaces can be efficiently learned under the challenging malicious noise model, where an adversary may corrupt both the unlabeled examples and the labels. We answer this question in the affirmative by designing a computationally efficient active learning algorithm with near-optimal label complexity of tildeObig(s log4 frac d ε big) and noise tolerance η = Omega(ε), where ε ∈ (0, 1) is the target error rate, under the assumption that the distribution over (uncorrupted) unlabeled examples is isotropic log-concave. Our algorithm can be straightforwardly tailored to the passive learning setting, and we show that the sample complexity is tildeObig(frac 1 ε s2 log5 d big) which also enjoys the attribute efficiency. Our main techniques include attribute-efficient paradigms for instance reweighting and for empirical risk minimization, and a new analysis of uniform concentration for unbounded data -- all of them crucially take the structure of the underlying halfspace into account.