On the Algorithmic Stability of Adversarial Training
Year: 2021

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.

heading: 1 Introduction
text: Successful machine learning algorithms require not only a 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 an example, in image recognition problems, a deep neural network will predict a wrong label when the testing image is 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 applications (Papernot et al., 2016a,b; Moosavi-Dezfooli et al., 2016), detecting attacked samples (Tao et al., 2018; Ma and Liu, 2019), and modifications on the training process to obtain adversarially robust models, i.e., adversarial training (Shaham et al., 2015; Madry et al., 2017; Jalal et al., 2017).
However, although adversarial training improves the adversarial robustness during testing, its generalization performance is still poor. While Yin et al. (2018) presented that the adversarial Rademacher complexity is never smaller than its natural counterpart, Schmidt et al. (2018); Zhai et al. (2019) argued that a better adversarial generalization requires more labeled/unlabeled data.
In the literature of natural DNN optimization via iterative gradient moves, the empirical loss at each iteration can be characterized by convergence rate analysis, yet generalization properties are not well understood. To characterize the generalization error, one popular way is to study the algorithmic stability. Algorithmic stability is first considered by Kearns and Ron (1999); Bousquet and Elisseeff (2001, 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 stability for different classes of algorithms, or relax the definition of stability to generalize its usage, see Ramezani-Kebrya et al. (2018); Charles and Papailiopoulos (2018); Kuzborskij and Lampert (2018); Zhou et al. (2018); Lei and Ying (2020); Ho et al. (2020); Madden et al. (2020).
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
In general, there are two ways to utilize algorithmic stability. On the one hand, as showed by Hardt et al. (2016), 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 is 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 to 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 in adversarial training than its natural counterpart. Theoretical justification of the noise injection method is provided for a wide range of data-generating models in several tasks, including both linear regression and logistic classification.
• Noticing that, in practice, adversarial attacks are mostly approximated via numerical methods, 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, a more accurate attack leads to better stability upper bound.
• The effectiveness of noise-injected adversarial training is further generalized to the L1 attack. Compared with L2, L1 training algorithm is generally less stable.
• Beyond the theoretical analysis under simple models, we provide a theory in two-layer ReLU 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 (e.g., PGD-k over FGM) improve the generalization error.

heading: 2 Related Works
text: Theories in adversarial training To theoretically understand how adversarial training works, Sinha et al. (2018); Wang et al. (2019a) investigated the convergence of adversarial training when the loss is 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, Xing et al. (2021a) 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 al., 2020; Allen-Zhu and Li, 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 (2018); Awasthi et al. (2020); Pinot et al. (2021); Xing et al. (2021b).
Observations in deep learning In terms of empirical studies, He et al. (2019); Zheltonozhskii et al. (2020); Xie et al. (2020); Lee and Chandrakasan (2020); 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 et al., 2019b), regularization (He et al., 2019; Zheltonozhskii et al., 2020; Wu et al., 2020), replacing nonsmooth components (Lee and Chandrakasan, 2020; Xie et 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 descent1 (SGD) and gradient descent (GD) have poor stability. It is recommended to run SGD/GD with an extremely small learning rate for a 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.
1We are considering sample-with-replacement SGD.
Another recent work, Farnia and Ozdaglar (2020), considered the algorithmic stability in the minmax problems for generative adversarial networks (GAN) to argue that simultaneous training in generator and discriminator leads to good stability. However, besides the strongly-convex-concave 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.

heading: 3 Stability of adversarial training
text: In this section, we study the uniform argument stability (UAS) of adversarial training. Utilizing the notations introduced in Section 3.1, we present in Section 3.2 the upper and lower bounds of UAS. Section 3.3 studies the effect of attack error on stability.

heading: 3.1 Notations
text: Adversarial training To introduce adversarial training, let l denote the loss function and f✓(x) be the model with parameter ✓. The (population) adversarial loss is defined as
R(✓, ✏) := E [l (f✓[x+A✏(f✓, x, y)], y)] ,
where A✏ is an attack of strength ✏ > 0 and intends to deteriorate the loss in the following way
A✏(f✓, x, y) := argmax z2Bp(0,✏) {l(f✓(x+ z), y)}, (1)
where Bp(x, r) is a Lp ball centering at x with radius r. Given n i.i.d. samples S = {(xi, yi)}ni=1, the adversarial training minimizes the sample version of R(✓, ✏) w.r.t. ✓:
RS(✓, ✏) = 1
n
nX
i=1
l (f✓[xi +A✏(f✓, xi, yi)], yi) , (2)
and the estimator b✓ aims to minimize RS(✓, ✏). We rewrite RS(✓, ✏) as RS(✓) for simplicity when there is no confusion.
The minimization in (2) is often implemented through an iterative two-step (min-max) update. In the t-th iteration, we calculate the adversarial sample ex(t)i = xi + A✏(f✓(t) , xi, yi) based on the current ✓(t), and then update ✓(t+1) based on the gradient of the adversarial training loss while fixing ex(t)i ’s with learning rate ⌘t. The algorithm runs for T iterations. A more detailed pseudocode is postponed to Algorithm 1 when introducing our adaptations. Note that for some loss function l or model f✓, there may not be an 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 ✓0 and ✓̄ as the minimizer of R and RS respectively. Then for the algorithm output b✓, the excess risk can be decomposed into four parts as below:
R(b✓) R(✓0) = R(b✓) RS(b✓)| {z } Egen +RS(b✓) RS(✓̄)| {z } Eopt +RS(✓̄) RS(✓0)| {z } 0 +RS(✓0) R(✓0)| {z } 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(b✓) RS(b✓) and optimization error RS(b✓) RS(✓̄). 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 L2 norm w.r.t an arbitrary change in a single data point. An algorithm is -UAS if for neighboring datasets S1 ⇠ S2 (i.e., S1 and S2 differ only in a single data point), it satisfies that
sup S1⇠S2 kb✓(S1) b✓(S2)k := sup S1⇠S2 (S1, S2)  .
where k·k represents the L2 norm. Under proper conditions, the UAS bound implies a generalization error bound (Bassily et al., 2020): if P (k (S1, S2)k )  0 for any neighboring (S1, S2), then for any ,
P " |Egen| c
(log n)(log(n/)) +
r log(1/)
n
!#  + 0. (3)

heading: 3.2 Upper and lower bound
text: 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. (2020) as follows: Proposition 1. Assume l(f✓(x), y) is L-Lipschitz and convex w.r.t. ✓, and ✓ 2 B2(0, r). The two models ✓(t)1 and ✓ (t) 2 are adversarial training estimators obtained using datasets S1, S2 respectively. For SGD,
sup S1⇠S2
E h k✓(T )1 ✓ (T ) 2 k i = O
0
@min
8 <
:r, L
vuut TX
t=1
⌘2t + L PT t=1 ⌘t n
9 =
;
1
A .
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., ⌘t = ⌘ for t = 1, ..., T . Theorem 1. Assume ✓ 2 B2(0, r). There exist some ✏ > 0 and some loss function l(f✓(x), y) which is differentiable and convex w.r.t. ✓, such that ✓(t)1 and ✓ (t) 2 , which are SGD-based adversarial training estimators obtained using S1, S2 respectively under attack strength ✏, satisfies that
sup S1⇠S2
Ek✓(T )1 ✓ (T ) 2 k = ⌦
✓ min ⇢ 1, T
n
⌘ p T + ⌘T
n
◆ .
For GD, the lower bound is
sup S1⇠S2
k✓(T )1 ✓ (T ) 2 k = ⌦
✓ min ⇢ 1, ⌘ p T + ⌘T
n
◆ .
To prove Theorem 1, similar to Bassily et al. (2020), we design a smooth clean loss function with two datasets S1 ⇠ S2 and study the exact change of the model parameters. The detailed proof is postponed to the Appendix D.
As discussed by Bassily et 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. (2020), but it is worth mentioning that the two results are not directly comparable since Bassily et al. (2020) studied the UAS of clean training when the loss function l(f✓(x), 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. (2016), is of order O(min{r, L
PT t=t0
⌘t/n}). Therefore, we conclude that adversarial training has a worse stability than its natural counterpart.
To ensure the convergence of optimization (i.e., ⌘T is not so small) and the generalization performance (Proposition 1 and Theorem 1), one may take T = n2 and ⌘ = 1/n3/2. The resulting optimization error and stability then become O(1/ p n), which matches the minimax lower bound of excess risk (Chen et al., 2018). However, such a choice of (⌘, T ) is impractical and needs to improve (refer to the discussion in Bassily et al., 2020).

heading: 3.3 The role of numerical attack error
text: In real-world applications, calculating the exact attack A✏ for general models is not easy, and usually, a numerical approximation A0✏ (e.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 A0✏). 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. (2020) studied the convergence of PGD attack.
For algorithmic stability, extended from Proposition 1, the following result considers the effect of attack error. Comparing the upper bounds of Proposition 1 and Corollary 1, it suggests one to control the attack error carefully in the adversarial training. Corollary 1. Under the same conditions of Proposition 1, assume the algorithm uses an approximation A0✏ instead of the exact attack A✏ with attack error min kA✏(x, y, w) A0(x, y, w)k  " for any (x, y, w), where the minimum is taken when the exact attack (i.e., (1)) is not unique. Assume O✓l(f✓(x), y) is -Lipschitz w.r.t. x. Then, for SGD
sup S1⇠S2
Ek✓(T )1 ✓ (T ) 2 k = O
0
@min
8 <
:r, L
vuut TX
t=1
⌘2t + L PT t=1 ⌘t n +  " TX
t=1
⌘t
9 =
;
1
A .
The upper bound of GD is the same.
Besides the convex case, some discussions for non-convex case can be found in Appendix A. The observations are similar.

heading: 4 Improving the stability
text: 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.

heading: 4.1 Source of non-smoothness
text: 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 are overfitted, i.e., the training loss is almost 0 and Oxi l(f✓(xi), yi) ⇡ 0, the adversary has no preference on the attack direction at xi, and the numerical estimation of A✏ is not stable, which possibly leads to an unstable update iteration of adversarial training; (2) there exists a certain set of ✓, such that the adversarial training loss is always non-differentiable regardless of the training data, even when its natural counterpart is smooth. For example, in linear regression, when ✓t is closed to the null model, the non-smoothness 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.

heading: 4.2 Injecting noise during training
text: In this section, we present the noise injection algorithm in adversarial training and provide some theoretical justifications.
Algorithm 1 below illustrates the details of the noise injection method. The basic idea behind this is that: the non-smoothness of adversarial loss occurs only when ✓ and xi’ belong to a certain special region (e.g., in linear regression, when ✓ is closed to either zero or when ✓>xi ⌘ yi), thus injecting some small noise to both ✓ and x helps them to escape from such region where non-smoothness occurs, which further ensures the Lipschitz continuity property. Remark 1. The Gaussian noise in Algorithm 1 is for proof simplicity. In general, it can be changed to other noise distributions if the tail is 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 et al. (2019), injecting noise in data was also considered to stabilize the training process of GAN (Arjovsky and Bottou, 2017; Jenni and Favaro, 2019).
Algorithm 1 Add noise to weight and data Input: data {(xi, yi)}ni=1, number of iterations T , learning rate {⌘t}Tt=1, attack strength ✏, noise size (⇠✓, ⇠x), scale parameter r , initialization ✓(0). for t = 1 to T do
Add Gaussian noise with variance ⇠2✓ to each dimension of ✓t to form e✓(t), and add Gaussian noise with variance ⇠2x to each dimension of xt to obtain exit . Calculate the attack (based on exit and e✓(t)) as bzit . Take gradient w.r.t e✓(t) on l(fe✓(t)(bzit), yit). Update ✓(t) to ✓(t+1) with rate ⌘t. Project ✓(t+1) onto B2(0, r).
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: l(f✓(x), y) = (x>✓ y)2.
• Logistic regression: l(f✓(x), y) = log1{y=1}(p) log1{y= 1}(1 p), where p = p(x>✓) = 1/(1 + e x >✓).
• Smooth hinge loss: the hinge loss max{0, 1 y(x>✓)} is not smooth at 0, hence is approximated by l(f✓(x), y) = (1 y(x>✓))H((1 y(x>✓))/h), where h > 0 is a bandwidth parameter, and H is a smooth approximation of the indicator function I{x 0}. The detailed conditions on H are postponed to Lemma 7 in the Appendix D.2.
The following assumption is imposed on the data: Assumption 1. The independent variable x 2 Rd follows multivariate Gaussian distribution with zero-mean and ⌃ whose eigenvalues are bounded and away from zero.
For regression, E|y| and Ekyxk are finite. For some constant C > 0, any ✓ 2 B2(0, Cr) satisfies P (|x>✓ y| 2 [⇣1r, ⇣2r]) = O(⇣2 ⇣1) for ⇣1, ⇣2 > 0. For classification, the label is y 2 {±1}. The upper bound r satisfies r/maxi=1,...,n kxik ! 0.
The Gaussian assumption in x is merely for derivation simplicity. The assumptions w.r.t. regression avoids |x>✓ y| from clustering around zero when k✓k/r approaches zero. A linear model E[y|x] = ✓>0 x with Gaussian noise satisfies Assumption 1.
Given the above problems and data generating models, the following lemma studies the smoothness (i.e., the Lipschitz constant) of O✓l(f✓(x), y), and of the gradient of noise injected adversarial loss. Lemma 1 (Informal Statement for Lemma 3). Assume Assumption 1 holds. Denote L as the Lipschitz constant of l(f✓(x), yj) w.r.t. ✓ for any x 2 B2(xj , 2✏) and all 1  j  n. Then, in probability, L is bounded by some finite L⇤. Take the noise injected in data as zero-mean Gaussian with variance (⇠20/d)Id, and the noise injected in parameters is zero-mean Gaussian with variance (⇠2/d)Id where ⇠ = ⇠0L⇤. Denote E(✓+ , ex, y) as the event that O✓l(f✓+ (ex+A✏(f✓+ , ex, y)), y) is B⇤/⇣Lipschitz for some B⇤ > 0. There exists some choice of (⇠, ⇣) ! 0 such that with probability tending to one over the generation of S, uniformly for all ✓ 2 B2(0, r),
P (Ec(✓ + , ex, y)|(x, y) 2 S) = o(1).
The formal statement is postponed to Lemma 3 in the appendix.
Let P (Ec|S) := sup✓2B2(0,r),(x,y) P (E c(✓ + , ex, y)|(x, y) 2 S) in what follows, for notation simplicity. Remark 2. The terms r, L are generic representations. For different loss functions and data dimension d, their values may change. In addition, the exact rate of P (Ec|S) is affected by the value of r, L as well as ⇠, ⇣. We postpone the details to 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⇤/⇣. Note that since Lemma 1 holds over the randomness of S, instead of uniform argument stability, we turn to a bound similar to hypothesis stability (Bousquet and Elisseeff, 2002) for the following results. To simplify the representation, the values of (B⇤, L⇤, r) are treated as constants in the following main text.
Lemma 2. Under the same conditions as in Lemma 1, uniformly for all i = 1, ..., n, with probability tending to one over the generation of S1 ⇠ S2 where the i-th sample is replaced, for both GD and SGD, given k✓(t 1)1 ✓ (t 1) 2 k = t 1, it follows that
E[k✓(t)1 ✓ (t) 2 k2|S1, S2, t 1]  ✓ 1 + 2⌘2t (B⇤)2
⇣2 1{⌘t
⇣ B⇤ } ◆ 2t 1 + reminder,
where the detail of reminder term can be found in (8) in Appendix D.2. Note that the expectation taken on k✓(t)1 ✓ (t) 1 k2 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 2 illustrates the relationship between k✓(t)1 ✓ (t) 2 k2 and 2t 1. Recall that B⇤/⇣ is the Lipschitz constant of O✓l(f✓+ (x̃+A), y). When ⌘t ⇣/B⇤, a larger Lipschitz constant implies a larger upper bound of stability. When taking ⌘t < ⇣/B⇤, we have the following result:
Theorem 2. Under the same conditions as in Lemma 1, when taking ⌘t  ⇣/B⇤, for both GD and SGD, with probability tending to one (where the probability refers to the generation measure of the n+ 1 distinct independent samples in S1 ⇠ S2),
E[k✓(T )1 ✓ (T ) 2 k|S1, S2] = O
0 @ " p P (Ec|S1) + P (Ec|S2) + r 1
n
#vuut TX
t=t0
⌘2t
1
A
+O  "+ 1
n + P (Ec|S1) + P (Ec|S2)
TX
t=t0
⌘t
! .
Furthermore, extending from Lemma 9 of Bousquet and Elisseeff (2002), the generalization gap is upper bounded using hypothesis stability as follows.
Proposition 2. Assume ✓ 2 B2(0, r). Denote b✓(S) as the model obtained based on dataset S using some algorithm. Assume l(f✓(x), y) 2 [0,M ] when kxk  p d log n, we have for any i = 1, ..., n,
E ⇣ R(b✓(S1)) RS1(b✓(S1)) ⌘2  M 2
2n + 4E
" sup
✓2B2(0,r) l2(f✓(x+A✏), y)1{kxk
p d log n}
#
(4)
+ 3ME h l(fb✓(S1)(xi +A✏), yi) l(fb✓(Si2)(xi +A✏), yi) i ,
where Si2 represents the neighboring dataset of S1 whose ith sample is replaced. The notion A✏ is an abbreviation of the attack A✏(f, x, y) or A✏(f, xi, yi).
Note that the last term on the RHS of (4) can be bounded according to the result of Theorem 2, under Lipschitz condition of the adversarial loss l(f✓(xi + A✏), yj). The second term on the RHS of (4) 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 (2002), in Proposition 2, there is an extra term corresponding to kxk > p d log n. In Proposition 2, we only assume l(f✓(x), y) 2 [0,M ] when kxk  p d log n, which is weaker than the uniform bounded assumption in Bousquet and Elisseeff (2002).
Besides, we also establish the optimization error bound. The following theorem presents the convergence of noise-injected adversarial training when ⌘t ⌘ ⌘. For the proof, one can refer to the Appendix D.2.
Theorem 3. Under the same conditions as in Lemma 1, for both GD and SGD, ✓̄ := argmin✓2B2(0,r) RS(✓), when ⌘t ⌘ ⌘,
E 
min t=1,...,T
RS(✓ (t)) min
✓2B2(0,r) RS(✓) S
 Ek✓ (0) ✓̄k2 2⌘T E[k✓ (T ) ✓̄k2|S] 2⌘T
+ ⌘(L⇤)2
2 +O(L⇤⇠) +O(r ").
Theorem 3 presents the convergence of adversarial training loss throughout the training. Under the boundedness of ✓ and ⇠ = ⇠0L⇤, when (⌘, T, ⇠0) is chosen properly (e.g. (⌘T ) ! 1 and ⇠0 ! 0) and ✏ ! 0, the adversarial training loss converges to its minimal asymptotically. It is noteworthy that the general design of Algorithm 1 does not specify the noise distribution.
While in Section 4.3, we use Gaussian noise to justify our theorems under linear regression empirically, different forms of noise can be utilized for complex models, refer to our experiments on deep neural networks in Section C.2. Remark 3. If an intercept term exists in the loss function, e.g., l = (x>✓ + b y)2 for linear regression, the analysis is similar to Lemma 1, leading to the same final conclusions as in Theorem 2 and 3. Remark 4 (L1 Attack in Adversarial Training). In general, the stability of L1 adversarial training is worse. To set an example, we consider the linear regression setup. For L2 attack, the gradient of adversarial loss is not Lipschitz only when ✓ approaches zero or ✓>x is closed to y. Under L1 attack, the adversarial loss becomes
(x>✓ y)2 + ✏2k✓k21 + 2✏k✓k1|x>✓ y|,
indicating there is a much larger set where the L1 adversarial loss is not smooth. Noise injection is still helpful to remedy the non-smooth issue for L1 adversarial training and leads to results similar to Theorems 2 and 3. However, one will derive a worse upper bound for the stability and optimization error. Refer to Appendix E for more detailed arguments.

heading: 4.3 Numerical illustration
text: 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 O✓l(f✓(x+A), y) in Lemma 2 is smaller.
We consider linear regression problem in this experiment. The data is generated using y = x>✓⇤+ with x ⇠ N(0, Id) with d = 10 and ⇠ N(0, 2). The coefficient ✓0 is taken as ✓⇤i = 1/ p d for i = 1, ..., d. The variance of noise is taken as 2 = 4 and attack strength is ✏ = 2. We randomly generated n = 1000 samples.
To train the regression model, we train T = 500 epochs with learning rate ⌘ = 0.01 and initialization ✓(0) = 0. In each iteration, we calculate kOft(✓(t)) Oft 1(✓(t 1))k/k✓(t) ✓(t 1)k as an approximation for the Lipschitz constant of the gradient, where Oft(✓) is the averaged gradient of adversairal loss for the tth batch of data St. Based on Lemma 2, a larger Lipschitz constant (B⇤/⇣) indicates a worse stability, which is the right tail of the histogram. The results are summarized the histograms in Figure 1.
From the left three histograms in Figure 1, one can see that injecting noise on parameters and data (where we set ⇠x = ⇠✓ = ⇠) leads to a smaller distribution of Lipschitz constant for Oft(✓(t)), in terms of right tail percentile. For the right two histograms in Figure 1, a smaller batch size implies a heavier tail in the distribution of Lipschitz constant due to larger stochastic noise in estimating Oft(✓(t)).
Besides the experiment showing how noise injection affects the training process, we also conduct a simulation to illustrate the effect of attack error on the generalization. Due to the space limit, the 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.

heading: 5 Exploration in Neural Networks
text: While our main contributions are for statistical models, we 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 is much larger than simple models, a simple bound on k✓(T )1 ✓ (T ) 2 k is not useful. Instead, we consider a two-layer neural network with lazy training and vanishing initialization in regression and provide a 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 lazying training in adversarial training setup. The formal statement of the theorem is postponed to Appendix C.1. Based on the following theorem, under proper configurations, the noise-injected training in neural networks improve the stability: Theorem 4 (Informal Statement). For two-layer nonlinear (including ReLU) networks, with proper initialization and training configurations, training only on the hidden layer with proper noise injection, it satisfies that
ES1⇠S2 l(f✓(T )1 [x+A✏(f✓(T )1 , xi, yi)], yi) l(f✓(T )2 [x+A✏(f✓(T )2 , xi, yi)], yi)
= O " L p P (Ec) + r L2
n
# ⌘ p T +  L
n + LP (Ec) ⌘T
! + rem,
where rem = o(1) and is not the dominant term.
There are two differences between Theorem 4 and the results in simple models. First, it is not useful to directly assume the weights of the neural network parameters within a large ball and put this large number into the bound, thus we simultaneously 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 CIFAR10 dataset. Due to space limit, we 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.

heading: 6 Conclusion
text: In this paper, we evaluate the algorithmic stability of the adversarial training method. Based on the lower bound and upper bound of UAS, we reveal that the naive adversarial training is not as stable
as its natural counterpart. To improve the stability, we argue that it is helpful to inject noise into model parameters and input 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 is smaller.
The above theoretical investigations emphasize the usage of noise injection and controlling numerical attack error during the adversarial training. These theoretical insights are well validated by our simulations under simple regression models.
There are two future research directions motivated by this study. Although we observe a 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 we mentioned in the numerical experiments, a wider neural network has a poor attack. Corresponding theoretical explanation is also an interesting topic.

heading: 7 Acknowledgements
text: This project is partially supported by NSF-SCALE MoDL(2134209) and NSF-DMS-1811812.

heading: 8 Checklist
text: 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 a 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 experiments 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, or 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 a lot.

Review summaries:
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.

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.

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. In order to improve stability, the authors suggest injecting noise into the weights and data (this was already investigated, see for example - Adversarial weight perturbation helps robust generalization, Neurips2020). Moreover, theoretical analysis is also provided for Linear Regression, Logistic Regression and learning with hinge loss. 

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.  1) 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. 2) The numerical approximation error of adversarial attacks used during training can have an impact on the algorithmic stability of the scheme.  3) Injecting noise to the learning procedure helps to make the loss function smooth again; hence restoring the algorithmic stability with high probability.