Algorithmic Stability Based Generalization Bounds for Adversarial Training
Authors: Runzhi Tian
Yongyi Mao
Venue: ICLR 2025 Poster (2025)
Keywords: algorithmic stability
generalization
adversarial training
Primary area: learning theory

Abstract: In this paper, we present a novel stability analysis of adversarial training and prove generalization upper bounds in terms of an expansiveness property of adversarial perturbations used during training and used for evaluation. These expansiveness parameters appear not only govern the vanishing rate of the generalization error but also govern its scaling constant. Our proof techniques do not rely on artificial assumptions of the adversarial loss, as are typically used in previous works. Our bound attributes the robust overfitting in PGD-based adversarial training to the sign function used in the PGD attack, resulting in a bad expansiveness parameter. The peculiar choice of sign function in the PGD attack appears to impact adversarial training both in terms of (inner) optimization and in terms of generalization, as shown in this work. This aspect has been largely overlooked to date. Going beyond the sign-function based PGD attacks, we further show that poor expansiveness properties exist in a wide family of PGD-like iterative attack algorithms, which may highlight an intrinsic difficulty in adversarial training.

Published as a conference paper at ICLR 2025
ALGORRHHIICC STABILITY BASED GENERALIZATION BOUNDS FOR ADVERSARIAL TRAINING
Runzhi Tian
Yongyi Mao University of Ottawa
University of Ottawa (riaa081@qutt.ear ca
ymao@uottawa.. ca
ABSTRACT
In this paper, we present a novel stability analysis of adversarial training and prove generalization upper bounds terms of an expansiveness property of ad- versarial perturbations used during training and used for evaluation. These ex- pansiveness parameters appear to not only govern the vanishing rate of the gen- eralization error but also govern its scaling constant. Our bound attributes the robust overfitting in PGD-based adversarial training to the sign function used in the PGD attack, resulting in bad expansiveness parameter. The peculiar choice of sign function in the PGD attack appears to impact adversarial train- shown
ing both in terms of (inner) optimization and in terms of generalization, in this work. This aspect has been largely overlooked to date. Going beyond the sign-function based PGD attacks, we further show that poor expansiveness properties exist in a wide family of PGD-like iterative attack algorithms, which may highlight an intrinsic difficulty in adversarial training. Code is available https: https://qithub. com/ rZT TazTian/Aaae A ATaaaATtSttabiyty
INTRODUCTION
Deep neural networks, despite their great success, have been shown vulnerable to adversarial attacks (Szegedy et al.] 2014
Kollett
Mandard Hormet)
Goodfellow et al., 2015). where carefully constructed small modifications of the input may cause the network to output a wrong prediction. A large body of works (Madry et al. 2019
54-
Zhang et al.) 2019 Croce et al. 20200 [haham et al. 2018 Qin
02-
jt al. 2019 Shafahi al.] 2019]] [ong et al. (020) then pro- pose revised training algorithms to combat adversarial attacks.
These algorithms, usually referred to as adversarial training (or
AT in this paper), among which the dominant approaches, such as PGD based AT (Madry et al., 2219). involve perturbing the input in a way similar adversarial attacks hopefully max- imize the loss function within a prescribed radius (referred to as "inner maximization"). Although these AT algorithms allow the learned model to defend, to some extent, against adversar- ial attacks, significant challenges remain.
Figure 1: The learning curve of model trained by AT on CIFAR-10 10 with 3-step PGD. The standard er- ror as well as the error against the same 3-step PGD attack are mea- sured during AT on both the train- ing and testing sets. The step size for PGD and the perturbation ra- dius w.r. the -0-norm are respec- tively set to 7/255 and 8/255. The learning rate is decayed at the 100 and the 150th epoch.
First, generalization for such training algorithms is much more difficult, phenomenon known as "robust overfitting" (Rice (Rice et al. 2020). Specifically, Rice et al.
(2020) shows that on the CTFAR-10 dataset (Krizhevsky et al. 2009), the model trained by AT using 10-step PGD attack is still vulnerable to the same 10-step PGD attack on the testing set. Our additional experi- ments (e.g., Figure I suggests that this is quite common. In Figure 1 we perform AT with a 3-step PGD and measure the error of the model against 3-step PGD attack as well as its standard error in the training process. We observe that the model trained with 3-step PGD is still vulnerable to the same PGD attack on the testing set. After the first learning rate decay (the 100th epoch), the testing emror w.r.t the 3-step PGD starts rise, similar the observations in Rice al. (2020).

---

Published as a conference paper at ICLR 2025
Second, it is much more difficult to develop theoretical understanding of the generalization behavior for models obtained from AT, comparing with those from standard training. In that direction, some theoretical works consider the setting where the inner maximization is perfectly solved, e.g., in Yin et al. (2018); : Awasthi et al. (2020). However, such settings are invalid for more complex neural networks, where the closed-form solution for the inner maximization is unavailable. Another line of works use uniform stability to analyze the generalization of AT. In Xing et al. (2021). the adversarial loss is assumed convex and non-smooth and AT is regarded as standard SGD on this loss, whereby an existing generic bound for non-smooth loss in Bassily et al. (2020) is invoked for analysis. As pointed out Xiao et al.] (2022)), the bound obtained in Xing et al. (202T) is independent of the specific choice of loss function used for training and insufficient to reflect the difference between AT and SGD observed in practice. The work of Xiao et al. (202b)) argues that the adversarial loss is approximately smooth and derive bounds based on the stability framework of SGD in Hardt et al.) (2016). The work of Wang et al. (2024), built upon Xiao et al. (2022b), extends the analysis sis of AT to the data-dependent stability framework in Kuzborskij & Lampert (011)). But the bounds obtained in both Xiao et al. (022b) and Wang et al. (2024) do not vanish with sample size.
To overcome these limitations and shed new light in understanding robust overfitting, we present in this work novel stability analysis for the generalization of models learned using an arbitrary AT al- gorithm. Specifically, we isolate two aspects in the problem scope. The first is the loss function used for performance evaluation (on both testing and training sets), which can in general be considered as a modification of the standard loss to version induced by a perturbation map and which reduces to the adversarial loss when J is specialized to a particular form J and to the standard loss when J specialized to the trivial identity map jåd, The second is the perturbation map π used during AT, corresponding to the solution heuristics used for solving the inner maximization problem. When allowing to potentially deviate from the perturbation J we include in our study the case where the inner maximization is not solved exactly. Additionally, considering = J allows to study robust overfitting as examplified in Figure [ where training using particular attack results in poor generalization when evaluation on the testing set is under the same attack.
In this setting, we carry out a stability analysis and present novel generalization bounds for models trained using AT with an arbitrary adversarial perturbation and evaluated a loss induced by an arbitrary perturbation J. At the heart of our analysis is the introduction of a notion of "expan- siveness" for the perturbation maps (J and т), which governs the behavior of the derived bounds. Specifically, we show that whenever the expansiveness parameter of J is strictly bounded, our gen- eralization bounds vanish with sample size n as ((1/n) and small expansiveness parameter of further helps generalization. On the other hand, when the J-loss (i.e., the loss induced by perturba- tion J) is defined with taken as the sign-PGD perturbation, the expansiveness parameter of is no longer bounded. In this case, our bound reveals an intrinsic tension between the stability parameter, and the perturbation radius, and the ambient data dimension, in their respective roles on generaliza- tion specifically, the bound converges to constant. Additional advantages of our bounds include the following. Our generic bound (Theorem 4.2) is applicable to AT algorithms based on any form of adversarial perturbations. Our bounds do not rely on any assumption since we only make assumptions on the standard loss and all properties of the adversarial loss are induced via perturbation map J. Finally, varying the form of J potentially enables this framework to be applicable to settings where generalization on other performance metrics is of interest.
the adversarial loss directly,
We zoom into models trained with multi-step PGD, and further demonstrate that the sign func- tion used in the perturbation is an important cause of robust overfitting for such AT methods. We experimentally replace the sign function in PGD with smooth approximation tanh,, where taub, (x) tanh(77a) and the parameter controls the smoothness of the function and hence the expansiveness of the PGD perturbation (decreasing 7 decreases the expansiveness). Our experiments show that reducing y results in smaller generalization gaps. These results validate our bound and its implication on generalization. Interestingly our experiments also reveal that sign-PGD appears as a stronger attack than tanh,- -PG and the raw gradient (RG)-PGD attack, even on the train- ing set. Performing AT with tanh and RG-PGD may be inadequate for defending against the sign-PGI attacks on the training set. Our observations suggest that sign-function, a building block of PGD-based AT, appears to play a peculiar role: comparing with the tanh, counter-part, the sign function helps to better solve the inner maximization problem but at the same time cause the perturbation т to suffer from bad expansiveness and results in poor generalization. This aspect of
2

---

Published as a conference paper at ICLR 2025
sign-PGD has been largely overlooked date, since most theoretical analysis of PGD removes the sign function in their consideration (i.e., studying RG-PGD instead).
In this work, also recognize sign-PGD an iterative method for solving the inner maximization problem where each step is principled by a locally linear approximation of the loss function. Based on this principle, we extend sign-PGD to wider family of perturbations. We show theoretically that every member in this family suffers from poor expansiveness. This result seems to point to certain intrinsic difficulty in training models adversarially.
2 OTHER RELATED WORKS
Robust generalization Beyond investigations via algorithmic stability perspectives (c.g.. Xing
et al. [202T; Xiao et al. 2022b); Wang et al.] (2024), ), robust generalization has also been studied
under the uniform convergence framework with conventional statistical learning tools such VC
dimension (Montasser et al. 2019). Rademacher complexity (Khim & Loh, 2019 Yin et al. 2018
Awasthi et al.) 2020 Xiao al. 2022a Attias et al., 2018) and other PAC learning frameworks
(Cullina et al. 2018: Diochnos et al. (019). Moreover, robust generalization has been investigated via the curvature of the local minima of the loss landscape: AT is observed have tendency to
reach sharper minima (Liu et al. (020), and flatter minima usually results in better generalization
(Wu et af. 2020). The work of Chen et al. (2020) observes that robust overfitting can be alleviated by smoothing the model prediction via knowledge distillation. The difficulty of achieving robust generalization has also been attributed to the inadequate expressive power of practical deep learning
models (Li et al. 2022), insufficient sample size for models to generalize (Schmidt et al. 2018 as
well as and the model's ' tendency to interpolate "hard training instances" (Liu et al. 2021
Uniform stability Uniform stability was first introduced by the landmark work of [ousquet & Elisseeff (2002). An influential work by Hardt et al. (0166) adapts this framework analyze the uniform stability of SGD with smooth loss functions, explaining the effectiveness of SGD in training neural networks. Since then, many studies have built upon Hardt et al. (2016) to develop stability bounds for SGD with non-smooth losses (c.g.. [Bassily et al. (2020): Lei & Ying (2020). Data- dependency in stability analysis is introduced in inKKubooskii & Lampert 2018 8) and uniform stability for more sophisticated variants of SGD is also studied (e.g.. Mou et al. (2018); Chen et al. (2018). Additionally, works such as Farnia & Ozdaglar (202I): I) Lei et al. (2021) have explored algorith- mie stability in general minimax problems. These studies are more closely related to generative adversarial networks (GANs), rather distant from the standard settings of adversarial training.
PROBLEM SETUP AND PRELIMINARIES
Over any real vector space, we will use || llp to denote the p-norm and abbreviate the Euclidean norm (i.e., 2-norm) as || |]. For a vector x E Rd, x=|i] denotes the 7th coordinate of x.
We consider the standard setting of supervised learning, where the training samples are instance- label pairs, (a,,, ys)'s, ss drawn i.i.d from an underlying data distribution over X' x y. Here the input space X' is Rd and the label space y is finite. We restrict to parameterized models, e.g., neural networks, in which the model parameter w lives in a subset W of some real vector space. We use f(w, x, 3) to denote the loss value of (I, y) under model parameter w, where a standard choice of loss function (e.g. 0-1 loss, cross-entropy loss, etc.) is absorbed in f. For example, f(w, x. y) can be the cross-entropy loss of the a neural network with parameter on sample (x: v)-
The central object of this study is adversarial training, which allows the learned model to resist adversarial attacks. Each adversarial attack (or adversarial perturbation) input is assumed to live in an co-norm ball Bo (I, <) == {t E Rdd ||t - xlloo I <) with radius e and centered at x.
Let J be a function mapping W x X' x Y'to to X' satisfying [xx; y, w) e Be (2. c). Then [(x; y. w) may be regarded as a perturbation of x by a magnitude up to (under co-norm). We then define the perturbation J induced loss or simply J-loss by
Perturbation induced loss
Sr(W, x. v) = I (w, [x;;
(0; y, w)
3

---

Published as a conference paper at ICLR 2025
Let J (z; (z: w. == arg maXaen(a.r) fw,, y), and Jid y, w. := Then it is easy to verify that when J = J", [,(,, v) is the adversarial loss max,e J (w; Fi v) -or which reason, we will denote the adversarial loss fJ- by f for simplicity and when J Jrd (w, x, y) is the standard loss fww I. y). We will soon encounter other forms of J-loss.
Generalization w.r.t the induced loss Let the training set S {(2 31 )== be drawn from D" Consider learning algorithm A, which when applied on S gives rise to a learned model parameter A(S). Notably entails randomness, due the random sampling of and the possible intrinsic randomness in A. The population risk and empirical risk w.r.t J-loss are defindd respectively as:
( (fx(A(S), x)] and Rs[A(S);J] =
(A(SS))
Note that Rp(A(S); J/ and Rs(A(S); are both random variables. The expected generalization gap w.r. the J-loss is then
(J, = Es.4 (RD[A(S); Rs(A(S):
where expectation over A refers averaging the intrinsic randomness in A. Specially, will call GG,, (Jid, A) and GG, ; A) respectively the standard generalization gap and the robust generalization gap of the algorithm A.
The generalization gap can be analyzed by exploiting the tool of uniform stability (Bousquet & Elisseeff 2002). We say that the algorithm A p-uniformly stable w.r.t J-loss, if
(J, = sup sup S= (x.))xxxy
Ea[sa (A(5), x, Ja (A(S"), x,,)] sp
Here S = S" denotes datasets that each contains samples but differ in at most one. It is shown in Hardt et al. (2016) that uniform stability implies generalization in expectation, namely,
Lemma 3.1 (Hardt et al. (2016)) For any perturbution J and any algorithm A,
(J, (J,A)))
The lemma due to that analysis Hardt et al. (2016) applies to arbitrary loss functions, including the lososs defined above. In our work, we will consider the family of that are Lipschitz and gradient-Lipschite with respect to both r and w in the following sense: there exist positive constants Lx. Lw. Ix and @ such that for any y V. any x, x! E X and any w, w W
If(w x',y) - f(w, x. v)1 & Lx][ x' + Lwl[w | w'll
(4)
|| w/ fw', a'',0 v) v fww, x, y| < Fx|1= - x'll + 3 3|| - w'll
(5)
Similar Lipschitzness and smoothness assumptions also used in other stability analysis literature, as in Hardt et al. (2016); Farnia & Ozdaglar (2021): Xiao et al. (022b): Wang et al. 2024).
With the Lipschitz condition of f. the uniform stability w.r.t fo be related to the notion of the uniform argument stability (UAS). a notion coined in Bassily et al. (2020), as well as an "expansive- ness" property of J, which will soon define. Specifically the UAS parameter of A is
8, (4) = sup EAl) - A(S')l
S~
and for any given define the c-expansiveness of perturbation J as
[|; y, w)) J(x; y, w')ll
(J) = sup (2.9)
sup
wi wonoflllue [ ||>
w w/ll
We note that such notion of expansiveness reduces to Lipschitz condition when 0. It measures the sensitivity of an operator to the perturbation of its imput, sharing similarity with the Lipschitz condition but provide extra benefit when analyzing operators whose Lipschitz constant unbounded. When taking с > O, this expansiveness, however, excludes measuring sensitivity for perturbation with magnitude lower than This consideration is motivated by the fact that in
4

---

Published as a conference paper at ICLR 2025
practice, extremely small perturbation do not arise. Additionally, this expansiveness behaves nicely, ie., being bounded, even for non-continuous operators, such as those defined via the sign function, to arise later in this paper.
For any given S and S" differing by only one element and every c* 2 0, let probability (under the probability measure induced by the randomness in A) that ||A()) A < c". Specifically, let S. and 5" denote two training sets with S, = S which achieve the supremum in the definition of A) in 2). We write (c²*) in place of Q(S., ((,,,,';'' c");c)) for simplicity.
denote the
Lemma 3.2. If the loss function f satisfies the Lipschitz condition then for any c² 2 0.
(J, < (Lw + q.- (J)Lx) + LxQ(c") 2evd
(6)
The proof of this lemma is deferred to Appendix A bound to analyze the generalization of adversarial training (AT) algorithms. We will show, for most cases, that this bound vanishes with sample size n by choosing a judicious choice of c*. The only case in which vanishing bound is not attainable is sign-PGD based AT, where the bound converges to constant. This may reveal some intrinsic difficulty in generalization for such AT algorithm.
the remainder of this paper, we will use this
4 UNIFORM STABILITY OF ADVERSARIAL TRAINING
suggests that the expansiveness of the perturbation J, which is used to define the J-loss fM, plays role in generalization. We now take A as an adversarial training (A7) algorithm where we will show that the expansiveness of the perturbation used in the AT training algorithm plays another role by impacting the UAS parameter 6,, (A).
Lemma 3.2
AT algorithms We consider the following iterative AT algorithm. At each iteration of AT, it first draws training sample (Zt, Vt.) and then updates the model parameter w, according to
xt 7 (3;; 3e:.: We)
W++1 = we Te ww. f(w,, 2. .3%.)
(8)
Here T, R4 denotes the step size of the gradient descend at the iteration it {1, .n is drawn uniformly and independently (across t) from {1, ....., .n), and x (I Mi. w2) denotes per- turbation of Hi, within B. (Ti, c). We note that ideally ı should be J (æz, Vh,, wy) but in practice is only an approximation of due to the difficulty in acquiring the exact solution. Additionally and more critically, we note that, despite that both π and J refer to perturbations, the two notions in this paper may be completely different. Specifically, J induces the J-loss, which is used as a performance metric (evaluated either on the training set or on the testing set), whereas denotes the perturbation operation applied during adversarial training. Although in some cases π is J or is related to J, there are scenarios in which π and J are completely decoupled, for example, when we perform adversarial training but choose to evaluate the model using the standard loss, i.e., using jid loss. In later section, we will see more cases in which J and л are completely different. As minor comment, note that when the perturbation in 7 is chosen the identity map jid the AT algorithm reduces to the standard stochastic gradient descend (SGD) algorithm. Finally, as may look into various choices of in AT algorithms, we use A, to denote AT algorithm, emphasizing its dependence on म. Under such notations, we may even consider "mis matched gen- eralization gap", namely, (J, with J + n, for example, J jid and æ is particular adversarial perturbation.
Note that although aeddy is also function of wt, the derivative operator in does not go through π, an option consistent with the standard AT implementation as in Madry el al. (2019) Rice et al. 2020).
We now present an upper bound for the UAS of AT.
Theorem 4.1. Suppose that f satisfies the conditions 4 and (5) If we run A for T steps with step
sizes < B. there exists a conslant > O such that we have
T (2 + xx3))
2LW
8 (Ax)) <
Σ
nB t=0
5

---

Published as a conference paper at ICLR 2025
We defer the proof of the theorem to Appendix A With the upper bound of the UAS, upper
bound for the mismatched generalization gap can be immediately derived according to (3) and 6 as below:
Theorem 4.2. Under the condition of Theorem 4.1 for any 2 O, there exists a constant c
0,
such that
2Lw
G., (Lxge-()) Lw)
n3 Σ
2 LxQ(c)))))++))))))))) 22Vd
(10)
The bound in (1) also includes special case the "matched" generalization gap GG, AJ), where the perturbation used in adversarial training is identical to that defining performance metric, as is typical in the adversarial training literature. Beyond the Lipschitz and smoothness conditions of J. the expansiveness parameters of π and J turn out to also influence the generalization of AT algorithms, as suggested in the generalization bound (1O). This has been overlooked by the previous stability analysis as in Xing et al. (2021): Xiao et al. (002bb); Wang et al. (0224).
The behavior of the bound in (10) clearly depends on Q(c"). We now show that with additional conditions, one can choose a e² to either remove the term containing Q(c") or make Q(c*) also vanish with n.
For example, if the perturbation J has bounded Lipschitz constant q", that is ge- (J) S S g < 0o for any c* 2 0 then taking simply results in the following bound that vanishes (1/nn).
GG, (Lxq² Lw)
2Lw nB
Σe 22 + (x())
(11)
On the other hand, if the second moment of the random variable |[A(S.) - A(S) has fast vanishing rate with n, one can choose e to decay with n at a judicious choice of rate, pushing Q(c") vanish faster than 1/n, resulting in the bound in the following form
2LW nB
GG Az) (Txxge (J) Lw)
Σ (2 + g. d(1/n)
(12)
We defer the proof of (12 to Appendix
Convex loss and strongly convex loss a tighter UAS upper bound can be attained.
When f is further assumed to be convex or strongly convex,
Theorem 4.3. Suppose that f(,, x. is convex for any (x, y) X Y and satisfies the conditions and 5). If we run Ax for T steps with step sizes T. S z. we have
2Lw Ea ((())(x)x/3))
8n (n(A))
nB
we further assume [(, v) is p p-stooggly convex, we have
8n (n
2Tw
Σ
(1 1
+ +xgc(T)/3))
nB
23
As shown, performing AT using convex loss functions results in tighter upper bound compared to the non-convex functions. When is strongly convex, the bound can be tightened again. In fact, in the strongly convex case, if ge (x())) is small enough, the UAS upper bound can be made independent of the number of iteration T.
Corollary 4.4. Suppose that f is u-strongly convex and satisfies the conditions 7 and (5) Sup- pose that (m) < 42(2Txx) x) and we run Az for T steps with step sizes T S 1
3. we have
4Lw
5, (Ax) < n(μ 2q.(
The proofs of Theorem 4.3 and Corollary 4 are deferred to Appendix A Notably, when æ is chosen as the identity map, we have (T) = and A, reduces to the standard SGD algorithm. this case, UAS upper bounds matches the bounds in Hardt al. (2016) up constants.

---

Published as a conference paper at ICLR 2025
Comparison with existing UAS bounds for AT The work in Farnia & Ozdaglar 2021 derives UAS bounds for the AT-like algorithm (refer to as GDmax their paper) under the assumption that is strongly concave in X. Our work goes beyond this restricted setting and derive UAS bounds without this assumption. In Xing et al. (202T). the stability of AT is analyzed by treating AT as standard SGD with an adversarial loss (i.e., I') and invoke the generic bound in Bassily et al. (2020)
for non-smooth losses, while assuming f to be non-smooth. The non-smoothness is however not quantitatively characterized in their work; additionally since the bound in Bassily et al. (2020) is developed for SGD with any non-smooth convex functions, it fails to explain the notable difference between SGD and AT observed in practice. The UAS bounds proposed in Xiao al. (20226); Wang et al. (2024) include terms that do not vanish with increasing sample size. Our bounds overcome this limitation, vanishing with the sample size (see Appendix B for more details).
REVISIT OF PGD-BASED AT
We now discuss the AT algorithm A, when is taken the PGD perturbation (Madry al. 2019). which we denote by n PGD, To begin, associated with any (x, y) and any weight parameter we we define and one-step PGD map T2,y,u by
Te (x') = (m,c) [x' + XG z' f(w, x', ,2)]
Here x' is any point in R4, G is mapping from I to R24, possibly taking various forms, which will specify momentarily, À is another step size, and [z,e) R& B ( (2),e) denotes the projection onto the set Box (2,,)., namely, IT (x.e) PGD perturbation PPG is then defined as the K'fold compositions of the (same) mapping Te.yww:
arg minge3 (z.c) || x² The K-step
PGD (x; y, w) == T.K 2..g, (I) = Tw.yyuu Te T2.y.w o ... T2.y.0
(x)
timees
In the well-known PGD attack (Madry et al., 2019), the mapping is taken as the sign function and is applied element-wisely on the gradients see Wong et al. (2020); Andriushchenko & Flammarion 22000); Wang et al. (202T) I); Rice et al. (2020); Dong et al. (2021); y Wu et al. (2020). Theoretical analyses of PGD (as Deng al. (2020) Fu & Wang (2023) Bubeck et al. (2015)) often considers the graw-gradient" version, namely taking G as the identity map. In our work, we will show that the choice of G, this peculiar and largely overlooked building block in PGD, in fact has non-negligible impact on the generalization performance of PGDD-hased AT.
To begin, assume that the gradient V.f is Lipschitz, namely, that there exist positive constants and I'w such that for any E y, any x, E X and any w, w' E W
V [w' s/; VaJ(w: v)ll S n|| x'1l T
w'll
(13)
Lemma 5.1 (Expansiveneess of PGD). Suppose that I satisfies the condition and the mapping G a- Lipschitz.
2vde c
(e(TT min
Σ Env,
1=0
where v Xad's w and μ + Aom,
We defer the proof to Appendix A
For all J-losses for which (J) is uniformly bounded by q-, plugging this bound to I1] immedi- ately gives a generalization bound that vanishes as (1/n). However, one of the most important J-loss, the one defined using sign-PGD attack, fails to satisfy this boundedness condition and the bound 11 does not apply. To carefully study such setting, let Jaign- function G taken as the sign function. We have the following results.
PGg where n sign is PGD with
Corollary 5.2. Let J PGD Suppose that for any S and S' with S ~ S",
<
B with probability I. Under the condition of Theorem 4.1 for any p > 0, there exists some N (depending on p). such that when n > N.
GG,, Ax) < 8n (A Lxx 2 +
7

---

Published as a conference paper at ICLR 2025
The proof is left in Appendix A Note that for J=inn-PD -ee---G--osss -loss and without additional information on |[A(S)) - (I) it appears difficult to arrive at a generalization bound that vanishes with n and the bound given here converges to constant. Although this may not mean that AT with psign-Phht loss does not have a vanishing generalization error, it nonetheless reveals certain intrinsic difficulty of generalization for this setting. Specifically, for large n, the perturbation radius (that defines the J-loss and the imput dimension appear to fight against the UAS parameter òn (Ax); when UAS pa- rameter decreases- which pushes towards better generalization, e d is amplified more significantly -causing poorer generalization.
To investigate how the expansiveness property affects generalization, we consider smooth approx- imation of the sign function by a tanh function, i.e., sgn(z) ss tanh,(z) == tanh(yz)). Notably, the approximation error here vanishes with increase 7/. By replacing sgn(z) (z) in PGD AT with (x), we may control the expansiveness of x PGD.
Experiments We conduct experiment for PGD-AT when G is chosen as tanh, as well as the identity map. Specially, for 7PD with different choice of G, we refer to it as "sign-PGD" when G(x) sgn(z), as "tanh,-PGD" when G(z) tanh, (z) and as "raw gradient (RG)-PGD" when G(z) x. In all the experiments, we primarily consider the J-loss defined in ① as our evaluation metric, with the loss function in taken as the 0-1 loss and refer to this metric as J-(0-1) loss. We mainly use J from (Lanh,,-GDD sign-PGID, Jid]. The experiments are conducted on CIFAR-10, C1FAR-100 (Krizhevsky et al. (2099) and SVHN(Netzer et al.. (001T). Our experimental setting is elaborated in Appendix which follows from the setting in Rice et al. (2020).
penurs Setes wo coeee
apochs PUDDA PUDAT
Traiiig spout NO (c)
09
(a)
(b)
Figure 2: Experiments on CIFAR-10. (a) Models trained with (anh,-PGD AT with different y and evaluated by J-(0-1) loss on the training and testing set. (b) JJ(0-1) loss with J = tan measured along the training trajectories of two sets of tanh,-PGi AT. (c) J-(0-1) loss measured along the trajectory of the RG-PGD AT with different choice of J.
Figure 2 (a) presents the results of experiments conducted on CIFAR10, where the models are trained using tanh., AT (i.e., An with ग = tanh,-PGD) with various 7 values. Each model is trained for 200 epochs and is evaluated using the J-(0-1) loss for J E (tanhh, -PGD, sign-PGD, jdd] (dis- tinguished by colors), where " matches the corresponding value in л. We use star-shaped dots and circle-shaped dots to respectively denote the J-(0-1) loss measured on the training set and the testing set. The gaps between each pairs of curves in the same color category then represents the gener- alization gap of the trained models evaluated by different J-(0-1) loss. By decreasing y in n, the generalization gaps reduce, as shown by the narrowing gaps across all pairs of the curves in the same color. The observed experimental results demonstrate that AT with less expansive π tends to achieve a smaller generalization gap, consistent with the generalization bound of (IO). Similar trends are also observed on SVHN and CIFAR 100 (see Appendix D Figure
Due to the mismatch between æ and J, the model trained by the algorithm A, may still have large empirical risk EE| (A)) J]], which in turn results in high population risk E RD (Ax()), JJ] even the generalization gap GG,, Az) ) is small. This is illustrated in Figure 2 (a) as the blue star-shaped curve consistently stays higher than the green star-shaped curve with notably large gap. As y increases, the tanh, function gradually approaches the sign function, leading to an intersection of the green and the blue curves. This indicates that sign is stronger perturbation compare to the tanh, -anh,--GDD PGD,, as the model trained with tanh,-PGi PGD AT can still be vulnerable to the sign-PGD attack the training set.
8

---

Published as a conference paper at ICLR 2025
The seminal work by Tsipras et al. (2018) found that AT can negatively impact standard generaliza- tion. They constructed specific data models to demonstrate that achieving robustness and standard generalization can be inherently conflicting, suggesting an unavoidable trade-off between these two
goals. This phenomenon has been extensively studied in subsequent research (Zhang et al. 2020
2019] Yang al., [0200] Raghunathan et al., 2020 Javanmard et al. 2020 Pang al. 2022 Our experimental results offer further insights into this phenomenon from the perspective of algorithmic stability. Specifically, we find that the decline in standard generalization performance caused by AT can be attributed to the poor expansiveness condition of the sign-PGD method employed in AT. As shown by the trend of the red circle-shaped curve Figure 2 (a), AT does not always harm standard generalization; reduction in the J (0-1) loss is observed as decreases. This suggests that the trade-off identified by Tsipras et al. (2018) might be side effect of the sign-PGD AT and is not necessarily unavoidable.
æ evaluated along the trajectory of the tanh, AT with y = 10 (the solid curves) and y 10x (the dashed curves). The dashed curves exhibit a phenomenon similar to robust overfitting observed in Rice et al. (2020): after the first learning rate decay (the 100th epoch), as the training loss continuously decreases, the testing loss starts to elevate. This phenomenon does not appear in the AT with 7 = 10, as shown in the trend of the solid curves. We conduct additional experiments for RG-PGD AT. As shown Figure (c), the generalization gap remains small across all groups of J-(0-1) loss throughout the training. Similar to the previous results, the model trained by this AT variant exhibits notable vulnerability to the sign-PGD perturbation, as indicated by the consistently high values of the orange and blue curves. These findings demonstrate that removing or altering the sign function in PGD leads to a non- negligible influence on both robust generalization and resistance to perturbations on the training set. This highlights the crucial role of the sign function in PGD-AT, which deserves a more careful and further depth investigation.
Figure 2 (b) plots the J-(0-1) loss with
6 REVISIT OF SIGN FUNCTION IN PGD
For simplicity, we write f(w,,, xr, 2) as f(x) hereafter. The sign-PGD perturbation can be treated as an iterative optimization algorithm for solving the constrained optimization problem maXseRa< fā). It is related to the sign gradient methods, which has been used for different purposes, such as for training neural networks (e.g.. Riedmiller & Braun| (1992)) and for gradient compression (e.g.. Bernstein et al. (2018)).
We now show that the sign gradient method can be viewed as a Steepest Descend (or ascend in our context) Method (SDM) w.r.t co oo-norm ball (e.g., see Chapter 9.4 in [Byyd & Vandenberghe (2004)). Specifically, for the loss f(a²") at the 1thh iteration in SDM, updates xx by finding a steepest ascend direction within a small neighborhood of x such that the loss [(*++1] with kt+ I² + V is locally maximized. Such neighborhood can chosen as a p-norm ball around x* (i.c., Bp(x* Ax)) with small radius Ap. Finding introduces a new optimization problem: +o), max AP) +(*++t) which is then approximately solved by replacing f(* +v) with its linear approximation around x² namely, solving max (xp) f(=*) + f=(*) which is equivalent
to solving maxvEB, (x* .2p) V(ak"" u whose closed form solution is
sgn sgn sgn(V)(**)) O (V
w¹ = (V((x))
where Gp(VS(a*))
(14)
|f
where we require 1 1/p + 1/9 The operator @ denotes the element-wise product. The closed form (14 then gives the following updating rule of SDM as
x+1 * + (V
As a special case, when p with q = co. SMD turns into the coordinate gradient method with G. (V)())) = sgn(max, f=(x>) (il))e; and i = arg max, [x Lill, where denotes the standard basis vector. When
q = 2, we have G2 (V =
When p = oo with g 1, the mapping Go reduces to the sign function, indicating that the sign- PGD is indeed a (projected) SDM w.r.t Boo(x*, >xo)). It is then curious to investigate the general- ization performance of the model trained by AT using the G,- Gp-PGD with p & oc We conduct
Note that in the G, GPPGD we still consider projecting onto Boc (xI, when p is taken other than oo.

---

Published as a conference paper at ICLR 2025
27
(a)
(b)
(c)
Figure 3: Experiments for Gp AT: (a) Model trained with various values and evaluated by J-(0-1) loss with J = and J sign-PGD. (b) Training curves of the AT with various p values. (c) Standard generalization performance of the models trained by the AT, where the green curves are copied from (a) for clearer presentation.
experiments for the G,- G,-PGDD-asees AT following the same experimental setting as in the previous section, except that Xp is adjusted to maintain the same volume of the balls (0, Ap) across dif- ferent p values (details in Appendix C Figure 3 (a) presents the experimental results on CIFARIO (results on the other datasets are in Appendix D Figure 5 and 6). The models are trained by Ar with π PPG for various p and are evaluated by the J-(0-1) loss with J (green curves) as well as J =ignn-PGD (blue curves). The yellow curve represents the generalization gap for models trained with -,GGG. As shown, larger tends result in larger generalization gaps. Indeed, nearly all PGG with p 2 1.3 cause notably overfitting in AT with generalization gaps exceeding 30%. The consistently higher position of blue star-shaped curves over the green star-shaped curve also suggests that sign-PGD is the strongest perturbations among the G,PPGD. Figure 3 (b) further exhibits the overfitting in PGD AT by plotting training curves for p {1, 2, 6), where continued training causes a rise of the testing errors (the blue and green curves), in contrast with the red curves, which demonstrate good generalization. Figure 3 (c) shows how the G,-PGI AT affect standard generalization where the red curves deontes the J-(0-1) loss with J Jjd and the green curves are copied from Figure 3 (a) for a clearer comparison. An enlarging standard generalization gap is also observed in PGD AT with larger p.
The observed overfitting caused by the Pp-PGD family is potentially attributed to that nearly all the members {Gp p E [1, do}} have a poor Lipschitzness, as shown in the following lemma, which leads to bad expansiveness of Gp-PGD
Lemma 6.1. Consider the mapping G, IRd + Ed specified in 14 with p [o]. Let I (1...., d). G is Opp Lipschitt over the set H (r) S Rd with H(r) = {o Rd :inier |x]i]] >
r} for some r > O, then we have
1
Op rd
We defer the proof in Appendix A This lower bound also implies that a, is unbounded in R2,, noting that the lower bound approaches infinity as - 0. Except for this extreme case, it is reasonable to assume that the gradients (x)(2)) lies in a set Hr) with sufficiently small r where the members in {Gp p E [1, }o}} have bounded but large Lipschitz constant. Noteworthy, the lower bound increases, as p ranges from to infimity, suggesting that the increased generalization gap in Figure (a) is attributed to the increasing expansiveness of Gp PGD caused by the rise in Otp-
LIMITATIONS
The main limitation of this work is that have only developed upper bound for the gener- alization of AT algorithms. Like all theoretical results based on upper bounds, they are adequate for understanding performance guarantees but may be inadequate explain poor generalization. Nonetheless, our experimental results have suggested that our upper bound may well explain robust overfitting.
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Maksym Andriushchenko and Nicolas Flammarion. Understanding and improving fast adversarial training. Advances in Neural Information Processing Systems, 33: 1008--1666, 2020.
Idan Attias, Aryeh Kontorovich, and Yishay Mansour, Improved generalization bounds for robust learning. CoRR, abs/1810.021 80, 2018. URL http: arxiv. wttp://.rrggab///100000/ 02180
Pranjal Awasthi, Natalie Frank, and Mehryar Mohri. Adversarial learning guarantees for linear
hypotheses and neural networks. CoRR, abs/2004. 13617, 2020. URL.pttpss//axxi.orrg
abs/2008 /204.204... 13617
Raef Bassily, Vitaly Feldman, Cristóbal Guzmán, and Kunal Talwar. Stability of stochastic gradient descent on nonsmooth convex losses. Advances in Neural Information Processing Systems, 33: 4381-4391, 2020.
Jeremy Bernstein, Yu-Xiang Wang, Kamyar Azizzadenesheli, and Animashree Anandkumar. signsgd: Compressed optimisation for non-convex problems. International Conference on Machine Learning, pp. 560-569. PMLR, 2018.
Olivier Bousquet and André Elissefff. Stability and generalization. The Journal of Machine Learn- ing Research, 226, 2002.
Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
Sébastien Bubeck et al. Convex optimization: Algorithms and complexity. Foundations and Trends@ in Machine Learning, 8(3-4):231-357, 2015.
Tianlong Chen, Zhenyu Zhang, Sijia Liu, Shiyu Chang, and Zhangyang Wang. Robust overfitting may be mitigated by properly learned smoothening. In International Conference on Learning Representations, 2020.
Yuansi Chen, Chi Jin, and Bin Yu. Stability and convergence trade-off of iterative optimization algorithms. arXiv preprint arXiv: /804.0160, 2018.
Francesco Croce, Maksym Andriushchenko, Vikash Sehwag, Edoardo Debenedetti, Nicolas Flam- marion, Mung Chiang, Prateek Mittal, and Matthias Hein. Robustbench: a standardized adver- sarial robustness benchmark. arXiv preprint arXiv:2010.09670, 2020.
Daniel Cullina, Arjun Nitin Bhagoji, and Prateck Mittal. Pac-learning in the presence of evasion adversaries, 2018
Zhun Deng, Hangfeng He, Jiaoyang Huang, and Weijie Su. Towards understanding the dynamics of the first-order adversaries. In International Conference Machine Learning, pp. 2484 2493. PMLR, 2020.
Dimitrios I. Diochnos, Saeed Mahloujifar, and Mohammad Mahmoody. Lower bounds for adversar- ially robust PAC learning. CoRR, abs/1906.05815, 2019. URL http://arxiv. abs/
1906.085 05815
Yinpeng Dong, Ke Xu, Xiao Yang, Tianyu Pang. Zhijie Deng. Hang Su, and Jun Zhu. Exploring memorization adversarial training. arXiv preprint arXiv:2106. 0606006066, 2021.
Farzan Farnia and Asuman Ozdaglar. Train simultaneously, generalize better: Stability of gradient- based minimax learners. In International Conference Machine Learning, pp. 3174-3185. PMLR, 2021.
Shaopeng Fu and Di Wang. Theoretical analysis robust overfitting for wide dnns: An ntk ap- proach. arXiv preprint arXiv:2310.06112 2023.
Ian J. Goodfellow. Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples, 2015.
Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability stochastic gradient descent. In International conference machine learning, pp. 1225-1234. PMLR, 2016.

---

Published as a conference paper at ICLR 2025
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Identity mappings in deep residual abs 05027
networks. CoRR, abs/1603.05027, 2016. URL /
Adel Javanmard, Mahdi Soltanolkotabi, and Hamed Hassani. Precise tradeoffs in adversarial training for linear regression. In Conference on Learning Theory, pp. 2034-2078 PMLR, 2020.
Justin Khim and Po-Ling Loh. Adversarial risk bounds via function transformation, 2019.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Iija Kuzborskij and Christoph Lampert. Data-dependent stability of stochastic gradient descent. In International Conference Machine Learning, pp. 2815-2824. PMLR, 2018.
Yunwen Lei and Yiming Ying. Fine-grained analysis of stability and generalization for stochastic gradient descent. In International Conference on Machine Learning, pp. 5809-5819. PMLR, 2020.
Yunwen Lei, Zhenhuan Yang, Tianbao Yang, and Yiming Ying. Stability and generalization of stochastic gradient methods for minimax problems. In International Conference on Machine Learning. pp. 6175-6188 PMLR, 2021.
Binghui Li, Jikai Jin, Han Zhong, John Hopcroft, and Liwei Wang. Why robust generalization in deep learning is difficult: Perspective of expressive power. Advances in Neural Information Processing Systems, 35:4370-4535 4384, 2022.
Chen Liu, Mathieu Salzmann, Tao Lin, Ryota Tomioka, and Sabine Süssttrukk. On the loss landscape of adversarial training: Identifying challenges and how to overcome them. Advances in Neural Information Processing Systems, 33:21476-21487, 2020.
Chen Liu, Zhichao Huang, Mathieu Salzmann, Tong Zhang, and Sabine Süsstrunk. On the impact of hard adversarial instances on overfitting in adversarial training. arXiv preprint arXi::2112.07324, 2021.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks, 2019.
Omar Montasser, Steve Hanneke, and Nathan Srebro. VC classes are adversarially robustly learn- able, but only improperly. CoRR, abs/1902.04217, 2019. URL http:://axxv..rr///eee
0992.04217
Wenlong Mou, Liwei Wang, Xiyu Zhai, and Kai Zheng. Generalization bounds of sgld for non- convex learning: Two theoretical viewpoints. In Conference on Learning Theory, pp. 605-638. PMLR, 2018.
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y Ng. Reading digits in natural images with unsupervised feature learning. 2011.
Tianyu Pang, Min Lin, Xiao Yang. Jun Zhu, and Shuicheng Yan. Robustness and accuracy could be reconcilable by (proper) definition. In International Conference on Machine Learning, pp- 17258-17277 PMLR, 2022.
Chongli Qin, James Martens, Sven Gowal, Dilip Krishnan, Krishnamurthy Dvijotham, Alhussein Fawzi, Soham De, Robert Stanforth, and Pushmeet Kohli. Adversarial robustness through local linearization. Advances in neural information processing systems, 32, 2019.
Aditi Raghunathan, Sang Michael Xie, Fanny Yang, John Duchi, and Percy Liang. Understanding and mitigating the tradeoff between robustness and accuracy. arXiv preprint arX1v:2002.10716, 2020.
Leslie Rice, Eric Wong, and J. Zico Kolter. Overfitting in adversarially robust deep learning. CORR, abs/2002.11569 2020. httttsss////aiiit org baarrg/ab//ae 2002.
Martin Riedmiller and Heinrich Braun. Rprop: a fast adaptive learning algorithm. In Proc. of the Int. Symposium Computer and Information Science VII, 1992.
12

---

Published as a conference paper at ICLR 2025
Ludwig Schmidt, Shibani Santurkar, Dimitris Tsipras, Kunal Talwar, and Aleksander Madry. Ad- versarially robust generalization requires more data. Advances in neural information processing systems, 31, 2018.
Ali Shafahi, Mahyar Najibi, Mohammad Amin Ghiasi, Zheng Xu, John Dickerson, Christoph Studer, Larry S Davis, Gavin Taylor, and Tom Goldstein. Adversarial training for free! Ad- vances neural information processing systems, 32, 2019.
Uri Shaham, Yutaro Yamada, and Sahand Negahban. Understanding adversarial training: Increasing local stability of supervised models through robust optimization. Neurocomputing, 307:195-204, 2018.
Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks, 2014.
Dimitris Tsipras, Shibani Santurkar, Logan Engstrom, Alexander Turner, and Aleksander Madry. Robustness may be at odds with accuracy. arXiv preprint 1805 12152, 2018.
Yihan Wang, Shuang Liu, and Xiao-Shan Gao. Data-dependent stability analysis of adversarial training. arXiv preprint arXiv:2401.00
2024.
Yisen Wang, Xingjun Ma, James Bailey, Jinfeng Yi, Bowen Zhou, and Quanquan Gu. On the convergence and robustness of adversarial training. arXiv preprint arXiv:2112.08304, 2021.
Eric Wong, Leslie Rice, and Zico Kolter. Fast is better than free: Revisiting adversarial training. arXiv preprint arXiv:2001.0333 2020.
Dongxian Wu, Yisen Wang, and Shutao Xia. Revisiting loss landscape for adversarial robustness.
CoRR, abs/2004.05884, 2020.
05884
Jiancong Xiao, Yanbo Fan, Ruoyu Sun, and Zhi-Quan Luo. Adversarial rademacher complexity of deep neural networks, 2022a.
Jiancong Xiao, Yanbo Fan, Ruoyu Sun, Jue Wang, and Zhi-Quan Luo. Stability analysis and gen- eralization bounds of adversarial training. Advances in Neural Information Processing Systems, 35:15446-15455 2022b.
Yue Xing. Qifan Song, and Guang Cheng. On the algorithmic stability of adversarial training. Advances in neural information processing systems, 34:26533-26535, 2021.
Yao-Yuan Yang, Cyrus Rashtchian, Hongyang Zhang, Ruslan Salakhutdinov, and Kamalika Chaud- huri. Adversarial robustness through local lipschitzness. CoRR, abs/2003.02460, 2020. URL
https: //tr:v//rrivvv./ org/ abss 2003. 02 62460
Dong Yin, Kannan Ramchandran, and Peter L. Bartlett, Rademacher complexxty for adversarially robust generalization. CoRR, htts//880.111144 2018. UBL.ttp://arxxvv.or///////
11914
Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. CoRR, Abs/1660.07114, 2016.
URL http://aariivoorrab///oo00.
http:/bss/16000 0111/
Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric Xing, Laurent El Ghaoui, and Michael Jordan. Theoretically principled trade-off between robustness and accuracy. In International conference on machine learning, pp. 7472-7482. PMLR, 2019.
Jingfeng Zhang, Xilie Xu, Bo Han, Gang Niu, Lizhen Cui, Masashi Sugiyama, and Mohan S. Kankanhalli. Attacks which do not kill training make adversarial learning stronger. CoRR, abs/2002. 1242, 2020. htLhhttss://att wwwp:lvoorrgr/o//aooeooeeee 11242
13

---

Published as a conference paper at ICLR 2025
A PROOFS
Proof of Lemma
(A,
sup sup S=5' (x.Ulexx)
BAls ((45))))))(((4)))/005444555...
(15)
sup (mx))Xa'))'
(16)
sup
A(S.)II
(w.))Xxx)
(17)
sup BA - A(S)
(a.))eX'))'
(18)
sup [A (. Lw sup EA BAllA(S) (nn))Xxy
A(S")
S=S"
(19)
The inequality 17 is derived based on the condition We now deal with the first term in (19)
For shorter notation, let S() == ||A(S.) A(S))l- For any number c* 2 0, let
Pr((S...))) c²). For any y we have
E -
(20)
=(1 -
J(z; A(S))) D(S., 20
(21)
+ Q(555.55.7BB.11221111114-5)5----
(()., <c'
(22)
- (1,,,, D(S,,,
D(S., S))
= Lx2vd
(23)
Sq.
(24)
5/- (J)Lx sup E
(25)
8=
The derivation above start by splitting the expectation into two conditional expectations conditioned on two complementary events (see the terms (2T) and (22)) and then utilize the e- c-expansiveness
property of as well the condition that [xx y, w) E 1 (xre) to individually derive the first and second terms in 23 Plug the final expression above back in (19 the lemma is proved.
Consider the AT algorithm specified in 7 and For two datasets and S' differing in only sample and respectively containing samples, let { Ww Jz= and {w W respectively denote the sequences of model parameters generated by running AT on 5 and S" for T iterations. Let e denote the smallest non-zero value of [| w/ll across / and across the randomness of when running AT algorithm A on S and S' (Note that such a choice of may be overly pessimistic, but it suffices obtain the desired rate of vanishing of the generalization bound in this theorem). For arbitrary iteration t E (1,...,33 T - 1}. we have
Proof of the Theorem 4.1
E |1411 1 w/+1ll
< V wt (we, (z
Ta V wf (w/, < we), v) w/ll + E. (w/, T ( /// w(),y') - 7. V wt (w/, ((:; y, wr).
(26)
Here the expectation is taken over all the randomness in wy and w/. We use (æ, and (a', v") respectively to denote the samples selected by the AT algorithm from S and S' at the iteration t. Inequality (26) is derived by adding and subtracting the term 7, V wt f (w/, <(;; y, we), y) and then applying the Triangle inequality. For the first term in (26). we have that
E w Ta V w (wi, TT:; y, wx) v) V wt (w/, (x: will
< w. w''l 7, W. wi(ll
(27)
by utilizing the triangle inequality and the condition 5 To deal with the second term in (6).. we consider that each iteration, with probability 1 T/n the samples selected by AT respectively
14

---

Published as a conference paper at ICLR 2025
from S and S' are the same. We have
Te V w ʃ (w/, <a': v', w(). - Te -e wwzJ (w/, (2; y, we), y)
Tel x [ w/) - w,)l || + 2n, L-w
-
(28)
TeT qe - w/ll + 2
14
(29)
The first term in (8 and (30) make use of the condition 5 and then the expansiveness condition
of и. Since f is Lw- Lipschitz w.r. W, we have V fw: v)ll s Ly for Vx, y, w. The second
term 28 then follows.
Putting together and considering the step sizes 7i S B. we have
Bll 01t1++1 w/+11l
27eL
<1 3T. + 1/1n/n][xxx(((( Bl|w woll +
(30)
n
$ 3r. + (x)c(TT) Ellw w/ll 2
(31)
n
2Lw
(2 + xx
(T) (x)g(()/2)) BlJwr w/ll
(32)
nB
Unravelling the recursion, we have
2Lw
WT w//1| S
5t
(33)
nB
(=0
where we take Ç 5 2 [xqa(m)/B.
Proof of 12 Let a > 2 be a constant. For shorter notation let 2 = - -
We
will show that the second moment EZ O , we can take EZ with ( and
b E (1, a 2)2, such that the probability Q(c*) decay at the rate of ---m. This is due to that
Q(c*) Pr I S e*]
(34)
Pr [ < BZ - 1] s Pr (t S 1 EZ
(35)
(36)
Var(Z)
(37)
12
EZ
(38)
12
(
1//1
0
(39)
1/n2h
n2 2b
where the inequality (37) is based on the Chebyshev's inequality. Note that such a choice of t will guarantee that c* 0 such that the derivation above is nontrivial. This is because Theorem
implies that EZ < (Ax)) = ( and therefore e² = - J.)) Taking > guarantees that
c² 0.
The proof is based on a slight modification of the proof in Theorem 4.1 We start from the inequality (26). For the first term (6). since that the loss function f is convex and 7i S 1/3 2/8, according to Lemma 3.7.2 in Hardt et al. (2016), we
Proof of the Theorem
4.3 and Corollary 4.4
have
E W Ta V I (wi, T (, V ma (w/, (x; p, v) will
< Elww, -w'll
(40)
When f is further assumed to be μي strongly convex, we have that μ < since f is also 3 smooth, implying that 7, < } < 2_ According Lemma 3.7.3 in Hardt et al. (016)) we have inequality
15

---

Published as a conference paper at ICLR 2025
as
E U2
To V Ve (wr, (T; + VVV wt (I; - will
BuTe
1
Bllws wi'l
(41)
+ 11
1
< 2 Tele
Blllw - will
(42)
In fact, since μ S 3, we also have S can be further simplified as
28 and thus TMP S
2np 3+h
with Tepe S 1. The inequality
B+
422
The second term in 26 follows the same derivation in the proof of Theorem 4.1 Putting together, when f is convex, we have
E Wt+1 u'41ll
(1++''x Bllwa will + Lw
(43)
2!w
< (1 + Ix xx+ Ellu w/ll + n..
(44)
when f is 1 strongly convex, we have
E W+++ w1(1ll
Lw
2 Tepl (x Bllux - w/ll -wgl
(45)
n
/ (x)g(T)/8
El|ls will
2L r2/3
(46)
233
Unravelling the recursion, we have
2Tw
B w/y1l
Σ 5²
(47)
nB
t=
with < = 111=====+xxxgx////0 when is convex and ( convex. For the strongly convex case, if we let (T( geometric series Σ 5 converges T + and entails closed form. The bound in (47) can therefore be further simplified as
tt + (x when f is μー strongly 2 we have 5 In this case, the
<
T
2Lw
E WT w/ <
c
n2 1=0
2Lw 5²
(48)
n2 1=0
2Lw 1
(49)
nB 1 1-6 C
4Lw
(50)
n(n 2T(
This derives the bound in Corollary 4.4
Proof of Lemma 5.1 To establish the proof, we first discuss the expansive property of the one step PGD perturbation T. For arbitrary E X, we have
T (T,y (z; w) T Te.y (#; Il
(51)
[[..)...z.e) [ AG (V (Ve &, w))l (L,,)) ( XG (Vaf(w (W,,,,100)0)) x.)i
(52)
<A ||G (V GVa (w' 2,,))
(53)
<Aa || ( vw 2. x)ll
(54)
<tal w/w w'll
(55)
16

---

Published as a conference paper at ICLR 2025
The inequality (53) is due to that the projection operation (z.c) is I-expansive. The inequalities 54
and (55) are derived based on the Lipschitz condition of G and Vaf.
For fixed E W, we have for arbitrary x', x" X
IT (x'; w) - (x=;"")w))
(56)
|| (z,c) [z' + AG
- I (x" +G XV f(w, f(w,=" ,,),)
(57)
s || + AG (V f(w, x ,)) - + XG f ,2)ll
(58)
E||=² - I + Xa V. / (wc, .)) - Sw, .1)l
(59)
$1 + Aar) x"Il
(60)
The derivation here follows the similar idea above, utilizing the 1-expansiveness condition of 1e (z,c) as well as the Lipschitz condition of G and the smoothness condition of f w.r.t X.
We now derive the upper bound for the expansiveness of x PPGD With a little abuse of notation,
let JK = TK (1; w) and similarly x'x
T.K ( w'). For shorter notation, let = w and
1 Aam
| PGD (2: y, w) - π PGD (o:y, w'll
(61)
|T (x; w) IxK, [=,y(x; (x;
(62)
[Tx - T (2.0(xkK111> w')l
(63)
( - T2, [K (I w'll + (xx-1;;)))) Te, (
(64)
<x || - wlll + 11 | - 2 K-
(65)
π || - w'll + 14| Tr. ( xxx w) - Ta., ( (x
(66)
K
1 w -w'l
(67)
00
Note that the bound 67 holds for any choice of w, w'. On the other hand, using the condition that Tz.y (#: w) E Bo (x, c), we can derive that for any w, wt E W with ||
w'll > c.
2v
2v w w'll
( w) T2.0 w'lll 2vdc=
11w - will
(68)
||
w0ll
Putting together, we have
K-1 Σ p'v,
2vde
9e PGD) & min
(69)
i=0
This completes the proof.
Proof of Corollary 5.2 We first establish the following result.
For any non-negative random variable bounded below B and any c" > 0,
Pr|Z s cc' B EZ( c*
(70)
This result simply follows from Pr/Z < c*| = Pr[B Z 2 B c*] and applying the Markov Inequality random variable B Z.
Now let Z
A(S) A(S') and c* = Bn 1/2 in Theorem 4.2 The second term in bound Devd, which converges to supswar EI ([)) Lx 2evd with It can be verified that the first term in the bound
of Theorem 4.2
then reduces to (1- sups=g B[JA(S)
Lx
B(1-x-174)
of Theorem 4.2
vanishes with (as n -1/2). The corollary then follows.
n.
17

---

Published as a conference paper at ICLR 2025
Proof of Lemma 6.1 The proof is established by noticing that all members in the set (r)) |x||]| = r, Vi E 2} achieves 1/(rd=) --iischitz and thus the Lipschitz constant over
{a E R2
(r)) is greater than it. Specifically, for any x, å E (r) with x o f, I_ == {i E I sgn + sgn(((()) and I, = I I_. We have
[[G(z) (())ll2
(71)
sgn(2) O |-=1-11
sgn ④) o |
(72)
||
||
2
sgm (g (2
sgn
(g(( 9-
(73)
||=|
|
sgm (xr [
sgn [
8-1
sgn [g](=[<<)\<<AA]
sgn ( [k:)
[k]]]
2-
+
c 18
|
2 12
|
(74)
2 1
2
(75)
1d-
KET
2
(76)
d=
where II_ denotes the cardinality of the set I.. The equality 75
is derived by noting that the first
term in is zero since |=[i]]| = |ززا]| and sgn([>[]i]) sgn([=[]]) for each j E I+ and noting
that ||00|o = rd for any x H (r). The power term 2-1 replaced by 1 since 1/q + 1/p = 1. We
also have
- #112
(77)
Σ [x]||] - a [b]1
(78)
- *b11
Σ
|a[k]] - =|/112
(79)
TET.
RET.
|
(80)
KEI
/ [
(81)
Putting together, we have that for any x, f (r) with x + 4,
[G(z) - G())ll2
[G(x') - G(I")ll2 = Cpp
sup of (.EEQ)) x'
(82)
x f 11
rd
xx' - z ||
This completes the proof.
B HYPER-PARAMETER SETTINGS FOR THE EXPERIMENTS
In our experiments, we follow the settings in Rice et al. be e = 8/255 w.r.t the sc-norm for the three datasets. The pre-activation ResNet 18 (PRN-18) model (He et al.) 2016) is used for CI and SVHN. The Wide ResNet 34 (WRN-34) model Zagoruyko & Komodakis 2016) is used for CIFAR- 100. We set K = 10 for all the PGD variants with À = 2/255 on CIFAR-10 10 and CIFAR- 100, and set À 1/255 for SVHN. The initial learning
(2000): The perturbation radius is set to
18

---

Published as a conference paper at ICLR 2025
rate of AT is set to be 0.1 for CIFAR-I0 and CIFAR-100 and set to be 0.01 for SVHN. The learning rate is decayed by 0.1 at the 100th and the 150th epoch the training. The batch size is set to be 128 and weight decay of 10 is used for all the experiments. The experiments our internal GPU clusters. Training PRN-18 on CIFAR- 10 and SVHN for 200 epochs spends around 18 hours with two NVIDIA v V100 GPUs, and training WRN-34 on CIFAR-100 requires around three days to complete with the same computing resources.
conducted on
C COMPUTING Xp
The volume of (O, Ap) is computed by
2T
+
vol (0,
X
(83)
Here r(-) denotes the Euler's gamma function. For p other than oo, to make vol (O,, Xp))
vol (Bxx (0, )o, we have
Ap exp {
mn d In
1)
(84)
p
rG + 1)
In the experiments, the value of A (i.e., the step size for the sign-PGD) is set to be the same as in Section and values for other Xp is computed from (84).
19

---

Published as a conference paper at ICLR 2025
D OMITTED FIGURES
(a)
(b)
Figure 4: Experiments in Figure reproduced SVHN and CIFAR-100.
Intourd Ci
(a)
(b)
Figure 5: Experiments in Figure reproduced on SVHN.
(a)
(b)
Figure 6: Experiments in Figure
reproduced on CIFAR-100.
E COMPARISON WITH THE WORKS IN XIAO ET AL. (2022B) AND WANG ET AL. 2024)
Since the work of Wang al. (2024) is built upon the framework in Xiao et al. (2022b), we here only presents the connections and differences between Xiao al. (022b) and our work.
Summary of generalization bounds in Xiao et al. (2022b) First would like to note that the problem setting in this paper includes the setting in Xiao et al. (002b)) as a special case. Specifi- cally, the generalization gap discussed in Xiao al. (2022b) corresponds the generalization gap GJ,, AA)) defined in this paper, where the perturbations both Josos and the AT algorithm taken as the optimal adversarial perturbation J"
This work and Xiao et al. (2022b) both take the Lipschitzness and smoothness conditions of the standard loss the starting point, but derive generalization bounds from different perspectives:
20

---

Published as a conference paper at ICLR 2025
the work in Xiao et al. (2022b) defines and proposes study the 17 approxiiia smoothness of the adversarial loss ( f in our notation) and derive generalization bounds based on this quantity. This work defines the notion of exxpassivenness of the perturbation operator (e.g., J)) and show how this quantity affects generalization performance of AT.
For completeness, here present the definition of 17 approximate smoothness, rewrite the Defini- tion 4.1 Xiao et al. (2022b) using the notations in this paper.
Definition E.1 appaappoo smoothness Xiao et al. (2022b)). loss function fa is called 7 ap-rrxxximmalll 3-gradient Lipschitz if there exists B 0 and nf > such that for any (z, EXXx y and for any w1, W2 E W we have
(Vr F. ff) 2, v)ll Bl[ - w2ll +
(85)
The work in Xiao al.) (2022b) then derives generalization bounds for loss functions that are ?) a-approximately smooth. For example, after replacing the notations in Xiao et al. (2022h) with ours, Theorem 5.1 of Xiao et al. (2022b) shows that if fy is mpapproximately 3 3-gradient Lips- chitz, convex in for all (z, y) and the standard loss satifies the same Lipschitz condition in (6) of this paper (or Assumption 4.1. in Xiao et al. (022b)), then their bound Theorem 5.1 becomes
To
21 W
GG.(J.A)
3 nT +
n
The authors of Xiao al. (2022b) show that the adversarial loss f satisfies 1-approxxmmaelly 3- gradient Lipschitz with r = 2I x so that the generalization bound above gives their generalization bound for adversarial training. In their determination of the r parameter, they have assumed that the standard loss f satisfies certain Lipschitz and smoothness condition; this condition is effectively equivalent to the condition (5) in this paper.
It is worth noting that the generalization bounds derived based on the approximate smoothness parameter 7) contain term unrelated to the sample size because of the independence of r on n.
The limitation of the framework in Xíao et al. (002bb) We would like note that when the standard loss f satisfies the Assumption 4.1 in Xiao et al. (2022b) (or condition (5) in this paper), in fact every Jososs (for any arbitrary J, including but not limited to JJ*) is 2 xx approximately smooth. To see this:
V w. ful, v. - V ww v)
[Va, [(w], J(: (x; wn) y) V fw, w2)
(86)
< w2|l + x (4; w1) - J(x; w2)ll
(87)
<BI|w wall + Fx [1] (z: w.) xI1 + | [ w2)l
(88)
<8 w2ll + x
(89)
where inequality 87 follows from Assumption 4.1 in Xiao et al.
2022b Inequality (88 and (89)
derived by using the triangle inequality and the condition that [ y, xl for any w E W.
Due to the fact that all the Josses have the same approximate smoothness parameter 7,. the gener- alization bounds derived for different J-loss, based on the framework in Xiao et al. (2022b). will be the same. This type of generalization bound ignores the influence of the perturbations used in AT on generalization and it is therefore unable to explain the experimental observations in Section 5 and of this paper where different choices of perturbations indeed have distinct impact on generalization.
Difference of our approach from Xíao et al. (002b In this paper, depart from the approach of Xiao et al. (022b)). which ignores the specific properties of perturbation J, and take a different route which considers the impact of measured via its expansiveness parameter. Our approach allows us to analyze how different perturbations used AT affect its generalization performance. Our bounds, derived based the expansiveness parameter, also avoid having the non-vanishing
21

---

Published as a conference paper at ICLR 2025
term (like the first term in Theorem 5.1 of Xiao et al. (2022b) when the expansiveness parameter is finite. Only in the case when the expansiveness parameter is unbounded, our results are similar to Xiao et al. (202bb), where the generalization bound contains a non-vanishing term.
The UAS parameter AT characterizes the gap || - w'll where w A(S) and w' A(S") the model parameters produced by the AT algorithm Intuitively, the difference between w and w' arises from the single different example in and S" (where larger training sample size tends reduce the probability of using that single different example to update model parameters in AT), and gets "magnified" by the perturbation along the AT training trajectory. The expansiveness parameter of J in this paper effectively captures this "magnification" factor. Thus, the eventual difference between w and w' depends on not only the sample size n but also the expansiveness parameter of Then the exploitation of the expansiveness of J brings sample size into the bounds.
nearly identical datasets 5 = S'
22


Reviews:
[{"review_id": "O5CroOzZR3", "reviewer": "Reviewer_e9T9", "summary": "Authors study the generalization of adversarial training with projected gradient descent. They provide uniform stability upper bounds of the generalization gap that consider the expansiveness of the adversarial attack operator. In the particular case of replacing the $\\text{sign}(x)$ operation in the PGD attack with $\\text{tanh}(\\gamma\\cdot x)$, they can show that their generalization upper bound decays to zero with the number of samples $n$ for a finite value of $\\gamma$. The experimental evaluation shows the tradeoff between generalization and robustness given by $\\gamma$, where smaller values of $gamma$ obtain good generalization but poor robustness and the opposite happens for larger $\\gamma$.", "questions": "- Some small typos: \n\t- Line 190: pernutation -> permutation\n\t- Line 267: exist -> exists\n\t- Line 483: It then curious -> It is then curious\n\n- How does the bound in [1,2] change when considering $\\text{tahn}_{\\gamma}$-PGD?\n- Have you tried larger $\\gamma$s? $\\gamma = 10^{5}$ seems to be very far from sign-PGD in Figure 2 (b).  It would be interesting to see how does $\\text{tahn}_{\\gamma}$-PGD behave when it’s close to sign-PGD.\n- Can you construct an experiment where the dependence on $n$ is displayed? For example taking a smaller number of samples from the studied datasets in order to see how the generalization gap grows. A synthetic distribution could also be employed where more and more samples are drawn and the gap decreases to zero for finite $\\gamma$.\n\n**References:**\n\n[1] Wang et al., Data-dependent stability analysis of adversarial training, ArXiv 2024.\n\n[2] Xiao et al., Stability Analysis and Generalization Bounds of Adversarial Training, NeurIPS 2022", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "- Simple theory and easy to follow paper. I didn’t read the proofs in full detail, but the main paper is easy to follow and the analysis and experiments are reasonable.\n\n- I found the analysis of the expansiveness of the adversarial attack operator very interesting and up to my knowledge, this has not been considered before.\n\n- When considering finite $\\gamma$, authors can show that their generalization upper bound converges to zero with increasing number of training samples $n$.", "weaknesses": "- Authors claim that their upper bound converges to zero with increasing number of training samples $n$ and the ones of [1,2] do not. This is misleading as [1,2] do not consider the expansiveness of the attack operator and the bound provided in this work, in the same setup as [1,2] does not vanish with $n$ (see lines 369-371). \n\n- The difference with the previous bounds is not clearly covered in the paper. The proof technique and assumptions are very similar to [1,2], nevertheless the bounds in [1,2] are not presented in the work and there is no discussion about how to integrate previous bounds with the expansiveness setup introduced in this work, making it difficult to assess the contributions. It would be nice to add a discussion about which role expansiveness plays in the result of [1,2], i.e., can it result in a vanishing upper bound with $n$? It would also be good to have a table comparing the different upper bounds.", "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": "", "extra_scores": {}}, {"review_id": "H3wrsJ0Bx2", "reviewer": "Reviewer_2VnC", "summary": "This paper studies generalization bounds for robust training by leveraging the framework of uniform stability. The authors analyze $\\ell_\\infty$ perturbations and derive several upper bounds on the generalization gap of predictors. They then investigate experimentally the performance of adversarially trained models using several algorithms to solve the inner maximization problem of the robust objective.", "questions": "- Which part of the analysis bypasses prior work and makes the bounds decay as $O(\\frac{1}{n})$?\n- In the experiments of Section 6, why do you change the threat model (finding different values of $\\lambda_p$)? One could imagine experiments with different steepest descent algorithms for the solution of the inner maximization problem, where the threat model does not change (i.e., projecting every time to the same $\\ell_\\infty$ balls around the original points). Of course, different steepest ascent algorithms (besides the commonly used sign gradient ascent) will perform worse in finding adversarial examples, so the number of inner iterations should be adjusted appropriately. However, I believe this could be an interesting experiment to conduct.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The paper studies an interesting problem: the large generalization gap of robust empirical risk minimization (adversarial training) in neural networks. This work leverages the framework of uniform stability, which has been rather unexplored in the robust learning community, and could potentially provide insights on this topic. Based on the theoretical analyses, the authors propose a sensible relaxation of the commonly used PGD attack, using the $tanh$ function instead. Finally, I agree with the authors that the optimization algorithm in the inner maximization problem has not received adequate attention in the literature, and thus, its study is welcome (despite its limitations—see below).", "weaknesses": "The paper is unfortunately difficult to follow, making it challenging to assess its content due to presentation issues. Furthermore, the conclusions seem unoriginal to me. In particular, I identified the following weaknesses:\n\n- Poor presentation: There are many instances where the text is not polished, with numerous grammatical errors (see the non-comprehensive list at the end of the Weaknesses). Additionally, the presentation of the technical results could be substantially improved (e.g., Theorem 4.1: remind the reader of the constants $\\beta, \\Gamma_X$). Furthermore, the authors should mention in the introduction that all of their results are solely about $\\ell_\\infty$ perturbations.\n- Introduction of many ad-hoc terms to denote well-established concepts: In many places, the authors use obscure words to define concepts that are well-defined in learning theory. For instance, lines 258-259: \"mis-matched generalization gap\" — this is just the standard generalization gap of a predictor trained robustly. Several such choices make it difficult for readers to comprehend the contributions of this work. Similarly, with so-called \"RG-PGD\" and the \"expansiveness property\" (a relaxed notion of Lipschitz continuity).\n- Unclear contributions: The paper does not clearly describe how the derived bounds differ from those of Xiao et al. (2022b) and Wang et al. (2024). In particular, the bounds from these prior works are not presented, and they are solely critiqued on the basis that they do not vanish with increasing sample size. Furthermore, the criticism of the non-smoothness of the loss function adopted in prior work seems unfounded (\"The source of the non-smoothness is, however, not explained in their work\"). Even for linear models under $\\ell_\\infty$ perturbations, a cross-entropy loss is non-smooth. Hence, the property of non-smoothness is well-motivated.\n- Unclear motivation for experiments: The authors seem to identify the sign function in the solution of the inner maximization problem in the robust objective as problematic, and they suggest an alternative based on a smooth approximation. However, they do not show any benefits in terms of robustness with the new method. Furthermore, the fact that for small $\\gamma$ we do not observe overfitting and the generalization gap is small appears to be a trivial observation, as the evaluation basically approaches the standard case of no perturbations. In short, it is not a good method for finding worst-case $\\ell_\\infty$ perturbations.\n- Results of Section 6: The authors mention the connection between adversarial training and steepest descent methods, but it is clear that this has been the motivation for the iterative solution of the inner maximization problem since the introduction of adversarial training. Furthermore, the experiments fail to highlight anything new, in my understanding (basically optimising an $\\ell_\\infty$ objective yields better coverage against $\\ell_\\infty$ attacks).\n\nGrammatical errors (non comprehensive list):\n- in the abstract: \"These expansiveness parameters appear not only govern the vanishing rate of the generalization error but also govern its scaling constant.\"\n- line 190: \"perturnation\" -> perturbation\n- line 202: \"related with\" -> related to\n- line 241: \"draw\" -> draws\n- line 245, 256: \"descend\" -> descent\n- line 316: \"independent with\" -> independent of\n- lines 536-537: \"Like all up-bound based theoretical results, such an approach is adequate for understanding performance guarantees but may be inadequte to explain poor generalization.\"", "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": "", "extra_scores": {}}, {"review_id": "QFekwNzx5X", "reviewer": "Reviewer_Fpbq", "summary": "This paper studies the algorithmic stability of adversarial training with a focus on how the inaccuracy of PGD attack affects the stability. Theoretical analysis are provided to justify that the sign function in PGD updates can significantly harm the stability, leading to a worse generalization (gap).", "questions": "Please address my comments above.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "(1) This paper is clear and easy to understand.\n\n(2) This paper studies the algorithmic stability of adversarial training from an interesting angle of the PGD attack.\n\n(3) Experiments demonstrate that using tanh to replace sign function can improve the generalization performance.", "weaknesses": "(1) While the paper considers the algorithmic stability of PGD attack, a missing component is the convergence of PGD attack. Intuitively, if we always use a fixed attack direction, then the algorithmic stability is not largely affected by the attack. However, the attack is not efficient. When using PGD attack, there is supposed to have a trade-off: with more iterations, the stability gets worse, but the attack becomes stronger. If at the test stage the attacker uses a very strong attack, e.g., AA attack, then balancing the attack effectiveness and stability is essential to obtain a better robust testing performance. Could the authors elaborate more from this perspective?\n\n(2) Please highlight the technical challenges for the theoretical contributions in this paper.\n\n(3) Please consider using some SOTA methods from RobustBench, e.g., leveraging synthetic data in adv training, to conduct the experiments. While improving the sign function seems to be helpful as illustrated by this paper, there is no enough evidence to demonstrate that this is one of the key issues in adversarial training.\n\n(4) Minor: In one line of research, to save the computation budget of adversarial training, algorithms have been proposed to explore fast adversarial training: instead of calculating the attack at each iteration, they update the attack for each sample for one step at each iteration, e.g., \n\nCheng, Xiwei, Kexin Fu, and Farzan Farnia. \"Stability and Generalization in Free Adversarial Training.\" arXiv preprint arXiv:2404.08980 (2024).\n\nI'm wondering if the authors can provide some comments on algorithms of this type.", "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": "", "extra_scores": {}}, {"review_id": "cFeCFL1RUU", "reviewer": "Reviewer_Jg1M", "summary": "This paper provides a new stability bound for adversarial training, where the inner maximization perturbation $J$ and the evaluation perturbation $\\pi$ can be different. The introduced term expansiveness can partly explain robust overfitting and experiments are conducted to validate the theoretical results.", "questions": "In total, I think this is a good paper, but there are some points that can improve this paper. Please refer to the weaknesses part.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The new stability theory differs from existing ones in terms of assumptions and the form of bounds. I like the separation of adversarial training perturbation $J$ and the evaluation perturbation $\\pi$, which means that the theory in this paper is a more abstract framework and can be applied in many cases.\n- The writing is good.", "weaknesses": "- It seems that the framework in this paper can not provide a proper description for the $Q(c^*)$ term, we need to calculate it according to the concrete choice of $J, \\pi$. However, to make this framework more significant, examples of how to calculate $Q(c^*)$ and how to choose $c^*$ should be added. Note: I mean examples in practice but not examples with overly simple assumptions (such as the assumption on the second moment in lines 293-294 and the assumption in Corollary 5.2 that a term is bounded by $B$ with probability 1). Just like the VC dimension, if we can not calculate the VC dimension of some hypothesis classes, the bound with the VC dimension is meaningless.\n- Typo: in line 149, it should be \"the label space $\\mathcal{Y}$ is finite\"\n- A minor issue: many equations in this paper are numbered, in fact, the equations that are not used later need not be numbered. For example, equation (2) is not used.\n- In lines 87-88, the paper says that \"the bound convergence to a constant, this helps explain the robust overfitting phenomenon\". In fact, a lower bound of the generalization gap that converges to a constant can explain overfitting. However, an upper bound can not because your bound may not be tight enough.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)