Benign Overfitting in Adversarially Robust Linear Classification
Authors: Jinghui Chen
Yuan Cao
Quanquan Gu
Venue: ICLR 2022 Submitted (2022)
Keywords: Benign Overfitting
Robust Linear Classification

Abstract: ``Benign overfitting'', where classifiers memorize noisy training data yet still achieve a good generalization performance, has drawn great attention in the machine learning community. To explain this surprising phenomenon, a series of works have provided theoretical justification in over-parameterized linear regression, classification, and kernel methods. However, it is not clear if benign overfitting still occurs in the presence of adversarial examples, i.e., examples with tiny and intentional perturbations to fool the classifiers. In this paper, we show that benign overfitting indeed occurs in adversarial training, a principled approach to defend against adversarial examples. In detail, we prove the risk bounds of the adversarially trained linear classifier on the mixture of sub-Gaussian data under $\ell_p$ adversarial perturbations. Our result suggests that under moderate perturbations, adversarially trained linear classifiers can achieve the near-optimal standard and adversarial risks, despite overfitting the noisy training data. Numerical experiments validate our theoretical findings.  

Under review as a conference paper at ICLR 2022
BENIGN OVERFITTING IN ADVERSARIALLY ROBUST LINEAR CLASSIFICATION
Anonymous authors
Paper under double-blind review
ABSTRACT
"Benign overfitting", where classifiers memorize noisy training data yet still achieve good generalization performance, has drawn great attention in the ma- chine learning community. To explain this surprising phenomenon, series of works have provided theoretical justification in reeepparamtteiieed linear regres- sion, classification, and kernel methods. However, is not clear if benign overfit- ting still occurs in the presence of adversarial examples, i.e., examples with tiny and intentional perturbations to fool the classifiers. In this paper, we show that benign overfitting indeed occurs in adversarial training, a principled approach to defend against adversarial examples. In detail, we prove the risk bounds of the ad adversarially trained linear classifier on the mixture of sub-Gaussian data under l, adversarial perturbations. Our result suggests that under moderate perturba- tions, adversarially trained linear classifiers can achieve the near-optimal standard and adversarial risks, despite overfitting the noisy training data, Numerical exper- iments validate our theoretical findings.
INTRODUCTION
Modern machine learning methods such deep learning have made many breakthroughs in a vari- ctt application domains, including image classification (He et Krizhevsy et al. 2012). speech recognition (Hinton et al., 2012) and etc. These models are typically over-parameterized::
the number of model parameters exceeds the size of the training samples. One mystery is that, these over-paramettrizee models can memorize noisy training data and yet still achieve quite good generalization performances on the test data (Zhang al. 2017). Many efforts have been made to explain this striking phenomenon, which against what the classical notion of overfitting might suggest. A line of research works (Soudry et al., 2018 Ji & Telgarsky 2019b Nacson et 2019 Gunasekar et al. [01 a) shows that there exists the so-called implicit bias (Neyshabur 2017] the training algorithms tend to converge to certain kinds of solutions even with no explicit regulariza-
tion. Specifically, Soudry et al. (0188) Ji & Telgarsky (2019b); Nacson et al. (2019) demonstrate that gradient descent trained linear classifiers logistic or exponential loss with no regularization
asymptotically converge to the maximum Le margin classifier. Recent works (Bartlett et al. 2020
Chatterji & Long. 2020: Cao et al., 2021 Wang & Thrampoulidis, 2021 Tsigler & Bartlet 2020)
further shows that over weer-parameterized and implicitly regularized interpolators can indeed achieve small test error, and formulate this phenomenon as "benign overfitting" More concretely, suppose the classification model ff is parameterized by 0 E O and the loss is denoted as f(-). The population risk is define as
IP P(xx))>Dlfo(x) + v].
where data pair yX is generated from certain data generation model. Chatterji & Long (2020) shows that with sufficient over-parameterivation,, gradient descent trained maximum 1.2 margin classifier can achieve nearly optimal population risk on noisy data for data generated from sub-Gaussian mixture model. This suggests that the overfitting can be "benign" in the over- parameterized setting.
Besides these studies on the benign overfitting phenomenon, another well-known feature of mod- em machine learning methods is that they are vulnerable to adversarial examples. Recent studies (Szegedy al. 2013; Goodfellow al. 2015) show that modern machine learning systems briutl: slight input perturbation that is imperceptible to human eyes could mislead a well-trained classifier into wrong classification result. These malicious inputs also known as the adversarial

---

Under review as a conference paper at ICLR 2022
examples (Szegedy al. 2013 Goodfellow et al. 2015 Adversarial examples raise severe trust- worthy issues and security concerns on the current machine learning systems especially in security- critical applications. Various methods (Kurakin et al. 2016; Madry et al.) 2018: Zhang et al. 2019) Wang et al. 2019; 2020) have been proposed to defend against the threats posed by adversarial ex- amples. One of the notable approaches is adversarial training (Madry et al. 2018). Specifically, adversarial training solves the following min-max optimization problem,
min 0
max {(fo(x)). W:), X (EB((x))
where {(x, v:)] is the training set and (x | | x, ll, S denotes the c-ball around x; in Lp norm (p 2 1). Many empirical or theoretical studies have been conducted trying to analyze or further improve adversarial training robustness (Zhang et al. [019 Rice al.) 2020) Wang al.,
2020
Carmon et al. 2019; Wang et al. 2019; Raghunathan et al. 2020). A recent work (Sanyal al. 2021) also pointed out that normally trained interpolators with the presence of label noise are unlikely to be adversarially robust, while ad vdversarillyy robust classifiers cannot overfit noisy labels under certain conditions. However, is still not clear whether the benign overfitting phenomenon occurs for extremely over per-parametteried models in the presence of adversarial examples.
In this paper, we show that benign overfitting indeed occurs in adversarial training. In order to properly characterize the benign overfitting phenomenon on adversarial training, we also define the population adversarial risk, which is the counterpart for population risk in standard training scenario:
(xx))>> [xx E Be (x) s.t., fx(x') + y]
The adversarial risk measures the misclassification rate of the target classifier under the presence of --normm adversarial perturbations. It is easy to observe that the adversarial risk is always larger
than standard risk as it requires the classifier to correctly classify the data examples within the entire local i norm ball.
We summarize our contributions of this paper in the following
We show that the benign overfitting phenomenon occur in adversarially robust linear classi- fiers with sufficient over paeerrrattttizzttionnn Specifically, under moderate ép norm perturbations, adversarially trained linear classifiers can achieve the near-optimal standard and adversarial risks, in spite of overfitting the noisy training data.
When the perturbation strength is set to be O, our adversarial risk bound reduces to the stan- dard one. The resulting standard risk bound extends Chatterji & Long (202 's risk bound to further characterize the behavior of the linear classifier trained by t-step gradient descent.
We show that depending on the value of (perturbation norm), the adversarial risk bound can be different. The higher value of p (typically for p 2 case) actually leads to larger gap between the adversarial risk and the standard risk with the same c.
Notation. we use lower case letters to denote scalars and lower case bold face letters to denote vectors. For vector x E Rd, we denote its Ep norm (p 2 1) of x by ||x||p = (Σ |a:; (e: 1/p the loo norm of by |||| max |at//- We denote " as the element-wise p-power of x. For p 2 1, we denote (x) as the Ep norm ball radius r centered at x. Given two sequences {an} and (bn), we write an (b,,) if there exists constant 0 C too such that a, I Cbn, We denote on (bbb)) if b, = Oan,). We denote a, = (b,,, if a2 = (b,,) and an = ((bb)).
2 RELATED WORK
There exists a large body of works on adversarial training, implicit bias and benign overfitting. In this section, we review the most relevant works with ours.
Adversarial Training, Adversarial training (Madry et al. 2018) and its variants Zhang et al. 2019
Wang et al. 2019 2020) are currently the most effective type of approaches to empirically defend
against adversarial examples (Szegedy et al. 2013) Goodlellow et al., 2015). And many attempts have been made understand its empirical success. Charles al. (201)) Li al. (020)) showed that the adversarially trained linear classifier directionally converges to the maximum margin classi- fier. Gao al. 2019); Zhang et (2020b) showed that adversarial training with neural networks can achieve low robust fraining loss. Yet these conclusions cannot explain the test (population) perfor- mances. Another line of research focuses the generalization performance of adversarial training
2

---

Under review as a conference paper at ICLR 2022
and the number of training samples. (Schmidt et al. (2018) showed that adversarial models require more data than standard models to achieve certain test accuracy. Chen et al. al. (2020) showed that more data may actually increase the gap between the generalization error of adversarially-trainee models and standard models. Yin et al. (2019): Cullina et al. (2018) studied the adversarial Rademacher complexity and VC-dimensions. Some other works focus on the trade-off between robustness and natural accuracy (Zhang et al., 2019 Tsipras et al. [2019] Wu et al., 2020; Raghunathan al. 2020, 2020; Dobriban et al. 2020 Javanmard & Soltanolkotabi 2020), adversarial model complexity lower bound (Allen-Zhu & Li, 2020). as well as the provable robustness upper bound
Yang et al.
(Fawzi et al.
2018 Zhang et al. 2020a).
Recently, some works also focus on studying the learning of robust halfspacces and linear models. Montasser et al. (2020) studied the conditions on the adversarial perturbation sets under which halfs- paces are robustly learnable in the presence of random label noise. Diakonikolas al. (2020) studied the computational complexity of adversarially robust halfspaces under Lp norm perturbations. Zou eet al. 2021) showed that adversarially trained halfspaces are provably robust with low robust clas- sification error in the presence of noise. Dan et al. (2020) proposed an adversarial signal to noise ratio and studied the excess risk lower/upper bounds for learning Gaussian mixture models. Taheri ct al. (2020); Davanmard & Soltamolkotabi (2020) studied adversarial learning of linear models on Gaussian mixture data where the data dimension and the number of training data points have fixed ratio.
Implicit Bias. Several recent works studied the implicit bias of various training algorithms in over- parameterized models. [Soudry et al. (2018) studied the implicit bias of gradient descent trained on linearly separable data while Ji & Telgarsky (2019b) studied the non-separable case. Gunasekar al. (2018a) studied the implicit bias of various optimization methods in linear regression and classification problems. Di & Telgarsky (019a) studied the implicit bias for deep linear networks and
Arora et al. (2019); Gunasekar et al. (2018b) studied the implicit bias for matrix factorization. Lyu & Li (020)) studied the implicit regularization of homogeneous neural networks with exponential loss and logistic loss.
Benign Overfitting and Double Descent. A series of recent works have studied the "benign over- fitting" phenomenon Bartlett al. (2020) that when training over- peee-paraeetrrieed models, classifiers Barteeetnnnntnttttttttet can still achieve good population risk even when overfitting the noisy training data. [Bartlett et al.) (2020): Tsigler & Bartlett (2020) studied the risk bounds for over- over-paramee perrraaammttezeed linear (ridge) gression and showed that under certain settings, the interpolating linear model with minimum param- eter norm can have asymptotically optimal risk. CChtterjj & Long 2020); Cao et al. (2021); Wang & Thrampoulidis 2021) studied the risk bounds in linear logistic regression and linear support vector machines. Belkin et al. (2018 2019a b); Hastie et al. al.) (2019); Wu & Xu (2020) further quantified the dependency curve between the population risk and the degree of over- werrparameterizzatoo and showed that the curve has double-descent shape.
PROBLEM SETTING AND PRELIMINARIES
We consider a GabbGaassiin mixture data generation model in our work. Specifically, the clean data
(x, 77 ~ D is generated such that, for each data point (x, 77 E Rd x (+1), we have y ~ Unif( (+1)) and X = 7pu + & where & Rdd and &1, fi.E2.... ........... Eu are i.i.d. zero-mean aab-Gaussian variables with
sub- Gaussann norm at most 1. The actual data examples are sampled from a noisy distribution D
which is close to the clean distribution D. Specifically, D can be any distribution over Rd x {+1)
who has the same marginal distribution on Rd and the total variation distance dTv(D, D) S 1 where 7) denotes the noise level.
Note that data generation model is standard for studying the population risk of over- parameterized linear classification. In fact, it is exactly the same as the one studied in CChtterri] & Loong (2020). In this model, following standard coupling lemma (Lindvall (2002). there always exists a joint distribution on original data and noisy data ((x, M) (x,y) y)) such that the marginal dis- tribution for (x. 7) is D. the marginal distribution for (x, y) is D, P(x = X] = 1 and Ply # Ø1 S n
In this paper, study the problem of robust binary classification with training data { (x;: y: ) drawn i.i.d. from the distribution D. Let's denote the "clean" sample index as C := {k : yk yk and the "noisy" sample index as N == (k: : yk # }. We consider the adversarially trained linear
3

---

Under review as a conference paper at ICLR 2022
Algorithm 1 Gradient Descent Adversarial Training
1: input: Training data {x, 3/ Ji=1> number of training iterations 7' maximum perturbation
strength 6, training step sizes ax;
2: initialize model parameter 0n-
3: for = 1,..., do
4: for each {x,, do
5: x arggmaxx (xp(-y;0,1xx)
6: end for
7: 0, = 0,-1 aie VoL(O--1)
8: end for
classifier under exponential loss. In such case, the adversarial loss be explicitly written
((O)
max exp(-1i0" x(). (X)
(3.1)
In gradient descent adversarial training algorithm, the adversarial loss L(0) is minimized by first solving the inner maximization problem in (3.1) with respect to the current model parameter 0,-1 and then update the model parameter 0, by performing gradient descent minimize the adversarial loss each iteration. We summarized the training procedure for gradient descent adversarial train-
ing in Algorithm 1 Note that in the linear classifier setting, the inner maximization problem in has the following property
argmax exp(- 1<p(-y:00 y:0 -x,0xx)x))))))) argmax exp(-9t +u)) argmin y: u; (.E
(3.2)
(x.)
[|u, ly
By Hölders' inequality it is easy to observe that the optimal adversarial loss and the corresponding gradient can be written as
L( Σ exp(-310 + ( = Σ - - 0|10 (xppppyy000 x; cl(01lg),
where 1/p+1/9 Also note that the over-parameterizet settings, training examples draw from our data generation model are linearly separable with high probability (See Lemma 5.1 in Section 5}. Linearly separable property ensures that the training samples have positive margin (with high probability). Following Li et al. (2020), we also define the standard and adversarial margin as
min y:0 X;: 7 := 7 ||01,_=1 ie(n]
min min y: x
(3.3)
0||==1 i (x.)
which are useful our later analysis. adversarial margin y defined above as
also define the unique linear classifier that achieves
MAIN RESULTS
In this section. we study both the behavior of the population risk and the population adversarial risk for adversarially trained linear classifiers.
Assumption 4.1. The adversarial perturbation radius is upper bounded by constant R and is smaller than the fp data margin 7, i.e., e < min [2
The goal of adversarial training is obtain high-accuracy classifiers that also robust to small input perturbations which can be ignored by human beings (e.g., small fo -nom perturbations that invisible to human eyes). Therefore, Assumption 4.1 is reasonable by constraining the maximum allowable perturbation magnitude.
Assumption 4.2. The noise & in the data generation model satisfies that [[[||| > kd for some constant K.
Assumption 4.2 is a common condition that has also been considered in Chatterji & Long 2020). It ensures that the summation the variances of the data input increases in the order of ((d). Clearly, this assumption covers the most common setting where the entries of & are i.i.d. and have a variance larger than equal K..
Note that in practice people often initialize d by small random vector (e.g.. Xavier initialization (Glorot Hengio 2010), while follow [i et 2020 and Og for the case of theoretical analysis.
4

---

Under review as a conference paper at ICLR 2022
Assumption 4.3. The gradient descent starts at 0, and the step sizes are set dg 1/((ddn),
24-2
Or = a S 1/(GdaM) for M max[[2d + e(q - 1) 24 //J (epp->>/(Ga)) + e/G), and constant G.
Assumption 4.3 summarizes our assumptions about the gradient descent algorithm on the adversarial loss. The learning rate conditions here are ensure the convergence of adversarial training, and is inspired by Li et al. (2020).
We first present theorem for standard risk of adversarial training method (Algorithm D
Theorem 4.4 (Standard Risk of Adversarial Training). For any p [1,+ suppose that As- 4.2 and 4.3 hold with k E (0, 1] and large enough constants and G. Moreover, for any 8 E [0. suppose the number of training samples n Colog(1/), the dimension d C. C-max(n) p n² (og(n/8)), the noise level 17 < 1/C, and | 2 max (log(n/6), ( e|1p for a large enough constant C. Then with probability at least 1 - ô, adversarially trained linear classifier fo. for sufficiently large t under lp --oom e-perturbation satisfies the following standard risk
sumptions 4.
( +c)+
4e]1
pu 1"T1
log 2 )
P P(x.o) (x) + yl S n exp
logt t
where C², C"", ,,",C"" C are absolute constants,
Remark 4.5. Theorem 4.4 presents the standard risk of adversarial training under lp norm pertur- bations. Note that adversarially trained linear classifier enjoys a bounded population risk which decreases as the number of training iterations t increases. Specifically, when t - co, have
lim P(x.))D(fo, (x) + v) s exp (-c (1lm) - 1el5--44llllly 4ellulla) 10000
(C" +c)++ (-<((((///
))
(4.1)
consider the case when the sample size n is fixed but dimension and || are growing, we discuss the conditions to reach minimum standard risk of noise level 7). Note that when 1 p we have q 2 2 and || || In this case, if || (2d22/4), the standard risk will come close to the noise level 1 when d is sufficiently large. When p > 2 and therefore g < 2, we have || S d-/4-1/2|1a |ll|.. In this case, ||æl|/2 = (2d214) and = pl12/ /////////////////)) the standard risk will come close to the noise level 7) with sufficiently large d. Note that our theorem condition also requires that 14/22 O(vd). Therefore, in order to reach the standard risk of need ||1||| (dd") for some E 1/24.
Remark 4.6. For (4.1
will reduce the standard training case. Specifically, if we set in (4.1). it reduces to the same conclusion as Theorem 3.1 in Chatterji & Long (2020). However, result is more general, as it covers the setting of adversarial training and gives risk bounds for the linear model obtained with a finite number of gradient descent iterations.
Remark 4.7. Choosing
Theorem 4.8 (Adversarial Risk of Adversarial Training). For any å E (0, 1), under the same con- ditions in Theorem 4.4 with probability at least 1 - 6, the adversarially trained linear classifier fo. for sufficiently large under f,-norm e-perturbation satisfies the following adversarial risk 1 S p 2
P PiX Ex's E (x) s.t., fo(x') + y)
-C"' (1111113 1 4e [1alla)) (C" + +evd
C" log n
)
2
< <nt exp
log t
and if > 2,
P(xx))D 3x E (x(( s.l., fo(x') $v] y]
(-c((lel (C" +c"+
(11ml133 - 4e (c11)))lg))
1dI1| logl edt- )
< 1 + exp exp
logt
where C²,C" C" 5 > are absolute constants, 1/p + 1/9
Remark 4.9. Theorem 4.8 shows the adversarial risk of adversarial training under lp norm per- turbations. The major difference from the standard risk (Theorem 4.4) lies in the additional
5

---

Under review as a conference paper at ICLR 2022
ed//9-1/2 term in the exponential function. This aligns with common sense that adversarial risk should always larger than the standard risk. This also suggests that for larger p-norm (p > 2) perturbation, the same magnitude of perturbation would lead to a larger gap between the adversarial risk and the standard risk. In terms of the perturbation strength, we can also observe that with a larger 6, adversarially trained classifiers obtain worse adversarial risk. This has been verified by many empirical observations of adversarial training (Madry et al. 2018, Zhang et al. 2019).
Remark 4.10. Note that when + oo, if S S 2, we have the following adversarial risk bound: -c) 2)
lim I (xx,))>D[> [3x' E fo(x') * w] exp -Ca [Ille]]3 - 4e 4el1 10000
(C" + +e)vd - )
and if p 2, we have
exp - -C" [Ilu1 ( 4cllpella) (C" ccva ed -
lim P(x,))D| Exx E (x), + #y S 1-000
Similar to the standard risk case (Remark 4.6). when p S 2, || O(d') for some r E (1/4, the adversarial risk will also come close to the noise level with sufficiently large d. When p > 2, if we have || = (dd") ) for some r E (1/4, and e = 14122// adversarial risk will be close 77 with sufficiently large d. Note that compared to the standard risk, this requirement on e is slightly stronger.
the
Remark 4.11. Note that our results imply striking fact that unlike those observed in previous stud- ies (e.g.. Rice et al. (2020) showed that overfitting leads to worse empirical robustness on real image distributions), overfitting in adversarial training can be benign for certain distributions. Specifically, Remark 4.10 shows that for linear models with sub-Gaussian mixture data, the overfitting effect is indeed benign. This is later empirically verified in the experiments for both linear and neural network models.
PROOF OUTLINE OF THE MAIN RESULTS
In this section, we present the proofs of our main theorems, which consists of three main steps.
Statistical properties of the training data points. We first list some basic properties of the training data points based on our data model defined in Section 3
Lemma 5.1 (Lemma 4.7 in Chatterji & Long (2020)). Let Z₁- yjxX. There exist absolute con-
stants R, and G and C, such that if the assumptions in Theorem 4.4 hold, then with probability at least 1 8,
d
12 S cod for all [n],
(5.1)
Co
12 ر₁1
S co (1 122 + / /llog(//o) for all i i j.
(5.2)
14" T 2 ||11 < / for all k C,
(5.3)
4 T zn (- ||l1)) < ||m11//2 2 for all & EV,
(5.4)
the number of noisy samples [W] S (n+ ci n, and all training samples are linearly separable, where Co > is an absolute constant.
Lemma 5.1
directly follows Lemma 4.7 in Chatterji & Long 2020). It provides direct high proba- bility bounds for || and μ Zy and also suggests that z vectors are nearly pairwise orthogonal in over- parameterized settings. It also guarantees that training examples are linearly separable with high probability.
Landscape properties of the training objective function. Given the properties of the training data points, we proceed to establish landscape properties of the objective function L(O)). The following lemma bound the loss for the adversarially trained classifier in step 1.
Lemma 5.2. [Theorem 3.4 in Li et al. [0200)] Under the same conditions as in Theorem 4.4 with probability least 1 d, we have L(,,) S 2n, and
L(0 < L(O.).
(5.5)
0 w
Ca logn n
1
<
(5.6)
00111
log t
for all (. 0, where eg is absolute constant.

---

Under review as a conference paper at ICLR 2022
easily observe that the adversarial training loss is bounded by 2n along the entire training trajectory. Lemma 5.2 also suggests that when - oo, the adversarially trained classifier 0, will converge in direction to the max adversarial margin classifier w defined in (3.3).
By Lemma 5.2
Length and direction of the adversarial training iterates 0,. We also establish properties of the adversarial training iterates 0,. We have the following lemmas.
Lemma 5.3. Under the same conditions as Theorem [.4 for all adversarial training iteration
t > O, with probability at least 1 - 6, we have ||0+11l2 S (V<D + +evvd> 2m=o Om am ((0)), where co is the absolute constant in Lemma 5.1
Lemma 5.3
upper bound the L2 norm of adversarially trained classifier Og by the summation of training losses along the training trajectory.
Lemma 5.4. Let Z Y&X under the same conditions as in Theorem for all adversar-
ial training iteration t 2 0. with probability as least 1 - 6, we have max exp( -,, z;) S mink- exp(-0, zz), where > 0 is an absolute constant.
Lemma 5.4 provides us a way to control the loss the noisy examples during the training procedure. Note that if max;= exp(-0, zk) S C3 mink=1 exp(-0,' zz), we also have max;= exp(-0, Z + ellO:Ilg) S C3 m exp(-0, Zi: + E Oll0)ll.). Therefore, the worst example training loss can be bounded via the best example training loss and further be bounded by the average training loss [(.).. In this way, we can guarantee that those noisy examples will not have major influence on model training even in later training stages.
By using Lemmas 5.1 5.4
we establish the following key lemma for our main theorems.
Lemma 5.5. Under the same condition as in Theorem 4.4 with probability at least 1 5, the adversarially trained linear model parameter O₂ satisfies
F 0: 0
C3 1
(Vor+
logt
where co is the absolute constant in Lemma 5.1
Lemma 5.5 provides the lower bound for the inner product of μ and the direction of 0,. This lemma extends Lemma 4.4 in Li al. (2020) by considering the training iteration rather than just the converged classifier w, and also extends to the adversarial training setting. Notice that this lower bound actually gets larger with the increase of iteration t.
Finalizing the proof. We now present the proof for Theorems and 4.8
First, following standard coupling lemma (Lindval] 2002), there always ex- ists joint distribution on original data and noisy data ((x, 17, (x, y)) such that the marginal distri- bution for (x. 7) is D, the marginal distribution for (x, 3) is D, IP[x = = and Ply + øl S n
Proof of Theorem 4.4
Notice that the standard population risk can be written
P P(x.y)=Dfoo. (x) # y] F Px 0,
$ " + P P(xx)) [y 0. < 0, 0,
+ (x. 0. 0].
(5.7)
where the inequality holds since Ply # S n. Since is the clean label for x. :x follows the same distribution as E + f and Ely- Txxi = 0 Therefore, (5.7 can be further written as
F(x.)) (x) + v] < 17 + P (x.x))>D
17 OT x EEg 0,xx] < -0, 0T1ml ml
17 + (xx,))>
[0] (jx E(ixx) 0, [4]
(0) 4)
< n + exp
(5.8)
0
where the last inequality holds by applying a Hoeffding-type Hoe
concentration inequality (Theorem C.I with 1. (0. 11)a. This bound in (5.8) enables the application of Lemma 5.5 which characterizes

---

Under review as a conference paper at ICLR 2022
how the direction of 0, aligns with μr during training. By direct calculation, have
P ((x.))=plfe( (x) # vl S exp (-o( [ ( cllpel1))
e3 l log
2
(voo+c)va
logt
This concludes the proof.
Proof of Theorem 4.8 Similar as in the proof of Theorem we start with calculating an upper bound of the population risk based on the formulation of the label noise. By the definition of the adversarial risk, we have
P(x.))>D Ex' E (x) s.t., (x') # u] = P ((x))) Ex' E (x(x) s.t., y 0 x' < 0]
S 1) + P ((xx))DD Exx E (x s.l., y/ 0 x < 0.y = D1
min ÿ 0. (x u) < 0] uEB((()
17 (x.)))D
1 0, 0 0]
+ PP (xxx))
(5.9)
where the inequality holds in the same way as in (57 Since ÿ is the clean label for x, 7x follows the same distribution μa and Ely 0. x] 0, μ.. Therefore, (5.9) can be further written
F ((x.))D Ex' E (x) s.t., (x') * y] - r + Iº (xx)))D [ 0.1x x Elū 0 x < 0, 1 cl [cll]]
7 + PP (x,))) 00 (ixx Eliix)) 5-07 0. /a [rll
(0, 1 - 0.10)
- r + exp
(5.10)
110.12
where the second inequality holds by applying the Hoeffding-type concentration inequality (Theo- rem C.I with / (0, μ [100glg) )2 Based (5.10) and Lemma 5.5 we can further give bounds
of the adversarial risk. We consider the two settings S < and < oo separately.
When p s 2, we have q 2 2 and |101| S |101|2. In this case, by Lemma 5.5 obtain
((xx)))lff((x) + v) 1 exp (-o ||لاا 4 ellealla) ca callmala log
)
(Veo= +evdd
logt
When p > 2 and therefore < 2, we have obtain
||l|| S d dd/9-2/2|1 pll2. In this case, by Lemma 5.5 we
(
(-o (
1 ellxallo)
callæol1a log ed 2
(-c (V tova log
Poowwoloo,.x + y] S + exp
This concludes the proof.
6 EXPERIMENTS
In this section, experimentally study the behavior of the adversarially trained linear classifier in the over-paranen parameterred regime on synthetic data. Specifically, we generate 50 training samples and 2000 test samples and set the label noise ratio 7 0.1 for all experiments. Each clean sample (x, 7) is drawn from a Gaussian mixture model such that j/ ~ Unif( (=11) and X = ÿ/u + & where & E Rd and E .......Ea Ea are i.i.d. standard Gaussian variables and μa simply shares the same direction as an all-one vector but has various different magnitudes. This aligns with our model assumptions in Section 3 For the adversarial training algorithm, we directly follows Algorithm [ except using more practical Xavier normal initialization (Glorot & Bengio, 2010), i.c.. sampling O, i.i.d. from from (0. 1/)d). We set the learning rate a, = 0.001 and the total number of iterations T = 1000 for all experiments. All results are obtained by averaging over 10 independent runs (both data sampling and training).
In the first of experiments, we verify our main conclusions in this paper, that benign overfitting can occur in adversarial training. Figure | (a-d) illustrates the risk and the adversarial risk of ad- versarially trained linear classifiers versus the dimension d under different scalings of μa for both
8

---

Under review as a conference paper at ICLR 2022
2.24
3.20-
2.40
3.22
3.18-
[all= gh?
0.20-
2 2.28
[el: gf
2.28-
3.44
2.24
9:2--
optinaal
2.22
0.22
3.50
5.50
3.00
530
1200
1500
2000
2300
530
1200
1500
2200
2300
530
1000
1500
2000
2002
Dmmrsson
(a) E perturbation
(b) & perturbation
(c) too perturbation
6.6
0.01
0.22
0.5
gf>
Addeeeadt Rio
[|4]]
ustimul A/
0.23
02-
0.2
0.16
6.3
1300
Ptteratonns
(d) L0 perturbation
(c) & perturbation
(f) foo perturbation
Figure 1: (a-d) Risk and adversarial risk of adversarially trained linear classifiers versus the di- mension d under different scalings of μ.. (a)(b) show the results for lg perturbation with 0.1 and (c) show the results for & perturbation with e = 0.01. (c-f) Adversarial risk of adversarially trained linear classifiers versus the training iterations for different with d 200 and || d0.3 The training error reaches 0 for all experiments.
2z-norm and -nom perturbations. We can observe that when || = d the (adversarial) risk starts increase the dimension d' increases after initial dive for both fo-n and lox -nom perturbations. While for cases where ||م/|| = d and |||||2 = d0.4, we can observe that the (adver- sarial) risk decreases steadily to the optimal risk the dimension d increases. This results backup our theory in Section 4 that the optimal risk is achievable when || = (dd") and r (1/4, 1/2]. Note that the training error reaches O for all settings in Figure [
In Figure (e-f), we present the adversarial risk of adversarially trained linear classifiers versus the training iterations t with different e but fixed dimension d and |||l|22 for both mn-morm and fo -norm perturbations. We can also observe that in general, larger will lead to the worse adversarial risk of the adversarially trained classifier. This also backs up our theory in Theorem 4.8
As our ultimate goal is study the benign overfitting phenomenon in real-world adversarial training settings, we also conducted experiments on 2-layer neural networks with ReLU activation functions. the 2-layer ReLU network suggest very similar trends the linear model. Due to space limit, we display these results in the supplemental materials.
In fact, the performances
7 CONCLUSIONS AND FUTURE WORK
In this paper, we show that the benign overfitting phenomenon also occurs in adversarial training, principled approach to defend against adversarial examples. Specifically, we derive the risk bounds of the adversarially trained linear classifiers and show that under moderate f, no-norm perturbations, they can achieve the near-optimal standard and adversarial risks, despite overfitting the noisy training data. The numerical experimental results also validate our theoretical findings.
Our current analysis is limited to linear classifiers, while in practice, adversarial training com- monly used with neural networks. We believe our work is the first step towards analyzing benign overfitting in adversarially trained neural networks. Yet extending our current analysis adversari- ally trained neural networks is highly non-trivial and we leave it as a future work.
REFERENCES
Zeyuan Allen-Zhu and Yuanzhi Li. Feature purification: How adversarial training performs robust deep learning. arXiv preprint arXiv:2005. 10/90, 2020.
Here we omit the plot for standard risk the curves are essentially overlapping to cach other.

---

Under review as a conference paper at ICLR 2022
Sanjeev Arora, Nadav Cohen, Wei Hu, and Yuping Luo. Implicit regularization in deep matrix factorization. Advances in Neural Information Prucessing Systems, 32, 2019.
Peter L. Bartlett, Philip M Long. Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 117(49):3003333007 2020.
Mikhail Belkin, Siyuan Ma, and Soumik Mandal. To understand deep learning we need to under- stand kernel learning. In International Conference Machine Learning, pp. 541-549. PMLR, 2018.
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine- learning practice and the classical bias-variance trade-off. Proceedings of the National Academy of Sciences,
2019a.
Mikhail Belkin, Daniel Hsu. and Ji Xu. Two models of double descent for weak features. arXiv preprint arXiv:1903.07577 07571,, 2019b.
Yuan Cao, Quanquan Gu, and Mikhail Belkin. Risk bounds for over-paraaeteriize maximum mar- gin classification sub- gaussian mixtures. arXiv preprint arXiv:2104.13626 2021.
Yair Carmon, Aditi Raghunathan, Ludwig Schmidt, John C Duchi, and Percy S Liang, Unlabeled data improves adversarial robustness. In NeurlPS, pp. 11192-11203, 2019.
Zachary Charles, Shashank Rajput, Stephen Wright, and Dimitris Papailiopoulos, Convergence and
margin of adversarial training on separable data. arXiv preprint arXiv: (9t.:09999999 2019.
Niladri Chatterji and Philip M Long. Finite-sample analysis of interpolating linear classifiers in the overparameterized regime. arXiv preprint arXiv:2004. 12019, 2020.
Lin Chen, Yifei Min, Mingrui Zhang, and Amin Karbasi. More data can expand the generalization gap between adversarially robust and standard models. In International Conference on Machine Learning, pp. 1670-1680. PMLR, 2020.
Daniel Cullina, Arjun Nitin Bhagoji, and Prateek Mittal. Pac-learning in the presence of evasion adversaries. Proceedings of the 32nd International Conference on Neural Information Processing Systems, 2018.
Chen Dan, Yuting Wei, and Pradeep Ravikumar. Sharp statistical guaratees for adversarially ro- bust gaussian classification. In International Conference on Machine Learning, pp. 2345-2355. PMLR, 2020.
Ilias Diakonikolas, Daniel M Kane, and Pasin Manurangsi. The complexity of adversarially robust proper learning of halfspaces with agnostic noise. Advances in Neural Information Processing Systems, 2020.
Edgar Dobriban, Hamed Hassani, David Hong, and Alexander Robey. Provable tradeoffs in adver- sarially robust classification. arXiv preprint (xXi:20006.05161, 2020.
Alhussein Fawzi, Hamza Fawzi, and Omar Fawzi. Adversarial vulnerability for any classifier. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pp. 1186-1195, 2018
Ruiqi Gao, Tianle Cai, Haochuan Li, Cho-Jui Hsich, Liwei Wang, and Jason Lee. Convergence of adversarial training in overparametrized neural networks. Advances in Neural Information Processing Systems, 32:13029-13044 2019.
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the thirteenth international conference on artificial intelligence and statistics, pp. 249-2569 JMLR Workshop and Conference Proceedings, 2010.
Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. ICLR, 2015.
Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro. Characterizing implicit bias in terms of optimization geometry. In International Conference on Machine Learning, pp. 1832- 1841. PMLR, 2018a.
10

---

Under review as a conference paper at ICLR 2022
Suriya Gunasekar, Blake Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, and Nathan Sre- bro. Implicit regularization matrix factorization. In 2018 Information Theory and Applications Workshop (ITA), pp. 1-10. IEEE, 2018b.
Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan Tibshirani. Surprises in high- dimensional ridgeless least squares interpolation. arXiv preprint
2019.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. CVPR, pp. 770-778, 2016.
Geoffrey Hinton, Li Deng, Dong Yu, George Dahl, Abdel-rahman Mohamed, Navdeep Jaitly, An- drew Senior, Vincent Vanhoucke, Patrick Nguyen, Brian Kingsbury, al. Deep neural networks for acoustic modeling in speech recognition. IEEE Signal processing magazine, 29, 2012.
Adel Javanmard and Mahdi Soltanolkotabi. Precise statistical analysis of classification accuracies for adversarial training. arXiv preprint arXiv:2010.12213, 2020.
Ziwei Ji and Matus Telgarsky. Gradient descent aligns the layers of deep linear networks. In International Conference Learning Representations, 2019a
Ziwei Ji and Matus Telgarsky. The implicit bias of gradient descent on nonseparable data. In Conference on Learning Theory, pp. 1772-1798. PMLR, 2019b.
Alex Krizhevsky, Nya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convo- lutional neural networks. In Neurips, pp. 1097-1105, 2012.
Alexey Kurakin, Ian Goodfellow, and Samy Bengio. Adversarial examples in the physical world. arXiv preprint 1rXiv:667.02253: 2016.
Yan Li, Ethan X.nang, Huan Xu, and Tuo Zhao. Implicit bias of gradient descent based adversarial training on separable data. In International Conference on Learning Representations, 2020.
Torgny Lindvall. Lectures on the coupling method. Courier Corporation, 2002.
Kaifeng Lyu and Jian Li. Gradient descent maximizes the margin of homogeneous neural networks. 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. ICML, 2018.
Omar Montasser, Surbhi Goel, Ilias Diakonikolas, and Nathan Srebro. Efficiently learning adver- sarially robust halfspaces with noise. In International Conference on Machine Learning, pp. 7010-7021. PMLR, 2020.
Mor Shpigel Nacson, Nathan Srebro, and Daniel Soudry. Stochastic gradient descent on separable data: Exact convergence with fixed learning rate. In The 22nd International Conference Artificial Intelligence and Statistics, pp. 3051-3059. PMLR, 2019.
Behnam Neyshabur. Implicit regularization in deep learning. arXiv preprint arXiv:1799.0195, 2017.
Aditi Raghunathan, Sang Michael Xie, Fanny Yang, John Duchi, and Percy Liang. Understanding and mitigating the tradeoff between robustness and accuracy. arXiv preprint arXiv:2002.10711 2020.
Leslie Rice, Eric Wong, and J Zico Kolter. Overfitting in adversarially robust deep learning. ICML., 2020.
Amartya Sanyal, Puneet K. Dokania, Varun Kanade, and Philip Torr. How benign benign overfit- ting? ? In International Conference on Learning Representations, 2021.
Ludwig Schmidt, Shibani Santurkar, Dimitris Tsipras, Kunal Talwar, and Aleksander Madry. Ad-
versarially robust generalization requires more data. Advances in Neural Information Processing Systems, 2018.
11

---

Under review as a conference paper at ICLR 2022
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The im- plicit bias of gradient descent on separable data. The Journal of Machine Learning Research, 19 (1):2822-2878, 28788, 2018.
Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. arXiv preprint arXiv:1312.6199, 2013.
Hossein Taheri, Ramtin Pedarsani, and Christos Thrampoulidis. Asymptotic behavior of adversarial training in binary classification. arXiv preprint arXiv:2010.132733 2020.
Alexander Tsigler and Peter L Bartlett. Benign overfitting in ridge regression. arXiv preprint
arXiv:2009. 14286, 2020.
Dimitris Tsipras, Shibani Santurkar, Logan Engstrom, Alexander Turner, and Aleksander Madry. Robustmess may be at odds with accuracy. In International Conference on Learning Representa- tions, 2019.
Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices. arXiv preprint arX1v:1011.3027, 2010.
Ke Wang and Christos Thrampoulidis. Benign overfitting in binary classification of gaussian mix- tures. In ICASSP 202/-2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp.
IEEE, 2021.
Yisen Wang, Xingjun Ma, James Bailey, Jinfeng Yi, Bowen Zhou, and Quanquan Gu. On the convergence and robustness of adversarial training. In ICMI, pp. 6586-6595, 2019.
Yisen Wang, Difan Zou, Jinfeng Yi, James Bailey, Xingjun Ma, and Quanquan Gu. Improving adversarial robustness requires revisiting misclassified examples. In International Conference on Learning Representations, 2020.
Boxi Wu, Jinghui Chen, Deng Cai, Xiaofei He, and Quanquan Gu. Do wider neural networks really help adversarial robustness? arXiv preprint arXiv:2010.01229, 2020.
Denny Wu and Ji Xu. On the optimal weighted & regularization in overparameterized linear regres- sion. Advances in Neural Information Processing Systems, 33, 2020.
Yao-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, 2020.
Dong Yin, Ramchandran Kannan, and Peter Bartlett Rademacher complexity for adversarially robust generalization. In International Conference on Machine Learning, pp. 7085-7094, PMLR, 2019.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. In International Conference on Learning Rep- resentations, 2017.
Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric Xing, Laurent El Ghaoui, and Michael Jordan. Theoretically principled trade-off between robustness and accuracy. In ICML, pp. 7472-7482, 2019.
Xiao Zhang, Jinghui Chen, Quanquan Gu, and David Evans. Understanding the intrinsic robust- ness of image distributions using conditional generative models. In International Conference on Artificial Intelligence and Statistics, pp. 3883-3893. PMLR, 2020a.
Yi Zhang, Orestis Plevrakis, Simon S Du, Xingguo Li, Zhao Song, and Sanjeev Arora. Over- parameterized adversarial training: An analysis overcoming the curse of dimensionality. Ad- vances in Neural Information P Processing Systems, 2020b.
Difan Zou, Spencer Frei, and Quanquan Gu. Provable robustness of adversarial training for learning halfspaces with noise. International Conference on Machine Learning, 2021.
12

---

Under review as a conference paper at ICLR 2022
A COMPARISON WITH DAN ET AL. (2020), TAHERI ET AL. (2020) AND JAVANMARD SOLTANOLKOTABI (2020)
Dan al. 2220) proposed an adversarial signal to noise ratio and studied the excess risk lower/upper bounds for learning Gaussian mixture models. Compared to the setting studied in Dan et al. (2020) our setting covers additional label flipping noises. More importantly we study an estimator found by gradient descent that overfits the training data, while Dan et al. (2020) studied a specific plug-in estimator which does overfit the training data. Due these difterences, there is discrepancy in the risk bounds derived in both papers.
Taheri al. 2020) Javanmard & Soltanolkotabi 2020 studied adversarial learning of linear mod- els in the proportional limit setting, Le., d/n O(1). this setting, the data Gram matrix and the sample covariance matrix be studied based on random matrix theory/Gaussian comparison inequalities/convex Gaussian min-max theorem. In contrast, our setting where Ö(n²), the sample covariance matrix is singular but the n x Gram matrix concentrates around its expecta- tion. Therefore, our setting different from the proportional limit setting in Taheri al. (2020); Javanmard & Soltanolkotabi (2020), and these results are not directly comparable.
B
PROOF OF KEY TECHNICAL LEMMAS
B.1 PROOF OF LEMMA 5.2
Proof. We first prove that L(O;)= S 2n. To show this, we observe that 0, ag Σk= Zg. Therefore
n
I(O1)=
Σ
exp(
0 2x + <(1011la)
Σ exp
0n Σ 2, Eu age Σ Zi
i=1
agn (agn(co Can(co((lea))) (1le111112+ + vdlog(n/0)) + eveod)
exp
k=
exp(1/16) S 2n,
k=
where the first equality holds due to Lemma 5.1 and the fact that for any Rdd, ||u|| S ||u/| S Vdllulla. while the second inequality is by the choice of sufficiently small og and the assumptions that d 2 Cnllual and < R for some absolute constants C' and R.
The rest part of Lemma 5.2 summarizes parts of the results in Li ct al. (2020). However, the results in Li et al. 2020))
derived under the setting that | 2|2 < I, Therefore to prove lemma 5.2
re-scale our data and model parameters and convert our setting to the setting in Li et al. (2020).
By lemma 5.1 with probability at least 1 - 6, ||x; _ < and for all i [n]. We therefore denote B = cyd, and then X; := X, B has fg-norm less than or equal to one. Further denote by B, the linear model parameters in Li et al. (2020)'s algorithm, 2; y, tu as their step sizes, as their perturbation strength, and
max min 0 x; 011==11E EE
the ep margin. Then the adversarial training update rule in Li et al. (2020)) is
B Br
11x
V Vxepp( -3,
BTTz. nx + B,).))))
n
Note that our update rule
0,+1 O, at
Vo expp-0,1 0. 24 =l(O,1lo))
13

---

Under review as a conference paper at ICLR 2022
Now in order to apply the results in Since
Li al. 2020),
convert parameters match their scaling.
0.41 = 0, ---a at _
Vo
nBa
0,
(B0) exp( B0, n + < B0, 1l B).
n
Therefore
nB2ar an
B0 B0:
(Bo)
2ς/ c/ 1lg/ / B).
n
easy to observe that we can now apply Theorem 3.3 and Theorem 3.4 in et al. 2020) by setting 3r B0,, 77: n, c/ Moreover, by X; x; x//B, B, 7. we have y = 7/ B. Based on these relations, it is easy to see that under the conditions Lemma 5.2 x, T/, 7 satisfy the assumptions of Theorems 3.3 and 3.4 in Li et al. 20220. Now (5.5) is an
c/ B and the definition of
intermediate result the proof of Theorem 3.3 Li al. (2020), and (5.6) follows by Theorem 3.4
in Li et al. (2020).
B.2 PROOF OF LEMMA 5.3
Proof. We have
|0 l12 = Σ am VL(0m)
m=0
am
VL((m))l
m=0
Σ Z - al00mll)) eep (- 2m
pm + eel0mlll))
Oem
where the first three inequality hold by triangle inequality. By Lemma C.2 we have
10+1 2 -
Zu 2l + +vvd) exp ( 2 0m + =m
am
m==
< (Voo Ve
exp ( 2 Om + +e =l)0mllag)
Omm
m=0
k=
= =(Vo+
Om L00m)
where the second inequality is due to Lemma 5.1
B.3 PROOF OF LEMMA 5.4
Proof. We will prove this lemma by induction.
Let's denote E = exp(-0f (T.TT.TT... zz). Without loss of generality, let E denotes the maximum of {E))R=) and ES denotes the minimum of {E) We also define A, == E Eg and the goal is to show that A, < 5c3.
For the base
0), we have F. =xxp(0) 1. Therefore have Ao S 5cg
14

---

Under review as a conference paper at ICLR 2022
For t > 0, notice that
A411 exp( 11)
-:p(-0/21) 21)
exp(a, (L(0))
exp( 0.4122) (22
exp(-0, z2)
exp(o, VI(0,)
A exp( (x:
04 Ek=1 (Zs: - - (lg))) 21 exp( 02 ns (110x
exp(-00 01 2 "1
k= (Zs: e0110:)
exp(-00 0, 2₁ 0(
exp( exp
01 (8) 0z (1)
exp(-00 02 24 (l0))ln))
A.
exp( 10:0-a (z (Z2 - ed 0: 1,) 22 exp( 0, 2n + +.(ll))))
11
exp(- (0(--a 04 Eizz (zt c0
T
21 exp(-(f 2₁z + +c(00llg))
(B.1)
exp(- 11---a 04
En k (7k 00
Z2 exp( -0pp 2₁ + c(0ell))
For term J1 note that by Lemma 5.1
we have
S 12xll S vodd.
Also since by Lemma C.2 we have @ =1
12 0|10 < 2xlll |0110.1a = 1|zlll S || S Vallaul12 S Vend.
(B.2)
Therefore, have
- - evood) exp(- 0,,-0,,2, + +e(0011l) + a (cod evood) exp( 0, + ellOblle)
41 S exp
C0
(- - ---evood) Ar ( exp (el10)1lo)
exp
(B.3)
For term
I2. by (..2 and [.2 we have
I2 S exp
ar co(1 + Vdlog(n/8)) + (vood) (Σ
exp(- 0, 24 + <((0ellg) +
Σ
exp(
0, 24 + c((0:ll)))
ligh
< exp
(2., co (1 + /dlog((/0)) + evcol
(B.4)
Substitute (B.3 and B.4 into
B.I have
- La, (at vood) (cod+ + eveod) exp (e110:1l))
A+t1 5 Ar exp
20. (10(1 + V /dlog(//8) + e
exp
(B.5)
Let us consider two cases here. If - - A, - (cod + <v/nd) > and, i.e., A₁ > (2cg + < /11//o -,/o),, we further have
A411 A, exp ( a Fbcodeepp (e (el16rll)) exp (000)())) Vdlog(n/0)) (v
< A . exp
- EaEyddd exp ex (el(0rll))
2a,nE (11(11111 Vdlog(n/6)) + evaad) exp (c100)1l))
exp
-xp
(aarEsculd -2n|| 2n log((//) 2nc exp (cl0
Ab
15

---

Under review as a conference paper at ICLR 2022
where the second inequality is due the fact that L(O,) Ex= E exp (cl(0)lag) and E max; Fg while the last inequality holds since d 2 C max (n) | log(n/5))-
On the other hand, if A I (2co eVeo) EvCo). we have
A4t1 S cxp
( cv/od) exp (cl(0:11a)
exp (0. (1111 Vdlog(n/o)) + <veod)
(.,( +ooodd++/vo +c exp (0.)( (co(llu] v log((//)) + /end)
< A. - exp
(2am (2) + 2 dlog(n/6) d) 3r 3e
$ A. exx
S (2c0 EV/o)/(L/oo cVco) exp(1/8)
where the first inequality is due to the fact that A, > 0, the third inequality holds by Lemma 5.2 the fourth inequality is because a₁ (/(CCnnd) and d 2 C max,n [ n² log(n/6)} and the last inequality is because < C" and C" can be chosen such that C' I 1/(2c) 1-) and we have
1/co-
c/Co 1/(2))..
This concludes the proof.
B.4 PROOF OF LEMMA 5.5
Proof. Note that
T 0.+1 =
(0: -T
a: Σ [zx e0110)1lg) exp(- 0,īzz 2ạ + <c10112))
k=
= 1 JuTo 0; - -at . 1 Tallolll L(O,) + a Σ (H T 2xx exp(-0; 2 + el101la)
k=1
2 1 To, 02 anel//l1o L(O,) + Σ (u zx) exp( 0, z2 +c|101la))
REC
Σ (ITTZn) expl- 0,7 <(101la)
(B.6)
BEN
where the inequality holds in the same way as in B.2 By Lemma 5.1 (1.3)) bound (B.6) by
5.3) and 5.4 ) we further
M 2 TT.. 0, axclllally I(OI) + 0t Σ
|M| exp( 0 25 + c(01k
exxp(00
2
REC
3a:
Σ
111/ exepppp0 0,¹ 2ạ + +e(l0l1)))
2
KEN
μ 0, arel|1lly L(O,) + oi (1111/L(0)) 2a mall Σ
exp( exp(-0,1 2 + +c|10llg)
keN
(B.7)
Note that we have
Σ
exp(- -0, 2/ c(11)))=
Σ exp(-ee 0, 2ς) exp(c||01lg)
REN
KEN
c3((n +i)n (max Fix) exp(c
$ cs(n + (c)
1
< 8
((0.).
16

---

Under review as a conference paper at ICLR 2022
where the first inequality is due Lemma 5.2 and the last inequality is because 7 1/C and be chosen arbitrarily small given sufficient large C. Therefore, (B.7) can be further written as
# 0ut1 2 0, arcl|zell L(O,)
Ct || [l.))
at rl ((1))(0,)
4
|1al - eclxull))
= =p 0, + ai
L(O,)
4
| ellsello
Σ
Om L(Om),
(B.8)
m00
where the last equality is due the fact that 0g = O. Now we multiply of (.8)) and take + 00
|w/l2//|0++11B ll2 on both sides
| Oet1)
|1
|/ ||2
lim
lim
elleelle
0'm
L(0m)
1
110++1112
m=0
Since |/w||2 L, and by Lemma
5.2 it is easy to observe that lim
01/1/0/12,, we have
||al12
E amm L(0m)
1 w
2
elleella)
lim +-
101+1112
1
4
(veo+ +ova
where the last inequality due to Lemma w|12 S c3 log log I, we have
5.3
Note that Lemma 5.2 also suggests that |0,/||0|||
02
O2
11
u
+
|10:1|
00
||
0₂
/1 0,
14
2
||0:1] 12
0
ca
|
log
1a O,
logt
0
Therefore,
O
C3 131|a1 logn
|
C3 sa||ee logn
el|allaa
0.1l2
log
(Veo e)vd
log
C AUXILIARY LEMMAS
Theorem C.1 (Proposition 5. in Vershynin (2010). Let X1, X2,..., Xa be independent centered sub-Gaussian random variables, and max, Xill Then for every a = (a), 02 .0. .n.) E Rn and for every & 0, have
Σ
ax >1) I exp (- 1=1
Ct2
K2l
where > is a constant.
Lemma C.2. For any Rdd
|01011a11 < Vd, |10101111|, = 1.
Proof. Note that have
8 89-1
01)))))):
sign( (0),
|
17

---

Under review as a conference paper at ICLR 2022
<- 0.01
0.6
c- 0.001
0.2
0.5
0.02
0.4
optimal risk
optimal risk
Adversarial
Adversarial
0.4
0.3
0.3
0.2
0.2
0.1
0.1
800
1000
200
400
#lterations
#fiter
(a) & perturbation
(b) 8oc perturbation
Figure 2: Risk and adversarial risk of adversarially trained linear classifiers versus the training iterations 1 for different perturbation level The label noise level is set as 7) 0.1, the training size n 50, dimension 200 and || = d The train error reaches for all experiments.
0.6
0.01
0.001
< 0.1
0.6
= 0.01
optimal risk
Adversarial Risk
optimal risk
Adversarial
0.4
0.3
0.2
0.2
0.1
800
1000
200
1080
elterations
Viterations
(a) E2 perturbation
(b) fxx perturbation
Figure 3: Risk and adversarial risk of adversarially trained linear classifiers versus the training iterations for different perturbation level e. The label noise level is set as 17 = 0.1, the training set size n 50, dimension d = 1000 and ||/4|/2 = n0.3 The train error reaches O for all experiments.
and since for any vector u E IRd, ||un| 2 ||u|| -o. ||l||| - Vdl|ullao, we have
||00 11
vallon= <vd.
|llllla ll
19-
|010
where o denotes element-wise power. This concludes the first part the lemma. For the second part, by p-norm definition have
|10(0~2111
10 1/p
2// 9-1
|010%
(0
0
1.
11018-1
10
10110-1
D ADDITIONAL EXPERIMENTS
In this section, we present the additional experiments covering more settings as well as more com- plex models such as 2-layer neural network.
D.1 ADVERSARIALLY TRAINED LINEAR CLASSIFIER UNDER VARIOUS SETTINGS
plot the adversarial risk of adversarially trained linear classifiers versus the training iterations / for different perturbation level e for various combinations of dimension d and ||ll|| Specifically, in Figure over-parameeterizatoon, adversarially trained linear classifiers can achieve near-optimal adversarial risks.
In Figures 4
observe that with moderate perturbations and sufficient
18

---

Under review as a conference paper at ICLR 2022
0.40
= 0.01
0.50
c= 0.001
0.35
0.2
0.40
0.02
optimal rick
optimal
0.30
Adversafall
0.35
Adversanal
0.25
0.25
0.15
0.15
0.10
200
400
600
800
1000
200
400
6.00
800
1000
#lterations
+lterations
(a) Eg perturbation
(b) fxx perturbation
Figure 4: Risk and adversarial risk of adversarially trained linear classifiers versus the training iterations for different perturbation level e. The label noise level is set as 17 = 0.1, the training set size n = 50, dimension 1000 and ||l|| d0.4, The train error reaches 0 for all experiments.
0.20
0.22
0.20
df?
0.18
Mkllaa df
0.16
MMl d
lbil gat
0.16
[kll dPA
dP
0.14
optimal
0.12
0.12
500
1000
15000
2000
2500
500
1000
1500
2000
2500
Dimension
Dimension
(a) & perturbation
(h) E perturbation
0.300
0.275
0.250
Nolle m de
0.225
lesi] m de2
Rik
pplla
l[ele = da3
0.200
0.14
optimal nsc
0.175
leela d*
optimal risk
0.12
0.150
0.125
0.10
0.100
500
1000
1500
2000
2500
500
1000
1500
2000
2500
Dimension
Dimension
(c) for perturbation
(d) E. perturbation
Figure 5: Risk and adversarial risk of adversarially trained 2-layer ReLU network versus the di- mension under different scalings of μ.. (a)() show the results for la perturbation with 0.1 and (c)(d) show the results for fo perturbation with 0.01. The training error reaches 0 for all experiments.
D.2 ADVERSARIALLY TRAINED 2-LAYER NEURAL NETWORKS
We have also conducted extra experiments on 2-layer neural networks with ReLU activation func- tions (one extra fix-dimension hidden layer). The data generation process are the same our linear experiments. Note that this setting, we no longer have the dlosed-form solutions to the inner max- imization problem. Therefore, we following Madry et al. (2018) and use 10-step Projected Gradient Descent to get the inner maximizer.
As can be seen from Figure 5 trends the linear classifier for both adversarial risks and standard risks. This further backs up our theoretical conclusions.
the empirical results on 2-layer ReLU network suggest very similar
19


Reviews:
[{"review_id": "sYzVa4Shox_", "reviewer": "Reviewer_V6MB", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "The problem discussed in this paper is very essential in machine learning, and the method of analysis will be useful for future reference.\nThe authors show that the upper bound of adversarial risk under adversarial training becomes similar to the standard risk under adversarial training. \n\nHowever, I could not how the theoretical result relates to the \"benign\" or optimality.  \n- In this context, what does the \"benign\" means?\n- Are there lower bounds on both of adversarial risk under adversarial training and the standard risk under adversarial training?\n- Do the upper bound match the lower bounds? I would like to see a clearer explanation of the connection between the two.  \n\nThe result just implies that the upper bound under adversarial risk matches that under standard risk, but this does not imply the \"benign overfitting\" because there is a possibility that the upper bounds are not tight.\n\nMinor:\nHolders' -> Hölder's?", "summary_of_the_paper": "Learning with an over-parametrized model is an important problem in machine learning, and the benign overfitting problem garnered attention. The results shown in this paper has a significant implication in this context. In this paper, the authors investigate the phenomenon of benign overfitting in adversarial training. Surprisingly, the authors report that the benign overfitting phenomenon can be observed even in the case where we use adversarial training. The authors' approach is reasonable and should serve as a reference for future research.", "summary_of_the_review": "This paper studies a very interesting setting. The approach is meaningful and can be used for future reference. However, I could not understand the extent to which the authors' claim of \"benign overfitting\" is supported. Therefore, I vote weak reject. If this point becomes clear to me and readers, I will raise the score to acceptance.", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "IOUzN8U1RM", "reviewer": "Reviewer_7uYN", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "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": "The main claim of the paper is that benign overfitting occurs in the adversarial case as well--that is, even though the training data are overfit perfectly, one can still attain reasonable generalization error. However, in practice it is well-documented that overfitting is indeed worse for adversarially-trained models, so I think an adequate analysis in this case would explain this phenomenon. I was not able to get such an explanation from the paper, although I may have missed it.\n\nAside from explaining empirical results, another potential contribution of theory papers is introducing new proof techniques. The paper does not include a discussion of what new technical contributions or proof techniques it contributes, so it was difficult to assess this aspect. While there is a proof outline in Section 5, it is not clear what is novel and what follows the previous proofs.", "summary_of_the_paper": "The paper considers the analysis of benign overfitting in linear regression, first described in Bartlett et al. (2020), and extends it to the case of adversarial linear classification. Previously, Chatterji & Long (2020) had studied the non-adversarial classification case, so the main new result is an extension to the adversarial case.", "summary_of_the_review": "I did not feel the paper made significant empirical or explanatory contributions, and was unable to assess the theoretical contributions. I thus overall would recommend against accepting the paper.", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "HGIjeKGVapa", "reviewer": "Reviewer_kp1N", "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": "This paper studies the \"Benign Overfitting\" phenomena in the setting of linear classification of sub-gaussian mixtures. Precise risk upper bounds are provided for adv-training of linear classifiers under exponential loss.\n\nOverall, this paper is well-written and the technical results look correct to me (although I did not check the details very carefully). The setting of interest is an important first step towards understanding overparameterized models - it generalizes the prior works to the sub-Gaussian mixture setting.\n\nHowever, there are a few weaknesses, summarized below.\n\n(1) Important references missing: there are a few recent papers that studied very similar settings which the authors weren't aware of:\nICML 2020, Sharp Statistical Guarantees for Adversarially Robust Gaussian Classification, by Chen Dan, Yuting Wei, Pradeep Ravikumar\nhttps://arxiv.org/abs/2010.11213: Precise Statistical Analysis of Classification Accuracies for Adversarial Training, by Adel Javanmard, Mahdi Soltanolkotabi\nhttps://arxiv.org/abs/2010.13275: Asymptotic Behavior of Adversarial Training in Binary Classification, by Hossein Taheri, Ramtin Pedarsani, Christos Thrampoulidis\nAll of these papers studied a Gaussian setting (which is a special case of the sub-Gaussian setting studied in this work). The latter two papers also worked on overparameterized models under d/n = \\Theta(1) regime, which is slightly different from this paper (their results are stronger in certain aspects and weaker in some other aspects).\n\nI think a detailed comparison with these works is very necessary and may help readers understand the contribution and novelty better.\n\nIn particular, I have a few questions regarding the differences with these papers: \n(1a) In Dan et al. 2020 (mentioned above), the authors proposed a notion called \"adversarial signal-to-noise ratio\", which measures the difficulty of adversarially robust classification in the Gaussian setting (a special case of this work). If my calculation was correct, for isotropic Gaussian mixture with l_inf perturbations, \n$$AdvSNR = \\|\\mu\\|_2 - \\epsilon \\|\\mu\\|_1 $$\nSince the minimum error is roughly exp(-O(AdvSNR^2)), which roughly translates to \n$$\\exp(-C*(\\|\\mu\\|_2^2 - 2 \\epsilon \\|\\mu\\|_1\\|\\mu\\|_2))$$ \nin the risk bound. However, in this work (theorem 4.4 and 4.8), the risk bound has the form of\n$$\\exp(-C*(\\|\\mu\\|_2^2 - 4 \\epsilon \\|\\mu\\|_1) - C'\\|\\mu\\|_2 )$$ \nCan you explain this discrepancy? Is this a typo, or something more fundamental, like (I) the difference between Gaussian and sub-Gaussian or (II) the specific behavior of adv-trained classifiers that are different from information-theoretically optimal classifiers?\n\n(1b) In Javanmard et al. 2020 and Taheri et al. 2020, the authors of both papers analyzed the setting of Gaussian mixtures in the d/n=O(1) setting. However, the analysis in this work (see theorem 4.4) requires d>= C*n^2 log(n), which is quite heavily overparameterized. To me, the proportional d/n=O(1) setting appears to be much more natural (although this may be my personal taste), and I think the analysis in this work isn't showing the complete story due to this requirement - it will be great if we can understand the behavior of adv training in the sub-quadratic overparameterization regime. \n\n(2) There doesn't appear to be much clear take-away from the theoretical results. While this paper is written clearly, it is a little too dry, and the lacking of take-aways limits the impact on the whole field of adversarial robustness. Besides, some of the behaviors that appeared in this work contradict empirical evidence for deep neural networks. \nFor example, one of the main messages conveyed by this paper is that overfitting is benign in adversarial training. However, this is clearly not true for deep neural networks, as observed by Rice et al. 2020. This discrepancy takes the validity/usefulness of the setting studied into question.\n", "summary_of_the_paper": "This paper studies the \"Benign Overfitting\" phenomena in the setting of linear classification of sub-gaussian mixtures. Precise risk upper bounds are provided for adv-training of linear classifiers under exponential loss.", "summary_of_the_review": "I like the theoretical results. However, some more detailed comparisons with prior works, along with take-aways for practitioners, are necessary to make this paper better.", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "0C0x1UhCbvI", "reviewer": "Reviewer_AeLK", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "Strength\n\nThe behaviour of overparameterised models in the presence of noise when trained with adversarial training is certainly a very important problem as both of these components(overparameterisation and noise) are important components in the ML context.\n\nThe analysis is clean and simple. The results are interpretable and  confirm the intuitions that one has about this problem,\n\nWeaknesses\n\nThe proofs rely very heaviliy on Li. et. al. 2020 and Chhaterji et. al. 2020, which raises questions about the technical novelty of the paper. In particular it relies heavily on the characterisation of the GAT solution in Li. et. al. 2020 and the characterisation of test error in the presence of noise in Chatterji et. al. 2020. \n\nThe paper also deals with a simple linear model and it is not immediately clear how it relates to overparameterised neural networks. While it is important to first understand a complex phenomenon theoretically on a linear model, in the absence of  a huge amount of novelty in the theory, I find this second drawback rather glaring.\n\n\n[1] \"Implicit bias of gradient descent based adversarial training on separable data\", Yan Li, Ethan X. Fang, Huan Xu, and Tuo Zhao, ICLR 2020.\n\n[2] \"Finite sample analysis of interpolating linear classifiers in the overparameterized regime\", Niladri S Chatterji and Philip M Long.\n\n\n========Update=============\n\nI have read the author's response. It didn't change my view on the paper as the authors did not provide any new information. However, I would still recommend acceptance of the paper based on my initial evaluation of the paper.  The problem is important and the results while, might appear a bit derivative and for a simple setting, it might be necessary to first look at this simple setting to get a better progress.", "summary_of_the_paper": "This paper studies the clean test and adversarial test error obtained using   _Gradient Descent Adversarial Training_ (GDAT). The data distribution is the gaussian mixture model and the hypothesis class is lilinear classifiers.\n\nIn Theorem 4.4, the authors show that the clean test error is worse than than the inherent noise rate. However, benign overfitting still exists though a larger $\\epsilon$ for the adversarial training hurts clean error.\n\nIn Theorem 4.8, the authors upper bound the robust test error obtained by GDAT. The result shows that adversarial error is certainly worse off than clean test error. Perhaps somewhat interesting this also shows that the perturbation radius needs to decrease with increasing $d$.\n\n", "summary_of_the_review": "In short, I found the problem interesting and the solution clean and understandable.\n\nHowever, the technical novelty in the work is relatively low and it mainly involves combining existing works in a smart way. I would urge the authors to either extend the theoretical results eg. by looking into more complex hypothesis classes or to improve the experimental work.", "strength_and_weaknesses": "", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies the benign overfitting phenomenon for linear models with adversarial training. The main issue is that the result is quite expected for experts versed in the benign overfitting papers, and indeed the reviewers pointed out that they could not see much technical novelty. However, even more importantly, the original benign overfitting papers had the advantage of proposing of simpler model (linear!!!) with the same behavior as the complex ones in practice. This is not the case here, as the result diverge from empirical observations on deep networks. The authors argue that it is a valuable finding that the empirical observation is not "universal", but this is a somewhat moot point as linear models are a priori very very different from the setting in which these empirical observations were made. For these reasons I believe the paper does not meet the bar for ICLR (yet it could still be publishable elsewhere).
Decision: Reject