Convergence and Margin of Adversarial Training on Separable Data

Abstract

Adversarial training is a technique for training robust machine learning models. To encourage robustness, it iteratively computes adversarial examples for the model, and then re-trains on these examples via some update rule. This work analyzes the performance of adversarial training on linearly separable data, and provides bounds on the number of iterations required for large margin. We show that when the update rule is given by an arbitrary empirical risk minimizer, adversarial training may require exponentially many iterations to obtain large margin. However, if gradient or stochastic gradient update rules are used, only polynomially many iterations are required to find a large-margin separator. By contrast, without the use of adversarial examples, gradient methods may require exponentially many iterations to achieve large margin. Our results are derived by showing that adversarial training with gradient updates minimizes a robust version of the empirical risk at a $\mathcal{O}(\ln (t{)}^2/t)$ rate, despite non-smoothness. We corroborate our theory empirically.

References in corpus (19)

• Intriguing properties of neural networks
• Ensemble Adversarial Training: Attacks and Defenses
• Transferability in Machine Learning: from Phenomena to Black-Box Attacks using Adversarial Samples
• Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization
• Adversarially Robust Generalization Requires More Data
• Understanding Adversarial Training: Increasing Local Stability of Neural Nets through Robust Optimization
• Robustness May Be at Odds with Accuracy
• Certifying Some Distributional Robustness with Principled Adversarial Training
• Adversarial Perturbations Against Deep Neural Networks for Malware Classification
• Robustness and Regularization of Support Vector Machines
• Defense-GAN: Protecting Classifiers Against Adversarial Attacks Using Generative Models
• Contextual Bandit Algorithms with Supervised Learning Guarantees
• Characterizing Implicit Bias in Terms of Optimization Geometry
• Adversarial Examples Are a Natural Consequence of Test Error in Noise
• Adversarial examples from computational constraints
• The Robust Manifold Defense: Adversarial Training using Generative Models
• Benchmarking Neural Network Robustness to Common Corruptions and Surface Variations
• Fast Feature Fool: A data independent approach to universal adversarial perturbations
• Risk and parameter convergence of logistic regression

Cited by in corpus (8)

• PDA: Progressive Data Augmentation for General Robustness of Deep Neural Networks
• Inductive Bias of Gradient Descent based Adversarial Training on Separable Data
• Robust Large-Margin Learning in Hyperbolic Space
• Adversarial Robustness of Supervised Sparse Coding
• Gradient descent follows the regularization path for general losses
• Asymptotic Behavior of Adversarial Training in Binary Classification
• Provable Robustness of Adversarial Training for Learning Halfspaces with Noise
• Recent Advances in Large Margin Learning