# Provable Robustness of Adversarial Training for Learning Halfspaces with Noise

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 51 references that are in the map.
- First posted on arXiv 19 Apr 2021.

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

- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Towards Evaluating the Robustness of Neural Networks](https://mlsanity.com/paper/1608.04644/) (2016)
- [Theoretically Principled Trade-off between Robustness and Accuracy](https://mlsanity.com/paper/1901.08573/) (2019)
- [Certified Adversarial Robustness via Randomized Smoothing](https://mlsanity.com/paper/1902.02918/) (2019)
- [Adversarial Examples Are Not Bugs, They Are Features](https://mlsanity.com/paper/1905.02175/) (2019)
- [Adversarial Machine Learning at Scale](https://mlsanity.com/paper/1611.01236/) (2016)
- [Robustness May Be at Odds with Accuracy](https://mlsanity.com/paper/1805.12152/) (2018)
- [Ensemble Adversarial Training: Attacks and Defenses](https://mlsanity.com/paper/1705.07204/) (2017)
- [Distillation as a Defense to Adversarial Perturbations against Deep Neural Networks](https://mlsanity.com/paper/1511.04508/) (2015)
- [Provable defenses against adversarial examples via the convex outer adversarial polytope](https://mlsanity.com/paper/1711.00851/) (2017)
- [Certified Robustness to Adversarial Examples with Differential Privacy](https://mlsanity.com/paper/1802.03471/) (2018)
- [Wild Patterns: Ten Years After the Rise of Adversarial Machine Learning](https://mlsanity.com/paper/1712.03141/) (2017)
- [Provably Robust Deep Learning via Adversarially Trained Smoothed Classifiers](https://mlsanity.com/paper/1906.04584/) (2019)
- [Do Adversarially Robust ImageNet Models Transfer Better?](https://mlsanity.com/paper/2007.08489/) (2020)
- [Certified Defenses against Adversarial Examples](https://mlsanity.com/paper/1801.09344/) (2018)
- [Understanding and Mitigating the Tradeoff Between Robustness and Accuracy](https://mlsanity.com/paper/2002.10716/) (2020)
- [Rademacher Complexity for Adversarially Robust Generalization](https://mlsanity.com/paper/1810.11914/) (2018)
- [Precise Tradeoffs in Adversarial Training for Linear Regression](https://mlsanity.com/paper/2002.10477/) (2020)
- [Convergence of Adversarial Training in Overparametrized Neural Networks](https://mlsanity.com/paper/1906.07916/) (2019)
- [Complexity Theoretic Limitations on Learning Halfspaces](https://mlsanity.com/paper/1505.05800/) (2015)
- [Learning Halfspaces with Massart Noise Under Structured Distributions](https://mlsanity.com/paper/2002.05632/) (2020)
- [Over-parameterized Adversarial Training: An Analysis Overcoming the Curse of Dimensionality](https://mlsanity.com/paper/2002.06668/) (2020)
- [Non-Convex SGD Learns Halfspaces with Adversarial Label Noise](https://mlsanity.com/paper/2006.06742/) (2020)
- [PAC-learning in the presence of evasion adversaries](https://mlsanity.com/paper/1806.01471/) (2018)
- [Efficiently Learning Adversarially Robust Halfspaces with Noise](https://mlsanity.com/paper/2005.07652/) (2020)
- [The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise](https://mlsanity.com/paper/2007.15220/) (2020)
- [Agnostic Learning of Halfspaces with Gradient Descent via Soft Margins](https://mlsanity.com/paper/2010.00539/) (2020)
- [Inductive Bias of Gradient Descent based Adversarial Training on Separable Data](https://mlsanity.com/paper/1906.02931/) (2019)

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

- [Learning a Single Neuron with Adversarial Label Noise via Gradient Descent](https://mlsanity.com/paper/2206.08918/) (2022)
- [Self-training Converts Weak Learners to Strong Learners in Mixture Models](https://mlsanity.com/paper/2106.13805/) (2021)
- [Interpolation can hurt robust generalization even when there is no noise](https://mlsanity.com/paper/2108.02883/) (2021)
- [Benign Overfitting in Adversarially Robust Linear Classification](https://mlsanity.com/paper/2112.15250/) (2021)
- [The Surprising Harmfulness of Benign Overfitting for Adversarial Robustness](https://mlsanity.com/paper/2401.12236/) (2024)
- [Adversarial Training: A Survey](https://mlsanity.com/paper/2410.15042/) (2024)
- [On the Convergence of Certified Robust Training with Interval Bound Propagation](https://mlsanity.com/paper/2203.08961/) (2022)
- [Adversarial Attack and Defense for Non-Parametric Two-Sample Tests](https://mlsanity.com/paper/2202.03077/) (2022)
- [Towards Better Generalization via Distributional Input Projection Network](https://mlsanity.com/paper/2506.04690/) (2025)
- [Sample-wise Adaptive Weighting for Transfer Consistency in Adversarial Distillation](https://mlsanity.com/paper/2512.10275/) (2025)

## Abstract (arXiv)

We analyze the properties of adversarial training for learning adversarially robust halfspaces in the presence of agnostic label noise. Denoting mathsfOPTp,r as the best robust classification error achieved by a halfspace that is robust to perturbations of ℓp balls of radius r, we show that adversarial training on the standard binary cross-entropy loss yields adversarially robust halfspaces up to (robust) classification error tilde O(√mathsfOPT2,r) for p=2, and tilde O(d1/4 √mathsfOPT∞, r + d1/2 mathsfOPT∞,r) when p=∞. Our results hold for distributions satisfying anti-concentration properties enjoyed by log-concave isotropic distributions among others. We additionally show that if one instead uses a nonconvex sigmoidal loss, adversarial training yields halfspaces with an improved robust classification error of O(mathsfOPT2,r) for p=2, and O(d1/4mathsfOPT∞, r) when p=∞. To the best of our knowledge, this is the first work to show that adversarial training provably yields robust classifiers in the presence of noise.