Over-parameterized Adversarial Training: An Analysis Overcoming the Curse of Dimensionality
arXiv:2002.06668
Abstract
Adversarial training is a popular method to give neural nets robustness against adversarial perturbations. In practice adversarial training leads to low robust training loss. However, a rigorous explanation for why this happens under natural conditions is still missing. Recently a convergence theory for standard (non-adversarial) supervised training was developed by various groups for {\em very overparametrized} nets. It is unclear how to extend these results to adversarial training because of the min-max objective. Recently, a first step towards this direction was made by Gao et al. using tools from online learning, but they require the width of the net to be \emph{exponential} in input dimension , and with an unnatural activation function. Our work proves convergence to low robust training loss for \emph{polynomial} width instead of exponential, under natural assumptions and with the ReLU activation. Key element of our proof is showing that ReLU networks near initialization can approximate the step function, which may be of independent interest.
References in corpus (8)
- 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
- Countering Adversarial Images using Input Transformations
- Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data
- Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks
- Quadratic Suffices for Over-parametrization via Matrix Chernoff Bound