Provable Robustness of Adversarial Training for Learning Halfspaces with Noise

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