On the Algorithmic Stability of Adversarial Training
Authors: Yue Xing
Qifan Song
Guang Cheng
Venue: NeurIPS 2021 Poster (2021)
Keywords: Algorithmic Stability
Generalization

Abstract: The adversarial training is a popular tool to remedy the vulnerability of deep learning models against adversarial attacks, and there is rich theoretical literature on the training loss of adversarial training algorithms. In contrast, this paper studies the algorithmic stability of a generic adversarial training algorithm, which can further help to establish an upper bound for generalization error. By figuring out the stability upper bound and lower bound, we argue that the non-differentiability issue of adversarial training causes worse algorithmic stability than their natural counterparts. To tackle this problem, we consider a noise injection method. While the non-differentiability problem seriously affects the stability of adversarial training, injecting noise enables the training trajectory to avoid the occurrence of non-differentiability with dominating probability, hence enhancing the stability performance of adversarial training. Our analysis also studies the relation between the algorithm stability and numerical approximation error of adversarial attacks.

On the Algorithmic Stability of Adversarial Training
Yue Xing Department of Statistics Purdue University xing4 90purdue .ddu edu
Qifan Song Department of Statisties Purdue University gfsong@purdue. edu
Guang Cheng
Department Statistics Purdue University
chenggg@purdue. edu
Abstract
The adversarial training is popular tool to remedy the vulnerability deep learn- ing models against adversarial attacks, and there is rich theoretical literature the training loss of adversarial training algorithms. In contrast, this paper studies the algorithmic stability of generic adversarial training algorithm, which fur- ther help to establish an upper bound for generalization error. By figuring out the stability upper bound and lower bound, we argue that the non-differentiability issue of adversarial training causes worse algorithmic stability than their natu- ral counterparts. To tackle this problem, consider noise injection method. While the non-differentiabiliy problem seriously affects the stability of adversar- ial training, injecting noise enables the training trajectory to avoid the occurrence of non-differentiabiliy with dominating probability, hence enhancing the stability performance of adversarial training. Our analysis also studies the relation between the algorithm stability and numerical approximation error of adversarial attacks.
Introduction
Successful machine learning algorithms require not only good empirical performance but also generalizing well to unseen data. For the robustness towards unseen data, empirical experiments show that deep learning models can be fragile and vulnerable against adversarial input (Biggio et al. 2013 Szegedy et al.) 2014) To set example, in image recognition problems, a deep neural network predict wrong label when the testing image slightly altered, while the change is barely recognizable by human eyes (Papernot et al. 2016a).
Related research efforts in adversarial learning include designing adversarial attacks in various ap- plications (Papernot el al. 2016a b Moosavi-Deztooll et al. 2016). detecting attacked samples (Tao) al. 2018 Ma and Liu 2019). and modifications on the training process obtain adversarially
Tobust models, 1.c., adversarial training (Shaham et al. 2015 Madry et al. 2017 Dalal et al. 2017
However, although adversarial training improves the adversarial robustness during testing, its gener- alization performance is still poor. While Yin et al. (2018) 8) presented that the adversarial Rademacher complexity is never smaller than its natural counterpart, Schmidt al. 2018); Zhai al. (2019)
gued that a better adversarial generalization requires more abbeled/unlabelee data.
In the literature of natural DNN optimization via iterative gradient moves, the empirical loss each iteration can characterized by convergence rate analysis, yet generalization properties are not well understood. To characterize the generalization error, popular way is to study the algorithmic sta- bility. Algorithmic stability first considered by Kearns and Ron 1999); Bousquet and Elisseeffl (001] 2002). Later, Hardt et al. (2016) explored the connection between algorithmic stability and generalization performance of gradient-type optimization. Some follow-up research studies the sta- bility for different classes of algorithms, relax the definition of stability generalize its usage, see KKaezzan-Kebrya et al. (2018); Charles and Papailiopoulos
(2018); Kuzborskij and Lampert 20188 Zhou al. (20 Lei and Ying 2020)) Ho al. (2020); Madden et (2020).
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

In general, there are two ways to utilize algorithmic stability, On the one hand, as showed by Hardi al. (216)), the algorithmic stability provides an upper bound for the generalization error: hence it will be useful when establishing the convergence of generalization error. On the other hand, the algorithmic stability itself also a measure that evaluates the performance of an algorithm.
Our work extends algorithmic stability analysis to adversarial training. Our contributions are:
Through figuring out the stability upper bound and lower bound, we argue that adversarial training leads to poor algorithmic stability even the clean loss is smooth. To solve this problem, we propose inject noise into the adversarial training process. Although some existing works proposed the usage of noise injection, we highlight that such a method is more meaningful tion of the noise injection method is provided for wide range of data-generating models in several tasks, including both linear regression and logistic classification.
adversarial training than its natural counterpart. Theoretical justifica-
Noticing that, in practice, adversarial attacks are mostly approximated via numerical meth- ods. e.g., fast gradient method (FGM) or projected gradient method (PGD), our theory investigates the role of accuracy of attack approximation for the stability of adversarial training algorithms. In short, more accurate attack leads to better stability upper bound.
The effectiveness of noise-injected adversarial training is further generalized to the Loo attack. Compared with C2, fox training algorithm generally less stable.
Beyond the theoretical analysis under simple models, provide a theory in two-layer ReL.U network with lazy training (training the hidden layer) and observe the effectiveness of the noise injection method. We also obtain empirical evidence that for deep neural networks model, proper forms of noise injection and more accurate attack calculation (c.g., PGD-k over FGM) improve the generalization error.
2 Related Works
Theories in adversarial training To theoretically understand how adversarial training works, Sinha et al. (2018); Wang et al. (019a) investigated the convergence of adversarial training when the loss strongly convex w.r.t. data attributes. In this case, it can be shown that the gradient of adversarial loss w.r.t. model parameters is Lipschitz, leading to good stability. However, when the loss is not strongly concave in data attributes, Xingg et al. (202 figured out that adversarial training does not have a Lipschitz gradient even for linear regression. Some studies in deep neural networks (Gao et al. 2019 Zhang et 2020 Allen-Zhu and Lij 2020) studied the convergence of adversarial training loss, and Allen-Zhu and Li
(2020) also provided a theoretical guarantee of the adversarial testing loss when attack strength is small enough. Some other literature in the generalization of
adversarial training can be found in Khim and Loh
Loh 20188 Awasthi et al. 2020 ; Pinot et al. (221));
Xing et al. (202Tb).
Observations in deep learning In terms of empirical studies, He et al.
2019 Zheltonozhskii
al. (2020); Xie et al. (2020); Lee and Chandrakasan (2000); Wu et al. (2020) focused on improving the performance of attack/adversarial robustness in deep learning.
In the literature, there are several ways to improve the adversarial training, including modifying the objective function to help the convergence of the training process (Zhang et al. 2019 Wang al.)
2019b), regularization (He et al. 2019 Zheltonozhskii et al. 2020 Wu et al. (020). replacing non-
smooth components (Lee and Chandrakasan 2020; Xie al. 2020). and handling over-fitting issue
[Lee and Chandrakasan 2020).
Stability for non-smooth loss and min-max problem Besides works in the algorithmic stability of first-order optimization methods on smooth loss, Bassily et al. (2020) studied the case when loss is convex but not smooth. In this scenario, the minimax lower bound and convergence upper bound of stability together imply that stochastic gradient d (SGD) and gradient descent (GD) have poor stability. It is recommended to SGD/GD with extremely small learning rate for vast number of iterations, which implies that it is not practical to train a non-smooth model with good stability. Consequently, adaptations are essential for non-smooth models to improve the training process.
We are considering sample- haaplle-witt-epppeeee wwthhreee SGD.

---

Another recent work, Farnia and Ozdaglar (220)) considered the algorithmic stability in the min- max problems for generative adversarial networks (GAN) argue that simultaneous training in generator and discriminator leads to good stability. However, besides the prrongly-convex-coned assumption in their loss, the "min-max" problem considered in GAN and adversarial training are not the same. These two differences lead to different conclusions between GAN and adversarial training.
3 Stability of adversarial training
In this section, we study the uniform argument stability (UAS) of adversarial training. Utilizing the notations introduced in Section 3.1 present in Section 3.2 the upper and lower bounds of UAS.
Section 3.3 studies the effect of attack eπror on stability.
3.1 Notations
Adversarial training To introduce adversarial training, ler denote the loss function and fo(x) be the model with parameter 0. The (population) adversarial loss is defined
R(0, c) E (folæ + A.(fo.,, y)l
where A, an attack of strength > 0 and intends to deteriorate the loss in the following way Af x, y) == argmax (I(fo + +)),)). =0,,(00c)
(1)
where B, r) is a Cp ball centering at a with radius r. Given n ii.d samples S {(1,, ))) the adversarial training minimizes the sample version of R(0, e) w.r.t. 0:
Rs(0,e) Di Ac We, v:)l,
ni
i=1
and the estimator aims to minimize Rs(0.c) c). We rewrite Rs c) Rs(0) for simplicity when there is no confusion.
The minimization in 22 is often implemented through an iterative two-step (min-max) update. In the t-th iteration, calculate the adversarial sample 2[!") I; + Ac(forn Ti, ys) based on the current g(0) and then update ((++1) based on the gradient of the adversarial training loss while fixing (!))s with learning rate 7)- The algorithm runs for 7 iterations. A more detailed pseudocode is postponed to Algorithm [ when introducing our adaptations. Note that for some loss function or model fe- there may not be analytic form for A, (e.g. deep neural networks), and numerical methods, e.g. FGM and PGD, are utilized to approximate A.,
Risk decomposition Define ig and 0 as the minimizer of R and Rg respectively. Then for the algorithm output 0, the excess risk can be decomposed into four parts as below:
R - R(o)) = R(O) Rs
Rs
Rs( + Rs(Ø) - Rs(Ov) + Rs(Ov) - R(0b). (
Syen
Eopt
E=0
Since the last two parts are either negative or with zero expectation, we mainly focus on the first two parts, namely, generalization error R(0) (0) and optimization error Rs(0) (o) Based on Hardt et al. (2016). Egen is upper bounded by algorithmic stability.
Uniform argument stability (UAS) UAS aims to quantify the output sensitivity in La norm w.n.t an arbitrary change in single data point. An algorithm is X-UAS if for neighboring datasets S ~ S2 (i.e., S and S2 differ only in single data point), it satisfies that
sup (0(S)) 0(S))) sup X(S1, S2) S X.
8,-S2
S

---

where ||-|| represents the L2 norm. Under proper conditions, the UAS bound implies generalization
error bound (Bassily et 2020 if P([IA(S), Sa)Il 2 7) S Ki for any neighboring S2), then for any
Egen 2 2looon)))llo///// [0g(1/n)) P
]
S R + No.
(3)
n
3.2 Upper and lower bound
This section presents the upper bound and lower bound of UAS of adversarial training when its natural counterpart is convex and smooth.
The upper bound of UAS of adversarial training can be directly extended from Bassily et al. (0220) as follows:
Proposition Assume I(fo(z).V) is L-Lipschitz and convex w.r.t. 8, and E (2) The two models o and 655 are adversarial training estimators obtained using datasets S1, S2 respectively.
For SGD,
1)
+ E me n
|10
800 =0
sup EE SI-Sa
min r,
mi
The upper bound of GD is the same.
The following theorem presents the lower bound of UAS. For simplicity, we consider the case of constant learning rate, i.e., 1/t = 17 for L = l,,.,,
Theorem 1. Assume 0 B2(0,r) There exist some >> O and some loss function I(fo(1)) y) which is differentiable and convex w.r.t. 0, such that ti¹h and 6,"), which are SGD-based adversarial training estimators obtained using S1, S2 respectively under attack strength e, satisfies that
sup B((0(T - 0 = Ω min (1, T 72
nTT + nT
SI~S2
For GD, the lower bound is
sup (10 8 Ω min n.T + ?7) n ))
Sir02
To prove Theorem [ similar to Bassily et al. 2020)) we design a smooth clean loss function with two datasets S S2 and study the exact change of the model parameters. The detailed proof is postponed to the Appendix D
As discussed by Bassily al. (2020). the non-smoothness of the loss is the main reason for poor stability. The presented low bounds match the result of Bassily et al. all..((2))) (2020), but it is worth mention- ing that the results not directly comparable since [assily et al. (2020) studied the UAS of clean training when the loss function 1(fo(z);)) y) is non-smooth, while our work studies the UAS of adversarial training when the loss function is smooth. On the other hand, the UAS of cleaning training under smooth loss, implied by Theorem 3.8 of Hardt et al. (016)). is of order Ommin (r, L I mt/n))) Therefore, we conclude that adversarial training has worse stability than its natural counterpart.
To ensure the convergence of optimization (i.e., 1/T' is not so small) and the generalization perfor- mance (Proposition and Theorem [}. one may take T == n² and y = 1/n The resulting optimization error and stability then become ((1/v)), /T), which matches the minimax lower bound of excess risk (Chen et al. 2018). However, such a choice of (17, T)) is impractical and needs to improve (refer the discussion in Bassily al. 2020
3.3 The role of numerical attack error
In real-world applications, calculating the exact attack A, for general models not easy, and usually, numerical approximation A', (c.g., by FGM or PGD) is used in the adversarial training algorithm.

---

Some recent literature start to aware the important impact of the numerical attack error (i.e.. the difference between A, and A²). For example, Gao et al. (2019) Zhang et al. (2020) took account of the attack approximation method in the convergence analysis of adversarial training, and Deng et al.
(020)) studied the convergence of PGI) attack.
For algorithmic stability, extended from Proposition |I the following result considers the effect of attack error. Comparing the upper bounds of Proposition I and Corollary it suggests one control
the attack error carefully in the adversarial training.
Corollary 1. Under the same conditions of Proposition | assume the algorithm uses an approxi- mation A' instead of the exact attack A, with attack error min ||A,(1, y. w) A' A'(x, w)ll < Ac for any (x. y, w), where the minimum is taken when the exact attack (i.e., 4 not unique. Assume V (ol(fo( (x), u) is k-pipschitz w.r.. Then, for SGD
T
sup B110T - 11 S1-82
-
min
L
Σ t=1
2 m
+
-i=1
The
k
Σ 7/2
1=1
The upper bound of GD is the same.
Besides the convex case, some discussions for non-convex case can be found Appendix A observations are similar.
The
4 Improving the stability
In this section, we show that injecting noise in adversarial training enhances the smoothness of adversarial loss, and hence improves the stability of adversarial training.
4.1 Source of non-smoothness
As mentioned after Theorem 1 the non-smoothness issue in adversarial training is the main cause of the poor stability. Summarizing from the related works, we identify two important sources of non-smoothness in adversarial training even when the standard loss is smooth: (1) when the data overfitted, i.e., the training loss is almost 0 and V (z,(((())))) yt) Rs 0, the adversary has no preference on the attack direction at 24, and the numerical estimation of A. is not stable, which possibly leads to an unstable update iteration of ad versariia training; (2) there exists certain set of 0, such that the adversarial training loss always non-differentiable regardless of the training data, even when its natural counterpart is smooth. For example, in linear regression, when 0g is closed to the null model, the non- moo-soothhesss issue occurs (Xing et al., 2021a).
To tackle both non-smooth issues, we propose incorporating noise injection in the training process as described in the following section.
4.2 Injecting noise during training
In this section, we present the noise injection algorithm in adversarial training and provide some theoretical justifications.
Algorithm below illustrates the details of the noise injection method. The basic idea behind this is that: the smotthnsss of adversarial loss occurs only when A and x, belong to certain special region (e.g., in linear regression, when 0 closed either zero when 0 x; = v1), thus injecting some small noise to both 0 and x helps them to escape from such region where moosthotssssss occurs, which further ensures the Lipschitz continuity property.
Remark 1. The Gaussian noise in Algorithm for proof simplicity. In general, it can be chunged to other noise distributions if the tail not heavy.
In the literature, there have been some applications of noise injection. For example, He et al. (2019) considered injecting noise to the weights as a regularization method to improve the adversarial robustness. Besides literature in supervised learning (Weng et al. (2018); Wang et al. (2018); Ford al. (2019), injecting noise in data was also considered to stabilize the training process of GAN
Arjovsky and Bottou 2017 Jenni and Favaro 2019
5

---

Algorithm Add noise to weight and data
Input: data { y/) 1i-1 number of iterations T, learning rate { Y attack strength e, noise size (Co: Ew), scale parameter r, initialization g(0)
for f = to T do
Add Gaussian noise with variance L to each dimension of 0g to form 000) and add Gaussian noise with variance < to each dimension of æt to obtain Ti,-
Calculate the attack (based on T., and ((t)) as Zhc Take gradient w.r.t (()) on l[face (2i,), yb.) Update g(e) to g(++1) with rate 7)--
Project ((++1) onto r2, end for
Output: ((T).
In the following theorems, we provide a theoretical justification for the stability and optimization when injecting noise into adversarial training for the following models:
Linear regression: ((fo()), v) = (x: To y)²
Logistic regression: l(fo(r),)) = - llog (ogg(v=l)(p)) (p) - log -y== 11 p), where p =
p(x 0) = 11(1 + + 0).
Smooth hinge loss: the hinge loss max(0, vxT is not smooth at 0, hence approx-
imated by (z), 3) (1 y(x H) y(x' 0))/h), where h a bandwidth
parameter, and И is a smooth approximation of the indicator function 1(x 2 0}. The detailed conditions on H are postponed to Lemma in the Appendix D.2
The following assumption is imposed on the data:
Assumption 1. The independent variable E Rd follows multivariate Gaussian distribution with zero-mean and whose eigenvalues are bounded and away from zero.
For regression, Elyl and B||yz||| are finite. For some constant C' > 0, any O E B2(0, satisfies P[[x" yl E [Sr,, (ar)) = O(22 - for Č1, (2 0.
For classification, the label is y E {=1}. The upper bound satisfies r/ max;= ||:||| 0.
The Gaussian assumption in is merely for derivation simplicity. The assumptions w.r.t. regression avoids |x: f yi from clustering around zero when |[0]/rr approaches zero. A linear model Efy|r] 0f x with Gaussian noise satisfies Assumption
Given the above problems and data generating models, the following lemma studies the smoothness (i.e., the Lipschitz constant) of Vol(fo(x) w), and of the gradient of noise injected adversarial loss.
Assume Assumption 7 hhold. Denote L the Lips- chitz constant of (f)(), Hj) w.r.t. 0 for any x E B2(1;, 2e) and all Sj n. Then, in probability, L is bounded by some finite L*. Take the noise injected in data zero-mean Gaussian with vuri- ance (E%/d)Ia. and the noise injected in parameters is zero-mear Gaussian with variance (E? /d)La where { = EoL". Denote E(0 + 8, I. y) as the event that Vol(fe+s(2 + Ac(fots T. v)), y) is B" /Ç- Lipschitz for some B* > O. There exists some choice of (E, + such that with probability tending to
Lemma 1 (Informal Statement for Lemma
the generation of S, uniformly for all B2(
P (EE + (, S) o(1).
The formal statement is postponed to Lemma in the appendix.
Let P(E7)S) suppEE. P 5, vz. E S) in what follows, for notation simplicity.
Remark 2. The terms L are generic representations. For different loss functions and data dimen- sion d, their values may change. In addition, the exact rate of P (EE))) is affected by the value of L well &, C. We postpone the details Appendix D.2 during the proof.

---

The following lemma is an intermediate step in the derivation of Theorem 2 below, and reveals the important role played by B* B²/ /Ç. Note that since Lemma I holds over the randomness of S, instead of uniform argument stability, we turn to bound similar to hypothesis stability (Bousquet and Elisseeff, 2002) for the following results. To simplify the representation, the values 1 are treated as constants in the following main text.
Lemma 2. Under the same conditions as in Lemma uniformly for all L,..,, Tu with probability tending to one over the generation of S1 ~ S2 where the i-th sample is replaced, for both GD and SGI, given 110[" 1)
11 1 it follows that
BlI10( 2 12 S1, S2, Ac-1l (1 (1+2n) 2nd
2 C²
1m 2 {
A reminder,
where the detail of reminder term can be found in S in Appendix D.2 Note that the expectation
taken on ||0(0) -189)88 " in GD is over the injected random noise, and the one for SGD is taken for both the sampling in SGD and the injected random noise.
Lemma illustrates the relationship between 10(00) - 0 and 2--1 Recall that B²/S is the Lipschitz constant of Vol(fo+s( + A), y). When 1tt 2 C/B", larger Lipschitz constant implies a larger upper bound of stability. When taking do < </B", we have the following result:
Theorem 2. Under the same conditions as in Lemmal 7 when taking ne C//",, for both GD and SGD, with probability tending to one (where the probability refers to the generation measure of the distinct independent samples in S₁ S2).
B((I0(T) 11T1 o [[IISSS))=O(VVSSSS=EFF-FEFF-
o (1 PLEAIS))+ +
Σ
n
1=
T
+0
PPE
S1) + P(E
Σ
n
tmfo
Furthermore, extending from Lemma of Bousquet and Elisseeif 2002). the generalization gap is upper bounded using hypothesis stability as follows.
Proposition 2. Assume E B2(0, r). Denote ((S) as the model obtained based on dataset S using some algorithm. Assume l(fo(z). v) E [0. M] when || I vdlog n, we have for any i 1.... n,
E (R(((S))- - Rs, (((S)))
M
+
sup (EB2(0.r)
((fo(x A.). Vdgog
2n
+ 3ME
| (o. + A.). 1[B[sz) Ae). ()..)))
where Sh represents the neighboring dataset of S₁ whose ith sample replaced. The notion A, is an abbreviation of the attack A. x, v) or (f, wt).
Note that the last term on the RHS of 4 can be bounded according to the result of Theorem under Lipschitz condition of the adversarial loss I[ (I; + Az), y₁). The second term on the RHS of can be bounded given some further conditions on the tail behavior of loss function.
Compared with the generalization upper bound obtained in Bousquet and Elisseeff (2022) in Propo- sition 2 there is an extra term corresponding to ||^||| > Vd n. In Proposition 2 we only assume ((fo()))) v) [0, .M] when ||x Vdl n, which weaker than the uniform bounded assumption
in Bousquet and Elisseeff 2002)
Besides, we also establish the optimization error bound. The following theorem presents the con- vergence of noise-injected adversarial training when = For the proof, one can refer to the Appendix D.2
7

---

Theorem 3. Under the same conditions as in Lemma 1 for both GD and SGD, 0
argminge B)(0,)) Rs( when f) = T
E min Rs(((0)- min R0( (E.r(),r)
Bl1000 - 01.
B(ll0(T) - -s13|s)
1.....
2n/T
2n/T"
(T')²
+ +
Theorem presents the convergence of adversarial training loss throughout the training. Under the boundedness and 5 Lo when (1), To) chosen properly (e.g. (1)7) + oo and ço - 0)
and A. 0, the adversarial training loss converges to its minimal asymptotically.
It is noteworthy that the general design of Algorithm L does not specify the noise distribution.
While in Section we use Gaussian noise to justify our theorems under linear regression empiri- cally, different forms of noise can be utilized for complex models, refer to our experiments on deep neural networks in Section 2
If an intercept term exists in the loss function, e.g., 1 regression, the analysis is similar to Lemma ! leading to the same final conclusions as in Theorem Land
Remark 3.
(0 +
y)² for linear
Remark 4 (Coc Attack in Adversarial Training). In general, the stability of Lo adversarial training worse. To set an example, we consider the linear regression setup. For L2 attack, the gradient of adversarial loss is not Lipschitz only when 0 approaches zero 0Jx is closed y. Under Loc attack, the adversarial loss becomes
(= 2)² +211011 2011011|==T0- y/.
indicating there is much larger set where the C adversarial loss is not smooth.
Noise injection is still helpful remedy the non-smooth issue for Loo adversarial training and leads to results similar to Theorems 2 [nnd However, one will derive a worse upper bound for the stability and optimization error. Refer Appendix for more detailed arguments.
4.3 Numerical illustration
We use simulation to illustrate how noise-injected adversarial training affects performance. In short, the quality of the updating gradient is better after injecting noise. The Lipschitz constant of (ol(F + A),y) in Lemma is smaller.
We consider linear regression problem in this experiment. The data is generated using y x TT with x N Ia) with d 10 and 5 ~ NO, d²). The coefficient Og is taken as 07 1 1/vd for i = 1, d. The variance of noise is taken as o² = and attack strength is = 2. We randomly generated 1000 samples.
To train the regression model, we train = 500 epochs with learning rate = 0.01 and initializa- each iteration, we calculate (((()) (00-)
tion ((0)
((--1) || as an
approximation for the Lipschitz constant of the gradient, where v (f( is the averaged gradient of adversairal loss for the ith batch of data S,. Based on Lemma 2 a larger Lipsehitz constant (B" /?) indicates worse stability, which is the right tail of the histogram. The results are summarized the histograms Figure M
From the left three histograms in Figure | one can see that injecting noise on parameters and data (where we set & = Eu = )) leads to a smaller distribution of Lipschitz constant for v v.(())()), in terms of right tail percentile. For the right two histograms in Figure I smaller batch size implies a heavier tail in the distribution of Lipschitz constant due to larger stochastic noise in estimating (((()))
Besides the experiment showing how noise injection affects the training process, we also conduct simulation to illustrate the effect attack error on the generalization. Due to space limit, simulation is postponed to the Appendix B To briefly summarize the observations, for all scenarios we consider, when there is an error when calculating the attack, the generalization gap becomes larger.

---

X---, so6th-100
xi.. 02, batch-100
X1-0.01, batch-100
X--5. batch-10
0/913
0.033
3.023
0.00
3.035
60056
0.000
0.034
0.022
0.000
0.99
200
0.000
3.00
Valuo
Valuo
10.05
- || Po.; = 1/ for i = =1, 1...., d 1000, o c= 0.01, 500. Vanishing initialization. implies smaller Lipschitz gradient of (.())) The (mean, sd, 99. ---uunillle are (178.90, 22.34, 323.36), (167.72, 19.20. 234.43), (174.95, 20.71, 247.93), (163.05, 34.89, 337.07) for the above four histograms.
Figure 1: Density of - with d 10.
larger
Exploration in Neural Networks
While main contributions are for statistical models, also provide some theoretical results and numerical experiments associated with neural networks.
It is still an open question how to connect existing algorithmic stability tools to neural networks. Since the number of parameters in neural networks much larger than simple models, a simple bound on ||0]7] - 0 is not useful. Instead, we consider two-layer neural network with lazy training and vanishing initialization in regression and provide stability bound directly on the loss. In order to track the neural network parameters, we track both the convergence and the stability together. This is more restrictive than simple models.
The following (informal) statement presents the stability of two-layer nonlinear networks with lazy- ing training adversarial training setup. The formal statement of the theorem is postponed to Appendix C.T Based on the following theorem, under proper configurations, the noise-injected training neural networks improve the stability:
Theorem (Informal Statement). For two-layer nonlinear (including ReLU) networks, with proper initialization and training configurations, training only on the hidden layer with proper noise injec- tion, it satisfies that
Es (1fg [x Ii,
- Mooog
1ofggll 1x + Aclf (r Iz V.)l,
= o =
(( L LVPLEE) +
I
L + LP(E") nI + rem.
nVT
n
where rem = o(1 and is not the dominant term.
There are two differences between Theorem and the results in simple models. First, it is not useful to directly assume the weights of the neural network parameters within large ball and put this large number into the bound, thus we simultancously study the convergence and stability of the neural network to tighten the stability bound. Second, instead of bounding the stability of the parameters, we turn to bound the stability of the loss, which is more meaningful to this over-parameterized method.
Besides the results in two-layer networks, we also numerically study the generalization gap using deep neural networks with CIFARIO dataset. Due space limit, postpone the experiments to Appendix C.2 The observations from numerical experiments are (1) injecting noise can reduce the generalization gap between training and testing performance, and (2) improving the accuracy of attack also improves the quality of the adversarial training. Both of the observations are similar to those in simulations.
6 Conclusion
In this paper, we evaluate the algorithmic stability of the adversarial training method. Based on the lower bound and upper bound of UAS, reveal that the naive adversarial training is not stable

---

as its natural counterpart. To improve the stability, we argue that it is helpful to inject noise into model parameters and imput data. Our theory verifies the effectiveness of noise injection in some simple models. Besides, our theory also considers the effect of attack error and indicates that the upper bound of UAS is smaller when the attack error smaller.
The above theoretical investigations emphasize the usage of noise injection and controlling numer- ical attack error during the adversarial training. These theoretical insights are well validated by our simulations under simple regression models.
There two future research directions motivated by this study. Although we observe similar phenomenon in deep neural networks as our theory in simple models, there is a gap between the exact algorithmic stability of deep neural networks and the UAS bounds in simple models. Our analysis in the two-layer neural networks is a trail in this area, but a more comprehensive study study on algorithmic stability of the deep neural network is wanted. Second, as mentioned in the numerical experiments, a wider neural network has a poor attack. Corresponding theoretical explanation is also an interesting topic.
Acknowledgements
This project is partially supported by NSF-SCALE M0DL(2134209) and NST-DMS-1811811.
References
Allen-Zhu, Z. and Li, Y. (2020), "Feature Purification: How Adversarial Training Performs Robust Deep Learning," arXiv preprint 200::::0000000090000
Arjovsky, M. and Bottou, L. (2017), "Towards principled methods for training generative adversarial networks." arXiv preprint 1rX1v:1701.04862.
Awasthi, P., Frank, N., and Mohri, M. (2020), "Adversarial learning guarantees for linear hypotheses and neural networks," in International Conference Machine Learning, PMLR, pp. 431-441,
Bassily, R., Feldman, V., Guzmán, C., and Talwar, K. (2020), "Stability of Stochastic Gradient Descent Nonsmooth Convex Losses," arXiv preprint arXiv:2006.06914.
Biggio, B., Corona, I., Maiorca, D., Nelson, B., Šındié, N., Laskov, P., Giacinto, G., and Roli, F. (2013), "Evasion attacks against machine learning at test time," " in Joint European Conference on Machine Learming and Knowledge Discovery in Databases, Springer, pp. 387-402.
Bousquet, O. and Elisseeff, A. (2001), "Algorithmic stability and generalization performance," in Advances in Neural Information Processing Systems, pp. 196-202.
- -(002), "Stability and generalization," Journal of machine learning research, 2, 499-526.
Charles, Z. and Papailiopoulos, D. (2018), "Stability and generalization of learning algorithms that converge to global optima," in International Conference on Machine Learning, pp. 745-754.
Chen, Y.. Jin, C., and Yu, B. (2018), "Stability and convergence trade-off of iterative optimization algorithms," arXiv preprint 10X1:11844.0669,
Deng. Z., He, H., Huang. and Su, W. (2020), "Towards Understanding the Dynamics of the First-Ordes Adversaries.".
Ding, G. W., Wang, L., and Jin, X. (2019), "AdverTorch v0.1: An Adversarial Robustness Toolbox based on PyTorch," arXiv preprint /002.07600
Farnia, and Ozdaglar, A. (2020), "Train simultaneously, generalize better: Stability of gradient- based minimax learners," arXiv preprint arXiv:2010. 12561.
Ford, N., Gilmer, J., Carlini, N., and Cubuk, D. (2019), "Adversarial examples are natural conse- quence of test error in noise." arXiv preprint arXiv:1901.10513.
10

---

Gao, R.. Cai, T., Li, H., Wang, L., Hsieh, C.-J., and Lee, J. D. (2019). "Convergence of adversarial training in overparametrized networks," arXiv preprint arXiv:1906.07916
Hardt, M., Recht, B., and Singer, Y. (2016), "Train faster, generalize better: Stability stochastic
gradient descent," in International Conference Machine Learning, pp. 1225-1234
He, Z., Rakin, S., and Fan, D. (2019). "Parametric noise injection: Trainable randomness to improve deep neural network robustness against adversarial attack," in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 588- 597.
Ho, N., Khamaru, K., Dwivedi, R., Wainwright, J., Jordan, M. L., and Yu, B. (2020), "Instability, Computational Efficiency and Statistical Accuracy," arXiv preprint arXiv: 1411.
Jalal, A., Nyas, A., Daskalakis, C., and Dimakis, A. G. (2017), "The robust manifold defense: Adversarial training using generative models,"
Jenni, S. and Favaro, P. (2019), "On stabilizing generative adversarial training with noise," in Pro- ceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 12145-12153.
Kearns, M. and Ron, D. (1999), "Algorithmic stability and sanity-check bounds for leave-one-out cross-validation." Neural computation, 11, 1427-1453.
Khim, J. and Loh, P.-L. (2018), "Adversarial risk bounds via function transformation." arXiv preprint arXiv:1810.09519.
Kuzborskij, I. and Lampert, (2018), "Data-dependent stability of stochastic gradient descent," in International Conference on Machine Learning, pp. 28 2815-2824.
Lee, K. and Chandrakasan, A. P. (2020), "Rethinking Empirical Evaluation of Adversarial Robust- ness Using First-Order Attack Methods," arXiv preprint arXiv:2006.01:: 01304.
Lei, Y. and Ying. Y. (2020), "Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descent," arXiv preprint (xXXi:2006.08155
Ma, and Liu, (2019), "Nic: Detecting adversarial samples with neural network invariant check-
ing." " in Proceedings of the 26th Network and Distributed System Security Symposium (NDSS 2019).
Madden, L., Dall' Anese, E., and Becker, S. (2020), "High probability convergence and uniform stability bounds for nonconvex stochastic gradient descent," arXiv preprint vrXiv:2006.056/1
Madry, A., Makelov, A., Schmidt, L., Tsipras, D., and Vladu, A. (2017), "Towards deep learning models resistant to adversarial attacks," arXiv preprint 17xvv:706.0608
Moosavi-Dezfooli, S.-M., Fawzi, A., and Frossard, (2016), "Deepfool: simple and accurate method to fool deep neural networks," in Proceedings of the IEEE conference on computer vision and patlern recognition, pp. 2574-2582.
Papernot, N., McDaniel, P., Jha, S., Fredrikson, M., Celik, Z. B., and Swami, A. (2016a), "The limitations of deep learning in adversarial settings," in Security and Privacy (EuroS&P), 2016 IEEE European Symposium on, IEEE, pp. 372-387.
Papernot, N., McDaniel, P., Swami, A., and Harang, R. (2016b), "Crafting adversarial input se- quences for recurrent neural networks," in Military Communications Conference, MILCOM 2016- 2016 IEEE, IEEE, pp. 49-54.
Pinot, R., Meunier, L., Yger, F., Gouy-Pailler C., Chevaleyre, Y., and Atif, J. (2021), "On the robustness of randomized classifiers to adversarial examples," arXiv preprint 10875.
Ramezani-Kebrya, A., Khisti, A., and Liang, B. (2018), "On the Stability and Convergence of Stochastic Gradient Descent with Momentum," arXiv preprint S1KY::889900455
Rice, I.., Wong, E., and Kolter, 7. (2020), "Overfitting in adversarially robust deep learning." arXiv preprint 11559.

---

Schmidt, L., Santurkar, S., Tsipras, D., Talwar, K., and Madry, A. (2018), "Adversarially robust generalization requires more data," Advances Neural Information Processing Systems, pp. 5014-5026.
Shaham, U., Yamada, Y., and Negahban, S. (2015); "Understanding adversarial training: Increasing local stability of neural nets through robust optimization," arXiv preprint arXiv: /51 1515.33...
Shorten, C. and Khoshgoftaar, M. (2019), "A survey on image data augmentation for deep learn- ing." Journal of Big Data, 6, 1-48.
Sinha, A., Namkoong, H., and Duchi, J. (2018), "Certifying some distributional robustness with principled adversarial training.".
Szegedy, C., Zaremba, W., Sutskever, I., Bruna, J., Erhan, D., Goodfellow, I. J., and Fergus, R. (2014), "Intriguing properties of neural networks," in 2nd International Conference on Learning Representations.
Tao, G., Ma, S., Liu, Y., and Zhang, X. (2018), "Attacks meet interpretability: Atribbue-steered detection of adversarial samples," in Advances in Neural Information Processing Systems, pp- 7717-7728.
Wang, B., Yuan, B., Shi, Z., and Osher, S. J. (2018), "Resnets ensemble via the feynman-kac for- malism to improve natural and robust accuracies," arXiv preprint arX1v:1811.10745.
Wang, Y., Ma, X., Bailey, J., Yi, Zhou, B., and Gu, Q. (2019a), "On the convergence and robust- ness of adversarial training." in International Conference on Machine Learning, pp. 6586-6595.
Wang, Y., Zou, D., J., Bailey, J., Ma, X., and Gu, Q. (2019b), "Improving adversarial robustness requires revisiting misclassified examples," in International Conference on Learning Representa- tions.
Weng, T.W... Zhang, H., Chen, P.Y Yi, J., Su, D., Gao, Y., Hsieh, C.-J,, and Daniel, (2018), "Evaluating the robustness of neural networks: An extreme value theory approach," arXiv preprint arXiv:1801. 10578.
Wu, D., Wang, Y., and Xia, S.-t (2020), "Adversarial Weight Perturbation Helps Robust General- ization," arXiv preprint arXiv:2004.0s: 05884..
Xie, C., Tan, M., Gong, B., Yuille, A., and Le, Q. V. (2020), "Smooth Adversarial Training," arXiv preprint ar arXiv:2006. 145:36006.14366
Xing, Y., Song, Q., and Cheng, G. (2021a), "On the generalization properties of adversarial training." in International Conference on Artificial Intelligence and Statistics, PMLR, pp. 505-513.
Xing, Y., Zhang, R., and Cheng, G. (2021b), "Adversarially Robust Estimate and Risk Analysis in Linear Regression," in International Conference on Artificial Intelligence and Statistics, PMLR, pp. 514-522.
Yin, D., Ramchandran, K., and Bartlett, P. (2018), "Rademacher complexity for adversarially robust generalization," arXiv preprint 1810.1181001110
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 4rXiv:1906.0055:
Zhang, H., Yu, Y., Jiao, J., Xing, E. P., Ghaoui, L. E., and Jordan, M. I. (2019), "Theoretically Principled Trade-off between Robustness and Accuracy," Proceedings of the 36th International Conference on Machine Learning. PMLR, vol. 97 of Proceedings of Machine Learning Research, pp. 7472-7482.
Zhang, Y., Plevrakis, O., Du, S. S., Li, X., Song, Z., and Arora, S. (2020), "Over--arameteriieed Adversarial Training: An Analysis Overcoming the Curse of Dimensionality." arXiv preprint arX1v:2002.06668.
12

---

Zheltonozhskii. E., Baskin, C., Nemcovsky, Y., Chmiel, B., Mendelson, A., and Bronstein, A. M. (2020). "Colored Noise Injection for Training Adversarially Robust Neural Networks," arXiv preprint arXiv:2003.02/88.
Zhou, Y., Liang, Y., and Zhang, H. (2018), "Generalization emror bounds with probabilistic guarantee for sgd in nonconvex optimization," arXiv preprint arXiv:1802.06903..
8 Checklist
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. We mention some limitations when discussing potential extensions in Conclusion.
(c) Did you discuss any potential negative societal impacts of your work? No. This paper studies theories and only uses CIFAR- 10 for real-data experiment.
(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 exper- imental results (either in the supplemental material or as URL)? No. We mention in the main text that we are using some implementation from other papers shared in Github.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? Yes.
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? Yes.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? No. From the design of the algorithms, they are similar to the original adversarial training algorithm, so the computation complexity does not change lot.
13


Reviews:
[{"review_id": "qieVKZCJ9wr", "reviewer": "Reviewer_Sgsz", "summary": "This work builds upon Bassily et al. and extends stability analysis to adversarial training algorithms. The authors use uniform algorithmic stability to derive lower and upper bounds on the robust accuracy.  Based on the theoretical analysis, they argued that non-differentiability (or gradient-masking) reduces the stability of adversarial training, which leads to the significant gap between training and testing robust accuracy. To reduce the generalization gap, the authors suggest using noise injection into the parameters and the input of the models.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "### Originality:\n- The work extends in a novel way uniform stability analysis to adversarial training algorithms.\n- The authors provide bounds in case of an imperfect attack, which is the case in all applications of adversarial training.\n\n### Quality:\n- The paper gives new insights into adversarial training and in a way explains catastrophic overfitting with weak adversaries.\n- The claims seem to be theoretically sound and correct.\n\n### Clarity:\n- The paper is well motivated and superbly written.\n\n### Significance:\n- The developed insights may lead to the development of new robust training algorithms.\n\n### Questions to the authors:\n1) The bounds for SGD does not depend on the batch size, which seems to be counterintuitive. Can the authors clarify that?\n2) Is the input noise injection equivalent to random start for PGD adversarial training? If it is not, what are the differences?\n3) What do the authors mean by vanishing initialization in Figure 1 as it is not clear from the context?\n4) In appendix A remark 4, the authors state \"adversarial training prefers a smaller number of steps to reduce the\ncorresponding UAS upper bound\". It seems to be correct for training with weak adversaries but incorrect for training with strong adversaries, since robust training with a strong adversary requires many more iterations. Can the authors clarify if I am wrong?\n5) In appendix C2.1, noise injection and data augmentation reduce adversarial test accuracy. Can the authors comment on this result?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "### Limitations:\n- Limitations of the work are discussed.\n\n### Societal impact:\n- The authors did not discuss societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "gRNM1v_eNuk", "reviewer": "Reviewer_MT9T", "summary": "The paper investigates the stability of adversarial training when using SGD/GD, motivated by the stability analysis of Bassily et al. (2020) and Hardt et al. (2016) in the standard learning model.\nIn order to improve stability, the authors suggest injecting noise into the weights and data\n(this was already investigated, see for example - Adversarial weight perturbation helps robust\ngeneralization, Neurips2020).\nMoreover, theoretical analysis is also provided for Linear Regression, Logistic Regression and learning with hinge loss.\n", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The main contributions are on the theoretical side.\nMy main concerns are about originality/novelty. The upper and lower bound on stability are adaptations of the claims of Bassily et al. (2020).\nMoreover, methods of weight perturbation were already investigated empirically  (see for example - Adversarial weight perturbation helps robust generalization, Neurips2020), and some theoretical justifications were also provided in follow-up papers.\n\nMoreover, there are glaring omissions in the literature review, especially on the theoretical side and regrading weights perturbation methods.\n\nOn the other hand, I think that the main research question is interesting and important. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "-", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "a61kcx2hY1", "reviewer": "Reviewer_ZiiQ", "summary": "This paper provides the argument stability bound for adversarial training for linear models and 2-layer NNs with or without noise injection. The stability has a direct connection to the generalization bound. The contribution is mainly on the theoretical side. Motivated by the non-smoothness in AT which causes poor stability, the paper proposes to inject noise during training for both weight and data. Theory and simulation results justify noise injection on improving stability and shrinking generalization gap.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Pros:\n- Provides the first lower bound and upper bound for uniform argument stability (UAS) for AT\n- Considers numerical attack error in inner maximization which better models the real scenario\n- Theoretically analyzes how noise injection improves the stability\n- The paper is well written and easy to follow.\n\nCons:\n- The theoretical results are limited to linear models (linear/logistic regression, smooth hinge loss) and two-layer NNs. Moreover, The UAS bounds without noise injection seem to be limited to convex and L-Lipschitz loss. Not sure whether it is a standard condition for UAS community.\n- The connection of UAS bound to generalization error bound seems not that direct:\n  - What are the proper conditions for Eqn. (3)? It seems that Eqn. (3) only relies on the argument stability but not any other properties of the model $f_\\theta$ itself, which is a bit weird. Are there any assumptions here, e.g., $f_\\theta$ is a linear model, $f_\\theta$ is convex or $L$-Lipschitz?\n  - Can Theorem 1 and Corollary 1 be extended to provide generalization bound for GD/SGD trained models? Do we need to further assume the tail distribution of $\\sup \\mathbb{E} ||\\theta_1^{(T)} - \\theta_2^{(T)}||$? Why do we have such generalization bound for noise injection (Proposition 2) regime but not for the normal regime?\n\nMinor:\n- What does $B$ stand for in Lemma 1?\n- It would be better if the $x$-axis scales in Figure 1 could be the same to allow for direct comparison.\n- I like the empirical evidence in C.2.1 that shows how noise injection shrinks the generalization gap in real-world data. Maybe move it to the main text?\n\nI don't work in theory and didn't check the correctness of the proof. While it appears to me that UAS bounds provide a new perspective on analyzing the generalization and stability for AT, and the UAS bounds in this paper are technically nontrivial. I tend to support the acceptance but would adjust my evaluation based on theory reviewers.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors adequately addressed the limitations. As a theory paper, the potential negative societal impact of their work is little.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "F6tvrOuDZvm", "reviewer": "Reviewer_6caz", "summary": "This paper studies the theory of adversarial examples from the angle of algorithmic stability. More precisely, the authors characterize the algorithmic stability of the now famous adversarial training scheme. Their main findings can be summarized as follows. \n1) Even if the loss function utilized during adversarial training is smooth, the adversarial perturbation applied to the input image causes some non-differentiability issues which impede guaranteeing a good algorithmic stability in the worst-case scenario.\n2) The numerical approximation error of adversarial attacks used during training can have an impact on the algorithmic stability of the scheme. \n3) Injecting noise to the learning procedure helps to make the loss function smooth again; hence restoring the algorithmic stability with high probability.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Relevance: \nThe problem of designing models that are robust against adversarial attacks is a burning issue both in academia and in the industry right now. As adversarial training is one of the most efficient strategies against this problem, it is important to better understand this technique from a theoretical standpoint. Hence, the main focus of this paper is completely relevant to the machine learning community. \n\nClarity:\nI had some troubles following some parts of the paper. I feel like the overall point could be much more convincing if the author were to reorganize and focus their contributions, at least in the main paper. For example, Lemma 1 seems overcomplicated in its current form because the authors wanted to encapsulate several Lemmas at once (as explained in the appendix). To clarify the contributions and to make the paper more readable, I would suggest that the authors focus on presenting results for the linear regression and leave similar findings with other models to the appendix. Note that results are actually demonstrated in the appendix only for the regression case anyway, and extensions are left to the reader. Similarly,  Algorithm 1 (while it is quite straightforward) seemed a bit vague at first sight. To my point of view,  very generic statements such as «Add noise with size $\\eta$» do not convey a clear point. I think the paper would benefit from focusing on the Gaussian noise injection, as it is the distribution that is used to demonstrate all the results.\n\nQuality:\nI had some trouble evaluating the soundness of the technical results because of the clarity issues mentioned above. Also, I am a bit uncomfortable with the way the authors demonstrate their statements. Some results (Lemma 1, Propositions 1 and 2, Corollary 1) are not provided with any formal proof. Some others (Theorems 2 and 3) are demonstrated only in the case of the linear regression. Even though the results presented in Appendix and existing works in the domain might be sufficient to provide simple proofs for these results, I feel like this should not be the reviewer’s (nor the reader’s for that matter) job to check for the soundness of the statements by combinations of different (rather technical) results . I think the authors should provide clear proofs for the result they state, even if those are very simple. As in the clarity section, I suggest providing clear statements with proofs at least for the regression case in the main paper and provide some leads for generalizing the results in the appendix. \n\nOn the experimental part, I felt that the point was rather not very convincing and was not sufficiently correlated with the results. This impression comes mostly from the fact that 1) the mean of the Lipschitz constants with and without noise injection do not seem to differ in a significant way and 2) low-dimensional intuitions are usually misleading when dealing with adversarial examples. This problem on the experimental part is not my main concern because this is a theory paper, but I think it would be better to either present more convincing results or simply no experiments at all.\n\nOriginality and Significance:\nI am might not be fully aware of the literature but I think that studying adversarial training through the scope of algorithmic stability is a new idea. The proposed solution of injecting noise is not very surprising (looking at the literature on algorithmic stability and specifically on the link between differential privacy and algorithmic stability) but the authors have the merit of using this solution in a new problem. I think the overall idea has some merit and this paper could become an interesting first step toward a better analysis of adversarial training once the technical content is polished. \n\nSome bibliographical notes: Here are some missing works that I think are worth mentioning.\n\nOn generalization of adversarial machine learning\n\n[1] J. Khim, et al. ‘‘Adversarial risk bounds for binary classification via function transformation’’ 2018\n\n[2] P. Awasthi, et al. “Adversarial Learning Guarantees for Linear Hypotheses and Neural Networks” 2020\n\n[3] R. Pinot, et al. ‘‘On the robustness of randomized classifiers to adversarial examples’’ 2021\n\nOn using noise injection to stabilize the model against adversarial attacks\n\n[4] B. Wang, et al. ‘‘ResNets Ensemble via the Feynman-Kac Formalism to Improve Natural and Robust Accuracies’’ 2019\n\n[5] J. Cohen, et al. ‘‘Certified Adversarial Robustness via Randomized Smoothing’’ 2019\n\n[6] N. Ford, et al. ‘‘Adversarial Examples Are a Natural Consequence of Test Error in Noise’’ 2019\n\n[7] T. Weng, et al. ‘‘Evaluating the robustness of neural networks: an extreme value theory approach’’ 2018\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "As this is mostly a theory paper, I do not see any potential negative social impact. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "Between 5 and 7 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The large generalization gap of adversarial training is a central problem of adversarial robustness. This paper makes the first attempt to study this problem from an algorithmic stability point of view. The authors establish upper and lower bounds for robust accuracy of adversarial training and investigate the causes of large generalization gap. In addition, the paper proposes a noise-injection method to improve the algorithmic stability and threfore reduces the generalization gap of adversarial training. Overall, this is a nice contribution to NeurIPS. It provides insightful understanding to a key problem of adversarial training. On the other side, the paper mainly contains theoretial analysis. More experimental study would benefit more readers. I recommend accept.
Decision: Accept (Poster)