# The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Jul 2020.

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

- [Cross-Entropy Loss Functions: Theoretical Analysis and Applications](https://mlsanity.com/paper/2304.07288/) (2023)
- [Calibration and Consistency of Adversarial Surrogate Losses](https://mlsanity.com/paper/2104.09658/) (2021)
- [Benign Overfitting in Adversarially Robust Linear Classification](https://mlsanity.com/paper/2112.15250/) (2021)
- [Provable Robustness of Adversarial Training for Learning Halfspaces with Noise](https://mlsanity.com/paper/2104.09437/) (2021)
- [Towards the Worst-case Robustness of Large Language Models](https://mlsanity.com/paper/2501.19040/) (2025)
- [Robust and Sparse Estimation of Linear Regression Coefficients with Heavy-tailed Noises and Covariates](https://mlsanity.com/paper/2206.07594/) (2022)
- [Robust Empirical Risk Minimization with Tolerance](https://mlsanity.com/paper/2210.00635/) (2022)
- [On the Computability of Robust PAC Learning](https://mlsanity.com/paper/2406.10161/) (2024)
- [Adversarial for Good? How the Adversarial ML Community's Values Impede Socially Beneficial Uses of Attacks](https://mlsanity.com/paper/2107.10302/) (2021)
- [Outlier Robust and Sparse Estimation of Linear Regression Coefficients](https://mlsanity.com/paper/2208.11592/) (2022)
- [Algorithms with More Granular Differential Privacy Guarantees](https://mlsanity.com/paper/2209.04053/) (2022)
- [Double-Adversarial Activation Anomaly Detection: Adversarial Autoencoders are Anomaly Generators](https://mlsanity.com/paper/2101.04645/) (2021)
- [Robust learning of halfspaces under log-concave marginals](https://mlsanity.com/paper/2505.13708/) (2025)
- [When are Local Queries Useful for Robust Learning?](https://mlsanity.com/paper/2210.06089/) (2022)
- [mathscrH-Consistency Estimation Error of Surrogate Loss Minimizers](https://mlsanity.com/paper/2205.08017/) (2022)

## Abstract (arXiv)

We study the computational complexity of adversarially robust proper learning of halfspaces in the distribution-independent agnostic PAC model, with a focus on Lp perturbations. We give a computationally efficient learning algorithm and a nearly matching computational hardness result for this problem. An interesting implication of our findings is that the L∞ perturbations case is provably computationally harder than the case 2 ≤ p < ∞.