Towards Understanding Robust Memorization in Adversarial Training
Authors: Binghui Li
Yuanzhi Li
Venue: Submitted to ICLR 2023 (2023)
Keywords: adversarial robustness
adversarial training
robust generalization gap
robust overfitting
deep learning theory

Abstract: Adversarial training is a standard method to train neural networks to be robust to adversarial perturbation. However, in contrast with benign overfitting in the standard deep learning setting, which means that over-parameterized neural networks surprisingly generalize well for unseen data, while adversarial training method is able to achieve low robust training error, there still exists a significant robust generalization gap, which promotes us exploring what mechanism leads to robust overfitting during learning process. In this paper, we propose an implicit bias called $\textit{robust memorization}$ in adversarial training under the realistic data assumption. By function approximation theory, we prove that ReLU nets with efficient size have the ability to achieve robust memorization, while robust generalization requires exponentially large models. Then, we demonstrate robust memorization in adversarial training from both empirical and theoretical perspectives. In particular, we empirically investigate the dynamics of loss landscape over input, and we also provide theoretical analysis of robust memorization on data with linear separable assumption. Finally, we prove novel generalization bounds based on robust memorization, which further explains why deep neural networks have both high clean test accuracy and robust overfitting at the same time.

Under review as a conference paper at ICLR 2023
TOWARDS UNDERSTANDING ROBUST MEMORIZATION IN ADVERSARIAL TRAINING
Anonymous authors Paper under double-blind review
ABSTRACT
Adversarial training is standard method to train neural networks be robust adversarial perturbation. However, in contrast with benign overfitting in the stan- dard deep learning setting, which means that over-parameterized neural networks surprisingly generalize well for unseen data, while adversarial training method is able to achieve low robust training error, there still exists significant robust generalization gap, which promotes us exploring what mechanism leads to robust overfitting during learning process. In this paper, we propose an implicit bias called robust memorization in adversarial training under the realistic data assump- tion. By function approximation theory, we prove that ReLU nets with efficient size have the ability to achieve robust memorization, while robust generalization requires exponentially large models. Then, we demonstrate robust memorization in adversarial training from both empirical and theoretical perspectives. In partie- ular, we empirically investigate the dynamics of loss landscape over input, and we also provide theoretical analysis of robust memorization on data with linear sepa- rable assumption. Finally, we prove novel generalization bounds based on robust memorization, which further explains why deep neural networks have both high clean test accuracy and robust overfitting at the same time.
INTRODUCTION
Although deep learning has made a remarkable success in many application fields, such as computer vision (Voulodimos et all, 2018) and natural language process (Devlin 2018), it is well-known that only small but adversarial perturbations additional to the natural data can make well-trained classifiers confused (Szegedy et all, 2013: Goodfellow et all 2OTE), which promotes designing ad- versarial robust learning algorithms. In practice, adversarial training methods (Madry et all 2017 Shatahi all 201% Zhang all 2019) widely used improve the robustness of models by regarding perturbed data as training data. However, while these robust learning algorithms are able achieve high robust training accuracy, it still leads non-negligible robust generalization gap (Raghunathan et all 2019), which is also called robust overfilting (Rice ei all 2020; eil 2022)..
To explain this puzzling phenomenon, series of works have attempted to provide theoretical under- standings from different perspectives. Despite these aforementioned works seem to provide series of convincing evidence from theoretical 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 all, 2018: Li all 2022). it is unclear that what mechanism, during adversarial training process, directly causes robust overfitting. 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 with random initialization), which implies that we should take learning process into consideration to analyze robust generalization.
Second and most importantly, while some works (Isipras et all 2018; Zhang el al, 2010) point out that achieving robustness may hurt clean test accuracy, in most of the cases, it is observed that drop of robust test accuracy is much higher than drop of clean test accuracy in adversarial training (Schmidt all 201& Raghunathan et all, 2019) (see in Table M... Namely, weak version of benign overfitting, which means that overparameterized deep neural networks can both random data powerfully and generalize well for unseen clean data, remains after adversarial training.

---

Under review as a conference paper at ICLR 2023
Table 1: Train and test performances on CIFAR-I0 (Kaghunathan all 2019)
Clean training
Adversarial training
Robust test
3.5%
45.8%
Robust train
100%
Clean test 95.2%
87.3%
Clean train
100%
100%
Therefore, it is natural to ask the following question:
What happens, during adversarial learning process, resulting in both benign clean overfitting and significant robust overfitting at the same time?
In this paper, we provide theoretical understanding of the adversarial training process by proposing a novel implicit bias called robust memorization under the realistic data assumption, which explains why adversarial training leads to both high clean test accuracy and robust generalization gap.
The fundamental data structure that we leverage is that data can be clean separated by neural network felean with moderate size but this neural classifier is non-robust data with small margin, which is consistent with the common practice that well-trained neural networks have good clean performance but fail to classify perturbed data due to the close distance between small margin data and decision boundary. The existence of small and large margin data for image classification has been empirically verified (Banburski et all (02T). And we also assume that data is well-separated which means that there exists a robust classifier in general (Yang et al, 2020). However, this robust classifier may be hard approximate by neural networks (Ll all 2022). In other words, clean training often finds simple but non-ro non-robust solution, although robust classifier always exists.
Specifically, we consider the underlying data distribution where l proportional data is with small margin, which can be perturbed as adversarial example, and 1 - fr proportional data is with large margin, which can be robustly classified by the neural network felean- In adversarial training, we access N instances S randomly drawn from D as training data. In fact, by applying concentra- tion technique in high dimensional probability, we know that there roughly exist JN small margin training data and N)NN large margin training data.
In order to answer the question that we ask, under the above realistic data assumption, we consider the following classifier,
fady (x:((x)== =
Σ (1
0.1i1> z:lpp S 8) + feleam [I)
min ((x, ). S.ati
|| - zillp
classifier other
robust local indicators small margin data
where Samall the small margin part of training dataset, and 8 denotes adversarial perturbation radius, which is smaller than the separation between data in our setting.
Indeed, the classifer fal satisfies all main characteristics of deep models outputted by adversarial training (Proposition (.2):: First, adversarial training error with respect to fady achieves zero; second, fal has good clean performance because the classifier is robust within the neighborhood of training data with small margin and it performs as the same as the clean classifier on other data; third, although this classifier has low robust training error, robustly memorizes training data with small margin, which results in robust overfitting.
non-robust on other data since it only
Inspired by the ideal model fatv, we then propose a conjecture that deep neural networks converge to solution similar to Say in adversarial training, which is a novel implicit bias of adversarial train- ing, and we call it robust memorization, which provides a theoretical understanding of adversarial training. including why solution found by adversarial training has both good clean generalization and robust generalization gap.
Based function approximation theory, we can prove that, for d d-dimensional training dataset S with N samples, ReLU networks with Ö(uNd + poly(d)) parameters are able represent the target functions faa that we mention for robust memorization (Theorem B.d and Corollary B44). However, still prove lower bound for the network size that is exponential in the data dimension
2

---

Under review as a conference paper at ICLR 2023
d make robust generalization (Theorem 6.5), and it manifests that robust classifier has higher representation complexity than the classifier with robust memorization, which potentially explain why adversarial training converges to robust memorization regime rather than finds robust classifier due to the inductive bias of low representation complexity.
To further demonstrate robust memorization in adversarial training, empirically investigate the dynamics of loss landscape over input during adversarial learning process. Concretely, for the loss function ((f(r),)) over classifier f and on data point (z, v). we verify whether f outputted by adversarial training is with robust memorization by certain measure maximum gradient norm within the neighborhood of training data input,
N
VaL(ff(r + 3i)ll) 16
max
where {( 3:) denotes the training dataset, and 1 + 1.
This measure reflects the local flatess of loss landscape over input training dataset. In robust memorization regime, the loss landscape will be very flat within the adversarial training perturbation radius but very sharp outside the neighborhood. Through numerical experiments, the dynamics of the measure observed in different perturbation radius ō and different training epoch shows that the behavior of models trained by adversarial training is very similar to robust memorization. More details are presented in Section !!
To further support our conjecture, we theoretically analyze the optimization process of adversarial training under simple linear separable data set. Our results (Theorem 5.J and Theorem 5.2)) show that clean classification on large margin data implics good clean performance on small margin data, and ReLU networks with moderate size robustly memorize small margin data efficiently. In other words, we prove that after adversarial training, the network exactly learns the function we described in Section B
Finally, motivated by robust memorization, we propose clean and robust generalization bounds. On one hand, clean generalization bound (Theorem b.2) shows that clean sample complexity is polyno- mial in data dimension d. On the other hand, we derive a upper bound of robust generalization gap (Theorem 6.33 that only relies the number of samples and global flatness of loss landscape input. Since adversarial training only promotes model robustly memorizing training data, the global flatness of landscape has no guarantee, and also verified by numerical results, which explains why robust generalization gap is large although robust training error can be very low in adversarial training.
RELATED WORK
Adversarial Examples and Adversarial Training (AT). Szegedy al. (20) first made an intrigu- ing discovery: even state-of-the-art deep neural networks are vulnerable to adversarial examples. Then, Goodfellow all (2014) proposes FGSM seek adversarial examples, and also introduce the adversarial training framework to enhance the defence of models against adversarial perturba- tions. Madry et al. 7 designs PGD to make adversarial attack and uses it to improve adversarial training, which can be viewed as the multi-step vision of FGSM. In general, FGSM-based AT and PGD-based AT are commonly regarded as the standard methods for adversarial training.
Robust Generalization Gap (Robust Overfitting). One surprising behavior of deep learning is that parameterized neural networks can generalize well, which also called benign overfitting that deep models have not only the powerful memorization but good performance for unseen data (Zhang et all, 2017; Belkin et all 2019). However, in contrast the standard (non-robust) gener- alization, for the robust setting, Rice et all (2020) empirically investigates robust performance of models based on adversarial training methods, which are designed to improve adversarial robust- ness (Szegedy et all 203; Madry et all 2017),, and the work shows that robust overfitting can be observed on multiple datasets.
Theoretical Understanding of Robust Overfitting. Schmidi et all (2018); Balan all (201);;
Dan et all (2020) study the sample complexity for adversarial robustness, and their works mani- fest that adversarial robust generalization requires more data than the standard setting, which gives
3

---

Under review as a conference paper at ICLR 2023
explanation of the robust generalization gap from the perspective of statistical learning theory. And another line of works (T'sppras et all, 2018; Zhang et all 2019) propose a principle called the robustieessacccuracyy trade-off and have theoretically proven the principle in different setting, which mainly explains the widely observed drop of robust test accuracy due to the trade-off between adver- sarial robustness and clean test accuracy. Recently, Liet all (2022) investigates the robust expressive ability of neural networks, which demonstrates that, for the well-separated dataset, robust general- ization requires exponentially large models, so the hardness of robust generalization may stem from the expressive power of practical models.
Memorization Adversarial Training. Dong et al. (2024)); et all (2022A) empirically and theoretically explore the memorization effect in adversarial training for promoting deeper under- standing of model capacity, convergence, generalization, and especially robust overfitting of the adversarially trained models. However, different from their works, the concept robust memorization 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.
3 ROBUST MEMORIZATION IN ADVERSARIAL TRAINING
In this section, we first introduce some preliminaries in our theoretical framework.
We consider binary classification task X V, where we use X' E [0, 10. {-1,1} to denote the supporting set of all data input and ground-trune truth labels, respectively, and the data input dimension is d. Let 'D be the underlying data distribution. We use clean 0 loss to evaluate clean performance of classifier as Ce (f) == (T(e))))(((s((((())
* v)]-
Then, we assume that data can be clean separated by a ReLU network with reasonable size (width and depth). Specifically, we assume that there exists ReLU network classifier falea such that CD (Selean) = O, where the clean classifier defined as
Sclemn (ar) == Ww.o
o (Wix + bi)...) + b1.-1) + bi.,
where W; E mm,-1, by E TR. S L,, ma d, my 1, and we use a(.) to denote ReLU activation function, which is defined as a(.) = max (0. -]. Besides, we consider that the width max(mo, mi, ,
,1l.),.,,,)))) } is (d), and the depth is constant.
To understand adversarial robustness by geometry way, we then introduce notion called decision boundary. Formally, the decision boundary of a classifier f is defined as,
DB(J) = (- E X 1 = 0, > 0, F, a E Bp(x, e), s. f.z' < 0).
Notice that this definition different from that Zhang al. (2019), since it requires that the sign of the neighborhood of the decision boundary can be changed, which helps us to establish the relative between decision boundary and adversarial robust margin. We define l, adversarial margin over classifier I and data point (I, u) as min 56 uf(x + E), then we have the following proposition.
Proposition 3.1. (The equivalent between adversarial margin and distance from decision boundary) Assume that the distance between data point and decision boundary is well-defined, then it holds that,
{i E X
min yf(x + +) 2 0} = {x E X dist, (x, DB())) 2 8),
16
{I E X
min yf(x + + < 03 = {a E dist, DB(J)) <8},
where we use (. to denote in distance between point and curve
Proposition B. shows that the classifier is robust data with large distance from decision boundary, and is non-robust on data with small distance from decision boundary. Thus, according distance from decision boundary,
divide all data into two classes, large margin data and small margin data. Namely, the former is defined as Xaarg = {o E X' dist, (fftta))) 2 8}. and the latter is defined as Xamall {i E X dist, DB(fetean) d). We also consider IP (fzz)))D(( E X I and P P(ma))DD fx E Marge
μ. where 0 μ 1 is proportional constant.
Another key notion of data in our setting is separaepa,,, which means that data is far from each other although there exists small margin data. This property is widely observed in Yang et all
4

---

Under review as a conference paper at ICLR 2023
(2020), and it is clear that this assumption is foundation of robust classifier. Formally, consider the supporting set X' = AUB C [0, 1] where two disjoint sets A, denote positive class and negative class, respectively. And assume that dist,(A, B) R, where use distp("--) to denote Ip distance between two sets.
3.1 ROBUST MEMORIZATION UNDER THE REALISTIC DATA ASSUMPTION
In this subsection, we consider adversarial training with access N sample training dataset S {(11,31) (I2, y2). .. (EN, ]N)} iid drawn from the data distribution D, we minimize 0 - 1
adversarial robust training loss addv (f) N Σ i=1 maxijell [f + {)) # y where is the perturbation radius.
Indeed,
also divide S into two sets, small margin training dataset and large margin training dataset. Specifically, let Small be the set {(z, y1) E dist, (B((feeaa) < 6}. and Stange be the set {< ys) dist,p(r., (f((aa))))
8).
To evaluate robust performance of models, we use adversarial robust test loss as L Cadv ( (a maxxiei 5. [sgn(f((r + <)) # y}] The final goal of adversarial training is to find good solution with low robust test loss.
Now, we present the concept that we mainly discuss in this work, robust memorization. Concretely, we consider the following classifier
fadv (z)
Σ
yilfll xillp S. falean(x)]1
min
||x- xsllp >0].
E
(aPs EESmll
Under the above realistic data assumption,
derive the following result.
Proposition 3.2. Assume that data within the Ip 5- neighborhood of training data has local con- stant label (which means data within neighborhood of certain data has the same label), then the classifier fodv has the following properties:
For adversarial robust training error, CS Ladv. (Sadr) = O;
For clean test error, Cetean (Sadt)
For adversarial robust test error, Cunhe (Sadr) = (c (Joteuc)
This proposition shows that the classifier Jadv has the same behavior deep models trained by adversarial training. They have the common performance that they achieve low robust training error and high clean test accuracy, but fail robust classify the data population D.
Motivated by this, we conjecture that adversarial training can learn functions that are close to this form, which called robust memorization, an implicit bias of adversarial training. In the later sec- tions, we formally analyze the properties of this function and adversarial training systematically from different views, including representation complexity, empirical evidence and theoretical evi- dence. Finally, based on robust memorization, we establish generalization guarantees explain good clean generalization and robust generalization gap.
3.2
ON THE REPRESENTATION COMPLEXITY OF ROBUST MEMORIZATION
Next, study the representation complexity of robust memorization, which asks how many param- eters are enough to express the robust memorization classifier faly via deep neural networks. In fact, only O(uNd + poly(d) weights are sufficient for ReLU nets to uniformly approximate the target function fatv, which is stated as the following theorem.
Theorem 3.3. Assume that the perturbation radius satisfies & < R/2, then there exists a classifier i represented by ReL.U net with at most
Ö +oly(d)
parameters such that 1f Sasil < for all x E 10,
5

---

Under review as a conference paper at ICLR 2023
Proof sketch of Theorem + to approximate a smooth function in general Vore et all 1989), some simple functions can be approximate by neural networks more efficiently [elgarsky (20T7). By leveraging this benefit, use ReI.U nets with few parameters to approximate the distance function d2(x)) == I| 2% lpp and we notice that the exact indicator IT(.) can be approximated by soft indicator with two ReLU neurons. Combined with these results, we can derive Theorem
Although exponentially large number of parameters is necessary
By applying the result of Theorem ER we have the following corollary, and it manifests that a neural network with OuNNd + poly(d) weights can achieve robust memorization.
Corollary 3.4. Assume that the perturbation radius satisfies 5 < R/2, then there exists a classifier represented by ReL.U net with O(uNd + poly(d)) parameters such that
For adversarial robust training error, LS (f) o(1):
For clean test error, Lefean (f) o(1);
For adversarial robust test error, Lasii ( = 2 (Cadv: ((etem))
However, while the previous results have shown that achieving both low robust training error and high clean test accuracy representatively efficient for ReLU nets, robust generalization still re- quires exponentially large models even with our data assumption.
Theorem 3.5. Let E (0,1) be small constant and Fr be the set of functions represented by ReLU networks with at most parameters. There exists sequence Na exp(I(d)), d 2 and universal constant C1 > such that the following holds: for any c E (0, 1). there exists a underlying data distribution D that satisfies all above data assumptions and is hu-balanced, such that for any R >> 26 and robust radius Ce, we have
inf { C (f) C1p0-
where poyballacedd means that there exists a uniform probability measure my on X' and the distri- bution DD satisfies that inf
D(E) m.(E)
Lebesgue measurable and mo(F) > 0 2 14o
In other words, the robust generalization error cannot be lower that a constant C1 unless the ReLU network has size larger than exp()i(d)).
Therefore, we get the following representation complexity inequality.
Representation Complexity: Clean Classifier
Robust Memorization
Robust Classifier exp(O(d)
poly(d)
OluNd-pollydd)
This inequality shows that, while functions achieving robust memorization have mildly higher repre- sentation complexity than clean classifiers, adversarial robustness requires excessively higher com- plexity, which may lead to adversarial training converges to robust memorization regime.
4 ROBUST MEMORIZATION ON REAL IMAGE DATASETS
In this section, we demonstrate that, on real image datasets, adversarial training can learn classifiers in robust memorization regime. Indeed, we need study whether models trained by adversarial training tend to memorize data points by approximating local robust indicators on training data.
Concretely, for training data (z, y). we use two measures, maximum gradient norm within the neighborhood of training data, max <8 [f (x) v) and maximum loss function value change max max|jell= [e (<f((( + E), v) - L(f(z), y)]. The former measures the d-local flatness on (z, y), and the latter measures 8 locall adversarial robustness on (x, y), which both describe the key information of loss landscape over input.
Experiment Settings. numerical experiments, we mainly focus on two common real-image datasets, MNIST and CIFAR10. During adversarial training, we use cyclical learning rates and

---

Under review as a conference paper at ICLR 2023
41%
1373
58
20
9pm
225
(a) MNIST: Grad
(b) MNIST: Change
CIFARIO: Grad
(d) CIFARIO: Change
Figure 1: (a)(b:: Robust Memorization on MNIST with Training Is0 Perturbation Radius c 0.1;
(d): Robust Memorization on CIFARIO with Training &o Perturbation Radius c 8/255.
$150
45
621
653
620
63
(a) MNIST: Train
(b) MNIST: Test
(c) CIFARIO: Train
(d) CIFARIO: Test
Figure 2: (a)(b): Learning Process on MNIST with Training Loo Perturbation Radius 0.1; (c)(d):
Learning Process on CIFAR1O with Training 3o Perturbation Radius 8/255.
mixed precision technique (Wong el al. M0200) On MNIST, we use a LeNet5 architecture and train total 20 epochs. On CIFARIO, we use Resnet9 architecture and train total 15 epochs.
Robust Memorization. To verify robust memorization adversarial training, we first use standard AT to train models by fixed perturbation radius ég, and then compute empirical average of maximum gradient norm and maximum loss change on training data within different perturbation radius e. We can numerical results in Figure M. and shows that loss landscape has flatness within the training radius, but is very sharp outside, which practically demonstrates robust memorization on real image datasets, including MNIST and CIFAR10.
Learning Process. We also focus on the dynamics of loss landscape over input during the adver- sarial learning process. Thus, we compute empirical average of maximum gradient norm within different perturbation radius and different training epochs. The numerical results are plotted in Figure D On both MNIST and CIFAR1O. with epochs increasing, is observed that the training curve descents within training perturbation radius, which implies models learn the local robust indi- cators robustly memorize training data. However, while the test curve MNIST has the similar behavior to training, on CI,AR10, the test curve ascents within training radius instead, which poten- tially explains why robust generalization gap on CIFAR10 is more significant than that on MNIST.
THEORETICAL ANALYSIS OF ADVERSARIAL TRAINING ON LINEAR SEPARABLE DATA
In this section, we theoretically demonstrate robust memorization by analyzing the convergence of adversarial training on a certain synthetic dataset.
Specifically, we assume that data E Rd can be formalized as cyw" + &. where w² is the target direction ([w")) I|2 1), y (-1,+1) +1} is the label, is the norm scale that is a for large margin data and is 3 for small margin data (3 < a), and (o w T is random Guassian noise orthogonal to =r.
Indeed, this synthetic dataset captures the main characteristics data assumption that we mention in Section H. On one hand, there exists simple but non-robust classifier faleam (x) =T that can clean classify data but is non-robust for small margin data. On the other hand, due to the randomness of noise, in the high-dimensional setting, small data is also well-separated.
7

---

Under review as a conference paper at ICLR 2023
We consider mixed learner model as f(x) Tx - (w; (t b), (-) is ReLU activation function and b is a threshold.
Tx)),
where the neuron ((
With .N- sample training dataset S = Small U Starge i.id. drawn from the underlying distribution D,
we minimize the exponential loss as Ls Lexp,adv, (J) N Ei= max] exp(-1> [xr + 6:)).
By using the standard adversarial training algorithm, FGSM (Gondfellow et atl 2014), we have the following result.
Theorem 5.1. With large margin data Starge as training data, we FGSM to train the model when only we is activated and zero initialized, deriving a parameter iteration sequence {wh { k=
Then, with high probability over the sampled set, we have limg-+00
w" = o
Theorem 5. shows that, under the linear separable data assumption, high clean test accuracy on large margin data implies good clean performance on small margin data, which can help us understand clean generalization better in adversarial training (see Theorem 6.2 in Section (
Theorem 5.2. By using a modified adversarial training algorithm all training dataset S, we de- rive a parameter sequence (Ah (wr)m 1=00 ==okk=,.... Then, with high probability, for O- adversarial training loss LS 20-1.adv,6 it holds that lim Cs 20-1,adv., (()))) O.
In fact, the above theorems show that adversarial training method on linear separable data will converge to the normalized target solution, fxx TTTT Ex,SSmmn Ve x), which is exactly the robust memorization function mentioned in Section C.
6 GENERALIZATION GUARANTEES BASED ON ROBUST MEMORIZATION
Standard generalization bound can not directly explain high clean test accuracy after adversarial training. In general, standard generalization bound can be stated the following form. With high probability over random sampled training data, we have
Celean
Celean (1) v
Complexity
N
where is the number of samples, and Complexity(F) denotes a complexity measure function family F, such as VC dimension and Rademacher complexity.
However, this standard generalization bound can not explain high clean test accuracy after ad- versarial training. In order to have enough capacity for achieving low robust training (i.e. minfer F Ladv. (ʃ) 0), need to set Complexity(FP (F) O(Nd) (due to Corollary [44 and the relation between VC dimension and the number of parameters (Bartlett et al, 2019)), which causes the above bound loose use.
6.1 IMPROVED GENERALIZATION BOUND ANALYSIS BASED ON ROBUST MEMORIZATION
Fortunately, notice that the robust memorization function fuáv has much lower complexity on all large margin data (poly(d)) than the complexity on only sampled small large margin data (O(d)). Inspired by this, we can prove novel generalization bound by leveraging it.
Assumption 6.1. We assume that, for any classifier f outputted by adversarial training under the realistic data assumption that we mention in Section we have Celean (ʃ) O (Cesam (f)). where use D amall Duage to denote small margin part and large margin part in the population D.
This assumption has been theoretically verified in Section S which means that the clean test accuracy on small margin data can be bounded by the clean test accuracy on large margin data. Indeed, it holds for any homogeneous classifier when we assume that small margin data also has small norm. We leverage this property prove the following clean generalization bound.
Theorem 6.2. Let D be the underlying distribution that satisfies all assumption in Section C and Assumption b.ll With access to Nssample training dataset {(x), y1 (Z2: V2)...., (x } is i...d. drawn from D, there exists modified adversarial training algorithm with perturbation
8

---

Under review as a conference paper at ICLR 2023
Traning
Training Process
0.90
godal Batrece
0.3
020
0.23
015
0.33
ndinn aidr
(a)
(b)
Figure 3: Left: Local and Global Flatness During Adversarial Training on CIFARIO; Right: The Relation Between Robust Generalization Gap and Global Flatness on CIFARIO.
radius 8, As DV + Fs. where Fs denotes the hypothesis class, such that f = As(S) satisfies
fighi (f) 0, and holds with probability high probability that Li (f) z Li (f) poly(d)
This result implies that the sample complexity adversarial training polynomial in the data dimension d, which provides theoretical guarantee for benign overfitting in adversarial training.
However, we still prove the following theorems to illustrate the hardness robust generalization. In contrast the clean generalization, we have another robust generalization bound that mainly depends on global flatness loss landscape over input.
Theorem 6.3. Let be the underlying distributtin with smooth density function, and N sample training dataset S = {(11(((1))) V1), (I2, y2)...., (I UN}} } is ii.dd drawn from D. Then, it holds with probability A over sampled set S that,
C(D,C) VA
Cap ( Lg
6 (f) N aोz
E(
max ( Lilellee 24
global flaness
where C(D, L) a constant that only depends on the distribution 'D and the loss function :(..)).
This robust generalization bound shows that robust generalization gap can be controlled by global flatness of loss landscape over input rather than local flatness. And we also derive the lower bound of robust generalization gap stated as follow.
Proposition 6.4. Let D be the underlying distribution with smooth density function, then have
cadu (ʃ) Celean Ω (8E(..))~ ( (I [[
Theorem T and Proposition 54 manifest that robust generalization gap is very related to global flatness. However, although adversarial training achieves good local flatness via robust memoriza- tion, models lack global flatness, which leads to robust overfitting. This point is also verified by numerical experiment on CIFARIO (see results in Figure D First, global flatness grows much faster than local flatness in practice. Second, with global flatness increasing during training process, leads to a increase of robust generalization gap.
CONCLUSION
This paper provides a theoretical understanding of adversarial training by proposing a implicit bias called robust memorization. We first explore the representation complexity of robust memorization under the realistic data assumption. Then, we empirically demonstrate robust memorization on real- image datasets. And we also theoretical analyze adversarial training in the linear separable data setting. Finally, we prove generalization guarantees inspired by robust memorization, which can explain why both good clean performance and robust overfitting happen in adversarial training.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Martin Anthony, Peter I. Bartlett, Peter I. Bartlett, et al. Newral network learning: Theoretical foundations, volume 9, cambridge university press Cambridge, 1999.
Yogesh Balaji, Tom Goldstein, and Judy Hoffman. Instance adaptive adversarial training: Improved accuracy tradeoffs in neural nets. arXiv preprint arXiv: 2019.
Andrzej Banburski, Fernanda De La Torre, Nishka Pant, Ishana Shastri, and Tomaso Poggio. Distri- bution of classification margins: Are all data equal? arXiv preprint arXiv:2107.10199 2021.
Peter L. Bartlett, Nick Harvey, Christopher Liaw, and Abbas Mehrabian. Nearly-tight ve-dimension and pseudodimension bounds for piecewise linear neural networks. The Journal of Machine Learning Research, 20(1):2285-2301, 2019.
Mikhail Belkin, Daniel Hsu. Siyuan Ma, and Soumik Mandal. Reconciling modern machine- learning practice and the classical varinvariance trade-off. Proceedings of the National Academy of Sciences, 1 116(32) 15854, 2019.
Chen Dan, Yuting Wei, and Pradeep Ravikumar. Sharp statistical guaratees for adversarially ro- bust gaussian classification. In International Conference Machine Learning, pp. 2345-2355. PMLR, 2020.
Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint 18Xiv:1810.04400 2018.
Ronald Vorere Ralph Howard, and Charles Micchelli. Optimal nonlinear approximation.
Manuscripta mathematica, 63(4))469 478, 1989.
Yinpeng Dong, Ke Xu, Xiao Yang, Tianyu Pang. Zhijie Deng, Hang Su, and Jun Zhu. Exploring memorization adversarial training. arXiv preprint arXiv:2106.00 06600 2021.
lan J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. arXiv preprint 141 2014.
Binghui Li, Jikai Jin, Han Zhong, John E Hopcroft, and Liwei Wang. Why robust generalization in deep learning is difficult: Perspective of expressive power. arXiv preprint arXiv:2205. 13863, 2022.
Yan Li, Ethan Fang, Huan Xu, and Tuo Zhao Implicit bias of gradient descent based adversarial training on separable data. In International Conference on Learning Representations, 2020.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint arXiv: arXiv:/706.000 170600608.
2017.
Guido F Montufar, Razvan Pascanu, Kyunghyun Cho, and Yoshua Bengio. On the number of linear regions of deep neural networks. Advances in neural information processing systems, 27, 2014.
Hemning Petzka, Michael Kamp, Linara Adilova, Mario Boley, and Cristian Sminchisescu. Relative flatness and generalization in the interpolation regime. arXiv preprint 1tXii:20011000933 2020.
Aditi Raghunathan, Sang Michael Xie, Fanny Yang, John C Duchi, and Percy Liang. Adversarial training can hurt generalization. arXiv preprint 190iv 06032, 2019.
Leslie Rice, Eric Wong, and Zico Kolter. Overfitting in adversarially robust deep learning. In International Conference Machine Learning, pp. 8093-8104. PMLR, 2020.
I Ludwig Schmidt, Shibani Santurkar, Dimitris Tsipras. Kunal Talwar, and Aleksander Madry. Ad- versarially robust generalization requires more data. Advances in neural information processing systems, 31, 2018.
Ali Shafahi. Mahyar Najibi, Mohammad Amin Ghiasi, Zheng Xu, John Dickerson, Christoph Studer, Larry S Davis, Gavin Taylor, and Tom Goldstein. Adversarial training for frree! Advances in Neural Information Processing Systems, 32, 2019.
10

---

Under review as a conference paper at ICLR 2023
Bernard W Silverman. Density estimation for statistics and data analysis. Routledge, 2018.
Christian Szegedy, Wojeiech Zaremba, llya Sutskever, Joan Bruna, Dumitru Erhan, lan Goodfellow, and Rob Fergus. Intriguing properties of neural networks. arXiv preprint arXiv:1312.611 6199,, 2013.
Matus Telgarsky, Neural networks and rational functions. In International Conference on Machine Learning, pp. 3387-3393. PMLR, 2017.
Dimitris Tsipras, Shibani Santurkar, Logan Engstrom, Alexander Turner, and Aleksander Madry, Robustmess may be at odds with accuracy. arXiv preprint Stt.::1800.221555 2018.
Athamasios Voulodimos, Nikolaos Doulamis, Anastasios Doulamis, and Eftychios Protopapadakis. Deep learning for computer vision: A brief review. Computational intelligence and neuroscience, 2018, 2018
Eric Wong, Leslie Rice, and J Zico Kolter. Fast is better than free: Revisiting adversarial training. arXiv preprint arXiv:2001.03994, 2020.
Han Xu, Xiaorui Liu, Wentao Wang, Wenbiao Ding, Zhongqin Wu, Zitao Liu, Anil Jain, and Jiliang Tang. Towards the memorization effect neural networks in adversarial training. arXiv preprint arXiv:2106.0m (rXi::2/06.04794 2021.
Yuan Yang. Cyrus Rashtchian, Hongyang Zhang, Russ R Salakhutdinov, and Kamalika Chaud- huri. A closer look at accuracy vs. robustness. Advances in neural information processing systems, 33:8588-8601, 2020.
Dmitry Yarotsky. Error bounds for approximations with deep relu networks. Neural Networks, 94: 103-114, 2017.
Chaojian Yu, Bo Han, Li Shen, Jun Yu, Chen Gong, Mingming Gong, and Tongliang Liu. Under- standing robust overfitting of adversarial training and beyond. In International Conference on Machine Learning, pp. 25595-25610 PMLR, 2022.
C Zhang, S Bengio, M Hardt, В Recht, and O Vinyals. Understanding deep learning requires rethinking generalization. iclr. arXiv preprint arXiv:1611.03530 2017.
Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric Xing, Laurent El Ghaoui, and Michael Jordan. Theoretically principled trade-off between robustness and accuracy. In International conference machine learning, pp. 7472-7482. PMLR, 2019.


Reviews:
[{"review_id": "g7U34dlkHg7", "reviewer": "Reviewer_W3fx", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper theoretically analysed the complexity caused by robust memorization in adversarial training. The paper first proposed the concept of memorization then derived the complexity of neural networks required for robust memorization and for robust generalization. The the paper discussed the sample complexity of adversarial training.", "summary_of_the_review": "In all, I think the paper is written well and has a clear structure. However, I recommend the authors to include some necessary discussion on their differences and connection between existing works on robust memorization. I listed some related papers in the review but there can be more related papers.", "strength_and_weaknesses": "Strength:\n* This paper thoroughly analyzed the robust memorization in adversarial training, from both representation complexity and sample complexity.\n* The paper is well-written and easy to follow.\n\nWeaknesses:\n* The paper lacks a large group of necessary references, e.g. [1][2][3][4][6].\n* The concept of robust memorization has been introduced and explored by many papers [1] [2] [3].\n* The generalization bound of adversarial training has been proved by [6] which is part of the last contribution of this paper.\n* In Section 3.2, the paper compares the representation complexity of robust memorization with robust generalization, where it states that the representation complexity of robust generalization is exponential to the dimension. This result is known in [5]. Although the authors have cited this in the introduction, it is not made clear here.\n\n[1] Exploring Memorization in Adversarial Training.\n\n[2] Adversarial Training Can Hurt Generalization.\n\n[3] Towards the Memorization Effect of Neural Networking Adversarial Training\n\n[4] Understanding Robust Overfitting of Adversarial Training and Beyond\n\n[5] Why robust generalizationin deep learning is difficult: Perspective of expressive power\n\n[6] Adversarially Robust Generalization Requires More Data", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "fhGddA9MTbP", "reviewer": "Reviewer_59uS", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In this paper, the authors proposed an implicit bias called robust memorization in adversarial training under the realistic data assumption. By function approximation theory, the authors proved that ReLU nets with efficient size have the ability to achieve robust memorization, while robust generalization requires exponentially large models. The authors also demonstrate robust memorization in adversarial training from both empirical and theoretical perspectives.  \n", "summary_of_the_review": "1. It seems that f_adv in page 2 is constructed, not trained. By “adversarial training error” did the author mean an adversarial loss of training data? If so, why does it implies “global convergence of adversarial training”?\n\n2. This new implicit bias still remains a conjecture in my opinion. First, a network that is able to represent the target functions f_adv does not mean it will lean towards f_adv. Second, the empirical study that the maximum gradient norm is sharp outside the perturbation region only suggests on training data it is robust. It cannot show anything related to the outside data points.\n\n3. Dividing data into small-margin and large-margin ones could fail in modern deep learning situations where each data point can easily find a small margin to any other classes (targeted adversarial examples). In other words, $\\mu$ could be just 1. \n\n4. For simple data distributions, previous works have shown that adversarial training can even achieve robust generalization, such as Dan et al. 2020 and\n\n    \"Precise statistical analysis of classification accuracies for adversarial training.\" arXiv preprint arXiv:2010.11213 (2020).\n\n    \"Benign Overfitting in Adversarially Robust Linear Classification.\" arXiv preprint arXiv:2112.15250 (2021).\n\n     Do the authors' results contradictory to theirs? The authors may want to comment on this.\n", "strength_and_weaknesses": "Strength\n1. Propose a new implicit bias called robust memorization to explain the empirical behavior of adversarial training\n2. Provide both empirical and theoretical results showing evidence from different perspectives\n\n\nWeakness\n1. This new implicit bias still remains a conjecture in my opinion. There lacks strong evidence to show that it is actually what happens.\n2. The empirical results is somewhat known, and do not provide many new information\n3. The authors did not compare their theoretical analysis on robust memorialization with previous theoretical studies in adversarial training\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Syz26Mljht", "reviewer": "Reviewer_z1zg", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the robust memorization problem in adversarial training, and explains that why adversarial training suffers from severe over-fitting problem.\n", "summary_of_the_review": "The paper has many writing issues. As listed in the weakness part, the big amount of typos/grammars in theorems preventing readers from understanding the paper.", "strength_and_weaknesses": "Strength:\nIt is an interesting idea to connect the adversarial training to some local estimate to explain over-fitting.\n\nWeakness:\n\nMain concern:\n\n[1] The authors need to improve the clarity of the mathematical notations and formulas. For example \n\n(1) Definition of f_adv is confusing. The second part of f_adv is reasonable, but why we take a summation on nearby samples? Is it a summation or an average? Also Sometimes it uses S and sometimes is uses \\mathcal{S}.\n\n(2) In Proposition 3.1, the same equation repeats?\n\n(3) In Proposition 3.2, what is \"local constant label\"?\n\n(4) In Corollary 3.4, if we want to claim that \"a neural network with (some number of) weights can achieve robust memorization\", should we prove that every network reaching a small robust training error has a poor robust test error? If we have \"there exists a classifier\", then how can we make sure this is the one the training is converging?\n\n(5) In Theorem 3.5, the notation N_d is used but not defined. There is a definition in Theorem C.1 that N_d is the number of parameters of the nueral network. Please move the definition to the main text.\n\n(6) In Theorem 5.1, how to understand the sentence \"...when only w0 is activated and zero initialized, deriving a parameter sequence...\"? In Theorem 5.2, again, what is the sequence (k)?\n\n(7) Theorem 6.3 provides an upper bound, and Proposition 6.4 provides a lower bound. Please add some descriptions about these two results in the paper. Also, Theorem 6.2 appears suddenly without any connection.\n\nIt is acceptable to have some minor typos, but there are so many typos in the paper and it prevents me from understanding the logic of the paper.\n\n[2] The authors need more evidence to show why their proposed analysis is prefered than other analysis, or why it is essential to consider the robust memorization.\n\n[3] Most papers in the reference list are published before 2021. Could the authors supplement the introduction with some more updated literature?\n\n========================\n\n\nMinor issues:\n\n[1] About the contribution: is the robust memorization an existing implicit bias in adversarial training? If this is the case, then why the contribution is that \"we propose an implicit bias called robust memorization in adversarial training...\" in the abstract as well as the introduction? Should it be that the authors figure out a source of the implicit bias in adversarial training and identify it as robust memorization? \n\n[2] Spelling or issue. \n\n(1) Page 2: \"is the (samll) margin part of training dataset\"\n\n(2) Theorem 5.1, 6.2: \"over (the) sampled set\", missing \"the\"\n\n(3) Theorem 6.3: \"Let D (is) the underlying\", \"is\" should be \"be\"\n\n(4) Section 5, paragraph 2: \"for small large data\"", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Reject