Over-parameterized Adversarial Training: An Analysis Overcoming the Curse of Dimensionality

By Yi Zhang, Orestis Plevrakis, Simon Shaolei Du, Xingguo Li, Zhao Song, Sanjeev Arora. 2020

56 citations recorded by the source corpus.

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 $d$, 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.

Subfields: Artificial Intelligence, Optimization & Training, Statistical Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Optimization & Training

In Statistical Learning Theory

Citations in the corpus

Feature Purification: How Adversarial Training Performs Robust Deep Learning (2020, background): “The works by [62, 64] focus on how adversarial training can be performed efficiently in the neural tangent kernel regime.”
Advances in adversarial attacks and defenses in computer vision: A survey (2021, background): “[362] extend their work for situations where the width of the network and its run time is polynomial in input dimension.”