Year: 2021

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 `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.

heading: 1 INTRODUCTION
text: Modern machine learning methods such as deep learning have made many breakthroughs in a variety of application domains, including image classification (He et al., 2016; Krizhevsky et al., 2012), speech recognition (Hinton et al., 2012) and etc. These models are typically over-parameterized: the number of model parameters far exceeds the size of the training samples. One mystery is that, these over-parameterized models can memorize noisy training data and yet still achieve quite good generalization performances on the test data (Zhang et 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 al., 2019; Gunasekar et al., 2018b;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 regularization. Specifically, Soudry et al. (2018); Ji & Telgarsky (2019b); Nacson et al. (2019) demonstrate that gradient descent trained linear classifiers on logistic or exponential loss with no regularization asymptotically converge to the maximum L2 margin classifier. Recent works (Bartlett et al., 2020; Chatterji & Long, 2020; Cao et al., 2021; Wang & Thrampoulidis, 2021; Tsigler & Bartlett, 2020) further shows that over-parameterized and implicitly regularized interpolators can indeed achieve small test error, and formulate this phenomenon as “benign overfitting”. More concretely, suppose the classification model f is parameterized by θ ∈ Θ and the loss is denoted as `(·). The population risk is define as
P(x,y)∼D[fθ(x) 6= y],
where data pair (x, y) is generated from certain data generation model. Chatterji & Long (2020) shows that with sufficient over-parameterization, gradient descent trained maximum L2 margin classifier can achieve nearly optimal population risk on noisy data for data generated from a sub-Gaussian mixture model. This suggests that the overfitting can be “benign” in the overparameterized setting.
Besides these studies on the benign overfitting phenomenon, another well-known feature of modern machine learning methods is that they are vulnerable to adversarial examples. Recent studies (Szegedy et al., 2013; Goodfellow et al., 2015) show that modern machine learning systems are brittle: slight input perturbation that is imperceptible to human eyes could mislead a well-trained classifier into wrong classification result. These malicious inputs are also known as the adversarial
examples (Szegedy et al., 2013; Goodfellow et al., 2015). Adversarial examples raise severe trustworthy issues and security concerns on the current machine learning systems especially in securitycritical 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 examples. One of the notable approaches is adversarial training (Madry et al., 2018). Specifically, adversarial training solves the following min-max optimization problem,
min θ∈Θ
1
n n∑ i=1 max x′i∈B p (xi) `(fθ(x ′ i), yi),
where {(xi, yi)}ni=1 is the training set and Bp (xi) = {x : ‖x−xi‖p ≤ } denotes the -ball around xi in `p norm (p ≥ 1). Many empirical or theoretical studies have been conducted trying to analyze or further improve adversarial training robustness (Zhang et al., 2019; Rice et al., 2020; Wang et al., 2020; Carmon et al., 2019; Wang et al., 2019; Raghunathan et al., 2020). A recent work (Sanyal et al., 2021) also pointed out that normally trained interpolators with the presence of label noise are unlikely to be adversarially robust, while adversarially robust classifiers cannot overfit noisy labels under certain conditions. However, it is still not clear whether the benign overfitting phenomenon occurs for extremely over-parameterized 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:
P(x,y)∼D [ ∃x′ ∈ Bp (x) s.t., fθ(x′) 6= y ] .
The adversarial risk measures the misclassification rate of the target classifier under the presence of `p-norm 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 `p norm ball.
We summarize our contributions of this paper in the following
• We show that the benign overfitting phenomenon can occur in adversarially robust linear classifiers with sufficient over-parameterization. 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 0, our adversarial risk bound reduces to the standard one. The resulting standard risk bound extends Chatterji & Long (2020)’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 p (perturbation norm), the adversarial risk bound can be different. The higher value of p (typically for p ≥ 2 case) actually leads to a larger gap between the adversarial risk and the standard risk with the same .
Notation. we use lower case letters to denote scalars and lower case bold face letters to denote vectors. For a vector x ∈ Rd, we denote its `p norm (p ≥ 1) of x by ‖x‖p = (∑d i=1 |xi|p )1/p , the `∞ norm of x by ‖x‖∞ = maxdi=1 |xi|. We denote x◦p as the element-wise p-power of x. For p ≥ 1, we denote Bpr (x) as the `p norm ball of radius r centered at x. Given two sequences {an} and {bn}, we write an = O(bn) if there exists a constant 0 < C < +∞ such that an ≤ C bn. We denote an = Ω(bn) if bn = O(an). We denote an = Θ(bn) if an = O(bn) and an = Ω(bn).

heading: 2 RELATED WORK
text: 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; Goodfellow et al., 2015). And many attempts have been made to understand its empirical success. Charles et al. (2019); Li et al. (2020) showed that the adversarially trained linear classifier directionally converges to the maximum margin classifier. Gao et al. (2019); Zhang et al. (2020b) showed that adversarial training with neural networks can achieve low robust training loss. Yet these conclusions cannot explain the test (population) performances. Another line of research focuses on the generalization performance of adversarial training
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. (2020) showed that more data may actually increase the gap between the generalization error of adversarially-trained 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 et al., 2020; Yang et al., 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 (Fawzi et al., 2018; Zhang et al., 2020a).
Recently, some works also focus on studying the learning of robust halfspaces and linear models. Montasser et al. (2020) studied the conditions on the adversarial perturbation sets under which halfspaces are robustly learnable in the presence of random label noise. Diakonikolas et al. (2020) studied the computational complexity of adversarially robust halfspaces under `p norm perturbations. Zou et al. (2021) showed that adversarially trained halfspaces are provably robust with low robust classification 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 et al. (2020); Javanmard & Soltanolkotabi (2020) studied adversarial learning of linear models on Gaussian mixture data where the data dimension and the number of training data points have a fixed ratio.
Implicit Bias. Several recent works studied the implicit bias of various training algorithms in overparameterized 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 et al. (2018a) studied the implicit bias of various optimization methods in linear regression and classification problems. Ji & Telgarsky (2019a) 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 (2020) 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 overfitting” phenomenon Bartlett et al. (2020) that when training over-parameterized models, classifiers 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-parameterized linear (ridge) regression and showed that under certain settings, the interpolating linear model with minimum parameter norm can have asymptotically optimal risk. Chatterji & 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. (2019); Wu & Xu (2020) further quantified the dependency curve between the population risk and the degree of over-parameterization and showed that the curve has a double-descent shape.

heading: 3 PROBLEM SETTING AND PRELIMINARIES
text: We consider a sub-Gaussian mixture data generation model in our work. Specifically, the clean data (x̃, ỹ) ∼ D̃ is generated such that, for each data point (x̃, ỹ) ∈ Rd×{±1}, we have ỹ ∼ Unif({±1}) and x̃ = ỹµ + ξ where ξ ∈ Rd and ξ1, ξ2, . . . , ξd are i.i.d. zero-mean sub-Gaussian variables with sub-Gaussian 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 × {±1} who has the same marginal distribution on Rd and the total variation distance dTV(D, D̃) ≤ η where η denotes the noise level.
Note that our data generation model is standard for studying the population risk of overparameterized linear classification. In fact, it is exactly the same as the one studied in Chatterji & Long (2020). In this model, following standard coupling lemma (Lindvall, 2002), there always exists a joint distribution on original data and noisy data ((x̃, ỹ), (x, y)) such that the marginal distribution for (x̃, ỹ) is D̃, the marginal distribution for (x, y) is D, P[x = x̃] = 1 and P[y 6= ỹ] ≤ η. In this paper, we study the problem of robust binary classification with training data {(xi, yi)}ni=1 drawn i.i.d. from the distribution D. Let’s denote the “clean” sample index as C := {k : yk = ỹk} and the “noisy” sample index as N := {k : yk 6= ỹk}. We consider the adversarially trained linear
Algorithm 1 Gradient Descent Adversarial Training 1: input: Training data {xi, yi}ni=1, number of training iterations T , maximum perturbation
strength , training step sizes αt; 2: initialize model parameter θ0 = 0 3: for t = 1, . . . , T do 4: for each {xi, yi} do 5: x′i = argmaxx′i∈B p (xi)
exp(−yiθ>t−1x′i) 6: end for 7: θt = θt−1 − αt · ∇θL(θt−1) 8: end for
classifier under exponential loss. In such case, the adversarial loss can be explicitly written as
L(θ) = n∑ i=1 max x′i∈B p (xi) exp(−yiθ>x′i). (3.1)
In gradient descent adversarial training algorithm, the adversarial loss L(θ) is minimized by first solving the inner maximization problem in (3.1) with respect to the current model parameter θt−1 and then update the model parameter θt by performing gradient descent to minimize the adversarial loss in each iteration. We summarized the training procedure for gradient descent adversarial training1 in Algorithm 1. Note that in the linear classifier setting, the inner maximization problem in (3.1) has the following property
argmax x′i∈B p (xi) exp(−yiθ>x′i) = argmax ui∈Bp (0) exp(−yiθ>(xi + ui)) = argmin ‖ui‖p≤ yiθ >ui. (3.2)
By Hölders’ inequality it is easy to observe that the optimal adversarial loss and the corresponding gradient can be written as
L(θ) = n∑ i=1 exp(−yiθ>xi + ‖θ‖q),∇θL(θ) = − n∑ i=1 (yixi − · ∂‖θ‖q) exp(−yiθ>xi + ‖θ‖q),
where 1/p+1/q = 1. Also note that in the over-parameterized 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 a positive margin (with high probability). Following Li et al. (2020), we also define the standard and adversarial margin as
γ̄ := max ‖θ‖q=1 min i∈[n]
yiθ >xi, γ := max
‖θ‖2=1 min i∈[n] min x′i∈B p (xi)
yiθ >x′i, (3.3)
which are useful in our later analysis. We also define the unique linear classifier θ that achieves adversarial margin γ defined above as w.

heading: 4 MAIN RESULTS
text: 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 a constant R and is smaller than the `p data margin γ̄, i.e., ≤ min{R, γ̄}.
The goal of adversarial training is to obtain high-accuracy classifiers that are also robust to small input perturbations which can be ignored by human beings (e.g., small `∞-norm perturbations that are 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 E[‖ξ‖22] ≥ κd for some constant κ.
Assumption 4.2 is a common condition that has also been considered in Chatterji & Long (2020). It ensures that the summation of 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 or equal to κ.
1Note that in practice people often initialize θ0 by a small random vector (e.g., Xavier initialization (Glorot & Bengio, 2010)), while we follow Li et al. (2020) and set θ0 = 0 for the ease of theoretical analysis.
Assumption 4.3. The gradient descent starts at 0, and the step sizes are set as α0 = 1/(Gdn), αt = α ≤ 1/(GdnM) for M = max{[2d + (q − 1)d 3q−2 2q−2 /γ] exp(−γ2/(Gd) + /G), 1} and a constant G.
Assumption 4.3 summarizes our assumptions about the gradient descent algorithm on the adversarial loss. The learning rate conditions here are to ensure the convergence of adversarial training, and is inspired by Li et al. (2020).
We first present our theorem for standard risk of adversarial training method (Algorithm 1). Theorem 4.4 (Standard Risk of Adversarial Training). For any p ∈ [1,+∞), suppose that Assumptions 4.1, 4.2 and 4.3 hold with κ ∈ (0, 1] and large enough constants R and G. Moreover, for any δ ∈ (0, 1), suppose the number of training samples n ≥ C log(1/δ), the dimension d ≥ C ·max{n‖µ‖22, n2 log(n/δ)}, the noise level η < 1/C, and ‖µ‖22 ≥ C max{log(n/δ), ‖µ‖q} for a large enough constant C. Then with probability at least 1−δ, adversarially trained linear classifier fθt for sufficiently large t under `p-norm -perturbation satisfies the following standard risk
P(x,y)∼D[fθt(x) 6= y] ≤ η + exp
( − C ′ ((‖µ‖22 − 4 ‖µ‖q) (C ′′ + ) √ d − C ′′′‖µ‖2 log n log t )2) ,
where C ′, C ′′, C ′′′ > 0 are absolute constants, 1/p+ 1/q = 1. Remark 4.5. Theorem 4.4 presents the standard risk of adversarial training under `p norm perturbations. Note that adversarially trained linear classifier enjoys a bounded population risk which decreases as the number of training iterations t increases. Specifically, when t→∞, we have
lim t→∞ P(x,y)∼D[fθt(x) 6= y] ≤ η + exp
( − C ′ ((‖µ‖22 − 4 ‖µ‖q) (C ′′ + ) √ d )2) . (4.1)
Remark 4.6. For (4.1), consider the case when the sample size n is fixed but dimension d and ‖µ‖2 are growing, we discuss the conditions to reach minimum standard risk of noise level η. Note that when 1 ≤ p ≤ 2 we have q ≥ 2 and ‖µ‖q ≤ ‖µ‖2. In this case, if ‖µ‖2 = Ω(d1/4), the standard risk will come close to the noise level η when d is sufficiently large. When p > 2 and therefore q < 2, we have ‖µ‖q ≤ d1/q−1/2‖µ‖2. In this case, if ‖µ‖2 = Ω(d1/4) and = O(‖µ‖2/d1/q−1/2), the standard risk will come close to the noise level η with sufficiently large d. Note that our theorem condition also requires that ‖µ‖2 = O( √ d). Therefore, in order to reach the standard risk of η, we need ‖µ‖2 = Θ(dr) for some r ∈ (1/4, 1/2]. Remark 4.7. Choosing = 0 will reduce to the standard training case. Specifically, if we set = 0 in (4.1), it reduces to the same conclusion as Theorem 3.1 in Chatterji & Long (2020). However, our 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. Theorem 4.8 (Adversarial Risk of Adversarial Training). For any δ ∈ (0, 1), under the same conditions as in Theorem 4.4, with probability at least 1 − δ, the adversarially trained linear classifier fθt for sufficiently large t under `p-norm -perturbation satisfies the following adversarial risk if 1 ≤ p ≤ 2
P(x,y)∼D [ ∃x′ ∈ Bp (x) s.t., fθ(x′) 6= y ] ≤ η + exp ( − C ′ ((‖µ‖22 − 4 ‖µ‖q) (C ′′ + ) √ d − C ′′′‖µ‖2 log n log t − )2) ,
and if p > 2, P(x,y)∼D [ ∃x′ ∈ Bp (x) s.t., fθ(x′) 6= y ] ≤ η + exp ( − C ′ ((‖µ‖22 − 4 ‖µ‖q) (C ′′ + ) √ d − C ′′′‖µ‖2 log n log t − d 1 q− 1 2 )2) ,
where C ′, C ′′, C ′′′ > 0 are absolute constants, 1/p+ 1/q = 1. Remark 4.9. Theorem 4.8 shows the adversarial risk of adversarial training under `p norm perturbations. The major difference from the standard risk (Theorem 4.4) lies in the additional or
d1/q−1/2 term in the exponential function. This aligns with common sense that adversarial risk should always be 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 , 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 t→∞, if 1 ≤ p ≤ 2, we have the following adversarial risk bound:
lim t→∞
P(x,y)∼D [ ∃x′ ∈ Bp (x), fθ(x′) 6= y ] ≤ η + exp ( − C ′ ((‖µ‖22 − 4 ‖µ‖q) (C ′′ + ) √ d − )2) ,
and if p > 2, we have
lim t→∞
P(x,y)∼D [ ∃x′ ∈ Bp (x), fθ(x′) 6= y ] ≤ η + exp ( − C ′ ((‖µ‖22 − 4 ‖µ‖q) (C ′′ + ) √ d − d 1 q− 1 2 )2) .
Similar to the standard risk case (Remark 4.6), when 1 ≤ p ≤ 2, if ‖µ‖2 = Θ(dr) for some r ∈ (1/4, 1/2], the adversarial risk will also come close to the noise level η with sufficiently large d. When p > 2, if we have ‖µ‖2 = Θ(dr) for some r ∈ (1/4, 1/2] and = O(‖µ‖2/d1/q), the adversarial risk will be close to η with sufficiently large d. Note that compared to the standard risk, this requirement on is slightly stronger. Remark 4.11. Note that our results imply a striking fact that unlike those observed in previous studies (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.

heading: 5 PROOF OUTLINE OF THE MAIN RESULTS
text: 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 zk = ykxk. There exist absolute constants R, κ and G and C, such that if the assumptions in Theorem 4.4 hold, then with probability at least 1− δ,
d c0 ≤ ‖zk‖22 ≤ c0d for all k ∈ [n], (5.1)
|z>i zj | ≤ c0 ( ‖µ‖22 + √ d log(n/δ) ) for all i 6= j, (5.2) |µ>zk − ‖µ‖22| ≤ ‖µ‖22/2 for all k ∈ C, (5.3) |µ>zk − (−‖µ‖22)| ≤ ‖µ‖22/2 for all k ∈ N , (5.4)
the number of noisy samples |N | ≤ (η+c1)n, and all training samples are linearly separable, where c0 > 1 is an absolute constant.
Lemma 5.1 directly follows Lemma 4.7 in Chatterji & Long (2020). It provides direct high probability bounds for ‖zk‖2 and µ>zk and also suggests that zk 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(θ1). The following lemma bound the loss for the adversarially trained classifier in step 1. Lemma 5.2. [Theorem 3.4 in Li et al. (2020)] Under the same conditions as in Theorem 4.4, with probability at least 1− δ, we have L(θ1) ≤ 2n, and
L(θt+1) ≤ L(θt), (5.5)
1− θ > t w
‖θt‖2 ≤ c3 log n log t (5.6)
for all t > 0, where c3 is an absolute constant.
By Lemma 5.2, one can easily observe that the adversarial training loss is bounded by 2n along the entire training trajectory. Lemma 5.2 also suggests that when t → ∞, the adversarially trained classifier θt will converge in direction to the max adversarial margin classifier w defined in (3.3).
Length and direction of the adversarial training iterates θt. We also establish properties of the adversarial training iterates θt. We have the following lemmas. Lemma 5.3. Under the same conditions as in Theorem 4.4, for all adversarial training iteration t > 0, with probability at least 1 − δ, we have ‖θt+1‖2 ≤ ( √ c0 + ) √ d ∑t m=0 αmL(θm), where c0 is the absolute constant in Lemma 5.1.
Lemma 5.3 upper bound the L2 norm of adversarially trained classifier θt by the summation of training losses along the training trajectory. Lemma 5.4. Let zk = ykxk, under the same conditions as in Theorem 4.4, for all adversarial training iteration t ≥ 0, with probability as least 1 − δ, we have maxnk=1 exp(−θ>t zk) ≤ c3 min n k=1 exp(−θ>t zk), where c3 > 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 maxnk=1 exp(−θ>t zk) ≤ c3 min n k=1 exp(−θ>t zk), we also have maxnk=1 exp(−θ>t zk+
‖θt‖q) ≤ c3 minnk=1 exp(−θ>t zk + ‖θt‖q). Therefore, the worst example training loss can be bounded via the best example training loss and further be bounded by the average training loss L(θt). 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 − δ, the adversarially trained linear model parameter θt satisfies
µ>θt ‖θt‖2
≥ ( ‖µ‖22
4 − ‖µ‖q
) 1
( √ c0 + ) √ d − c3‖µ‖2 log n log t .
where c0 is the absolute constant in Lemma 5.1.
Lemma 5.5 provides the lower bound for the inner product of µ and the direction of θt. This lemma extends Lemma 4.4 in Li et al. (2020) by considering the training iteration t 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 4.4 and 4.8.
Proof of Theorem 4.4. First, following standard coupling lemma (Lindvall, 2002), there always exists a joint distribution on original data and noisy data ((x̃, ỹ), (x, y)) such that the marginal distribution for (x̃, ỹ) is D̃, the marginal distribution for (x, y) is D, P[x = x̃] = 1 and P[y 6= ỹ] ≤ η. Notice that the standard population risk can be written as
P(x,y)∼D[fθt(x) 6= y] = P(x,y)∼D[y · θ>t x < 0] ≤ η + P(x,y)∼D[y · θ>t x < 0, y = ỹ] = η + P(x,y)∼D[ỹ · θ>t x < 0], (5.7)
where the inequality holds since P[y 6= ỹ] ≤ η. Since ỹ is the clean label for x, ỹx follows the same distribution as ξ + µ and E[ỹ · θ̂>x] = θ̂>µ. Therefore, (5.7) can be further written as
P(x,y)∼D[fθt(x) 6= y] ≤ η + P(x,y)∼D [ ỹ · θ>t x− E[ỹ · θ>t x] < −θ>t µ ] = η + P(x,y)∼D [ θ>t ( ỹx− E[ỹx] ) < −θ>t µ
] ≤ η + exp ( − c (θ > t µ) 2
‖θt‖22
) , (5.8)
where the last inequality holds by applying a Hoeffding-type concentration inequality (Theorem C.1) with t = (θ>t µ) 2. This bound in (5.8) enables the application of Lemma 5.5 which characterizes
how the direction of θt aligns with µ during training. By direct calculation, we have
P(x,y)∼D[fθt(x) 6= y] ≤ η + exp
( − c ((‖µ‖22 4 − ‖µ‖q )
( √ c0 + ) √ d − c3‖µ‖2 log n log t
)2) .
This concludes the proof.
Proof of Theorem 4.8. Similar as in the proof of Theorem 4.4, we start with a 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,y)∼D [ ∃x′ ∈ Bp (x) s.t., fθt(x′) 6= y ] = P(x,y)∼D[∃x′ ∈ Bp (x) s.t., y · θ>t x′ < 0] ≤ η + P(x,y)∼D[∃x′ ∈ Bp (x) s.t., y · θ>t x′ < 0, y = ỹ]
= η + P(x,y)∼D [
min u∈Bp (0)
ỹ · θ>t (x + u) < 0 ]
= η + P(x,y)∼D [ ỹ · θ>t x− ‖θt‖q < 0 ] , (5.9)
where the inequality holds in the same way as in (5.7). Since ỹ is the clean label for x, ỹx follows the same distribution as ξ + µ and E[ỹ · θ>t x] = θ>t µ. Therefore, (5.9) can be further written as
P(x,y)∼D [ ∃x′ ∈ Bp (x) s.t., fθt(x′) 6= y ] ≤ η + P(x,y)∼D [ ỹ · θ>t x− E[ỹ · θ>t x] < −θ>t µ + ‖θt‖q ] = η + P(x,y)∼D [ θ>t ( ỹx− E[ỹx] ) < −θ>t µ + ‖θt‖q
] ≤ η + exp ( − c (θ > t µ− ‖θt‖q)2
‖θt‖22
) , (5.10)
where the second inequality holds by applying the Hoeffding-type concentration inequality (Theorem C.1) with t = (θ>t µ− ‖θt‖q)2. Based on (5.10) and Lemma 5.5, we can further give bounds of the adversarial risk. We consider the two settings 1 ≤ p ≤ 2 and 2 < p <∞ separately. When 1 ≤ p ≤ 2, we have q ≥ 2 and ‖θ‖q ≤ ‖θ‖2. In this case, by Lemma 5.5 we obtain
P(x,y)∼D[fθt(x) 6= y] ≤ η + exp
( − c ((‖µ‖22 4 − ‖µ‖q )
( √ c0 + ) √ d − c3‖µ‖2 log n log t − )2) .
When p > 2 and therefore q < 2, we have ‖µ‖q ≤ d1/q−1/2‖µ‖2. In this case, by Lemma 5.5 we obtain
P(x,y)∼D[fθt(x) 6= y] ≤ η + exp
( − c ((‖µ‖22 4 − ‖µ‖q )
( √ c0 + ) √ d − c3‖µ‖2 log n log t − d 1 q− 1 2
)2) .
This concludes the proof.

heading: 6 EXPERIMENTS
text: In this section, we experimentally study the behavior of the adversarially trained linear classifier in the over-parameterized regime on synthetic data. Specifically, we generate 50 training samples and 2000 test samples and set the label noise ratio η = 0.1 for all experiments. Each clean sample (x̃, ỹ) is drawn from a Gaussian mixture model such that ỹ ∼ Unif({±1}) and x̃ = ỹµ+ ξ where ξ ∈ Rd and ξ1, ξ2, . . . , ξd are i.i.d. standard Gaussian variables and µ 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 1 except using a more practical Xavier normal initialization (Glorot & Bengio, 2010), i.e., sampling θ0 i.i.d. from fromN (0, 1/ √ d). We set the learning rate αt = 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 set of experiments, we verify our main conclusions in this paper, that benign overfitting can occur in adversarial training. Figure 1 (a-d) illustrates the risk and the adversarial risk of adversarially trained linear classifiers versus the dimension d under different scalings of µ for both
`2-norm and `∞-norm perturbations. We can observe that when ‖µ‖2 = d0.2, the (adversarial) risk starts to increase as the dimension d increases after an initial dive for both `2-norm and `∞-norm perturbations. While for cases where ‖µ‖2 = d0.3 and ‖µ‖2 = d0.4, we can observe that the (adversarial) risk decreases steadily to the optimal risk η as the dimension d increases. This results backup our theory in Section 4 that the optimal risk is achievable when ‖µ‖2 = Θ(dr) and r ∈ (1/4, 1/2]. Note that the training error reaches 0 for all settings in Figure 1.
In Figure 1 (e-f), we present the adversarial risk2 of adversarially trained linear classifiers versus the training iterations t with different but fixed dimension d and ‖µ‖2 for both `2-norm and `∞-norm perturbations. We can also observe that in general, a 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 to study the benign overfitting phenomenon in real-world adversarial training settings, we also conducted experiments on 2-layer neural networks with ReLU activation functions. In fact, the performances on the 2-layer ReLU network suggest very similar trends as the linear model. Due to space limit, we display these results in the supplemental materials.

heading: 7 CONCLUSIONS AND FUTURE WORK
text: In this paper, we show that the benign overfitting phenomenon also occurs in adversarial training, a principled approach to defend against adversarial examples. Specifically, we derive the risk bounds of the adversarially trained linear classifiers and show that under moderate `p-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 is commonly 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 to adversarially trained neural networks is highly non-trivial and we leave it as a future work.

heading: A COMPARISON WITH DAN ET AL. (2020), TAHERI ET AL. (2020) AND JAVANMARD SOLTANOLKOTABI (2020)
text: Dan et al. (2020) 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 not overfit the training data. Due to these differences, there is a discrepancy in the risk bounds derived in both papers.
Taheri et al. (2020); Javanmard & Soltanolkotabi (2020) studied adversarial learning of linear models in the proportional limit setting, i.e., d/n = O(1). In this setting, the data Gram matrix and the sample covariance matrix can be studied based on random matrix theory/Gaussian comparison inequalities/convex Gaussian min-max theorem. In contrast, in our setting where d > Õ(n2), the sample covariance matrix is singular but the n × n Gram matrix concentrates around its expectation. Therefore, our setting is different from the proportional limit setting in Taheri et al. (2020); Javanmard & Soltanolkotabi (2020), and these results are not directly comparable.

heading: B PROOF OF KEY TECHNICAL LEMMAS

heading: B.1 PROOF OF LEMMA 5.2
text: Proof. We first prove that L(θ1) ≤ 2n. To show this, we observe that θ1 = α0 ∑n k=1 zk. Therefore
L(θ1) = n∑ k=1 exp(−θ>1 zk + ‖θ1‖q)
= n∑ k=1 exp ( − α0 n∑ i=1 z>i zk + α0 ∥∥∥ n∑ i=1 zi ∥∥∥ q )
≤ n∑ k=1 exp ( α0n ( c0 ( ‖µ‖22 + √ d log(n/δ) ) + √ c0d ))
≤ n∑ k=1 exp(1/16) ≤ 2n,
where the first equality holds due to Lemma 5.1 and the fact that for any u ∈ Rd, ‖u‖q ≤ ‖u‖1 ≤√ d‖u‖2, while the second inequality is by the choice of sufficiently small α0 and the assumptions that d ≥ Cn‖µ‖22 and ≤ R for some absolute constants C and R. The rest part of Lemma 5.2 summarizes parts of the results in Li et al. (2020). However, the results in Li et al. (2020) are derived under the setting that ‖xi‖2 ≤ 1, Therefore to prove lemma 5.2, we 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 − δ, ‖xi‖22 ≤ c0d for all i ∈ [n]. We therefore denote B := √ c0d, and then x̃i := xi/B has `2-norm less than or equal to one. Further denote by βt the linear model parameters in Li et al. (2020)’s algorithm, z̃i = yix̃i, ηt as their step sizes, ̃ as their perturbation strength, and
γ̃ := max ‖θ‖2=1 min i∈[n]
yiθ >x̃i
as the `p margin. Then the adversarial training update rule in Li et al. (2020) is
βt+1 = βt − ηt n n∑ i=1 ∇β exp(−β>t z̃k + ̃‖βt‖q).
Note that our update rule is
θt+1 = θt − αt n∑ k=1 ∇θ exp(−θ>t zk + ‖θt‖q).
Now in order to apply the results in Li et al. (2020), we convert our parameters to match their scaling. Since
θt+1 = θt − αt ∑ i ∇θ exp(−Bθ>t zk/B + ‖Bθt‖q/B)
= θt − nBαt n ∑ i ∇(Bθ) exp(−Bθ>t zk/B + ‖Bθt‖q/B).
Therefore
Bθt+1 = Bθt − nB2αt n ∑ i ∇(Bθ) exp(−Bθ>t zk/B + ‖Bθt‖q/B).
It is easy to observe that we can now apply Theorem 3.3 and Theorem 3.4 in Li et al. (2020) by setting βt = Bθt, ηt = nB2αt, ̃ = /B. Moreover, by x̃i = xi/B, ̃ = /B and the definition of γ̃, we have γ̃ = γ̄/B. Based on these relations, it is easy to see that under the conditions of Lemma 5.2, x̃i, ηt, ̃, γ̃ satisfy the assumptions of Theorems 3.3 and 3.4 in Li et al. (2020). Now (5.5) is an intermediate result of the proof of Theorem 3.3 in Li et al. (2020), and (5.6) follows by Theorem 3.4 in Li et al. (2020).

heading: B.2 PROOF OF LEMMA 5.3
text: Proof. We have
‖θt+1‖2 = ∥∥∥∥ t∑ m=0 αm · ∇L(θm) ∥∥∥∥ 2
≤ t∑
m=0
αm‖∇L(θm)‖2
≤ t∑
m=0
αm ∥∥∥∥ n∑ k=1 ( zk − · ∂‖θm‖q ) · exp ( − z>k θm + ‖θm‖q )∥∥∥∥ 2 ,
where the first three inequality hold by triangle inequality. By Lemma C.2, we have
‖θt+1‖2 ≤ t∑
m=0
αm n∑ k=1 (‖zk‖2 + √ d) · exp ( − z>k θm + ‖θm‖q ) ≤ ( √ c0 + ) √ d
t∑ m=0 αm n∑ k=1 · exp ( − z>k θm + ‖θm‖q ) = ( √ c0 + ) √ d
t∑ m=0 αmL(θm),
where the second inequality is due to Lemma 5.1.

heading: B.3 PROOF OF LEMMA 5.4
text: Proof. We will prove this lemma by induction.
Let’s denote Etk = exp(−θ>t zk). Without loss of generality, let Et1 denotes the maximum of {Etk}nk=1 and Et2 denotes the minimum of {Etk}nk=1. We also define At := Et1/Et2 and the goal is to show that At ≤ 5c20. For the base case (t = 0), we have E0k = exp(0) = 1. Therefore we have A0 = 1 ≤ 5c20.
For t > 0, notice that
At+1 = exp(−θ>t+1z1) exp(−θ>t+1z2) = exp(−θ>t z1) exp(−θ>t z2) · exp(αt∇L(θt) >z1) exp(αt∇L(θt)>z2)
= At · exp(−αt
∑n k=1(zk − ∂‖θt‖q)>z1 · exp(−θ>t zk + ‖θt‖q))
exp(−αt ∑n k=1(zk − ∂‖θt‖q)>z2 · exp(−θ>t zk + ‖θt‖q))
= At · exp(−αt(z1 − ∂‖θt‖q)>z1 · exp(−θ>t zk + ‖θt‖q)) exp(−αt(z2 − ∂‖θt‖q)>z2 · exp(−θ>t zk + ‖θt‖q))︸ ︷︷ ︸
I1
· exp(−αt
∑n k 6=1(zk − ∂‖θt‖q)>z1 · exp(−θ>t zk + ‖θt‖q))
exp(−αt ∑n k 6=2(zk − ∂‖θt‖q)>z2 · exp(−θ>t zk + ‖θt‖q))︸ ︷︷ ︸
I2
. (B.1)
For term I1, note that by Lemma 5.1 we have√ d
c0 ≤ ‖zk‖2 ≤
√ c0d.
Also since by Lemma C.2, we have ∥∥∂‖θt‖q∥∥p = 1,
|z>k ∂‖θt‖q| ≤ ‖zk‖q · ∥∥∂‖θt‖q∥∥p = ‖zk‖q ≤ ‖zk‖1 ≤ √d‖zk‖2 ≤ √c0d. (B.2)
Therefore, we have I1 ≤ exp ( − αt ( d c0 − √ c0d ) exp(−θ>t z1 + ‖θt‖q) + αt ( c0d+ √ c0d ) exp(−θ>t z2 + ‖θt‖q) )
= exp ( − αtEt2 (( d c0 − √ c0d ) At − ( c0d+ √ c0d )) exp ( ‖θt‖q )) . (B.3)
For term I2, by (5.2) and (B.2) we have I2 ≤ exp ( αt ( c0 ( ‖µ‖22 + √ d log(n/δ) ) + √ c0d )( n∑
k 6=1 exp(−θ>t zk + ‖θt‖q) + n∑ k 6=2 exp(−θ>t zk + ‖θt‖q) ))
≤ exp ( 2αtL(θt) ( c0 ( ‖µ‖22 + √ d log(n/δ) ) + √ c0d ))
(B.4)
Substitute (B.3) and (B.4) into (B.1), we have
At+1 ≤ At · exp ( − αtEt2 (( d c0 − √ c0d ) At − ( c0d+ √ c0d )) exp ( ‖θt‖q ))
· exp ( 2αtL(θt) ( c0 ( ‖µ‖22 + √ d log(n/δ) ) + √ c0d )) . (B.5)
Let us consider two cases here. If (d/c0 − √ c0d)At − (c0d + √ c0d) > c0d, i.e., At > (2c0 +
√ c0)/(1/c0 − √ c0), we further have
At+1 ≤ At · exp ( − αtEt2c0d exp ( ‖θt‖q )) · exp ( 2αtL(θt) ( c0 ( ‖µ‖22 + √ d log(n/δ) ) + √ c0d ))
≤ At · exp ( − αtEt2c0d exp ( ‖θt‖q )) · exp ( 2αtnE t 2 ( c0 ( ‖µ‖22 + √ d log(n/δ) ) + √ c0d ) exp ( ‖θt‖q
)) = At · exp ( − αtEt2c0 ( d− 2n‖µ‖22 − 2n √ d log(n/δ)− 2n √ c0 ) exp ( ‖θt‖q
)) ≤ At,
where the second inequality is due to the fact that L(θt) = ∑n k=1E t k exp ( ‖θt‖q ) and Et2 = maxk E t k while the last inequality holds since d ≥ C ·max{n‖µ‖22, n2 log(n/δ)}. On the other hand, if At ≤ (2c0 + √ c0)/(1/c0 − √ c0), we have
At+1 ≤ At · exp ( αtE t 2 ( c0d+ √ c0d ) exp ( ‖θt‖q )) · exp ( 2αtL(θt) ( c0 ( ‖µ‖22 + √ d log(n/δ) ) + √ c0d ))
≤ At · exp ( αtL(θt) ( c0d+ √ c0d )) · exp ( 2αtL(θt) ( c0 ( ‖µ‖22 + √ d log(n/δ) ) + √ c0d ))
≤ At · exp ( 2αtn ( c0 ( 2‖µ‖22 + 2 √ d log(n/δ) + d ) + 3 √ c0d )) ≤ (2c0 + √ c0)/(1/c0 − √ c0) · exp(1/8)
≤ 5c20, where the first inequality is due to the fact that At > 0, the third inequality holds by Lemma 5.2, the fourth inequality is because αt ≤ 1/(c0Cnd) and d ≥ C · max{n‖µ‖22, n2 log(n/δ)} and the last inequality is because < C ′ and C ′ can be chosen such that C ′ ≤ 1/(2c1.50 ) and we have 1/c0 − √ c0 > 1/(2c0).
This concludes the proof.

heading: B.4 PROOF OF LEMMA 5.5
text: Proof. Note that
µ>θt+1 = µ > ( θt + αt n∑ k=1 ( zk − ∂‖θt‖q ) exp(−θ>t zk + ‖θ‖1) ) = µ>θt − αt · µ>∂‖θt‖q · L(θt) + αt
n∑ k=1 ( µ>zk ) exp(−θ>t zk + ‖θ‖q) ) ≥ µ>θt − αt ‖µ‖q · L(θt) + αt
∑ k∈C ( µ>zk ) exp(−θ>t zk + ‖θ‖q) ) + αt
∑ k∈N ( µ>zk ) exp(−θ>t zk + ‖θ‖q) ) , (B.6)
where the inequality holds in the same way as in (B.2). By Lemma 5.1 ((5.3) and (5.4)), we further bound (B.6) by
µ>θt+1 ≥ µ>θt − αt ‖µ‖q · L(θt) + αt 2 ∑ k∈C ‖µ‖22 exp(−θ>t zk + ‖θ‖q) )
− 3αt 2 ∑ k∈N ‖µ‖22 exp(−θ>t zk + ‖θ‖q) )
= µ>θt − αt ‖µ‖q · L(θt) + αt 2 ‖µ‖22L(θt)− 2αt‖µ‖22 ∑ k∈N exp(−θ>t zk + ‖θ‖q) ) .
(B.7)
Note that we have∑ k∈N exp(−θ>t zk + ‖θ‖q) = ∑ k∈N exp(−θ>t zk) · exp( ‖θ‖q)
≤ c3(η + c1)n · (
max k Ek
) · exp( ‖θ‖q)
≤ c3(η + c1)L(θt)
≤ 1 8 L(θt),
where the first inequality is due to Lemma 5.2 and the last inequality is because η < 1/C and c1 can be chosen arbitrarily small given sufficient large C. Therefore, (B.7) can be further written as
µ>θt+1 ≥ µ>θt − αt ‖µ‖q · L(θt) + αt 2 ‖µ‖22L(θt)− αt 4 ‖µ‖22L(θt)
= µ>θt + αt
( ‖µ‖22
4 − ‖µ‖q
) · L(θt)
=
( ‖µ‖22
4 − ‖µ‖q
) · t∑ m=0 αmL(θm), (B.8)
where the last equality is due the fact that θ0 = 0. Now we multiply ‖w‖2/‖θt+1‖2 on both sides of (B.8) and take t→∞
lim t→∞ ‖w‖2(µ>θt+1) ‖θt+1‖2 ≥ lim t→∞
( ‖µ‖22
4 − ‖µ‖q ) ‖w‖2 ‖θt+1‖2 · t∑
m=0
αmL(θm).
Since ‖w‖2 = 1, and by Lemma 5.2, it is easy to observe that w = limt→∞ θt/‖θt‖2, we have µ>w ≥ ( ‖µ‖22
4 − ‖µ‖q ) · lim t→∞ ∑t m=0 αmL(θm) ‖θt+1‖2
≥ ( ‖µ‖22
4 − ‖µ‖q
) 1
( √ c0 + ) √ d .
where the last inequality is due to Lemma 5.3. Note that Lemma 5.2 also suggests that ‖θt/‖θt‖2− w‖2 ≤ c3 log n/ log t, we have
µ>w = µ> (
w − θt ‖θt‖2 + θt ‖θt‖2 ) ≤ ‖µ‖2 · ∥∥∥∥w − θt‖θt‖2 ∥∥∥∥ 2 + µ>θt ‖θt‖2
≤ c3‖µ‖2 log n log t + µ>θt ‖θt‖2 .
Therefore,
µ>θt ‖θt‖2 ≥ µ>w − c3‖µ‖2 log n log t
≥ ( ‖µ‖22
4 − ‖µ‖q
) 1
( √ c0 + ) √ d − c3‖µ‖2 log n log t .

heading: C AUXILIARY LEMMAS
text: Theorem C.1 (Proposition 5.10 in Vershynin (2010)). LetX1, X2, . . . , Xn be independent centered sub-Gaussian random variables, and let K = maxi ‖Xi‖ψ2 . Then for every a = (a1, a2, . . . , an) ∈ Rn and for every t > 0, we have
P (∣∣∣∣ n∑
i=1
aiXi ∣∣∣∣ > t) ≤ exp(− Ct2K2‖a‖22 ) ,
where C > 0 is a constant. Lemma C.2. For any θ ∈ Rd, ∥∥∂‖θ‖q∥∥2 ≤ √d, ∥∥∂‖θ‖q∥∥p = 1. Proof. Note that we have
(∂‖θ‖q)i = θq−1i ‖θ‖q−1q · sign(θ),
and since for any vector u ∈ Rd, ‖u‖q ≥ ‖u‖∞, ‖u‖2 ≤
√
d‖u‖∞, we have
∥∥∂‖θ‖q∥∥2 = ∥∥θ◦(q−1)∥∥ 2 ‖θ‖q−1q ≤ √ d‖θ‖q−1∞ ‖θ‖q−1q ≤ √ d,
where ◦ denotes element-wise power. This concludes the first part of the lemma. For the second part, by p-norm definition we have
∥∥∂‖θ‖q∥∥p = ∥∥θ◦(q−1)∥∥ p
‖θ‖q−1q =
1
‖θ‖q−1q ( d∑ i=1 (θq−1i ) p )1/p = 1 ‖θ‖q−1q (( d∑ i=1 θqi )1/q)q−1 = 1.

heading: D ADDITIONAL EXPERIMENTS
text: In this section, we present the additional experiments covering more settings as well as more complex models such as 2-layer neural network.

heading: D.1 ADVERSARIALLY TRAINED LINEAR CLASSIFIER UNDER VARIOUS SETTINGS
text: In Figures 2,3,4, we plot the adversarial risk of adversarially trained linear classifiers versus the training iterations t for different perturbation level for various combinations of dimension d and ‖µ‖2. Specifically, in Figure 4, we can observe that with moderate perturbations and sufficient over-parameterization, adversarially trained linear classifiers can achieve near-optimal adversarial risks.

heading: D.2 ADVERSARIALLY TRAINED 2-LAYER NEURAL NETWORKS
text: We have also conducted extra experiments on 2-layer neural networks with ReLU activation functions (one extra fix-dimension hidden layer). The data generation process are the same as our linear experiments. Note that in this setting, we no longer have the closed-form solutions to the inner maximization 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, the empirical results on 2-layer ReLU network suggest very similar trends as the linear classifier for both adversarial risks and standard risks. This further backs up our theoretical conclusions.

Review summaries:
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.  In 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.  In 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$.  

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.

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.