Stability and Generalization of Adversarial Training for Shallow Neural Networks with Smooth Activation
Authors: Kaibo Zhang
Yunjuan Wang
Raman Arora
Venue: NeurIPS 2024 poster (2024)
Keywords: Stability
adversarial training
neural networks
optimization and generalization guarantees
Moreau envelope
convexity
smoothness
Primary area: safety_in_machine_learning

Abstract: Adversarial training has emerged as a popular approach for training models that are robust to inference-time adversarial attacks. However, our theoretical understanding of why and when it works remains limited. Prior work has offered generalization analysis of adversarial training, but they are either restricted to the Neural Tangent Kernel (NTK) regime or they make restrictive assumptions about data such as (noisy) linear separability or robust realizability. In this work, we study the stability and generalization of adversarial training for two-layer networks **without any data distribution assumptions** and **beyond the NTK regime**. Our findings suggest that for networks with *any given initialization* and *sufficiently large width*, the generalization bound can be effectively controlled via early stopping. We further improve the generalization bound by leveraging smoothing using Moreau’s envelope.

Stability and Generalization of Adversarial Training for Shallow Neural Networks with Smooth Activation
Kaibo Zhang Johns Hopkins University Baltimore, MD 21218 kzhang90@jhu. edu
Yunjuan Wang Johns Hopkins University Baltimore, MD 21218 ywang509@jhu. edu
Raman Arora
Johns Hopkins University Baltimore, MD 21218 arora@cs. ..jracs.jjuu..... thu.edu. edu
Abstract
Adversarial training has emerged as popular approach for training models that are robust inference-time adversarial attacks. However, our theoretical understanding of why and when it works remains limited. Prior work has offered generalization analysis of adversarial training, but they are either restricted the Neural Tangent Kernel (NTK) regime they make restrictive assumptions about data such as (noisy) linear separability or robust realizability. In this work, we study the stability and generalization of adversarial training for two-layer networks without any data distribution assumptions and beyond the NTK regime. Our findings suggest that for networks with any given initialization and sufficiently large width, the generalization bound can effectively controlled via early stopping. We further improve the generalization bound by leveraging smoothing using Moreau's envelope.
Introduction
Despite the remarkable performance of parametraeterriee deep networks in real-world applications, recent studies have revealed that they are highly vulnerable to adversarial attacks. These attacks maliciously crafted imperceptible perturbations designed to deceive trained neural networks during inference [Szegedy et al., 2013, Biggio et al., 2013]. The lack of adversarial robustness has raised significant concerns for deploying neural network-basce models in safety-critical applications. Therefore, it is crucial to design algorithms to learn robust models that can make reliable predictions on test data even in the presence of adversarial perturbations.
One principal approach to robust learning, adversarial training [Madry et al., 2018] (along with its variants [Zhang et al., 2019, Wang al., 2020]), has proven to be effective empirical defense mechanism against adversarial attacks. Naturally, this puts an emphasis on also developing a theoretical understanding of robust learning. To study the generalization performance of robust learning, one traditional approach is via uniform convergence [Khim and Loh, 2018, Yin et al., 2019, Awasthi et al., 2020, Mustafa al., 2022], which provides the worst-case type uniform bounds for a given hypothesis class and are algorithm independent. Another line of work focuses on analyzing the convergence and generalization guarantees of adversarial training, yet they either focus on linear classifiers [Charles et al., 2019, Li et al., 2020, Zou et al., 2021, Chen et al., 2023], or introduce restrictive distribution assumptions such as (noisy) linear separability [Wang et al., 2024b] or robust realizability [Mianjy and Arora, 2024]. Therefore, it remains unclear whether we can derive theoretical results for adversarial training that extend beyond these simplifying assumptions.
In this work, we leverage a different machinery by analyzing adversarial training algorithm through the lens of uniform stability. Stability is classical tool in learning theory that has been extensively studied the literature [Bousquet and Elisseeff, 2002, Hardt et al., 2016]. Uniform argument stability measures the difference in output parameters when an algorithm run on two training sets that
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

differ by only one sample. In the standard (non-robuse) setting, Hardt et al. [2016] show uniform stability bound of O 7 losses using a training dataset of size n. They further provide uniform stability bound of O [ for smooth and non-convex losses with decaying step size 1j = O where g E (0, 1) is a constant. The choice of decaying step size is common in the non-convex setting, as maintaining constant step size leads to an exponentially increasing bound on uniform stability.
n after T iterations of gradient descent with step size yf on convex and smooth
When it comes to the robust setting, the primary challenge lies in the non-smoothness of the robust (adversarial) loss. The robust loss is generally non-smooth even if the standard counterpart is smooth [Xing et al., 2021a, Xiao et al., 2022a]. Previous work by Xing et al. [2021a] studied the convex non-smooth adversarial losses and provide an additional term of (TT/T) compared to the convex and smooth losses. Later Xiao et al. [2022a] studied the general non-smooth adversarial losses by leveraging the approximate co-coercivity of the gradient and provide the bound with an additional term of (nTa) that grows linearly in T. where a is the size of adversarial perturbation in lp threat models. These works, while partially addressing the issue, only focus on general convex non-convex functions. However, neural networks, which are specific instance of non-convex functions and are widely used in practice, require further investigation.
In this work, we study the stability and generalization guarantees of variants of adversarial training algorithms. We focus on solving the binary classification problem using two-layer over perapparmeterized neural networks with smooth activation functions and logistic loss. Our key contributions are as follows:
1. We present a bound of O(VIT+++ TT
VBn7 on the uniform argument stability of the gradient descent-based adversarial training over-paramenne peee-parameterieed network after iterations with step size
n.
1), where 3 represents the precision of generating adversarial examples at each iteration.
2. We provide robust generalization guarantees that depend on the Adversarial Regularized Empirical Risk Minimization (ARERM) Oracle. Our results hold for any given initialization and any data distribution. Specifically, if the learner is provided with a good initialization such that there exist robust networks around this initialization, then a small robust test loss is achieved via early stopping. Furthermore, our results can be extended to stochastic gradient bessentt-based adversarial training.
3. We leverage Moreau's 's envelope to construct a smooth loss that approximates robust empirical loss. We present bounds on the stability and generalization error of gradient descent with Moreau's s smoothing, and demonstrate its superiority compared with gradient descent-based adversarial training algorithm.
1.1 Related Work
Stability Analysis. The notion of stability was initially introduced in Bousquet and Elisseeff [2002] to study the generalization of statistical learning problems. More recently, fine-grained analysis has been presented by Feldman and Vondrak [2019] and Bousquet al. [2020]. For smooth loss functions, Hardt et al. [2016] explored the stability of SGD in both convex and non-convex settings, which was later extended to convex non-smooth loss functions by Bassily et al. [2020] and the bound incorporated an additional term of (1i/T) due to non-smoothness. Lei and Ying [2020) tackled the non-smoothness differently by assuming the gradient of the loss to be Hölder continuous. For non-convex and non-smooth loss, Lei [2023] introduced the stability of sub-gradient, as convergence to local minimizers is observed in this setting.
Robust Generalization Guarantee. The standard method of giving a generalization guarantee is through uniform convergence. These theories typically yield an upper bound of O ( and require a large number of training samples in order to get a small generalization gap. Techniques in this category include analyzing the Rademacher complexity [Yin et al., 2019, Khim and Loh, 2018, Awasthi et al., 2020), VC dimension [Cullina al., 2018, Montasser et al., 2020], covering number [Balda et al., 2019, Mustafa et al., 2022, Li and Telgarsky, 2023], PAC Bayesian analysis [Farnia et al., 2018, Viallard al., 2021, Xiao al., 2023] and margin-based analysis [Farnia et al., 2018).
Generalization Guarantee of Adversarial Training. Providing generalization guarantees for adversarial training of neural networks is challenging due to its non-convex nature. A series of
2

---

works [Charles et al., 2019, Li et al., 2020, Zou et al., 2021, Chen et al., 2023] have focused on simpler problem adversarial training of linear models with a convex loss wherein generating adversarial examples admits a closed-form solution. Several works bypass this challenge by con- sidering a lazy training regime [Gao et al., 2019, Zhang et al., 2020, Li and Telgarsky, 2023] in which the landscape of the neural network can be studied near certain random initialization, and the generalization guarantee is usually obtained via uniform convergence. Unfortunately, Wang et al. [2022] proved that adversarial robustness is at odds with lazy regime. Recently, Mianjy and Arora [2024], Wang et al. [2024b] provide convergence and generalization guarantees for adversarial training of neural networks, yet they make restrictive assumptions the data distribution such as (noisy) linear separability and robust realizability.
Another line of research investigates the generalization of adversarial training through algorithmic stability analysis. Despite the smoothness of the standard loss, the adversarial loss remains non- smooth [Liu et al., 2020, Xing et al., 2021a, Xiao et al., 2022b]. To resolve this issue, Farnia and Ozdaglar [2021] make strong assumption that the loss is concave in input x. Xing et al. [2021a] provide adversarial training of convex and non-smooth losses, yielding an additional term of (VV1TT)) compared to the standard non-robust counterpart. Xiao et al. [2022a] and Wang et al. [2024a] leverage the idea of approximate smoothness and provide bounds that scale linearly with njT' and the perturbation size. Cheng al. [2024] consider generating adversarial examples via single step of gradient descent and demonstrate that such variant of adversarial training algorithm achieves better stability. Farnia et al. [2018] also consider specific attack algorithms these attacks while being more practical and designed with continuity and Lipschitzness property, may differ significantly from the worst-case attack, and do not yield good bound on the robust generalization gap.
2 Problem Setup
Notation.
Throughout the paper, we denote scalars, vectors, and matrices with lowercase italics, lowercase bold, and uppercase bold Roman letters, respectively; e.g., u. u, and U. We use [m]] to denote the set (1,2,..., m) and use both || - || and || 2|2 for fz-norm. Given a matrix U = [ul,.... umm] E Rdxmm we use ||U]| and ||U||, to represent the Frobenius norm and spectral norm, respectively. We use the standard O-notation (O, e and !?).
We consider a binary classification problem with a bounded input space X' inside a Euclidean ball of radius C.. and label space )' = {+1). We assume that data are drawn according to an unknown probability distribution DD on X' x V. The learner has access to n training data drawn i.i.d. from D; i.e., S = {z+ = (x,, (x,,y,) y,)) ~ D We do not make any restrictive distributional assumptions such as realizability [Mianjy and Arora, 2024] or (noisy) linearly separability [Wang et al., 2024b].
We focus on learning two-layer neural networks, parameterized by pair of weight matrices (a, W):
fw (x) fx: W) := Σm= ( (w,,x)).
Here, m is a positive integer representing the number of hidden units, i.c. the width of the networks. R + R is a I-Lipschitz, H H-smooth activation function. Formally, V2, E R. (o((2)) < 1, (z) - 0'(z') < H |z --2 z'1. The smoothness property of activation functions is commonly assumed in algorithmic stability literature and in theory of deep learning and covers wide range of activation functions such as smoothed ReLU and smoothed leaky ReLU [Frei et al., 2022]. The weight matrices at the top and bottom layer are denoted as [a|, [a,.-.., am] E Rm and W W -=/W...... Wmn] E Rdxm respectively. The top layer weights are initialized such that |a,] 1. Vi E [m]. and are kept fixed throughout the training process. Prior works [Du et al., 2018, Arora vm
et al., 2019, Ji and Telgarsky, 2019] often initialize a; to be uniformly sampled from {= vm }, which can be seen as a special instance of ours. We do not make any assumption on the initialization of the bottom layer matrix, i.e., Wo can be either standard Gaussian [Du et al., 2018, Ji and Telgarsky, 2019], or a vanishing initialization [Ba et al., 2019, Xing et al., 2021b], or a pre-trained model.
Adversarial Attacks. We consider a general threat model where the adversary's 's perturbation set is defined as B : X' + 2*x Given an input x, B(x) represents the set of all possible perturbations of x that an adversary can choose from. This broader definition of attack includes both the standard bp threat models with perturbation size of a, i.e., B(x) = (x : ||x x|Ip & a). as well as discrete set of large-norm transformations. Unlike prior works [Mianjy and Arora, 2024, Wang et al., 2024b), we do not make any assumptions on the perturbation size.
3

---

In this work, we focus on logistic loss, {(z) surrogate loss for the 0-1 loss. With slight abuse of notation, for fixed sample (x, y), we define ((7,, W) == (x; W)). The population and empirical loss w.r.t. {(.) are denoted, respectively, as
In(1 + -- which serves smooth and convex
n L(W) (xx.))-f((f(x W)), S) Σ (x (x):
Given B, for fixed sample (x, yx, we define the robust loss as frob w) == max (xf((x: W)).
XEB(x)
The robust population and empirical loss w.r.t E(.) defined as
Lrob(W) () = (x.)) max (x; Tros (W = 71 Σ
max ((;f(x;;W)) x.B
XEB(X)
Adversarial Training. During training, the network bottom layer weight W are updated using gradient descent-based adversarial training (or its stochastic version). We denote the weight matrix at the (-th iterate of adversarial training W,, For each training example (x,, Vi). at iteration 6, we generate a B1 optimal adversarial example (W),,, 91), which satisfies the following condition:
(x, Wc)) 2 max [f: W))) - B1. xEB(K.)
(1)
Setting 31 O recovers the scenario where we have access the worst-case adversarial attack. As this may not be feasible in practice due to computational reason, the parameter 31 allows us capture the precision of the attack algorithm, which includes common attacks such as projected gradient descent (PGD) [Madry et al., 2018]. We should regard 31 as parameter we can choose. Our results in Section suggest that can achieve better generalization by adding more computation and making 31 smaller.
Algorithm 1 Variants of Adversarial Training Algorithms Input: Step size y, Number iterations T. Initial weight Wo. B 2 0. f 0.
for t = ...... T 1 do
GD: Vi [n]. compute 31-optimal adversarial example (W, that satisfies Equation (1).
Update W = W. Σ (W Wt)).
SGD: Compute a 3 opttimll adversarial example &441 (W,) that satisfies Equation (1).
Update Wt+1 W,- 1 V w f(ce1 W:)).
Moreau Envelope: Compute 82-optimal minimizer Ü" (W;: that satisfies Equation (2).
Update W++1 = W. (W: - S))
end for return: (Wo)
T
Optimizing the Moreau Envelope. Since the robust loss non-smooth [Xiao et al., 2022a], we utilize Moreau's envelope to construct smooth function that approximates the empirical robust loss. Such an idea has previously been explored in Xiao et al. [2024]. Given training data S and μ >> 0, we redefine the robust surrogate loss as follows:
M (W: S) = min (U: +
||U - WII
2p
Selecting μ appropriately ensures that Lros(U; (U; + 2u IU WI1? is strongly convex function
w.r.t. U. Given W and S, define UM(W; S) argminuuR4xx Tros (U; z ||U W|l which can be obtained via subgradient- based method (solve min-max optimization). The gradient of the Moreau envelope can be simply calculated as Vw WWM S): = 1(W UU(W;
(W:SS) S)). Given training
data S, at each iteration I, we generate 322-optimal minimizer U (W.; S) that satisfies
~/t
Lras (T S); S) + 1 _ -10"'(W;; (W.;)) w.ll < B2 + M (W(W;;S)
2μ
We remark that 82- optimall minimizer defined in Equation (2) and 31 opttiaa adversarial example defined in Equation (1) are approximating different quantities, which are not comparable. All the algorithms described above are summarized in Algorithm 1.

---

Uniform Argument Stability. Given a training set S = | drawn i..d. from D. let S' denote the training set obtained by replacing one example S with an independently drawn example z' D. We refer to S' as neighboring samples and write S = 5". Given an algorithm A (X' x y)" - H. where the hypothesis class H is parameterized using a parameter matrix W Rdxm, we define the uniform argument stability as
I[A(5) - A(S")
For any L-Lipschitz loss function argument [Mohri et al., 2018] relates the expected generalization gap the uniform argument stability.
< (S, S"). The standard stability
gew (A(S)) = ESSDD (EnDD((A(S) 2) Σ s(A(5),2))) < L sup (A(S,S") (3) 1=1
9=5'
In this paper, we consider robust generalization using logistic loss, so function g rrob (z, W),
and Egen(W) (W) = Ez-D|eret(2 (z, W)] E==1 (Z, W). We also remark that high probability bound for stabile algorithms can be given based on Feldman and Vondrak [2019]. For simplicity, our generalization bounds in this paper are only in expectation.
3
Main Result
In this section, we present our main results, providing theoretical guarantees for adver- sarial training of two-layer neural networks with smooth activation functions. We dis- cuss (stochastic) adversarial training in Section 3.1 and gradient descent-based Moreau's smoothing in Section 3.2. Our generalization bounds rely Adversarial Regularized Empirical Risk Minimization (ARERM) Oracle defined as
key quantity, the 2|[W Woll?
oraale min WeR
(Irrad W)
n/T
Given a sample, Agracle returns the minimal empirical risk in the vicinity of an initialization Wo-
3.1 Generalization Guarantees for Adversarial Training
We begin by presenting a bound on the uniform argument stability (UAS) of Algorithm 1 with GD. Theorem 3.1. Assume that the network width satisfies m 2 H² + 1)2. Then, after T iterations of Algorithm with GD, for any neighboring datasets S, we have
sup (S, S O(C.IVT + C. T/T S
(.rT).
n
Remarkably, setting 81 = 0 yields a bound of O1iV + II on the UAS of Algorithm 1, thereby recovering the result prior work of Xing al. [2021a]. However, note that Xing et al. [2021a] show the result only for convex learning problems, whereas we consider training two-layer neural networks using logistic loss, which is non-convex and non-smooth. Further note that assume that the networks are sufficiently over-parameterized, i.c., m 2 !(r²T²), condition that is commonly assumed in deep learning theory. We can also regard this condition as early stopping, wherein
T << O v/m HC? This view is also consistent with several empirical studies [Caruana al., 2000,
Rice et al., 2020, Pang et al., 2021].
Next, we show that stable robust leamning rules do not overfit.
Theorem 3.2. Define a1 (7. == OC C2 of' + C2 (InTT.... Assume that the width of the networks satisfies m 2 22 + and a (). < 1. Then, after T' iterations of Algorithm I with GD, we have
17a (11 T)
Ca 2
min (o7) SIST
ESwDn gee (W.)
Es Aoracle +
81
(1
and
1
C2
min Es Lyob (W) OStST
Es A oracle oracle
+
+ 3
ai 00111,77 T)
2
5

---

The result above bounds the robust generalization gap and the robust loss in terms of the ARERM oracle, a step size-dependent term O17), and the precision of the adversarial examples 31. Note though that the bound holds for the minimum over the last few iterates (past iterates), rather than for the last iteration. This distinction arises because, unlike standard gradient descent for neural networks, we cannot guarantee a decreasing robust training loss without additional assumptions on the data distributions owing to the non-smooth nature of the robust loss. The step size-dependent term arises for the same reason. A direct corollary gives us bound on the expected robust loss.
Corollary 3.3. After T S Ommin(n², क iterations of Algorithm I with GD using a step size of on a network with width m 2 S2T",, for any weight matrix W
C.
Woll? VT
min ES (W) & 1.1 0S1ST
+0
+ O
VT
Since corollary 3.3 holds for any Wo. it underscores the importance of initialization for robust learning. Given a good initialization, such as a pre-trained model, and assuming that there exists a robust network W, in the vicinity of the initialization (i.e., IlW, Woll = O(1)) that achieves a small robust loss Tenbh (W.) Ri O, we have that the minimum expected robust loss over all iterates approaches O (+) Further, if B1 is small enough and 2 n² then T can be of the order (n?))
leading to (1/nn) upper bound on the robust test loss.
We remark that by a similar analysis, our result can be reduced to the standard (non-robust) setting for gradient descent training of two-layer networks by setting the perturbation set (xx) {x}, Vx E X, In this context, we can show that gradient descent for the binary classification problem can achieve excess risk bound of ((1/vn) by taking 1/T = ((v))
31 = O, and redefining ai (1), T) ( oT x
m Z n and assuming ||W, Woll = (11, where W. E argmin Lro (W).
Next, we extend our result to the stochastic adversarial training.
Theorem 3.4. After T iterations of Algorithm with SGD on a network of width m 2 (T 1)a we have that for any weight matrix W,
min E (e 2.). 2. Toro [oro + |W - Woll TT(T 1)
C2n 2
+ B1.
OSTST
Similar to the discussion following Corollary 3.3, assert that if we assume that there exists an prer-parameterized robust network with small robust loss, then using step size of rj 1/VT, stochastic adversarial training yields an excess risk bound of O(1vT)).
3.2
Generalization Guarantees for Gradient Descent on Moreau's Envelope
We now present a bound on the uniform argument stability of gradient descent with smoothing based on Moreau's 's envelope.
Theorem 3.5. After T iterations of Algorithm with Moreau Envelope with step-size 1) I ymm vm } S 2HCT. on network of width m 2 H²C for any neighboring datasets min sHCE S,5', we have
(c. T + Cr
32 P
sup (A 0O
T
S
n
Setting 32 0 yields bound of O O prior work of [Hardt et al., 2016, Xiao et al., 2024] for convex and smooth functions. Note that by using Moreau's 's envolope, we are able to shave off the O(y/T) term that appears in Theorem 3.1.
the UAS of Algorithm 1, thereby recovering the result in
Although inspired by Xiao et al. [2024], Theorem 3.5 differs from the non-conven setting of Xiao et al. (2024). Our result utilizes the specific structure of over-parameterized neural networks that exhibit weakly convex properties, a special instance of non-convex functions, and allows for constant step size. contrast, [Xiao et al., 2024, Theorem 4.7] follows the traditional stability argument for non-convex and smooth functions in Hardt et al. [2016], considering decaying step size t H.

---

Such condition might be impractical if is chosen to be sufficiently small. In fact, our results indicate that necessary select a sufficienlly small μ so that the robust training loss is well approximated by the Moreau envelope (see Lemma C.I in the Appendix).
Even though the gradient descent-based algorithm with Moreau's smoothing achieves better stability guarantees compared to gradient descent-based adversarial training when 31 .3 = 0, it requires more computational resources. Specifically, for the calculation of the gradient at each step, we need solve a min-max optimization problem with a strongly convex and non-smooth objective to obtain a 3-optimal minimizer. Additionally, for every step of this min-max optimization, we need generate adversarial examples and apply sub-gradient descent.
Theorem 3.6. Define () O + CavIT ) Assume a2 T) < 1. Then, after 2 8 iterations of Algorithm Moreau Envelope with step-size S μ on a network of width 2 H2 we have
ES gen (W,) S 55az(11 T) 1 oz (17, T)
B oracle + +2 +1) 82
min SiST
and
1
+ C2 + 2n(T + 32 ES Ag
min ES Lrob 1 02 (1, T) ISSS
oracle
Similar to Theorem 3.2, the result above shows that both the robust generalization gap well the robust loss can be bounded in terms of the ARERM oracle, parameter μ in Moreau's 's envelope, and a the precision of generating the minimizer of Moreau envelope.
term of On7 82/p) dependent While the bound above is on the minimum expected generalization gap (and expected robust test loss) over the last few iterates (past iterates), we can give bound for the the last iterate for the case when 32 = O. We conclude the section by presenting the following direct corollary.
Corollary 3.7. After < Ommnn(n², 4273 iterations of Algorithm with Moreau Envelope with
step-size 7 μ O (3LT) network of width 2 -2(T), have for any weight matrix W,
C [
Woll?
min ESNDO Le (W.) < (. + +0 ISIST
+ O
VT
VT
4
Proof Sketch
We begin by providing a high level intuition behind our analysis technique, and then we highlight the key ideas in the proofs of the main theorems. For simplicity, we assume that the learner can generate optimal attacks during adversarial training, i.e., we consider 91 = 0, B2 0 in this section. We refer the reader to the Appendix for proofs of the more general case.
Our analysis relies on a key lemma demonstrating that the objective function (i.e., the robust empirical risk) being minimized in adversarial training of two-layer neural networks with smooth activation functions using the logistic loss function is "almost" convex.
Definition 4.1. Let 7 > 0. A function (x: is said to be -l-weakly convex if f(x) + 1 | is convex in x.
Lemma 4.2. (Restatement of Lemma A.4) For any weight matrices W' and w
HC2
Lres (W2; 2 (wo)(W (w w W2)
W W
2/m m
Equivalently, (r:
(W: S)
H122 -weakly convex.
HC² Vm
We borrow many ideas from Xiao et al. [2024] and Xing et al. [2021a] in our proofs. These papers primarily focus on the convex setting, while only giving a general result for non-convex functions. We extend their results to a special case of learning neural networks. We argue that by specializing our analysis neural networks would lead to sharper results than a general non-convex function class, as we will be able to leverage the "almost" convexity of neural network training [Richards
7

---

and Rabbat, 2021, Richards and Kuzborskij, 2021]. This allows us to get stability and optimization guarantees that are similar to the convex setting when we consider an over- per--aaameterieed network m 2 poly(17). An additional challenge we face is that the robust loss is non-smooth even if its standard counterpart (logistic loss) smooth, making the analysis more complicated than the standard (non-robust) scenario. Nevertheless, we can still leverage the "almost" convex nature of the loss to establish the stability of adversarial training.
The following lemma gives a relationship between stability and generalization which is useful in both standard adversarial training as well as gradient descent with Moreau's envelope. When the robust training loss T.ras( Wr;
(W:; 5) is small, Lemma 4.3 provides a tighter bound than directly applying Equation (3). See Proposition A.3 for both results.
Lemma 4.3. (Restatement of Proposition A.3) The robust test loss satisfies the following:
Esw (rr) < ES 1- sup dA SY) Lrob (Wr;S).
1
C2
S=S"
This result gives a way to bound the expected robust loss. Say you want to bound the expected robust test loss by (1 + e) times the expected training loss. Then, to ensure I-ai(,,)) + need
ai (n. T) S Itc O()).(((ee)) a1 (7. 7) = - af + (Bn'T) we can set different parameters in more than one way ensure that 0: (n. T) Occ). We can set 31 O n @(1/c). T = (11/c)) O ( or set 31 =
0(1 ((1/c)) 0
4.1 Generalization Guarantees for Gradient-Based Adversarial Training
The stability guarantee we give in the following Theorem 4.4 is similar to the result in the convex case [Xing al., 2021a]. While [Xing al., 2021a] use the monotone subgradient condition of the convex functions, we show that the subgradients of an "almost" convex loss function are "almost" monotone. We do incur an additional term of exp (2HC3 /m). which small for over-parameterized neural networks (m (noy()T))
Theorem 4.4. (Restatement of Theorem 3.1) Let S and S' be any two neighboring data sets, i.c., they differ only in one example. Let Wr and W/ denote the weight matrices returned after T iterations of Algorithm with GD on S and S', respectively. Then, we have
| w/ P3 S exp (1+ 2 (AC3P(T (T }1))) n²
vm
We next provide intermediate lemma that lead us to Theorem 3.2.
Lemma 4.5. (Restatement of Theorem B.2) Set k = (1+ NC²n Vm
Then after T <
1
HHC29
iterations of Algorithm 1 with GD,
C3
ks (W:; < Ag grraee +
T Σ
Richards and Kuzborskij [2021] (see Lemma 2 in their paper) give an optimization guarantee
by providing an upper bound on the averaged training loss + Σ [(W.; S) of all iterates. In Lemma 4.5 we use a more refined analysis by considering the weighted average of the training loss. Specifically, for any weight matrix W. we follow the standard technique in the convex case and upper bound the following:
|W W I = J|W W + V (W:; + 21/ (Vw Lros S), W WW.)
The second term on the right hand side is bounded by the Lipschitzness of the logistic loss. The inner product in the third term is bounded by frro a. (W.; 2.mm || Well? using Lemma A.4. We finish the proof by telescoping. The weighted telescoping technique removes all of the ||W - W. terms (t > 0) in the upper bound, thereby giving simpler result. The term C/,//2 in the upper bound stems from the non-smoothness of the robust loss, and is unavoidable even if the robust loss is convex. Finally, Theorem 3.2 follows from Theorem 4.4 and Lemmas 4.3 and 4.5.
HO²
8

---

4.2 Generalization Guarantees for
on Moreau's Envelope
Below we give the key lemmas for bounding the generalization error of GD with Moreau's 's envelope. The proof technique here is similar to that for standard ad adversarial training (in the previous section), except that we get utilize the smoothness Moreau's envelope. Specifically, Lemma 4.6 leverages the fact that the gradient is "almost" co-coercive to control the uniform argument stability.
Theorem 4.6. (Restatement of Theorem C.4) Let S = S' be any two neighboring data sets, i.c., S ym
and S' differ only in one example. For any 7) min( sHOT weight matrices obtained by T iterations of gradient descent with Moreau's envelopes on datasets S and S", respectively. Then, we have that
S
2HCT. let Wr and W be the
v/m
8HC2 m
16C (T
|| wi & exp 1+
n2
Lemma 4.7 also leverages smoothness due to Moreau's 's envelope and yields a bound that does not involve the additional term C2n/2 compared with Lemma 4.5.
(1
2HC2. m
Lemma 4.7. (Restatement of Theorem C.6) Set k
After T iterations of
Algorithm with Moreau Envelope with S S
m 2HC
and T -
m HCgn
we have
T k
(W, < g
Σ
1=
Theorem 3,6 is naturally derived via Theorem 4.6, Lemma 4.3 and 4.7.
Conclusion
In this work, we establish the generalization guarantees for variants of adversarial training applied to two-layer networks with smooth activation functions. For over- paraamterred neural networks, we present robust generalization bound that are controlled by the Adversarial Regularized Empirical Risk Minimization (ARERM) oracle, applicable to any given initialization and any data distributions. One future direction to extend our analysis to deep neural networks and beyond neural networks with smooth activation functions.
Acknowledgments and Disclosure of Funding
This research was supported, in part, by the DARPA GARD award HR001 12020004, NSF CAREER award IIS- 114-19,,,,,, funding from the Institute for Assured Autonomy (IAA) at JHU, and the Spring 22 workshop on "Learning and Games" at the Simons Institute for the Theory of Computing.
References
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. In International Conference on Machine Learning, pages 322-332. PMLR, 2019.
Pranjal Awasthi, Natalie Frank, and Mehryar Mohri. Adversarial learning guarantees for linear hypotheses and neural networks. In International Conference on Machine Learning, pages 431- 441. PMLR, 2020.
Jimmy Ba, Murat Erdogdu, Taiji Suzuki, Denny Wu, and Tianzong Zhang. Generalization of two-layer neural networks: An asymptotic viewpoint. In International conference on learning representations, 2019.
Emilio Rafael Balda, Arash Behboodi, Niklas Koep, and Rudolf Mathar. Adversarial risk bounds for neural networks through sparsity based compression. arXiv preprint arXiv: 00698, 2019.

---

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.
Battista Biggio, Igino Corona, Davide Maiorca, Blaine Nelson, Nedim vSrndić, Pavel Laskov, Giorgio Giacinto, and Fabio Roli. Evasion attacks against machine learning at test time. In Machine Learning and Knowledge Discovery Databases: European Conference, ECML PKDD 2013, Prague, Czech Republic, September 23-27, 2013, Proceedings, Part III 13, pages 387-402. Springer, 2013.
Olivier Bousquet and André Elisseeff. Stability and generalization. The Journal of Machine Learning Research, 2:499-522 526, 2002.
Olivier Bousquet, Yegor Klochkov, and Nikita Zhivotovskiy. Sharper bounds for uniformly stable algorithms. In Conference on Learning Theory, pages 610-626. PMLR, 2020.
Rich Caruana, Steve Lawrence, and C. Giles. Overfitting in neural nets: Backpropagation, conjugate gradient, and early stopping, In Advances in Neural Information Processing Systems, volume 13. MIT Press, 2000.
Zachary Charles, Shashank Rajput, Stephen Wright, and Dimitris Papailiopoulos. Convergence and margin of adversarial training separable data. arXiv preprint arXiv:/905, 09209, 2019.
Jinghui Chen, Yuan Cao, and Quanquan Gu. Benign overfitting in adversarially robust linear classification. In Conference on Uncertainty in Artificial Intelligence, 2023.
Xiwei Cheng, Kexin Fu, and Farzan Farnia. Stability and generalization in free adversarial training. arXiv preprint urXiv:2404.08980 2024.
Daniel Cullina, Arjun Nitin Bhagoji. and Prateek Mittal. PAC-learning in the presence of adversaries. Advances in Neural Information Processing Systems, 31, 2018.
Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. arXiv preprint arXiv: 2018.
Farzan Farnia and Asuman Ozdaglar. Train simultaneously, generalize better: Stability of gradient- based minimax learners. International Conference on Machine Learning, pages 3174-3185. PMLR, 2021.
Farzan Farnia, Jesse M Zhang, and David Tse. Generalizable adversarial training via spectral normalization. arXiv preprint arXiv: 2018.
Vitaly Feldman and Jan Vondrak. High probability generalization bounds for uniformly stable algorithms with nearly optimal rate. Conference on Learning Theory, pages 1270-1279. PMLR, 2019.
Spencer Frei, Niladri S Chatterji, and Peter Bartlett. Benign overfitting without linearity: Neural network classifiers trained by gradient descent for noisy linear data. In Conference on Learning Theory, pages 2668-2703. PMLR, 2022.
Ruiqi Gao, Tianle Cai, Haochuan Li, Cho-Jui Hsieh, Liwei Wang, and Jason D Lee. Convergence of adversarial training in overparametrized neural networks. Advances Neural Information Processing Systems, 32, 2019.
Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In International conference on machine learning, pages 1225-1234. PMLR, 2016.
Ziwei Ji and Matus Telgarsky. Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networks. arXiv preprint 199.v2190. 2019.
Justin Khim and Po-Ling Loh. Adversarial risk bounds via function transformation. arXiv preprint arXiv:1810.09519. 2018.
10

---

Yunwen Lei. Stability and generalization of stochastic optimization with nonconvex and nonsmooth problems. In The Thirty Sixth Anmual Conference on Learning Theory. pages 91-227. PMLR, 2023.
Yunwen Lei and Yiming Ying. Fine-grained analysis of stability and generalization for stochastic gradient descent. In International Conference on Machine Learning, pages 5809-5819, PMLR, 2020.
Justin D Li and Matus Telgarsky. On achieving optimal adversarial test emror. In International Conference on Learning Representations, 2023.
Yan Li, Ethan Fang. Huan Xu, and Tuo Zhao. Implicit bias of gradient descent based adversarial training on separable data. In International Conference on Learning Representations, 2020.
Chen Liu, Mathieu Salzmann, Tao Lin, Ryota Tomioka, and Sabine Süsstrunk. On the loss landscape of adversarial training: Identifying challenges and how to overcome them. Advances in Neural Information Processing Systems, 33:21476-21487, 2020.
Aleksander Madry. Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. International Conference on Learning Representations, 2018.
Poorya Mianjy and Raman Arora. Robustness guarantees for adversarially trained neural networks Advances in Neural Information Processing Systems, 36, 2024.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018
Omar Montasser, Steve Hanneke, and Nati Srebro. Reducing adversarially robust learning to non- robust PAC learning. Advances Neural Information Processing Systems, 13:44726-14637, 2020.
Waleed Mustafa, Yunwen Lei, and Marius Kloft. On the generalization analysis of adversarial learning. International Conference on Machine Learning, pages 16174-16196. PMLR, 2022.
Tianyu Pang. Xiao Yang, Yinpeng Dong, Hang Su, and Jun Zhu, Bag of tricks for adversarial training. In International Conference on Learning Representations, 2021.
Leslie Rice, Eric Wong, and Zico Kolter. Overfitting in adversarially robust deep learning. In Proceedings of the 37th International Conference on Machine Learning, pages 8093-8104. PMLR, 2020.
Dominic Richards and Ilja Kuzborskij. Stability & generalisation of gradient descent for shallow neural networks without the neural tangent kernel. Advances in neural information processing systems, 34:8609-8621, 2021.
Dominic Richards and Mike Rabbat. Learning with gradient descent and weakly convex losses. In International Conference on Artificial Intelligence and Statistics, pages 1990-1998. PMLR, 2021.
Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. arXiv preprint arXiv: 1312,699,,, 2013.
Paul Viallard, Eric Guillaume VIDOT, Amaury Habrard, and Emilie Morvant. A PAC-Bayes analysis of adversarial robustness. Advances in Neural Information Processing Systems, 34:14421-14433,, 2021.
Yihan Wang, Shuang Liu, and Xiao-Shan Gao. Data-dependent stability analysis of adversarial training. arXiv preprint arXiv:2401.03 2024a.
Yisen Wang, Difan Zou, Jinfeng Yi, James Bailey, Xingjun Ma, and Quanquan Gu. Improving
adversarial robustness requires revisiting misclassified examples. In International Conference Learning Representations, 2020.
Yunjuan Wang, Enayat Ullah, Poorya Mianjy, and Raman Arora. Adversarial robustness is at odds
with lazy training. Advances in Neural Information Processing Systems, 35:6505-655 16, 2022.
11

---

Yunjuan Wang, Kaibo Zhang, and Raman Arora. Benign overfitting in adversarially trained neural networks. In International Conference on Machine Learning. 2024b.
Jiancong Xiao, Yanbo Fan, Ruoyu Sun, and Zhi-Quan Luo. Adversarial rademacher complexity of deep neural networks. arXiv preprint 1rXiv:2211.1496: 2022a.
Jiancong Xiao, Yanbo Fan, Ruoyu Sun, Jue Wang, and Zhi-Quan Luo. Stability analysis and generalization bounds adversarial training. Advances in Neural Information Processing Systems, 35:15446- 15459, 2022b.
Jiancong Xiao, Ruoyu Sun, and Zhi-Quan Luo. PAC-Bayesian adversarially robust generalization bounds for deep neural networks. In The Second Workshop on New Frontiers in Adversarial Machine Learning, 2023.
Jiancong Xiao, Jiawei Zhang, Zhi-Quan Luo, and Asuman Ozdaglar. Uniformly stable algorithms for adversarial training and beyond. arXiv preprint arXiv:2405.0/887, 2024.
Yue Xing, Qifan Song, and Guang Cheng. On the algorithmic stability of adversarial training. Advances in neural information processing systems, 34:26523-26535 2021a.
Yue Xing, Qifan Song, and Guang Cheng. On the generalization properties of adversarial training. In International Conference on Artificial Intelligence and Statistics, pages 505-513, PMLR, 2021b.
Dong Yin, Ramchandran Kannan, and Peter Bartlett. Rademacher complexity for adversarially robust generalization. In International conference on machine learning, pages 7085-7094. PMLR, 2019.
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, pages 7472-7482. PMLR, 2019.
Yi Zhang, Orestis Plevrakis, Simon S Du, Xingguo Li, Zhao Song, and Sanjeev Arora. Over- parameterized adversarial training: An analysis overcoming the curse of dimensionality. Advances in Neural Information Processing Systems, 33:679-688 2020.
Difan Zou, Spencer Frei, and Quanquan Gu. Provable robustness of adversarial training for learning halfspaces with noise. In International Conference on Machine Learning, pages 13002-1301 PMLR, 2021.
12

---

Supplementary Material
A Technical Theorems and Lemmas
Lemma A.1. Let E(2) = 1n(1 + =)) be the logistic loss function. We have [e'(z) min min {(x))
Proof of Lemma A.I.
1: { In(1+oT9).
(6" {=>0) 0)
[e(=)] = -((=)= = 1 e²
14z S 1m([+
#
Lemma A.2. For any sample z = (x, v). and any weight matrices W and W we have Evoblz, W) lrob( w') C || W2 min(1, (r, W)}.
Proof of Lemma A.2.
lz,s(z, W) - (z,
max ((ys(x; W)) REB(X)
max (yf((X; W'))
REB(X)
< max (X(us(x; W)) (xys W')) REB(X)
< max REB(x)
(xx W)) (MJ(3; W) - -x((;
(E is convex)
max keB(x)
(us((x W))
Σ
a (ow((w x)) - E' (o
==1
< max REB(X)
(yf((: W))
(Wo w2,,))
(ø is I-Lip)
max REB(x)
C'(s( W))
(w. W' x)²
(Cauchy's inequality)
< max REB(x)
(yf W)) ||W - 1 |
<O₂, W W/
max REB(x)
(xf W))l
<C₂ W W/ min 1, max (xf W))} REB(x)
(Lemma A.I)
=Ca W - W/ min (2, W)}.
In the following proposition, we build the relationship between the generalization gap and uniform stability.
Proposition A.3. Let S and S' be any two neighboring data sets that differ only in one example. Let W, = A(S), W A(S") be the weight returned after running algorithm A for steps using S and s" respectively. (S, [|A(S) A(S')le. Then if sup SS) < C
we have
S=
ES (W.) S ESND" 1 Cr sup (A( S
Lras S)
(4)
and
Es-D= Lyob We) S ESnDa Lrob (W;; S) + C₁- sup (A S').
(5)
S
13

---

Proof of Proposition A.3. Let S and S' differ in one example, and z' = S
EswD" (Wi) Lros (Wo: (W: = Bsu [(frou(z', (z), - Cros (z', W;)) (6)
Combining Lemma A.2 and Equation (6) get
ESwDa (Lrob (W,) - (We: s Bss. (r) WC min Croblz' Wol..
Based on the definition ÒAA
ES (Lros (We) - (robb(We;;)
(W:;
I C sup (S, S") -Bsu(e)=Dn++ min(1, lros(z', Wo)
S=8'
S Cr sup (5, S') min(1, ES Lo (W.)). S=s'
Simplifying this inequality, get
BS-DDLrob (W)) Es 1 Cp sup 6A 8y) (Wr:
and
1swDDITrosWW/ S RS Toros (W, C. sup 6A S").
Swaf
The following lemma gives the weakly convex property of the robust loss (by considering the special case of {3 = 0).
Lemma A.4. Given any data (x, y). for model with weight W. let x x(W) E Bxx) be an 3 optimall adversarial examples such that ((yf(X(W)) W)) 2 max E(yf(X, W)) 81. Then for any two weight xEB(x)
matrices W w Rdxm, we have
HC2 2/m
((((())) v), W 2 e((x(W"), ),)), W (W))++(WW(((())))))))))) W w2 W - 31
| W
Proof of Lemma A.4.
e((x(W?), v), w²) - e((x((()))))))))))))))))>>)))()_ ), W (Vwe((((W)) v), W W2 W + ,1 =llyfwa (X(W2))) ([ (VWe(((((")) ), v). W w -W') + +1
max (lyfwa(x) Clyfwi (X(W")) (VVW((X(W")),) v),, W W pP2-w" -W"> keB(x)
(By definition of 31-optimal adversarial examples)
Zllyfwe (X(()(((W)))) 1)) (X(W") ( ). w w -
2l(yfw (x('))) (x(W)( wfw ((("")))(((<((((V))) (Vw<((x(W") ).)), W W w
(E convex)
(() (ol(w x(W+))) (o(ww. -'w, (w w x())()
2 1e' (X(W)))))))))))
(w? - w..
(o is H-smooth)
H
2 1. 2/m
I1(22 - [
(Lemma A.
HC²
I22 w2-w'113 w/
(|X(W> S C.)
2 2 m m
14

---

The following lemma tells us the gradient has universal upper bound.
Lemma A.S. For any data (x, v) and any weight matrix W,
(vv[yf((;W))l) S Cr-
Proof of Lemma A.S. Since Vwl(yf(x;W)) = (()
m
[we(uf(x w))le
(x( W))ya,
C2 f(yf(x: W))
(asl vm
1 00 1., |1112122 S C2)
< Cz.
(Lemma A.1)
B Missing Proofs in Section 3.1
Now we give the uniform argument stability upper bound.
Theorem B.1. (Restatement of Theorem 3.1) Let S and ( only differ in the i-th data. Wr and
w( denote the weight matrices returned after after running Algorithm GD for T iterations S and 8 respectively. Then we have
WT W 11? SE e 2ue22
4C3 + 1)2 + (8
(T +1)
n²
Proof of Theorem B. For any weight matrix W and any perturbation of the j-th data X, E (xx,) Σ (R); W)) to be the loss of the (perturbed) data set (j * i), define Lgv (W; (8phsts) +
without including the i-th data. Let (W,) denote the 31-optimal adversarial example of xj given W,, and xj(W) (W(") denote the 3i-optimal adversarial example of x, given w( We first show that the gradient is an "almost" monotone operator, which is derived from the weakly convex property of the robust loss (see Lemma A.4).
HC
B1
+
W
w/ + LSV (Wes (W.))azs)
2
2/m
m
1
HC²
81 +
IW: - (()
2/m
341
w(
(Wwele, (Vw))=(VVee, w( W. W.-wiy -w("]] (Lemma A.4)
= L (w (
11z1)) + (V (w))))))
(x, W. - w!!) ww-w!")
Similarly, we get
HC2 r
W - w/' + Lsv (x (w("))
B1 +
2
24 We: {x, (W.))ss))) + (WWLSV (w:; (8, w! -we)
Adding these two inequalities together, we get
(V (W!"), (W(( ( VW w/O - -w,)
HC²
2 28
Vm W
(7)
15

---

Now we start upper bounding |/ W 11.
|We+11 w
||W VVV (We; (8,(W))))+)) ? (wellyf((((W:::.)
n2 -w.- + W (W/ (R (
n
< IW, V/V ( (W))))))))) -
N ( (x, b
21yCa
W/ + V/ ( (Lemma A.5)
T W (W
T++
Cn²²2
+T + 2) 2
(1+ + (1 1/p)b² for p > 0.)
n2
W. w
+ T+1
T +
In
(w,( (1) )
T+1
T+2 2
- (W -w)-w.)
22 T +1
+ + +2) Cr2C²
n²
T T+1
W. w/") || + T+1
2
C2 T+
(48m++
2HC²
n, w + (T +2)
4n 4n/222
T+1
vm
n12
(Lemma A.5 and Equation (7))
T+2
2HC
4r7² 2
(1+
n 2 1) W.- w/ + C2 + 4817 + (T 11)
T+1
Vm
Define y= T+1
T+2
(1 + vm
2Hc²
n)).
then the incquality above can be written as
[W+1- w(t) 11 <// w/' +
T
4n 48 (T 1)
4n
x
T+1
n2
Dividing both sides by ,(t1,
W
w(O) W 11
I w0
T + 2 2 + 43 + (T + 1) 1)20 202022
2441
7
T ++1
gt+1
Summing up this inequality for t 0, 0, ..... T 1, we obtain
T + 2 C2 + +43nn + (T + 1) 22
W
w (6)
T
n²
T+1
7
t=
T
T 2
4n 4n + +4817 + (T'1) 472 C2
7- 1 T +1
n2
ST + 1)n" T T +2
4n7C2a
4n7² + 4,1 + (T + 1)
T+1
n²
= = + 1)
T+2
T++
2HC2 1 T) /n// + +337 + (T + 1)
4n
T+1
Vm
n²
2n02nT T
< (T + 1)e.e
Cr1C2 + +43 + (T+1)
(1+x5e" ea)
n²
2NC
4C 1)2
(T+)(
481n(T +1)
m
n
16

---

2BC2 vm
The proof of Theorem 3.1 is immediately obtained from Theorem B.1 by observing e+
Next we give an optimization guarantee. We show that when T is sufficiently large, the robust training loss approach the adversarial regularized empirical risk minimization oracle. We do not need early stopping in the Theorem below.
Theorem B.2. After running Algorithm GD for T iterations, we have
min Loos (W min 0S1ST
Lro (W: 2/m(1
HC²
W
Ca W
+B1
WER
2
(1+
MC v/m
Proof of Theorem B.2. For any given W, we have
IW
Wetill 1
| W. + V L (W.))
=I -|W w.ll3 + 17
Vw L(W;; (Rx(()))))))) W.) + 2n/ (Vw (WW. (X..) W W.)
<|W- W HC
<
| W (W: (w, (& (W)E=)
mm
(Lemma A.5 and Lemma A.4)
+(1+
HCM
J/w )
-.Wl. 02 2nIr (W:S) 2n (&.,)))))))))
Vm
Dividing both sides by (1 + HC3n 1++
we get
mm
W W
W We
C²
2m Crob
(W:5) (
L(W,; (
HC g+z (1+
(1 +
HC
(1
HC 1041 vm
(1
HCZu [++
Vm
vm
vm
(8)
Taking the sum for t 0, 1, ..... we get
Trat (W; S)
C
2n
I
Woll 2
(1 + HCz0 je+1 Vm
HC )
\mn
L(W:: (W:))))
2n
(9)
(1 HCPaya+t
vm
Dros (We; B1
22
(1
HC yt+1 vm
1=0
2n min Dras (Wri S) 0SEST
Σ
2n
31
(1 +
HC
4+11
1= (1 +
t=0
vm
vm
Simplifying the above inequality, we have
110
C²n
min USt5T
S Lrob (w: +
Wo
+ B1.
2
2/m(1
(1+
HC
Theorem 3.2. Define a1 (1. OC:: C2 + Cz CITBITT) Assume that the width of the
networks satisfies m 2 H2C, (T with GD, we have
2 1)2 and 01 (n. T) < 1. Then, after T iterations of Algorithm
17a T)
Ch 2
min (97) SIST
ES Een (W,)
Es A Aoracle +
81
an (1,
and
1
C2
min OStST
ES Lyob (W) < 1- a (11, T)
EswD A oracle oracle
+
2 + 3
17

---

Proof of Theorem 3.2.
Define to ==
197
and k ==
From equation (9), we have
T
Loob S)
T
n F
21)
W
Wo
HC gr+1
y++
0=
t=
vm
L(W:; {I (W:))
2-1
(1+ HC yet1
1=
Loob (Wri S) 31
221
(1 +
HC3n ja+1 vm
1=to
Taking minimum over all weight matrices W,
T
Σ
k++1
(Wr:))
- -
toto
T
W Woll?
T
min
Σ
Σ
b:41
20
2
|W Woll
C²n
ket1 min (W:
T
t=
21 Σ h+11
1=0
(Iroo(W::))
I - Woll?
C²11
k+
min
(m 2 HC 1)3)
(T
2
t=0
C21 2
kt+1.
Agracl
Taking the expectation on both sides, we get
T
T
Σ
M
min teSeST
ES LLa (W::
Σ
Broo - B3)
t=to
t=
T
C2.1
Egaaangrache
<
+ 2
Simplifying the equation above, get
b41
Ch.1 + 2
min ES-D= Trooh (W::roo(:::::) (W: 511++
ES-D= A oracle
(10)
Σ
kl+1
t=fo
I
C211
3 +
(ESiDn A oracle
k
2
S +
Σ eto
(Eswon A oradle
+
C2n
2
(m 2 (T -)3)
Ca 2
$ 31 + 17
ASwDnAgradh
+
18

---

Equation (4) gives us for any t 1 T, En (W,) -
(n.3)) [n, Bs Lros (W,;; (W Therefore,
01 (7),))
min teSTS
Dgen (W,)
min fostST
Dn Drod (W::S)
1 01 (1,, T)
01 (7,
C2
B1 + 17 ESSDD Agral
01 (n, T)
2
The proof of the second statement takes similar approach. Following the same procedure, replace to by 0 in equation (10), and get
C 31.
min ES-D= Lross (W.; S ES Agracle + 2 USIST
Combining with equation (4),
min ES (W)) 1 ai (n, T)) 0StST
min ostsT
Es Drob
C
EswDD As
oracle
+ $
(n(
2
Corollary 3.3. After T S (minn(n², 3) iterations of Algorithm I with GD using step size of 7 O CTVT on a network with width m S2(T), for any weight matrix W
min ES-DD Lros s 1.1 (W) + C Wolfs VT
+0
OSEST
VT
Proof of Corollary 3.3. Under the conditions of the corollary, we have m 2 17 + 1)3, and 01 (n. T) = OC + C off + C2vB177 can be small enough so that I-ailn.7j S 1.1. Then
it is clear that this corollary is special case of Theorem 3.2.
We now extend the previous ideas to stochastic adversarial training.
Lemma B.3, After iterations of Algorithm with SGD, for any weight matrix W,
HC?
I - Woll + C.1
min (Crob(Ze+1, W.) - (rob1 W)) < OSEST
+ B1.
2/m(1
2
(1+ yT4
BC vmm
Proof of Lemma B.3.
The proof proceeds similarly Theorem B.2.
|W-
We+ill
-|I W, W (WW Woll
=||W Well W (W.). Woll + 2n (W.(( W.). W W,)
W W.ll + C2 + HC?.1 || - + 2nproo (2411, w) 21)(((R(+1 (W,), Bo+1), W,)
vm
(Lemma A.5 and Lemma A.4)
HC <(1 || w.1 + 12 c2 + 2n W) 20frob W.) 21/31-
Dividing both sides by (1 + HC?n ,+1
we get
mm
WW- W
W well
C2 + 2nPro W) 2nfros(Z441 W.) + 2nB1
HC
HC
HC2n 1+1
Vm
Vm
vm
19

---

Taking the sum of the above equation for =
T
17 C2 + 2m/11
W Woll.
+
1=0 (1 + H jet1
vm
lrob(Ze+1, W.) (eob W)
2 221
(11)
(1+ HC )++1
vm
min 0S1ST
(Crob(Ze11, We) (rab(tt11 W))
2m
(1 +
H 1
t=
vm
Simplifying the above inequality we have
HC²
Chy
min (crob(Ze+1, W.) - (rob(Ze41, w)) 5 OSEST
IW
Woll
2 + 3r.
2/m(1
(14
HC
y
Theorem 3.4. After T iteeatiion of Algorithm with SGD on a network of width m 2 HT 1)² we have that for any weight matrix W,
min E (( Lot (W.) S (W) + | WollE OSEST
C.n
+ B
TTT + 1)
2
Proof Theorem 3.4. Taking the expectation over S D on both sides of Equation (11), obtain
T
1 C2 + 2m/3
|| Woll? +
(1
#C yc+1 Vm
1=
T
2e Byg iDD eoerrod (7++1, Wo) E (2 W)
2n
(1 + HCCn )141
t=0
Vm
T
( M 1WD (W,) LW)
21
(1 HC? ye+1 /m
T min E ( Lrbb(We) Crob(W)
0S1ST
22
(1 +
HC )0t1
Simplifying the above inequality, we get
HC²
C.n
min E Loor (W) & Lrob (W) + 2/m(1
| woll +
+ B
0StST
2
(1+ mm
< Lw) + I Woll
Chn
+ 31.
m[T' +
2
(m 2 HTC 1)3)
C Missing Proofs in Section 3.2
From Lemma A.4, for any μ the Moreau envelope is defined as
HCT Loos + 1 ||| W|E is strongly convex in U. Recall that
M MW(W)S) = min
mijn
(U:)+
|IU - WI
2p
20

---

The minimizer of the optimization problem above is denoted as
[Lroo( (U;S)
_ I -U--Wi
U (W: = argmin
U
2p
We borrow a few properties of the Moreau envelope from Xiao et al. [2024]. Lemma C.1. For any
HC?
1. min (M:W; S) has the same global solution set as min Lr (W: S).
W
2. The gradient ("( 5) is Vw.M"WW:S)- = ( UW;;W);;)))
3. M"(W;5) [WIP
convex.
w BCT vom HCT
4. S) is
- Lipschitz in W w.r. the Frobenius norm.
5. M";W;S) is max
smooth.
6. T. (W:
C2
MW:W: & (W;
2
HC?
7. MW; S Cz.
Proof of Lemma C.I. The first statements are covered in the proof of [Xiao et al., 2024, Lemma A.I]. For the statement 6,
L Srot(WSS. (W:S)
1 + 2μ
IW- -
min (Iroe (U; |IU ||lb?
24
= ():
= -rroo(W:5) + min
(T:n) - -Troo (W: + |U - W||
1
2/
2 (o:b((::) + min
(WWwIroo (W; U-W)
HC²
|U- + -U-
2
241
("almost" convex robust loss from Lemma A.4)
HC²
|U - W + 1
> LW: + min U
-
I -IIU-W WIE
2/m
2μ
(Lemma A.5)
C2
= Lrob(W::
HC²
vm
Now we prove statement 7. For any 7 E (0, 1), from the definition of the Moreau envelope,
(U:: 2μ (U((WS)) w/]
UU" S); ()
[[11 - 7) +W -
2μ
(U"(W; obtains the minimum)
72
(U C1 (00111-11l) 7) (1(1-))ll
|| | | S) WI
2μ
(The robust loss is C.-Lip from Lemma A.2)
21

---

Simplifying the inequality above, we get
2₂C²2 ([U)(W:)) -WIlF - 1+7
Let 7 + we get
\w; (1) -WWls S Cz.
Next we show result similar [Xiao et al., 2024, Lemma A.2]. They use the first-order optimal condition to prove the result, which only holds for the smooth loss functions. Here we give a different proof that doesn't I depend on the subgradient, so it can be applied to the robust loss.
Lemma C.2. Let Ú" (W; S) be any 82-optimal minimizer of min (Uro) + 1 -U- -
U_
For two data sets and s+i) that differ in only one example and any weight matrix W, we have
2C,
[IU(WW:)) U U (W:
S
HC?
n A
and
2,32
(W; -W S
JC2
vm
Proof of Lemma C.2. From strong convexity of the regularized robust loss, we have
Lro (W; + 2p
| (W; w/
(W: w/ + ( HC²
ZT (W:: + 24
(WU S)):
24 2/m
and similarly,
(W;) + |U"(W;:) -W1
241
HC²
(U (U" (W; (()) + 2/
(U((W W + (,)
(UU((W:)) U
2/1 2 2/m
Adding these two inequalities,
HC² (U"(W:S) U (W; 13 Vm
(UO (U" (W; S(D): -
Cros (2i, UW; (( (2,, U (W; )(0))
72 1krob(2 U?:::)) - U (W;W:)))
Lr
1
fron (z;, (U(W: Cros (Z+ U (W: (W: 53)
(ros(z), U"(W; - Crob (24, U (W; 5()))
2C
(Lemma A.2)
Therefore.
2C
() - <
(12)
HC²
n
mm
22

---

From the strong convexity of the regularized robust loss, we also have
B2 2
(T; +
1
1 (W; wil
2/11
- (Urr)(U +
1 2p
(U:((W:) - 11:
HC²
2 ( 24
)|i² (W; 5)
U (W: S)
2/m
We get IJÜ"(W; (W;S) U (W; 5
02
2ym
Now show an upper bound that is key bounding the stability of the weight matrix.
Lemma C.3. For any S S
ym and any weight matrices W and W2.
2HC3
< | W 2
|W - - WW. w + (WV
4
Proof of Lemma C.3. Define (W) = () M"(W":
-mooth.. From the standard descent lemma of smooth functions, for From Lemma C.1, (W) is p any 17 S Pb
1 (w2 1/V ww/h S (w2)
2/2 V /wih /wbh( )W
7
[W?)
"
Vw.MM (W")
2
Since 1 (W) +
|
is convex from Lemma C.I.
2
vm HC
1/ ww - 77 ww22
/ w/V (W?) - 1/
2W + (W"), w² - V - W
2
HC?
m
11
-WI(W") w22 VW (W²) 12
2 HC? 11
(W1(W)) I - V/ (w?; S) - W + NWMM
Combining the two inequalities above,
M (M((W::) MM (w': :S) (VwM" :S), w2-w") -W? - (W))
Vw. S) W WW
/m
HCT
Similarly, we can get the counterpart of this equation:
MH(W MM - ( <V.MM(W22 S), w - W22)
(V..:: || WW' 2
-22 VW W (W?
HC?
23

---

Adding these two inequalities, we get
(VwM"(W?; :S - 55) w2 W )
-
W. w 17 V (W2:
21 -
y/m
HC?
Thus.
W "/VW'M" W - VW 5012
W -W211 + wwllI//w'''''.. - Vw.M
-217 (S
5)
W - W
<
W w 17 Vw."
Vw.M/((2,
VV 3 Www.::WwWW::. :) Vw: 5)
4n | WW w + n M (w2
V
HC
S/W //W- 1 4HC VW ;5) w + MWW
Vm
We get the desired result by simplifying the above inequality.
Theorem C.4. (Restatement of Theorem 3.5) For any 1 S min(H, SHO?
let Wr and
2
w be the weight matrices returned after running Algorithm I with Moreau Envelope using S and sO) respectively for T' iterations. Here S and ( only differ in the i-th data. We have
SHC2 u2 vm
B2 4ACzm + +Amy
W
w 1 S e 1+
(T+ + 1)2
n
1
Proof of Theorem C.4.
|| 6+1 (1(1) 11
= =I[W; -1 (: Ú (W;; - w!O + + (w (
1
2
|W - 11 (w, - U"( -W" w/ + 1イ- (w! - U' +
(0)
2n
2,32
HC²
vmm
(Lemma C.2)
1 (W, U S)) w( + 1 1 (w! :
2C²1
W: 1) "
1
HC² Vm
pm
2m
232
(Lemma C.2)
11
HC?
Wm
2
|| (We- - UN(W::))) - w!" +
1 (w - (n(W"" + 4
4Czn
+ +Am
32
n
11
2
++2 2
(4Cz0) + +4n
32
W SW - w + + (W()) (1) 5)) + (T +
T+1
P
((a 6)2 - (1 (1+ (1+p)aa + (1 1/p)b² for p > 0.)
2
T+2
W; ((0) + (T +2
4Czz + 4n
32
(Lemma C.3)
T+1
1
4
1
m
24

---

Define 7
T42 T+1
then the inequality above can be written as
4RO2n
1- Vm
AAx2 n
B2 p
W w
(T (T+ +
+ /
Dividing both sides by - and summing up the inequality, we get
7
4Cam 32
|Wr w
(T +)
+ 1
7-1
n
1
1AC=11
B2
ST + +1([T +2)
+ 1in 14
72
2
T T
AC + An
82
(T + 1)2
T+1
4HC. vm
1
4HC
v/m
aWG2
4Can + 417
32
<
vm
(T 1)2
( S et
n
8HC2 oT
4Ca1I + 171
B2
S
1+
(T 1)²
m (n S SHC?
n
BHC2 TT V'n
The proof of Theorem 3.5 is obvious from Theorem C.4 by observing have the following corollary by combining Theorem C.4, Lemma C.1-6 and Proposition A.3.
e
Corollary C.5. Assume the width of the networks satisfies m 2 2, After T iterations of Algorithm with Moreau Envelope with S. min(p, SHC?
I
/m 2HC2
we have
MP
Czu
Es-D= (WT) S ES-D"
e150., + +1)
1C²n + Anl
82
and
4020
B2
ESwDa Tross S (Bs-p: + C C,(T+1)
4nl
Now we derive an optimization guarantee of optimizing the Moreau envelope.
Theorem C.6. Assume the width of the networks satisfies 2 HT After running Algo- rithm 1 with Moreau Envelope for T iterations with S S 2HC2
mm
we have
(Er
2 nT
83 32) W Wol + (T + 1)
min (W: & min ISST
W
11
Proof of Theorem C.6. From Lemma C.I, M MH( is J smooth, so
M²(We1;S)
<M*(W; (W41 We, Vw) 1
| -.
(13)
24
25

---

From the weakly convex property Lemma C.1-3,
M" M"(W;)) SW
2 5) + (V, W We) HC²
vm |W; - W
HC²
=M"(W,; 8) + SW -- + (We+1 W., Vw.:
W. WIl
V V
1
HC²
("(W(+1:5)+ + (W,)) -- WW
W -w.1
||, W
2p
vm
(equation (13))
(") + =W2+1 - W., We+1 101 W)
1
[ w.ll
HC² vm
W
W|l
21
(p 2 m)
(U - (W, |W++1 W/FF
(Lemma C.1-2.)
1
1
HC² w.ll?
(((W++1:5) (We+1 Wo W W)
W 1+1
IW wl?
2n
/m
-2// B2 |W++1 WilF-
(Lemma C.2)
From the incquality above, for any weight matrix W.
|We+11
=||W;- W | - We + 2 (We+1 W. W W)
2HC2 7
82 | - WIlF)
<|[W;
WII + 2m:"(W;S)) 2n +
IW, - W + 4m
Vm
Simplifying the above inequality and combining with Lemma
C.1-6 gives us
W w
1
2HO
wI + + IWW
32 82
p W
vm
1
2nIrrs
2HO31
1
W/E + 447 + 1) 82
1
W - WIL + T+1
|
Vm
2n (W; -
Thus,
1 -
2
[We+1- - W <
1
1
||W, -
Vm
(1 + -
(Trroo (W:S) MP (W): + 2n(T + =1)
+ 20
(14)
11
Dividing both sides by (1 + 11 (1
++1 2HO9, vm
and summing up the inequality for
0, 0,1,..,,T 1, we get
B2
W woll
min M"(W;; < Lrob (W:S) 21y(T + +1 1515T
+
1
2n (1+
Σ
(1+4)* 1+ 2803,
2
B2
<
IW - woll 2n + +1)
T/T
/
where in the last inequality we use (1 + +) (1+
2HC3n
S (1+ #) (1 2) S 11+3 T
vm
26

---

Theorem 3.6. Define a2(n. == - + / Assume a2 T) < 1. Then, after
T 8 iterations of Algorithm Moreau Envelope with step-size S l network of width m 2 TT we have
min ESwDD - 55az(11,1 T) silTT
BswDn_grac + + + + (n + +1) 82
1 (2
and
1
ESWDD As oradl + C2 + 2n(T + 1) 32
Lro (W)) & 1- 02 (1,, 7) 1StST
min
Proof of Theorem 3.6. Define = 10
and k
Dividing both sides of
(1+ 28C
equation (14) by (1 + +)
(1
2M
4+1
and summing up, we have
(W: + 2T(T + 1) 82
2n
1 T
Σ kt
+ ||W Woll
14
T
22n
(1+
1+
Σ
kf (";,;;
t=to
Taking minimum over all weight matrices W,
2n
1 1 T
kt (W:))(W::S)-C C2P)
<nn
1 T
ke (W;
(Lemma C.1-6.)
t=to
S min
21 1 1
Σ ke
T
(Trob( 2n + +1) 82 + 1|| wo
W
<2n
1+
-
Σ
T
min W
(Loos(W:))
2 n/T
|| Wolli + +nn(T + 1) 32
1=1
T
B2 1
-2n
1+
Σ
Agracle + (T + +1
T
t=1
Taking the expectation on both sides, we get
min fostST
ES-DE (w;:s) 02
Σ k' Drok 0al1
t=to
T
32 kt ESSD A gracle + 2T + 1) $1
Simplifying the equation above, we get
kt
min ES-D- Iro SW C.u +
ESS.D- pracle 2T + 1) 1)²2
(15)
Σ kt
t
9
r10
)
EESDa A Agracle + 2T + 1) B2
S C.
Σ
To
27

---

3r S
Σ eto
9
(ESwDn Agrucla Agruclo + +2n(T + +1) 82
(m 2 112
C. + 55 AS Agracle +2n((T 1) 82
Equation (4) gives us for any t 1 T, ES (W,) S I-22(1,7) Bs Drob SW Therefore,
aa(n..)
a2
ES W1) SSST
min
min ToSIST
ES Turot (W;:
a2
02 (n,
Ch + 55 Agaanagrach (T 1){²) p
82 )))
The proof of the second statement takes similar approach. Following the same procedure, we can replace to by equation (15), and get
32
ES Tro Wr; S Eg An Agracle C. + 21((T +1) OS1ST
min
Combining with equation (4),
min ES-D- Loo (W:) 0SEST
min Da (W(:5) OStST
(2 T)
32 [ESD Agrade C2 + 2n + 1)
$ 1 T2
11
Corollary 3.7. After T < Ominn }) iterations of Algorithm with Moreau Envelope with
step-size 77 = μ ( CTVT on network of width m 2 I(T)), have for any weight matrix W,
C - Woll VT
ESNDE (W,) < ( O ISEST
min
+0
VT
Proof of Corollary 3.7. Under the conditions of the corollary, we have 2 2² and
a2(n. T) O C Le) can be small enough so that I-a2(m.]) S 1.1. Then it is
clear that this corollary is a special case of Theorem 3.6.
28

---

NeurIPS Paper Checklist
A. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
We further expand on the claims made in Abstract and Introduction in Section 3.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
B. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
The paper discussed the limitations in the Conclusion section.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
C. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]

---

The paper provide the full set of assumptions and a complete and correct proof for each theoretical result. Please see Appendix. Guidelines:
Justification:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
D. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
E. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
30

---

Answer: [NA]
Justification:
The paper does not include experiments requiring code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
/ //nips wttpccccppppccccceeec.ccccccccct guides/ /CodeSubmic
hutoli/c/giddes/odeeuuiiiiii cerbbbisssiooi aeionPolicyy for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
F. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
G. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
31

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
show in tables or
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
H. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: h/t/ueuuipp..ee cctppcce/t//thiicccsuiiiideeeed
Answer: [Yes]
Justification:
The research conducted in the paper conform with the NeurIPS Code Ethics
in every respect. The theoretical nature of the results means there minimal ethical concerns.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., . if there is special consid- eration due to laws or regulations in their jurisdiction).
J. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: The societal impacts of the paper is overall positive.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
32

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
K. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
L. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/dataseta has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
33

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
M. New Assets
Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Question:
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
N. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
O. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
34


Reviews:
[{"review_id": "CuufCoGSy8", "reviewer": "Reviewer_fRZq", "summary": "This paper uses uniform stability to analyze adversarial training on wide shallow networks when the adversarial perturbations are $\\beta_1$-optimal. Assuming there exists a robust network near initialization, in expectation the best network iterate has test loss that scales with $1/\\sqrt{T}$. The results for GD are extended to SGD and when using Moreau's envelope.", "questions": "- How realistic is the assumption that there exists a robust network in the vicinity of the initialization?\n- Should I be thinking of $beta_1$ as a constant? If so, how should Corollary 3.3 be interpreted?", "limitations": "Yes.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The bounds are tied to how strong the adversarial training attack is, providing an approximation to practical attacks while allowing for tractability in the theoretical analysis.\n- No assumptions are made on the data distribution, and the adversarial attack threat model is very general.", "weaknesses": "- The bounds are in expectation and not high probability bounds.\n- A large width is required for the bounds to hold.\n- The $\\beta_1$ parameter is set in the worst-case, and as a result for practical attack algorithms is likely to be high. In fact, if $\\beta_1 > 0$ is constant, then it appears Corollary 3.3 is vacuous.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "### W1: The bounds are in expectation and not high probability bounds.  \n\nWe can give high probability bounds based on [r1], which relates high probability generalization bounds with algorithmic stability, but they are looser than the bounds in expectation. We had those originally in the paper but chose to remove them as they are not very informative.\n  \n   \n   \n### W2: A large width is required for the bounds to hold.\n\nTraining neural networks (i.e., implementing the ERM rule) is known to be computationally hard, even for a two layer network with only three hidden nodes. This has been known since the 90s. Recent results in deep learning theory focus on the setting where networks are greatly overparameterized. Indeed, all results giving computational guarantees for learning deep neural networks assume that the networks are overparameterized. So, it is not surprising that we need a similar condition in the adversarially robust setting. The assumption on width, $m\\geq \\eta^2 T^2$, has also appeared in related prior works [r2] and [r3].\n\nAlso, note that the way we present the results, we can also rewrite the condition above as $\\eta T \\leq O(\\sqrt{m})$ and interpret it as early stopping . \n\n### W3: The $\\beta_1$ parameter is set in the worst-case, and as a result for practical attack algorithms is likely to be high. In fact, if $\\beta_1>0$ is constant, then it appears Corollary 3.3 is vacuous.\n\n[TLDR] $\\beta_1$ is not a constant, it is a parameter you can choose. You can make it arbitrarily small by adding more computation. Large $\\beta_1$ means that the quality of simulated adversarial attacks is poor, so indeed our bounds suggest that the robust generalization will not be good. This is what should be expected, it is not a weakness of our result. \n\nRecall that adversarial training involves finding an adversarial perturbation of every training example in the training set. Can we solve this optimization problem exactly? If so, then $\\beta_1$ is equal to zero. Most works in theory of robust learning assume that. We argue that in practice that is not true. So, we allow for approximate optimization for finding an adversarial example during training. We introduce a parameter $\\beta_1$ that is bound on the suboptimality of an adversarial example. Note that this is a design parameter that a practitioner can choose. If you choose a large $\\beta_1$, the training is easier but the resulting model is not good. So, of course, one should choose a small $\\beta_1$. This involves a computational cost that most previous papers ignore. The only paper that carefully shows how many iterations are needed to find a $\\beta_1$ suboptimal attack is that of Mianjy and Arora (2023) – they show that we need $1/\\beta_1^2$ iterations of PGD attack to find a $\\beta_1$ suboptimal attack. \n\n[Mianjy and Arora, 2023] “Robustness Guarantees for Adversarially Trained Neural Networks,” NeurIPS 2023. \n\n### Q1: How realistic is the assumption that there exists a robust network in the vicinity of the initialization?\n\n[TLDR] Existence of a network that generalizes well in the vicinity of a certain way of initialization is a high dimensional phenomenon that is central to the NTK setting, a dominant framework for computational learning theory of deep neural networks.  Nonetheless, our results also yield guarantees that do not depend on the distance from initialization.  \n\nMost computational learning results for deep neural networks assume overparametrization and a certain initialization that ensures that the weights of the trained network do not change by much from initialization. Yet, these trained networks in the so-called lazy regime or the NTK setting, are guaranteed to generalize. So, assuming the existence of a network that generalizes well in the vicinity of initialization (chosen at the right scale) is a high dimensional phenomenon. We argue that if the conditions of our theorems are met (i.e., we consider over-parametrized settings), then such an assumption is not unrealistic. It is same as saying “how realistic is it that a unit ball has almost no volume and all of its mass is concentrated near the boundary.” Well it happens in high dimensions. \n\nWhile we give a bound on robust generalization in terms of distance from initialization, it does not mean that it is a necessary and the only condition for robust generalization. In fact, we can also give a robust generalization bound that does not depend on the distance from initialization. This follows using Theorem 3.1 and Lemma 4.2. \n\n### Q2: Should I be thinking of $\\beta_1$ as a constant? If so, how should Corollary 3.3 be interpreted?\n\nNo, $\\beta_1$ should not be treated as constant, it is a design parameter you can choose. Please see a detailed discussion above. \n\n[r1] Feldman, Vitaly, and Jan Vondrak. \"High probability generalization bounds for uniformly stable algorithms with nearly optimal rate.\" Conference on Learning Theory. PMLR, 2019.\n\n[r2] Richards, Dominic, and Ilja Kuzborskij. \"Stability & generalisation of gradient descent for shallow neural networks without the neural tangent kernel.\" Advances in neural information processing systems 34 (2021): 8609-8621.\n\n[r3] Lei, Yunwen, Rong Jin, and Yiming Ying. \"Stability and generalization analysis of gradient methods for shallow neural networks.\" Advances in Neural Information Processing Systems 35 (2022): 38557-38570.", "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": "nCLPJANI88", "reviewer": "Reviewer_GasY", "summary": "This work studies the stability of adversarial training in two-layer neural networks in binary classification problems. The authors study gradient-descent-based adversarial training, with nearly-optimal adversarial perturbations, in two-layer neural networks with a frozen second layer, and they obtain guarantees on the stability of the algorithm and its robust generalization. Furthermore, the paper considers a smoothened empirical robust loss and obtains guarantees for this case too. The proofs of the main results are deferred to the Appendix, yet a proof sketch is presented in Section 4 for the case of (exactly) optimal adversarial perturbations during training.", "questions": "I have a few questions/suggestions:\n\n* Lines 9 and 10 in the abstract: If I understand correctly, there should be something added along the lines of “provided there exists a robust network around the initialization.”\n* Lines 193-194, “This view is also consistent with several empirical studies.”: can you please elaborate on this?\n* Theorem 3.2, for the result on the generalization gap you should explicitly state the loss function, right? (since eq. (3) is defined with respect to a generic function $f$).", "limitations": "The limitations of the work are thoroughly discussed.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "The paper is well written and makes it easy to follow its contributions and contextualize them with respect to prior work. Furthermore, the results are cleanly organized and presented. The main result is a stability bound on GD-adversarial training, which overcomes the non-convexity and non-smoothness of the objective. I particularly enjoyed reading the proof sketch section and, in particular, Lemma 4.1, which makes it clear how the analysis can sidestep the aforementioned challenges. I consider this work to be a valuable contribution to the field of theoretical robust (deep) learning.", "weaknesses": "The theoretical results hold for a special class of networks (two-layer with smooth activations and frozen 2nd layer weights) and do not appear to be particularly surprising or useful for inspiring practical ideas. This is the reason why I do not recommend a higher score. Perhaps the authors could discuss some of their assumptions in Section 5; for instance, they could comment on the assumption of eq. (1). Should we consider $\\beta_1$ to be constant during training? Do we expect it to be smaller or larger as training progresses? Could it be empirically estimated? Similarly, the authors could comment on the feasibility of adversarial training with the smoothened loss.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "### W1: Detached from practice? \n\nOur is a theoretical result and theory always lags practice and rarely matches the practice perfectly. Having said that, we would like to remind the reviewer that it is known since the early 90s that training neural networks is computationally hard, even for two layer networks with three hidden neurons. Modern theory of deep learning avoids those hardness results by considering (a) overparameterized two layer-networks, (b) a certain small-scale randomized initialization, and (c) freezing the top layer and training only the bottom layer. Under this setting, we can bound the training error of GD after T iterations by $1/\\sqrt{T}$. This is the state-of-the-art results in computational theory of deep learning. It is indeed too specialized and not close to practice, but this is all we have currently. \n\n### W2: Feasibility of adversarial training with the smoothed loss. \n\nYes, it is very feasible and practical and has shown to be successful in prior work. [Xiao 2024] discuss at length the feasibility of adversarial training with smoothed loss and present extensive empirical results. \n\n[Xiao 2024] \"Uniformly Stable Algorithms for Adversarial Training and Beyond.\" arXiv preprint arXiv:2405.01817 (2024).\n\n### W3: How to think about $\\beta_1$? \n\nWe should not think of $\\beta_1$ as a constant. It is a parameter that you as an algorithm designer can choose. You can make it arbitrarily small by adding more computation. Large $\\beta_1$ means that the quality of simulated adversarial attacks is poor, so indeed our bounds suggest that the robust generalization will not be good. This is what should be expected, it is not a weakness of our result. \nWe further expand on our comment above. Recall that adversarial training involves finding an adversarial perturbation of every training example in the training set. Can we solve this optimization problem exactly? If so, then $\\beta_1$ is equal to zero. Most works in theory of robust learning assume that. We argue that in practice that is not true. So, we allow for approximate optimization for finding an adversarial example during training. We introduce a parameter $\\beta_1$ that is bound on the suboptimality of an adversarial example. Note that this is a design parameter that a practitioner can choose. If you choose a large beta, the training is easier but the resulting model is not good. So, of course, one should choose a small beta. This involves a computational cost that most previous papers ignore. The only paper that carefully shows how many iterations are needed to find a $\\beta_1$ suboptimal attack is that of Mianjy and Arora (2023) – they show that we need $1/\\beta_1^2$ iterations of PGD attack to find a $\\beta_1$ suboptimal attack. \n\n[Mianjy and Arora 2023] “Robustness Guarantees for Adversarially Trained Neural Networks,” NeurIPS 2023.\n\n### Q1: Lines 9 and 10 in the abstract: If I understand correctly, there should be something added along the lines of “provided there exists a robust network around the initialization.”\n\nWhile we give a bound on robust generalization in terms of distance from initialization, it does not mean that it is a necessary and the only condition for robust generalization. In fact, we can also give a robust generalization bound that does not depend on the distance from initialization. This follows using Theorem 3.1 and Lemma 4.2. \n\n### Q2: Lines 193-194, “This view is also consistent with several empirical studies.”: can you please elaborate on this?\n\nEarly stopping is a standard approach for algorithmic regularization. It has been shown to prevent overfitting in many settings, see for example [r1, r2, r3]. Here, we show that it is able to mitigate robust overfitting as well. \n\n[r1] ​​Caruana, Rich, Steve Lawrence, and C. Giles. \"Overfitting in neural nets: Backpropagation, conjugate gradient, and early stopping.\" Advances in neural information processing systems 13 (2000).\n\n[r2] Rice, Leslie, Eric Wong, and Zico Kolter. \"Overfitting in adversarially robust deep learning.\" International conference on machine learning. PMLR, 2020.\n\n[r3] Pang, Tianyu, et al. \"Bag of tricks for adversarial training.\" arXiv preprint arXiv:2010.00467 (2020).\n\n### Q3: Theorem 3.2, for the result on the generalization gap you should explicitly state the loss function, right? (since eq. (3) is defined with respect to a generic function $f$).\n\nYes. We will state the loss function explicitly.", "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": "KrlQDtNIHN", "reviewer": "Reviewer_381R", "summary": "Adversarial Training is a popular method to train models that enhance robutness to adversarial examples. In recent years, a lot of papers study the generalization of adversarial training in various models. In this paper, the authors study the generalization of adversarial training for a special shallow neural networks with uniform stability, they show the theoretical reults for three different algorithms.", "questions": "Is this possible to generalize the results from special neural network to regular neural network with mild assumptions like the Theorem 4.7 in [1]?", "limitations": "This work study a speical neural network, and it is unclear whether the results can be generalized to regular neural netowrks.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The authors show theoretical results for a special shallow neural networks with logistic loss, which is non-convex and non-smooth.\n2. The authors discuss stability and generalization guarantees of three variants of adversarial training.\n3. The proof of this work is clear to read.", "weaknesses": "1. The model studied in this work is a special neural network. By fixing the weights of last layer, it has only one layer of trainable parameters, it is unclear if the results shown in this special neural network can be generalized to regular neural netowrk.\n2. The authors claim that they use a over-parameterized neural network, while they explian \"over-parameterized\" as $m \\geq O(\\eta T)$. It is confused that $m$ depends on $\\eta$ and $T$ but not depends on the number and dimention of inputs. \n3. In section 4, the bound shown in theoretical results depend on $m$ with a same order. I check the proof of this work, and find that these bounds depend on $m$ since the weights of last layer is initilized from $\\\\{ \\frac{1}{\\sqrt{m}}, -\\frac{1}{\\sqrt{m}} \\\\}$, which means that the bounds depends on the initilization of weights of last layer. If the last layer is initilized from other parameters, especially, initilized from $\\\\{ \\sqrt{m}, -\\sqrt{m} \\\\}$, does the reult still hold for over-parameterized neural network?\n4. The main techniques used in proofs depend on the weakly convex property of function, and uniform stability of algorithm. It is suggested to show the formal definition of weakly convex function.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "### W1: The model studied in this work is a special neural network. By fixing the weights of last layer, it has only one layer of trainable parameters, it is unclear if the results shown in this special neural network can be generalized to regular neural netowrk.\n\nIt is known since the early 90s that training neural networks is computationally hard, even for two layer networks with three hidden neurons. Modern theory of deep learning avoids those hardness results by considering (a) overparameterized two layer-networks, (b) a certain small-scale randomized initialization, and (c) freezing the top layer and training only the bottom layer. Under this setting, we can bound the training error of GD after T iterations by $1/\\sqrt{T}$. This is the state-of-the-art results in computational theory of deep learning. Yes, it may be too specialized and not close to practice, but this is all we have currently. So, even in the standard setting, it remains unclear if these results can be generalized to “regular” networks. \n\n\n### W2: The authors claim that they use a over-parameterized neural network, while they explian \"over-parameterized\" as $m\\geq O(\\eta T)$. It is confused that $m$ depends on $\\eta$ and $T$ but not depends on the number and dimention of inputs.\n\nWe state $m$ in terms of $T$ and the learning rate \\eta as our generalization bounds are based on algorithmic stability which depends on those algorithmic parameters. Similar assumptions have also appeared in related prior works [r1] and [r2]. \nIf we were using tools from uniform convergence, then m would naturally depend on the sample size and input dimension $d$. Note that we could still write the condition $m \\geq O(\\eta^2 T^2)$ as $m \\geq \\Theta(n^2)$ and $\\eta T = O(n)$, but that would seem superfluous as there could be other regimes that could still give us the condition we need. \n\n[r1] Richards, Dominic, and Ilja Kuzborskij. \"Stability & generalisation of gradient descent for shallow neural networks without the neural tangent kernel.\" Advances in neural information processing systems 34 (2021): 8609-8621.\n\n[r2] Lei, Yunwen, Rong Jin, and Yiming Ying. \"Stability and generalization analysis of gradient methods for shallow neural networks.\" Advances in Neural Information Processing Systems 35 (2022): 38557-38570.\n\n### W3: In section 4, the bound shown in theoretical results depend on $m$ with a same order. I check the proof of this work, and find that these bounds depend on $m$ since the weights of last layer is initilized from $\\\\{\\frac{1}{\\sqrt{m}},-\\frac{1}{\\sqrt{m}}\\\\}$, which means that the bounds depends on the initilization of weights of last layer. If the last layer is initilized from other parameters, especially, initilized from $\\\\{{\\sqrt{m}},-{\\sqrt{m}}\\\\}$, does the reult still hold for over-parameterized neural network?\n\nNo. The scale of the initialization is important. As we state above, this is the case with the dominant framework for a computational theory of deep learning even in the standard setting. Such initialization has also appeared in prior works, e.g., [r3, r4, r5]. In particular, we need the initialization to be at that scale for our Lemma 4.1 to hold. \n\n[r3] Du, Simon S., et al. \"Gradient descent provably optimizes over-parameterized neural networks.\" arXiv preprint arXiv:1810.02054 (2018).\n\n[r4] Arora, Sanjeev, et al. \"Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks.\" International Conference on Machine Learning. PMLR, 2019.\n\n[r5] Ji, Ziwei, and Matus Telgarsky. \"Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow relu networks.\" arXiv preprint arXiv:1909.12292 (2019).\n\n\n### W4: The main techniques used in proofs depend on the weakly convex property of function, and uniform stability of algorithm. It is suggested to show the formal definition of weakly convex function.\n\nWe will include a formal definition of weakly convex functions.\n\n### Q1: Is this possible to generalize the results from special neural network to regular neural network with mild assumptions like the Theorem 4.7 in [1]?\n\nWe are not sure what is reference [1], but see our response above regarding the state-of-affairs with computational learning theoretic results for training neural networks.", "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": "s4oxfn43bS", "reviewer": "Reviewer_RLPb", "summary": "The paper studies generalization bounds for two-layer networks trained using several variants of adversarial training. The main results are a bound on the stability of the algorithm, which in turn provides a bound on the generalization and the robust accuracy.", "questions": "1) Given $\\epsilon > 0$, how should we set the parameters of the problem (i.e. $T, \\beta_1, \\eta, ||W-W_0||, m$ etc.) to get generalization error and robust accuracy smaller than $\\epsilon$? \n\n2) What happens when m is chosen independently of T - although we allow it to depend on n, i.e. the overparameterized regime compared to the number of samples.", "limitations": "The authors discuss the limitations of their results.", "rating": 7, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "- As far as I know, the results presented in this paper are novel. The approach of studying the generalization capabilities of adversarial training through the lens of stability seems like a promising direction with interesting results.\n\n- The paper studies 2-layer networks (where the weights of the second layer are fixed) which go beyond current research in this field, and potentially beyond the NTK/kernel regime.\n\n- The results of the Moreau Envelope are also novel in this context AFAIK, and provide tighter bounds than GD or SGD analysis (although they are computationally less efficient)", "weaknesses": "Although the results of this paper are interesting, there are some issues with the proofs and with some of the setting of the problem, specifically the amount of over-parameterization. In more detail:\n\n1) The assumption on m I think is a bit misleading. If I understand correctly, the authors assume that $m \\geq T^2 \\eta^2$ which means that the change of the weights when doing GD is very small compared to the number of neurons. This in turn means that slightly changing the loss (by a single sample), and beginning from the same starting point will lead to almost the same weights, hence the stability result. However, I don’t think this assumption makes sense in more practical settings. It basically means that the number of iterations is so small (or the learning rate is so small) that most weights barely move from their initialization. \nThis is also emphasized in Theorem B.1, where the change depends on $\\exp(T\\eta /\\sqrt(m))$. This means that even if m is slightly smaller than $T^2\\eta^2$, (e.g. $m = (T\\eta)^{1.5}$) then the difference changes exponentially, and the algorithm is very non-stable. This issue is not addressed in the paper and is only briefly mentioned in the proof intuition.\n\n2) The bounds in Theorem 3.2 don’t make sense. If $\\alpha_1(\\eta,T) > 1$ then the r.h.s of the bounds is negative. Do the bounds only work when $\\alpha_1(\\eta,T) < 1$? If so, this means that $T<1/\\eta\\cdot\\beta_1$ so the number of iterations might be very small compared to the learning rate. \nThis also seems relevant to Theorem 3.6 with $\\alpha_2$\n\n3) There is an issue with the value of T in Corollary 3.3. Which value of T gives that $1/(1/\\alpha_1) < 1.1$? Suppose $\\beta_1$ is a constant, then we need $T<1/\\eta$ to get a constant term rather than $T< 1/\\eta^2$, no?\n\n4) Line 509 - I don’t understand this, how is Eq (4) related to \\epsilon_gen?\n\nI will be happy to see the author’s response to these issues and will consider raising my score accordingly.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "### W1: Regarding $m\\geq  \\eta^2 T^2$\n\nReviewer has a correct understanding of why stability holds, i.e., the change of the weights when doing GD is very small compared to the number of neurons. We utilize the weakly convex robust loss (see Lemma 4.1) as well as $m\\geq O(\\eta^2 T^2)$ to establish stability.(see Theoorem 4.3)\n\nNote that training neural networks (i.e., implementing the ERM rule) is known to be computationally hard, even for a two layer network with only three hidden nodes. This has been known since the early 90s. Recent results in deep learning theory focus on two-layer neural networks that are greatly overparameterized ($m$ is large) and involve a certain scale of initialization. Under these settings, we can bound the training error of GD after T iterations by $1/\\sqrt{T}$. This is the state-of-the-art results in computational theory of deep learning. \n\nNow, the important point we want to make here is that the key to the analysis is ensuring that the weights of the trained network do not change by much from initialization. One can then show that training neural networks is similar to dynamics of kernel methods. This is the dominant framework for computational learning theoretical guarantees for training neural networks and is aptly called the “lazy regime” or the “neural tangent kernel” (NTK) setting. \n\nThe early works that laid the foundations for this theory are [r1, r2, r3].\n\n### W2: Regarding $\\alpha_1(\\eta,T)<1$\n\nYes, for that result of ours to make sense we do need $\\alpha_1(\\eta,T) < 1$. However, we can also give a result that is of the same form as the expression in equation (4) of [r4] and get a factor of  $C\\alpha_1(\\eta,T)\\cdot (1+\\alpha_1(\\eta,T))$ instead of $C\\frac{\\alpha_1(\\eta,T)}{1-\\alpha_1(\\eta,T)}$. In that case we don’t need $\\alpha_1(\\eta,T) < 1$.\n\n### W3: Regarding $\\frac{1}{1-\\alpha_1}<1.1$\n\nIt is possible that the reviewer did not realize $\\eta=O(\\frac{1}{\\sqrt{T}})$.\n\nIn order to get $\\frac{1}{1-\\alpha_1}<1.1$, we need $\\alpha_1$ to be a small positive real number, and equivalently, $\\eta\\sqrt{T}$, $\\frac{\\eta T}{n}$ and $\\sqrt{\\beta_1\\eta T}$ are small positive real numbers (through the definition of $\\alpha_1$). Note that we have selected $\\eta=c_0\\frac{1}{\\sqrt{T}}$ in Corollary 3.3, plugging in $\\eta$, we equivalently require $c_0$, $c_0\\frac{\\sqrt{T}}{n}$ and $c_0\\beta_1\\sqrt{T}$ to be small positive real numbers. In Corollary 3.3, we assumed $T\\leq O(n^2)$ and $T\\leq O(1/\\beta_1^2)$, so we can choose $c_0$ to be a proper (small) positive constant so that the three inequalities hold. \n\n### W4: Regarding line 509\n\nThe definition of the generalization gap is the test loss minus the training loss $\\epsilon_{gen}=L_{rob}(W_t)-$$\\hat{L}_{rob}(W_t;S)$\n\nso we can get line 509 by subtracting $E_{S\\sim\\mathcal{D}^{n}}\\hat{L}_{rob}(W_t;S)$ on both sides of Eq (4), so the left hand side will have the generalization gap.\n\n### Q1: Given $\\epsilon>0$, how should we set the parameters of the problem to get generalization error and robust accuracy smaller than $\\epsilon$?\n\nThe relationship is a bit involved since our bounds are post-hoc and not a-priori. In other words, our bound is instance specific, and depends on the given training data and the output of the algorithm. This is in stark contrast to bounds that are based on uniform convergence and hold simultaneously for all hypotheses in the class – there you can ask how many samples or iterations you need to ensure suboptimality. However, note that uniform convergence bounds can be overly pessimistic/vacuous.\nAnyhow, even though there is not a simple answer, below we try to give an intuitive understanding. \n\nLet’s say you want to bound the expected robust test loss by $(1+\\epsilon)$ times the expected training loss (see Lemma 4.2 relating the two quantities). Then, \nTo ensure $\\frac{1}{1-C_x\\cdot \\alpha_1}\\leq 1+\\epsilon$, we need $\\alpha_1\\leq\\frac{\\epsilon}{C_x(1+\\epsilon)}=O(\\epsilon)$. We can give two possible ways of setting the different parameters to ensure that $\\alpha_1 = O(\\epsilon)$. \n\nRecall that $\\alpha_1=O(\\eta\\sqrt{T}+\\frac{\\eta T}{n}+\\sqrt{\\beta_1\\eta T})$.\n\nSet $\\beta_1 = O(\\epsilon^2)$, $n=\\Theta(1/\\epsilon)$, $T=\\Theta(1/\\epsilon^2)$, $\\eta=O(\\frac{1}{T})$,\n\nor set $\\beta_1 = O(\\epsilon^3)$, $n=\\Theta(1/\\epsilon^2)$, $T=\\Theta(1/\\epsilon^4)$, $\\eta=O(\\frac{\\epsilon}{\\sqrt{T}})$.\n\nCheck that $\\eta\\sqrt{T}=O(\\epsilon)$, $\\frac{\\eta T}{n}=O(\\epsilon)$ and $\\sqrt{\\beta_1\\eta T}=O(\\epsilon)$. \n\n### Q2: What happens when m is chosen independently of T\n\nWe can choose $m \\geq \\Theta(n^2)$, and then set $\\eta T\\leq O(n)$. Note though that it seems superfluous as there could be other regimes that could still give us the condition we need. This is why prior works (e.g., [r4, r5]) also state the assumption as we do. \n\nThis also makes sense as our generalization bounds are based on algorithmic stability which depends on parameters $\\eta$ and $T$. If we were using tools from uniform convergence, then m would naturally depend on the sample size and input dimension d. \n\n[r1] Du, Simon S., et al. \"Gradient descent provably optimizes over-parameterized neural networks.\" arXiv preprint arXiv:1810.02054 (2018).\n\n[r2] Arora, Sanjeev, et al. \"Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks.\" International Conference on Machine Learning. PMLR, 2019.\n\n[r3] Ji, Ziwei, et al. \"Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow relu networks.\" arXiv preprint arXiv:1909.12292 (2019).\n\n[r4] Richards, Dominic, et al. \"Stability & generalisation of gradient descent for shallow neural networks without the neural tangent kernel.\" Advances in neural information processing systems 34 (2021): 8609-8621.\n\n[r5] Lei, Yunwen, et al. \"Stability and generalization analysis of gradient methods for shallow neural networks.\" Advances in Neural Information Processing Systems 35 (2022): 38557-38570.", "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:

Meta-review: This paper studies the stability and generalization of adversarial training for two-layer neural networks with smooth activation functions in binary classification problems, focusing on settings beyond the NTK regime and without data distribution assumptions. The authors derive generalization bounds based on uniform stability, particularly for gradient descent (GD) and stochastic gradient descent (SGD). After the authors’ responses, the reviewers recognized the theoretical novelty and generally agreed that this work contributes to a valuable theoretical understanding of adversarial training. Some reviewers also raised concerns about the practical relevance of the results, though this concern is common in theoretical papers. Overall, all reviewers appreciate this theoretical paper, and I recommend acceptance.
Decision: Accept (poster)