# On the Clean Generalization and Robust Overfitting in Adversarial Training from Two Theoretical Views: Representation Complexity and Training Dynamics

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 51 of its 62 references that are in the map.
- First posted on arXiv 2 Jun 2023.

## Builds on (most cited first, 30 of 51)

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Segment Anything](https://mlsanity.com/paper/2304.02643/) (2023)
- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Wide Residual Networks](https://mlsanity.com/paper/1605.07146/) (2016)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [Theoretically Principled Trade-off between Robustness and Accuracy](https://mlsanity.com/paper/1901.08573/) (2019)
- [Reconciling modern machine learning practice and the bias-variance trade-off](https://mlsanity.com/paper/1812.11118/) (2018)
- [Robustness May Be at Odds with Accuracy](https://mlsanity.com/paper/1805.12152/) (2018)
- [A Convergence Theory for Deep Learning via Over-Parameterization](https://mlsanity.com/paper/1811.03962/) (2018)
- [Fast is better than free: Revisiting adversarial training](https://mlsanity.com/paper/2001.03994/) (2020)
- [Evasion Attacks against Machine Learning at Test Time](https://mlsanity.com/paper/1708.06131/) (2017)
- [Gradient Descent Provably Optimizes Over-parameterized Neural Networks](https://mlsanity.com/paper/1810.02054/) (2018)
- [Adversarial Training for Free!](https://mlsanity.com/paper/1904.12843/) (2019)
- [Error bounds for approximations with deep ReLU networks](https://mlsanity.com/paper/1610.01145/) (2016)
- [Gradient Descent Finds Global Minima of Deep Neural Networks](https://mlsanity.com/paper/1811.03804/) (2018)
- [Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks](https://mlsanity.com/paper/1901.08584/) (2019)
- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [Overfitting in adversarially robust deep learning](https://mlsanity.com/paper/2002.11569/) (2020)
- [On the Number of Linear Regions of Deep Neural Networks](https://mlsanity.com/paper/1402.1869/) (2014)
- [Adversarially Robust Generalization Requires More Data](https://mlsanity.com/paper/1804.11285/) (2018)
- [Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks](https://mlsanity.com/paper/1703.02930/) (2017)
- [Towards Understanding Ensemble, Knowledge Distillation and Self-Distillation in Deep Learning](https://mlsanity.com/paper/2012.09816/) (2020)
- [Improving Robustness using Generated Data](https://mlsanity.com/paper/2110.09468/) (2021)
- [A Universal Law of Robustness via Isoperimetry](https://mlsanity.com/paper/2105.12806/) (2021)
- [Adversarial Training Can Hurt Generalization](https://mlsanity.com/paper/1906.06032/) (2019)

## Built on by (most cited first, 5 of 5)

- [Provable Benefit of Cutout and CutMix for Feature Learning](https://mlsanity.com/paper/2410.23672/) (2024)
- [Is Certifying ℓp Robustness Still Worthwhile?](https://mlsanity.com/paper/2310.09361/) (2023)
- [Can overfitted deep neural networks in adversarial training generalize? -- An approximation viewpoint](https://mlsanity.com/paper/2401.13624/) (2024)
- [Does Order Matter : Connecting The Law of Robustness to Robust Generalization](https://mlsanity.com/paper/2602.20971/) (2026)
- [Sample-wise Adaptive Weighting for Transfer Consistency in Adversarial Distillation](https://mlsanity.com/paper/2512.10275/) (2025)

## Abstract (arXiv)

Similar to surprising performance in the standard deep learning, deep nets trained by adversarial training also generalize well for unseen clean data (natural data). However, despite adversarial training can achieve low robust training error, there exists a significant robust generalization gap. We call this phenomenon the Clean Generalization and Robust Overfitting (CGRO). In this work, we study the CGRO phenomenon in adversarial training from two views: representation complexity and training dynamics. Specifically, we consider a binary classification setting with N separated training data points. First, we prove that, based on the assumption that we assume there is operatornamepoly(D)-size clean classifier (where D is the data dimension), ReLU net with only O(N D) extra parameters is able to leverages robust memorization to achieve the CGRO, while robust classifier still requires exponential representation complexity in worst case. Next, we focus on a structured-data case to analyze training dynamics, where we train a two-layer convolutional network with O(N D) width against adversarial perturbation. We then show that a three-stage phase transition occurs during learning process and the network provably converges to robust memorization regime, which thereby results in the CGRO. Besides, we also empirically verify our theoretical analysis by experiments in real-image recognition datasets.