On the Clean Generalization and Robust Overfitting in Adversarial Training from Two Theoretical Views: Representation Complexity and Training Dynamics
Authors: Binghui Li
Yuanzhi Li
Venue: ICML 2025 poster (2025)
Keywords: deep learning theory
adversarial training
clean generalization and robust overfitting
representation complexity
training dynamics
feature learning theory
Primary area: deep_learning->theory
TL;DR: We provide a theoretical understanding why clean generalization and robust overfitting both happen in adversarial training.

Abstract: Similar to surprising performance in the standard deep learning, deep nets trained by adversarial training also generalize well for unseen clean data (natural data). However, despite adversarial training can achieve low robust training error, there exists a significant robust generalization gap. We call this phenomenon the Clean Generalization and Robust Overfitting (CGRO). In this work, we study the CGRO phenomenon in adversarial training from two views: representation complexity and training dynamics. Specifically, we consider a binary classification setting with $N$ separated training data points. First, we prove that, based on the assumption that we assume there is $\operatorname{poly}(D)$-size clean classifier (where $D$ is the data dimension), ReLU net with only $O(N D)$ extra parameters is able to leverages robust memorization to achieve the CGRO, while robust classifier still requires exponential representation complexity in worst case. Next, we focus on a structured-data case to analyze training dynamics, where we train a two-layer convolutional network with $O(N D)$ width against adversarial perturbation. We then show that a three-stage phase transition occurs during learning process and the network provably converges to robust memorization regime, which thereby results in the CGRO. Besides, we also empirically verify our theoretical analysis by experiments in real-image recognition datasets.

On the Clean Generalization and Robust Overfitting in Adversarial Training from Two Theoretical Views: Representation Complexity and Training Dynamics
Binghui Li
Yuanzhi Li
Abstract
et al., 2020; Kirillov et al., 2023) and natural language pro- cess (Devlin et al., 2018; Brown et al., 2020; Ouyang et al., 2022). However, it is well-known that small but adversarial perturbations to the natural data can make well well-trained clas- sifiers confused (Biggio et al., 2013; Szegedy et al., 2013; Goodfellow et al., 2014), which potentially gives rise to reli- ability and security problems in real-world applications and promotes designing adversarial robust learning algorithms.
Similar surprising performance in the standard deep learning, deep nets trained by adversarial training also generalize well for unseen clean data (natural data). However, despite adversarial train- ing can achieve low robust training error, there exists a significant robust generalization gap. We call this phenomenon the Clean Generalization and Robust Overfitting (CGRO). In this work, we study the CGRO phenomenon in adversarial train- ing from two views: representation complexity and training dynamics. Specifically, we consider a binary classification setting with N separated training data points. First, we prove that, based on the assumption that we assume there is poly(D): size clean classifier (where D is the data dimen- sion), ReLU net with only Ö(ND) D) extra param- eters is able to leverages robust memorization to achieve the CGRO, while robust classifier still requires exponential representation complexity in worst case. Next, we focus on a structured-dait case to analyze training dynamics, where we train a two-layer convolutional network with Ö(N D) width against adversarial perturbation. We then show that three-stage phase transition occurs during learning process and the network provably converges to robust memorization regime, which thereby results in the CGRO. Besides, we also empirically verify our theoretical analysis by ex- periments real-image recognition datasets.
In practice, adversarial training methods (Goodfellow et al., 2014; Madry et al., 2017; Shafahi et al., 2019; Zhang et al., 2019; Pang et al., 2022) are widely used to improve the robustness of models by regarding perturbed data as training data. However, while these robust learning algorithms are able to achieve high robust training accuracy (Gao et al., 2019), it still leads to non-negligible robust generalization gap (Raghunathan et al., 2019), which is also called robust overfitting (Rice et al., 2020; Yu et al., 2022).
To explain this puzzling phenomenon, a series of works have attempted to provide theoretical understandings from different perspectives. Despite these aforementioned works seem to provide series of convineing evidence from the- oretical views in different settings, there still exists gap between theory and practice for at least two reasons.
First, although previous works have shown that adversarial robust generalization requires more data and larger models (Schmidt et al., 2018; Gowal al., 2021: Li et al., 2022; Bubeck & Sellke, 2023), it is unclear that what mechanism, during adversarial training process, directly causes robust overfitting. A line of work about uniform algorithmic stabil- ity (Xing et al., 2021; Xiao et al., 2022), under Lipschitzian smoothness assumptions, also suggest that robust generaliza- tion gap increases when training iteration is large. In other words, we know there is no robust generalization gap for a trivial model that only guesses labels totally randomly (e.g. deep neural networks at random initialization), which im- plies that we should take learning process into consideration to analyze robust generalization.
1. Introduction
Nowadays, deep neural networks have achieved excellent performance in variety of disciplines, especially including in computer vision (Krizhevsky et al., 2012; Dosovitskiy
'Center for Machine Learning Research. Peking University "Machine Learning Department. Carnegie Mellon University. Cor- respondence to: Binghui Li <libinghui @ pkw.edu.en>, Yuanzhi Li <yuanzhil wandre..cm..du....
Second and most importantly, while some works (Tsipras et al., 2018; Zhang et al., 2019; Hassani Javanmard, 2022) point out that achieving robustness may hurt clean test accu- racy, in most of the cases, it is observed that drop of robust
Proceedings of the nnnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

On the Clean Generalization and Robust Overfitting in Adversarial Training
2. Additional Related Work
Empirical Works on Robust Overfitting. One surpris- ing behavior of deep learning is that over-parameterized neural networks can generalize well, which is also called benign overfitting that deep models have not only the pow- erful memorization but good performance for unseen data (Zhang et al., 2017; Belkin et al., 2019). However, in con- trast to the standard (non-robust) generalization, for the robust setting, Rice et al. (2020) empirically investigates robust performance of models based on adversarial training methods, which are used to improve adversarial robustness (Szegedy et al., 2013; Madry et al., 2017), and the work Rice et al. (2020) shows that robust overfitting can be observed on multiple datasets, including CIFARI0 and ImageNet.
30
Accuracy
70
Clean
25
200
Epoch
Figure 1. The learning curves of adversarial training on CIFARIO with &or pertuurbaatinn radius ō = 8/255 (Rice et al., 2020).
Theoretical Works on Robust Overfitting, A list of works (Schmidt et al., 2018; Balaji et al., 2019; Dan et al., 2020) study the sample complexity for adversarial robustness, and their works manifest that adversarial robust generalization requires more data than the standard setting, which gives explanation of the robust generalization gap from the perspective of statistical learning theory. And another line of works (Tsipras et al., 2018; Zhang et al., 2019) propose a principle called the robustness- -cccuurcy trade-off and have theoretically proven the principle in different setting, which mainly explains the widely observed drop of robust test accu- racy due the trade-off between adversarial robustness and clean accuracy. Recently, Li et al. (2022) investigates the robust expressive ability of neural networks and shows that robust generalization requires exponentially large models.
test accuracy is much higher than drop of clean test accuracy in adversarial training (Madry et al., 2017: Schmidt et al., 2018; Raghunathan et al., 2019) (see in Figure 1, where clean test accuracy is more than 80% but robust test accu- racy only attains nearly 50%). Namely, a weak version of benign overfitting (Zhang et al., 2017), which means that overparameterized deep neural networks can both fit random data powerfully and generalize well for unseen clean data, remains after adversarial training. Therefore, it is natural to ask the following question:
What is the underlying mechanism that results in both Clean Generalization and Robust Overfitiig (CGRO) during adversarial training?
In this paper, we provide theoretical understanding of this question. Precisely, we make the following contributions:
Feature Learning Theory of Deep Learning. The fea- ture learning theory of neural networks (Allen-Zhu & Li, 2020a;b; 2022; Shen et al., 2022: Jelassi & Li, 2022; Jelassi et al., 2022; Chen et al., 2022; Chidambaram al., 2023) is proposed to study how features are learned in deep learning tasks, which provide a theoretical analysis paradigm beyond the neural tangent kernel (NTK) theory (Jacot et al., 2018; Du et al., 2018; 2019; Allen-Zht et al., 2019; Arora et al., 2019). In this work, we make a first step to understand clean generalization and robust overfitting (CGRO) phenomenon in adversarial training by analyzing feature learning process under our theoretical framework about structured data.
In Section 3, we first present some useful notations used in our work, and then provide the formal definition of the CGRO classifier (Definition 3.4).
In Section 4, we study the CGRO classifiers via the view of representation complexity. Based on some data assumptions observed in practice, we prove that achieving CGRO classifier only needs extra linear pa- rameters by leveraging robust memorization (Theorem 4.4). but robust classifier requires even exponential model capacity in worst case (Theorem 4.7).
Memorization in Adversarial Training. Dong et al. (2021); Xu et al. (2021) empirically and theoretically ex- plore the memorization effect in adversarial training for promoting a deeper understanding of model capacity, con- vergence, generalization, and especially robust overfitting of the adversarially trained models. However, differrnt from their works, the concept clean generalization and robust overfitting (CGRO) proposed in our paper focuses on both robust overfitting and high clean test accuracy, which means that there is surprisingly no clean memorization or clean overfitting.
In Section 5, under our theoretical framework of ad- versarial training, we apply a two-layer convolutional network to learn the structured data. We propose three-stage analysis technique decouple the compli- cated training dynamics of adversarial training, which shows that the network learner provably converges to the CGRO regime (Theorem 5.9).
In Section 6, we empirically demonstrate our theoreti- cal results in Section 4 and Section 5 by experiments in real-world data and synthetic data, respectively.
2

---

On the Clean Generalization and Robust Overfitting in Adversarial Training
3. Preliminaries
3.2. Problem Setup
In this section, we first introduce some useful notations that are used in this paper, and then present our problem setup.
We consider a binary classification setting, where we use X E X' C R to denote the data input and the binary label y is in y (-1,1}. Given data distribution D that is joint distribution over the supporting set X' x V, and a function ʃ X + R as the classifier, we can define the following measurements to describe the clean (robust) classification performance of the classifier f on data D.
3.1. Notations
Throughout this work, we use letters for scalars and bold letters for vectors. We will use [k]] to indicate the index The indicator of an event is defined as I[-} = 1 if the event holds and [[-)] = 0 otherwise. We use sgn(-) to denote the sign function of the real number , and we use span(u1, U1, V2 "* ,Ua) to denote the linear span of the vectors U1 122 :.. Un E R.D
set (1,2.-.. .k..
Definition 3.1. (Clean Test Error) The clean test error of the classifier f w.r.t. the data distribution D is defined as LD (J) == P(x w)~D [sgn([(X)) # v).
Definition 3.2. (Robust Test Error) Given a lp-robust radius 2 O, the robust test error of the classifier f w.r.t. the data distribution D and under lp norm is defined as CD (f) := E y>> [max xX - 11 (fsgn(f(X # v}]
For any given two sequences [A and {B,)a-or we denote A, O (B,) if there exist some absolute constant C > 0 and N1 0 such that |Anl _ C₁ [B]] for all N1. Similarly, we denote A, = 92 (B,) if there exist
In our work, we mainly focus on the cases when p = 2 and p = xc, which can be extended to the general p case as well.
C2 > 0 and N2 > 0 such that |A,| 2 C2 |Bl] for all n > N2. We say An, = O (B.) if An = O (B,) and A Ω (B,) both holds. We use (()) and ē(-) to hide logarithmic factors in these notations respectively. Moreover, we denote An = poly (B.) if An = 0 (D%) for some positive constant K, and A, = polylog (B.) if B, = poly (log( (B.)). We also say An = =B,)) if for arbitrary positive constant C33 > 0, there exists N₂ > such that AAm < B.l for all n > Ng. An event is said that it happens with high probability (or w.h.p. for short) if it happens with probability at least 1 - o(1).
In adversarial training, with access to the training dataset S = {(1, 11,1), (X2, (X N, 2N)} randomly sam- pled from the data distribution D, we aim to minimize the following robust training error to derive the robust classifier.
Definition 3.3. (Robust Training Error) Given a ro-rutttt radius 5 2 0, the robust training error of the classifier f w.r.t. training dataset S and 8 under lp norm is defined as C3 (f) =- N MM maxix - 26 (Xs)(((XX))) + y}
=
We use the notation 1P E [1, +oo to denote the lp norm in the vector space RDD For two sets A, B C RR, we can define the b distance between A and B as dist,, B) = inf X - Yllp: X E A, Y E B}. For r O, B (x, = z P RD: 1| - X p S r f is de- fined as the ep-ball with radius r centered at X.
Now, we present the concept CGRO classifier that we mainly study in this paper as the following definition.
Definition 3.4. (CGRO Classifier) Given e--robust radius 8 2 O, we say classifier f is CGRO classifier w.r.t. the data distribution D and training dataset S if it satisfies that (f( = o(1), 23 (f) = o(1) but C2 (f) = 2(1).
multi-layer neural network is function from input in R to output in RT which is defined as follows:
Remark 3.5. In the above definition of CGRO classifier, the asymptotic notations o(1) and l11)) are both defined with respective to the data dimension D, which means that CGRO classifier has a good clean test performance but a poor robust generalization at the same time.
Fw, X)= == an (W, (W (... 0ia (Wo
+Bo) + B....)+ + 11 1)+ + Bt.
and
4. Analyzing the CGRO Phenomenon from the View of Representation Complexity
Wo E R
W.E -
WL E R M
B B R -0is
In this section, we provide a theoretical understanding of the CGRO phenomenon from the view of representation complexity. First, We present the data assumption as follow.
B, E.. XERD, FW.B(X) E ERT. (X)
where the weight W Wo, WT,". Wz] and the bias B = [Bo BI.... BB]] are learnable parameters, and max ma, my. "01.-..,m--1.. m,-1,, m) and L ++1 1 are the width and depth of the neural network, respectively. We use (-) to denote the (non-ling mon--ineer) entry-wise activation function, and ReLU activation function is defined as a(.) == max(.,)) 0).
For the data distribution D and f--robust radius 5 > 0, the supporting set of the data input X' can be divided into two sets X, and X that correspond to the positive and negative classes respectively. i.c. X4 == {X E X : (X, e D,y = 1) and X == (X E X (X,
= -
3

---

On the Clean Generalization and Robust Overfitting in Adversarial Training
Assumption 4.1. (Bounded) There exists absolute con- stant R such that, with high probability over the data distribution D, it holds that the data input X E [-R,, RIP.
(Assumption 4.3) and robustly memorizes training data by the second summand, which belongs to CGRO classifiers
Back to the proof of Theorem 4.4, the key idea is to approx- imate the classifier fs proposed in Lemma 4.5 by ReLU network. Indeed, the function fs can be rewritten as
Recall the definition of CGRO classifier (Definition 3.4). W.l.o.g., we can only focus on the case X' C [R R]P.
Assumption 4.2. (Well-Separated) we assume that the sep- aration between the positive and negative classes is large than twice the robust radius, i.e. distp((', (,, X_) 28.
fs(X) = Σ (yx- Selean X))HIII - XiIlp 5
weighted sum of robust local indicators
This assumption is necessary to ensure the existence of robust classifier, and which is indeed empirically observed in real-world image classification data (Yang et al., 2020).
+ Seleam (X)
poly(D)
Assumption 4.3. (Polynomial-Size Clean Classifier Exists) we assume that there exists a clean classifier felean X' - IR represented as a ReLU network with PDly(D) parameters such that LD(Setoo)) ()) but CD (Setem) = 2(1).
Therefore, we use ReLU nets approximate the distance function di (X) := |X X, pllp in [-R, R efficiently, and we also noticed that the indicator I(-) can be approx- imated by a soft indicator represented by two ReLU neu- rons. Combined with the above results, there exists a ReLU net SCORO with poly( + Ó(N parameters such that f|fCGRO fslloo = o(1) which implies Theorem 4.4. O
In Assumption 4.3, the asymptotic notations o() and Q(1)) are defined w.r.t. the data dimension D. It means that the clean classifier with moderate size can perfectly classify the natural data but fails to classify the adversarially perturhed data, which is consistent with the common practice that well-trained neural networks are vulnerable to adversarial examples (Szegedy et al., 2013: Raghunathan et al., 2019).
Remark 4.6. Theorem 4.4 manifests that ReLU net with only Ó(N extra parameters is able to leverages robust memorization (Lemma 4.5) to achieve the CGRO regime.
However, to achieve robust generalization, higher complex- ity seems necessary. We generalize the result in Li et al. (2022) from separabee setting to Assumption 4.3.
Now, we present our main result about the upper bound of representation complexity for CGRO classifier as follow.
Theorem 4.4. (Polynomial Upper Bound for CGRO) Under Assumption 4.1, 4.2 and 4.3, with N -ammpl training dataset S ={(X,, V1), (X2, B2)...... (X } drawn from the data distribution D, there exists a CGRO classifier JCGRO X + IR that can be represented as a ReLU network with at most PDly(D) + +(ND) parameters.
Theorem 4.7. (Exponential Lower Bound for Robust Clas- sifer) Let FM be the family of function represented by ReLU networks with at most M parameters. There exists a number MD ()(xp(()) and a distribution 'D satisfying Assump- tion 4.1, 4.2 and 4.3 such that, for any classifier in the family FMD. the robust test error w.E.t. D is at least (2(1).
Proof Sketch. First, we show the existence of the CGRO classifier w.r.t the data distribution DD and training dataset S.
Proof Sketch. The main proof idea of Theorem 4.7 the linear region decomposition of ReLU nets (Montufar et al., 2014), and then apply the technique bounding the VC dimension for local region similar to Li et al. (2022). O
Lemma 4.5. For given the data distribution 'D satisfying Assumption 4.1, 4.2 and 4.3, and the randomly sampled training dataset S (1)))))..... (X2, y2)...., (NN. (NyyN) }}, we consider the following function Is X The defined
According to Assumption 4.3, Theorem 4.4 and Theorem 4.7, we obtain the following inequalities about representa- tion complexity of classifiers in different regimes.
fx( Setean (X) (1 I(X B (),
clean classification on unseen test data
Clean Classifier S CGRO Classifier < Robust Classifier. poly(D)
+ v. e B,(,,,
poly(D))((NN)
M(exp(D)
These inequalities states that while CGRO classifiers have mildly higher representation complexity than clean classifiers, adversarial robustness requires ex- cessively higher complexity, which may lead the classifier trained by adversarial training to the CGRO regime. We also empirically verify this by the experiments of adversarial training regarding different model sizes in Section 6.
Remark 4.8.
mbbust memorization training data
And it holds that the function fs is a CGRO classifier.
Due to Assumption 4.2, it is clear that we have (x,, 5) Bp (P,,,, 5) = 9 for any distinct i.j E [V]. Thus, fs per- fectly clean classifies unseen test data by the first summand
4

---

On the Clean Generalization and Robust Overfitting in Adversarial Training
5. Analyzing Dynamies of Adversarial Training on Structured Data
Rdd + R is defined
m1
P
fw(()= = Σ
Σ
o ( x(i)))
In the previous section, we show the efficiency of CGRO classifier via representation complexity. However, it is un- clear how the classifier trained by adversarial training con- verges to the CGRO regime. In this section, we will focus on a structured-dat setting to study the learning process of adversarial training. First, we introduce our structured data setting follow, and then provide fine-gr fine-grained analysis of adversarial training under our theoretical framework.
r= j=l
m Σ
Σ>
a, 0 (( (, x(1)))
where W = Ha | {a, } (w Jy=1 { } are learnable parameters, and a is the ReLU activation function defined as o(.) = (max(, ( (q 2 2).
1m
ReLU activation functions are useful to address the non- smoothness of ReLU function zero, which are widely applied in literatures of deep learning theory (Kileel et al., 2019; Allen-Zhu & Li, 2020a;b; Chen et al., 2021; Jelassi & Li, 2022; Jelassi et al., 2022). To simplify our analysis, we fix the second layer weights as at = a. = We also assume that q is odd and it holds that w, := w. = -. during optimization process. At initialization, we sample w, i.i.d from NN0,, of,,o La)... Our results can be extended to the case when q is even and w. w, are differently.
5.1. Structured Data Setting
In this section, we consider the case that data input X R.D has patch structure as follow, which is similar to a list of theoretical works about feature learning (Allen-Zhu & Li, 2020b: Chen et al.. 2021; Jelassi & Li, 2022; Jelassi et al., 2022; Kou et al., 2023; Chidambaram et al., 2023).
Definition 5.1. (Patch Data Distribution) We define a data distribution D. in which each instance consists in an input X E X P and label y E y = 1-1,1} generated by
The Role of Non-linearity. Indeed, series of recent theo- retical works (Li et al., 2019; Chen et al., 2021; Javanmard & Soltanolkotabi, 2022) show that linear model can achieve robust generalization for adversarial training under certain settings, which but fails to explain the CGRO phenomenon observed in practice. To mitigate this gap, we improve the expressive power of model by using non-linear activation that can characterize the data structure and learning process more precisely.
1. The label y is uniformly drawn from 1-1.
2. The input X = [1], X()),, where each patch X(s] E Rd and P D/ is the number of patches (we assume that D/d is an integer and P = polylog(d).
3. Meaningful Signal patch: for each instance, there ex- ists one and only one meaningful patch signal(X) E [P] satisfies X (siigna(XX) = ayw", where w" E Rd (11w0 1l2 1) is the unit meaningful signal vector and a 0 is the norm of signal.
In adversarial training, we aim to minimize the following ad- versarial training loss, which is trade-off between natural risk and robust regularization defined as follow.
4. Noisy patches: Xbi ~ N (0, (I. - w w oo)) for j E (signal)))) where of denotes the variance of noise.
w"""
Definition 5.4. (Adversarial Training Loss) For a hyperpa- rameter À > 0 and the f--robust radius 5 > 0, the adversar- ial training loss of the network fw w.r.t. the training dataset S = {X11 11),,(( (X2, B2),............. (XN, (.yyN) is defined as
Remark 5.2. The patch structure that we leverage can be viewed as simplification of real-world vision-recognition datasets. Indeed, images are divided into signal patches that are meaningful for the classification such as the whisker of a cat or the nose of a dog, and noisy patches like the uninformative background of a photo. And our patch data assumption can also be generalized to the case that there exist a set of patches that are meaningful, while analyzing the learning process will be too complicated to un-clarify our main idea that we want to present. Therefore, we focus on the single meaningful patch case in our work.
1 N
Eat Cas((W) =
Σ N 1=1
CWW:X...
natural risk
[c (w: (W:X..)) C LWW X,, [<W
max +
-
(X,,,
robust regularization
where we use L(W; XX, to denote the single-point loss with respect to fw on (X, v) and Ap (8 denotes the perturbed range of the data point X with fp-radius 5.
To learn our structured data, we use two-layer convolutional neural network (CNN) (LeCun et al., 1998; Krizhevsky et al., 2012) with non-linear activation as the learner network. Definition 5.3. (Two-layer Convolutional Network) For a given input data X E Pd, our network learner fw :
Remark 5.5. Adversarial training loss in Definition 5.4 gives a general form of adversarial training methods (Good- fellow et al., 2014; Madry et al., 2017; Zhang et al., 2019) for different values of hyperparameter X and different types of loss function L (W X.y) and perturbed range Aop (,5).
5

---

On the Clean Generalization and Robust Overfitting in Adversarial Training
Here, we use the logistic loss defined as L(W; x,,) == log (1 + exp( -xw (X))). And we apply the perturbed range defined as Ap (X, 6) ;= Bp (x, 6) n A
5.2. Main Results
First, we introduce the concept called feature learning to characterize what the model learns from training dynamics.
where A (X) C IB satisfies that
Definition 5.8. (Feature Learning) Specifically, given a certain training data-point (X.y) ~ 'D and the network learner fw, we focus on the following two types of feature learning.
span(w") j= = signal(X),
A (X) [
0
otherwise.
This perturbed range ensures that adversarial perturbations used to generate adversarial examples are always aligned with the meaningful signal vector w* during adversarial training, which exactly simplifies the optimization analysis. Definition 5.6. (Adversarial Training Algorithm) We run the standard gradient descent method to update the network parameters [W for T' iterations w.r.t. the adver- sarial training loss that can be rewritten as Z(0 (W) N 1E X)C (.. + XL [W: -.k).
True Feature Learning. We project the weight W on the meaningful signal vector to measure the correlation between the model and the true feature
172
u :
(,,, w w²)²
Spurious Feature Learning, We project the weight W on the random noise to measure the correlation between the model and the spurious feature as
1
where x.dvv(()) denotes the adversarial example generated by i-th training data X; at t-th iteration. Concretely, the ad- versarial examples (t)) and network parameters (t))
V = Σ Σ
(w., x (
are updated alternatively as
Thus, it holds that the model correctly classify the clean data in two cases. One is that the model learns the true feature and ignores the spurious features, i.e. U = 2(1) > [V]. Another is that the model doesn't 't learn the true feature but memorizes the spurious features, i.c. U o(1) and V
X (.dd).(() argmax L <(W10); , [N], [N), (X.6)
((+1) ( C
210 (W(+),,
where 77 > 0 is the learning rate.
(211 >> O. We can analyze the perturbed data similarly.
Next, make the following assumptions about hyperpa- rameters we introduced in our structured-dat setting.
Now, we give our main result about feature learning process. Theorem 5.9. Under Assumption 5.7, we run the adversar- ial training algorithm Definition 5.6 to update the weight of the network learner for T = ((poly(d)) (d)) iterations. Then, with high probability, it holds that the network leanrer
Assumption 5.7. (Choice of Hyperparameters) We assume that:
a= = ),
op = Old ))
m = ((N) poly(d),
0 polylog(d)
a=a a
1. partially learns the true feature, i.e. U(F) +(aa
Vd
Vd polylogg(
2. exactly memorizes the spurious feature, i.e. for each i i [VV, V(T) = (1)..
1 [polydd)
.1.
1
11 0. poly(d)
where Ca. Cp E (0, 1) are constants satisfying Ca + Cp > 1
where ((0) and VgS1) is defined for i-th instance (Xi,yi) and 1-th iteration as the same in Desinition 5.8. Conse- quently, the clean test error and robust training error are both smaller than o(1), but the robust test error is at least 2 - o(1), which means that Jwiry is a CGRO classifier. Remark 5.10. Theorem 5.9 states that, during adversarial training, the neural network partially learns the true feature of objective classes and exactly memorizes the spurious fea- tures depending on specific training data, which causes that the network learner is able to correctly classify clean data by partial meaningful signal (clean generalization), but fails to classify the unseen perturbed data since it leverages only data-wit random noise to memorize training adversarial examples (robust overfitting). We also conduct numerical simulation experiments to confirm our results in Section 6.
2- Discussion of Hyperparameter Choices. Actually, the choices of these hyperparameters are not unique. We make concrete choices above for the sake of calculations in our proofs. but only the relationships between them are impor- tant. Namely, since the norm of signal patch is a and the norm of noise patch w.h.p. is (a our choices ensure that meaningful signal stronger than noise. Without this assumption, other word, if the signal-to-nois ratio is very low, there even exists clean generalization, which has been theoretically shown under the similar patch-structured data setting (Cao et al., 2021; Chen et al., 2021; Frei et al., 2022). The width of network learner is OND) to achieve mildly over over- preepaarttttiiitiionn we mentioned in Theorem 4.4. The separation in Assumption 4.2 also holds due to 5 < a.
6

---

On the Clean Generalization and Robust Overfitting in Adversarial Training
Feature leaming Pronecs
Performance of Uirteren: bizes on MNNS
Partormance of Difterent Sizes on CIFAR1O
Lian Wr.
and
13
ACcouracy
AeTuvnryy
Velure
60-
Simall Halue Hemnatration Neerage iiii Hemertiziin
Tras Poulard Lourning
15
60
Model
Size
Model Size
iteration
(a)
(b)
(c)
Figure 2. (a)b): The effect of network capacity on the performance of the network. We trained the networks of varying capacity on MNIST (a) and CIFARIO (b); (c): Feature learning process of the two-layer convolutional network on the structured data.
5.3. Analysis of Learning Process
component is upper bounded as
Next, we provide a proof sketch of Theorem 5.9. To obtain a detailed analysis of learning process, we consider the following objects that can be viewed as weight-wise version of (t()) and v!!)) We define (1) and Uig as
(t) 0ō ma-06)
Σ 1=
(la- -) + -!!())
N
+ +
u = max
w
(Signal Component),
rE[m]
Lemma 5.12 shows that, after partial true feature learning, the increment of signal component is mostly dominated by the noise component 1)!"), which implies that the growth of
== max rE(m)
Wy yi X (Noise Component),
for each [m], i [N] and j E [P] signal( X,).
signal component will converge when V!!) = 2(1)-
We then propose three-stage analysis technique to decou- ple the complicated feature learning process as follows.
Phase III: After that, by the quadratic increment of noise component (Lemma 5.13), the total noise v:(") eventually attains the order 22(1), which implies the model memorizes the spurious feature (data-wise noise) in final.
Phase I: At the beginning, the signal component of lottery tickets winner (1()) increases quadratically (Lemma 5.1
Lemma 5.11. (Lower Bound of Signal Component Growth) For each r [m]] and any & 2 0, the signal component grows
Lemma 5.13. (Lower Bound of Noise Component Growth) For each i [N], r E [m] and j [P] signal (g;) and any 1 2 1, the noise component grows as
(((+1)) 2 ( + O(Ta²) (2
9-1 3 (2
(0) 1i 2.
(0)
+
nozd N
Σ (001)) (v
(1)))
where we use (b)-) to denote the negative sigmoid function functiion (2) = T+e= - as well as Lemma 5.12.5.13.
- -
Lemma 5.11 manifests that the signal component increases quadratically at initialization. Therefore, we know that, after To = θ -0- iterations, the signal component TT) attains the order 2(o=1), which implies the model learns partial true feature at this point.
The practical implication of Lemma 5.13 is two-fold. First, by the quadratic increment of noise component, we derive that, after T, = N top 3 - iterations, the to-
tal noise memorization DITT attains the order I((1), which suggests that the model is able to robustly classify adversar- ial examples by memorizing the data-wise noise. Second, combined with Lemma 5.12, the signal component (t) will maintain the order ((a ((a which immediately implies the main conclusion of Theorem 5.9. And the full detailed proof of Theorem 5.9 can be see in Appendix E.
Phase II: Once the signal component (9 attains the order 1(a-1), the growth of signal component nearly stop up- dating since that the increment of signal component is now mostly dominated by the noise component (Lemma 5.12).
Lemma 5.12. (Upper Bound of Signal Component Growth) For To (1) 1 (e-); and any E (To, T), the signal
7

---

On the Clean Generalization and Robust Overfitting in Adversarial Training
Table I. Performance of Models with Different Sizes
Dataset
MNIST
CIFARIO
Model Size Factor
1
2
8
12
16
2
5
10
Clean Test Acc
11.35
11.35
11.35
95.06
94.85
82.56
84.92
85.83
86.05
Robust Test Acc
11.35
11.35
11.35
77.96
83.43
43.39
43.74
46.25
50.08
Robust Train Ace
11.70
11.70
11.70
99.3
99.5
64.19
79.82
97.37
99.57
6. Experiments
by the adversarial training algorithm we mentioned in Defi- nition 5.6. We choose the hyperparameters that we need as: d = 100, P = 2, a = 10, op = 1,00 = 0.01, = 3, N = 20, m = p 2,8 = 10, A 0.9, 0.1,
In this section, we empirically verify our theoretical results in Section 4 and Section 5 by experiments in real-world image-recognition datasets and synthetic structured data.
100, which is a feasible one under Assumption 5.7. We char- acterize the true feature learning and noise memorization via calculating 2t(() and the smallest/argesstaaeragg of (V(") heeN We calculate the robust train and test accu- racy of the model by using the standard PGD attack.
6.1. Effeet of Different Model Sizes
Experiment Settings. For the MNIST dataset, we consider a simple convolutional network, LeNet-5 (LeCun et al., 1 1998), and study how its performance changes as we in- creases the size of network (i.e. we expand the number of convolutional filters and the size of the fully connected layer to the size number multiple of the initial, where the size num- bers are 1, 4, 8, 12, 16). The original convolutional network has a convolutional layer with 1 filters, followed by another convolutional layer with 2 filters, and fully connected hid- den layer with 32 units. Convolutional layers are followed by x 2 max-pooling layers. For the CIFARIO dataset, we apply WideRessNet334 (Zagoruyko & Komodakis, 2016) with different widen factors 2, 5, 10. We use the standared projected gradient descent (PGD) (Madry et al., 2017) to train the network by adversarial training. We choose the classical Loo -e-eruurrbation with radius 0.3 for MNIST and 8/255 for CIFARIO 10. All models are trained for 100 epoches on MNIST and 200 epoches on CIFARIO.
Table 2. Performance Synthetic Data
Train
test
Clean Acc
100.0
98.5
Robust Ace
100.0
17.5
Experiment Results, We plot the dynamics of true feature learning and noise memorization in Figure 2 (c). It is clear that a three-stage phase transitions happen during adversar- ial training, which is consistent with our theoretical analysis of learning process (Lemma 5.1 1, Lemma 12 and Lemma 5.13), and finally the model partially learns true feature but exactly memorizes all training data (Theorem 5.9). The per- formance of the model is presented in Table 2, which shows that the network converges to CGRO classifier eventually.
Experiment Results. We report our results about the perfor- mance (including the clean test accuracy, robust test accu- racy and robust training accuracy) of models with different sizes in Table and Figure 2 (a)(b). It shows that when the model size becomes larger, first the robust training loss decreases but the robust generalization gap remains large, and then when the model gets even larger, the robust gener- alization gap gradually decreases, and we also find that, in the small size case (see LeNet with the size number 1, 4, 8), adversarial training converges to trivia solution that always predicts fixed class, while it can learn an accurate clean classifier through the standard training, which corresponds to the theoretical results in Theorem 4.4 and Theorem 4.7.
7. Conclusion
In this paper, we study the CGRO phenomenon adver- sarial training and present theoretical explanations: from the perspective of representation complexity, we prove that the CGRO classifier is efficient to achieve by leveraging ro- bust memorization regarding the training data, while robust generalization requires excessively large model capacity in worst case, which may lead adversarial training to the CGRO regime; from the perspective of training dynamics, we propose a three-stage analysis technique to analyze the feature learning process of adversarial training under our structured- framework, and it shows that two-layer neu- ral network trained by adversarial training provably learns the partial true feature but memorizes the random noise from training data, which thereby causes the CGRO regime. On the empirical side, we confirm our theoretical findings above by real-world vision datasets and synthetic data simulation.
6.2. Synthetic Structured Data
Experiment Settings. Here we generate synthetic data ex- actly following Definition 5.1 and apply the two-layer con- volutional network in Definition 5.3. We train the network
8

---

On the Clean Generalization and Robust Overfitting in Adversarial Training
Acknowledgements
Biggio, B., Corona, I., Maiorca, D., Nelson, B., Sindić, N., Laskov, P., Giacinto, G., and Roli, F. Evasion attacks against machine learning at test time. In Machine Learn- ing and Knowledge Discovery in Databases: European Conference, ECMLIPKDD PKDD 2013, Prague, Czech Repub- lic, September 23-27, 2013, Proceedings, Part III 13, pp. 387-402. Springer, 2013.
Binghui Li is partially supported by the Elite Ph.D. Program in Applied Mathematics for PhD Candidates in Peking Uni- versity. We thank anonymous reviewers for their valuable suggestions.
Impact Statement
Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, J. D., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., et al. Language models are few-shot learners Advances in neural information processing systems, 33: 1877-1901, 2020.
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Bubeck, S. and Sellke, M. A universal law of robustness via isoperimetry. Journal of the ACM, 7022)11-8, 2023.
References
Allen-Zhu, Z. and Li, Y. Backward feature correction: How deep learning performs deep learning. arXiv preprint arXiv:2001.044133 2020a.
Cao, Y., Gu, Q., and Belkin, M. Risk bounds for over- parameterized maximum margin classification on sub- gaussian mixtures. Advances in Neural Information Pro- cessing Systems, 34:8407-8411 2021.
Allen-Zhu, Z. and Li, Y. Towards understanding ensem- ble, knowledge distillation and self-distillation deep learning, arXiv preprint (eXii:0012.09811 2020b.
Chen, J., Cao, Y., and Gu, Q. Benign overfitting in ad- versarially robust linear classification. arXiv preprint arXiv:2112.15250 2021.
Allen-Zhu Z. and Li, Y. Feature purification: How adversar- ial training performs robust deep learning. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). pp. 977-988. IEEE, 2022.
Chen, Z., Deng. Y., Wu, Y., Gu, Q. and Li, Y. Towards understanding mixture of experts in deep learning. arXiv preprint arXiv:2208. 02813, 2022.
Allen-Zhu, Z., Li, Y., and Song. Z. convergence theory for deep learning via pnee-parameterization. In International Conference Machine Learning, pp. 242-252. PMLR, 2019.
Chidambaram, M., Wang, X., Wu, C.,, and Ge, Provably learning diverse features in multi-view data with mid- point mixup. In International Conference Machine Learning, pp. 5563-5599, PMLR, 2023.
Dan, C., Wei, Y., and Ravikumar, P. Sharp statistical guara- tees for adversarially robust gaussian classification. In International Conference on Machine Learning, pp. 2345- 2355. PMLR, 2020.
Anthony, M., Bartlett, P. L., Bartlett, P. L., et al. Neural network learning: Theoretical foundations, volume cambridge university press Cambridge, 1999.
Arora, S., Du, S., HU, W. Li, Z., and Wang. R. Fine-grained analysis of optimization and generalization for overpa- rameterized two-layer neural networks. In International Conference on Machine Learning, pp. 322-332. PMLR, 2019.
Devlin, J., Chang, M.-W., Lee, K., and Toutanova, K. Bert: Pre-training of deep bidirectional transformers for lan- guage understanding. arXiv preprint arXiv: 1810.04805, 2018.
Dong, Y., Xu, K., Yang, X., Pang, T., Deng, 7., Su, H., and Zhu, J. Exploring memorization in adversarial training. arXiv preprint arXiv:2106.0166 2021.
Balaji, Y., Goldstein, T., and Hoffman, J. Instance adap- tive adversarial training: Improved accuracy tradeoffs in neural nets. arXiv preprint arXiv: 1tt////900.00.. 2019.
Dosovitskiy, A., Beyer, L., Kolesnikov, A., Weissenborn, D.,, Zhai, X., Unterthiner, T., Dehghani, M., Minderer, M., Heigold, G., Gelly, S., et al. An image is worth 16x16 words: Transformers for image recognition at scale. arXiv preprint arXiv:2010. 1929, 2020.
Bartlett, P. L.. Harvey, N., Liaw, C., and Mehrabian, A. Nearly-tight ve-dimension and pseudodimension bounds for piecewise linear neural networks. The Journal of Machine Learning Research, 20(1):2285-233) 2019.
Belkin, M., Hsu, D., Ma, S., and Mandal, S. Reconciling modern machine-learning practice and the classical bias- variance trade-off. Proceedings of the National Academy of Sciences, 116(32): 15844155541 2019.
Du, S., Lee, J., Li, H., Wang, L., and Zhai X. Gradient descent finds global minima of deep neural networks. In International conference on machine learning, pp. 1675- 1685. PMLR, 2019.
9

---

On the Clean Generalization and Robust Overfitting in Adversarial Training
Du, S. S., Zhai, X., Poczos, B., and Singh, A. Gradient descent provably optimizes over-parameterizeed neural networks. arXiv preprint arXiv: 2018.
Kirillov, A., Mintun, E., Ravi, N., Mao, H., Rolland, C., Gustafson, L., Xiao, 'T,, Whitehead, S., Berg, A. C., Lo, W.-Y., et al. Segment anything. arXiv preprint 3XX1:2300.026433. 2023.
Frei, S., Chatterji, N. S., and Bartlett, P. Benign overfitting without linearity: Neural network classifiers trained by gradient descent for noisy linear data. In Conference on Learning Theory, pp. 2668-1266 2668-2705 2703. PMLR, 2022.
Kou, Y., Chen, Z., Chen, Y., and Gu, Q. Benign over fitting for two-layer relu networks. arXiv preprint arXiv:2303.044 04145, 2023.
Gao, R., Cai, T., Li, H., Hsieh, C.-J,, Wang, L.,, and Lee, J. D. Convergence of adversarial training in overparametrized neural networks. Advances in Neural Information Pro- cessing Systems, 32, 2019.
Krizhevsky, A., Sutskever, I,, and Hinton, G. E. Imagenet classification with deep convolutional neural networks. Advances in neural information processing systems, 25, 2012.
Goodfellow, I. J., Shlens, J., and Szegedy, C. Explain- ing and harnessing adversarial examples, arXiv preprint arXiv:1412.6572, 2014.
LeCun, Y., Bottou, L.., Bengio, Y., and Haffner, P. Gradient- based learning applied to document recognition. Proceed- ings of the IEEE, 86(1 1 11:2278-22222 1998.
Gowal, S., Rebuffi, S.-A., Wiles, O., Stimberg, F., Calian, D. A., and Mann, T. A. Improving robustness using gen- erated data. Advances in Neural Information Processing Systems, 34:4218-4233 2021.
Li, B., Jin, J., Zhong, H., Hopcroft, E., and Wang, Why robust generalization in deep learning is dif- ficult: Perspective of expressive power. arXiv preprint arXiv:2205. 13863, 2022.
Hassani, H. and Javanmard, A. The curse of over- parametrization in adversarial training: Precise analysis of robust generalization for random features regression. arXiv preprint ar arXiv:2001.05149, 2022.
Li, Y., Fang, E. X., Xu, H., and Zhao, T. Inductive bias of gradient descent based adversarial training separable data. arXiv preprini arXiv: 1906.09936,,,,,, 2019.
Madry, A., Makelov, A., Schmidt, I.., Tsipras, D., and Vladu, A. Towards deep learning models resistant to adversarial attacks. arXiv preprint arXiv:1706.060S: 2017.
Jacot, A., Gabriel, F., and Hongler, C. Neural tangent ker- nel: Convergence and generalization in neural networks. Advances in neural information processing systems, 31, 2018.
Montufar, G. F., Pascanu, R., Cho, K., and Bengio, Y. On the number of linear regions of deep neural networks. Advances in neural information processing systems, 27, 2014.
Javanmard, A. and Soltanolkotabi, M. Precise statistical analysis of classification accuracies for adversarial train- ing. The Annals of Statistics, 50(4):2127-21566 2022.
Jelassi, S. and Li, Y. Towards understanding how momen- tum improves generalization deep learning. In Interna- tional Conference on Machine Learning, pp. 9965-10040. PMLR. 2022.
Ouyang, L., Wu, J., Jiang, X., Almeida, D., Wainwright, C., Mishkin, P., Zhang, C., Agarwal, S., Slama, K., Ray, A., al. Training language models follow instructions with human feedback. Advances in Neural Information Processing Systems, 35:27730-27748 2022.
Jelassi, S., Sander, M., and Li, Y. Vision transformers provably learn spatial structure. Advances in Neural In- formation Processing Systems, 35:37822-37888 2022.
Pang, T., Lin, M., Yang. X., Zhu, and Yan, S. Robustness and accuracy could be reconcilable by (proper) definition. In International Conference on Machine Learning, pp. 17258-17 -17877 PMLR, 2022.
Karimi, H., Nutini, J., and Schmidt, M. Linear conver- gence gradient and proximal-gradice methods under the lojyak-lojasiewwiz. condition. In Machine Learn- ing and Knowledge Discovery in Databases: European Conference, ECML PKDD 2016, Riva del Garda, Italy, September 19-23, 2016, Proceedings, Part I 16, pp. 795- 811. Springer, 2016.
Petzka, H., Kamp, M., Adilova, I.., Boley, M., and Smin- chisescu, C. Relative flatness and generalization in the interpolation regime. arXiv preprint S0tv:20001000339 2020.
Kileel, J., Trager, M., and Bruna, J. On the expressive power of deep polynomial neural networks. Advances in neural information processing systems, 32, 2019.
Raghunathan, A., Xie, S. M., Yang. F., Duchi, J. C., and Liang, P. Adversarial training can hurt generalization. arXiv preprint arXiv: 06032, 2019.
10

---

On the Clean Generalization and Robust Overfitting in Adversarial Training
Rice, L., Wong, E., and Kolter, Z. Overfitting in adversari- ally robust deep learning. In International Conference Machine Learning, pp. 8093-8104. PMLR, 2020.
Zagoruyko, S. and Komodakis, N. Wide residual networks.
arXiv preprint arXiv: /605.00/000.7 146, 2016.
Zhang, C., Bengio, S., Hardt, M., Recht, B., and Vinyals, O. Understanding deep learning requires rethinking general- ization. iclr. arXiv preprint arXiv: 16,,0530, 2017.
Schmidt, L., Santurkar, S., Tsipras, D., Talwar, K., and Madry, Adversarially robust generalization requires more data. Advances in neural information processing systems, 31, 2018.
Zhang, H., Yu, Y., Jiao, J., Xing, E., El Ghaoui, L., and Jordan, M. Theoretically principled trade-off between robustness and accuracy. International conference on machine learning, pp. 7472-7482. PMLR, 2019.
Shafahi, A., Najibi, M., Ghiasi, M. A., Xu, Z., Dickerson, J., Studer, C., Davis, L. S., Taylor, G., and Goldstein, T. Adversarial training for free! Advances in Neural Information Processing Systems, 32, 2019.
Shen, R., Bubeck, S., and Gunasekar, S. Data augmentation as feature manipulation: story of desert cows and grass cows. arXiv preprint 2xXiv:2003.01722 2022.
Silverman, W. Density estimation for statistics and data analysis. Routledge, 2018.
Szegedy, C., Zaremba, W., Sutskever, I., Bruna, J., Erhan,
D., Goodfellow, I., and Fergus, R. Intriguing properties of neural networks. arXiv preprint arXiv: 1312.6199 2013.
Tsipras, D., Santurkar, S., Engstrom, L., Turner, A., and
Madry, A. Robustness may be at odds with accuracy.
arXiv preprint arXiv:1805.1213: 2018.
Wong, E., Rice, L., and Kolter, J. Z. Fast is better than free: Revisiting adversarial training. arXiv preprint wxXiv:2011009900 2020.
Xiao, J., Fan, Y. Sun, R., Wang. J.. and Luo. Z.-Q. Stability analysis and generalization bounds of adversarial training. arXiv preprint arXiv:22 10.02990, 2022.
Xing, Y., Song, Q. and Cheng, G. the algorithmic stability of adversarial training. Advances neural infor- mation processing systems, 34:26523-26675 2021.
Xu, H., Liu, X., Wang, W., Ding, W. Wu, Z., Liu, Z., Jain, A., and Tang, J. Towards the memorization effect of neural networks in adversarial training. arXiv preprint vrXiv:2/06.044 2021.
Yang. Y.-Y.. Rashtchian, C., Zhang, H., Salakhutdinov, R. R., and Chaudhuri, K. A closer look at accuracy vs. robustness. Advances in neural information processing systems, 33:8588-8601. 2020.
Yarotsky, D. Error bounds for approximations with deep relu networks. Neural Networks, 94: 104, 2017.
Yu, C., Han, B., Shen, L., Yu, J., Gong, C., Gong, M., and Liu, T. Understanding robust overfitting adversarial training and beyond. In International Conference on Machine Learning, pp.
PMLR, 2022.

---

On the Clean Generalization and Robust Overfitting in Adversarial Training
-22
4200
550
04.
30
1/
00
70
26
1h
62
(a) MNIST: Grad
(b) MNIST: Change
(c) CIFARIO: Grad
(d) CIFARIO: Change
crsl soutarr ma0ig. MOOM!
caove.oars /2 mocss
(c) MNIST:
Train
(f) MNIST: Test
(g) CIFARIO: Train
(h) CIFARIO: Test
Figure 3. Experiment Results (fxc Perturbation Radius cn = 0.1 on MNIST, = 8/255 on CIFARIO).
A. A Additional Experiments Regarding Robust Memorization
In this section, demonstrate that adversarial training converges to similarities of the construction is of Lemma 4.5 real image datasets, which results in CGRO. In fact, we need to verify models trained by adversarial training tend to memorize data by approximating local robust indicators on training data.
Concretely, for given loss L(:;)) :). instance (X, y) and model f, we use two measurements, maximum gradient norm within the neighborhood of training data,
max [| + +),,))1,, EE S8
and maximum loss function value change
max [C(((X+ L(f(X),v)
lK 00 55
The former measures the 8-local flatness on (X, .). and the latter measures dolal adversarial robustness on (X, which both describe the key information of loss landscape over input.
Experiment Settings. In numerical experiments, we mainly focus on two common real-image datasets, MNIST and CIFARIO. During adversarial training, we use cyclical learning rates and mixed precision technique (Wong et al., 2020). For the MNIST dataset, we use LeNet architecture and train total 20 epochs. For the CIFAR10 dataset, we use a Resnet architecture and train total 15 epochs.
Numerical Results. First, apply the adversarial training method to train models by fixed perturbation radius eg. and then we compute empirical average of maximum gradient norm and maximum loss change on training data within different perturbation radius e. We can see numerical results in Figure 3 (a~dd,, and it shows that loss landscape has flatness within the training radius, but is very sharp outside, which practically demonstrates our conjecture on real image datasets.
Learning Process. We also focus on the dynamics of loss landscape over input during the adversarial learning process. Thus, we compute empirical average of maximum gradient norm within different perturbation radius and in different training epochs. The numerical results are plotted in Figure 3 (e~h). Both on MNIST and CIFAR10, with epochs increasing, it is observed that the training curve descents within training perturbation radius, which implies models learn the local robust indicators to robustly memorize training data. However, the test curve of CIFAR10 ascents within training radius instead, which is consistent with our theoretical analysis in Section 5.
Robust Generalization Bound. Moreover, we prove a robust generalization bound based on flattess loss landscape (see in Appendix B). We show that, while adversarial training achieves local flatness by robust memorization, the model lacks global flatness, which causes robust overfitting.
12

---

On the Clean Generalization and Robust Overfitting in Adversarial Training
Adhesanii, Thaming Preewes
Afcocaiial Towning
0.30
0.38
415-
018
10
12
0303
0001
anto
ncer 0085
4307
2363
Idbaa Sencneoeccaaal Ca
(a)
(b)
Figure 4. Left: Local and Global Flatness During Adversarial Training on CIFARIO; Right: The Relation Between Robust Generalization Gap and Global Flatness on CIFARIO.
B. Robust Generalization Bound Based on Global Flatness
In this section, we prove a novel robust generalization bound that mainly depends on global flatness of loss landscape. We consider lp 1b-ade adversarial robustness with perturbation radius and we use Lecean. Lunv (f) and Late (J) to denote the clean test risk, the adversarial test risk and the adversarial empirical risk w.r.t. the model f. respectively. We also assume + for the next results.
Theorem B.1. (Robust Generalization Bound) Let D be the underlying distribution with a smooth density function, and N sample training dataset S {(X1; v1), (X2, (2.9))..... (XN: (N,. i.id drawn from D. Then, with high prohability, holds that,
Caiv()) S (f) + N nta E E(XW)~
max ( 21 Elll S8
global flatness
This generalization bound shows that robust generalization gap can be dominated by global flatness of loss landscape. And we also have the lower bound of robust generalization gap stated as follow. Proposition B.2. Let D be the underlying distribution with smooth density function, then have
Lado( Letean(f) 2 (x,)D ||| ((((X).
Theorem B.1 and Proposition B.2 manifest that robust generalization gap is very related to global flatness. However, although adversarial training achieves good local flatness by robust memorization on training data, the model lacks global flatness, which leads to robust overfitting.
This point is also verified by numerical experiment on CIFARIO (see results in Figure 4). First, global flatness grows much faster than local flatness in practice. Second, with global flatness increasing during training process, it causes an increase of robust generalization gap.
13

---

On the Clean Generalization and Robust Overfitting in Adversarial Training
C. Preliminary Lemmas
First, we present a technique called Tensor Power Method proposed by Allen-Zhu & Li (2020a;b). Lemma C.1. Let {
Jt=o 0 be positive sequence defined by the following recursions
x(+11) 2 20) + m (2(0))
x(1+1) 20 + M (z(1)²
where 200) > is the initialization and m, M > Let > such that z(0) S v. Then, the time to such that 2, 2 v for all t 2 to is:
8M
[og (1/20)
to m² +
log(2)
Lemma C.2. Let S1= be positive sequence defined by the following recursion
11=0
2 2 (0) A (z(1)) C
z(0 < (0) A Σ ==0 (z(o1)2 +C
where A, C > and 2(0) > 0 is the initialization. Assume that C $ z /2. Let u > such that 20) < v. Then, the time t such that 2()) 2 u upper bounded as:
log (1/=0)
21
to 8
+
log(2)
(2(0))
Lemma C.3. Let T 2 O. Let (zd)ST be a non-negative sequence that satisfies the recursion: ((+1) S <x(0) A (2(1))
for O. Then, it is bounded at a time > T as
10 S
A(I A(--T)
Then, provide probability inequality proved by Jelassi & Li (2022).
Lemma C.4. Let {0, 1, be vectors in Id such that there exist a unit norm vector æ that satisfies Dm (0r, 20) 21.
Then, for Ei..... EN ~ N (0.)²Ia) ii.dd we have:
p
O(d)
P
(rr
Ei)
2 (0²)
21
21/d
Next, we introduce some concepts about learning theory.
Definition C.5 (growth function), Let F be class of functions from X' Rd to {-1, +1}. For any integer 2 define the growth function of F to be
(m))
max ssism
((f(1)) ... (f
FH
In particular, if f(f())) .... (fe ff 2"h then (I1, (21,22, "..",,m .m) is said to be shattered by F. Definition C.6 Slapnik-Chervoneee dimension). Let F be class of functions from X RD {-1, The VC- dimension of F, denoted by VC-dim(F), is defined the largest integer m 2 0 such that IIx(m) = 2m For real-value function class H. we define VC-dim(HL == VC-dim(sgn(74).
The following result gives a nearly-tight upper bound on the VC-dimension of neural networks. Lemma C.7. (Bartlett et al., 2019) Consider ReLU network with T. layers and W total parameters. Let F be the of (real-valued) functions computed by this network. Then we have VC-dim F) = O lo)(
The growth function connected to the VC-dimension via the following lemma; see e.g. Anthony et al. (1999).
Lemma C.8. Suppose that VC-dim(F) = k, then 11m (F) < Ek (TT). In particular, we have 11m (FF S (em/k)* for all
m +
14

---

On the Clean Generalization and Robust Overfitting in Adversarial Training
D. Feature Learning
In this section, we provide full introduction to feature learning, which is widely applied theoretical works (Allen-Zhu Li, 2020a;b; 2022; Shen et al., 2022; Jelassi & Li, 2022; Jelassi et al., 2022; Chen et al., 2022) explore what and how neural networks learn in different tasks. In this work, we first leverage feature learning theory to explain CGRO phenomenon in adversarial training. Specifically, for an arbitrary clean training data-point (X, y) D and given model fw, we focus
True Feature Learning. We project the weight W on the meaningful signal vector to measure the correlation between the model and the true feature
U Σ (,,, w'
Spurious Feature Learning. We project the weight W on the random noise to measure the correlation between the model and the spurious feature as
Σ
(w,, x(I)"
jE (X)ggnall)))
We then calculate the model's classification correctness certain clean data point
v//w()) = y Wr. X [signal( x)]} +
Σ
Σ
(,r X [))
jE(P)\signal(X
y w,, axyw" 8 +
Σ
Σ
(w,, X ()))
jE(P (signal(()))
V
Thus, the model correctly classify the data if and only if a 2 0, which holds in at least two cases. Indeed, one is that the model learns the true feature and ignores the spurious features, where /f {1) >> VV. Another is that the model doesn't learn the true feature but memorizes the spurious features, where [u]] (1) and V S2(1) > 0.
Therefore, this analysis tells us that the model will generalize well for unseen data if the model learns true feature learning, But the model will overfit training data if the model only memorizes spurious features since the data-specific random noises are independent for distinct instances, which means that, with high probability, holds that = o(1) for unseen data (X,y). y).
We also calculate the model's classification correctness on perturbed data point, where attack proposed in definition 5.6 to generate adversarial example as
X ady [)] = { a(1 -")y"",""""" j= Xbiii E [p] (iignal(X)
We then derive the correctness as
Wr, X adv [signal( ())) (xsnal(()))_a0 yfw (fwwXuuy udy = Σ
+ M
Σ
(w, (xa
je PP) ([(iignaa(()) (X)
Wrr a: (1 -'yy"" "
Σ
(w,, x(11.
signaall))
(1-)))u
Thus, the model correctly classify the perturbed data if and only if (1-11))++++2 0, which implies that We can analyze the perturbed data similarly.
15

---

On the Clean Generalization and Robust Overfitting in Adversarial Training
E. Proof for Section 5
In this section, we present the full proof for Section 5. To simplify our proof, we only focus on the case when y = 3, and can be easily extended the general case when q 2 2. And we need the re-defined notation as the following.
For r E [m]. i E [N] and j E [P] signal(X x)) we define 5 and u vij.r as
3 Signal Component. 4,² : w wn thus (((0) = =ErEmm (4 )
Noise Component, ( f.j.r == yi (w) x.(i)). thus - D = [te(Plaagnaaix)) (v(() (1s..)
First, we give detailed proofs of Lemma 5.11, Lemma 5.12 and Lemma 5.13. Then, we prove Theorem 5.9 base on the above lemmas.
We prove our main results using an induction. More specifically, we make the following assumptions for each iteration t T.
Hypothesis E.1. Throughout the learning process using the adversarial training update for t < T, we maintain that:
(Uniform Bound for Signal Component) For each r E [m]], we assume (1) zŌ(a
(Uniform Bound for Noise Component) For each r E [m], E [N] and E [P] signal(X;) we assume ( 2 1 O())
In what follows, assume these induction hypotheses for & < T to prove main results. We then prove these hypotheses for iteration t = T' in Lemma E.11.
Now, we first give proof details about Lemma 5.11.
Theorem E.2. (Restatement of Lemma 5.11) For each r E [mm] and any / 2 0, the signal component grows
o ((+1) 2 u + O(ja²)
(14)) (nf))²² vi a
(e)
uk
km(m)
where we use vb()) to denote the negative sigmoid function (/x)) = Ite= as well as Lemma 5. 5.12,5.13.
functionn
Proof. First, calculate the gradient of adversarial loss with respect to (r [m]) as
(1- (1-A)yı with (t) xxbii)²
Ays (w)) (1) ..
[1])
Vw, CantaanWiiii (Wit))
X1
X.auy [s]
N
+ exp (Hifwie (X,))
1 exp (Bhfwco) (Xqut)))
j=l
N
(t)
2
X)a + da - -7) 3): (wiffrro (a (x w
N
2 ((1- (1
Σ
Xe x
Then, we project the gradient descent algorithm equation W(+1) (+)) V/V w Eutte (W(!)) on the signal vector w
16

---

On the Clean Generalization and Robust Overfitting in Adversarial Training
We derive the following result due X
1 wt for [P] signal(X,).
2 N
37j
u((+1) = u +
(())
((1 (1-N)a (yi (X.)) + - (() (x)
N
3njx (1 - 2)
N
2 u +
(1())
(wiswo) (X:))
N
2 u + O(Ta9) (u.0)
a
Σ A
)
ukk
( (a²Inetm) "4k (1))) ) which is obtained due
where derive last inequality by using w'yes/orre (X:)) 0(1) Hypothesis E.I.
Consequently, we have the following result that shows the order of maximum signal component.
Lemma E.3. During adversarial training, with high probability, it holds that, after To Ô (nrdoo) iterations, for all
E To, T). we have [m up i(aa'
Proof. From the proof of Theorem E.2, we know that
N
3n N
2
4 (1+1)
(1) =
Σ
(1-
((t.)wooo + Aa (1 ( (x.")))
i=1
By applying Hypothesis E.I, we can simplify the above equation to the following inequalities.
(1+1)
(1)
(t) (1)
2
ur
S ur +
ur
(++1)
2 ur
(1)
+ B 11
where A and B are respectively defined as:
= Õ(1) ((1 2)a (1)-11))))
-
B = (1
At initialization, since choose the weights wi (0) N (0, Lي know the initial signal components ut (0) are i..d. zero-mean Gaussian random variables, which implies that the probability that at least one of the ur is non-negative is 1 - = 10--- (1).
Thus, with high probability, there exists an initial signal component u 2 By using Tensor Power Method (Lemma C.1) and setting v = -1), we have the threshold iteration To as
- log E (DOa))
6(1) ioul
6(1) ((1 A)a + (835)
(1 2)a3
log(2)
Next, we prove Lemma 5.12 to give an upper bound of signal components" growth.
17

---

On the Clean Generalization and Robust Overfitting in Adversarial Training
Theorem E.4. (Restatement of Lemma 5.12) For To = θ bounded as
1
and any t E [To.T] the signal component is upper
s0(a +0010000 (1a0(1 7)33
[-1 N
max u r
Σ
(1-1))
Σ
(u( + V(.1)
To
kE [m/]
Proof. First, we analyze the upper bound of derivative generated by clean data. By following the proof of Theorem E.2, we know that, for each [m]]
max ( + 3na A) [m]]
2
max u (1+1) [m[m]
max u0)
Σ
rE(m]
1
2 max ()) + [(maa rE[m]
Wyifwro (x.)).
N
(1) where we obtain the first inequality by the definition of maxye[m] ur mamxaaeemm u7 ((a=1) derived by Lemma E.3 in the last inequality. Thus, we then have
(t+1)
and we use max+e[m) ur 2
N v (oifwoo(ii)) S aa
max ((+1) max ul!))
N
(r/mm]
rE[m]
(++1)
(1) By the non-decreasing property of up we have
Now, we focus on maxyg[m]
max+e[m] Wr
max u re [m]
(t+1) max u
(+1) - (00)
rE(m
rE/m]
< (1- ()n))(na)
3
Σ (c()))
Σ
(au(())
+ 110
(n0211
(1- 7)3
Σ
N
(urfwoo
N
rE(m)
rE(mn
$ (1 - A)0(na²)0)
(u(e))
+ +
N N
7)33
(yilwooo (Xxal))),
rE fm)
where we (6-) denote the logistics function defined as d(2) logg1 + exp(-2)) and we derive the last incquality by Hypothesis E. Then, we know
N
(u(o))
Σ Vunfwo (1 (1-)))(( x)ō(aJá
a Σ
re(m)
(a211- - 7)3
N Σ
+ 10
N
18

---

On the Clean Generalization and Robust Overfitting in Adversarial Training
Then, derive the following result by Hypothesis E.1 and the above inequality.
max Uy rE [mm]
11+1)
2 max ( + rE(m]
3n
max u rE(m)
2
Σ (a1 (11 ((.
+ Aa 8 (1 7)² (yi (wo: (x)))))
< max u + @mpa) re[m]
1 A
Σ ((nifiit (Xi)) +
[na(1 - 7) -
Σ
(wrfwil (x:a)))
N
N
S max 4 + (1 2)0(na²)) j rE[m]
a Σ
(u()))
+
7)
byh (x.
N
rE(m]
(1 A)Ō(na²)
(1-
7)3
S max u(t) rE(m]
byrtsoo (Xpll))
(t) 3)
N
1 + exp
a Ere(m)
(1 A)Ō(na²)
naa
7) N
N
S max u rE[m]
+
+ +
byilwoo (X.ai)).
1 + exp (2(1))
By summing up iteration 8 = To...... 1 - 1, we have the following result as
(1- x)0(na²)
(1-2)3
max u0 max (((bb)
+
Murfwo (X.
rE[m]
rE ml]
+ exp (5((1)
N
To
To
s 5 +
naa (1 7)
# a² aa - 7)²
(1))) + v1.0)
==1a
kE(m)
Therefore, derive the conclusion of Theorem E.4.
Next, we prove the following theorem about the update of noise components.
Lemma E.5. For each r [m]) i [N] and j E [P] signal(X.)) any iterationto, t such that to < S T, with high probability, it holds that
(2) 1ii
(ta) vis
+
no²dd
Σ
[-1
300)
(5) 2 (u/
2ō ( >naa -7)3 (1-)
Σ
Σ
N
(yif (X.
N
N
+O(PoZa-1Va)
where we use the notation (100) denote (1 -)((ssSwoo))))) Xebli (X.dr))
Proof. To obtain Lemma E.5, we prove the following stronger result by induction w.r.t. iteration L.
t- tg
(to) C.g.r Vighr
- 0
Σ 3500)
< c (1 Xan + aod
Σ
(P-IVa)-
N
a=ta
9=0
(I)
>yna"(1 -7)33 (Ana
t- b-g N
+ +
Σ Σ 1i---Va - (e $=
N
0=0
19

---

On the Clean Generalization and Robust Overfitting in Adversarial Training
First, we project the training update on noise patch x;(i] to verify the above inequality when / L0 + 1 as
U,j Uijir
(1o+1)
(ta)
-6
1102d
((t))
(5) (1di
2
5 n
Σ
(ito) (to) 2 abbiT)
N
beésignal Xx)
N
A N
I SinPo
+ + Σ 1=1
(X:i.))
N
s á (1+ Xan + a²dd.
where apply 1-> EE= (yrfwioo (X.)) I a )) (maxre(m) (1+1)) N
max ultt)) 0n1 -3) and
Up
Ein (wrffwoo (X."))) )) & (1)) to derive the last inequality.
Next, we assume that the stronger result holds for iteration t, and then we prove the result for iteration & ++ as follow.
n0 2d
t-1
no²d
t-1
((++1) (to)
-
(v13).)
J(tt
a.bbr))
begt bessignal( (Xa)
N (WiSwao (X.)) (17
N
+
O1jPo²
Σ
Wyiswar (x."))).
Then, we bound the first term in the right of the above inequality by our induction hypothesis for t, and we can derive
((+1) (fo)
Vigg
-
no?d d
< á'(Po' Vo) (1 Aam +
a o2d
Σ (P-IVd)
a=to
Xna (1 - 733
t-to-1 t-g N
+
() -8 (y
N
+ O(Pooa
a Xan dd) + +
d N
Σ
By summing up the terms, proved the stronger result for t + 1.
Finally, we simplify the form of stronger result by using Σ PP- (P-1 Vd) 9 == (1- P/Va) O(1), which implies the conclusion of Lemma E.5.
Now, we prove Lemma 5.13 based on Lemma E.5 as follow.
Theorem E.6. (Restatement of Lemma 5.13) For each E [N], r e [m] and j E [P] signal(X, and any t 2 1, the signal component grows as
no²d
(0) Vij.rr
(0)
+
(1geer) O(Po2a
N
#=0
Proof. By applying the one-side inequality of Lemma E.5, we have
2d
(-1
(1pe - 7)3
71)
f-1 N
(0) (ta)
θ
2 -
(X.
N
N
s=to
e=ta
1=1
O(Poza-
Thus, we obtain Theorem E.6 by using δ
Anye (1-)) N
Er ΣN (ln (x."d))) S OO -77) 1
Ô(Poña VVd) and (((0) (1(()) derived by Hypothesis E.
20

---

On the Clean Generalization and Robust Overfitting in Adversarial Training Consequently, derive the upper bound of total noise components follow.
( N
Lemma E.7. During adversarial training, with high probability, holds that, after Ti O
iterations, for all
n
e [T and each i [N]. we have Vi(a O().
Proof. By applying Lemma E.5 as the same in the proof of Theorem E.6, we know that
(tt) Ui
11 1
v
(15i)) S
(.)
) SO(Po'a-VVa)
which implies that, for any iteration t & T, we have
(0)
2 v 1j
(0)
+
+
A
15. C
(0)
Vij.
(0)
A 0=
(8)
+0
where A, C are constants defined
θ (no²d)
=
C= O(Po
N
At initialization, since we choose the weights wr ~ N L and X,II ~ N (0. I'I,), we know the initial noise (0)
components Vaj.r are i..dd zero-mean Gaussian random variables, which implies that, with high probability, there exists at least one index r' such that V..jr 2 S By using Tensor Power Method (Lemma C.2) and setting v -(1)
we have the threshold iteration Ti as
Ō(L)
log
21N
8N
T
θ (n u/.f.r
θ (1ord)
Uiijerr
(0)
log (2)
Therefore, we get Tj θ
N 2 ) and we use v!!) = =rr((m) EjEe(p/
)² to derive V(9) 2 Ộ((1.. ((1,)))
Indeed, our aimed loss function Laty (W) is non-convex due to the non-linearity of our CNN model fww To analyze the convergence of gradient algorithm, we need to prove the following condition that is used to show non-convexly global convergence (Karimi al., 2016; Li et al., 2019).
Lemma E.8. (Lojasiewicz Inequality for Non-convex Optimization) During adversarial training, with high probability, iterations, for all E [Ti, we have
holds that, after Ti θ (
Vw W Ludr (W()) ((1) (wll).
Proof. To prove Lojasiewicz Inequality, we first recall the gradient w.r.t. Wy as
V Eadinanni (Wit))
3 N
()a"(()sw: + da (111-))30) (ur (x.tin) w (1ge))
(.10) )² ((1- ()(((ufwooo( + Ax(unfirros X,bil
#=1 (x))
21

---

On the Clean Generalization and Robust Overfitting in Adversarial Training
Then, project the gradient the signal direction and total noise, respectively. For the signal component, we have
V Ean (Wrio))
( "n..aav (WV())), 200) 2
))
(2(2))))
2 2(11)
(1 1)a² (11-))a² (uf²)
()a((((())
v a² Σ
AE [m)
For the total noise component, we have
N
Σ sisgnal( x.) X:(i]
2
V w. Ludv Lade((
Ei=1
N
Σ Exsignal(Xx)) X:(5]
2
N
(1(0) (1.j.r ((1 - () + Aeb(ur (x,")))) X,1i),
1=1 splaignal(X.)
Σ byssignall X..) X
Σ Ea=1
Edpsiigaal X.)
Xa [6]
3
N
2
a=
N
hessignal x.))
Xa(b)
(isier (1 A)b(us/woo (X:))
N
N [xtsignal(X..) Xalb]
i=1 (
2
2
3
(100 2 (155r) Ap(usSwro(X;3 )X,15l,,
Ex=1
Eorsignal(x.. Xa(b)
Σ
N
EN
Xa Xal6] Eopsiggna(x.) x..)
{
For the first term, with high probability, it holds that
Σx E Enstsignal( (x.) Xa(b]
Σ
(Vig.T)
2 (1 (Xx
>>> E Eopsignal x.) Xa
(
(1
(1) (1 A)
N
1=1 (x)))
Ev Σ Engtrionnl
where we use that
X,bil
is a sub-Gaussian random variable of parameter a, which implies
E Eopengmai
[0
w.h.p. (
X.b...
Σx=1 Enggetennti x.) (b(b) >>
< Ō()).
Eepeignat( X.10
For the second term, with high probability, it holds that
N
ΣN Σ instiggall x.) Xalb]
3
Σ
(o12.) Xehunfwro (X."" X1,,),
N
>0= Σ Orssignal Xx.) X,
N
(X))
(11)
X 1ill
(ur)))) Xep(erfwrr (x.atr)
N
>>> Enysiggaat x.) Xalbl
j+signal(X..)
((VV))
Σ
N
1= X.)
22

---

On the Clean Generalization and Robust Overfitting in Adversarial Training
where we w.h.p.
for (i. * (i',5")
Laz1 Zxpriggatt x,10
Lazt Xx Xa(bil1
Now, combine the above bounds, we derive
Vw, Cad (HV(()))
V w. Eadv (Wr()) -0-200))))
2
1=1
Eim Σ Hissignal x.) X
N
V u., Cadv (Wr(t)),
+
Σ Ejtsigna(Xx, X; [i]
2
1 m
(1 - A)a
m
(u(t) v
a
(1 (1)))
ke(m!
O(ovd)
N
+
E
(1j.r)
Aeb Swiss (X.a)r)
N
r=1
j x.)
2
(1)((1 A)
(1) Uiiger) )²
(1 N)s(Usffcco (Xi))
N
r= i=1 j+signal(X.)
2 Σ Φ (2!tt) )
N
2 (((1)
(1 (1=2)0 2)0
a Σ
(u((0)
3
+
N
rE[ml
2 (() (Late (wrrt))²
Consequently, we derive the following sub-linear convergence result by applying Lojasiewicz Inequality. Lemma E.9. (Sub-linear Convergence for Adversarial Training) During adversarial training, with high probability, it holds iterations, the adversarial training loss sub- linearly converges to zero as
that, after Ti θ (ppoooo
Ō(1) Eadr (wll)== v nit +1
Proof. Due the smoothness of loss function Ladv (W) and learning rate r) Ö(1), we have
Enty (wrltt)) I Euty (wrlt) - V Eatv (wrlo){ 5 Entty (wi(t) (2()) (Luer (wr:)))
2
where we use Lojasiewicz Inequality in the last inequality. Then, by applying Tensor Power Method (Lemma C.3), we obtain the sub-linear convergence rate.
Now, we present the following result to bound the derivative generated by training-adversariaa examples.
Lemma E. During adversarial training, with high probability, it holds that, after Ti = θ
N
iterations, we
have EN (yulfwor 1
Proof. First, we bound the total derivative during iteration s = Ti,..., By applying the conclusion of Lemma E.5, we
23

---

On the Clean Generalization and Robust Overfitting in Adversarial Training
have
N
1-1 N ΣΣ
(X:
((00)
N
== 1=1
Aaa (1 د)
P
+0
Σ
Σ
(X.
+0
(navd))
No2d
s=21
Due to Ō --(
< 1, we know
0td
Σ
((1)
Σ Σ
((0) (8)
(nawa
P
N
i=1
Õ(1)
(-1 N
Σ Σ
(y)10)
+
N
navd
i=1
0 Σ
Endy (wrl))
+0
P
navd
T=
0i) Σ
Õ(1)
+Õ
P
11(1 Ti +1)
naaa
==1
Thus, obtain / E. E (WySSwo) (x.e)) < ((T
Consequently, have the following lemma that verifies Hypothesis E. for T.
Lemma E.11. During adversarial training, with high probability, it holds that, for any S T, we have max+e(m) ur S ((a and [o < f(r each E [m], [N], E [P] signal(X,).
Proof. Combined with Theorem E.4 and Lemma E010, we can derive max,e(mi ut (T) < Ō(a
By applying Lemma E.5, we have
y00d
1-1
2
Iu Vija
+
(8)
N
==1o
(1 -3)3
N
+ +
4
Wyiffwoo O(PPP V O(1)
N
Ō(1) + ( + 0(a 7) 05))))))))
Therefore, our Hypothesis E.1 holds for iteration é = T.
Finally, we prove main result follow.
Theorem E.12. (Restatement of Theorem 5.9) Under Assumption 5.7, we run the adversarial training algorithm update the weight of the simplified CNN model for T ((poly(d)) iterations. Then, with high probability, it holds that the CNN model
1. partially learns the true feature, i.e. (T) (aaa 3);
2. exactly memorizes the feature, i.e. for each E [N], ((T) =(1).
where (t() and vi is defined for 3-th instance (X,,y.) and t t-th iteration as the same in (I)(1). Consequently, the clean test error and robust training error are both smaller than ()1), but the robust test error least 2 o(1).
24

---

On the Clean Generalization and Robust Overfitting in Adversarial Training
Proof. First, by applying Lemma E.3, Lemma E.7 and Lemma E.11, know for any i [N]
u =
Σ
(
Oa 3)
re(m]
Σ
Σ
0 (igher
(T) 3
= 9())
rE(m] (X,,
Then, since adversarial loss sub-linearly converges to zero i.e. Lud (W(T) 1 robust training error is also at most o(1).
n(T I 2O 5( ) = o(1), the
0(1)
To analyze test errors, we decompose w. (T) into wi (T) (T)
pe "0 + +BtT) for each r E [m], where B.²²) (span(ww))
Due to DI7T) (1), we know ||3!! 1| (1))
For the clean test error, we have
P(X.)) (uswen) (X) =PpppD
3
+ y
Σ
(ufTx(ii) x(i) <0
r=1
r=1
$ P(x
Σ
m
(
3
2 2Q(1)
jE ssggall())
$2(1)
S exp
00
poly(a)) o(1)
o6 Dm
(T
11
where we use the fact that Em [jE(P|signna(( (
is a sub-Gaussian random variable with parameter
0² (P- | 2.
For the robust test error, we use A(:) to denote attack in Definition 5.6, and then we derive
P(Xw>D
min [lElla58
y/war (X + + <
2 P (A(I) <0)
m
3
m
(2) (1p),xiii) 3
=P(xww/D
U
(1 71-
<
jE (P)) (iigna((X))
2 (X
1
m
Σ
(B x(i)) 2 20((1 ((1-)))))
2
1
O(d)
-o(1,
2
2d
(signaa)))l)
where we use Lemma C.4 in the last inequality.
25

---

On the Clean Generalization and Robust Overfitting in Adversarial Training
F. Proof for Section 4
We prove Theorem 4.4 by using ReLU network to approximate fs proposed in Section
Theorem F.1. (Restatement of Theorem 4.4) Under Assumption 4.1, 4.2 and 4.3, with N Nasample training dataset (X..
S 1, (X2.3)...... ...,..... (XN,yN) yN'} drawn the data distribution D, there exists a CGRO classifier that can be represented as ReLU network with poly(D) (ND) parameters, which means that, under the distribution 'D and dataset 8, the network achieves zero clean test and robust training errors but its robust test error is at least S11).
Proof. First, we give the following useful results about function approximation by ReLU nets.
Lemma F22 (Yarotsky, 2017) The function f(z) = x² on the segment [0, 1] can be approximated with any error e >> 0 by a ReLU network having the depth and the number of weights and computation units (llog(//c).
Lemma F.3. (Yarotsky. 2017) Let 0. < < b and 2 1 be given. There exists a function x B]² - B²] computed by ReLU network with O (log² Bc) parameters such that
(xx, v) xy S
sup [0,
and (xx v) = 0 xy = 0.
Σ ( (1) x.O by using Lemma F22 there exists a function Φ1 computed by a ReLU network with O ( log (Ei D)) parameters such that [
Since for VX E [0, 1] the distanne function | 1
- | Xolla| SE.
Return to our main proof back, indeed, functions computed by ReLU networks are piecewise linear but the indicator functions not continuous, we need to relax the indicator such that [x)((2)) 1 for I 8 + co. [so(()) 0 for 2 R - deg and Two is linear in (ō + co. R dea) by using only two ReLU neurons, where en is sufficient small for approximation.
Now, we notice that the constructed function fs can be re-written as
N
fs(X) = Setean (1-1(X E B2,,, + Σ will x E B2(X,,0)
felean ()) + >> (y: 1=1
falean (X)) - X; 11 8
Combined with Lemma F.2, Lemma F.3 and the relaxed indicator, we know that there exists a ReLU net h with at most Poly(D)+ + Ō(ND) parameters such that h fsl = o(1) for all input X E [0, 1)". Thus, is easy to check that h belongs to CGRO classifiers.
Next, we prove Theorem 4.7 by using the VC-dimension theory.
Theorem F.4. (Restatement of Theorem 4.7) Let FM be the family of function represented by ReLU networks with most M parameters. There exists number MD M(exp(()) and distribution 'D satisfying Assumption 4.1, 4.2 and 4.3 such that, for any classifier in the family FM under the distribution D, the robust test error is at least (2(1).
Proof. Now, notice that ReLU networks are piece- wise linear functions. Montufar et al. (2014) study the number of local linear regions, which provides the following result.
Proposition F.5. The maximal number of linear regions of the functions computed by any ReLU network with a total of n hidden units is bounded from above by 2n.
Thus, for a given clean classifier felemn represented by a ReLU net with poly(D) parameters, we know there exists at least a local region V such that decision boundary of felean is linear hyperplane in V. And we assume that the hyperplane is (D) =
26

---

On the Clean Generalization and Robust Overfitting in Adversarial Training
Then, let V" be the projection of V on the decision boundary of Selean- and P be an 26-packing of V'. Since the packing number P(V", || I| 26) 2 C(V", || lla, 26) exp()(D)), where C( |l, 6) is the d-covering number of set O For any 60 (0, 1), we can consider the construction
S = {
1 n.
+ 60 o(x)) E
2
where á P + (-1, +1} is an arbitrary mapping. It's easy | S vI ej are in V" so that by choosing co sufficiently small, we can guarantee that |S n V exp([(D))) For convenience we just replace SΦ with Sq n V from now on.
that all points in S with first D - components satisfying
Let A4 ( V xD)) 2). B As- It's easy to see that for arbitrary o, the construction is linear-separable and satisfies 26 se-seaarab.lity.
Assume that for any choices of o the induced sets Ag and B can always be robustly classified with (O()), pu)-acurracy by a ReLU network with at most M parameters. Then, we can construct an enveloping network Fe with M hidden layers, M neurons per layer and at most M/ parameters such that any network with size < .M can be embedded into this envelope network. As result, Fg is capable of (0(5), po)-rouutlly classify any sets Ag. Bg induced by arbitrary choices of cb We use Rg to denote the subset of 5 As U B& satisfying R&l = (1 14) |Sal exp(I( such that R.g can be (())-robustly classified.
Next, we estimate the lower and upper bounds for the cardinal number of the vector set
R = {(f(()))))))) E FMOd.
Let denote [P], then we have
R = ((2) FMoh
where p = { L2 J.
On one hand, we know that for any E 1,", there exists o R such that du(u, 1) S an, where d=(:-)) denotes the Hamming distance, then we have
2"
R N N({[1,1)", 2
=i=0
On the other hand, by applying Lemma C.8, we have
2
R < 11 (n)
where is the VC-dimension of FM In fact, we can derive 1 = [(n) then we have Σ/zo (t) < (en/t)' and Den (?) s (e/u)an, ( so
when μ is a small constant. Assume that / < n - 1,
2
(e/u) pm S | S (en/1)².
We define a function (z)) as h(x)= (e/x)* then we derive
#
1/n
2 <
=/4gh(/m))
1/n
When y is sufficient small, l/n C(u) that is constant only depending on μ4, which implies / 2(n). Finally, by using Lemma C.7 and n = [P] exp()(D))), we know MD exp(S(D)).
27

---

On the Clean Generalization and Robust Overfitting in Adversarial Training
G. Proof for Section B
Theorem G.1. (Restatement of Theorem B.1) Let D be the underlying distribution with a smooth density function, and N- sample training dataset S {(x1: V1), (22 y...... (XN. i.idd drawn from D. Then, with high probability, holds that,
Cadv S Eado(f) + N 0iz ((XW))
+
max Ellp S6
global flatness
Proof. Indeed, we notice the following loss decomposition.
Ladv (J) Luav (J) (fccean()) - (ntt(()) + (Catr Letean Lcceen()))
To bound the first term, by applying A to denote kernel density estimation (KDE) proposed in Petzka al. (2020), then derive
Letean (f) (s) (xxx))
max EE
([
S [ - N
E A [C(f(x;+++++ + 2),
==1
J pD (x)
ps (s(X)C(((XX)
- Eslps (PD(X)-Eslee)
-X)X))) (x))
(1)
/ (Es(ps(X)) x
ps -
(11)
where pD pp(() (X) the density function of the distribution D, and ps (X is the KDE of point X. With the smoothness of density function of D and Silverman (2018), know that (1) O(8²).
For (II), by using Chebychef inequality and Silverman (2018), with probability 1 - A, we have
(IT) = = - +
On the other hand, by Taylor expansion, we know
(f Lelemn (f) < (())
V Vx + +)),))ll 511p556
max
Combined with the bounds for (I) and (IT), we can derive Theorem B.I.
28


Reviews:
[{"review_id": "HLFuX12AOt", "reviewer": "Reviewer_sZef", "summary": "The authors explained the common Clean Generalization and Robust Overfitting (CGRO) phenomenon in adversarial training from a theoretical analysis. The authors first proved that a two-layer ReLU net will achieve CGRO with small extra parameters, and the ideal robust classifier requires exponential parameters. Then, as the main contribution, the authors proved that the network has a three-stage phase during training. The network learns some “true features” in the first stage, and the noise component increases in the second stage; at last, the network learns the data-specific noise, which results in CGRO.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for the encouraging and insightful feedback, and for highlighting the strength of our theoretical contributions and the clarity of our writing. We are very glad to address the questions and suggestions raised by the reviewer, which we believe will help further refine our work. Below are our responses to the questions raised by the reviewer.\n\n>**[Q1]** the intervals in Table 1 and the figure need modification.\n\n**[A1]** We thank the reviewer for the valuable suggestion. \n- For MNIST, we have added experiments with model size factors of 9, 10, and 11. The experimental results are presented in the following table.\n\n| Model Size Factor | 1     | 2     | 8     | 9    | 10    | 11    | 12    | 16   |\n|-------------------|-------|-------|-------|-------|-------|-------|-------|-------|\n| **Clean Test Acc**| 11.35 | 11.35 | 11.35 | 11.35 | 11.35 | 95.24 | 95.06 | 94.85 |\n| **Robust Test Acc**| 11.35 | 11.35 | 11.35 | 11.35 | 11.35 | 73.22 | 77.96 | 83.43 |\n| **Robust Train Acc**| 11.70 | 11.70 | 11.70 | 11.70  | 11.70  | 95.50 | 99.30 | 99.50 |\n\nWe can observe that when the model size factor is less than or equal to 11, the adversarially trained LeNet model fails to learn non-trivial classifiers. However, when the model size factor is greater than or equal to 12, there is a sudden improvement in model performance. This phenomenon has also been mentioned in previous empirical work [1], and studying the theoretical mechanism behind it is an interesting future direction.\n\n- For CIFAR10, we did not observe the robust test accuracy spike phenomenon (we used the WideResNet architecture here, and a model size factor smaller than 1 results in an inability to achieve a clean classifier, even with clean training). We speculate that this is due to the inherent complexity of the CIFAR10 dataset, which is much higher than that of the MNIST dataset. We also acknowledge that theoretically analyzing the occurrence or absence of the spike phenomenon is an interesting and important direction for future research.\n\n\n>**[Q2]** It is not clear about the smallest/largest/average noise memorization in figure 2(c).\n\n**[A2]** We would like to clarify that, for our two-layer neural network and a given data point $(\\boldsymbol{X}, y)$, we define the noise memorization as $\\mathcal{V} := \\sum_{r=1}^{m}\\sum_{j \\in [P] \\setminus \\operatorname{signal}(\\boldsymbol{X})} \\langle \\boldsymbol{w}_r^{(T)}, y \\boldsymbol{X}[j] \\rangle^q$, which is mentioned in lines 291-296 (right page). Then, for the $N$-size training dataset, we obtain a total of $N$ noise memorizations $\\mathcal{V}_1, \\mathcal{V}_2, \\dots, \\mathcal{V}_N$. We define the smallest, largest, and average values of these as the smallest, largest, and average noise memorization, respectively. We thank the reviewer for pointing this out, and we will include the relevant explanation in the revision of our paper.\n\n>**[Q3,4]** From Figure 2(c) and Phase III analysis, it seems the true feature learning would not decrease during the training, so how do the authors explain the general phenomenon that robust test accuracy will decrease after some point in the training phase? Similarly, why does the true feature learning not suffer catastrophic forgetting since the “signal component is now mostly dominated by the noise component” as claimed in the paper?\n\n**[A3,4]** As the reviewer mentioned, we would like to clarify that during training, the true feature learning does not decrease. However, its increment is dominated by the noise component (as seen in Lemma 5.12). Thus, our theory cannot directly explain the observation that robust test accuracy decreases after some point in the training phase and that true feature learning suffers catastrophic forgetting, which implies a gap between theory and observation. We believe that theoretically explaining this gap is an interesting and important future direction.\n\n**Reference**\n\n[1] Madry, A., Makelov, A., Schmidt, L., Tsipras, D., & Vladu, A. (2017). Towards deep learning models resistant to adversarial attacks. arXiv preprint arXiv:1706.06083.", "claims_and_evidence": "Yes, all the claims are supported by the theoretical analysis.", "methods_and_evaluation_criteria": "Yes, the evaluation criteria make sense to me for all the experiments.", "theoretical_claims": "Yes, I have checked all the theoretical claims and their proofs, including the Representation Complexity part and Learning Process part. I didn't find any significant errors in it, but I can't guarantee that it's completely correct.", "experimental_designs_or_analyses": "Yes, I have checked all the experimental designs and analyses. All the experiments seem fine, however, there are some concerns:\n(1) In Table 1 and Figure 2, the interval of model sizes seems to be less fully reflective of model robustness, e.g., there are no results for the acc surge process in MNIST and no surge phenomenon in CIFAR10.\n(2) It is not clear about the smallest/largest/average noise memorization.", "relation_to_broader_scientific_literature": "The main results of this paper focus on explaining the CGRO Phenomenon from the Representation Complexity and Learning Process on Structured Data. There are several prior works that figure out the robust generalization requires more data and larger models, which may somewhat diminish the first contribution of the paper. However, the analysis of the Learning Process seems interesting and inspiring, which may provide new insights for future research.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "The quality of the paper is good, presenting a reasonable motivation and methodology. The paper is generally well-written and easy to follow. The paper theoretically explains the GCOR and the learning process in adversarial learning, which makes the paper inspiring. \n\nHowever, these are some concerns. For example, the intervals do not seem convincing, and there is confusion about the smallest/largest/average noise memorization. On the other hand, even though the authors explain the learning process, they do not give the solution for the GCOR which may slightly diminish the contribution.", "other_comments_or_suggestions": "No", "questions_for_authors": "As mentioned above, I have some concerns about this paper:\n(1) the intervals in Table 1 and the figure need modification. There are no results between 8 and 12 in MNIST, which makes readers wonder how exactly accuracy changed during this surge. On CIFAR-10, the robust test accuracy didn't spike with robust training accuracy as it did in MNIST. Could the authors increase the intervals (e.g., less than 1 and greater than 10) or provide an explanation?\n\n(2) It is not clear about the smallest/largest/average noise memorization in figure 2(c).\n\n(3) From Figure 2(c) and Phase III analysis, it seems the true feature learning would not decrease during the training, so how do the authors explain the general phenomenon that robust test accuracy will decrease after some point in the training phase?\n\n(4) similarly, why the true feature learning would not suffer catastrophic forgetting since the “signal component is now mostly dominated by the noise component” as claimed in paper?", "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": "z9SVNJoxDI", "reviewer": "Reviewer_wBzb", "summary": "This study focuses on the phenomenon of clean generalization and adversarial overfitting. The authors theoretically formulate this phenomenon and analyze it from the perspective of representation complexity and learning dynamics. First, they derive the complexity required to learn CGRO models and robust models, showing that robust models require more complexity than CGRO models. Second, the authors study the learning dynamics to discover three stages in training.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for the thoughtful feedback. We are very glad to address the questions and suggestions raised by the reviewer, which we believe will help further refine our work. Below are our responses to the questions and suggestions raised by the reviewer.\n\n**Response to claims and evidences:**\n>See our response to **[Q3-1]**.\n\n**Response to methods and evaluation criteria:**\n>**[Q1]** As the reviewer mentioned, we would like to clarify that the main theorem relies on Assumption 4.3, where we apply a teacher-student learning framework. This framework assumes the existence of a ground-truth neural network of moderate size that can achieve perfect clean classification. This teacher-student setup is widely used in deep learning theory (e.g., [1][2][3]). We also emphasize that the polynomial-size assumption arises from empirical observations, where mildly over-parameterized networks achieve good clean classification performance but poor robust classification performance (e.g., [4][5][6]), rather than from a rigorous mathematical proof. Furthermore, providing a lower bound for the representation complexity required to achieve robust generalization under Assumption 4.3 is highly non-trivial due to the complex decision boundary induced by the ground-truth polynomial-size network. To address this, we build on the technique from [7] to establish an exponential lower bound in the worst case.\n\n>**[Q2]**  We sincerely thank the reviewer for the valuable and thoughtful suggestion. Indeed, if the data distribution $\\mathcal{D}$ satisfies that the covering number of the supporting set is exponential in the data input dimension $D$, we can rigorously prove the third condition, i.e., $L_{\\mathcal{D}}^{p,\\delta}(f) = \\Omega(1)$, which complete the proof of Lemma 4.5. We will include this in the revision of our paper. \n\n>**[Q3-1]** We would like to clarify that, from the perspective of expressive power, our analysis demonstrates that CGRO classifiers can be achieved with only polynomial representation complexity (Theorem 4.4), whereas an exactly robust classifier necessitates representation complexity that is exponential in the worst case (Theorem 4.7). Given the simplicity bias inherent in neural network training (e.g., [8][9][10][11]), this fundamental complexity gap may explain the implicit bias observed in adversarial training.\n\n>**[Q3-2]** We would like to clarify that our paper focuses on the underlying mechanism behind CGRO, and explaining the effectiveness of robustness improvement methods (such as [12]) is beyond the scope of our paper.\n\n>**[Q4]** We simplify real-world vision-recognition datasets by dividing images into meaningful patches (e.g., a cat's whisker or a dog's nose) and noisy ones (e.g., an uninformative background). While this can be generalized to scenarios with multiple meaningful patches, analyzing such cases would complicate our explanation. Hence, we focus on a single meaningful patch. Defining true versus spurious feature learning in real data and models is difficult, making phase transition verification challenging, as seen in feature learning theory papers. We believe validating this on real data is a promising direction for future research.\n\n**Response to experimental designs and analyses:**\n> We would like to emphasize that our exponentially large lower bound for representation complexity holds only in the worst case. On the other hand, the computational cost of training neural networks with exponentially large input dimensions is unacceptable in practice. Therefore, as an alternative, we conducted experiments on MNIST and CIFAR10 by appropriately scaling up the network, and the phenomena observed are consistent with our theory.\n\n**Response to essential references not discussed:**\n> We thank the reviewer for pointing out the related work [17]. We will include it in the related work section in the revised version of our paper.\n\n**Response to other comments and suggestions:**\n> We thank the reviewer for the valuable suggestion. Indeed, when the training data is sufficiently large, i.e., when $N = \\Omega(exp(D))$ (at which point Lemma 4.5 no longer holds, as seen in our response to **[Q2]**), the upper bound of the CGRO classifier's complexity matches the lower bound of the robust classifier's complexity. This also indicates that adversarial robustness requires more data. We will include this part in the revision of our paper.\n\n**Reference (Arxiv Index)**\n\n[1] 1811.04918\n\n[2] 2001.04413\n\n[3] 2102.06701\n\n[4] 1708.06131\n\n[5] 1312.6199\n\n[6] 1412.6572\n\n[7] 2205.13863\n\n[8] 1901.06523\n\n[9] 2201.07395\n\n[10] 2110.13905\n\n[11] 2410.10322\n\n[12] 2004.05884\n\n[13] 2012.09816\n\n[14] 2210.13512\n\n[15] 2208.02813\n\n[16] 2303.08433\n\n[17] 2209.14105", "claims_and_evidence": "Remark 4.8 states that “which may lead the classifier trained by adversarial training to the CGRO regime.” However, the theoretical analysis is not agnostic to adversarial training and it cannot explain the effects of adversarial training.", "methods_and_evaluation_criteria": "- The main result of this paper, Theorem 4.4, is based on Assumption 4.3, but Assumption 4.3 is not proven or justified. Especially, the restriction of $poly(D)$ requires justification.\n\n- Why is the function in Lemma 4.5 a CGRO model? While a CGRO classifier needs to satisfy three conditions in Definition 3.4, the function $f_S$ in Lemma 4.5 is not proven to satisfy the third one, i.e., $L^{p,\\delta}_D (f) = \\Omega (1)$.\n\n- The analysis from the perspective of representation complexity fails to explain the mechanism of adversarial training. Moreover, many methods (e.g., (Wu et al., 2020)) have been proposed to improve the adversarial generalization of DNNs, and this study fails to explain the effectiveness of these studies.\n\nWu et al., Adversarial Weight Perturbation Helps Robust Generalization, in NeurIPS 2020.\n\n\n- The analysis from the perspective of learning dynamics is limited to a specific dataset and two-layer network with a pre-defined parameter structure. Its scalability to real datasets and complex architectures is questioned.", "theoretical_claims": "Assumption 4.3 is not justified.\n\nWhether the function in Lemma 4.5 belongs to CGRO classifiers needs clarification.", "experimental_designs_or_analyses": "I’m concerned about how experiments in Table 1 and Figure 2 support the theoretical analysis. I expect a comparison between models with only linear complexity and models with exponential complexity.", "relation_to_broader_scientific_literature": "This study provides two perspectives to understand the prior discovery of the adversarial overfitting phenomenon.", "essential_references_not_discussed": "Liu et al., (2023) also studied the relationship between network architecture (weight sparsity) and adversarial generalization. \n\nLiu et al., Exploring the Relationship between Architectural Design and Adversarially Robust Generalization, in CVPR 2023.", "other_strengths_and_weaknesses": "No.", "other_comments_or_suggestions": "Previous studies have discovered that adversarial robust generalization requires more data. It would be better to use the theoretical analysis in this study to explain this discovery, since the theoretical analysis here is also related to the dataset size.", "questions_for_authors": "No.", "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": "V8Y5WL10M4", "reviewer": "Reviewer_WvLq", "summary": "This paper investigates the Clean Generalization and Robust Overfitting (CGRO) problem – defined as “robust overfitting and high clean test accuracy” (without clean overfitting/memorisation) – from perspectives of representation complexity and training dynamics. On the one hand, they show that under data assumptions of boundedness, well-separation, clean classifiers require $poly(D)$ complexity (assumption 4.3), CRGO classifiers require $poly(D) + \\tilde{O}(ND)$, and adversarially robust classifiers require $exp(D)$. On the other hand, they demonstrate a three stage phase transition during learning, to understand how a convolutional classifier (on structured data) converges to robust memorisation and CRGO under adversarial training.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for the positive feedback! We greatly appreciate the recognition of the novelty and significance of our contribution to the topic of adversarial robustness in the deep learning community, as well as the positive remarks on the clarity of our writing. We are very glad to address the questions and suggestions raised by the reviewer, which we believe will help further refine our work. Below are our responses to the questions and suggestions raised by the reviewer.\n\n>**[Q1]** How would practitioners efficiently verify that a given task satisfies assumptions 4.1-4.3 in order to leverage insights from claim 1 to construct their model and vary its capacity?\n\n**[A1]** For Assumption 4.1, due to the normalization (or centralization) of the data, we assume that Assumption 4.1 holds for general deep learning problems. For Assumption 4.2, we compute the $\\ell_{p}$ distance between data from different classes in the training or test set, as done in the empirical work [1], to validate Assumption 4.2. For Assumption 4.3, we train a suitably-sized ReLU neural network (with network width equal to $\\operatorname{poly}(D)$ and network depth $L$ as a constant, resulting in a total parameter count of $\\operatorname{poly}(D)$) as a clean classifier. We then test its clean test accuracy and robust test accuracy to verify whether Assumption 4.3 holds. We thank the reviewer for this insightful suggestion, and we will add the above discussion in the revision of our paper.\n\n>**[Q2]** Can claim 2 (eventual CRGO and the three stage phase transition) be demonstrated for a real, existing dataset without special construction?\n\n\n**[A2]**  We would like to clarify that the patch structure we use can be seen as a simplification of real-world vision-recognition datasets. Specifically, images are divided into signal patches that are meaningful for classification, such as the whisker of a cat or the nose of a dog, and noisy patches, like the uninformative background of a photo. Our assumption about patch data can also be generalized to situations where there exists a set of meaningful patches. However, analyzing the learning process in such cases would complicate our explanation and obscure the main idea we wish to present. Therefore, we focus on the case of a single meaningful patch in our work. We would like to point out that, for real data and real models, it is difficult to rigorously define true feature learning and spurious feature learning. As a result, verifying the phase transition in real-world experiments is challenging, and this issue is commonly encountered in feature learning theory papers, such as [2][3][4][5]. We also believe that validating this on real data is an important and promising direction for future research.\n\n>**[Q3]** Have the authors considered experimentally comparing against a standardly trained model baseline in Section 6.2 on the synthetically constructed dataset? This would serve as a relevant control to understand unique dynamics of adversarial training.\n\n**[A3]** We thank the reviewer for the valuable suggestion. We have added a standardly trained model baseline on the synthetically constructed dataset.  The experiment results are presented as follows:\n|                      | Train | test |\n|----------------------|-------|------|\n| Clean Acc            | 100.0 | 100.0 |\n| Robust Acc           | \\ | 1.5 |\nWe will include this experiment in the revision of our paper.\n\n**Reference**\n\n[1] Yang, Y. Y., Rashtchian, C., Zhang, H., Salakhutdinov, R. R., & Chaudhuri, K. (2020). A closer look at accuracy vs. robustness. Advances in neural information processing systems, 33, 8588-8601.\n\n[2] Allen-Zhu, Z. and Li, Y. (2023b). Towards understanding ensemble, knowledge distillation and self-distillation in deep learning. In The Eleventh International Conference on Learning Representations.\n\n[3] Chidambaram, M., Wang, X., Wu, C. and Ge, R. (2023). Provably learning diverse features in multi view data with midpoint mixup. In International Conference on Machine Learning. PMLR.\n\n[4] Chen, Z., Deng, Y., Wu, Y., Gu, Q., & Li, Y. (2022). Towards understanding mixture of experts in deep learning. arXiv preprint arXiv:2208.02813.\n\n[5] Zou, D., Cao, Y., Li, Y., & Gu, Q. (2023, July). The benefits of mixup for feature learning. In International Conference on Machine Learning (pp. 43423-43479). PMLR.", "claims_and_evidence": "The first claim compares the representation complexity for clean vs. CRGO vs. robust classifiers: Clean($poly(D)$) $\\lesssim$ CRGO($poly(D) + \\tilde{O}(ND)$)  $\\ll$ Robust($\\Omega(exp(D))$). This claim relies on assumptions of bounded input, well-separated data for classification, and the existence of a ReLU clean classifier with $poly(D)$ complexity. I find these assumptions empirically reasonable for the experimental setups of CIFAR and MNIST, though I am unfamiliar with results on polynomial-sized ReLU networks for approximating clean classifiers.   \n   \nThe second claim concerns the dynamics of adversarial training, that the network will partially learn the true feature for well-separated classes and will exactly memorise the spurious features of specific training data. They argue that the former demonstrates clean generalisation while the latter is a case of robust overfitting (since the data-wise random noise is used for memorisation). Besides the training regime, the authors additionally connect claim 2 to CRGO in the test data regime, where the clean test error and robust training error are both small while the robust test error is significant. From what I understand, this analysis appears sound.", "methods_and_evaluation_criteria": "This is a predominantly theoretical work, where theoretical insights are cross-checked in practice. Experiments are conducted on the image modality (boundedness), on simple vision datasets of CIFAR-10 and MNIST (well-separated), with sufficiently expressive convolutional models of WideResNet-34 and LeNet-5, under standard $l_\\infty$ PGD attacks. The clean and robust accuracies are recorded for training and unseen testing examples.", "theoretical_claims": "Referencing the above section on \"claims and evidence\", I examined whether the assumptions of claim 1 (4.1-4.3) are reasonable in practice; followed the proof sketch of claims 1 (section 4) and 2 (section 5) in detail; did a summary review of the claims' full proofs, comprising supplement sections D, E, F.", "experimental_designs_or_analyses": "To verify the complexity of CRGO and robust classifiers, the authors vary the model size and record the resultant changes in robust training loss and robust generalization gap. To examine the dynamics under adversarial training, they additionally test on synthetic, structured data, replicating the three-stage phase transition and phenomenon of CRGO. The experiments are well-aligned with the theory and provide numerical support.", "relation_to_broader_scientific_literature": "This work contrasts the representation complexity of clean vs. CRGO vs. robust classifiers, which enriches our understanding of the properties and demands of adversarial robustness. Furthermore, this work discusses the learning dynamics of networks under adversarial training, outlining the processes of partial true feature learning (which results in clean generalisation) and spurious memorisation of noisy, data-wise components (which results in robust overfitting). Together, this analysis sheds light on why CRGO eventually occurs, which is a standing problem in trying to understand adversarial training.", "essential_references_not_discussed": "Not to my knowledge.", "other_strengths_and_weaknesses": "1. **Strength (Soundness) -** This paper analyses CRGO in adversarial training from refreshing perspectives of representation complexity and training dynamics analysis. In my judgement, the analysis is technically sound and contributes to better understanding of the challenges (exponential complexity) and processes (signal and noise) underlying adversarially robust classification.   \n2. **Weakness (Significance) -** This paper considers adversarial training and robust classifiers under highly structured data settings. It may be challenging to determine for an arbitrary data modality, dataset and task, whether the assumptions hold and whether the theoretical insights apply.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "1. How would practitioners efficiently verify that a given task satisfies assumptions 4.1-4.3 in order to leverage insights from claim 1 to construct their model and vary its capacity?  \n2. Can claim 2 (eventual CRGO and the three stage phase transition) be demonstrated for a real, existing dataset without special construction?   \n3. Have the authors considered experimentally comparing against a standardly trained model baseline in Section 6.2 on the synthetically constructed dataset? This would serve as a relevant control to understand unique dynamics of adversarial training.", "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": "fcyEG2Ug0U", "reviewer": "Reviewer_3vVc", "summary": "I happen to review this paper again. This paper has almost no changes when compared to previous version. \n\nThis paper studies the Clean Generalization and Robust Overfitting (CGRO) of neural networks under adversarial training. It studies the CGRO from two views: representation complexity and training dynamics. A CGRO Classifier is defined as: clean test error is small, robust training error is small, but robust test error is large.\n\nRepresentation complexity (Section 4): the main result shows that clean classifier requires $ploy(D)$ parameters, and CGRO requires $ploy(D + ND)$ parameters, while robust classifer requires $\\exp(D)$ parameters. It shows the separation between clean/robust classifiers from approximation theory, i.e.,\n\nClean Classifier ($poly(D)$) ≲ CGRO Classifier($poly(D)+ND$) ≪ Robust Classifier (Ω($\\exp(D)$))\n\nIn training dynamics, the results show that adversarial training makes the neural network conducts partial true feature learning and exactly memorizes spurious features. That means, after adversarial training, the network correctly classifies unseen clean data with high probability in Theorem E.12; but fails to classify the adversarial examples generated from unseen clean data with probability at least 1/2.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for the positive support and valuable feedback! We greatly appreciate the insightful review, and the recognition of highlighting the significance of our contribution and solidity of our theory, as well as the clarity of our writing. We are very glad to address the questions and suggestions raised by the reviewer, which we believe will help further refine our work. Below are our responses to the questions and suggestions raised by the reviewer.\n\n>**[C1]** However, the results heavily depend on Assumption 4.3 rather than proven, as mentioned by two reviewers as well. Though it may be observed from empirical results, it requires a careful theoretical demonstration.\n\n**[A1]** We sincerely thank the reviewer for the valuable and thoughtful suggestion. As the reviewer mentioned, we would like to clarify that the main theorem relies on Assumption 4.3, where we apply a teacher-student learning framework. This framework assumes the existence of a ground-truth neural network of moderate size that can achieve perfect clean classification. This teacher-student setup is widely used in deep learning theory (e.g., [1][2][3]).\n\nWe also emphasize that the polynomial-size assumption arises from empirical observations, where mildly over-parameterized networks achieve good clean classification performance but poor robust classification performance (e.g., [4][5][6]), rather than from a rigorous mathematical proof. Furthermore, providing a lower bound for the representation complexity required to achieve robust generalization under Assumption 4.3 is highly non-trivial due to the complex decision boundary induced by the ground-truth polynomial-size network. To address this, we build on the technique from [7] to establish an exponential lower bound in the worst case.\n\n>**[C2]** Regarding the training dynamics, the statement is incomplete as the comparison to classifiers under standard training is missing. In this case, it is unclear to us whether a model trained via standard (non-adversarial) training would only learn the true feature and ignore the spurious feature?\n\n**[A2]** We sincerely thank the reviewer for the insightful suggestion. As the reviewer pointed out, we can prove that a model trained using standard (non-adversarial) training will only learn the true feature and ignore the spurious feature. We will include this statement in the revision of our paper.\n\n**Reference**\n\n[1] Allen-Zhu, Z., Li, Y., & Liang, Y. (2019). Learning and generalization in overparameterized neural networks, going beyond two layers. Advances in neural information processing systems, 32.\n\n[2] Lv, B., & Zhu, Z. (2022). Implicit bias of adversarial training for deep neural networks. In International Conference on Learning Representations.\n\n[3] Allen-Zhu, Z., & Li, Y. (2023, July). Backward feature correction: How deep learning performs deep (hierarchical) learning. In The Thirty Sixth Annual Conference on Learning Theory (pp. 4598-4598). PMLR.\n\n[4] Biggio, B., Corona, I., Maiorca, D., Nelson, B., Šrndi´ c, N., Laskov, P., Giacinto, G. and Roli, F. (2013). Evasion attacks against machine learning at test time. In Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2013, Prague, Czech Republic, September 23-27, 2013, Proceedings, Part III 13. Springer.\n\n[5] Szegedy, C., Zaremba, W., Sutskever, I., Bruna, J., Erhan, D., Goodfellow, I. and Fergus, R. (2013). Intriguing properties of neural networks. arXiv preprint arXiv:1312.6199.\n\n[6] Goodfellow, I. J., Shlens, J. and Szegedy, C. (2014). Explaining and harnessing adversarial examples. arXiv preprint arXiv:1412.6572.\n\n[7] Li, B., Jin, J., Zhong, H., Hopcroft, J., & Wang, L. (2022). Why robust generalization in deep learning is difficult: Perspective of expressive power. Advances in Neural Information Processing Systems, 35, 4370-4384.", "claims_and_evidence": "I have the following two concerns:\n\nClean Classifier ($poly(D)$) ≲ CGRO Classifier($poly(D)+ND$) ≪ Robust Classifier (Ω($\\exp(D)$))\n\nHowever, the results heavily depend on Assumption 4.3 rather than proven, as mentioned by two reviewers as well. Though it may observe from empirical results, it requires a careful theoretical demonstration.\n\nRegarding the training dynamics, the statement is incomplete as the comparison to classifier under standard training is missing. In this case, it is unclear to us whether a model trained via standard (non-adversarial) training would only learn the true feature and ignore the spurious feature? Establishing this distinction is important, as it would suggest that CGRO arises from the nature of adversarial training itself rather than from the artificial construction of the data model.", "methods_and_evaluation_criteria": "This is a theoretical paper and the numerical experiments can support the theoretical findings.", "theoretical_claims": "Yes, I checked the proof and mentioned it in the previous part on \"Claims and Evidence\".", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "yes, this topic is important to the machine learning community.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "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: The paper studies the Clean Generalization and Robust Overfitting (CGRO) phenomenon from two views: representation complexity and training dynamics.

The reviewers agreed upon positive ratings. Overall I recommend accept.
Decision: Accept (poster)