Stability and Generalization in Free Adversarial Training
Authors: Xiwei Cheng
Kexin Fu
Farzan Farnia
Venue: Accepted by TMLR ()

Abstract: While adversarial training methods have significantly improved the robustness of deep neural networks against norm-bounded adversarial perturbations, the generalization gap between their performance on training and test data is considerably greater than that of standard empirical risk minimization. Recent studies have aimed to connect the generalization properties of adversarially trained classifiers to the min-max optimization algorithm used in their training. In this work, we analyze the interconnections between generalization and optimization in adversarial training using the algorithmic stability framework. Specifically, our goal is to compare the generalization gap of neural networks trained using the vanilla adversarial training method, which fully optimizes perturbations at every iteration, with the free adversarial training method, which simultaneously optimizes norm-bounded perturbations and classifier parameters. We prove bounds on the generalization error of these methods, indicating that the free adversarial training method may exhibit a lower generalization gap between training and test samples due to its simultaneous min-max optimization of classifier weights and perturbation variables. We conduct several numerical experiments to evaluate the train-to-test generalization gap in vanilla and free adversarial training methods. Our empirical findings also suggest that the free adversarial training method could lead to a smaller generalization gap over a similar number of training iterations. The paper code is available at https://github.com/Xiwei-Cheng/Stability_FreeAT.

Published in Transactions on Machine Learning Research (11/2024)
Stability and Generalization in Free Adversarial Training
Xiwci Cheng
swchengGlinkk.c culkk edu.hk
The Chinese University of Hong Kong
Kexin Fu Purdue University
fu4488purdue. edu
Farzan Farnia
farvia Oese. cubkk edu. hk
The Chinese University of Hong Kong
Reviewed on OpenReview: https: //
// openreveew.eee..m net/ forum? id= (mw.iiCbbg
Abstract
While adversarial training methods have significantly improved the robustness of deep neural networks against norm-bounded adversarial perturbations, the generalization gap between their performance training and test data is considerably greater than that of standard empirical risk minimization. Recent studies have aimed to connect the generalization prop- erties of adversarially trained classifiers to the min-max optimization algorithm used their training. In this work, we analyze the interconnections between generalization and optimiza- tion in adversarial training using the algorithmic stability framework. Specifically, our goal to compare the generalization gap of neural networks trained using the vanilla adversar- ial training method, which fully optimizes perturbations at every iteration, with the free adversarial training method, which simultaneously optimizes norm-bounded perturbations and classifier paramcters. We prove bounds on the generalization error of these methods, indicating that the free adversarial training method may exhibit a lower generalization gap between training and test samples due to its simultaneous min-max optimization classifier weights and perturbation variables. We conduct several numerical experiments evaluate the train-to-test generalization gap in vanilla and free adversarial training methods. Our empirical findings also suggest. that the free adversarial training method could lead to smaller generalization gap similar number of training iterations. The paper code is com wwt.////wwwe--eoo///eaaaaaiiiiii
available at
1 Introduction
Deep neural networks (DNNs) have attained state-of-the-art results in various supervised learning tasks in computer vision, speech recognition, and natural language processing. However, it is widely recognized that DNNs are susceptible to minor adversarially designed perturbations to their input data, commonly regarded as adversarial attacks (Szegedy et al.) 2013 Goodfellow et al. 2014). Adversarial examples are typically generated by optimizing a norm-constrained perturbation leading to the maximum classification loss for input data. A standard approach to defending against adversarial attacks is adversarial training (AT) (Madry) et al. 2017), according to which the DNN classifier is learned using adversarially perturbed training data. AT methods have significantly improved the robustness of DNNs against norm-bounded perturbations. In recent years, several variants of AT methods have been developed to accelerate and facilitate the application
of AT to large-scale models and datasets (Kannan et al. 2018 Shafahi et al. 2019 Wong et al. 2020).
While AT algorithms offer significant robustness against standard norm-bounded attacks, the generalization gap between their performance on training and test data has been found be considcrably greater than that of DNNs trained by standard empirical risk minimization (ERM) (Schmidt al. 2018 Raghunathan 2019 To study the overfitting phenomenon in adversarial training, the recent. literature has focused et al.

---

Published in Transactions on Machine Learning Research (11/2024)
the generalization analysis of adversarially trained models. The studies have attempted to analyze the
generalization error in learning ad adversarially-roout models (Yin et al. 2019 Awasthi et al. 2020
Xiao et al.
(022b) and to show the reduction of generalization gap under explicit and implicit regularization methods
such as carly stopping and Lipschitz regularization (Rice et al. 2020
Zhang ct al.
2022
Xiao et al. 2023b)
Specifically, several works (Lei et al. 2021 Farnia & Ozdaglar 2021 Xiao et al. 2022b 2024b) have concen- models, Since adversarial training methods use adversarial training examples with the worst-case norm-bounded perturbations, they are typically formulated as min-max optimization problems where the classifier and ad- versarial perturbations are the minimization and maximization variables, respectively. To solve the min-max optimization problem, the vanilla AT framework follows an iterative algorithm where, at every iteration, the inner maximization problem is fully solved for designing the optimal perturbations and subsequently, a single gradient update is applied the DNN's parameters. Therefore, the vanilla AT results in a non-simultancous optimization of the minimization and maximization variables of the underlying min-max problem. However, the theoretical generalization error bounds in (Farnia & Ordaglar 2021 Lei et al. 2021 suggest. that the non-simultaneous optimization of the min and max variables in min-max learning problem could lead to a greater gencralization gap. Therefore, a natural question is whether an adversarial training algorithm with simultancous optimization of the min and max problems can reduce the generalization gap.
trated on the interconnections between the optimization and generalization of adversarially
In this work, we focus on a widely-used variant of adversarial training proposed by Shafahi et al. (0019) adversarial truining for free (Free AT), and aim to analyze its generalization behavior compared to the vanilla AT approach. While the vanilla AT follows a sequential optimization of the DNN and perturbation variables, the Free AT approach simultancously computes the gradient of the two groups of variables at every round of applying the backpropagation algorithm to the multi-layer DNN. We aim to demonstrate that the simultancous optimization of the classifier and adversarial examples in free AT could translate into a lower generalization error compared to vanilla. AT. To this end, we provide theoretical and numerical results to compare the genoralization properties of vanilla vs. free AT frameworks.
On the theory side, we leverage the algorithmic stability framework (Bousquet & Elisseeff 2002 Hardt et al. 2015) to derive generalization error bounds for free and vanilla adversarial training methods. The shown generalization bounds suggest that in the nonconvex-nonconeewy regime, the free AT algorithm could enjoy lower generalization gap than the vanilla AT, since it applies simullaneous gradient updates to the DNN's and perturbations' variables. We also develop a similar generalization bound for the fast AT methodology Gooodfelow et al.] 2014) which uses a single gradient step to optimize the perturbations. Our theoretical results suggest a comparable generalization bound between free and fast AT approaches.
Finally, we present the results of our numerical experiments to compare the generalization performance of the vanilla and free AT methods over standard computer vision datasets and neural network architectures. Our numerical results also suggest that the free AT method results in considerably lower generalization gap than the vanilla AT. Furthermore, we propose applying the free AT framework to implement TRADES, free-AT version of the adversarial training algorithm TRADES (Zhang et al., 2019). The numerical results suggest that the TRADES algorithm similarly has a lower generalization gap under simultaneous optimization of the min and max optimization variables. This work's contributions can be summarized as:
Applying the algorithmic stability framework to analyze the generalization behavior of free AT, Providing a theoretical comparison of the generalization properties of the vanilla and free AT methods,
Numerically analyzing the generalization performance of the free vs. vanilla AT schemes under white-box and black-box adversarial attacks,
Proposing Free-Trree Tree-TRDDE, a simultaneous updating variant of TRADES with better generalization.
2 Related Work
Generalization in Adversarial Training: Since the discovery of adversarial examples (Szegody et al.
2013), a large body of works has focused on training robust DNNs against adversarial perturbations (Good-
fellow et al. 2014 Carlini & Wagner 2017 Madry et al. 2017 Zhang et al. 2019). Shafahi et. al. (2019)
2

---

Published in Transactions on Machine Learning Research (11/2024)
proposed the free adversarial training algorithm to update the neural net and adversarial perturbations si- multaneously, aimed at reducing the computational cost of adversarial training. Also, WWon el al. (2020) discussed the application of the fast AT algorithm, aiming to lower the computational costs.
Compared to standard ERM training, the overfitting in adversarial training is shown to be more severe Rice
jet al. 2020). A line of works analyzed adversarial generalization by applying uniform convergence tools such
as VC-dimension (Montasser al.
2019
Attias et al. 2022 and Rademacher complexity (Yin et al.) 2019
Farnia al., 2018: Awasthi et al. 2020 Xiao et al. 2022a 2024ap. Schmidd et al. (2018) proved tight
bounds on the adversarially robust generalization error showing that vanilla adversarial training requires
more data for proper generalization than standard training. Xing et al. (2022) studied the phase transition of generalization error from standard training to adversarial training. Also, the reference (Andriushchenko
& Flammarion 2020) discusses the catastrophic overfitting in the Fast AT method.
Uniform Stability: Bousquet & Elisscoff (2002) developed the algorithmic stability framework to analyze the generalization performance of learning algorithms. [Hardt et al. (2013) further extended the algorit
stability approach to stochastic gradient- maddeent-based optimization (SGD) methods. [Bsssily et al. (2020): Lei (2023)
analyzed the stability under non-smooth functions. Some recent works applied the stability framework to study the generalization gap of adversarial training, while they mostly assumed an oracle to obtain perfect perturbation and focused on the stability of the training process. [ing et al. (2021) analyzed the stability by shedding light on the non-smooth nature of the adversarial loss. Xiao et al. (2022b) further investigated
the stability bound by introducing a notion of approximate smoothness. Based on this result, Xiioo et al. (2022c) proposed smoothed version of SGDmax to improve the adversarial generalization. Xiao et al. 2023a utilized the stability framework to improve the robustness of DNNs under various types of attacks.
Generalization in minimax learning frameworks: The generalization analysis of general minimax learning frameworks has been studied in several related works. Arora et al. (2017) established a uniform convergence generalization bound in terms of the discriminator's parameters in generative adversarial net- works (GANs). Zhang et al. (2017); Bai et al. (2018) characterized the generalizability of GANs using the Rademacher complexity of the discriminator function space. Some work also analyzed generalization GANs from the algorithmic perspective. Farnia & Ozdaglar (2021); Lei al. (2021) compared the gener- alization of SGDA and SGDmax in minimax optimization problems using algorithmic stability. [Wu et al.
(019)) studied generalization in GANs from the perspective of differential privacy. Oxdaglar el. al. (2022) proposed new metric to evaluate the generalization of minimax problems and studied the generalization behaviors of SGDA and SGDmax.
3 Preliminaries
Suppose that labeled sample (x, y) is randomly drawn from some unknown distribution D. The goal of adversarial training is to find a model fw with parameter w e W which minimizes the population risk against the adversarial perturbation from feasible perturbation set A, defined
R(w) = B( max h(w, 8; 8; v)
SEA
where h(w, 5;,r, v) = Loss(fu(x + v) is the loss function in the supervised learning problem. Since the
learner does not have access to the underlying distribution D but only datasct S = (21, T2, ,.n] J of size n, we define the empirical adversarial risk as
Rs(w)= = Σ max hw, 5; dEa
The generalization adversarial risk Egen (w) of model parameter w is defined as the difference between pop- ulation and empirical risk, i.c., Egen == R(w) Rs(w). For a potentially randomized algorithm which takes a dataset S as input and outputs a random vector w A(S), we can define its expected generalization adversarial risk over the randomness of training set S and stochastic algorithm A, e.g. under mini-batch
3

---

Published in Transactions on Machine Learning Research (11/2024)
selection in stochastic gradient methods random initialization of the weights of neural net classifier, Egen (A) == ISs (R(A(S) - (s((()))
to denote the L2 norm of vectors or the Throughout the paper, unless specified otherwise, we use ||
Frobenius norm matrices.
3.1 Adversarial Training
In standard applications of adversarial training, the perturbation set A is usually an C2-norm or - bounded ball of some small radius (Szegedy al. 2013 Goodfellow al.) 2014). To robustify neural network, the standard methodology AVanilla to train the network with (approximately) perfectly perturbed
samples, both in practice (Madry et al. 2017 Rice el al. 2020 and in theoretical analysis (Xing et al. 2021
Xiao et al.
2022b), which is formally defined as follows:
A Algorithm Vanilla Adversarial Training Algorithm Avanilla
1: Input:
Training samples S, perturbation set A, learning rate of model weight aw mini- batch size b, number of itcrations T
for slep + 1,1,,-. .,., do
Uniformly random mini-batch B BCS. of size
Compute adversarial attack 65 for all (xj,);)) E B: 8j t arg maxzea h(w, 8; Update with perturbed samples: t- a= (e V Fwh(w,6f:2,,1
6: end for
In practice, due to the non-convexity of neural networks, it is computationally intractable to compute the best adversarial attack d arg maxjes h(w, 0;,),, but the standard projected gradient descent (PGD) attack (Madry et al. 2017) is widely believed to produce near-optimal attacks, by iteratively projecting the gradient V 7ah(w, x: onto the set of extreme points of A, i.c.,
(9(9)= = arg min
l|g - 8112
BeEstremePointt(()
updating the attack d with the projected gradient TA (V(Ww, (1 8;z)) and some step size as, and projecting the update attack the feasible set A, i.e,
Pa(g) = arg min [|g 811
(2)
dEA
Despite the significant robustness gained from Avanilla it demands significant computational costs for train- ing. The Free adversarial training algorithm AFron (Shafahi et al. 2019) is proposed to avoid the overhead cost, by simultaneously updating the model weight parameter w when performing PGD attacks. AFree is em- pirically observed achieve comparable robustness to Avanilla while can considerably reduce the training
time (Shafahi et al. 2019
Wong et al. 2020)
A Algorithm 2 Free Adversarial Training Algorithm AFree
Input: Training samples S, perturbation set A, step size of model weight. Oww learning rate of adversarial attack as, free step m, mini-batch size b, number of iterations T for step + ..., 1... 3: Uniformly random mini-batch B S of size
T/m do
4: == (5 () <- Uniform(A*)
5: for iteration i - 1......
do
6:
Compute weight gradient and attack gradient by backpropagation:
Iw + & E(e Vwh(w, Szz vs), and gs + [Vsh(w, 8y; 8ill Update with mini-batch gradient descent:
w awlw
Update 8 with projected gradient ascent: 8 - (6, + (aoTs(9s) 111
10: end for
11: end for
4

---

Published in Transactions on Machine Learning Research (11/2024)
We also compare Avanilla and AFree with the Fast adversarial training algorithm Apatt Wong et al. 2020 variant of the fast gradient sign method (FGSM) proposed by Goodfellow et al. (2014). Instead of computing a perfect perturbation, it applies only one projected gradient step with fine-tuned step size from a randomly initialized point in A. Apast empirically shown to achieve comparable robustness to the standard PGD
training with lower training costs (Wong al., 2020 Andriushchenko Flammarion 2020
A Algorithm 3 Fast, Adversarial Training Algorithm A
Input: Training samples X, perturbation set A, learning rate of model weight aws step size of adver- sarial attack ds, mini-balch size b, number of iterations T
2: for step & + 1, ................... T do
3: Uniformly random mini-batch B S of size
Compute adversarial attack with random start:
ò = ( (D)B < Uniform(A")
6: 9s + (,,
d [Pa(o, a (2:4,))))
Update with perturbed sample: w ax Ee 6z
end for
4 Stability and Generalization in Adversarial Training
To bound the generalization adversarial risk, the notion of uniform stability with respect to the adversarial loss is introduced (Bousquet & Elisseeff 2002).
Definition 1. randomized algorithm A is e-uniformly stable if for all datasets S, S' E D such that S and S' differ in at most one example, we have
sup EA max ((A(S), - max ((A(s))A))))))))))))))))))())))) 6: SE.
(3)
REA
ΛEA
Similar to Theorem 2.2 Hardt et al. (0015), the gencralization risk in expectation of a uniformly stable algorithm can be bounded by the Tollowing theorem
Theorem 1. Assume that randomized algorithm A is e-uniformly stable, then the expected generulization risk satisfies
Egenl = ((sTA(())))R(((())))) Se.
Proof. The proof can be found in Theorem 2.2 in Hardt et al. (005 by replacing the loss function with the adversarial loss maxsea ((w,6;z)
In order to study the uniform stability of adversarial training, make the following assumptions the Lipschitzness and smoothness of the objective function. Our generalization results will hold long Assumptions 1 2 hold locally within an attack radius distance from the support set of X.
Assumption 1. h(w, 8) is jointly L-Lipschitz in (w, and -ippschht in over W x A, i.e., for every w/ E W and 8, 8' E A we have
[hww, 8) - hhww,8')) < T.2 (111 w/ w0112 11 8'113),
[uw,, 6) 1(w',0)) < L, 2|| w/11
Assumption hww, 5) is continuously differentiable and 3-smooth over W x A, dee, (V. 8), Voh(w, 8)] is B-Lipschite over W A and for every w, w W, 5, we have
|| I/Whhw 5) Vinh(w' 8')11 + Vah(w, 5) Voh(w', I B² (||w w0112 + ||ō - 5' 13

---

Published in Transactions on Machine Learning Research (11/2024)
We clarify that the Lipschitzness and smoothness assumptions common practice in the uniform stability
analysis (Hardt et al. 2015 Xing et al. 2021 Farnia & Oxdaglar 2021 Xiao et al. 2022b). In practice.
although ReLU activation function is non-smooth, recent works (Du et al. 2019 Allen- Zhu et al. 2019) showed that the loss function of over- nee--paamcttrized neural networks is scmi-smooth; also, another line of
works (Xie et al.) 2020 Singla et al. 2021 suggest. that, replacing ReLU with smooth activation functions can strengthen advesariial training; and some works (Fazlyab et al. 2019: Shi et al. 2022) attempt compute
the Lipschitz constant of neural networks.
5 Stability-based Generalization Bounds for Free AT
In this section, we provide generalization bounds on vanilla, free, and fast adversarial training algorithms. While previous works mainly locus on theoretically analyzing the stability behaviors of vanilla adversarial training under the scenario that h(w, d; ) convex in w (Xing et al. 2021 Xiao et al. 2022b), or f(w, 8; x)
is concave or even strongly-concave in 8 (Lei et al., 2021 Farnia & Ozdaglar 2021 Yang et al. 2022
Ozdaglar et al. 2022), our analysis focuses on the nonconvex-noncooneay scenario: without assumptions on the convexity of h(w, d; in w or concavity of h(w, d;2r) in 5. We defer the proof of Theorems
2 and to
the Appendix A.1 and A.2 Throughout the proof, we assuine that Assumptions [ and 2
hold.
Theorem 2 (Stability generalization bound Avanilaa. Assume that h(w, satisfies Assumptions 1 and 2 and is bounded in [0, 1], and the perturbation set is an C2-norm ball of some constant radius E, i.e.,
A {ō : ||6|| S E}. Suppose that we run A Vansila in Algorithm | Ouet & c/t. Let constant À Vanilla == Be, then
for T steps with vonishing step size
Egen(A (gensavons S
b (1 1
1
(e3n+11)
T 7 "'Venills +1
A
(4)
A Vanitla
By equation 4 we have the following asymptotic bound on (Avaniia)lla)) with respect to T and n
(AVanilla) = O (
Avanilla Avanllla /nn "Vaiilll
Avantll
(5)
This bound suggests that the vanilla adversarial training algorithm could lead to large generalization gaps,
Avauilla,
AVamilla
because for any === [[)), the bound T *Avanill+7 /n Avanills = ((1) is non- non-vanishing even when we are given
infinity samples. This implication is also confirmed by the following lower bound from the work of Xing
et al. g and Xiao et al. (2022b):
Thcorem 3 (Lower bound on stability; Theorem 1 in Xing et al. 2021), Theorem 5.2 in Xiao et al 2022b
Suppose A = (ō : ||²|| S e). Assume w(S) is the oulpul of ranming A Vanitaa the dalasel S with mini-balch size 6 = 1 and constant step size aw I 1/3 for T steps. There exist some loss function h(w, 8; which is differentiable and conver with respect to w, some constant & > O, and some datasets S and S' that differ in only one sample, such that
B[[[((S) w(S')l)2 Ω VT+
(VV T n
(+++T
(6)
This lower bound indicates that AVanilla could lack stability when the attack radius = RI),, hence the algorithm may result in significant generalization error from the stability perspective. Note that the lower bound in equation 0 is not inconsistent. with Theorem 2 in which the step-size is assumed to be vanishing aw,t I c/t and thus the lower bound is not directly applicable under that assumption. However, this constant generalization gap could be reduced by free adversarial training.
Theorem 4 (Stability generalization bound of AFree) Assume that h(w, 8) satisfies Assumptions and 2 and is bounded in [0, and the perturbation set is an L2-norm ball of some constant radius i.e.,
A A= {5 || v $}. Suppose we run A in Algorithmm for T/m sleps with vanishing step size Ow, S c ml and constant step size Cgg- If the norm of gradient Voh(w, d; is lower bounded by 1/2b for constant tb > 0 with probability during the training process, let constant A == Be(1 + Be/m + ( then
Egea(A A Free) S b (1
1
22L bB
Apre+T
T
Aprctt
X
(7)
A
m
6

---

Published in Transactions on Machine Learning Research (11/2024)
Remark 1. To validate the soundness of the assumption on the lower-bounded norm Voh(w, 5;x) by constant 1 1/p in practical sellings, in Appendiz B.6 we present the remmrrica evoluation of the gradient norm over the course of ATee-AT' on C-FAR-10 and CIFAR 100 data, indicating that the norm is consistently lower- bourdb by O(10-3) in the experiments.
Remark 2. Theorem 4 indicates how the simrultaneous updates influence the generalization of adversarial we have the following asymptotic bound on gA with respect T and training. From equation 7
Egen(AFree)= O (0
Arree /nl)
(8)
Therefore, by controlling the step size 0gg of the marimization step, we can bound the coefficient XFree and thus control the generalization gop of Apree where lower og can result in a smaller generalization gop.
Remark 3. One technical contribution of this work is to perform the stability analysis where the marimiza- tion variable is re-initialized after every m iterations where a new mini-batch of data is used. Our theoretical results suggest that as long as m is bounded by ((aset/))) the generalization risk will not change signifi- cantly with a greater m value, which is not implied by the standard bounds in the eristing works [Farnia E Ozdaglar (021) in the literature. Also, our theoretical analysis considers the normalized gradient (instead of the vanilla gradient) for the gradient ascent step of solving the marimization sub-p sub-problem and mini-bato stochastic oplimization for updaling min and mar variables al every ileralion, which are not analyzed in the previous literature (Farnia & Ozdaglar 20210.
We note that Theorem 3 Xing et al. 2021 Xiao et al. 2022b gives a lower bound (2(T/n) on the algorithmic
stability of vanilla adversarial training. On the other hand, comparing equation S with equation suggests that AFree can generalize better than AVenilla for any T = O(n), since
Arron T Ti /n
T
Vanillaa FT
1
Free
=0 (1/1
x
Aaanilla
Avantlla /n Avanillic
T Avanllli +1
Furthermore, when T O(n), equation gives Egen (Apree) O 0011 //ice))) which implics that the generalization gap of AFree be bounded given enough samples. If the number of iterations T is fixed, one can see that the generalization gap of Apree has a faster convergence to 0 than Avanilaa Therefore, neural nets trained by the free AT algorithm could generalize better than the vanilla adversarially-traiee due to their improved algorithmic stability. Our theoretical results also echo the conclusion in [Schmdtt et al. (2018) that adversarially robust generalization requires more data, since AFree increases with respect to e.
networks
Remark 4. We note that the Free-AT method in Algorithm 2 follows the update rule of a projected gradient descent. ascent (Projected GDA) which has been widely studied in the oplimizalion lilerabure. To the best of our knowledge, tight convergence rate for Projected GDA applied to a general optimization problem is still open question in the community [Lón et al. 2020 Li et al.) (022)). As a tight convergence rate for GDA conconeex-noncomen numerical experiments to verify the improvement in the generulization gap by Free-AT method. Note that our numericaa experiments use standard selections of stepsizes and other hoperppaaamteers for the AT algorithms, and their numerical results suggest the slandard hyperparameter selection leads to a lower generalization gup for Free-AT compared to Vanilla-AT.
optimization is not avoilable in the literature, we relied on
We also provide theoretical analysis for the fast adversarial training algorithm Arast in Theorem whose proof is deferred to Appendix A.3
Theorem 5 (Stability generalization bound of Arast). Assume that h(w, 8) satisfies Assumptions i and 2 and is bounded in 10, and the perturbation set is an L2-norm ball of some constant radius e, i.e. A = ||]]| I E}. Suppose that we run A in Algorithm forr T steps with vanishing step size aw, S c/t and constant step size ōag- If the norm of gradient Vgh(w, o;x) is lower bounded by 1/10 for some constant s > 0 with probability 1 during the training process, let constant A := Bc(1 + ã) then
- (1 1+
b
1
( (2oLLI)) b
Apontt
APset
Eyen(A (astt) S 71
T TAFUETT
(9)
AFast
7

---

Published in Transactions on Machine Learning Research (11/2024)
Vanila
30
Fesl
60
Train/Teal error
Generalization
20
10
20
Ventla.train
Vanillattos Fastieett teat
Fasttrain
Free train
100
150
200
100
160
200
Training epochs
Training epochs
Robust train test error and generalization gap against Zz-norm attack.
80
50
Fast
40
Free
TrainFTest error
80
Generalization
30
40
20
20
train
10
Festitrein
Feelitel
Free
25
50
75
100
125
150
175
200
25
50
75
100
125
150
175
200
Training epochs
Training epochs
(b) Robust train/test and generalization gap against Coe -nom attack.
Figure 1: Learning curves of different algorithms for a ResNet18 model adversarially trained against L2 and Doo attacks on CIFAR-10. The free curves are scaled horizontally by a factor of m.
Similar to Remark 2 have the following asymplotic bound on Egen (Apast) with respect to T and
= O T //n
(10)
Therefore, by controlling the step size Os of the maximization step, we can bound the coefficient Apast and thus control the generalization gap Arast, where a lower âs can result in a smaller generalization gap. Comparing equation 10 with equation 5 also suggests that for any T = O(n), Apast can generalize better
AFaal
than Avanillas since
T XPooo
/n
Avanmitt
Fust O (I/TTRR
Avantlla
Avanilla
T Vanilll
/n Vaauilia
6 Numerical Results
In this section, we evaluate the generalization performance of vanilla, fast, and free adversarial training algorithms in series of numerical experiments. We first demonstrate the overfitting issue vanilla adver- sarial training and show that free or fast algorithms can considcrably reduce the gencralization gap. We demonstrate that the smaller generalization gap could translate into greater robustness against score-based transferred black-box attacks. To examine the advantages of free AT, we also study the generalization gap for different numbers of training samples.
We conduct our experiments on datasets CIFAR-10, CIFAR-100 (Krizhesky & Hinton 2009), Tiny-ImageNae (Le Yang 2015), and SVHN (Nezzer et al. 2011 Following the standard setting Madry et al. (2017), we use ResNet18 (He et al. 2016) for CIFAR- 10 and CIFAR-100, ResNet50 for Mony-ImageNet, and VGG19 (Simonyan & Zisserman (0144) for SVHN to validate our results on diverse selection of network architectures. For vanilla adversarial training algorithm, since the inner optimization
Experiment Settings:
8

---

Published in Transactions on Machine Learning Research (11/2024)
Table 1: Robust training accuracy, testing accuracy, and generalization gap of the vanilla, fast, and free algorithms across CIFAR-10 and CIFAR-100 datasets.
Dataset
Attack
Results (%)
Vanilla-7
Vanilla-10
Fast
Free-2
Free-4
Free-6
Free-8
Free- 10
Train Anc.
100.0
100.0
89.7
89.5
86.4
78.9
74.3
71.1
L2
Test: Acc.
65.5
65.6
59.7
62.1
66.0
66.2
65.4
64.2
Gen. Gap
34.5
34.4
30.0
27.4
20.4
12.7
8.9
6.9
CIFAR-10
Train Acc.
94.8
95.1
81.4
37.9
63.7
58.8
55.6
52.7
50
Test Ace.
42.9
43.7
38.9
28.2
46.3
47.2
48.2
46.9
Gen. Gap
51.9
51.4
42.5
17.4
11.6
7.4
5.8
Train Anc.
99.9
99.9
81.5
94.0
82.9
68.
58.2
49.7
L2
Test Acc.
35.7
36.5
30.8
34.8
36.6
38.0
37.8
36.9
Gen. Gap
64.2
63.4
50.7
59.2
46.3
30.1
20.4
12.8
CIFAR-100
Train Acc.
95.6
96.0
70.3
36.9
52.9
43.2
36.7
32.2
20 Test Ace.
20.0
20.3
17.3
15.0
22.4
24.5
24.9
24.5
Gen. Cap
75.6
75.7
53.0
21.9
30.5
18.7
11.8
7.7
lask maxse h(w, d;;) is computationally intractable for neural networks which are generally non-concave, we apply standard projected gradient descent (PGD) attacks (Madry et al. 2017) as a surrogate adversary.
For free and fast algorithms, we adopt AFree and Apast defined in Algorithms and 3 following from Shafahi et al.
20199; Wong et al. (020)).
Robust Overfitting during Training Process: We applied Cg-norm attack of radius E 128/255 and norm attack of radius 8/255 to adversarially train ResNet18 models CIFAR-10. For the vanilla algorithm, used PGD adversary to perturb the image. For the free algorithm, we applied the learning rate of adversarial attack Ogg = & with free step m as 2, 4, 6, 8, and 10 The other implementation details are deferred to Appendix [.1 We trained the models for 200 epochs and after every epoch, we tested the models' robust accuracy against a PGD adversary and evaluated the generalization gap. The numerical results on CTFAR-10 and CIFAR- are presented Table [ and the training curves are plotted Figure Further numerical results on SVHN and Tiny-ImageNet are deferred to Table g in Appendix B.1
Based on the empirical results, observe the significant overfitting in the robust accuracy of the vanilla adversarial training: the generalization gap is above 30% against La attack and 50% against Loo attack. On the other hand, the free AT algorithm has less severe overfitting and reduced the generalization gap to 20%. Although the free AT algorithm applies a weaker adversary, it achieves comparable robustness on test samples to the vanilla AT algorithm against the PGD attacks by lowering the generalization gap. Additional numerical results for different numbers of free AT steps and on other datasots are provided Appendix [B.1]
Robustness Evaluation Against Black-box Attacks: To study the consequences of the generalization behavior of the free AT algorithm, evaluated the robustness of the adversarially-train trained networks against black-box attack schemes where the attacker does not have access to the parameters of the target models (Bhagoji et al. 2018). We applied the square attack (Andriushchenko et al. 2020), a score- based methodology via random search, to examine networks ad adversarially trained by the discussed algorithms as shown in Figure
We also used adversarial examples transferred from other independently trained robust models as shown in Figure More experiments on different datasets are provided in Appendix B.2
We extensively observe the improvements of the free algorithm compared to the vanilla. algorithm against different black-box attacks, which suggests that its robustness is not gained from gradient-masking (Athalyc et al. 2018) but rather altributed to the smaller generalization gap. Furthermore, our numerical findings in Appendix B.3 indicate that the adversarial perturbations designed for DNNs trained by free AT could transfer better to an unseen target noural not than those found for DNNs trained by vanilla and fast AT.
Generalization Gap for Different Numbers of Training Samples: To examine our theoretical re- sults in Theorems and we evaluated the robust generalization loss with respect different mum-
TThroughout this work, use "Vanilla-m" to denote the vanilla AT algorithm with PGD-adversary iterations, and "Vanilla" without specification Vanilla-10 by default. We also use "Free-m" to denote the free AT algorithum with free steps, and "Free" without specification means Free-4 by default. It is worth noting that Vanilla-1 equivalent fast. AT algorithm.
9

---

Published in Transactions on Machine Learning Research (11/2024)
Vanilla
Fast
Free
82.5
80
80.0
Test accuracy
Test accuracy
78
77.5
75.0
76
72.5
74
70.0
64
80
96
112 128 144 160 176 Radius
192
3 4 5
6
7
8
9
Radius
Figure 2: Robust accuracy of ResNet18 models adversarially trained by vanilla, fast, and free algorithms against square attack on CIFAR10. The left figure applies L2 attacks of radius ranging from to 192, and the right figure applies Coo attacks radius ranging from to
Vanilla
Fast
Free
85
80
80
Test accuracy
75
Test accuracy
75
70
70
65
65
60
60
80
96
112
128 144 Radius
160
176
192
6
7
8
9
Radius
Figure Robust accuracy against transferred attacks designed for another independently trained robust model. The left figure applies L2 attacks of radius ranging from 64 to 192, and the right figure applies C.o attacks of radius ranging from to 9.
bers of training samples n. We randomly sampled subset from the CIFAR-10 training dataset of size n E (10000, 20000, 30000, 40000, 50000), and adversarially trained ResNet18 models on the subset for fixed number of iterations. As shown Figure g the generalization gap of free AT notably decreasing faster than vanilla AT with respect n, which consistent with our thcoretical analysis. More experimental results discussed in the Appendix B.4
Generalization analysis of friendly adversarial training (Zhang et al. 2020) with adaptive attack steps: We also perform mumerical experiments to compare vanilla AT with friendly adversarial training (Friendly-ATT [Zhang et al. 2020). which applies an adaptive number of steps and an adaptive training perturbation radius Etrain. As shown in Table 2 by choosing a sufficiently large Etrain its generalization improvement over vanilla AT is similar that of Fast-AT. On the other hand, a smaller étaain results accuracy explored by
PGD AT-like numerical results, showing the trade-off in Fri The theoretical analysis of Friendly-AT will be interesting future direction for work.
10

---

Published in Transactions on Machine Learning Research (11/2024)
Vanilla
Fast
Free
Vanilla
Fast
Free
50
70
Generalization gap
Generalization gap
60
50
40
30
30
20
20
10000
20000
30000
40000
50000
10000
20000
30000
40000
50000
Number of training samples
Number of training samples
(a) Ca-norm-bused Adversarial Training
(b) --e-norm- Adversarial Training
Figure 4: Adversarial generalization gap of ResNet18 models adversarially trained by vanilla, fast, and free algorithm for fixed number of steps subset of CIFAR-10.
Table 2: Robust generalization performance of Friendly-AT Zhang et al. models adversarially trained against L2 and L.o attacks on CIFAR-10
2020 and Vanilla-AT for ResNet18
We set the extent. steps = 3 in
AT, and other implementations follow from Zhang et al. 2020
CIFAR-10, L2 allack
CIFAR-10, Loo allack
Results (%)
Vanilla
Friendly
Friendly
Vanilla
Friendly
Friendly
Etrain = 128/255
Etrain = 256/255
Strain = -8/255
Strain
16/255
Train Acc.
100.0
99.9
100.0
95.1
94.7
88.7
Test Acc.
65.6
65.8
66.9
43.7
44.1
46.3
Gen. Gap
34.4
34.1
33.1
51.4
50.6
42.4
7 Free-TRADES
Our theorelical results suggest that the improved generalization in the free AT algorithm could follow from its simultaneous min-max optimization updates. A natural question is whether we can extend these results to other adversarial training methods. Here we propose the Froc-TRADES algorithm, combination of the free AT algorithm and another well-ostablished adversarial learning algorithm, TRADES (Zhang et al. 2019), and numerically evaluate the proposed Free- Tre-TRADES method.
The main characteristic of TRADES can be summarized substituting the adversarial loss h(w, 8; Loss(f [z= + 8), v) with surrogate loss:
hx(w 6; v) = Loss(fu +
fu 8)).
(11)
The TRADES algorithm aimed to minimize the surrogate risk 1 natural idea gained from our theoretical analysis to apply simultaneous updates the adversarial attack and model weight w, which is stated in Algorithm
n Ey maxsea (w, 6; o; Therefore,
We performed several numerical experiments compare the performance of TRADES and Free-TRADES algorithms. The results demonstrated in Table g show that Free-TRADES could considerably improve the generalization gap while attaining comparable (sometimes better) test performance to TRADES, which indicates that other adversarial training algorithms different from vanilla AT can also benefit. from simultaneous optimization updates. Furthermore, we note that Free-AT and Free- TRADES also have a better generalization performance on the clean data than Vanilla-TT and TRADES. Our theoretical results suggest that the training process of free AT is algorithmically more stable than vanilla AT, therefore the free AT could be similarly expected to generalize better clean data than vanilla AT. The numerical results
11

---

Published in Transactions on Machine Learning Research (11/2024)
Algorithm 4 Free TRADES Adversarial Training Algorithun AFroe
ARAo-TRADES TRADES
Input: Training samples S, perturbation set A, step size of model weight aws learning rate of attack Oks, free step m, mini-batch size b, number of iterations T, TRADES coefficient À for step +
...,, ..., T/m do 3: Uniformly random mini-batch B C.S of size
4: := -==,,,k;=,,,, EB) + Uniform(A9)
5: for iteration i 1, ... m do
6:
Compute weight gradient and attack gradient by backpropagation:
fw 5 b, gg EB Vichi by: Bj), and gô < [Voh> (w, Jz: V un)l (mmm)e)))
Update with mini-batch gradient descent:
w Owefo
Update å with projected gradient ascent: 8 <- [Pa(d] + aasTA (g6, )) ()=
10: end for
11: end for
Table 3: Robust gencralization performance of the TRADES and Treo-TRADES algorithms for ResNot18 models adversarially trained against L2 and foo attacks on CIFAR-10 and CIFAR-100. We set TRADES
coefficient X 1/6, free steps = 4, and other details following from B.1 We rum five independent trials and report the mean and standard deviation.
CIFAR-10, Le allack
CIFAR-10 10,
Loo atlack Free- TRADES
Results (%)
TRADES
Free- TRADES
TRADES
Train Acc.
99.1 00.1:00 0.1
83.4 0.3
85.6 0.3
61.2 0.8 49.8 + 0.5
Test Acc.
66.3 + 0.3
68.2
50.4 0.3
Gen. Gap
32.8 0.4
15.2 +
35.3
11.4 + 0.3
CIFAR-100, L2 attack FReO-TRADES
CIFAR-100,
Lx attack Free-TRADES
Results (%)
TRADES
TRADES
Train Acc.
0.1
0.8
8.75
46.5 0.4
Test Aec.
35.6 + 0.3
40.0 0.2
2..3
25.4 0.3
Gen. Gap
64.0 + 0.2
41.1
57.3
21.1 + 0.4
shown in Table in Appendix B.1 are consistent with this intuition. The theoretical analysis of Areee TRADES will be an interesting future dircction for our work.
8 Conclusion
In this work, we studied the role of min-max optimization algorithms in the gencralization performance of adversarial training methods. We focused on the widely-used free adversarial training method and, leveraging the algorithmic stability framework we compared its generalization behavior with that of vanilla adversarial training. Our generalization bounds suggest that not only can the free AT approach lead to a faster optimization compared to the vanilla AT, but also it leads to a lower generalization gap between the performance on training and test data. We note that our theoretical conclusions are based on the upper bounds following the algorithmic stability-based generalization analysis, and an interesting topic for future study is to prove similar result for the actual generalization gap under simple linear shallow neural net classifiers. Another future direction could be to extend our theoretical analysis of the simultaneous optimization updates to other adversarial training methods such as ALP (Kannan et al. 2018
Acknowledgment
The work of Farzan Farnia partially supported by a grant from the Research Grants Council of the Hong Kong Special Administrative Region, China, Project 14209920, and is partially supported by a CUHK Direct Research Grant with CUHK Project No. 4055164.
12

---

Published in Transactions on Machine Learning Research (11/2024)
References
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterizatton. In International conference on machine learning, pp. 242 252. PMLR, 2019.
Maksym Andriushchenko and Nicolas Flammarion. Understanding and improving fast adversarial training. Advances in Newral Information Processing Systems, 33:16048- 16059, 2020.
Maksym Andriushchenko, Francesco Croce, Nicolas Flammarion, and Matthias Hein. Square atlack: a query- efficient black-box adversarial attack via random search. In European conference on computer vision, pp- 484 501. Springer, 2020.
Sanjeev Arora, Rong Ge, Yingyu Liang, Tengyu Ma, and Yi Zhang. Generalization and equilibrium in generative adversarial nets (gans). In International conference on machine learning, pp. 224 232. PMLR, 2017.
Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples. In International conference on machine learning, pp- 274 283. PMLR, 2018
Idan Attias, Aryeh Kontorovich, and Yishay Mansour. Improved generalization bounds for adversarially robust learning. The Journal of Machine Learning Research, 23())7787777927, 2022.
Pranjal Awasthi, Natalie Frank, and Mehryar Mohri. Adversarial learning guarantees for linear hypotheses and neural networks. In International Conference on Machine Learning, pp. 431-441. PMLR, 2020.
Yu Bai, Tengyu Ma, and Andrej Risteski. Approximability of discriminators implics diversity in gans. arXiv preprinl Xiv: 10586, 2018.
Racf 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-423 4391,, 2020.
Arjun Nitin Bhagoji, Warren He, Bo Li, and Dawn Song. Practical black-box alLacks on deep neural networks using efficient query mechanisms. In Proceedings of the European conference computer vision (ECCV), pp. 154-169, 2018.
Olivier Bousquet and André Elisscoff. Stability and generalization. The Journal of Machine Learning Research, 2:499 526, 2002.
Nicholas Carlini and David Wagner. Towards evaluating the robustness of noural networks. In 2017 ieee symposium on securily and privacy (sp), pp. 39 57. Ieee, 2017.
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In International conference on machine learning, pp. 1675-1685. PMLR, 2019.
Farzan Farnia and Asuman Ozdaglar. Train simultaneously, generalize better: Stability of gradient-based minimax learners. In International Conference on Machine Learning, pp. 3174-3185. PMLR, 2021.
Farzan Farnia, Jesse M Zhang, and David Tse. Generalizable adversarial training via spectral normalization. arXiv preprint ar Xim: 17:m1811 18 07457, 2018
Mahyar Fazlyab, Alexander Robey, Hamed Hassani, Manfred Morari, and George Pappas. Efficient and accurate estimation of lipschitz constants for deep neural networks. Advances in Neural Information Processing Systems, 32, 2019.
lan J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. arXiv preprint arXio:1412.65777 2014.
Moritz Hardt, Benjamin Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. ar Xáu preprint ar arXi::1509.011 01240, 2015.
13

---

Published in Transactions on Machine Learning Research (11/2024)
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on compuler vision and pattern recognilion, pp- 770-775 2016.
Zhichao Huang, Yanbo Fan, Chen Liu, Weizhong Zhang, Yong Zhang, Mathieu Salzmann, Sabine Süsstrunk, and Jue Wang. Fast adversarial training with adaptive step size. IEEE Transactions on Image Processing, 2023.
Harini Kannan, Alexey Kurakin, and Ian Goodfellow. arXiv:1803.0633 2018.
Adversarial logit
pairing.
arXiv preprinl
Hoki Kim, Woojin Lee, and Jaewook Lec. Understanding catastrophic overfitting in single-step adversarial training. In Proceedings of the AAAI Conference Artificial Intelligence, volume 35, pp. 8119-8127, 2021.
Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. Technical Report 0, University of Toronto, Toronto, Ontario, 2009. URL https://www cs. toronto /dt.ottti/dd//kii/// features-- 2009-TR. TR.
Ya Le and Xuan Yang. Tiny imagenel visual recognition challenge. CS 231N, 7(7):, 2015.
Yunwen Lei Stability and generalization of stochastic optimization with nonconvex and nonsmooth problems.
In The Thirty Sinth Annual Conference Learning Theory, pp. 191-227, PMLRR 2023.
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 6186. PMLR, 2021.
Haochuan Li, Farzan Farnia, Subhro Das, and Ali Jadbabaie. On convergence gradient descent ascent: A tight local analysis. In International Conference on Machine Learning, pp. 12717-12740. PMLR, 2022.
Tianyi Lin, Chi Jin, and Michael Jordan. On gradient descent ascent for nonconvex-concave minimax problems. In International Conference on Machine Learning, pp. 6083-6090 PMLR, 2020.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint arXiv: 000806 2017.
Omar Montasser, Steve Hanneke, and Nathan Srebro. Ve classes are adversarially robustly learnable, but only improperly. In Conference on Learning Theory, pp. 2512-2530. PMLR, 2019.
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y Ng. Reading digits in natural images with unsupervised feature learning. 2011.
Asuman Ozdaglar, Sarath Pattathil, Jiawei Zhang, and Kaiqing Zhang. What good metric to study generalization of minimax learners? Advances Neural Information Processing Systems, 35:38190-38203, 2022.
Aditi Raghunathan, Sang Michael Xie, Fanny Yang, John C Duchi, and Percy Liang. Adversarial training can hurt generalization. arXiv preprint arXeo:1906. 06032, 2019.
Loslie Rico, Eric Wong, and Zico Kolter. Overfitting in adversarially robust deep learning. In International Conference on Machine Learning, pp. 8093-8104 PMLR, 2020.
Ludwig Schmidt, Shibani Santurkar, Dimitris Tsipras, Kunal Talwar, and Aleksander Madry. Adversarially 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! Advances in Neural Information Processing Systems, 32, 2019.
14

---

Published in Transactions on Machine Learning Research (11/2024)
Zhouxing Shi, Yihan Wang, Huan Zhang, J Zico Kolter, and Cho-Jui Hsich. Efficiently computing local lipschitz constants of neural networks via bound propagation. Advances in Neural Information Processing Systems, 35:2350 2364, 2022.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint Xro::: 1556, 2014.
Vasu Singla, Sahil Singla, Sohcil Feizi, and David Jacobs. Low curvature activations reduce overfitting in adversarial training. In Proceedings of the IEEE/CVI International Conference on Compuler Vision, pp.
2021.
Christian Szegedy, Wojeiech Zaremba, Tlya Sutskever, Joan Bruna, Dumitru Erhan, Tan Goodfellow and Rob Fergus. Intriguing properties of neural networks. arXiv preprint arXi::1312.611 6199, 2013.
Eric Wong, Leslic Rice, and J Zico Kolter. Fast is better than free: Revisiting adversarial training. arXiv preprinl 0rXi:2001.0039, 2020.
Bingzhe Wu, Shiwan Zhao, Chaochao Chen, Haoyang Xu, Li Wang, Xiaolu Zhang, Guangyu Sun, and Jun Zhou. Generalization in generative adversarial networks: A novel perspective from privacy protection. Advances in Newral Information Processing Systems, 32, 2019.
Jiancong Xiao, Yanbo Fan, Ruoyu Sun, and Zhi-Quan Luo. Adversarial rademacher complexity of deep neural networks. arxic preprint orXi::2211.14966 2022a.
Jiancong Xiao, Yanbo Fan, Ruoyu Sun, Jue Wang, and Zhi-Quan Luo. Stability analysis and generalization bounds of adversarial training. Advances in Neural Information Processing Systems, 1544546-15459, 2022b.
Jiancong Xiao, Jiawei Zhang, Zhi- Chi-Quan Luo, and Asuman E. Ozdaglar. Smoothed-SGDmax: A stability- inspired algorithm to improve adversarial generalization. In NeurIPS ML Safety Workshop, 2022c. URL https://openreview ottppp/rrrrrreeeeeeeffrrrrraaaaa
Jiancong Xiao, Zeyu Qin, Yanbo Fan, Baoyuan Wu, Jue Wang, and Zhi-Quan Luo. Improving adversar- ial training for multiple perturbations through the lens of uniform stability. In The Second Workshop on New Frontiers in Adversarial Machine Learning, 2023a. URL https://openreviex: net. qvALKZ8BUV
Jiancong Xiao, Ruoyu Sun, and Zhi-Quan Luo. Pac-bayesian spectrally-nnrrmalizedd bounds for adversarially robust generalization. Advances in Neural Information Processing Systems, 36:36305-36323, 2023b.
Jiancong Xiao, Qi Long, Weijie Su, al. Bridging the gap: Rademacher complexity in robust and standard generalization. In The Thirty Seventh Annual Conference Learning Theory, pp. 5074-5075. PMLR, 2024a.
Jiancong Xiao, Jiawei Zhang, Zhi-Quar Luo, and Asuman E. Ozdaglar. Uniformly stable algorithms for adversarial training and beyond. In Forty-frss International Conference on Machine Learning, 2024b. URL https://openreviie nett/oorumidd
Cihang Xie, Mingxing Tan, Boqing Gong, Alan Yuille, and Quoc V Le. Smooth adversarial training. arXiv preprint Xiv:2000 14536, 2020.
Yue Xing, Qifan Song, and Guang Cheng. On the algorithmic stability of adversarial training. Advances in neural information processing systems, 34:26523 26535, 2021.
Yue Xing, Qifan Song, and Guang Cheng. Phase transition from clean training to adversarial training. Advances in Neural Information Processing Systems, 35:9330 9343, 2022.
Zhenhuan Yang, Shu Hu, Yunwen Lei, Kush R Vashney, Siwei Lyu, and Yiming Ying. Differentially private sgda for minimax problems. In Uncertainty in Artificial Intelligence, pp. 2192 2202. PMT.R, 2022.
15

---

Published in Transactions on Machine Learning Research (11/2024)
Dong Yin, Ramchandran Kannan, and Peter Bartlett. Rademacher complexity for adversarially robust generalization. In International conference on machine learning, pp. 7085-7094 PMLR, 2019.
Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. arXiv preprint arXiv: 1xXx:1605.07140. 2016.
Bohang Zhang, Du Jiang, Di He, and Liwei Wang. Rethinking lipschitz neural networks and certified robustness: A boolean function perspective. Advances in neural information processing systems, 35: 19398 19413, 2022.
Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric Xing, Laurent El Ghaoui, and Michael Jordan. Theo- retically 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 Kankanhalli. Attacks which do not kill training make adversarial learning stronger. In International conference on machine learning, pp. 11278 11287. PMLR, 2020.
Pengchuan Zhang, Qiang Liu, Dengyong Zhou, Tao Xu, and Xiaodong He. On the discrimination- generalization tradeoff in gans. arxiv preprint arXin: 711 711002771 2017.
A Proof of Stability Generalization Bounds
We first prove the Lipschitzness of maxs5a h(w,;: 6; x) by the following Lemma: Lemma 1. Define hmmo (w; maxs h(w, 8;a). If h(w, 8;a) salisfies Assumption 7 then Imaa is Law- Lipschitz in w for any fized x.
Proof. For any w, w/ and x E X, without loss of generality assume that hmax(w) 2 Amax(w'), then upon defining 8" arg maxsea h(w, 6;x) we have
max (w; x) 1mmx xz)] = h(w, dz;z) max h(w', (6;z)
SEA
< h(w, d";xx) -ow ;z)
$ L ||w - w'll.
thus completes the proof.
Another important observation is that similar to Lemma 3.11 in Hardt et al. 2015 mini-batch gradient descent typically makes several steps before it encounters the one example on which two datasets in stability analysis differ.
Lemma 2. Suppose hmaae 2) max, h(w, 6; is bounded as hmar E [0, 1]. By applying mini-batch gradient descent for two datasets S, that only differ in only one sample 8, denole by wi and wi the output after steps respectively and define d(") :- I|w, w/ll- Then for any x and to.
blo
E B. (Wiz
hmoa h x)
End ( = 0).
Proof. Denote the event E =
(4()) -o)=
-0y- Noting that if the sample is not visited before the fo-th step,
Wa 3i since the updates the same, hence
_ Pr(s E B,) bto
Pr(E)) <
16

---

Published in Transactions on Machine Learning Research (11/2024)
Then, by the law of total probability,
/ll (wr æ) - Nmax (w); =
mmx (uff:)) E
+ M (W4;
hmaax (w/g: x:) E
S Bd 1d
(w)) -]
btu
n
where the last step comes from the Lipschitzness proved Lemma
Equipped with Lemmas and it remains to bound E[d ( (d(")) (d = 0J. The following lemma allows us to do is recursively bounded by the previous E[d["]]
this, given that for every 1, E.d "
Lemma 3. Suppose that for every step t, the expected distance between weight perameters is bounded by the following recursion for some constants v and & (depending on the algorithm A):
Eid (w)
)
" B[a nt
(12)
Then, after T steps, the generalization adversarial risk can bounded by
Egen(A) S b (1 1
(1+ ( :) (t
( Lungy
T
Proof. Conditioned on d(w)) for some to: by the recursion bound equation 12 we have
E Bld (a!
0]
II t1o+1
(1+
V
7
II
exp
(7)
exp
n
11
1=
T
T
I exp
v/ log
to
to
By Lemma 2
further obtain
{
(/T)
bto
(wrx - Amax =x)x(w(())]
5 Lu
+
10
The bound is maximized at
Lo (/= (H 1411
Combining this bound with Theorem 1 finally gives us
E [lllmax (wx:z) 2)) hmax (w(ix)]] I 1 1 1 ((u
Egen (A)
sup S
T
hence the proof is complete.
A.1 Proof of Theorem 2
Lemma 4 (Growth Lemma of A- Consider two datasets S, differ in only one sample s. Then the following recursion holds for any step
E [ < (1 + Ow. (le)))) B) +
a. 2L
2en +
n
17

---

Published in Transactions on Machine Learning Research (11/2024)
Proof. At step t, let B₁, Bi denote the mini-batches respectively. If s & Bt, we have
dc m
W/-1 1
Our.t
V (1 w//11
Own b
Σ
V
(13)
b
EyEB,
$ 11-1 w/-1l1 +
Owst
v= 2, Z,EB,
V vwh(w// x5)z5)]
(14)
+ a
(15)
ByEBi
$ | w/-1l +
Onnt
Σ
- Ow.t Σ
3 11āy- 8'1l
(16)
ZyEB.
EB.
(1 + (d) + 21.
(17)
where the last inequality is because the perturbation set A = {6: || S $) hence ||5 - -,y1 - 2e. If 8 E B
by the Lipschitzness of h we can bound //V,, dai s)ll s L for w, 6, s. Hence
W awa (
w/-1 + awa 1 s d_a + 2a
Similar to equation 17 we can further bound
V vud(((-11,;;zz)) w/+1+ aw
Wt-1
(18)
b
ZyEB,
(1 aw+ Bdd + 20aw
+ (dww) + 20w,)
(19)
b
Since B, is randomly drawn from S, Pr(s E Bi) Combining equations probability we have
17 and 19 by the law of total
2 B[d(-)] S + am (m. E(d + 2e0 + n
a
hence we finish the proof of Lemma
By Lemma 4 upon plugging v = Be and & = 2En + 2L into Lemma we obtain the desired result
Egen (vailla) <
+
1
(
22w
(sBn + +1)
B641 de
T
Bc
b
A.2 Proof of Theorem 4
Lemma 5 (Iteration-wise Growth Lemma of AFree). Consider two datasets S, differ in only sample s. At iteration i of step t, let B,, B₁ denote the mini-batches respectively, let Wt,s, wh,s denote the model porameters and dg,s, 8y denote the perturbations respectively, and let d( == -lwe, wh,ll, d. = EB [1(5g,)) - (8%,),i1. Define the exponsivity matria
1 + aw.
aw.18 + aserr
=
axsu1BB
(20)
Then we have
(w))
(w)
La L
<
+ 1 (sEBe)
(8)
18

---

Published in Transactions on Machine Learning Research (11/2024)
Proof. If s & Be, which implies B, = B'd, have
[(w)
a... 11,i
aw.. Vuh(uur, (dz,));zz5) -w/,
(21)
1,1+1
b
b
E.B
< | w', +
aw..
(o V (8t)))i
(22)
EyEB
+ Orwet
Wunliuee (6 Vuhlwwes (3)))))))))
(23)
B
< |r, - w/,1 +
aw,t
- B11 -
Ow.t B - (6/,)b
Σ ajEBt
(24)
-
b
b
ByEBc
= (1 + a. 3)
(25)
If s B,, the gradient difference with respect to and s' shall be separately bounded. By the Lipschitzness of h, we can bound the expansive property of the minimization step with respect to and 8' by
| - awet (wh(w (ōe,) wh, + aw, W (8..); s di + 2.
Similar to equation we can further derive the bound for mini-batch gradient descent by
(w) 1,441
aw!t Vahlwee (Fe))):z)g) wh, aw. W1i1
Σ
Vuhlwih (o..)iit))
b
By E..
b-1 (1 (1+ amn + Bd
1
(dw))) + 20web)
+
b
b
$ (1 + a. 3dl + Ba + b awiet.
2
We then proceed to bound d recursively. When A = in equation [ we have
||0| < &),, by the definition of projected gradient
llg 5112 Eg
(g)
arg min Polltss))PPllnts())
|9|||
Since we assume that with probability 1 the norm of gradient Voh(w, d; is lower bounded by 1/1b for some constant 1 > O, we can translate TA into the projection onto the convex set A. For any vector g such that ||l|| 2 1/1,
(g)
Eg
<gg
evgg
arg min |levy 8112 (P)g)))). SEA
(26)
1 |all
max [ax
Since is convex, the projection Pa(+) 1-Lipschitz. So for all j such that Iy E we have
11) - (8,++1)111== = |iPa ((6r.); + aasTs ((5 - + assT (96))))
< (1(6r,), + a.TT -
< [1(8r,); + -atp://aann-PPPPPllllhh Pa(evg())l
< [1(b.:),- ((..))ll+
(6.));; Vah(w(, (Z.)):
If xy n'y, by the smoothness we can further bound
11(5,,41); (6%,44)))l < - (ws.a///ohaa//ooooooo////aaaaaaa (0 - Vsh(wi,,
(5))))
(27)
+ ouevi (oMh -ashirr)))sss/(iii. (8,)))::3311
(28)
(1 + a,e0))](6..)) 3
(29)
19

---

Published in Transactions on Machine Learning Research (11/2024)
Otherwise if x, + z'j, bound it by the Lipschitzness
[[() (0% = (1(62,)); (01,),11+ 2ageriL.
(30)
Upon combining equations 29 and 30 we obtain the desired recursion bound for di.)
2 S (1 + aser)B)d + asewidd + [eE b Fs
Finally, combining the above completes the proof.
Lemma 6 (Step-wise Growth Lemma of Apree). Consider two datasets S² differ in only one sample s. Let Bt, B3 denote the batchestches at step t respectively, and let di == ||wa, - "mmml be the distance between weight parameters after step t. Over the randomness of Be, we have
2L n 1
Sc (1+ 1 aSE
[B nB
2L
Eid,
Proof. Noting that by Lemma (w)
we can obtain
2L/b3
(r)
26 a
+ [.EB.)
0
M
1 (g
1
(w)
[2T/bB]]
+1 (sEB))
Since the updates are repeated for m itcrations in one step, by induction we have
[w]
2L/b3
[
2L/63
(8)
+
(sEn,)
0
(.E
0
t.m
Denote a := a..33 and r := agEn //w,, for simplicity. By the definition in equation 20 we can calculate the eigendecomposstion m
1+a a
1
-1
a((+())))))))
+
[
1/t
or
1 1 or
1
Denoting do d(w)
1 (.E
}
2L b3
and dm
= d(w))
(sEB,)
2L we can solve the recursion
b3
dm
do
-1
[1 + a(r + 1)) m
1/1
d
-17
(1 + a(r + 1))m
0
r do
=
0
r do
(1 + a(r 1))m
r do
r+ do
r+(1-a(++1) do
r+]
(((ta(r-1)) do
Noting that by assumption Ownt S c/mm, upon plugging in a: amee, and aser//aw,ts
+ (1 + a(r + 1))
= (1+a a(r + 11)
++
r+
m-1
=1+a
(1 + alrarr- 1))²
1=
< 1 + m(1 a(r m-1
Bc
3 t
(1 am.. + mmer)3)m-1
20

---

Published in Transactions on Machine Learning Research (11/2024)
Since d: dn and d dho0 obtain that
2T. d( + (sEB,)
1 (1 [+
Be t
(1 aw, -sex)3)m-11
( b (d=4 + (eE
21.
b,3
Since Bt is drawn uniformly randomly from S, Pr(s E Ba)= f. By the law of total probability, we complete the proof.
By Lemma since awt S c/mll S e/m, upon plugging Bc(1 + 30/m m (3eb3))))
AFree and & = 2/
33
into Lemma we obtain that after T/m steps,
Aprnn
b 1+ XFree
22 63
T
Egen (Avanilla)
XFree
n
m
A.3 Proof of Theorem 5
To prove Theorem start with the following growth lemma of A
Lemma 7 (Growth Lemmna of AFast). Consider two datasets S. differ in only sample s. Then the following recursion holds for any step t
Eld
) s (1 31 a (w) + -ow.eL.
Proof. We first bound the difference between 6y and 8/. At step t, let Bi Bi denote the mini batnhb respectively. By equation 26 we have TA (g)) = Pa (eVg) if ||al| 2 1/v. Since A is convex, the projection (-(-) is I-Lipschitz. So for all such that 2y E B we have
||o, 811 = || (6; + ( - Pa(o, + (
< (1 + - - (8, ãSTA )
s äs (P( - -PA(EV96))
s ãsew Voh((w,-11 k5: -
If æ, = n²y, by smoothness we obtain 116, - 8811 S a
V m (u - V vwh(w(/11 86:
V ( - vwh(w'' 8,j a hww - (,
B||wr-1 w/-1ll B116, 8/11
8 {
Otherwise if x. + I'y we can only bound this term by the Lipschitzness
/ k5j - 13: s 2T.
Therefore, we can bound d( by the following recursion
d.)) W4-1
Ow
Vul((u--10;;iz.) w/-1+ aw.
b
2y E.B.
< W1-1 wi=1l || + Qwit
Vuh(wi-1110;iz.) - hw
EyEB;
< dmw) + 3(1 a (w) [.EB,)
20w.eL
21

---

Published in Transactions on Machine Learning Research (11/2024)
Since B, is randomly drawn from S, Pr(s E Bi) h. So by the law of total probability we have
E ) S (1 + (11 ass + -h L,
hence we finish the proof of Lemma
0
Armed with Lemmas 3 and
by letting v = Sc(1 + )5EN3)) and Blltage00] we obtain
24
Egen (Arat) S (1+
(2ch. Bc(1 +aseb))) Be(1++ae03))
paltagevant
dell ageve) T 1
b
thus complete the proof.
B Additional Numerical Results
B.1 Robust Overfitting During Training Process
Implementation Details: For the training process of networks, follow the standards in the literature (Madry et al.) 2017: Rice et al. 2020). We apply mini-batch gradient descent with batch size b 128.
Weight decay is set to be 2 x 10 We adopt a piecewise learning rate decay schedule, starting with 0.1 and decaying by factor of 10 at the 100th and 150th epochs, for 200 total epochs. For the vanilla algorithm, we apply PGD adversaries with 1, 7, or 10 iterations and set the step size as E, E/4, or e/4 respectively. For the free algorithum, since it repeats m iterations at each step, we use 200/m epochs to match their training iterations for fair comparison. For the adversaries, we consider both C2-norm attack of radius 128/255, and -orm attack of radius 8/255 (except for Tiny-ImageNet & = 4/255).
We extend the experiments in Section D using different free steps m, various neural network architectures, and other datasets. We use 18 for CIFAR-10 and CIFAR-100, NesNet50 for Tiny-ImageNer and VGG19 for SVHN. We apply both L2 and L.v adversaries and provide the plots of training curves for CIFAR-10 and CIFAR-100 in Figure 5 We can observe that the vanilla training suffers from robust overfitting, while the Tree am with moderate free sleps generalizes better and achieves comparable robustness to the vanilla algorithm.
22

---

Published in Transactions on Machine Learning Research (11/2024)
Table 4: Robust training accuracy, testing accuracy, and generalization gap of the vanilla, fast, and free algorithms across Tiny-ImngeNet and SVHN datascts.
Dataset
Attack
Results (%)
Vanilla-7
Vanilla-10
Fast
Free-2
Free-d
Free-6
Free-8
Free-10
Train Acc.
100.0
100.0
100.0
100.0
100.0
99.3
65.1
46.8
L2
Test Acc.
22.9
23.0
23.5
23.8
24.8
22.7
23.6
23.8
TingeImageNet.
Gen. Gap
77.1
77.0
76.5
76.2
75.2
76.6
41.5
23.0
Train Acc.
100.0
100.0
100.0
99.8
96.2
60.2
39.5
Test Acc.
13.8
13.9
13.5
12.3
14.5
14.4
15.7
16.8
Gen. Gap
86.5
86.9
85.3
81.8
44.5
22.7
Train Acc.
100.0
100.0
96.9
89.2
95.1
90.0
93.5
91.0
L2
Test Acc.
61.4
61.2
60.8
61.6
60.8
62.3
61.6
62.5
Gen. Gap 38.6
38.8
36.1
27.6
34.3
27.7
31.9
28.5
SVHN
Train Acc.
89.1
88.9
55.1
49.6
55.4
63.8
56.7
56.9
Test Acc.
38.7
38.8
39.5
38.3
47.1
46.7
45.0
Gen. Gap
50.1
15.6
12.7
16.7
10.0
11.9
Table 5: Clean and robust training accuracy, testing accuracy, and generalization gap of the vanilla, free, TRADES, and Free-TRADES algorithms on CIFAR-10 dataset.
Attack
Results (%)
Vanilla
Free
TRADES
Free TRADES
Clean Train Acc.
100.0
98.7
99.8
95.8
Clean Test Acc.
88.1
88.6
86.2
86.8
Clean Gen. Gap 11.9
10.1
13.6
9.0
L2
Robust Train Acc.
100.0
86.4
99.2
83.1
Robust Test Acc.
65.6
66.0
66.2
68.0
Robust Gen. Gap 31.4
20.1
33.0
15.1
Clean Train Acc.
99.9
95.1
97.7
91.0
Clean Test Acc. 84.7
85.9
82.4
83.1
Clean Gen. Gap 15.2
9.2
15.3
7.9
Loo
Robust Train Acc.
95.1
63.7
85.5
60.2
Robust Test Ace.
46.3
50.1
Robust Gen. Gap 51.4
17.4
35.4
11.5
23

---

Published in Transactions on Machine Learning Research (11/2024)
Tondila
60
Ceneralization gap
Tieedd
Train/Test offor
20
40
10
20
Fostitonn
Fast
Tramed
land
50
100
150
200
50
100
150
200
Training epochs
Training epochs
(a) Robust train/test and generalization gap against Cz-norm attack CIFAR-10.
80
50
Vanilla
hasl
Fiee-d
Generalization gap
40
Train/Test error
60
30
20
20
10
Fosttroin
Fostiest
100
200
50
100
150
200
Training epochs
Training epochs
(b) Robust train/test and generalization gap against -oom attack CIFAR-10.
Man Ene
80
Pree-1
Froe
Ceneralization
60
40
Train/Test
40
20
Fastibed Tree-1 feet
50
100
150
200
50
100
150
200
Training epochs
Training epochs
(c) Robust train/tee ttst error and generalization gap against C2-norm attack on CIEAR-100.
60
Train/Tast error
Coneralization
60
40
40
20:
20
0
0
50
100
150
200
0
50
100
150
200
Training epochs
Training epochs
(d) Robust train/test and generalization gap against Corm attack 10FAR-100.
Figure 5: Learning curves of different algorithms for ResNet18 model adversarially trained against Lo-norm and Loe-nor attacks on CIFAR-10 and CIFAR-100. The free curves are scaled horizontally by a factor of m for clear comparison.
24

---

Published in Transactions on Machine Learning Research (11/2024)
B.2 Robustness Against Black-box Attack
We perform additional experiments to lest the robust accuracy of models trained by vanilla, fast, and free algorithms against black-box attacks. In Figure 6 we demonstrate their accuracy against Ce and Cso square attacks with 5000 queries of various radius. independently trained robust models.
In Figure 7
we use transferred attacks designed for other
Vanilla
Fast
Free-4
Free-6
82.5
80
80.0
Test accuracy
Test accuracy
78
77.5
75.0
76-
72.5
70.0
96 112
160
176
192
7
Radius
Radius
(a) Accuracy of adversarially trained ResNet18 models against La and Loo square attacks CIFAR-10.
Vanilla -
Fast
Free-4
Free-6
50.0
50
Test accuracy
Test accuracy
47.5
48
45.0
46
42.5
44
40.0
112
160
Radius
Radius
(b) Accuracy of adversarially trained ResNet18 models against L2 and Coo square attacks
CIFAR-100 100.
Vanilla
Fast
Free-4
Free-6
34
accuracy
32
33
Test
28
31
26
80
128 144 Radius
176
192
2
9
Radius
(c) Accuracy of adversarially trained ResNet50 models against La and Loo attacks Imagee...
Figure 6: Robust accuracy of adversarially trained models by vanilla, fast, and free algorithms against square attacks on CIFAR-10, CIFAR-100, and Tiny-mmaceNet. The left figure applics C2 attacks of radius from 64 to 192, and the right figure applies Loo attacks of radius from to
25

---

Published in Transactions on Machine Learning Research (11/2024)
Vanilla
Fast
Frae-4
Free-8
85
80
80
Test accuracy
75
Test accuracy
75
70
70
65
60
64
80
96
112
128 Radius
144
160
176
192
2
3
5
6
7
8
9
Radius
(a)
Accuracy of adversarially trained ResNet18 models against L2 and Loe transferred attacks CIFAR-
10.
Vanilla
Fast
Free-4
Free-6
55
Test accuracy
Test accuracy
50
45
40
40
35
112 128
144 Radius
160
176
192
7
8
Radius
Accuracy of adversarillly trained ResNet18 models against C2 and foc transferred attack CTFAR-
100.
Vanilla
Fast
Free-4
Free-8
36
35
34
Test accuracy
Test accuracy
30
32
25
20
64
80
96
112
128 Radius
144
160
176
192
2
3
Radius
(c) Accuracy of adversarially trained ResNet50 models against L2 and Coo transferred attacks on Tiny- ImageNet.
Figure 7: Robust. accuracy of models adversarially trained by vanilla, fast, and free algorithms against transferred attacks designed for other independently trained robust models on CIFAR-1O, CIFAR-100, and Tmageet. The left figure applies L2 attacks of radius ranging from 64 to 192, and the right figure applies Loo attacks of radius ranging from 1 to 9.
26

---

Published in Transactions on Machine Learning Research (11/2024)
B.3 Transferability
We further investigated the transferability of the adversarial examples designed for the models trained by the mentioned adversarial training algorithms. We computed the adversarial perturbations designed for the robust models and used them to attack other standard ERM-trained models. We test the transfcrability of models trained by vanilla, fast, and free algorithms. In Figure g we transfer the attacks to a standard
ResNet 18 model on CIFAR- and standard ResNet50 model on Tiny-ImageNet. Tn Figure 9 we transfer
the attacks various standard models including ResNet18, ResNet50, and Wide-Res.Net34 Zagoruyko & Komodakis 2016 CIFAR-10.
Our numerical results suggest that the better generalization performance of the free algorithm could result in more transferable adversarial perturbations, which could be more detrimental to the performance of other unseen neural network models.
Vanilla
Fast
Free-4
Free-6
72.5
60
Test accuracy
Test accuracy
70.0
50
67.5
40
65.0
30
62.5
64
80
96
112
128 Radius
144
160
176
192
4
5
6
10
11
12
Radius
(a) Test accuracy of standard ResNet18 target model against transferred attacks from adversarially trained models on CIFAR-I00
Vanilla
Fast
Free-4
Free-6
39
30
38
Test accuracy
Test accuracy
37
25
36
20
35
15
34
64
80
96
112
128 Radius
144
160
176
192
Radius
(b) Test accuracy standard ResNet50 target model against transferred attacks from adversarially trained models on Tiny-Imagele
Figure 8: Test accuracy of standard ResNet18 and ResNet50 target models against transferred attacks from models adversarially trained by vanilla, fast, and free algorithms on CIFAR-100 and Tiny-ImageNet. The left figure applies L2 attacks of radius ranging from 64 to 192, and the right figure applies Coo attacks of radius ranging from to 12.
27

---

Published in Transactions on Machine Learning Research (11/2024)
Vanilla
Fast
Free-4
Free-6
90.0
80
Test accuracy
Test accuracy
87.5
85.0
60
82.5
80.0
64
80
96
112
128 Radius
144 160
176
192
4
5
6
7
10
11
12
Radius
(a) Test accuracy of standard ResNet18 target model against transferred attacks from adversarially trained ResNet18 models.
Vanilla
Fast
Free-4
Free-6
94
80
Test accuracy
Test accuracy
70
90
88
50
86
40
128 Radius
160
176
192
11
12
Radius
(b) Test sccuracy a standard ResNet50 target model against transferred attacks from adversarially trained ResNet18 models.
Vanilla
Fast
Free-4
Free-6
90
94
Test accuracy
Test accuracy
80
70
60
50
64
80
96
112
128 Radius
144
160
176
192
4
5
6
10
11
12
Radius
(c) Test accuracy of standard Wide-ResNett34 target model against transferred attacks from adversar- ially trained ResNet18 models.
Figure 9: Test accuracy of standard ResNet11, ResNet50, and Wide-RessNtt3 target models against trans- ferred attacks from ResNet18 models adversarially trained by vanilla, fast, and free algorithms on CIFAR-10. The left figure applies L2 attacks of radius ranging from 64 to 192, and the right figure applies Cop attacks of radius ranging from 12.
28

---

Published in Transactions on Machine Learning Research (11/2024)
B.4 Generalization Gap for Different Numbers of Training Samples
We perform additional experiments to study the relationship between the number of training samples and the generalization gap. We randomly sampled subset from the CIFAR-10 and CIFAR-100 1-00 training datasets of size n E {10000, 20000, 30000, 40000, 50000), and adversarially trained ResNet18 models on the subset for a fixed number iterations. The results are demonstrated in Figure
Vanilla
Fast
Vanilla
Fast
Free-4
Free-6
Free-4
Free-6
Generalization gap
Generalization gap
40
40
30
20
10000
20000
30000
40000
50000
10000
20000
30000
40000
50000
Number of training samples
Number of training samples
2o-m adversarial training in CIFAR-10.
(b) Co -torm adversarial training CIFAR-10.
Vanilla
Vanilla
Fast
Free-4
Free-6
Free-4
Free-6
80
Generalization gap
70
Generalization gap
60
50
40
30
20
10000
20000
30000
40000
50000
10000
20000
30000
40000
50000
Number training samples
Number training samples
(c) C2-norm adversarial training in CIPAR-100.
(d) Coe-torn adversarial training in CIFAR-100.
Figure 10: Adversarial gencralization gap of ResNet18 models adversarially trained by vanilla, fast, and free algorithms (with free steps m = 4 or m = 6) for fixed number of steps on a subset of CIFAR-10 or C1FAR-100.
29

---

Published in Transactions on Machine Learning Research (11/2024)
B.5 Hyperparameter Choices and Generalization Behavior with Early Stopping
For the fast adversarial Iraining algorithm, applied the learning rale of adversarial attack as 7/255 for Loo attack and ag = 64/255 for L2 attack over 200 training epochs, following from Andriusbchenkoo & Flammarion (2200). We note that our hyperparameter selection is different from the original implementation of fast AT [Wong et al. 2020), which applied the attack step size ag = 10/255 for C attack over 15 training epochs with early stopping. We clarify that we do not use early stopping in our implementation generalization behavior of fast AT over the same 200 number of epochs we choose for PGD and free AT, where the choice of 200 epoch numbers follows from the reference RRiee et al. (2020) studying overfitting in adversarial training. Regarding the choice of attack step size, we observed that setting the fast atlack learning rate as = 10/255 will lead to fast AT's catastrophic overfitting over the course of 200 training epochs. The learning curves of fast AT with learning rate as - 7/255 and aş 10/255 for Loo atlack over 200 training epochs are demonstrated in Figure II The catastrophic overfitting phenomenon fast AT has
test the
been similarly observed and reported the literature (Andriushchenko & Flammarion) 2020) Kim et al.
2021
Huang al. 2023
100
FrsL
FastJm10
90
Train error
Test error
mmw
20
Fastir10
25
50
75
100
125
150
175
200
0
25
50
75
100
125
150
175
200
Training epochs
Training epochs
Figure 11: Learning curves of fast AT with attack learning rate 7/255 and 10/255 for a ResNet18 model adversarially trained against foe attacks on CIFAR-10.
We also note that the stability framework gives generalization bound in terms of the min and max steps, our theoretical analysis is also applicable if early stopping is employed. From the learning curves in Figure 5 we note that throughout the whole training process, the generalization performance free AT is consistently better than vanilla AT, which consistent with our theoretical results. For instance, Table reports the generalization gaps of the models trained by vanilla, fast (with as 10/255), and free AT algorithms if the training process is stopped the 50th epoch.
Table 6: Robust training, testing, and generalization performance of the models trained by vanilla, fast (with as 10/255), and free AT algorithms against S attack on CIFAR-10, where the training process is stopped at the 50th epoch.
Results (%)
Vanilla
Fast
Free
Train Acc.
53.7
41.8
37.0
Test Acc.
47.1
39.6
35.4
Gen. Gap
6.6
2.2
1.6
30

---

Published in Transactions on Machine Learning Research (11/2024)
B.6 Soundness of Lower-bounded Gradient Norm Assumption in Theorem 4
In Theorem we make an assumption that the norm of gradient Vah(w, d; is lower bounded by 1/1 for some constant & > 0 with probability 1 during the training process. We note that the assumption is only roquired for the points within the c-distance from the training data. To address the soundness of this assumption, we have numerically evaluated the gradient norm over the course of free-AT training on CIFAR-10 and CTFAR-100 data, indicating that the minimum gradient norm on training data constantly lower-bounded by (10-5) in those experiments, i.e. v O(10²) is an upper bounded constant.
We trained ResNet18 networks on CIFAR-10 and CIFAR- 100 datasets, applying Le adversary and setting the free step m as 4 and 6, and we recorded the gradient norm Vah(w, ky U5) of every sample throughout the training process. The heatmaps are plotted in Figure 12
109
10a
0,000
Gradient norm
Gradient nom
10"2
0.006
Freque requeecy
10
00.00
Frequency
10
10
0.000
0,002
0,002
10
0.000
10th
0,000
25
50
75
100
125
150
175
200
25
50
75
100
123
150
175
200
Training epochs
Training epochs
(a) CIFAR-10, Free-4
(b) CIFAR-10, Free-6
10P
10p
10-1.
10-1
Gradient norm
Gradient norm
10-2
Freequ Trequeecy
Frequency
0.003
10-0
20-3
0L002
10
10
10
25
50
75
100
125
150
175
200
25
50
75
100
125
150
175
200
Training epochs
Training epochs
(c) CIFAR-100, Frev-4
(d) CIFAR-100, Free-6
Figure 12: The heat map of gradient norm throughout the training process.
31


Reviews:
[{"review_id": "SkgSZkiOSU", "reviewer": "Reviewer_3qGX", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Advantage: The writing of this paper is clear and easy to understand, and the proofs in the appendix are also clear. The proposed method demonstrates its effectiveness.\n\nConcerns: However, there are several concerns regarding the contents of this paper:\n\n(1) The theorems only provide the algorithmic stability of the three adversarial training methods, while the optimization convergence result is missing. From my understanding, the optimization convegence is as important as the algorithmic stability: If we always return 0 as the output, then the stability is perfect, but the optimization convergence is poor. In this situation, the training loss is large, and the testing loss will be large as well even if the gap between testing and training is zero.\n\n(2) There is no enough highlights of the technical contributions of this paper. In particular, although the proofs of this paper is different from the common techniques used in Xing et. al. 2021 and Xiao et. al. 2022b, the steps of considering the attack update together with the parameter update is similar to handling the discriminator and the generator of GAN in\n\nFarnia, Farzan, and Asuman Ozdaglar. \"Train simultaneously, generalize better: Stability of gradient-based minimax learners.\" International Conference on Machine Learning. PMLR, 2021.\n\nThe authors need to highlight the key challenges when deriving the stability.\n\n(3) There is no clear explanation or insights on why free adversarial training brings better algorithmic stability. Is the advantage of free adversarial training caused by technical tricks (because the proof of free is different from vanilla)? Or is it caused by any special property of the training algorithm?\n\n(4) A minor issue: Theorem 5 for fast adversarial training is postponed to the appendix. Please consider move it to the main content and conduct a formal comparison with vanilla and free.\n\n(5) What will happen if we consider convex function as in Xing et. al. 2021 and Xiao et. al. 2022b? What is the advantage of free adversarial training compared to vanilla adversarial training in this case?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the algorithmic stability of free adversarial training and compares it with the stability of vanilla adversarial training and fast adversarial training. It considers the nonconvex-nonconcave scenario, and the results demonstrate the advantage of free adversarial training. In addition, the authors also propose a new algorithm of free-TRADES, which maintains the robust test accuracy while reduces the generalization gap.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please consider addressing my comments in the weaknesses section.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "GuMJBzPI6z", "reviewer": "Reviewer_pSfY", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "__Strengths:__\n\n- Theoretical Novelty. The paper applies an algorithmic stability analysis to Free AT, offering new insights into its generalization properties. The generalization bounds derived for Free AT, compared to Vanilla AT, provide a theoretical foundation for its improved performance.\n\n- Empirical Support. The empirical results validate the theoretical claims. Experiments on CIFAR-10, CIFAR-100, Tiny-ImageNet, and SVHN show that Free AT exhibits a smaller generalization gap and better robustness against adversarial attacks.\n\n- Free-TRADES Extension. The introduction of Free-TRADES extends the applicability of Free AT to a broader class of adversarial training methods, enhancing its relevance and impact on the field.\n\n\n__Weaknesses:__\n\n- Limited Insights for Practice. The theoretical findings, while novel, do not provide strong guidance for developing new training methods or regularization techniques. The paper could benefit from a more detailed discussion of how these results can inspire practical advancements in adversarial training.\n\n- Discussion on Robustness: The relationship between generalization gap and robustness could be elaborated further. For example, it has not been fully explored how Free AT's reduced generalization gap translates to better robustness in real-world adversarial settings. From the results from Figure 1 and Table 1, it seems that the reduced generalization gaps (w.r.t. free AT) are mainly due to the significant decrease in training robust accuracies, which requires further discussion.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents a comparative study on the generalization performance of adversarial training methods, focusing on Free Adversarial Training (Free AT) and Vanilla Adversarial Training (Vanilla AT). The authors utilize an algorithmic stability framework to derive generalization bounds for these methods. Additionally, they introduce the Free-TRADES algorithm, extend the Free AT approach to the TRADES framework, and demonstrate its advantages in terms of generalization error and robustness.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "While the paper is generally well-written and provides solid theoretical results regarding free adversarial training, it would benefit from clarifications on the following:\n\n- Discussion on Robustness-Accuracy Trade-off: Elaborate on how Free AT affects the trade-off between robustness and accuracy, especially in comparison with other adversarial training methods like TRADES and Fast AT.\n\n- Practical Impact: Discuss potential ways the theoretical bounds can guide the development of new adversarial training techniques or regularization methods.", "broader_impact_concerns": "I have no broader impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "sGI2dNd10t", "reviewer": "Reviewer_d8jU", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "#Strengths \\\n1 The authors clearly articulate the research background and motivation for their study.\\\n2 They support their claims with solid evidence, drawing from both theoretical and empirical results. \\\n3 The authors propose a promising direction for reducing the generalization gap in adversarial training (AT) development.\n\n#Weaknesses \\\n1 The paper is not very well-structured, I think they misused their appendix section. \nThe authors claim to have made four contributions, but only three are discussed in the main text. The fourth contribution, the framework Free-TRADES, is detailed in the appendix rather than in the main body of the thesis. I believe the appendix section is for the supplementary material but not for the main contribution. I would suggest reorganizing your paper for better readability. \\\n2 The innovation is limited, since the main contribution mostly focused on investigating and evaluating on existing methods proposed by others rather than focusing on their own solution \\\n3 This paper only focuses on the DNN architecture but not consider the transformer architecture \\\n4 A key citation is missing (see below)", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors highlight that traditional adversarial training, while demonstrating outstanding performance against adversarial examples, often leads to larger generalization gaps. They also observe that Free-AT, a variant of traditional adversarial training, exhibits a smaller generalization gap in comparison. \\\nThe primary contribution of this paper is the analysis and compares the generalization behaviors across different adversarial training solutions through both theoretical tools and empirical results. \nMoreover, the authors propose Free-TRADES, which combines Free-AT with the TRADES adversarial training algorithm, to further improve the generalization behavior of TRADES.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The authors analysis the bound between generalization and optimization of adversarial training w.r..t. single attack step (Fast AT and Free AI) and multi-attack step (Vanilla AT and TRADES)\nHowever, a key analysis \"adaptive step\" (something between single step and multi-attack), i.e., friendly adversarial training [1] is missing. \nFriendly adversarial training used curriculum training strategy, which can greatly enhance optimization, leading to better generalization. \n\n[1] Attacks Which Do Not Kill Training Make Adversarial Learning Stronger, in ICML 2020", "broader_impact_concerns": "I don’t find any ethical implications concerns should be related to this work", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers were satisfied with the rebuttals, and as AE, I believe that this paper is technically solid enough and of interest enough to some members of the ML community to make it appropriate for publication in TMLR. The authors should be sure to provide an up-to-date, camera ready version of the paper with all of the changes fully incorporated.
Decision: Accept (poster)