Stability Analysis and Generalization Bounds of Adversarial Training
Authors: Jiancong Xiao
Yanbo Fan
Ruoyu Sun
Jue Wang
Zhi-Quan Luo
Venue: NeurIPS 2022 Accept (2022)
Keywords: Generalization
Adversarial Training
Uniform Stability

Abstract: 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 (\emph{e.g.,} early stopping, cyclic learning rate, and stochastic weight averaging) are stability-promoting in theory.

Stability Analysis and Generalization Bounds of Adversarial Training
Jiancong Xiao!.*, Yanbo Fan?.t, Ruoyu Sun 1.3.t, Jue Wang", Zhi-Quan Luo 4.3
'The Chinese University of Hong Kong. Shenzhen; Tencent Al Lab; SShnnzenn Research Institute of Big Data jiancongxiaoollnke cuhk. en, fanyanbo01240gmail com, sunruoyu@cuhk, edu, en, arphid@gmail com, luozq@cuhk edu, cn
Abstract
In adversarial machine learning, deep neural networks can fit the adversarial ex- amples the training dataset but have poor generalization ability the test set. This phenomenon is called robust overfitting, and it can be observed when adver- sarially training neural CIFAR-100, and ImageNet. In this paper, we study the robust overfitting issue 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, the standard technique (e.g., (Hardt al. 2016)) cannot be applied. Our ap- proach is to consider 7-approximate smoothness: we show that the outer function satisfies this modified smoothness assumption with 1) being a constant related the adversarial perturbation Based on this, we derive stability-base gener- alization bounds for stochastic gradient descent (SGD) on the general class of 7/approximmae smooth functions, which covers the adversarial loss. Our results suggest that robust test accuracy decreases in when is large, with speed between (cv/T) and (cT)). This phenomenon also observed in practice. Ad- ditionally, we show that few popular techniques for adversarial training (e.g. early stopping, cyclic learning rate, and stochastic weight averaging) are stability- promoting in theory.
common datasets, including SVHN, CIFAR-10,
Introduction
Deep neural networks (DNNs) (Krizhevsky al. 2012 Hochreiter and Schmidhuber 1997) have become successful in many machine learning tasks and rarely suffered overfitting issues (Zhang al.) 2021). A neural network model can be trained to achieve zero train- ing error and generalize well to the unseen data. While in the setting of adversarial training, robust overfitting is dominant issue (Rice) al. 2020). Specifically, robust overfitting characterizes a train- ing procedure shown in Fig. [ After a particular epoch, the robust test accuracy (black line) starts decrease, but the robust train- ing accuracy (blue line) is still increasing. This phenomenon can be observed in the experiments on common datasets, e.g., SVHN CIFAR-10. 10, CIFAR- 100, and ImageNet. Recent works (Gowal et al. 2020 Rebuffi et al., 2021) mitigated the overfitting issue using reg- ularization techniques such as stochastic weight averaging (SWA)
0.9
0.6
TraFfAc:
03
Text Aaber
50
1:30
260
spochs
Figure 1: Experiments of ad- versarial training on CIFAR-
10.
"This work is done when Jiancong Xiao a research intern at Tencent AI Lab, China. i "oorrsppndiigg Authors.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

and early stopping, but it still has large generalization gap. Therefore, it is essential to study this issue from a theoretical perspective. In this paper, we study the robust overfitting issue of adversarial training by using tools from uniform stability.
Uniform stability analysis (Bousquet and Elisseefi 2002) in learning problems has been intro- duced to measure generalization gap instead of uniform convergence analysis such as classical VC- dimension (Vapnik and Chervonenkis 2015) and Rademacher complexity (Bartlett and Mendelson 2002). Generalization gap can be bounded in terms of uniform argument stability (UAS). Formally, UAS is the gap between the output parameters 0 of running an algorithm on two datasets S and S' differ in at most one sample, denoted as 5(S, S = [[((S) - ((S")l I|. In standard training prob- lem with n training samples, assuming that the loss function convex, L-Lipschitz and B-gradient Lipschitz, running stochastic gradient descent (SGD) with step size a S 1/3 for ' steps, the UAS bounded by ([LTT/n) (Hardt et al., 2016). Since the generalization gap is controlled by the number of samples n, this bound (at least partially) explains the good generalization of a standard training problem. Beyond (Hardt et al.) 2016). BBassily et al.] (2020) considered the case that the loss function is non-smooth. Without the 3-gradient Lipschitz assumption, they showed that the UAS is bounded by O(LaVT + LaT/n) and provided a lower bound to show that the additional term TL is unavoidable. In adversarial settings, two works have discussed the stability of adversarial training to our knowledge.
Firstly, Farnia and Ozdaglar (202T) considered the stability of minimax problems. Their work in- cludes discussion on an algorithm called GDmax (gradient descent on the maximization of the inner problem), which can be viewed as general form of adversarial training. It provides the stabil- ity of GDmax when the inner problem is further assumed to be strongly concave. Under the strongly concave assumption, the outer function is smooth. Then, the generalization bound O ((LaT//i (n) can be applied in this case. However, the inner problem is not strongly concave in practice. The bound O (LaT//n) /n) does not match the poor generalization of adversarial training observed in practice.
Another stability analysis of adversarial training is the work of (Xing et al. 2021a). Before they propose their algorithm, they use the stability bound O(LavT + LoT/n) (Bassily al. 2020) to characterize the issue of robust generalization. However, the bound is e-mdependent. Let us
Consider two cases, e + and e is large (e.g., 16/255). In the first case, adversarial training is very close to standard training and has good generalization ability. In the second case, robust generalization very poor. The bound is the same these two different cases. Therefore, it cannot provide an interpretation of robust generalization.
In summary, existing stability-ban bbsse generalization bounds (Hardt al. 2016 Bassily et al. 2020 have limited interpretation on robust generalization. In this paper, we provide a new stability analy- sis of adversarial training using the notion of n-approximate smoothness. We first show that, under the same assumptions as (Hardt et al. 2016 Xing et al. (221aa), even though the outer function (ad- versarial loss) is non- non-smooth, is a-apprxximately smooth (see Definition(4.1I. where 17 is constant linearly depending on the gradient Lipschitz of the inner function and the perturbation intensity e. Then, we derive stability- -aased generalization bounds (Thm. 5. to 5.4) for stochastic gradient de- scent (SGD) on this general class of a-approximate smooth functions, which covers the adversarial loss. Our main result can be summarized in the following equation. Running SGD on adversarial loss for T steps with step size a < 1/B, the excess risk, which is the sum of generalization error and optimization error, satisfies
for standard training
additional
2L n
D2 Tox
Excess Risk S Eyen + Eopt S LnTTa
L.a.
(1.1)
for adverssuial training
The excess risk of adversarial training has an additional term LnT'a. We also provide a lower bound of UAS of running SGD on adversarial loss. Our results suggest that robust test accuracy decreases in c when T is large, with speed between Q(evTT) and OCTT). This phenomenon is also observed in practice. It provides an understanding of robust overfitting from the perspective of uniform stability. Additionally, we show that a few popular techniques for adversarial training (e.g., early stopping, cyclic learning rate, and stochastic weight averaging) are stability-rromotingg in theory and also empirically improve adversarial training. Experiments on SVHN CIFAR-10, CIFAR- 100, and ImageNet confirm our results. Our contributions are listed as follows:

---

Main results: we derive stability- suaee generalization bounds for adversarial training us- ing the notion of n-approximate smoothness. Based on this, we provide an analysis to understand robust overfitting.
We provide the stability analysis of a few popular techniques for adversarial training and show that they indeed stability-promotii
We provide experiments on SVHN, CIFAR-10, CIFAR-100, and ImageNet. The results verify the generalization bounds.
Technical contribution: develop set of properties of naapproximately smooth function, which might be useful in other tasks.
The paper is organized as follows. After discussing the related work in Sec. [ the rest of the paper contains two parts. The first part is the technical part to derive stability bounds. The second part is to analyze robust overfitring. Specifically, the first part, Sec. iintroduue the preliminary knowledge about UAS. Sec. provides the Lemma and properties of approximately smooth functions and Sec. 5 gives the stability bounds. In the second part, Sec. @analyyess the robust overfitting in the theoretical settings and Sec. presents the experiments.
2 Related Work
Adversarial Attacks and Defense. Starting from the work of (Szegedy et al. 2013), has been commonly realized that deep neural networks are highly susceptible to imperceptible corruptions to the input data (Goodfellow et al. 2014, Carlini and Wagner 2017 Madry et al.! 2017). A series
of work aimed at training neural networks robust to such small perturbations (Wu et al. 2020
Gowal et al. 2020 Zhang et al.] 2020) and another line work aimed at designing more powerful adversarial attack algorithms (Athalye et al. 2018 Tramer et al. 2020: Fan et al. 2020; Xiao al., 2022c Qin et al. 2022). A series of work considered adversarial robustness in black-box settings
(Chen et al. 2017 Qin et al. (02TT. Semi-supervise
learning has been used to improve adversarial
robustness Carmon et al. [ et al. 2022). Fast adversarial training (Wong et al. 2020
Huang
al.
2022
was introduced to save training time.
Robust Generalization. A series of work tried to explain robust generalization the uniform
convergence framework, including VC-dimension (Attias al. 2021 Montasser et al. 2019) and
Rademacher complexity (Khim and Loh 2018: Yin et al. 2019; (Aaasth et al. 2020 Xiao et al.
2022a). Uniform algorithmic stability is another framework to study robust generalization (Farnia and Ozdaglar 2021 Xing et af.] 2021a Xiao et al. 2022b). The work of (Schmidt et al. 2018
Raghunathan et al. 2019 Zhai et al. 2019) have shown that in some scenarios achieving robust
generalization requires more data. The work of (Xing et al. [02Ibjc]Javannard et al.) (020) studied
the generalization in the setting of adversarial linear regression. (Sinha et al. (017]) studied the
generalization of distributional robustness. The work of (Taheri et al. [2200] Javanmard et al. 2020
Dan et al. 2020) analyzed robust generalization in Gaussian mixture models.
Uniform Stability. Stability is a classical approach to provide generalization bounds. It can be traced back to the work of (Rogers and Wagner 1978). After few decades, it was well devel- oped in analyzing the generalization bounds in statistical learning problems (Bousquet and Elisseeff] 2002). These bounds have been significantly improved in a recent sequence of works (Feldman and Vondrak 2018 2019). The work of (Chen et al., 2018) derived minimax lower bounds for excess risk and discussed the optimal trade-off between stability and convergence. Ozdaglar al. (0022) considered the generalization metric of minimax optimizer.
3 Preliminaries of Stability
Consider the following setting of statistical learning. There is an unknown distribution D over examples from some space Z. We receive a sample dataset S = {21...., 2n } of examples drawn i..dd from D. The population risk and empirical risk are defined as:
n
Ro) def E.-D 1(00 2) and Rs(0) del
h(0, 2:),
3

---

respectively, where h(---) is the loss function.
Risk Decomposition. Let 0 and be the optimal solution of RD( and (2( respectively. Then for the algorithm output 8 A(S), the excess risk can be decomposed
(o) R0 = R - R.s (
R R - ( + Rs( (8*) + Rs( R
Egen
Expe
S0
E=U
To control the excess risk, we need to control the generalization gap Egen and the optimization gap Eapt. In the rest of the paper, we use Egen and Eopt to denote the expectation of the generalization and
optimization gap. To bound the generalization gap of model 0 A(S) trained by randomized algorithm A, we employ the following notion of uniform stability.
Definition 3.1. A randomized algorithm A is e-uniformly stable for all data sets S, 2" such that S and S' differ in at most one example, we have
EA [h(A(S):)) MMA())):))MMA())))
(3.1)
Here, the expectation is taken only over the internal randomness of A. We recall the important theorem that uniform stability implies generalization in expectation (Hardt et al. (016))
Theorem 3.1 (Generalization in expectation). Let be s-uniformly stable. Then, the expected generalization gap satisfies
Egent = [Es.A Rs[A(S)]I E
Therefore, we turn the properties of iterative algorithms that control their uniform stability.
4 Stability of Adversarial Training
Adversarial Surrogate Loss. In adversarial training, we consider the following surrogate loss
h(0; 2) = max
I|s->'ll, 2())2'),
(4.1)
where g(0; 2) is the loss function of the standard counterpart, || is the fp-norm, p 2 1. Usually, can also be written in the form of ((f( y), where fo the neural network to trained and (ær, y) is the input-label pair. We assume the loss function g satisfies the following smoothness assumption. Assumption 4.1. The function g satisfies the following Lipschitzian smoothness conditions:
1|9(01, 2) g(2,, 2) < L| 02ll.
[eg((1,22 Veg(O2, =)] < Le 0a 0211,
(eg((0 Veg(O, 22) 22 < Lg |21 - 2211p-
where ||-]| is Euclidean norm.
Assumption 4. assumes that the loss function is smooth, which are also used in the stability litera- ture (Farnia and Ozdaglar 2021; Xing al. 2021a). as well as the convergence analysis literature (Wagg et 2019 Liu et a 2020). While ReLU activation function is non-smooth, recent works Alllen-Zhu et al. 2019 Du et a (2199) showed that the loss function of over over-parameterized DNNs semi-smooth. It helps justify Assumption 4.1 Under Assumption
4.1 the loss function of adver-
sarial training satisfies the following Lemma (Liu al. 2020).
Lemma 4.1. Let h be the adversarial loss defined in Eq. v0,,0 B2 and V2 Z. the following properties hold.
4.1 and g satisfies Assumption 4.1
1. (Lipschitz
[|h(02, 2) 1u(02, =)1l S L| 82ll.
2. For all subgradient d d(0,z) E (0, we have [Id(01, d(0g, =)]l < Lo]10 - -21l 2Lze.
If we further assume that g0, 2) is ju-strongly concave in z, the adversarial surrogate loss h(0, 2) is also smooth (Sinha et al. (017). Therefore, the uniform stability of adversarial training follows (Hardt et al. 22066] Farnia and Ozdaglar 2021), see Appendix B.3. However, g(0, 2) is non-strongly concave in practice. The above results provide limited explanations of the poor generalization of adversarial training. We discuss the generalization properties of adversarial training under Lemma

---

4.1 Basic Properties of Approximate Smoothness
To simplify the notation, we use h(0) as a shorthand notation of h(0, 2). To simplify the argu- ment, we consider differentiable function h. The results can be extended to non non-differentiabee cases. Lemma I.
to analyze function with the following modified smoothness assumption, which we call approximate smoothness assumption.
Definition 4.1. Let 3 >> O and > O. We say a differentiable function h(0) is 1p-aproxxmaatlly 3-gradient Lipschitz, if'0, and 02, have
IVv((1)) Vh(02)ll - B||01 - -02ll +
In definition 4.1 7) controls the smoothness of the loss function h(.). When 1/ = 0, the function is
gradient Lipschitz. When 17 + +o0, h is a general non-smooth function. As our discussion before, the adversarial surrogate loss is e-pppooxiiaalll smooth. As far as we know, this assumption rarely discussed in the optimization literature since it cannot improve the convergence rate from general non-smooth assumption. But affects uniform stability, as we will discuss later. We need to develop the basic properties of approximate smoothness first.
Lemma 4.2. Assume that the function is n-approximately 3-gradient Lipschitz. V01, 02 and Va E 2, the following properties hold.
1. (n-approximate descent lemma.)
3 h(01)= - h(02) S Vh(02) - -82) 110 0211 + nl|01 - 02l1-
(n-aaprrximattll co-coercive.) Assume addition that h(0, 2) is convex for all 2 E Z. Let
[+ max(0,)) +). We have
(Vh(O,) - Vh(02), 8, 02) [IVn(0)) - m1+
We defer the proof to Appendix A. Note that the loss function is L-Lipschitz for every example 2, we have (0,, z) - (02, 2)] S. LIE| - 03]1 for all E Z. To obtain the stability generalization bounds, we need to analysis the difference |10 0g |. where of and 0 are the outputs of running SGD on adversarial surrogate loss for 7' iterations on two datasets with only one different sample. Next we provide the recursive bounds under the approximate smoothness assumption.
Algorithms. We consider the stochastic gradient descent on the adversarial surrogate loss. i.c.
g = 0¹ a V (0" );.),
(4.2)
where a is the step size in iteration t, 2,, is the sample chosen in iteration t. We consider two popular schemes for choosing the examples indices &, Sampling with replacement: One is to pick n at each step. Fixed permutation: The other is to choose a random permu- tation over (1.... ] and cycle through the examples repeatedly in the order determined by the permutation. Our results hold for both variants.
it ~ Uniform(1,
Properties of Update Rules. We define (f) 0 vV((f,2) be the update rule of SGD. The following lemma holds.
Lemma 4.3. Assume that the fanction a-approximately B-gradient Lipschitz. VO,, O2 and 2, we have
(unt-aprroiimutely (1 + -e)xespaasivve. [[Ga, (0..
S (1 a;3) - 02l1 + an.
(oroapproxllaaell non non-expansive.) Assume in addition that h00,2) 2) convex in O for all E 2, for a 1/3, we have
Ga.2 (f))
1|0 021 + am)
3. (ox-approximately (1 contrrctctv) Assume in addition that h(0, 2) is stsoongyy comvex in for folall= = f.r a 1/8, we have (0, G..: (02) || S (1 a0)] 02] + on.
The proof of Lemma 4.3 is based on Lemma 4.2 and is deferred to Appendix A. Lemma 4.3 provides the recursive distance [ 02] from iteration to / + 1. Based on this, we can recursively derive the distance |io7 0f I]. Then, we can obtain the stability generalization bounds.
5

---

Stability Generalization Bounds
In the previous section, we have discussed the properties of approximate smoothness and developed tools we need to use. In this section, we discuss the stability bounds.
5.1 Convex Optimization
We first consider the case that =)) is convex in 0 for all E Z. Theorem 5.1. Assume that 2) convex, L-Lipschitz and n-approximately 3-gradient Lipschitz in for all given E 2. Suppose that we run SGD with step sizes S 1/3 for 'T steps. Then,
2L
Egen = E(" Rs(0")) s I.
4t-
(5.1)
The proof is mainly based on Lemma 4.3 that the update rule is approximately non-expansive in this case. We defer it to appendix A. We have shown that the adversarial surrogate loss 2 approximately Lg-gradient Lipschitz. Let 2 in Eq. (5.T), we directly obtain the stability bounds for adversarial training. In practice, the solution of the inner problem is sub-optimal. Let Ae be the maximum error between the optimal and sub-optimal attacks in each iteration. We have the following Corollary.
Corollary 5.1 (Uniform stability for sub-optimal attacks adversarial training.). Under Assumption 4.1 assume in addition that g(0, 2) is convex in for all given z E Z. Suppose that we run adversarial training with step sizes On I 1/Lo for T steps. Then, adversarial training satisfies uniform stability with
2L
Σ a s ooLLLet
T
L > T
Egen I (2LL((+ Ae)
at
(5.2)
shows that adversarial training with weak attacks (large Ac) have worse robust generalization than that with strong attacks. This is also observed in practice. However, Ac is at most 2c, the upper bound of AT with different attacks have the same order. It might be due to the weakness of Assumption 4.1 4.Tor or uniform stabilty framework.
Remark: Corollary 5.1
we let = in Eq. (5.2) it reduced to the generalization bound in (Hardt et al.) 2016) for standard training. Therefore, the additional generalization error of adversarial training comes from the additional term Lg The global gradient Lipschitz Le with respect plays an important role generalization. Even though the perturbation is small, is amplified by the Lipschitz L, and finally hurts the robust generalization.
Interpreting Robust Generalization.
5.2 Further Discussion on the Generalization Bounds
We first provide lower bound. Then compare our bounds with the existing bounds in Table
Theorem 5.2 (Lower Bound). There exists functions h(0, 2), s.f. is convex, L-Lipschitz, and n approximately 3- 3-gradient Lipschitz in @ for all given
Z. Exists S and S' differ in one sample.
Suppose that we run SGD with step fixed step sizes a S 1/B for T steps. Then,
E S') 2 Ω (navT++ LaT
(5.3)
Table 1: Comparison of the upper and lower bounds of E[8(S, S')) Comparing with the previous results, we replace L by r7 and provide the matching lower bound in
Assumption
Upper bounds OLLaa/n)
Lower bounds ((LTa/n)
Farnia and Ozdaglar 2021
convex-strongly concave
Xing et al. (202aa)
convox-nonconcave convox-noneomcave
OLLTTa+ LTa/n)
Ours
O LTa/n)
M + LTa/n)
Compared with the work of (Farnia and Ozdaglar 2021) they assume that the inner problem is strongly concave. Thus the bounds are not comparable.
Comparison with the Existing UAS Bounds.

---

Strongly concave is a strong assumption in practice. Therefore, the work of (Xing et al. 2021a) and our analysis focus on the nonconcave cases. Comparing with the bound (LLvTa Ta + LTa/n), our bound captures critical aspect of robust generalization bound: c-dependent. As observed in practice, the robust generalization gap reduces to the standard generalization gap + 0. Our bound consists with this observation. On the contrary, the bound (LVVTa + LTa/n) is very large when e -> O. Additionally, we provide matching lower bound w.r.t v). The comparison is provided in Table
Comparison with the Work of (Xing al. 2021a). The work of (Xing et al. 2021a) argued that the max function is not smooth even though the standard counterpart is smooth. Therefore, they followed the bound in non-smooth cases (Bassily et al., 2020). Then, they aimed solve the non-smooth issue. They design a noise- cnsse-ijecttd algorithm and show its effectiveness in tackling the non-smooth issue. Our work focus on providing better bounds interpret robust overfitting.
5.3 Non-convex Optimization and Strongly Convex Optimization
Next, consider the that the loss function h is general non-convex and strongly convex. By Lemma 4.3] we have
Theorem 5.3. Assume that h(0,z) is L-Lipschitz, and n-approximately 3-gradient Lipschitz for all given 2 Z. Assume in addition that h(0,2) < B for all 8 and 2. Suppose that run SGD with diminishing step sizes on I 1/((t) for T steps. Then
BL + (2L - Lyn)T
Egen
(5.4)
B(n-
Theorem 5.4. Assume that h(0,z) =) is 7-strongly convex, L-Lipschitz, and n-approximately B- gradient Lipschitz in 0 for all given z E Z. Suppose that we run SGD with step sizes og S 1/3 for T steps. Then
Egen = ((R)(0") - Rs((0)] Ln +
2L
(5.5)
yn
The bound in non-convex cases provides similar interpretation of robust generaliza- tion to the analysis in the convex case. uniform stability analysis, whether the loss function is convex or non-convex does not give major difference. Therefore, we provide the analysis of the non-convex case in Appendix B. We also provide our convergence analysis of running SGD on n-approximate smoothness, non-convex function in Theorem B.1. Strongly convex strong assumption. We leave the analysis of the bound in strongly convex cases in Appendix B.2.
Remark:
6 Excess Risk Minimization
Based on the risk decomposition, we have Excess Risk < Egen + Eapt. we need to minimize Eyen + Expt to achieve better performance. Per our previous discussion, whether the loss function is convex or non-convex does not give a major difference in stability analysis. We study the convex case in this section. We leave the discussion on the non-convex and strongly convex cases in Appendix B. and B.2, respectively. We first introduce the optimization error.
Optimization Analysis. The convergence analysis of SGD on a L-Lipschitz, convex function is discussed in (Nemirovski et al. 2009). The convergence rate cannot be improved if we further assume that the function is gradient Lipschitz. Therefore, a weaker condition, approximately gradient Lipschitz, cannot improve the convergence rate. We the following convergence bound (adopted from (Nemirovski et al. 2009)) for the optimization error both adversarial training and standard training.
Theorem 6.1. Assume that h(0, 2) is L-Lipschitz and convex in 0 for all given z E Z. Let D 1800 1. where 80 is the initialization of SGD. Suppose that we run SGD with step sizes at for T steps. Then, 3K < T, s.t.
D2
-
TT
of
Eope (
21=1
(6.1)
Σ
04
7

---

If we let 1/VT, we have Eopt I {O(/VT)) which is the convergence rate of SGD on convex function. Since we need consider the generalization and optimization errors simultaneously, we keep the 04 in Theorem 6.
Trade-off. We have now discussed the optimization and general- ization errors of adversarial training. We aim to find the optimal trade-off between generalization and optimization in terms of a and T. However, finding the optimal a, and T simultaneously is challenging. We consider the settings we use in practice.
Anneraalzation-Opiinizzati
Fixed Step Size. We first consider the simplest case, the step size a is fixed. Then, combining Eq.
5.1
and Eq. 6.1 we have
for standard training
additional
2L D²
Egen + Eopt S
LnTa +
+ Ta
+ LZa
(6.2)
for adversarial training
Interpretation of Robust Overfitting. In standard training, overfitting is rarely observed in prac- tice. The optimization error and generalization error are both small. In Eq. (6.2) the second to the fourth terms are for standard training. The second term is controlled by the number of samples n, which small if we have sufficient training samples. The third term is controlled by T, and the last term is fixed given a small a. This bound partially explains the good performance of standard training. However, have additional term LiyTa a for excess risk in adversarial training. Then, after a particular iteration that LifI'a a dominates Eq. (6.2). robust overfitting appears. This is con- sistent with the training procedure practice. Therefore, the _ approximate smoothness of adversarial loss provides possible explanation of robust overfitting. To achieve better performance, we need to stop training the model earlier.
Early Stopping, It shown that early stopping is an important training technique for adversarial training (Rice al. 2020). In Eq. (6.2). if we optimize the right-hand-side with respect to T, we have
1100 - 11
2L D D+I2 D
Egen + Eopt I // Ln
a Ln 2L2/n'
Therefore, it is the best to stop training at T However, T is unknown in practice. It is important to select stopping criteria. For example, we can use a validation set to determine when to stop.
Varying Step Size. We discuss one popular varying step size schedule, eyclic learning rate, which also called super-converge learning rate for adversarial training. It is shown that it can speed up adversarial training with fewer epochs (Wong et al. 2020). The Super-converge learning rate follows the following rules. In the first phase (warm-up), the step size increase from to a' linearly. In the second phase (cold down), the step size decreases back to 0 linearly. It is unclear (to knowledge) why this schedule can speed up convergence in optimization theory. But the generalization part can partially be explained by UAS. If we set a' = 2o, it is easy check that Egen & (In + 2T. TT in this case, which is the same as the bound the fixed learning rate case. Notice that the cyclic learning rate usually requires fewer steps T to converge. Then, the generalization gap is smaller. Cyclic learning rate can be viewed as another form of early stopping from the perspective of UAS.
Stochastic Weight Averaging. SWA is also useful training technique for adversarial training (Hwang et al., 2021). Instead of using the last checkpoint, SWA suggests using the average of the checkpoints for inference. It is shown that SWA find a model with better generalization since it leads to wider minima (Izmailov et al. 2018). Below we study SWA from the perspective of UAS.
Theorem 6.2. Assume that h(0, 2) is convex, L L-Lisschitz and apprrooximt 3-gradient Lipschitz in 0 for all given z E Z. Suppose that we run SGD with step sizes a₁ S 1/3 for T steps. Let 0 be the average of the trajectory. Then,
Ln 2
I
Eopt (0) 5 100 112 + L2 1T T
Egen (0) <
Ctss
(6.3)
n
Σ1 a4
8

---

In words, SWA reduces the generalization error bound to one-half of the one without SWA. But the training error bound remains unchanged.
Experiments
Training Settings. We mainly consider the experiments on CIFAR-10 (Krizhevsky et al. 2009), CIFAR-100, and SVHN (Netzer et al. 201T). We also provide one experiment on ImageNet (Deng et al. 2009). For the first three datasets, we conduct the experiments
training ArtRess 18, which follows (Rice et al., 2020), For the experiment on ImageNet, we use ResNet-50 (He et al.)
2016). following the experiment of (Madry et al. 2017). For the inner problems, we adopt the &oc
PGD adversarial training in (Madry et al. 2017), the step size in the inner maximization is set to be
// on CIFAR-10 and CIFARION and is set to be e/8 on SVHN, Weight decay is set to be 5 x 10-
Additional experiments are provided Appendix
TeP ACE
Tet 200 Ace
43-
55-
45-
150
24
20
100
1.4
202
319
159
20
Addirone soochrreatton p1im (r0ce)
(b)
Figure 2: Robust overfitting in the experiments on (a) CIFAR-10, (b) CIFAR-100, (c) SVHN and (d) ImageNet.
Robust Overfitting on Common Dataset. In Fig. 2 (a), (b), and (c), we show the experiments on the piece-wise learning rate schedule, which is 0.1 over the first 100 epochs, down to 0.01 over the following 50 epochs, and finally be 0.001 in the last 50 epochs, on CIFAR-IO. CIFAR-100, and SVHN. Experiments on different are shown in Appendix C. Robust Overfitting on ImageNet. We provide one experiment on ImageNet in Fig. (d). We start from pre-trained model from Madry's Lab and keep running 50 more epochs. Robust overfitting can be observed in these experiments.
After a particular epoch (around the 1h epoch), the robust training accuracy is still increasing, but the robust test accuracy starts to decrease.
Buzusi itaitig room zoy
Jccsnup, OPARLO
Rebus: la arthg uccuraty OPARLEE
Tabot 2002 ayy CPAN100
0.5
63-41
5.1
601-
0.1
603-4
305
5.0
155
223
33
120
330
25
18
206
130
(b)
Figure 3: Experiments of adversarial training on CIFAR-10 10 and CIFAR-100 100 with fixed learning
rate, (a) Robust training accuracy on CIFAR-10. 10. (b) Robust test accuracy on CIFAR-10. 10. (c) Robust training accuracy on CIFAR-100, (d) Robust test accuracy on CIFAR- 100. are set to be 2, 4, 6, 8, and 10.

---

Fixed Step Size. To better understand robust overfitting and match the theoretical settings (in Eq. (.2))) we consider the fixed learning rate schedule. In Fig. [ we show the experiments of adversarial training using fixed learning rate 0.01. The perturbation intensity is set to be 2, 4, 6, and respectively. Fig- (a) and (b) show the experiments on CIFAR-10. Fig. (c) and (d) show the experiments on CIFAR-100, respectively. Fig. shows the experiments on SVHN
Generalization Error Dominates Training Error. In the robust overfitting phase, the ro- bust generalization error dominates the robust training error. This phenomenon corresponds to the Eq. (6.2) that the first term dominates the other terms with large T.
tnhing scorsdy
Rozust scoracy
06
Com- Robust Test Accuracy Decreases that the paring different in Fig. El robust test accuracy decreases faster when is larger. This corresponds to the robust overfit- ting rule in the theoretical setting that the test performance decreases in These phenom- ena are similar in theoretical and practical set- tings. Therefore, the stability analysis provides a different perspective on understanding robust overfitting.
35
(a)
Figure 4: Experiments of adversarial training on
SVHN with a fixed learning rate. (a) Robust train-
ing accuracy. (b) Robust test accuracy.
Robust Test Accuracy Decreases in Rate between ((cVT) and O(TT). If c is small, e.g., 2, the decrease rate is close to OEET). If e is large, the decrease rate is more likely to be (evTT)) This is also the gap between the upper bound and lower bound in Sec.
8 Conclusion
Limitations and Future Work. Firstly, in Fig- 3 we can see that the decrease rate of robust over- fitting is close to (T) when is small and close to (2(v (2(VT) when is large. One possible direction to figure out the relation. Secondly, one might improve adversarial training by controlling L.- L depends on the loss, the network architecture, and the dataset. One possible direction to design a smoother loss smooth activation function (e.g., SiLU) for a lower Lg. Notice that L, is uniform for all 8. If we view (f) locally with respect to 6 we might use an (approximated) second-order penalty term on its magnitude to control it.
In this paper, we show that the adversarial loss satisfies 1/approximate smoothness, and we derive stability-band -based generalization bounds on this general class of 7-aaproximmaee smooth functions. Our bounds give a different perspective on understanding robust overfitting- The robust test accuracy decreases in and experimental results confirm this phenomenon. We think our work will inspire more theoretical and empirical research to improve adversarial training.
Acknowledgement
We would like to thank Jiawei Zhang, Congliang Chen, and Zeyu Qin for the helpful discussions. We thank all the anonymous reviewers for their comments and suggestions. The work is supported by Data Computing.
NSFC-6173100 and the Guangdong Provincial Key Laboratory of Big
10

---

References
Allen-Zhu, Z., Li, Y., and Song, Z. (2019). A convergence theory for deep learning via over- parameterization. In International Conference Machine Learning, pages 242-252. PMLR.
Athalye, A., Carlini, N., and Wagner, D. (2018). Obfuscated gradients give false sense of security:
Cireumventing defenses to adversarial examples. arXiv preprint urXiv:/802.000
Attias, I., Kontorovich, A., and Mansour, Y. (2021). Improved generalization bounds for adversari- ally robust learning.
Awasthi, P., Frank. N., and Mohri, M. (2020). Adversarial learning guarantees for linear hypotheses and neural networks. In International Conference on Machine Learning, pages 431-441, PMLR.
Bartlett, P. L. and Mendelson, S. (2002). Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):463-482
Bassily, R., Feldman, V., Guzmán, C., and Talwar, K. (2020). Stability of stochastic gradient descent on nonsmooth convex losses. arXiv preprint arXiv:2006.06914.
Bousquet, O. and Elisseeff, A. (2002). Stability and generalization. The Journal of Machine Learn- ing Research, 2:499-526.
Carlini, N. and Wagner, D. (2017). Towards evaluating the robustness of neural networks. In 2017 ieee symposium security and privacy (sp), pages 39-57 57. IEEE.
Carmon, Y., Raghunathan, A., Schmidt, L., Duchi, J. C.. and Liang, P. S. (2019). Unlabeled data improves adversarial robustness. In Advances in Neural Information Processing Systems, pages 11190-11201.
Chen, P.-Y., Zhang, H., Sharma, Y., Yi, and Hsieh, C.-J (2017). Zoo: Zeroth order optimization based black-box attacks to deep neural networks without training substitute models. Proceed- ings of the 10th ACM Workshop on Artificial Intelligence and Security, pages 15-26.
Chen, Y., Jin, C., and Yu, B. (2018). Stability and convergence trade-off of iterative optimization algorithms. arXiv preprint 10Xx:1884.00119
Dan, C., Wei, Y., and Ravikumar, P. (2020). Sharp statistical guaratees for adversarially robust
gaussian classification. In International Conference Machine Learning, pages 2345-2355 PMLR.
Deng. J., Dong, W., Socher, R., Li, L.-J,, Li, K., and Fei-Fei, L. (2009). Imagenet: A large-scale hi- erarchical image database. In 2009 IEEE conference computer vision and pattern recognition, pages 248 255. leee.
Du, S., Lee, J., Li, H., Wang, L., and Zhai, X. (2019). Gradient descent finds global minima of deep neural networks. In International Conference on Machine Learning, pages 1675-1685. PMLR.
Fan, Y., Wu, B., Li, T., Zhang, Y., Li, M., Li, Z., and Yang, Y. (2020). Sparse adversarial attack via perturbation factorization. In European conference on computer vision, pages 35-50. Springer.
Farnia, F. and Ozdaglar, A. (2021). Train simultaneously, generalize better: Stability of gradient- based minimax learners. In International Conference on Machine Learning, pages 3174-3185. PMLR.
Feldman, V. and Vondrak, J. (2018). Generalization bounds for uniformly stable algorithms. arXiv preprint arXiv:/8/2.09859,
Feldman, V. and Vondrak, J. (2019). High probability generalization bounds for uniformly stable al- gorithms with nearly optimal rate. In Conference on Learning Theory, pages 1270-1279, PMLR.
Goodfellow, I. J., Shlens, J., and Szegedy, C. (2014). Explaining and harnessing adversarial exam- ples. arXiv preprint
Gowal, S., Qin, C., Uesato, J., Mann, T., and Kohli, P. (2020). Uncovering the limits of adversarial training against norm-bounded adversarial examples. arXiv preprint arX1v:2010.03593.

---

Hardt, M., Recht, B., and Singer, Y. (2016). Train faster, generalize better: Stability of stochastic gradient descent. In International Conference on Machine Learning, pages 1225-1234. PMLR.
He, K., Zhang, X., Ren, S., and Sun, J. (2016). Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778.
Hochreiter, S. and Schmidhuber, J. (1997). Long short-term memory. Neural computation, 9()::1335
Huang, Z., Fan, Y., Liu, C., Zhang. W., Zhang, Y., Salzmann, M., Süsstrunk, S., and Wang. J. (2022). Fast adversarial training with adaptive step size. arXiv preprint arXiv:2206.0244 02417.
Hwang, J.-W., Lec, Y., Oh, S., and Bae, Y. (2021). Adversarial training with stochastic weight average. 2021 IEEE International Conference on Image Processing (ICIP), pages 814-818.
IEEE.
Izmailov, P., Podoprikhin, D., Garipov, T., Vetrov, D., and Wilson, A. G. (2018), Averaging weights leads wider optima and better generalization. arXiv preprint arXiv:1803.05400
Javanmard, A.. Soltamolkotabi, M., and Hassani, H. (2020). Precise tradeoffs in adversarial training for linear regression. In Conference on Learning Theory, pages 2034-2078. PMLR.
Khim, J. and Loh, P.-L. (2018), Adversarial risk bounds via function transformation. arXiv preprint arXiv: 19519.
Krizhevsky, A., Hinton, G., et al. (2009), Learning multiple layers of features from tiny images.
Krizhevsky, A., Sutskever, I., and Hinton, G. E. (2012). Imagenet classification with deep convolu- tional neural networks. In Advances in neural information processing systems, pages 1097-1 105.
Li, Y., Wu, B., Feng, Y., Fan, Y., Jiang, Y., Li, Z., and Xia, S.-T. (2022). Semi-supervised robust training with generalized perturbed neighborhood. Pattern Recognition, 124: 108472.
Liu, C., Salzmann, M., Lin, T., Tomioka, R., and Süisttrunk, S. (2020). On the loss landscape of adversarial training: Identifying challenges and how to overcome them. arXiv preprint arXiv:2006.0844
Madry, A., Makelov, A., Schmidt, I.., Tsipras, D., and Vladu, A. (2017).
Towards deep learning
models resistant to adversarial attacks. arXiv preprint arXiv:
Montasser, O., Hanneke, S., and Srebro, N. (2019). Ve classes are adversarially robustly learnable, but only improperly. In Conference Learning Theory, pages 2512-25330 PMLR.
Nemirovski, A., Juditsky, A., Lan, G., and Shapiro, A. (2009). Robust stochastic approximation approach to stochastic programming. SIAM Journal on optimization, 19(4):1574-1609
Netzer, Y., Wang, T., Coates, A., Bissacco, A., Wu, B., and Ng, A. Y. (2011). Reading digits in natural images with unsupervised feature learning.
Ozdaglar, A., Pattathil, S., Zhang, J., and Zhang, K. (2022). What is a good metric to study gener- alization of minimax learners? arXiv preprint arXiv:2206.04502.
Qin, Z., Fan, Y., Liu, Y., Zhang, Y., Wang, J., and Wu, B. (2022). Boosting the transfcrability of adversarial attacks with reverse adversaria perturbation.
Qin, Z., Fan, Y., Zha, H., and Wu. B. (2021). Random noise defense against query- based black-box attacks. Advances in Neural Information Processing Systems, 34:7650-7663.
Raghunathan, A., Xie, M., Yang, F,, Duchi, J. C., and Liang, P. (2019). Adversarial training can hurt generalization. arXiv preprint arXiv:1906.000 190660606660.
Rebuffi, S.-A., Gowal, S., Calian, D. A., Stimberg, F., Wiles, O., and Mann. T. (2021). Fixing data augmentation to improve adversarial robustness. arXiv preprint arXiv:2103.01944
Rice, I.., Wong, E., and Kolter, Z. (2020). Overfitting adversarially robust deep learning. In International Conference Machine Learning, pages 8093-8104. PMLR.
12

---

Rogers, W. H. and Wagner, T. J. (1978). A finite sample distribution-fres performance bound for local discrimination rules. The Annals of Statisties, pages 506-514.
Schmidt, L., Santurkar, S., Tsipras, D., Talwar, K., and Madry, A. (2018). Adversarially robust generalization requires more data. In Advances in Neural Information Processing Systems, pages 5014-5026.
Sinha, A., Namkoong, H., and Duchi, J. (2017. Certifiable distributional robustness with principled adversarial training. arXiv preprint arXiv:1710.1055
Szegedy, C., Zaremba, W., Sutskever, Bruna. J., Erhan, D., Goodfellow, and Fergus, R. (2013). Intriguing properties of neural networks. arXiv preprint arXiv:1312.6199
Taheri, H., Pedarsami. R., and Thrampoulidis. C. (2020). Asymptotic behavior of adversarial training in binary classification. arXiv preprint arXiv:2010.1322 13275.
Tramer, F., Carlini, N., Brendel, W., and Madry, A. (2020), On adaptive attacks to adversarial example defenses. arXiv preprint arX1v:2002.08837.
Vapnik, V. N. and Chervonenkis, A. Y. (2015). On the uniform convergence of relative frequencies of events to their probabilities. In Measures of complexity, pages 11-30. Springer.
Wang, Y., Ma, X., Bailey, J., Yi. J., Zhou, B., and Gu, Q. (2019), On the convergence and robustness of adversarial training. In ICML, volume page
Wong, E., Rice, L., and Kolter, J. Z. (2020). Fast better than free: Revisiting adversarial training. arXiv preprint arXiv:2001.03994.
Wu, D., Xia, S.-T., and Wang, Y. (2020). Adversarial weight perturbation helps robust generaliza- tion. arXiv preprint arXiv:2004.055: 05884.
Xiao, J., Fan, Y., Sun, R., and Luo, Z.-Q. (2022a). Adversarial rademacher complexity of deep neural networks.
Xiao, J., Qin, Z., Fan, Y., Wu, B., Wang. J., and Luo, Z.-Q. (2022b). Adaptive smoothness- weighted adversarial training for multiple perturbations with its stability analysis. arXiv preprint arXiv:2210.005: 00557.
Xiao, J., Yang, I.,, Fan, Y., Wang. J., and Luo, Z.-Q. (2022c). Understanding adversarial robustness against on-manifold adversarial examples. arXiv preprint arXiv:22/0.004::
Xing, Y., Song, Q. and Cheng, G. (2021a). On the algorithmic stability of adversarial training. In Thirty- Fifth Conference on Neural Information Processing Systems.
Xing, Y., Song, Q., and Cheng, G. (2021b). On the generalization properties of adversarial training.
In International Conference on Artificial Intelligence and Statistics, pages 505-513. PMLR.
Xing, Y., Zhang, R., and Cheng, G. (2021c), Adversarially robust estimate and risk analysis in linear regression. In International Conference on Artificial Intelligence and Statistics, pages 514-522. PMLR.
Yin, D., Kannan, R., and Bartlett, (2019). Rademacher complexity for adversarially robust gener- alization. In International Conference on Machine Learning, pages 7085-7094. PMLR.
Zhai, R., Cai, T., He, D., Dan, C., He, K., Hopcroft, J., and Wang. L. (2019). Adversarially robust generalization just requires more unlabeled data. arXiv preprint arXiv:1906.0055
Zhang, C., Bengio, S., Hardt, M., Recht, B., and Vinyals, O. (2021). Understanding deep learning
(still) requires rethinking generalization. Communications of the ACM, 64(3):107-155.
Zhang, Xiao, P., Sun, R., and Luo, Z. (2020). A single-loop smoothed gradient descent-ascent al- gorithm for nonconvex-coneet min-max problems. Advances in Neural Information Processing Systems, 33:7377-7389.
13

---

1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [Yes]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report enror bars (e.g., with respect to the random seed after running experi- ments multiple times)? [No]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you using existing assets (c.g., code, data, models) curating/relcasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifi- able information offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "x87ilfd_Pt4", "reviewer": "Reviewer_LfVE", "summary": "The paper is concerned with a uniform stability analysis of adversarial training, in order to gain a better understanding of the robust overfitting phenomenon.\nTo this end the authors introduce a class of $\\eta$-approximately smooth functions, i.e., functions $h$ whose gradient is approximately Lipschitz continuous and satisfies\n$$\\|\\nabla h(\\theta_1) - \\nabla h(\\theta_2)\\|\\leq L \\|\\theta_1-\\theta_2\\| + \\eta.$$\nThis is motivated by the fact that the adversarial loss $h(\\theta; z) := \\max_{\\|z'-z\\|\\leq\\varepsilon} g(\\theta; z')$ is $\\eta$-approximately smooth with $\\eta=2 L_z \\varepsilon$ where $L_z$ is the Lipschitz constant of $z\\mapsto\\nabla_\\theta g(\\theta, z)$.\n\nThe authors then prove bounds for the generalization and the optimization gap of stochastic gradient descent (SGD) applied to the adversarial risk for different assumptions on the loss function (such as different degrees of convexity). The most notable discovery is that the generalization gap after $T$ steps of SGD with learning rate $\\alpha$ contains and extra term of order $L_z \\varepsilon T \\alpha$. The authors make the point that this explains robust overfitting since this term blows up for more and more SGD steps. This is also indicated by their numerical results.\n\n", "questions": "I have a couple of questions and remarks which should be taken into account for a revised version of the article:\n\n- a short paragraph on notation would be good. In particular, you should remark that you use the Euclidean norm not any norm.\n- Assumption 4.1: comment on the third assumption (see above)\n- Lemma 4.2: the comments before and after the lemma are a little confusing: This lemma shows that the adversarial loss is $\\eta$-approximately smooth and not that its not Lipschitz smooth. For this you would need a lower bound.\n- Lemma 4.2: Why is $h$ differentiable with respect to $\\theta$? A priori, this is not obvious due to the maximum in $z$.\n- line 170: Calling (4.2) SUBgradient descent seems out of place. This is just stochastic gradient descent and the gradient is a proper gradient by your assumptions.\n- line 198: did you mean to refer to Eq. (5.1) instead of (5.3)? \n- Corollary 5.2 basically shows that the inner maximization problem does not play a role at all in your analysis and you could just choose an arbtrary point which is $\\varepsilon$-close to $z$. I suspect this is due to the strong Lipschitz assumption on the gradient of $h$ (see above). This should be pointed out.\n- Theorem 5.3 should read: \"IT exists a function h...\", \"THERE EXIST data sets S and S'...\"\n- line 223: Is the improvement from L (the $\\theta$ Lipschitz constant of the loss) to $L_z\\varepsilon$ really an improvement?\n- line 223: I thought $L$ is the Lipschitz constant of the loss and not its gradient?\n- lines 223-230: the language of this paragraph is clumsy and should be revised. \n- Theorems 5.4 and 5.5 have slightly different wording which is confusing. For instance, \"we run SGD\" versus \"we run SGD on the adversarial surrogate\". Are there different assumptions here? \n- Theorem 5.4: It should read $\\alpha\\leq 1/\\beta$.\n- Maybe formula (6.2) could be moved to the beginning of the article. It seems to contain the main contribution.\n- Could one use a discrepancy principle (as used for variational regularization schemes to solve inverse problems) for the early stopping?\n- lines 347-348: For small values of $\\varepsilon$ I agree that the robust test accuracy seems to behave linearly in $\\varepsilon$ but not necessarily for large values ($\\varepsilon=10$).", "limitations": "The limitations of the assumption of an input-Lipschitz continuous gradients of the loss function should be discussed.\n\nNegative societal impact is not to be expected.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strenghts: \n\nThe paper is structured in a clear way and the arguments are easy to follow. The analysis of gradient descent type schemes for $\\eta$-approximately smooth functions is a valuable contribution on its own (at least I think its novel). The main strengths of the contribution are (1) a uniform stability analysis which depends on the adversarial budget $\\varepsilon$ and extends to non-convex losses and (2) a theoretical explanation of robust overfitting.\n\nWeaknesses: \n\nMy main criticism is that the Lipschitz gradient assumption $\\|\\nabla_\\theta g(\\theta, z_1) - \\nabla_\\theta g(\\theta,z_2)\\| \\leq L_z \\|z_1 - z_2\\|$ $\\forall \\theta$ with respect to the input variable $z$ seems very strong. Note that $L_z$ multiplies the adversarial budget $\\varepsilon$ in the stability estimates. Standard network architectures are known to be very far from being Lipschitz continuous with a moderate constant. In the light of this, demaning uniform Lipschitz continuity of the loss w.r.t. $z$ appears to be questionable. This is particularly important since recently it was shown that adversarial training leads to a total variation regularization instead of Lipschitz regularization, see [1,2]. Hence, in practice such uniform Lipschitz continuity may get lost during the optimization. \nThis issue requires some more explanations and justifications.\nBesides that, the paper would benefit from a careful language revision.\n\n[1] Finlay, C., Oberman, A. M., & Abbasi, B. (2018). Improved robustness to adversarial examples using Lipschitz regularization of the loss.\n[2] Bungert, L., Trillos, N. G., & Murray, R. (2021). The geometry of adversarial training in binary classification. arXiv preprint arXiv:2111.13613.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "dx9Rh9t3phF", "reviewer": "Reviewer_zt8C", "summary": "This paper provides a stability analysis ( and the consequent generalization analysis) of adversarial training. In order to tackle the nonsmoothness of adversarial loss, it introduces the eta approximation smoothness as an analysis tool. It derives a better rate than prior works with new theoretical insights. ", "questions": "One suggestion is that the theory considers gradient descent of empirical adversarial loss, while in practice, the optimization is done by an alternative min-max type optimization. I wonder whether this gap is essential or not.", "limitations": "N.A.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is well written and I believe it makes a good contribution to this line of research. \n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "SWPKOsKBoX", "reviewer": "Reviewer_mocV", "summary": "- The paper shows that the adversarial loss is approximately gradient Lipschitz, with the smoothness dependent on the adversarial perturbation size $\\varepsilon$\n- The paper derives an $\\varepsilon$ dependent generalization bounds, and interprets the bounds to argue that overfitting is a result of the non-smoothness of the adversarial loss\n- The paper analyzes common methods to mitigate adversarial overfitting to show that they are stability promoting\n- Experiments on SVHN, CIFAR-10, CIFAR-100, Imagenet to verify the bounds", "questions": "1. See weaknesses 1, 2. Do the authors have opinions on this?\n2. Does robust overfitting affect non-adversarial training based defenses such as randomized smoothing? Perhaps this could be useful evidence in support of the paper in case these other methods do face the same overfitting issue.", "limitations": "See weaknesses/questions section.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. Good presentation, and explains necessary context/background well\n2. Interesting result, and the paper provides a clear interpretation of it to explaining the robust overfitting phenomenon. The derived bound seems significant and is potentially useful beyond adversarial training literature. Very clear explanation of how this result compares to existing bounds\n3. Section 6 provides interpretations of methods which have been shown to reduce robust overfitting - this part is quite interesting\n\nWeaknesses:\n1. The derived result doesn't seem to explain why robust generalization requires significantly more datapoints (compared to regular training), and why this reduces robust overfitting. It seems that the bound derived would imply that robust overfitting would occur at the same rate regardless of $n$. We understand that this is perhaps outside of the scope of the paper, however a mention of this missing piece might be helpful\n2. A limitations sections explaining aspects of robust overfitting remain unexplained by this bound would be useful.\n3. Experiments feel a bit rudimentary, i.e. it feels like the experiments section verifies already known results, without a real attempt at nitpicking/ablating the theory. The reviewer is unsure what experiments could be conducted to improve this section", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "1oJHVx3psrf", "reviewer": "Reviewer_4YYt", "summary": "This paper studies the algorithmic stability of adversarial training. Compared to existing literature, it provides a better way to describe the smoothness of adversarial training, and obtain a more intuitive description on the algorithmic stability, convergence, and generalization error in adversarial training. Theorems and experiments are provided to justify their arguments.", "questions": "Please help address my concerns in the weaknesses section.", "limitations": "NA", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n[1] Different from existing literature, this paper provides another aspect of approximate smoothness to analyze the algorithmic stability of adversarial training. General results in algorithmic stability may not fit adversarial training very well, and this work overcomes this issue.\n\n[2] This paper provides theoretical results in terms of algorithmic stability, generalization, and optimization, which together characterize the adversarial training process. The theorems are easy to understand. They also provide a lower bound result, which further strengthens their contribution.\n\nWeaknesses: \n\n[1] Given a real data set, the relationship between \\eps and \\eta is fixed. Therefore, from the current experiments, it is not so convincing that the large generalization gap is caused by a large \\eta. It would be great if the authors can provide some simulation studies to verify the relationship between \\eta and the generalization when varying L and \\eps. It would be even better if there is a simulation in other tasks rather than adversarial training to justify the relationship between \\eta and generalization error.\n\n[2] This paper does not provide enough new insights on how to improve adversarial training. For example, this paper argues the necessity of early stopping, but it is a known conclusion as in Bassily et. al. (2020). In Xing et. al. (2021), they consider the noise-injection method to improve robustness, which is beyond Bassily et. al. (2020) and particular for adversarial training. However, in this submission, the authors only mention some potential solutions without any strong evidence.\n\n[3] This submission compares a lot with Xing et. al. (2021), and mentions a lot of weaknesses of that paper. However, after reading Xing et. al. (2021), my understanding is that they directly verify the effectiveness of the noise injection (optimal rate), so there is no need to work on a fine-grained analysis on a sub-optimal rate in their paper. Please tune your description when describing Xing et. al. (2021).\n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept