Provable Robustness of Adversarial Training for Learning Halfspaces with\n Noise

2021/04/19 by Difan Zou, Zou, Difan, Spencer Frei +3 · 2 citations
Computer Science · Engineering · #Adversarial Robustness in Machine Learning #Fault Detection and Control Systems

paper · pdf · doi:10.48550/arxiv.2104.09437

Abstract

We analyze the properties of adversarial training for learning adversarially\nrobust halfspaces in the presence of agnostic label noise. Denoting\n\OPT_p,r as the best robust classification error achieved by a\nhalfspace that is robust to perturbations of \ℓ_p balls of radius r, we\nshow that adversarial training on the standard binary cross-entropy loss yields\nadversarially robust halfspaces up to (robust) classification error nO(\√\OPT_2,r) for p=2, and O(d^1/4\n\√\OPT_{\∞, r} + d^1/2 \OPT_\∞,r) when\np=\∞. Our results hold for distributions satisfying anti-concentration\nproperties enjoyed by log-concave isotropic distributions among others. We\nadditionally show that if one instead uses a nonconvex sigmoidal loss,\nadversarial training yields halfspaces with an improved robust classification\nerror of O(\OPT_2,r) for p=2, and O(d^1/4\OPT_\∞,\nr) when p=\∞. To the best of our knowledge, this is the first work to\nshow that adversarial training provably yields robust classifiers in the\npresence of noise.\n

Citations

• The perceptron: A probabilistic model for information storage and organization in the brain.
• Certified Adversarial Robustness via Randomized Smoothing

Cited by

• Sample-wise Adaptive Weighting for Transfer Consistency in Adversarial Distillation
• Interpolation can hurt robust generalization even when there is no noise

Related

• Efficiently Learning Adversarially Robust Halfspaces with Noise
• On the Power of Localized Perceptron for Label-Optimal Learning of Halfspaces with Adversarial Noise
• The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise
• Attribute-Efficient Learning of Halfspaces with Malicious Noise: Near-Optimal Label Complexity and Noise Tolerance
• An Efficient Tester-Learner for Halfspaces