  In adversarial machine learning, deep neural networks can fit the adversarial
examples on the training dataset but have poor generalization ability on the
test set. This phenomenon is called robust overfitting, and it can be observed
when adversarially training neural nets on common datasets, including SVHN,
CIFAR-10, CIFAR-100, and ImageNet. In this paper, we study the robust
overfitting issue of adversarial training by using tools from uniform
stability. One major challenge is that the outer function (as a maximization of
the inner function) is nonsmooth, so the standard technique (e.g., hardt et
al., 2016) cannot be applied. Our approach is to consider $\eta$-approximate
smoothness: we show that the outer function satisfies this modified smoothness
assumption with $\eta$ being a constant related to the adversarial perturbation
$\epsilon$. Based on this, we derive stability-based generalization bounds for
stochastic gradient descent (SGD) on the general class of $\eta$-approximate
smooth functions, which covers the adversarial loss. Our results suggest that
robust test accuracy decreases in $\epsilon$ when $T$ is large, with a speed
between $\Omega(\epsilon\sqrt{T})$ and $\mathcal{O}(\epsilon T)$. This
phenomenon is also observed in practice. Additionally, we show that a few
popular techniques for adversarial training (e.g., early stopping, cyclic
learning rate, and stochastic weight averaging) are stability-promoting in
theory.
