Convergence of Adversarial Training in Overparametrized Neural Networks

Abstract

Neural networks are vulnerable to adversarial examples, i.e. inputs that are imperceptibly perturbed from natural data and yet incorrectly classified by the network. Adversarial training, a heuristic form of robust optimization that alternates between minimization and maximization steps, has proven to be among the most successful methods to train networks to be robust against a pre-defined family of perturbations. This paper provides a partial answer to the success of adversarial training, by showing that it converges to a network where the surrogate loss with respect to the the attack algorithm is within $\epsilon$ of the optimal robust loss. Then we show that the optimal robust loss is also close to zero, hence adversarial training finds a robust classifier. The analysis technique leverages recent work on the analysis of neural networks via Neural Tangent Kernel (NTK), combined with motivation from online-learning when the maximization is solved by a heuristic, and the expressiveness of the NTK kernel in the ${\ell }_{\infty }$-norm. In addition, we also prove that robust interpolation requires more model capacity, supporting the evidence that adversarial training requires wider networks.

arXiv commentNeurIPS 2019

References in corpus (35)

• ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Models
• Towards Deep Learning Models Resistant to Adversarial Attacks
• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• Obfuscated Gradients Give a False Sense of Security: Circumventing Defenses to Adversarial Examples
• A Convergence Theory for Deep Learning via Over-Parameterization
• Provable defenses against adversarial examples via the convex outer adversarial polytope
• Adversarially Robust Generalization Requires More Data
• Robust Physical-World Attacks on Deep Learning Models
• Characterizing Adversarial Subspaces Using Local Intrinsic Dimensionality
• Countering Adversarial Images using Input Transformations
• Gradient Descent Provably Optimizes Over-parameterized Neural Networks
• Efficient Neural Network Robustness Certification with General Activation Functions
• PixelDefend: Leveraging Generative Models to Understand and Defend against Adversarial Examples
• Defense-GAN: Protecting Classifiers Against Adversarial Attacks Using Generative Models
• Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
• Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks
• Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks
• Toward Deeper Understanding of Neural Networks: The Power of Initialization and a Dual View on Expressivity
• On the Convergence and Robustness of Adversarial Training
• Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks
• On the Power of Over-parametrization in Neural Networks with Quadratic Activation
• Optimal approximation of continuous functions by very deep ReLU networks
• A Convex Relaxation Barrier to Tight Robustness Verification of Neural Networks
• Adversarial examples from computational constraints
• Rademacher Complexity for Adversarially Robust Generalization
• Training verified learners with learned verifiers
• Adversarial Robustness May Be at Odds With Simplicity
• You Only Propagate Once: Accelerating Adversarial Training via Maximal Principle
• SGD Learns the Conjugate Kernel Class of the Network
• Small ReLU networks are powerful memorizers: a tight analysis of memorization capacity
• On the Inductive Bias of Neural Tangent Kernels
• Gram-Gauss-Newton Method: Learning Overparameterized Neural Networks for Regression Problems
• RANDOM MASK: Towards Robust Convolutional Neural Networks
• Intriguing properties of adversarial training at scale
• Learning in Non-convex Games with an Optimization Oracle

Cited by in corpus (28)

• A Theoretical Analysis of Deep Q-Learning
• Do Adversarially Robust ImageNet Models Transfer Better?
• A Review of Adversarial Attack and Defense for Classification Methods
• Smooth Adversarial Training
• Adversarially Robust Generalization Just Requires More Unlabeled Data
• Do Wider Neural Networks Really Help Adversarial Robustness?
• The Curious Case of Adversarially Robust Models: More Data Can Help, Double Descend, or Hurt Generalization
• Intriguing properties of adversarial training at scale
• Single-Timescale Actor-Critic Provably Finds Globally Optimal Policy
• Exploring Memorization in Adversarial Training
• Neural Temporal-Difference and Q-Learning Provably Converge to Global Optima
• On the Generalization Properties of Adversarial Training
• Robust Processing-In-Memory Neural Networks via Noise-Aware Normalization
• Risk-Sensitive Deep RL: Variance-Constrained Actor-Critic Provably Finds Globally Optimal Policy
• Fast Learning in Reproducing Kernel Krein Spaces via Signed Measures
• Provably Efficient Neural Estimation of Structural Equation Model: An Adversarial Approach
• Amata: An Annealing Mechanism for Adversarial Training Acceleration
• Towards Deep Learning Models Resistant to Large Perturbations
• Robust Sensible Adversarial Learning of Deep Neural Networks for Image Classification
• Optimal Gradient-based Algorithms for Non-concave Bandit Optimization
• Provable Regret Bounds for Deep Online Learning and Control
• Adversarial Robustness Guarantees for Random Deep Neural Networks
• Provable Robustness of Adversarial Training for Learning Halfspaces with Noise
• Robust Deep Learning as Optimal Control: Insights and Convergence Guarantees
• Robust Generalization of Quadratic Neural Networks via Function Identification
• A Law of Robustness for Weight-bounded Neural Networks
• Provably Training Overparameterized Neural Network Classifiers with Non-convex Constraints
• Going Beyond Linear RL: Sample Efficient Neural Function Approximation