Stability and Generalization of Adversarial Training for Shallow Neural Networks with Smooth Activation

Authors: kaibo  zhang
yunjuan  wang
raman  arora
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 06:23:35

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.

Main paper: 
 introduction: 
 Despite the remarkable performance of over-parameterized deep networks in real-world applications, recent studies have revealed that they are highly vulnerable to adversarial attacks. These attacks use 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-based 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 et al., 2020] ), has proven to be an 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 et 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 a classical tool in learning theory that has been extensively studied in the literature [Bousquet and Elisseeff, 2002, Hardt et al., 2016] . Uniform argument stability measures the difference in output parameters when an algorithm is run on two training sets that differ by only one sample. In the standard (non-robust) setting, Hardt et al. [2016] show a uniform stability bound of O( ηT n ) after T iterations of gradient descent with step size η on convex and smooth losses using a training dataset of size n. They further provide a uniform stability bound of O( T q n ) for smooth and non-convex losses with decaying step size η = O( 1 t ), where q ∈ (0, 1) is a constant. The choice of decaying step size is common in the non-convex setting, as maintaining a constant step size leads to an exponentially increasing bound on uniform stability.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 O(η √ 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 O(ηT α) that grows linearly in T , where α is the size of adversarial perturbation in ℓ p threat models. These works, while partially addressing the issue, only focus on general convex / non-convex functions. However, neural networks, which are a 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-parameterized neural networks with smooth activation functions and logistic loss. Our key contributions are as follows:1. We present a bound of O( √ ηT + ηT n + √ βηT ) on the uniform argument stability of the gradient descent-based adversarial training of over-parameterized network after T iterations with step size η, where β 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 descent-based adversarial training. 3. We leverage Moreau'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 smoothing, and demonstrate its superiority compared with gradient descent-based adversarial training algorithm.Stability Analysis. The notion of stability was initially introduced in Bousquet and Elisseeff [2002] to study the generalization of statistical learning problems. More recently, a fine-grained analysis has been presented by Feldman and Vondrak [2019] and Bousquet et 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 O(η works [Charles et al., 2019 , Li et al., 2020 , Zou et al., 2021 , Chen et al., 2023] have focused on a 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 considering 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 on 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 nonsmooth [Liu et al., 2020 , Xing et al., 2021a , Xiao et al., 2022b] . To resolve this issue, Farnia and Ozdaglar [2021] make a strong assumption that the loss is concave in input x. We consider a binary classification problem with a bounded input space X inside a Euclidean ball of radius C x , and label space Y = {±1}. We assume that data are drawn according to an unknown probability distribution D on X × Y. The learner has access to n training data drawn i.i.d. from D; i.e., S = {z i = (x i , y i )} n i=1 ∼ D n . 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 a pair of weight matrices (a, W):f W (x) = f (x; W) := m s=1 a s ϕ(⟨w s , x⟩).Here, m is a positive integer representing the number of hidden units, i.e., the width of the networks.ϕ : R → R is a 1-Lipschitz, H-smooth activation function. Formally, ∀z, z ′ ∈ R, |ϕ ′ (z)| ≤ 1, |ϕ ′ (z) -ϕ ′ (z ′ )| ≤ H |z -z ′ |.The smoothness property of activation functions is commonly assumed in algorithmic stability literature and in theory of deep learning and covers a 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 1 , . . . , a m ] ∈ R m and W = [w 1 , . . . , w m ] ∈ R d×m , respectively. The top layer weights are initialized such that|a i | = 1 √ m , ∀i ∈ [m],and are kept fixed throughout the training process. Prior works [Du et al., 2018 , Arora et al., 2019 , Ji and Telgarsky, 2019] often initialize a i to be uniformly sampled from {± 1 √ m }, 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., W 0 can be either a 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 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 ℓ p threat models with perturbation size of α, i.e., B(x) = {x : ∥x -x∥ p ≤ α}, as well as a 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.In this work, we focus on logistic loss, ℓ(z) = ln(1 + e -z ), which serves as a smooth and convex surrogate loss for the 0-1 loss. With a slight abuse of notation, for a fixed sample z = (x, y), we define ℓ(z, W) := ℓ(yf (x; W)). The population and empirical loss w.r.t. ℓ(•) are denoted, respectively, asL(W) := E (x,y)∼D ℓ(yf (x; W)), L(W; S) := 1 n n i=1 ℓ(y i f (x i ; W)).Given B, for a fixed sample z = (x, y), we define the robust loss as ℓ rob (z, W) := maxx∈B(x) ℓ(yf (x; W)).The robust population and empirical loss w.r.t. ℓ(•) are defined asL rob (W) := E (x,y)∼D max x∈B(x) ℓ(yf (x; W)) L rob (W; S) := 1 n n i=1 max xi∈B(xi) ℓ(y i f (x i ; W)).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 t-th iterate of adversarial training as W t . For each training example (x i , y i ), at iteration t, we generate a β 1 -optimal adversarial example (x i (W t ), y i ), which satisfies the following condition:EQUATIONSetting β 1 = 0 recovers the scenario where we have access to the worst-case adversarial attack. As this may not be feasible in practice due to computational reason, the parameter β 1 allows us to capture the precision of the attack algorithm, which includes common attacks such as projected gradient descent (PGD) [Madry et al., 2018] . We should regard β 1 as a parameter we can choose. Our results in Section 3 suggest that we can achieve better generalization by adding more computation and making β 1 smaller. Optimizing the Moreau Envelope. Since the robust loss is non-smooth [Xiao et al., 2022a] , we utilize Moreau's envelope to construct a 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 L rob (U; S) + 1 2µ ∥U -W∥ 2 F .Selecting µ appropriately ensures that L rob (U; S) + 1 2µ ∥U -W∥ 2 F is a strongly convex function w.r.t. U. Given W and S, we define U µ (W; S) = argmin U∈R d×m L rob (U; S) + 1 2µ ∥U -W∥ 2 F , which can be obtained via subgradient-based method (solve a min-max optimization). The gradient of the Moreau envelope can be simply calculated as∇ W M µ (W; S) = 1 µ (W -U µ (W; S)).Given training data S, at each iteration t, we generate a β 2 -optimal minimizer U µ (W t ; S) that satisfiesEQUATIONWe remark that β 2 -optimal minimizer defined in Equation ( 2) and β 1 -optimal 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 = {z i } n i=1 drawn i.i.d. from D, let S ′ denote the training set obtained by replacing one example in S with an independently drawn example z ′ ∼ D. We refer to S, S ′ as neighboring samples and write S ≃ S ′ . Given an algorithm A : (X × Y) n → H, where the hypothesis class H is parameterized using a parameter matrix W ∈ R d×m , we define the uniform argument stability as δ A (S, S ′ ) := ∥A(S) -A(S ′ )∥ F .For any L-Lipschitz loss function g, |g(A(S), z)-g(A(S ′ ), z)| ≤ Lδ A (S, S ′ ). The standard stability argument [Mohri et al., 2018] relates the expected generalization gap to the uniform argument stability.E S∼D n ε gen (A(S)) := E S∼D n E z∼D g(A(S), z) - 1 n n i=1 g(A(S), z i ) ≤ L sup S≃S ′ δ A (S, S ′ ). (3)In this paper, we consider robust generalization using logistic loss, so function g(W, z) = ℓ rob (z, W), andε gen (W) = E z∼D [ℓ rob (z, W)] -1 n n i=1 ℓ rob (z i , W).We also remark that a 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. 
the gradient of m: 
 µ (W; S) is ∇ W M µ (W; S) = 1 µ (W -U µ (W; S)). 3. M µ (W; S) + ∥W∥ 2 F 2 √ m HC 2 x -µ is convex. 4. U µ (W; S) is √ m HC 2 x √ m HC 2 x -µ -Lipschitz in W w.r.t the Frobenius norm. 5. M µ (W; S) is max 1 µ , 1 √ m HC 2 x -µ -smooth. 6. L rob (W; S) - C 2 x 2 1 µ - HC 2 x √ m ≤ M µ (W; S) ≤ L rob (W; S). 7. ∥∇ W M µ (W; S)∥ F ≤ C x .Proof of Lemma C.1. The first 5 statements are covered in the proof of [Xiao et al., 2024, Lemma A.1] . For the statement 6,L rob (W; S) = L rob (W; S) + 1 2µ ∥W -W∥ 2 F ≥ min U L rob (U; S) + 1 2µ ∥U -W∥ 2 F = M µ (W; S) = L rob (W; S) + min U L rob (U; S) -L rob (W; S) + 1 2µ ∥U -W∥ 2 F ≥ L rob (W; S) + min U ∇ W L rob (W; S), U-W - HC 2 x 2 √ m ∥U-W∥ 2 F + 1 2µ ∥U-W∥ 2 F ("almost" convex robust loss from Lemma A.4) ≥ L rob (W; S) + min U -C x ∥U -W∥ F - HC 2 x 2 √ m ∥U -W∥ 2 F + 1 2µ ∥U -W∥ 2 F (Lemma A.5) = L rob (W; S) - C 2 x 2 1 µ - HC 2 x √ m. Now we prove statement 7. For any γ ∈ (0, 1), from the definition of the Moreau envelope,L rob (U µ (W; S); S) + 1 2µ ∥U µ (W; S) -W∥ 2 F ≤ L rob ((1 -γ)W + γU µ (W; S); S) + 1 2µ ∥(1 -γ)W + γU µ (W; S) -W∥ 2 F (U µ (W; S) obtains the minimum) ≤ L rob (U µ (W; S); S) + C x (1 -γ)∥U µ (W; S) -W∥ F + γ 2 2µ ∥U µ (W; S) -W∥ 2 F . (The robust loss is C x -Lip from Lemma A.2)Simplifying the inequality above, we get∥U µ (W; S) -W∥ F ≤ 2µC x 1 + γ . Let γ → 1, we get ∥∇ W M µ (W; S)∥ F = 1 µ ∥U µ (W; S) -W∥ F ≤ C x .Next we show a result similar as [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 depend on the subgradient, so it can be applied to the robust loss.Lemma C.2. Let Ũµ (W; S) be any β 2 -optimal minimizer of minU L rob (U; S) + 1 2µ ∥U -W∥ 2 F .For two data sets S and S (i) that differ in only one example and any weight matrix W, we have∥U µ (W; S) -U µ (W; S (i) )∥ F ≤ 2C x n 1 µ - HC 2 x √ m and ∥ Ũµ (W; S) -U µ (W; S)∥ F ≤ 2β 2 1 µ - HC 2 x √ m .Proof of Lemma C.2. From strong convexity of the regularized robust loss, we haveL rob (U µ (W; S (i) ); S) + 1 2µ ∥U µ (W; S (i) ) -W∥ 2 F ≥ L rob (U µ (W; S); S) + 1 2µ ∥U µ (W; S) -W∥ 2 F + ( 1 2µ - HC 2 x 2 √ m )∥U µ (W; S (i) ) -U µ (W; S)∥ 2 F ,and similarly,L rob (U µ (W; S); S (i) ) + 1 2µ ∥U µ (W; S) -W∥ 2 F ≥ L rob (U µ (W; S (i) ); S (i) ) + 1 2µ ∥U µ (W; S (i) ) -W∥ 2 F + ( 1 2µ - HC 2 x 2 √ m )∥U µ (W; S) -U µ (W; S (i) )∥ 2 F .Adding these two inequalities,EQUATION)From the strong convexity of the regularized robust loss, we also haveβ 2 ≥ L rob ( Ũµ (W; S); S) + 1 2µ ∥ Ũµ (W; S) -W∥ 2 F -L rob (U µ (W; S); S) + 1 2µ ∥U µ (W; S) -W∥ 2 F ≥ ( 1 2µ - HC 2 x 2 √ m )∥ Ũµ (W; S) -U µ (W; S)∥ 2 F . We get ∥ Ũµ (W; S) -U µ (W; S)∥ F ≤ β2 1 2µ - HC 2 x 2 √ m. Now we show an upper bound that is key to bounding the stability of the weight matrix.Lemma C.3. For any η ≤ µ ≤ √ m 2HC 2x and any weight matrices W 1 and W 2 ,∥W 1 -η∇ W M µ (W 1 ; S) -W 2 + η∇ W M µ (W 2 ; S)∥ 2 F ≤ ∥W 1 -W 2 ∥ 2 F 1 - 4HC 2 x η √ m . Proof of Lemma C.3. Define ψ 1 (W) = M µ (W; S) -M µ (W 1 ; S) -∇ W M µ (W 1 ; S), W -W 1 . From Lemma C.1, ψ 1 (W) is 1 µ -smooth.From the standard descent lemma of smooth functions, for any η ≤ µ,ψ 1 (W 2 -η∇ W ψ 1 (W 2 )) ≤ ψ 1 (W 2 ) - η 2 ∥∇ W ψ 1 (W 2 )∥ 2 F = ψ 1 (W 2 ) - η 2 ∥∇ W M µ (W 2 ; S) -∇ W M µ (W 1 ; S)∥ 2 F . Since ψ 1 (W) + ∥W∥ 2 F 2 √ m HC 2 x -µ is convex from Lemma C.1, ψ 1 (W 2 -η∇ W ψ 1 (W 2 )) ≥ψ 1 (W 1 ) + ∇ψ 1 (W 1 ), W 2 -η∇ W ψ 1 (W 2 ) -W 1 - ∥W 2 -η∇ W ψ 1 (W 2 ) -W 1 ∥ 2 F 2 √ m HC 2 x -µ =ψ 1 (W 1 ) - ∥W 2 -η∇ W ψ 1 (W 2 ) -W 1 ∥ 2 F 2 √ m HC 2 x -µ ≥ψ 1 (W 1 ) - ∥W 2 -η∇ W M µ (W 2 ; S) -W 1 + η∇ W M µ (W 1 ; S)∥ 2 F √ m HC 2 x .Combining the two inequalities above,M µ (W 2 ; S) -M µ (W 1 ; S) -∇ W M µ (W 1 ; S), W 2 -W 1 =ψ 1 (W 2 ) -ψ 1 (W 1 ) ≥ η 2 ∥∇ W M µ (W 2 ; S)-∇ W M µ (W 1 ; S)∥ 2 F - ∥W 2 -η∇ W M µ (W 2 ; S)-W 1 +η∇ W M µ (W 1 ; S)∥ 2 F √ m HC 2 x .Similarly, we can get the counterpart of this equation:M µ (W 1 ; S) -M µ (W 2 ; S) -∇ W M µ (W 2 ; S), W 1 -W 2 ≥ η 2 ∥∇ W M µ (W 1 ; S)-∇ W M µ (W 2 ; S)∥ 2 F - ∥W 1 -η∇ W M µ (W 1 ; S)-W 2 +η∇ W M µ (W 2 ; S)∥ 2 F √ m HC 2 x .Adding these two inequalities, we get∇ W M µ (W 2 ; S) -∇ W M µ (W 1 ; S), W 2 -W 1 ≥η∥∇ W M µ (W 1 ; S)-∇ W M µ (W 2 ; S)∥ 2 F - 2∥W 1 -η∇ W M µ (W 1 ; S)-W 2 +η∇ W M µ (W 2 ; S)∥ 2 F √ m HC 2 x . Thus, ∥W 1 -η∇ W M µ (W 1 ; S) -W 2 + η∇ W M µ (W 2 ; S)∥ 2 F =∥W 1 -W 2 ∥ 2 F + η 2 ∥∇ W M µ (W 1 ; S) -∇ W M µ (W 2 ; S)∥ 2 F -2η ∇ W M µ (W 1 ; S) -∇ W M µ (W 2 ; S), W 1 -W 2 ≤∥W 1 -W 2 ∥ 2 F + η 2 ∥∇ W M µ (W 1 ; S) -∇ W M µ (W 2 ; S)∥ 2 F -2η 2 ∥∇ W M µ (W 1 ; S) -∇ W M µ (W 2 ; S)∥ 2 F + 4η∥W 1 -η∇ W M µ (W 1 ; S) -W 2 + η∇ W M µ (W 2 ; S)∥ 2 F √ m HC 2 x ≤∥W 1 -W 2 ∥ 2 F + 4HC 2 x η∥W 1 -η∇ W M µ (W 1 ; S) -W 2 + η∇ W M µ (W 2 ; S)∥ 2 F √ m .We get the desired result by simplifying the above inequality.Theorem C.4. (Restatement of Theorem 3.5) For any η ≤ min{µ,√ m 8HC 2 x } ≤ √ m 2HC 2 x , let W T and W (i)T be the weight matrices returned after running Algorithm 1 with Moreau Envelope using S and S (i) respectively for T iterations. Here S and S (i) only differ in the i-th data. We have∥W T -W (i) T ∥ 2 F ≤ e 1+ 8HC 2 x ηT √ m (T + 1) 2 4C x η n + 4η β 2 µ 2 .Proof of Theorem C.4.∥W t+1 -W (i) t+1 ∥ 2 F =∥W t -η 1 µ (W t - Ũµ (W t ; S)) -W (i) t + η 1 µ (W (i) t - Ũµ (W (i) t ; S (i) ))∥ 2 F ≤   ∥Wt -η 1 µ (W t -U µ (W t ; S)) -W (i) t + η 1 µ (W (i) t -U µ (W (i) t ; S (i) ))∥ F + 2η µ 2β 2 1 µ - HC 2 x √ m    2 (Lemma C.2) ≤ ∥W t -η 1 µ (W t -U µ (W t ; S)) -W (i) t + η 1 µ (W (i) t -U µ (W (i) t ; S))∥ F + 2C x η µn 1 µ - HC 2 x √ m + 2η µ 2β 2 1 µ - HC 2 x √ m 2 (Lemma C.2) ≤ ∥W t -η 1 µ (W t -U µ (W t ; S)) -W (i) t + η 1 µ (W (i) t -U µ (W (i) t ; S))∥ F + 4C x η n + 4η β 2 µ 2 ≤ T + 2 T + 1 ∥W t -η∇ W M µ (W t ; S) -W (i) t + η∇ W M µ (W (i) t ; S)∥ 2 F + (T + 2) 4C x η n + 4η β 2 µ 2 ((a + b) 2 ≤ (1 + p)a 2 + (1 + 1/p)b 2 for p > 0.) ≤ T + 2 T + 1 • 1 1 - 4HC 2 x η √ m ∥W t -W (i) t ∥ 2 F + (T + 2) 4C x η n + 4η β 2 µ 2 . (Lemma C.3) Define γ = T +2 T +1 • 1 1- 4HC 2 x η √ m, then the inequality above can be written as∥W t+1 -W (i) t+1 ∥ 2 F ≤ γ∥W t -W (i) t ∥ 2 F + (T + 2) 4C x η n + 4η β 2 µ 2 .Dividing both sides by γ t+1 and summing up the inequality, we get∥W T -W (i) T ∥ 2 F ≤ γ T γ -1 (T + 2) 4C x η n + 4η β 2 µ 2 ≤ γ T (T + 1)(T + 2) 4C x η n + 4η β 2 µ 2 = T + 2 T + 1 T +1   1 1 - 4HC 2 x η √ m   T (T + 1) 2 4C x η n + 4η β 2 µ 2 ≤ e 1+ 4HC 2 x η √ m T 1- 4HC 2 x η √ m (T + 1) 2 4C x η n + 4η β 2 µ 2 ( 1 1-x ≤ e x 1-x ) ≤ e 1+ 8HC 2 x ηT √ m (T + 1) 2 4C x η n + 4η β 2 µ 2 . (η ≤ √ m 8HC 2 x )The proof of Theorem 3.5 is obvious from Theorem C.4 by observing e x η 2 T 2 . After T iterations of Algorithm 1 with Moreau Envelope with η ≤ min{µ,√ m 8HC 2 x } ≤ √ m 2HC 2 x , we have E S∼D n L rob (W T ) ≤ E S∼D n M µ (W T ; S) + C 2 x µ 1 -e 4.5 C x (T + 1) 4Cxη n + 4η β2 µ and E S∼D n L rob (W T ) ≤ E S∼D n M µ (W T ; S) + C 2 x µ + e 4.5 C x (T + 1) 4C x η n + 4η β 2 µ .Now we derive an optimization guarantee of optimizing the Moreau envelope.Theorem C.6. Assume the width of the networks satisfies m ≥ H 2 C 4 x η 2 T 2 . After running Algorithm 1 with Moreau Envelope for T iterations with η≤ µ ≤ √ m 2HC 2 x , we have min 1≤t≤T M µ (W t ; S) ≤ min W L rob (W; S) + 2 ηT ∥W -W 0 ∥ 2 F + 2η(T + 1) β 2 µ .Proof of Theorem C.6. From Lemma C.1, M µ (W; S) is 1 µ smooth, so M µ (W t+1 ; S)EQUATIONFrom the weakly convex property Lemma C.1-3,M µ (W; S) ≥ M µ (W t ; S) + ⟨∇ W M µ (W t ; S), W -W t ⟩ - HC 2 x √ m ∥W t -W∥ 2 F = M µ (W t ; S) + ⟨∇ W M µ (W t ; S), W -W t+1 ⟩ + ⟨W t+1 -W t , ∇ W M µ (W t ; S)⟩ - HC 2 x √ m ∥W t -W∥ 2 F ≥ M µ (W t+1 ; S) + ⟨∇ W M µ (W t ; S), W -W t+1 ⟩ - 1 2µ ∥W t+1 -W t ∥ 2 F - HC 2 x √ m ∥W t -W∥ 2 F (equation (13)) ≥ M µ (W t+1 ; S) + 1 η ⟨W t+1 -W t , W t+1 -W⟩ - 1 2η ∥W t+1 -W t ∥ 2 F - HC 2 x √ m ∥W t -W∥ 2 F (µ ≥ η) - 1 µ ∥U µ (W t ; S) - Ũµ (W t ; S)∥ F • ∥W t+1 -W∥ F (Lemma C.1-2.) ≥ M µ (W t+1 ; S) + 1 η ⟨W t+1 -W t , W t+1 -W⟩ - 1 2η ∥W t+1 -W t ∥ 2 F - HC 2 x √ m ∥W t -W∥ 2 F -2 β 2 µ • ∥W t+1 -W∥ F . (Lemma C.2)From the inequality above, for any weight matrix W,∥W t+1 -W∥ 2 F =∥W t -W∥ 2 F -∥W t+1 -W t ∥ 2 F + 2 ⟨W t+1 -W t , W t+1 -W⟩ ≤∥W t -W∥ 2 F + 2ηM µ (W; S) -2ηM µ (W t+1 ; S) + 2HC 2 x η √ m ∥W t -W∥ 2 F + 4η β 2 µ • ∥W t+1 -W∥ F .Simplifying the above inequality and combining with Lemma C.1-6 gives usEQUATIONDividing both sides by 1 +1 T t+1 1 + 2HC 2 x η √ m t+1and summing up the inequality for t = 0, 1, . . . , T -1, we getmin 1≤t≤T M µ (W t ; S) ≤ L rob (W; S) + 2η(T + 1) β 2 µ + ∥W -W 0 ∥ 2 F 2η 1 + 1 T T t=1 1 (1+ 1 T ) t 1+ 2HC 2 x η √ m t ≤ L rob (W; S) + 2 ηT ∥W -W 0 ∥ 2 F + 2η(T + 1) β 2 µ ,where in the last inequality we use 1+ 1 T 1 + 2HC 2 x η √ m ≤ 1 + 1 T 1 + 2 T ≤ 1 + 3 T +1 T 2 . Theorem 3.6. Define α 2 (η, T ) := O(C 2 x ηT n + C x ηT β2 µ ). Assume α 2 (η, T ) < 1.Then, after T ≥ 8 iterations of Algorithm Moreau Envelope with step-size η ≤ µ on a network of width m ≥ H 2 C 4x η 2 T 2 , we have min[ 9T 10 ]≤t≤T E S∼D n ε gen (W t ) ≤ 55α 2 (η, T ) 1 -α 2 (η, T ) E S∼D n ∆ oracle S + C 2 x µ + 2η(T + 1) β 2 µ ,andmin 1≤t≤T E S∼D n L rob (W t ) ≤ 1 1 -α 2 (η, T ) E S∼D n ∆ oracle S + C 2 x µ + 2η(T + 1) β 2 µ .Proof of Theorem 3.6. Define t 0 := [ 9T 10 ] and k :=1 (1+ 1 T ) 1+ 2HC 2 x η √ m. Dividing both sides of equation ( 14) by 1 +1 T t+1 1 + 2HC 2 x η √ m t+1and summing up, we have2η 1 + 1 T T t=1 k t L rob (W; S) + 2η(T + 1) β 2 µ + ∥W -W 0 ∥ 2 F ≥2η 1 + 1 T T t=t0 k t M µ (W t ; S).Taking minimum over all weight matrices W,2η 1 + 1 T T t=t0 k t L rob (W t ; S) -C 2 x µ ≤2η 1 + 1 T T t=t0 k t M µ (W t ; S) (Lemma C.1-6.) ≤ min W 2η 1 + 1 T T t=1 k t L rob (W; S) + 2η(T + 1) β 2 µ + ∥W -W 0 ∥ 2 F ≤2η 1 + 1 T T t=1 k t • min W L rob (W; S) + 2 ηT ∥W -W 0 ∥ 2 F + 2η(T + 1) β 2 µ =2η 1 + 1 T T t=1 k t • ∆ oracle S + 2η(T + 1) β 2 µ .Taking the expectation on both sides, we getT t=t0 k t min t0≤t≤T E S∼D n L rob (W t ; S) -C 2 x µ ≤ T t=t0 k t E S∼D n L rob (W t ; S) -C 2 x µ ≤ T t=1 k t • E S∼D n ∆ oracle S + 2η(T + 1) β 2 µ .Simplifying the equation above, we getmin t0≤t≤T E S∼D n L rob (W t ; S) ≤ C 2 x µ + T t=1 k t T t=t0 k t • E S∼D n ∆ oracle S + 2η(T + 1) β 2 µ (15) ≤ C 2 x µ + 9 r=0 1 k r T 10 • E S∼D n ∆ oracle S + 2η(T + 1) β 2 µ ≤ C 2 x µ + 9 r=0 e 3r 10 • E S∼D n ∆ oracle S + 2η(T + 1) β 2 µ (m ≥ H 2 C 4 x η 2 T 2 ) ≤ C 2 x µ + 55 E S∼D n ∆ oracle S + 2η(T + 1) β 2 µ .Equation (4) gives us for any t ≤ T , E S∼D n ε gen (W t ) ≤ α2(η,T ) 1-α2(η,T ) E S∼D n L rob (W t ; S). Therefore,min t0≤t≤T E S∼D n ε gen (W t ) ≤ α 2 (η, T ) 1 -α 2 (η, T ) min t0≤t≤T E S∼D n L rob (W t ; S) ≤ α 2 (η, T ) 1 -α 2 (η, T ) C 2 x µ + 55 E S∼D n ∆ oracle S + 2η(T + 1) β 2 µ .The proof of the second statement takes a similar approach. Following the same procedure, we can replace t 0 by 0 in equation ( 15), and getmin 0≤t≤T E S∼D n L rob (W t ; S) ≤ E S∼D n ∆ oracle S + C 2 x µ + 2η(T + 1) β 2 µ .Combining with equation ( 4),min 0≤t≤T E S∼D n L rob (W t ) ≤ 1 1 -α 2 (η, T ) min 0≤t≤T E S∼D n L rob (W t ; S) ≤ 1 1 -α 2 (η, T ) E S∼D n ∆ oracle S + C 2 x µ + 2η(T + 1) β 2 µ . Corollary 3.7. After T ≤ O(min{n 2 , 1 β 2/3 2 }) iterations of Algorithm 1 with Moreau Envelope with step-size η = µ = Θ( 1 C 2 x √T ) on a network of width m ≥ Ω(T ), we have for any weight matrix W,min 1≤t≤T E S∼D n L rob (W t ) ≤ 1.1L rob (W) + O C 2 x ∥W -W 0 ∥ 2 F √ T + O 1 √ T .Proof of Corollary 3.7. Under the conditions of the corollary, we have m ≥ H 2 C 4 x η 2 T 2 , andα 2 (η, T ) = O(C 2 x ηT n + C x ηT β2µ ) can be small enough so that 1 1-α2(η,T ) ≤ 1.1. Then it is clear that this corollary is a special case of Theorem 3.6.• 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 a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
main result: 
 In this section, we present our main results, providing theoretical guarantees for adversarial training of two-layer neural networks with smooth activation functions. We discuss (stochastic) adversarial training in Section 3.1 and gradient descent-based Moreau's smoothing in Section 3.2.Our generalization bounds rely on a key quantity, the Adversarial Regularized Empirical Risk Minimization (ARERM) Oracle defined as∆ oracle S := min W∈R d×m L rob (W; S) + 2∥W -W 0 ∥ 2 F ηT .Given a sample, ∆ oracle S returns the minimal empirical risk in the vicinity of an initialization W 0 .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 ≥ H 2 C 4 x η 2 (T + 1) 2 . Then, after T iterations of Algorithm 1 with GD, for any neighboring datasets S, S ′ , we havesup S≃S ′ δ A (S, S ′ ) ≤ O(C x η √ T + C x ηT n + β 1 ηT ).Remarkably, setting β 1 = 0 yields a bound of O(η √ T + ηT n ) on the UAS of Algorithm 1, thereby recovering the result in prior work of Xing et 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 we assume that the networks are sufficiently over-parameterized, i.e., m ≥ Ω(η 2 T 2 ), a condition that is commonly assumed in deep learning theory. We can also regard this condition as early stopping, whereinT ≤ O √ m HC 2x η . This view is also consistent with several empirical studies [Caruana et al., 2000 , Rice et al., 2020 , Pang et al., 2021] .Next, we show that stable robust learning rules do not overfit. Theorem 3.2. Define α 1 (η,T ) := O(C 2 x η √ T + C 2 x ηT n + C x √ β 1 ηT ).Assume that the width of the networks satisfies m ≥ H 2 C 4x η 2 (T + 1) 2 , and α 1 (η, T ) < 1. Then, after T iterations of Algorithm 1 with GD, we have min[ 9T 10 ]≤t≤T E S∼D n ε gen (W t ) ≤ 17α 1 (η, T ) 1 -α 1 (η, T ) E S∼D n ∆ oracle S + C 2 x η 2 + β 1 ,andmin 0≤t≤T E S∼D n L rob (W t ) ≤ 1 1 -α 1 (η, T ) E S∼D n ∆ oracle S + C 2 x η 2 + β 1 .The result above bounds the robust generalization gap and the robust loss in terms of the ARERM oracle, a step size-dependent term O(η), and the precision of the adversarial examples β 1 . 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 a bound on the expected robust loss.Corollary 3.3. After T ≤ O(min{n 2 , 1 β 2 1 }) iterations of Algorithm 1 with GD using a step size of η = Θ( 1 C 2 x √T ) on a network with width m ≥ Ω(T ), for any weight matrix Wmin 0≤t≤T E S∼D n L rob (W t ) ≤ 1.1L rob (W) + O C 2 x ∥W -W 0 ∥ 2 F √ T + O 1 √ T .Since corollary 3.3 holds for any W 0 , 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., ∥W * -W 0 ∥ F = O(1)) that achieves a small robust loss L rob (W * ) ≈ 0, we have that the minimum expected robust loss over all iterates approaches O 1 √ T . Further, if β 1 is small enough and m ≳ n 2 , then T can be of the order Θ(n 2 ), leading to a O(1/n) 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 setB(x) = {x}, ∀x ∈ X , β 1 = 0, and redefining α 1 (η, T ) = O(C 2 x ηT n ).In this context, we can show that gradient descent for the binary classification problem can achieve excess risk bound ofO(1/ √ n) by taking ηT = Θ( √ n) if m ≳ n and assuming ∥W * -W 0 ∥ F = O(1), where W * ∈ argmin W L rob (W).Next, we extend our result to the stochastic adversarial training. Theorem 3.4. After T iterations of Algorithm 1 with SGD on a network of width m ≥ H 2 C 4x η 2 (T + 1) 2 we have that for any weight matrix W,min 0≤t≤T E {z1,...,zt}∼D t L rob (W t ) ≤ L rob (W) + ∥W -W 0 ∥ 2 F η(T + 1) + C 2 x η 2 + β 1 .Similar to the discussion following Corollary 3.3, we assert that if we assume that there exists an over-parameterized robust network with small robust loss, then using a step size of η = 1/ √ T , stochastic adversarial training yields an excess risk bound of O(1/ √ T ).We now present a bound on the uniform argument stability of gradient descent with smoothing based on Moreau's envelope. Theorem 3.5. After T iterations of Algorithm 1 with Moreau Envelope with step-size η ≤ min{µ,√ m 8HC 2 x } ≤ √ m 2HC 2 x , on a network of width m ≥ H 2 C 4x η 2 T 2 , for any neighboring datasets S, S ′ , we havesup S≃S ′ δ A (S, S ′ ) ≤ O C x ηT n + ηT β 2 µ .Setting β 2 = 0 yields a bound of O( ηT n ) on the UAS of Algorithm 1, thereby recovering the result in prior work of [Hardt et al., 2016 , Xiao et al., 2024] for convex and smooth functions. Note that by using Moreau's envolope, we are able to shave off the O(η √ T ) term that appears in Theorem 3.1.Although inspired by Xiao et al. [2024] , Theorem 3.5 differs from the non-convex 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 a constant step size. In 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 a decaying step size η t ≤ µ t .Such a condition might be impractical if µ is chosen to be sufficiently small. In fact, our results indicate that it is necessary to select a sufficiently small µ so that the robust training loss is well approximated by the Moreau envelope (see Lemma C.1 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 β 1 = β 2 = 0, it requires more computational resources. Specifically, for the calculation of the gradient at each step, we need to solve a min-max optimization problem with a strongly convex and non-smooth objective to obtain a β-optimal minimizer. Additionally, for every step of this min-max optimization, we need to generate adversarial examples and apply sub-gradient descent.Theorem 3.6. Define α 2 (η,T ) := O(C 2 x ηT n + C x ηT β2 µ ). Assume α 2 (η, T ) < 1. Then, after T ≥ 8 iterations of Algorithm Moreau Envelope with step-size η ≤ µ on a network of width m ≥ H 2 C 4x η 2 T 2 , we have min[ 9T 10 ]≤t≤T E S∼D n ε gen (W t ) ≤ 55α 2 (η, T ) 1 -α 2 (η, T ) E S∼D n ∆ oracle S + C 2 x µ + 2η(T + 1) β 2 µ ,andmin 1≤t≤T E S∼D n L rob (W t ) ≤ 1 1 -α 2 (η, T ) E S∼D n ∆ oracle S + C 2 x µ + 2η(T + 1)β 2 µ .Similar to Theorem 3.2, the result above shows that both the robust generalization gap as well as the robust loss can be bounded in terms of the ARERM oracle, parameter µ in Moreau's envelope, and a term of O(ηT β 2 /µ) dependent on the precision of generating the minimizer of Moreau envelope. 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 a bound for the the last iterate for the case when β 2 = 0. We conclude the section by presenting the following direct corollary. Corollary 3.7. After T ≤ O(min{n 2 , 1β 2/3 2 }) iterations of Algorithm 1 with Moreau Envelope with step-size η = µ = Θ( 1 C 2 x √ T) on a network of width m ≥ Ω(T ), we have for any weight matrix W,min 1≤t≤T E S∼D n L rob (W t ) ≤ 1.1L rob (W) + O C 2 x ∥W -W 0 ∥ 2 F √ T + O 1 √ T . 
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 β 1 = 0, β 2 = 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 l > 0. A function f (x) is said to be -l-weakly convex if f (x) + l 2 ∥x∥ 2 2 is convex in x. Lemma 4.2. (Restatement of Lemma A.4) For any weight matrices W 1 and W 2 , L rob (W 2 ; S) ≥ L rob (W 1 ; S) + ∇ W L rob (W 1 ; S), W 2 -W 1 - HC 2 x 2 √ m ∥W 2 -W 1 ∥ 2 F . Equivalently, L rob (W; S) is - HC 2 x √ m -weakly convex.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 to 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 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-parameterized network m ≥ poly(ηT ). An additional challenge we face is that the robust loss is non-smooth even if its standard counterpart (logistic loss) is 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 L rob (W T ; S) 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:E S∼D n L rob (W T ) ≤ E S∼D n 1 1 -C x • sup S≃S ′ δ A (S, S ′ ) L rob (W T ; S).This result gives a way to bound the expected robust loss. Say you want to bound the expected robust test loss by (1 + ϵ) times the expected training loss. Then, to ensure1 1-α1(η,T ) ≤ 1 + ϵ, we need α 1 (η, T ) ≤ ϵ 1+ϵ = O(ϵ).Since α 1 (η, T ) = O(η √ T + ηT n + √ β 1 ηT ),we can set different parameters in more than one way to ensure that α 1 (η, T ) = O(ϵ). We can setβ 1 = O(ϵ 2 ), n = Θ(1/ϵ), T = Θ(1/ϵ 2 ), η = O( 1 T ); or set β 1 = O(ϵ 3 ), n = Θ(1/ϵ 2 ), T = Θ(1/ϵ 4 ), η = O( ϵ √ T ).The stability guarantee we give in the following Theorem 4.4 is similar to the result in the convex case [Xing et al., 2021a] . While [Xing et 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 2HC 2 x ηT / √ m , which is small for over-parameterized neural networks (m ≥ ploy(ηT )). Theorem 4.4. (Restatement of Theorem 3.1) Let S and S ′ be any two neighboring data sets, i.e., they differ only in one example. Let W T and W ′ T denote the weight matrices returned after T iterations of Algorithm 1 with GD on S and S ′ , respectively. Then, we have∥W T -W ′ T ∥ 2 F ≤ exp 1 + 2HC 2 x ηT √ m • 4C 2 x η 2 (T + 1) + 4C 2 x η 2 (T + 1) 2 n 2 .We next provide an intermediate lemma that lead us to Theorem 3.2.Lemma 4.5. (Restatement of Theorem B.2) Set k = 1 + HC 2 x η √ m -1 . Then after T ≤ √ m HC 2 x η -1 iterations of Algorithm 1 with GD, 1 T t=0 k t T t=0 k t L rob (W t ; S) ≤ ∆ oracle S + C 2 x η 2 .Richards and Kuzborskij [2021] (see Lemma 2 in their paper) give an optimization guarantee by providing an upper bound on the averaged training loss 1 T T t=1 L(W t ; 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 t+1 ∥ 2 F = ∥W -W t ∥ 2 F + η 2 ∥∇ W L rob (W t ; S)∥ 2 F + 2η ∇ W L rob (W t ; S), W -W t .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 L rob (W; S) -L rob (W t ; S)+ HC 2 x 2 √ m ∥W -W t ∥ 2F using Lemma A.4. We finish the proof by telescoping. The weighted telescoping technique removes all of the ∥W -W t ∥ 2 F terms (t > 0) in the upper bound, thereby giving a simpler result. The term C 2 x η/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.Below we give the key lemmas for bounding the generalization error of GD with Moreau's envelope. The proof technique here is similar to that for standard adversarial training (in the previous section), except that we get to utilize the smoothness of 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.e., S and S ′ differ only in one example. For any η ≤ min{µ,√ m 8HC 2 x } ≤ √ m 2HC 2x , let W T and W ′ T be the weight matrices obtained by T iterations of gradient descent with Moreau's envelopes on datasets S and S ′ , respectively. Then, we have that∥W T -W ′ T ∥ 2 F ≤ exp 1 + 8HC 2 x ηT √ m • 16C 2 x η 2 (T + 1) 2 n 2 .Lemma 4.7 also leverages smoothness due to Moreau's envelope and yields a bound that does not involve the additional term C 2 x η/2 compared with Lemma 4.5.Lemma 4.7.(Restatement of Theorem C.6) Set k = 1 + 2HC 2 x η √ m -1 . After T iterations of Algorithm 1 with Moreau Envelope with η ≤ µ ≤ √ m 2HC 2 x and T ≤ √ m HC 2x η , we have1 T t=1 k t T t=1 k t M µ (W t ; S) ≤ ∆ oracle S .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-parameterized 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 is to extend our analysis to deep neural networks and beyond neural networks with smooth activation functions. 
 
 Appendix: Lemma A.1. Let ℓ(z) = ln(1 + e -z ) be the logistic loss function. We have |ℓ ′ (z)| ≤ min{1, ℓ(z)}.Proof of Lemma A.1.|ℓ ′ (z)| = -ℓ ′ (z) = 1 1 + e z ≤ 1;(e z > 0)ln(1 + e -z ).x 1+x ≤ ln(1 + x)Lemma A.2. For any sample z = (x, y), and any weight matrices W and W ′ , we haveℓ rob (z, W) -ℓ rob (z, W ′ ) ≤ C x ∥W -W ′ ∥ 2 • min{1, ℓ rob (z, W)}.Proof of Lemma A.2.ℓ rob (z, W) -ℓ rob (z, W ′ ) = max x∈B(x) ℓ(yf (x; W)) -max x∈B(x) ℓ(yf (x; W ′ )) ≤ max x∈B(x) (ℓ(yf (x; W)) -ℓ(yf (x; W ′ ))) ≤ max x∈B(x) |ℓ ′ (yf (x; W)) • (yf (x; W) -yf (x; W ′ ))| (ℓ is convex) = max x∈B(x) ℓ ′ (yf (x; W)) • m s=1 a s ϕ(⟨w s , x⟩) - m s=1 a s ϕ(⟨w ′ s , x⟩) ≤ max x∈B(x) ℓ ′ (yf (x; W)) • 1 √ m m s=1 | ⟨w s -w ′ s , x⟩ | (ϕ is 1-Lip) ≤ max x∈B(x) ℓ ′ (yf (x; W)) • m s=1 ⟨w s -w ′ s , x⟩ 2 (Cauchy's inequality) ≤ max x∈B(x) |ℓ ′ (yf (x; W)) • ∥W -W ′ ∥ 2 • ∥x∥ 2 | ≤C x ∥W -W ′ ∥ 2 • max x∈B(x) |ℓ ′ (yf (x; W))| ≤C x ∥W -W ′ ∥ 2 • min{1, max x∈B(x) ℓ(yf (x; W))} (Lemma A.1) =C x ∥W -W ′ ∥ 2 • min{1, ℓ rob (z, 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 t = A(S), W ′ t = A(S ′ ) be the weight returned after running algorithm A for t steps using S and S ′ , respectively. δ A (S,S ′ ) = ∥A(S) -A(S ′ )∥ F . Then if sup S≃S ′ δ A (S, S ′ ) < 1Cx , we haveEQUATIONandEQUATIONProof of Proposition A.3. Let S and S ′ differ in one example, and z ′ = S ′ \S.E S∼D n L rob (W t ) -L rob (W t ; S) = E S∪{z ′ }∼D n+1 [(ℓ rob (z ′ , W t ) -ℓ rob (z ′ , W ′ t ))] . (6)Combining Lemma A.2 and Equation ( 6) we getE S∼D n L rob (W t )-L rob (W t ; S) ≤ E S∪{z ′ }∼D n+1 [C x ∥W t -W ′ t ∥ 2 •min{1, ℓ rob (z ′ , W t )}].Based on the definition of δ A ,E S∼D n L rob (W t ) -L rob (W t ; S) ≤ C x • sup S≃S ′ δ A (S, S ′ ) • E S∪{z ′ }∼D n+1 min{1, ℓ rob (z ′ , W t )} ≤ C x • sup S≃S ′ δ A (S, S ′ ) • min{1, E S∼D n L rob (W t )}.Simplifying this inequality, we getE S∼D n L rob (W t ) ≤ E S∼D n 1 1 -C x • sup S≃S ′ δ A (S, S ′ ) L rob (W t ; S)andE S∼D n L rob (W t ) ≤ E S∼D n L rob (W t ; S) + C x • sup S≃S ′ δ A (S, S ′ ).The following lemma gives the weakly convex property of the robust loss (by considering the special case of β 1 = 0). Lemma A.4. Given any data (x, y), for model with weight W, let x(W) ∈ B(x) be an β 1 -optimal adversarial examples such that ℓ(yf(x(W), W)) ≥ max x∈B(x)ℓ(yf (x, W))-β 1 . Then for any two weight matrices W 1 , W 2 ∈ R d×m , we haveℓ((x(W 2 ), y), W 2 ) ≥ ℓ((x(W 1 ), y), W 1 ) + ∇ W ℓ((x(W 1 ), y), W 1 ), W 2 -W 1 -β 1 - HC 2 x 2 √ m ∥W 2 -W 1 ∥ 2 2 .Proof of Lemma A.4.ℓ((x(W 2 ), y), W 2 ) -ℓ((x(W 1 ), y), W 1 ) -∇ W ℓ((x(W 1 ), y), W 1 ), W 2 -W 1 + β 1 =ℓ(yf W 2 (x(W 2 ))) -ℓ(yf W 1 (x(W 1 ))) -∇ W ℓ((x(W 1 ), y), W 1 ), W 2 -W 1 + β 1 ≥ max x∈B(x) ℓ(yf W 2 (x)) -ℓ(yf W 1 (x(W 1 ))) -∇ W ℓ((x(W 1 ), y), W 1 ), W 2 -W 1 (By definition of β 1 -optimal adversarial examples) ≥ℓ(yf W 2 (x(W 1 ))) -ℓ(yf W 1 (x(W 1 ))) -∇ W ℓ((x(W 1 ), y), W 1 ), W 2 -W 1 ≥ℓ ′ (yf W 1 (x(W 1 ))) • yf W 2 (x(W 1 )) -yf W 1 (x(W 1 )) -∇ W ℓ((x(W 1 ), y), W 1 ), W 2 -W 1 (ℓ is convex) =ℓ ′ (yf W 1 (x(W 1 )))y m s=1 a s ϕ( w 2 s , x(W 1 ) ) -ϕ( w 1 s , x(W 1 ) ) -ϕ ′ ( w 1 s , x(W 1 ) ) w 2 s -w 1 s , x(W 1 ) ≥ -|ℓ ′ (yf W 1 (x(W 1 )))| m s=1 1 √ m • H 2 w 2 s -w 1 s , x(W 1 ) 2 (ϕ is H-smooth) ≥ -1 • H 2 √ m ∥(W 2 -W 1 ) T x(W 1 )∥ 2 2 (Lemma A.1) ≥ - HC 2 x 2 √ m ∥W 2 -W 1 ∥ 2 2 . (∥x(W 1 )∥ 2 ≤ C x )The following lemma tells us the gradient has a universal upper bound. Lemma A.5. For any data (x, y) and any weight matrix W,∥∇ W ℓ(yf (x; W))∥ F ≤ C x . Proof of Lemma A.5. Since ∇ W ℓ(yf (x; W)) = [ℓ ′ (yf (x; W))ya s ϕ ′ (⟨w s , x⟩)x] m s=1 , ∥∇ W ℓ(yf (x; W))∥ F = m s=1 ∥ℓ ′ (yf (x; W))ya s ϕ ′ (⟨W s , x⟩)x∥ 2 2 ≤ -C x • ℓ ′ (yf (x; W)) (|a s | = 1 √ m ,ϕ ′ ≤ 1, ∥x∥ 2 ≤ C x ) ≤ C x . (Lemma A.1)B Missing Proofs in Section 3.1Now we give the uniform argument stability upper bound.Theorem B.1. (Restatement of Theorem 3.1) Let S and S (i) only differ in the i-th data. W T and W(i)T denote the weight matrices returned after after running Algorithm GD for T iterations on S and S (i) , respectively. Then we have∥W T -W (i) T ∥ 2 F ≤ e 1+ 2HC 2 x ηT √ m 4C 2 x η 2 (T + 1) + 4C 2 x η 2 (T + 1) 2 n 2 + 4β 1 η(T + 1) .Proof of Theorem B.1. For any weight matrix W and any perturbation of the j-th data xj ∈ B(x j )(j ̸ = i), define L S \i (W; {x j } j̸ =i ) = 1 n j̸ =iℓ(y j f (x j ; W)) to be the loss of the (perturbed) data set without including the i-th data. Let xj (W t ) denote the β 1 -optimal adversarial example of x j given W t , and xj (W(i)t ) denote the β 1 -optimal adversarial example of x j given W (i)t . 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).β 1 + HC 2 x 2 √ m ∥W t -W (i) t ∥ 2 F + L S \i (W t ; {x j (W t )} j̸ =i ) ≥ 1 n j̸ =i β 1 + HC 2 x 2 √ m ∥W t -W (i) t ∥ 2 F + ℓ(y j f (x j (W t ); W t )) ≥ 1 n j̸ =i ℓ(y j f (x j (W (i) t ); W (i) t )) + ∇ W ℓ(y j f (x j (W (i) t ); W (i) t )), W t -W (i) t (Lemma A.4) =L S \i (W (i) t ; {x j (W (i) t )} j̸ =i ) + ∇ W L S \i (W (i) t ; {x j (W (i) t )} j̸ =i ), W t -W (i) t.Similarly, we getβ 1 + HC 2 x 2 √ m ∥W t -W (i) t ∥ 2 F + L S \i (W (i) t ; {x j (W (i) t )} j̸ =i ) ≥L S \i (W t ; {x j (W t )} j̸ =i ) + ∇ W L S \i (W t ; {x j (W t )} j̸ =i ), W (i) t -W t .Adding these two inequalities together, we getEQUATIONNow we start upper bounding ∥W t -W(i) t ∥ F . ∥W t+1 -W (i) t+1 ∥ 2 F =∥W t -η∇ W L S \i (W t ; {x j (W t )} j̸ =i ) - η n ∇ W ℓ(y i f (x i (W t ); W t )) -W (i) t + η∇ W L S \i (W (i) t ; {x j (W (i) t )} j̸ =i ) + η n ∇ W ℓ(y ′ i f (x ′ i (W (i) t ); W (i) t ))∥ 2 F ≤ ∥W t -η∇ W L S \i (W t ; {x j (W t )} j̸ =i ) -W (i) t + η∇ W L S \i (W (i) t ; {x j (W (i) t )} j̸ =i )∥ F + 2ηC x n 2 (Lemma A.5) ≤ T + 2 T + 1 ∥W t -η∇ W L S \i (W t ; {x j (W t )} j̸ =i ) -W (i) t + η∇ W L S \i (W (i) t ; {x j (W (i) t )} j̸ =i )∥ 2 F + (T + 2) 4η 2 C 2 x n 2 ((a + b) 2 ≤ (1 + p)a 2 + (1 + 1/p)b 2 for p > 0.) = T + 2 T + 1 ∥W t -W (i) t ∥ 2 F + T + 2 T + 1 ∥η∇ W L S \i (W t ; {x j (W t )} j̸ =i ) -η∇ W L S \i (W (i) t ; {x j (W (i) t )} j̸ =i )∥ 2 F -2η T + 2 T + 1 ∇ W L S \i (W (i) t ; {x j (W (i) t )} j̸ =i ) -∇ W L S \i (W t ; {x j (W t )} j̸ =i ), W (i) t -W t + (T + 2) 4η 2 C 2 x n 2 ≤ T + 2 T + 1 ∥W t -W (i) t ∥ 2 F + T + 2 T + 1 4η 2 C 2 x + T + 2 T + 1 (4β 1 η + 2HC 2 x √ m η∥W t -W (i) t ∥ 2 F ) + (T + 2) 4η 2 C 2x n 2 (Lemma A.5 and Equation ( 7))= T + 2 T + 1 (1 + 2HC 2 x √ m η)∥W t -W (i) t ∥ 2 F + 4η 2 C 2 x + 4β 1 η + (T + 1) 4η 2 C 2 x n 2 . Define γ = T +2 T +1 (1 + 2HC 2x √ m η), then the inequality above can be written as∥W t+1 -W (i) t+1 ∥ 2 F ≤ γ∥W t -W (i) t ∥ 2 F + T + 2 T + 1 4η 2 C 2 x + 4β 1 η + (T + 1) 4η 2 C 2 x n 2 .Dividing both sides by γ t+1 ,∥W t+1 -W (i) t+1 ∥ 2 F γ t+1 ≤ ∥W t -W (i) t ∥ 2 F γ t + T + 2 T + 1 4η 2 C 2 x + 4β 1 η + (T + 1) 4η 2 C 2 x n 2 γ t+1 .Summing up this inequality for t = 0, 1, . . . , T -1, we obtain∥W T -W (i) T ∥ 2 F ≤ γ T T -1 t=0 T + 2 T + 1 4η 2 C 2 x + 4β 1 η + (T + 1) 4η 2 C 2 x n 2 γ t+1 ≤ γ T γ -1 T + 2 T + 1 4η 2 C 2 x + 4β 1 η + (T + 1) 4η 2 C 2 x n 2 ≤ (T + 1)γ T T + 2 T + 1 4η 2 C 2 x + 4β 1 η + (T + 1) 4η 2 C 2 x n 2 = (T + 1)( T + 2 T + 1 ) T +1 (1 + 2HC 2 x √ m η) T 4η 2 C 2 x + 4β 1 η + (T + 1) 4η 2 C 2 x n 2 ≤ (T + 1)e • e 2HC 2 x ηT √ m 4η 2 C 2 x + 4β 1 η + (T + 1) 4η 2 C 2 x n 2 (1 + x ≤ e x ) = e 1+ 2HC 2 x ηT √ m 4C 2 x η 2 (T + 1) + 4C 2 x η 2 (T + 1) 2 n 2 + 4β 1 η(T + 1) .The proof of Theorem 3.1 is immediately obtained from Theorem B.1 by observing e1+ 2HC 2 x ηT √ m ≤ e 3 .Next we give an optimization guarantee. We show that when T is sufficiently large, the robust training loss can 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 havemin 0≤t≤T L rob (W t ; S) ≤ min W∈R d×m    L rob (W; S) + HC 2 x 2 √ m(1 - 1 (1+ HC 2 x η √ m ) T +1 ) ∥W -W 0 ∥ 2 F + C 2 x η 2 +β 1   .Proof of Theorem B.2. For any given W, we have∥W -W t+1 ∥ 2 F =∥W -W t + η∇ W L(W t ; {x i (W t )} n i=1 )∥ 2 F =∥W -W t ∥ 2 F + η 2 ∥∇ W L(W t ; {x i (W t )} n i=1 )∥ 2 F + 2η ⟨∇ W L(W t ; {x i (W t )} n i=1 ), W -W t ⟩ ≤∥W -W t ∥ 2 F + η 2 C 2 x + HC 2 x η √ m ∥W -W t ∥ 2 F + 2η L rob (W; S) -2ηL(W t ; {x i (W t )} n i=1 ) (Lemma A.5 and Lemma A.4) =(1 + HC 2 x η √ m )∥W -W t ∥ 2 F + η 2 C 2 x + 2η L rob (W; S) -2ηL(W t ; {x i (W t )} n i=1 ).Dividing both sides by (1 +HC 2 x η √ m ) t+1 we get ∥W -W t+1 ∥ 2 F (1 + HC 2 x η √ m ) t+1 ≤ ∥W -W t ∥ 2 F (1 + HC 2 x η √ m ) t + η 2 C 2 x (1 + HC 2 x η √ m ) t+1 + 2η( L rob (W; S) -L(W t ; {x i (W t )} n i=1 )) (1 + HC 2 x η √ m ) t+1 . (8)Taking the sum for t = 0, 1, . . . , T we get2η T t=0 L rob (W; S) (1 + HC 2 x η √ m ) t+1 + ∥W -W 0 ∥ 2 F + T t=0 η 2 C 2 x (1 + HC 2 x η √ m ) t+1 ≥2η T t=0 L(W t ; {x i (W t )} n i=1 ) (1 + HC 2 x η √ m ) t+1 (9) ≥2η T t=0 L rob (W t ; S) -β 1 (1 + HC 2 x η √ m ) t+1 ≥2η min 0≤t≤T L rob (W t ; S) • T t=0 1 (1 + HC 2 x η √ m ) t+1 -2η T t=0 β 1 (1 + HC 2 x η √ m ) t+1 .Simplifying the above inequality, we havemin 0≤t≤T L rob (W t ; S) ≤ L rob (W; S) + HC 2 x 2 √ m(1 - 1 (1+ HC 2 x η √ m ) T +1 ) ∥W -W 0 ∥ 2 F + C 2 x η 2 + β 1 . Theorem 3.2. Define α 1 (η, T ) := O(C 2 x η √ T + C 2 x ηT n + C x √ β 1 ηT ).Assume that the width of the networks satisfies m ≥ H 2 C 4x η 2 (T + 1) 2 , and α 1 (η, T ) < 1. Then, after T iterations of Algorithm 1 with GD, we have min[ 9T 10 ]≤t≤T E S∼D n ε gen (W t ) ≤ 17α 1 (η, T ) 1 -α 1 (η, T ) E S∼D n ∆ oracle S + C 2 x η 2 + β 1 ,andmin 0≤t≤T E S∼D n L rob (W t ) ≤ 1 1 -α 1 (η, T ) E S∼D n ∆ oracle S + C 2 x η 2 + β 1 .Proof of Theorem 3.2. Define t 0 := [ 9T 10 ] and k :=1 1+ HC 2 x η √ m. From equation ( 9), we have2η T t=0 L rob (W; S) (1 + HC 2 x η √ m ) t+1 + ∥W -W 0 ∥ 2 F + T t=0 η 2 C 2 x (1 + HC 2 x η √ m ) t+1 ≥2η T t=t0 L(W t ; {x i (W t )} n i=1 ) (1 + HC 2 x η √ m ) t+1 ≥2η T t=t0 L rob (W t ; S) -β 1 (1 + HC 2 x η √ m ) t+1 .Taking minimum over all weight matrices W,T t=t0 k t+1 L rob (W t ; S) -β 1 ≤ min W T t=0 k t+1 L rob (W; S) + ∥W -W 0 ∥ 2 F 2η + T t=0 ηC 2 x 2 k t+1 = T t=0 k t+1 • min W     L rob (W; S) + ∥W -W 0 ∥ 2 F 2η T t=0 k t+1 + C 2 x η 2     ≤ T t=0 k t+1 • min W L rob (W; S) + ∥W -W 0 ∥ 2 F η(T + 1) + C 2 x η 2 (m ≥ H 2 C 4 x η 2 (T + 1) 2 ) ≤ T t=0 k t+1 • ∆ oracle S + C 2 x η 2 .Taking the expectation on both sides, we getT t=t0 k t+1 min t0≤t≤T E S∼D n L rob (W t ; S) -β 1 ≤ T t=t0 k t+1 E S∼D n L rob (W t ; S) -β 1 ≤ T t=0 k t+1 • E S∼D n ∆ oracle S + C 2 x η 2 .Simplifying the equation above, we getmin t0≤t≤T E S∼D n L rob (W t ; S) ≤ β 1 + T t=0 k t+1 T t=t0 k t+1 • E S∼D n ∆ oracle S + C 2 x η 2 (10) ≤ β 1 + 9 r=0 1 k r T +1 10 • E S∼D n ∆ oracle S + C 2 x η 2 ≤ β 1 + 9 r=0 e r 10 • E S∼D n ∆ oracle S + C 2 x η 2 (m ≥ H 2 C 4 x η 2 (T + 1) 2 ) ≤ β 1 + 17 E S∼D n ∆ oracle S + C 2 x η 2 .Equation ( 4) gives us for any t ≤ T , E S∼D n ε gen (W t ) ≤ α1(η,T ) 1-α1(η,T ) E S∼D n L rob (W t ; S). Therefore,min t0≤t≤T E S∼D n ε gen (W t ) ≤ α 1 (η, T ) 1 -α 1 (η, T ) min t0≤t≤T E S∼D n L rob (W t ; S) ≤ α 1 (η, T ) 1 -α 1 (η, T ) β 1 + 17 E S∼D n ∆ oracle S + C 2 x η 2 .The proof of the second statement takes a similar approach. Following the same procedure, we can replace t 0 by 0 in equation ( 10), and getmin 0≤t≤T E S∼D n L rob (W t ; S) ≤ E S∼D n ∆ oracle S + C 2 x η 2 + β 1 .Combining with equation ( 4),min 0≤t≤T E S∼D n L rob (W t ) ≤ 1 1 -α 1 (η, T ) min 0≤t≤T E S∼D n L rob (W t ; S) ≤ 1 1 -α 1 (η, T ) E S∼D n ∆ oracle S + C 2 x η 2 + β 1 . Corollary 3.3. After T ≤ O(min{n 2 , 1 β 2 1}) iterations of Algorithm 1 with GD using a step size ofη = Θ( 1 C 2 x √T ) on a network with width m ≥ Ω(T ), for any weight matrix Wmin 0≤t≤T E S∼D n L rob (W t ) ≤ 1.1L rob (W) + O C 2 x ∥W -W 0 ∥ 2 F √ T + O 1 √ T .Proof of Corollary 3.3. Under the conditions of the corollary, we have m ≥ H 2 C 4 x η 2 (T + 1) 2 , andα 1 (η, T ) = O(C 2 x η √ T + C 2 x ηT n + C x √ β 1 ηT) can be small enough so that 1 1-α1(η,T ) ≤ 1.1. Then it is clear that this corollary is a special case of Theorem 3.2.We now extend the previous ideas to stochastic adversarial training. Lemma B.3. After T iterations of Algorithm 1 with SGD, for any weight matrix W,min 0≤t≤T (ℓ rob (z t+1 , W t ) -ℓ rob (z t+1 , W)) ≤ HC 2 x 2 √ m(1 - 1 (1+ HC 2 x η √ m ) T +1 ) ∥W -W 0 ∥ 2 F + C 2 x η 2 + β 1 .Proof of Lemma B.3. The proof proceeds similarly as Theorem B.2. .5 and Lemma A.4 )∥W -W t+1 ∥ 2 F =∥W -W t + η∇ W ℓ((x t+1 (W t ), y t+1 ), W t )∥ 2 F =∥W -W t ∥ 2 F + η 2 ∥∇ W ℓ((x t+1 (W t ), y t+1 ), W t )∥ 2 F + 2η ⟨∇ W ℓ((x t+1 (W t ), y t+1 ), W t ), W -W t ⟩ ≤∥W -W t ∥ 2 F + η 2 C 2 x + HC 2 x η √ m ∥W -W t ∥ 2 F + 2ηℓ rob (z t+1 , W) -2ηℓ((x t+1 (W t ), y t+1 ), W t ) (Lemma A≤(1 + HC 2 x η √ m )∥W -W t ∥ 2 F + η 2 C 2 x + 2ηℓ rob (z t+1 , W) -2ηℓ rob (z t+1 , W t ) + 2ηβ 1 .Dividing both sides by (1 +HC 2 x η √ m ) t+1 , we get ∥W -W t+1 ∥ 2 F (1 + HC 2 x η √ m ) t+1 ≤ ∥W -W t ∥ 2 F (1 + HC 2 x η √ m ) t + η 2 C 2 x + 2ηℓ rob (z t+1 , W) -2ηℓ rob (z t+1 , W t ) + 2ηβ 1 (1 + HC 2 x η √ m ) t+1 .Taking the sum of the above equation for t = 0, 1, . . . , T :∥W -W 0 ∥ 2 F + T t=0 η 2 C 2 x + 2ηβ 1 (1 + HC 2 x η √ m ) t+1 ≥2η T t=0 ℓ rob (z t+1 , W t ) -ℓ rob (z t+1 , W) (1 + HC 2 x η √ m ) t+1 (11) ≥2η T t=0 min 0≤t≤T (ℓ rob (z t+1 , W t ) -ℓ rob (z t+1 , W)) (1 + HC 2 x η √ m ) t+1 .Simplifying the above inequality we havemin 0≤t≤T (ℓ rob (z t+1 , W t ) -ℓ rob (z t+1 , W)) ≤ HC 2 x 2 √ m(1 - 1 (1+ HC 2 x η √ m ) T +1 ) ∥W -W 0 ∥ 2 F + C 2 x η 2 + β 1 .Theorem 3.4. After T iterations of Algorithm 1 with SGD on a network of width m ≥ H 2 C 4 x η 2 (T + 1) 2 we have that for any weight matrix W,min 0≤t≤T E {z1,...,zt}∼D t L rob (W t ) ≤ L rob (W) + ∥W -W 0 ∥ 2 F η(T + 1) + C 2 x η 2 + β 1 .Proof of Theorem 3.4. Taking the expectation over S ∼ D n on both sides of Equation ( 11), we obtain∥W -W 0 ∥ 2 F + T t=0 η 2 C 2 x + 2ηβ (1 + HC 2 x η √ m ) t+1 ≥2η T t=0 E {z1,...,zt}∼D t E zt+1∼D ℓ rob (z t+1 , W t ) -E zt+1∼D ℓ rob (z t+1 , W) (1 + HC 2 x η √ m ) t+1 =2η T t=0 E {z1,...,zt}∼D t L rob (W t ) -L rob (W) (1 + HC 2 x η √ m ) t+1 ≥2η T t=0 min 0≤t≤T E {z1,...,zt}∼D t L rob (W t ) -L rob (W) (1 + HC 2 x η √ m ) t+1 .Simplifying the above inequality, we getmin 0≤t≤T E {z1,...,zt}∼D t L rob (W t ) ≤ L rob (W) + HC 2 x 2 √ m(1 - 1 (1+ HC 2 x η √ m ) T +1 ) ∥W -W 0 ∥ 2 F + C 2 x η 2 + β 1 ≤ L rob (W) + ∥W -W 0 ∥ 2 F η(T + 1) + C 2 x η 2 + β 1 . (m ≥ H 2 C 4 x η 2 (T + 1) 2 )C Missing Proofs in Section 3.2From Lemma A.4, for any µ <√ m HC 2 x , L rob (U) + 1 2µ ∥U -W∥ 2 F is strongly convex in U.Recall that the Moreau envelope is defined asM µ (W; S) = min U L rob (U; S) + 1 2µ ∥U -W∥ 2 F .The minimizer of the optimization problem above is denoted asU µ (W; S) = argmin U L rob (U; S) + 1 2µ ∥U -W∥ 2 F .We borrow a few properties of the Moreau envelope from Xiao et al. [2024] . Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [NA] Justification: The paper does not include experiments.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as 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 it into the paper).Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Answer: [Yes] Justification: The research conducted in the paper conform with the NeurIPS Code of Ethics in every respect. The theoretical nature of the results means there are 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 circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction).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 societal impact or 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.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a 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 is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are 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 to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: The paper poses no such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 to 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 a best faith effort.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 not use 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 a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.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, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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.38th Conference on Neural Information Processing Systems (NeurIPS 2024). 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: - The bounds are in expectation and not high probability bounds.
- A large width is required for the bounds to hold.
- 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.
questions: questions: - How realistic is the assumption that there exists a robust network in the vicinity of the initialization?
- Should I be thinking of $beta_1$ as a constant? If so, how should Corollary 3.3 be interpreted?
limitations: limitations: Yes.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: questions: I have a few questions/suggestions:

* 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.”
* Lines 193-194, “This view is also consistent with several empirical studies.”: can you please elaborate on this?
* 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: limitations: The limitations of the work are thoroughly discussed.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
2. 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. 
3. 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?
4. 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.
questions: 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: limitations: This work study a speical neural network, and it is unclear whether the results can be generalized to regular neural netowrks.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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:

1) 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. 
This 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.

2) 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. 
This also seems relevant to Theorem 3.6 with $\alpha_2$

3) 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?

4) Line 509 - I don’t understand this, how is Eq (4) related to \epsilon_gen?

I will be happy to see the author’s response to these issues and will consider raising my score accordingly.
questions: 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$? 

2) 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: limitations: The authors discuss the limitations of their results.

Comments: comment: Thank you for addressing my concerns, especially regarding $\beta_1$. I have raised my score to a 6.

I wonder if requiring the $\beta_1$-optimal condition to hold everywhere can be relaxed (for example, to an averaged case), for networks where guaranteeing nearly optimal adversarial attacks is more difficult.
I apologise for my delayed response.

Thank you very much for your reply and the references provided (especially [Mianjy and Arora 2023]). I would advise you to reference this paper when introducing $\beta_1$, and to discuss its computational considerations.
Thanks for your response. My main concern is regarding the setting of an over-parameterized neural network. After reading the authors' response and the comments from other reviewers, my concerns have been addressed. I will raise my rating to a "Weak Accept" accordingly.
I thank the authors for their response.

Other reviewers (including myself) found it strange that the overparameterization depends on the learning rate and number of iterations. However, after reading the author's response I agree that this dependence is indeed the right one for stability analysis of generalization bounds, contrary to uniform convergence analysis.

To conclude, my questions are answered, and I will raise my score to 7. I think the authors should add in the final version several clarifications that were raised from the reviewer's question. I also think it would strengthen the paper to include the proof for \alpha_1  > 1.