Provable Robustness of Adversarial Training for Learning Halfspaces with Noise

Abstract

We analyze the properties of adversarial training for learning adversarially robust halfspaces in the presence of agnostic label noise. Denoting ${\mathsf{OPT}}_{p,r}$ as the best robust classification error achieved by a halfspace that is robust to perturbations of ${\ell }_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}(\sqrt{{\mathsf{OPT}}_{2,r}})$ for $p=2$, and $\tilde{O}(d^{1/4}\sqrt{{\mathsf{OPT}}_{\infty ,r}}+d^{1/2}{\mathsf{OPT}}_{\infty ,r})$ when $p=\infty$. 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({\mathsf{OPT}}_{2,r})$ for $p=2$, and $O(d^{1/4}{\mathsf{OPT}}_{\infty ,r})$ when $p=\infty$. 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.

arXiv comment42 pages, 2 figures

References in corpus (8)

• Wild Patterns: Ten Years After the Rise of Adversarial Machine Learning
• Provable defenses against adversarial examples via the convex outer adversarial polytope
• Certified Adversarial Robustness via Randomized Smoothing
• Adversarial Machine Learning at Scale
• On the Convergence and Robustness of Adversarial Training
• Convergence of Adversarial Training in Overparametrized Neural Networks
• Convergence and Margin of Adversarial Training on Separable Data
• Agnostic Learning of Halfspaces with Gradient Descent via Soft Margins

Cited by in corpus (1)

• Interpolation can hurt robust generalization even when there is no noise