mlsanityData to 7 Oct 2026

Provable Robustness of Adversarial Training for Learning Halfspaces with Noise

arXiv 2104.09437 ↗First posted 19 Apr 2021cs.LG cs.CR math.OCcited by 10

Not on the map. Why?

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.

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

Builds on

31 of 51 references.

References · 31

  1. 2014Explaining and Harnessing Adversarial Examplescited by 7,287
  2. 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,326
  3. 2013Intriguing properties of neural networkscited by 5,114
  4. 2016Towards Evaluating the Robustness of Neural Networkscited by 2,976
  5. 2019Theoretically Principled Trade-off between Robustness and Accuracycited by 1,510
  6. 2019Certified Adversarial Robustness via Randomized Smoothingcited by 1,324
  7. 2019Adversarial Examples Are Not Bugs, They Are Featurescited by 950
  8. 2016Adversarial Machine Learning at Scalecited by 934
  9. 2018Robustness May Be at Odds with Accuracycited by 873
  10. 2017Ensemble Adversarial Training: Attacks and Defensescited by 833
  11. 2015Distillation as a Defense to Adversarial Perturbations against Deep Neural Networkscited by 675
  12. 2017Provable defenses against adversarial examples via the convex outer adversarial polytopecited by 564
19 more
  1. 2018Certified Robustness to Adversarial Examples with Differential Privacycited by 462
  2. 2017Wild Patterns: Ten Years After the Rise of Adversarial Machine Learningcited by 411
  3. 2019Provably Robust Deep Learning via Adversarially Trained Smoothed Classifierscited by 328
  4. 2020Do Adversarially Robust ImageNet Models Transfer Better?cited by 315
  5. 2018Certified Defenses against Adversarial Examplescited by 305
  6. 2020Understanding and Mitigating the Tradeoff Between Robustness and Accuracycited by 148
  7. 2018Rademacher Complexity for Adversarially Robust Generalizationcited by 132
  8. 2020Precise Tradeoffs in Adversarial Training for Linear Regressioncited by 76
  9. 2019Convergence of Adversarial Training in Overparametrized Neural Networkscited by 58
  10. 2015Complexity Theoretic Limitations on Learning Halfspacescited by 50
  11. 2020Learning Halfspaces with Massart Noise Under Structured Distributionscited by 45
  12. 2020Over-parameterized Adversarial Training: An Analysis Overcoming the Curse of Dimensionalitycited by 36
  13. 2020Non-Convex SGD Learns Halfspaces with Adversarial Label Noisecited by 30
  14. 2018PAC-learning in the presence of evasion adversariescited by 23
  15. 2020Efficiently Learning Adversarially Robust Halfspaces with Noisecited by 22
  16. 2020The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noisecited by 15
  17. 2020Agnostic Learning of Halfspaces with Gradient Descent via Soft Marginscited by 14
  18. 2019Inductive Bias of Gradient Descent based Adversarial Training on Separable Datacited by 12
  19. 2019Convergence and Margin of Adversarial Training on Separable Datacited by 5

Built on by

Cited by year

Citing papers per year: 2021: 3; 2022: 3; 2023: 0; 2024: 2; 2025: 2.

10 papers.

  1. 2022Learning a Single Neuron with Adversarial Label Noise via Gradient Descentcited by 20
  2. 2021Self-training Converts Weak Learners to Strong Learners in Mixture Modelscited by 19
  3. 2021Interpolation can hurt robust generalization even when there is no noisecited by 15
  4. 2021Benign Overfitting in Adversarially Robust Linear Classificationcited by 11
  5. 2024The Surprising Harmfulness of Benign Overfitting for Adversarial Robustnesscited by 7
  6. 2024Adversarial Training: A Surveycited by 6
  7. 2022On the Convergence of Certified Robust Training with Interval Bound Propagationcited by 5
  8. 2022Adversarial Attack and Defense for Non-Parametric Two-Sample Testscited by 2
  9. 2025Towards Better Generalization via Distributional Input Projection Networkcited by 1
  10. 2025Sample-wise Adaptive Weighting for Transfer Consistency in Adversarial Distillationcited by 0