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

arXiv: https://arxiv.org/abs/2002.06668 · HTML: https://mlsanity.com/paper/2002.06668/

## Key facts

- Cited by 36 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Feb 2020.

## Built on by (most cited first, 30 of 36)

- [Advances in adversarial attacks and defenses in computer vision: A survey](https://mlsanity.com/paper/2108.00401/) (2021)
- [Exploring Memorization in Adversarial Training](https://mlsanity.com/paper/2106.01606/) (2021)
- [Does Preprocessing Help Training Over-parameterized Neural Networks?](https://mlsanity.com/paper/2110.04622/) (2021)
- [A Fast Optimization View: Reformulating Single Layer Attention in LLM Based on Tensor and SVM Trick, and Solving It in Matrix Multiplication Time](https://mlsanity.com/paper/2309.07418/) (2023)
- [Bypass Exponential Time Preprocessing: Fast Neural Network Training via Weight-Data Correlation Preprocessing](https://mlsanity.com/paper/2211.14227/) (2022)
- [How to Protect Copyright Data in Optimization of Large Language Models?](https://mlsanity.com/paper/2308.12247/) (2023)
- [A Sublinear Adversarial Training Algorithm](https://mlsanity.com/paper/2208.05395/) (2022)
- [Robustness in deep learning: The good (width), the bad (depth), and the ugly (initialization)](https://mlsanity.com/paper/2209.07263/) (2022)
- [Federated Adversarial Learning: A Framework with Convergence Analysis](https://mlsanity.com/paper/2208.03635/) (2022)
- [FL-NTK: A Neural Tangent Kernel-based Framework for Federated Learning Convergence Analysis](https://mlsanity.com/paper/2105.05001/) (2021)
- [Benign Overfitting in Adversarially Robust Linear Classification](https://mlsanity.com/paper/2112.15250/) (2021)
- [Adversarial robustness of sparse local Lipschitz predictors](https://mlsanity.com/paper/2202.13216/) (2022)
- [Efficient SGD Neural Network Training via Sublinear Activated Neuron Identification](https://mlsanity.com/paper/2307.06565/) (2023)
- [Provable Robustness of Adversarial Training for Learning Halfspaces with Noise](https://mlsanity.com/paper/2104.09437/) (2021)
- [Theoretical Analysis of Robust Overfitting for Wide DNNs: An NTK Approach](https://mlsanity.com/paper/2310.06112/) (2023)
- [An Automatic Learning Rate Schedule Algorithm for Achieving Faster Convergence and Steeper Descent](https://mlsanity.com/paper/2310.11291/) (2023)
- [Local Convergence of Approximate Newton Method for Two Layer Nonlinear Regression](https://mlsanity.com/paper/2311.15390/) (2023)
- [Provable Regret Bounds for Deep Online Learning and Control](https://mlsanity.com/paper/2110.07807/) (2021)
- [Convergence of Two-Layer Regression with Nonlinear Units](https://mlsanity.com/paper/2308.08358/) (2023)
- [Robust NAS under adversarial training: benchmark, theory, and beyond](https://mlsanity.com/paper/2403.13134/) (2024)
- [Adversarial for Good? How the Adversarial ML Community's Values Impede Socially Beneficial Uses of Attacks](https://mlsanity.com/paper/2107.10302/) (2021)
- [On the Convergence of Certified Robust Training with Interval Bound Propagation](https://mlsanity.com/paper/2203.08961/) (2022)
- [Adversarial Training for Gradient Descent: Analysis Through its Continuous-time Approximation](https://mlsanity.com/paper/2105.08037/) (2021)
- [Unlabeled Data Help: Minimax Analysis and Adversarial Robustness](https://mlsanity.com/paper/2202.06996/) (2022)
- [A direct proof of a unified law of robustness for Bregman divergence losses](https://mlsanity.com/paper/2405.16639/) (2024)
- [Generating Less Certain Adversarial Examples Improves Robust Generalization](https://mlsanity.com/paper/2310.04539/) (2023)
- [A Law of Robustness for Weight-bounded Neural Networks](https://mlsanity.com/paper/2102.08093/) (2021)
- [Understanding Overfitting in Adversarial Training via Kernel Regression](https://mlsanity.com/paper/2304.06326/) (2023)
- [Diffusion-based Cumulative Adversarial Purification for Vision Language Models](https://mlsanity.com/paper/2506.03933/) (2025)
- [Finding Dynamics Preserving Adversarial Winning Tickets](https://mlsanity.com/paper/2202.06488/) (2022)

## Abstract (arXiv)

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 exponential in input dimension d, and with an unnatural activation function. Our work proves convergence to low robust training loss for 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.