  Similar to surprising performance in the standard deep learning, deep nets
trained by adversarial training also generalize well for $\textit{unseen clean
data (natural data)}$. However, despite adversarial training can achieve low
robust training error, there exists a significant $\textit{robust
generalization gap}$. We call this phenomenon the $\textit{Clean Generalization
and Robust Overfitting (CGRO)}$. In this work, we study the CGRO phenomenon in
adversarial training from two views: $\textit{representation complexity}$ and
$\textit{training dynamics}$. Specifically, we consider a binary classification
setting with $N$ separated training data points. $\textit{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. $\textit{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. $\textit{Besides}$, we also
empirically verify our theoretical analysis by experiments in real-image
recognition datasets.
