[edit]
Provable Robustness of Adversarial Training for Learning Halfspaces with Noise
Proceedings of the 38th International Conference on Machine Learning, PMLR 139:13002-13011, 2021.
Abstract
We analyze the properties of adversarial training for learning adversarially robust halfspaces in the presence of agnostic label noise. Denoting OPTp,r as the best 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 classification error ˜O(√OPT2,r) for p=2, and ˜O(d1/4√OPT∞,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 non-convex sigmoidal loss, adversarial training yields halfspaces with an improved robust classification error of O(OPT2,r) for p=2, and O(d1/4OPT∞,r) when p=∞. To the best of our knowledge, this is the first work showing that adversarial training provably yields robust classifiers in the presence of noise.