On the Clean Generalization and Robust Overfitting in Adversarial Training from Two Theoretical Views: Representation Complexity and Training Dynamics
This work addresses the robust generalization gap in adversarial training for deep learning, which is an incremental theoretical analysis with practical implications for improving model security.
The paper investigates the phenomenon of Clean Generalization and Robust Overfitting (CGRO) in adversarial training, where models generalize well on clean data but poorly on adversarial examples, proving that ReLU nets with O(ND) extra parameters can achieve this via robust memorization, while robust classifiers require exponential complexity in worst cases, and showing a three-stage phase transition in training dynamics that leads to CGRO, with empirical validation on real-image datasets.
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 $\operatorname{poly}(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.