Year: 2021

Abstract:
Adversarial training is a popular method to robustify models against adversarial attacks. However, it exhibits much more severe overfitting than training on clean inputs. In this work, we investigate this phenomenon from the perspective of training instances, i.e., training input-target pairs. We provide a quantitative metric measuring the difficulty of an instance in the training set and analyze the model’s behavior on instances of different difficulty levels. This lets us show that the decay in generalization performance of adversarial training is a result of the model’s attempt to fit hard adversarial instances. We theoretically verify our observations for both linear and general nonlinear models, proving that models trained on hard instances have worse generalization performance than ones trained on easy instances, and that this generalization gap is larger in adversarial training. Finally, we investigate solutions to mitigate adversarial overfitting in several scenarios, including when relying on fast adversarial training and in the context of fine-tuning a pretrained model with additional data. Our results demonstrate that using training data adaptively improves the model’s robustness.

heading: 1 INTRODUCTION
text: The existence of adversarial examples (Szegedy et al., 2014) causes serious safety concerns when deploying modern deep learning models. For example, for classification tasks, imperceptible perturbations of the input instance can fool state-of-the-art classifiers. Many strategies to obtain models that are robust against adversarial attacks have been proposed (Buckman et al., 2018; Dhillon et al., 2018; Ma et al., 2018; Pang et al., 2020; 2019; Samangouei et al., 2018; Xiao et al., 2020), but most of them have been found to be ineffective in the presence of adaptive attacks (Athalye et al., 2018; Croce & Hein, 2020b; Tramer et al., 2020). Ultimately, this leaves adversarial training (Madry et al., 2018) and its variants (Alayrac et al., 2019; Carmon et al., 2019; Gowal et al., 2020; Hendrycks et al., 2019; Kumari et al., 2019; Wu et al., 2020; Zhang et al., 2019a) as the most effective and popular approach to construct robust models. Unfortunately, adversarial training yields much worse performance on the test data than vanilla training. In particular, it strongly suffers from overfitting (Rice et al., 2020), with the model’s performance decaying significantly on the test set in the later phase of adversarial training. While this can be mitigated by early stopping (Rice et al., 2020) or model smoothing (Chen et al., 2021b), the reason behind the overfitting of adversarial training remains poorly understood.
In this paper, we study this phenomenon from the perspective of training instances, i.e., training input-target pairs. We introduce a quantitative metric to measure the difficulty of the instances and analyze the model’s behavior, such as its loss and intermediate activations, on training instances of different difficulty levels. This lets us discover that the model’s generalization performance decays significantly when it fits the hard adversarial instances in the later training phase.
To more rigorously study this phenomenon, we then perform theoretical analyses on both linear and nonlinear models. For linear models, we study logistic regression on a Gaussian mixture model, in which we can calculate the analytical expression of the model parameters upon convergence and thus the robust test accuracy. Our theorem demonstrates that adversarial training on harder instances leads to larger generalization gaps. We further prove that the gap in robust test accuracy between models trained by hard instances and ones trained by easy instances increases with the size of the adversarial budget. In the case of nonlinear models, we derive the lower bound of the model’s Lipschitz constant when the model is well fit to the adversarial training examples. This bound increases with the
difficulty level of the training instances and the size of the adversarial budget. Since a larger Lipschitz constant indicates a higher adversarial vulnerability (Ruan et al., 2018; Weng et al., 2018a;b), our theoretical analysis confirms our empirical observations.
Our findings can be broadly applied to obtain robust models. To evidence this, in addition to the standard adversarial training settings of (Madry et al., 2018), we study the following two scenarios: fast adversarial training and adversarial fine-tuning with additional training data. Our proposed method assigns adaptive targets or adaptive weights on training instances to avoid fitting hard inputtarget pairs. We show it can mitigate adversarial overfitting and improve models’ performance. For fast adversarial training, our results are better than other accelerated adversarial training methods available on RobustBench (Croce et al., 2020). For adversarial fine-tuning with additional training data, we show improved performance over the methods in (Alayrac et al., 2019; Carmon et al., 2019).
Contributions. In summary, our contributions are as follows: 1) Based on a quantitative metric of instance difficulty, we show that fitting hard adversarial instances leads to degraded generalization performance in adversarial training. 2) We conduct a rigorous theoretical analysis on both linear and nonlinear models. For linear models, we show analytically that models trained on harder instances have larger robust test error than the ones trained on easy instances; the gap increases with the size of the adversarial budget. For nonlinear models, we derive a lower bound of the model’s Lipschitz constant. The lower bound increases with the difficulty of the training instances and the size of the adversarial budget, indicating both factors make adversarial overfitting more severe. 3) We show that the adaptive use of the easy and hard training instances can improve the performance in fast adversarial training and adversarial fine-tuning with additional training data.
Notation and terminology. In this paper, x and x′ are the clean input and its adversarial counterpart. We use fw to represent a model parameterized by w and omit the subscript w unless ambiguous. o = fw(x) and o′ = fw(x′) are the model’s output of the clean input and the adversarial input. Lw(x,y) and Lw(x′,y) represent the loss of the clean and adversarial instances, receptively, in which we sometimes omit w and y for notation simplicity. We use ‖w‖ and ‖X‖ to represent the l2 norm of the vector w and the largest singular value of the matrix X, respectively. sign is an elementwise function which returns +1 for positive elements, −1 for negative elements and 0 for 0. 1y is the one-hot vector with only the y-th dimension being 1. The term adversarial budget refers to the allowable perturbations applied to the input instance. It is characterized by lp norm and the size as a set S(p)( ) = {∆|‖∆‖p ≤ }, with defining the budget size. Therefore, given the training set D, the robust learning problem can be formulated as the min-max optimization minw Ex∼Dmax∆∈S(p)( ) Lw(x+ ∆). A notation table is provided in Appendix A. In this paper, vanilla training refers to training on the clean inputs, and vanilla adversarial training to the adversarial training method in (Madry et al., 2018). RN18 and WRN34 are the 18-layer ResNet (He et al., 2016) and the 34-layer WideResNet (Zagoruyko & Komodakis, 2016) used in (Madry et al., 2018) and (Wong et al., 2020), respectively. To avoid confusion with the general term overfitting, which denotes the gap between the training and test accuracy, we employ the term adversarial overfitting to indicate the phenomenon that robust accuracy on the test set decreases significantly in the later phase of vanilla adversarial training. This phenomenon was pointed out in (Rice et al., 2020) and does not occur in vanilla training. Our code is submitted on GoogleDrive anonymously1.

heading: 2 RELATED WORK
text: We concentrate on white-box attacks, where the attacker has access to the model parameters. Such attacks are usually based on first-order information and stronger than black-box attacks (Andriushchenko et al., 2020; Dong et al., 2018). For example, the fast gradient sign method (FGSM) (Goodfellow et al., 2014) perturbs the input based on its gradient’s sign, i.e., ∆ = sign(OxLw(x)). The iterative fast gradient sign method (IFGSM) (Kurakin et al., 2016) iteratively runs FGSM using a smaller step size and projects the perturbation back to the adversarial budget after each iteration. On top of IFGSM, projected gradient descent (PGD) (Madry et al., 2018) use random initial perturbations and restarts to boost the strength of the attack.
Many methods have been proposed to defend a model against adversarial attacks (Buckman et al., 2018; Dhillon et al., 2018; Ma et al., 2018; Pang et al., 2020; 2019; Samangouei et al., 2018; Xiao
1https://drive.google.com/file/d/1vb6ehNMkBeNIM3dLr_igKMUcCgBd9ZmK/view?usp=sharing
et al., 2020). However, most of them were shown to utilize obfuscated gradients (Athalye et al., 2018; Croce & Hein, 2020b; Tramer et al., 2020), that is, training the model to tackle some specific types of attacks instead of achieving true robustness. This makes these falsely robust models vulnerable to stronger adaptive attacks. By contrast, several works have designed training algorithms to obtain provably robust models (Cohen et al., 2019; Gowal et al., 2019; Raghunathan et al., 2018; Salman et al., 2019; Wong & Kolter, 2018). Unfortunately, these methods either do not generalize to modern network architectures or have a prohibitively large computational complexity. As a consequence, adversarial training (Madry et al., 2018) and its variants (Alayrac et al., 2019; Carmon et al., 2019; Hendrycks et al., 2019; Kumari et al., 2019; Wu et al., 2020; Zhang et al., 2019a) have become the de facto approach to obtain robust models in practice. In essence, these methods generate adversarial examples, usually using PGD, and use them to optimize the model parameters.
While effective, adversarial training is more challenging than vanilla training. It was shown to require larger models (Xie & Yuille, 2020) and to exhibit a poor convergence behavior (Liu et al., 2020). Furthermore, as observed in (Rice et al., 2020), it suffers from adversarial overfitting: the robust accuracy on the test set significantly decreases in the late adversarial training phase. (Rice et al., 2020) thus proposed to perform early stopping based on a separate validation set to improve the generalization performance in adversarial training. Furthermore, (Chen et al., 2021b) introduced logit smoothing and weight smoothing strategies to reduce adversarial overfitting. In parallel to this, several techniques to improve the model’s robust test accuracy were proposed (Wang et al., 2020; Wu et al., 2020; Zhang et al., 2021), but without solving the adversarial overfitting issue. By contrast, other works (Balaji et al., 2019; Huang et al., 2020) were empirically shown to mitigate adversarial overfitting but without providing any explanations as to how this phenomenon was addressed. In this paper, we study the causes of adversarial overfitting from both an empirical and a theoretical point of view. We also identify the reasons why prior attempts (Balaji et al., 2019; Chen et al., 2021a; Huang et al., 2020) successfully mitigate it.

heading: 3 A METRIC FOR INSTANCE DIFFICULTY
text: Parametric models are trained to minimize a loss objective based on several input-target pairs called training set, and are then evaluated on a held-out set called test set. By comparing the loss value of each instance, we can understand which ones, in either the training or the test set, are more difficult for the model to fit. In this section, we introduce a metric for instance difficulty, which mainly depends on the data and on the perturbations applied to the instances.
Let L(x) denote the average loss of x’s corresponding perturbed input across all training epochs. We define the difficulty of an instance x within a finite set D as
d(x) =P(L(x) < L(x̃)|x̃ ∼ U(D)) + 1 2 P(L(x) = L(x̃)|x̃ ∼ U(D)) , (1)
where x̃ ∼ U(D) indicates x̃ is uniformly sampled from the finite set D. d(x) is a bounded function, close to 0 for the hardest instances, and 1 for the easiest ones. We discuss the motivation and properties of d(x) in Appendix D.1, and show that it mainly depends on the data and the perturbation applied, the model architecture or the training duration can hardly affect the difficulty function. That is, d(x) can represent the difficulty of x within a set under a specific type of perturbation.

heading: 4 INSTANCE DIFFICULTY AND ADVERSARIAL OVERFITTING
text: The model-agnostic difficulty metric of Section 3 allows us to select training instances based on their difficulty. In Figures 20 and 21 of Appendix D.2, we show some samples of the easiest and the hardest instances of each class in CIFAR10 (Krizhevsky et al., 2009) and SVHN (Netzer et al., 2011), respectively. In both cases, the easiest instances are visually highly similar, whereas the hardest ones are much more diverse, some of them being ambiguous or even incorrectly labeled. Below, we study how easy and hard instances impact the performance of adversarial training, with a focus on the adversarial overfitting phenomenon. The detailed experimental settings are deferred to Appendix C.1.

heading: 4.1 USING A SUBSET OF TRAINING DATA
text: We start by training RN18 models for 200 epochs using either the 10000 easiest, random or hardest instances of the CIFAR10 training set via either vanilla training, FGSM adversarial training or PGD
adversarial training. The adversarial budget is based on the l∞ norm and = 8/255. Note that the instance’s difficulty is defined under the corresponding perturbation type, and we enforce these subsets to be class-balanced. For example, the easiest 10000 instances consist of the easiest 1000 instances in each class. We provide the learning curves under different settings in Figure 1.
For PGD adversarial training, in Figure 1(a), while we observe adversarial overfitting when using the random instances, as in (Rice et al., 2020), no such phenomenon occurs when using the easiest instances: the performance on the test set does not degrade during training. However, PGD adversarial training fails and suffers more severe overfitting when using the hardest instances. Note that, in Figure 5 (Appendix D.3), we show that this failure is not due to improper optimization.
In contrast to PGD, FGSM adversarial training and vanilla training (Figure 1(b), 1(c)), through which the model does not achieve true robustness (Madry et al., 2018), do not suffer from severe adversarial overfitting. In these cases, the models trained with the hardest instances also achieve non-trivial test accuracy. Furthermore, the gaps in robust test accuracy between the models trained by easy instances and by hard ones are much smaller.
In Appendix D.3, we perform additional and comprehensive experiments, evidencing that our conclusions hold for different datasets and values of , and for an adversarial budget based on the l2 norm. We show that more severe adversarial overfitting happens when the size of the adversarial budget increases. Furthermore, we experiment with training models using increasingly many training instances, start with the easiest ones. Our results in Figure 10 show that the models can benefit from using more data, but only using early stopping as done in (Rice et al., 2020). This indicates that the hard instances can still benefit adversarial training, but need to be utilized in an adaptive manner.

heading: 4.2 HARD INSTANCES LEAD TO OVERFITTING
text: Let us now turn to the more standard setting where we train the model with the entire training set. To nonetheless analyze the influence of instance difficulty in this scenario, we divide the training set D into 10 non-overlapping groups {Gi}9i=0, with Gi = {x ∈ D|0.1 × i ≤ d(x) < 0.1 × (i + 1)}. That is, G0 is the hardest group, whereas G9 is the easiest one. We then train an RN18 model on the entire CIFAR10 training set using PGD adversarial training and monitor the training behavior of the different groups. In particular, in Figure 2(a), we plot the average loss of the instances in the groups G0, G3, G6 and G9. The resulting curves show that, in the early training stages, the model first fits the easy instances, as evidenced by the average loss of group G9 decreasing much faster than that of the other groups. By contrast, in the late training phase, the model tries to fit the more difficult instances, with the average loss of groups G0 and G3 decreasing much faster than that of the other groups. In this period, however, the robust test error (solid grey line) increases, which indicates that adversarial overfitting arises from the model’s attempt to fit the hard adversarial instances.
In addition to average losses, inspired by (Ilyas et al., 2019), which showed that the penultimate layer’s activations of a robust model correspond to its robust features that cannot be misaligned by adversarial attacks, we monitor the group-wise average magnitudes of the penultimate layer’s activations. As shown in Figure 2(b), the model first focuses on extracting robust features for the easy instances, as evidenced by the comparatively large activations of the instances in G9. In the late
phase of training, the norm of the activations of the hard instances increases significantly, bridging the gap between easy and hard instances. This further indicates that the model focuses more on the hard instances in the later training phase, at which point it starts overfitting.

heading: 5 THEORETICAL ANALYSIS
text: We now study the relationship between adversarial overfitting and instance difficulty from a theoretical viewpoint. We start with the linear model, where the loss function has an analytical expression, and then generalize our analysis to the nonlinear cases. We use {xi, yi}ni=1 to represent the training data, and (X,y) as its matrix form. {x′i, yi}ni=1 and (X′,y) are their adversarial counterparts. Here, xi ∈ Rm, yi ∈ {−1,+1}, X ∈ Rn×m and y ∈ {−1,+1}n. The notation used for our theoretical analysis is summarized in Table 3 of Appendix A.

heading: 5.1 LOGISTIC REGRESSION
text: We study the logistic regression model under an l2 norm based adversarial budget. In this case, the model is parameterized by w ∈ Rm and outputs sign(wTx′i) given the adversarial example x′i of the input xi. The loss function for this instance is 1
1+eyiw T x′ i . We assume over-parameterization,
which means n < m.
The following theorem shows that, under mild assumptions, the parameters of the adversarially trained logistic regression model converge to the l2 max-margin direction of the training data.
Theorem 1. For a dataset {xi, yi}ni=1 that is linearly separable under the adversarial budget S(2)( ), any initial point w0 and step size α ≤ 2‖X‖−2, the gradient descent wu+1 = wu − αOwLwu(X′) converges asymptotically to the l2 max-margin vector of the training data. That is,
lim u→∞ wu ‖wu‖ = ŵ ‖ŵ‖ , where ŵ = arg min w ‖w‖ s.t. ∀i ∈ {1, 2, ..., n}, wTxi ≥ 1 . (2)
The proof is deferred to Appendix B.1. Theorem 1 extends the conclusion in (Soudry et al., 2018), which only studies the non-adversarial case. It also indicates that the optimal parameters are only determined by the support vectors of the training data, which are the ones with the smallest margin. According to the loss function, the smallest margin means the largest loss values and thus the hardest training instances based on our definition in Section 3.
To further study how the training instances’ difficulty influences the model’s generalization performance, we assume that the data points are drawn from a K-mode Gaussian mixture model (GMM). Specifically, the k-th component has a probability pk of being sampled and is formulated as follows:
if yi = +1, xi ∼ N (rkη, I); if yi = −1, xi ∼ N (−rkη, I). (3)
Here, η ∈ Rm is the unit vector indicating the mean of the positive instances, and rk ∈ R+ controls the average distance between the positive and negative instances. The mean values of all modes in this GMM are colinear, so rk indicates the difficulty of instances sampled from the k-th component. Without the loss of generality, we assume r1 < r2 < ... < rK−1 < rK . As in Section 4, we consider models trained with the subsets of the training data, e.g., n instances from the l-th component. l = 1 then indicates training on the hardest examples, while l = K means using the easiest. In matrix form, we have X = rlyηT + Q for the instances sampled from the l-th component, where the rows of noise matrix Q are sampled from N (0, I). Although the max-margin direction in Equation (2), where the parameters converge based on Theorem 1, does not have an analytical expression, the results in (Wang & Thrampoulidis, 2020) indicate that, in the over-parameterization regime and when the training data is sampled from a GMM, the max-margin direction is the min-norm interpolation of the data with high probability. Since the latter has an analytical form given by XT (XXT )−1y, we can then calculate the exact generalization performance of the trained model as stated in the following theorem. Theorem 2. If a logistic regression model is adversarially trained on n separable training instances sampled from the l-th component of the GMM model described in (3). If mn logn is sufficiently large
2, then with probability 1−O( 1n ), the expected adversarial test errorR under the adversarial budget S(2)( ), which is a function of rl and , on the whole GMM model described in (3) is given by
R(rl, ) = K∑ k=1 pkΦ (rkg(rl)− ) , g(rl) = (C1 − 1 C2r2l + o(r 2 l ) ) 1 2 , C1, C2 ≥ 0. (4)
C1, C2 are independent of and rl. The function Φ is defined as Φ(x) = P(Z > x), Z ∼ N (0, 1).
We defer the proof of Theorem 2 to Appendix B.2, in which we calculate the exact expression of R(rl, ), C1, C2, and show that C1, C2 are positive numbers almost surely. Since C1 and C2 are independent of rl, and Φ(x) is a monotonically decreasing function, we conclude that the robust test errorR(rl, ) becomes smaller when rl increases. That is, when the training instances become easier, the corresponding generalization error under the adversarial attack becomes smaller.
Theorem 2 holds for all only if the training data is separable under the corresponding adversarial budget. The following corollary shows that the difference in the robust test error between models trained with easy instances and the ones with hard ones increases when becomes larger. Corollary 1. Under the conditions of Theorem 2 and the definition ofR in Equation (4), if 1 < 2, then we have ∀ 0 ≤ i < j ≤ K,R(ri, 1)−R(rj , 1) < R(ri, 2)−R(rj , 2).
The proof is in Appendix B.3. This indicates that, compared with training on clean inputs, i.e., = 0, the generalization performance of adversarial training with > 0 is more sensitive to the difficulty of the training instances. This is consistent with our empirical observations in Figure 1.

heading: 5.2 GENERAL NONLINEAR MODELS
text: In this section, we study the binary classification problem using a general nonlinear model. We consider a model with b parameters, i.e., w ∈ Rb. Without loss of generality, we assume the output of the function fw to lie in [−1,+1]. Furthermore, we assume isoperimetry of the data distribution: Assumption 1. The data distribution µ is a composition of K c-isoperimetric distributions on Rm, each of which has a positive conditional variance. That is, µ = ∑K k=1 αkµk, where αk > 0
and ∑K k=1 αk = 1. We define σ 2 k = Eµk [V ar[y|x]], and without loss of generality assume that σ1 ≥ σ2 ≥ ... ≥ σK > 0. Furthermore, given any L-Lipschitz function fw, i.e., ∀x1,x2, ‖fw(x1)− fw(x2)‖ ≤ L‖x1 − x2‖, we have
∀k ∈ {1, 2, ...,K} P(x ∼ µk, ‖fw(x)− Eµk(fw)‖ ≥ t) ≤ 2e − mt2 2cL2 . (5)
This is a benign assumption; the data distribution is a mixture of K components and each of them contains samples from a sub-Gaussian distribution. These components correspond to training
2Specifically, m and n need to satisfy m > 10n logn+ n− 1 and m > Cnrl √ log 2n‖η‖. The constant
C is derived in the proof of Theorem 1 in (Wang & Thrampoulidis, 2020).
instances of different difficulty levels measured by the conditional variance. We then study the property of the model fw under adversarial attacks.
Definition 1. Given the dataset {xi, yi}ni=1, the model fw, the adversarial budget S(p)( ) and a positive constant C, we define the function h(C, ) as
h(C, ) = min w∈T (C, ) min i hi,w( ) s.t. T (C, ) = { w| 1 n n∑ i=1 (fw(x ′ i)− yi)2 ≤ C } ,
where hi,w( ) = max ζ, s.t. [fw(xi)− ζ, fw(xi) + ζ] ⊂ { fw(xi + ∆)|∆ ∈ S(p)( ) } .
(6)
Here, x′i is the adversarial example of x. We omit the superscript (p) for notation simplicity.
By definition, hi,w( ) ≥ 0 depicts the bandwidth ζ of the model’s output range in the domain of the adversarial budget on a training instance. h(C, ) is the minimum bandwidth among the models whose mean squared error on the adversarial training set is smaller than C. Based on the definitions of T and hi,w, and for a fixed value of C, we have ∀ 1 < 2, hi,w( 1) ≤ hi,w( 2) and T (C, 2) ⊂ T (C, 1). As a result, ∀ 1 < 2, h(C, 1) ≤ h(C, 2). In addition, since ∀C1 < C2, T (C1, ) ⊂ T (C2, ) for a fixed value of , we have ∀C1 < C2, h(C1, ) ≥ h(C2, ). That is to say, h(C, ) is a monotonically non-decreasing function on and a monotonically non-increasing function on C. In practice, when fw represents a deep neural network, h(C, ) increases with almost surely, because the attack algorithm usually generates adversarial examples at the boundary of the adversarial budget. We then state our main theorem below. Theorem 3. Given n training pairs {xi, yi}ni=1 sampled from the l-th component µl of the distribution in Assumption 1, the parametric model fw, the adversarial budget S(p)( ) and the corresponding function h defined in Definition 1, we assume that the model fw is in the function space F = {fw,w ∈ W} withW ⊂ Rb having a finite diameter diam(W) ≤W and, ∀w1,w2 ∈ W, ‖fw1 − fw2‖∞ ≤ J‖w1 −w2‖∞. We train the model fw adversarially using these n data points. Let x′ be the adversarial example of the data point x and δ ∈ (0, 1). If we have 1n ∑n i=1(fw(x ′ i)− yi)2 = C and γ := σ2l + h 2(C, )−C ≥ 0, then with probability at least 1− δ, the Lipschitz constant of fw is lower bounded as
Lip(fw) ≥ γ
27
√ nm
c ( b log(4WJγ−1)− log(δ/2− 2e−2−11nγ2) ) , (7) where Lip(fw) is the Lipschitz constant of fw: ∀x1,x2, ‖fw(x1)−fw(x2)‖ ≤ Lip(fw)‖x1−x2‖.
The proof is deferred to Appendix B.4. Theorem 3 extends the results in (Bubeck & Sellke, 2021) to the case of adversarial training. Note that modern deep neural network models typically have millions of parameters, so b max{c,m, n}. In this case, we can approximate the lower bound (7) by Lip(fw) & γ27 √ nm bc log(4WJγ−1) , and the right hand side increases with γ. Since γ :=
σ2l + h 2(C, )− C, the lower bound increases with both σl and but decreases as C increases.
The Lipschitz constant is widely used to bound a model’s adversarial vulnerability (Ruan et al., 2018; Weng et al., 2018a;b): larger Lipschitz constants indicate higher adversarial vulnerability. Recall that γ needs to be non-negative, so C is upper bounded, which means that the model is well fit to the adversarial training set and the adversarial vulnerability is approximately the generalization gap. Based on this, the adversarial vulnerability of a model increases with the size of the adversarial budget and the difficulty level of the training instances; it also increases as the training mean squared error decreases. That is, under the same adversarial budget, the adversarial vulnerability increases with the instances’ difficulty, measured by σl in our theorem; using the same training instances, the adversarial vulnerability increases with the adversarial budget measured by . In addition, as adversarial training progresses, the mean squared error C on the adversarial training instances becomes smaller, which makes the lower bound of the Lipschitz constant larger. This indicates that adversarial vulnerability becomes larger in the later phase of adversarial training.
We provide empirical evidence to confirm the conclusions of Theorem 3 in Appendix D.4. Since calculating the Lipschitz constant of a deep neural network is NP-hard (Scaman & Virmaux, 2018), exactly calculating the Lipschitz constant (Jordan & Dimakis, 2020) can only be achieved for simple multi-layer perceptron (MLP) models, not for modern deep networks. Instead, we estimate the upper bound of the Lipschitz constant numerically, as in (Scaman & Virmaux, 2018).

heading: 6 MITIGATING ADVERSARIAL OVERFITTING
text: Existing methods mitigating adversarial overfitting study the standard adversarial training scenario: PGD adversarial training from scratch. In Appendix D.5, we show that they use either adaptive inputs (Balaji et al., 2019) or adaptive targets (Huang et al., 2020; Chen et al., 2021b) to implicitly avoid fitting hard input-target pairs, thus providing an explanation for their success.
Below, we study two settings other than standard adversarial training: fast adversarial training and adversarial fine-tuning with additional data, to validate our findings. We show that methods inspired by our findings can avoid adversarial overfitting and improve the performance. The detailed experimental settings for this section are in Appendix C.2.

heading: 6.1 FAST ADVERSARIAL TRAINING
text: Adversarial training in (Madry et al., 2018) introduces a significant computational overhead. Thus it is desirable to accelerate this method. Our experiments in this section are based on adversarial training with transferable adversarial examples (ATTA in (Zheng et al., 2020)), which stores the adversarial perturbation for each training instance as an initial point for the next epoch. We show that adaptively utilizing the easy and hard training instances not only mitigates adversarial overfitting, but also significantly improves the performance of the final model.
First, we introduce a reweighting scheme to assign lower weights to hard instances when calculating the loss objective. Specifically, each training instance is assigned a weight equal to the adversarial output probability of the true label. Then this weight is normalized to ensure that the weights in a mini-batch sum to 1. Note that our reweighting scheme is based on the adversarial output instead of the clean output, because the adversarial output probability will also be used to calculate the loss objective. As a result, the computational overhead of the reweighting scheme is negligible.
In addition to reweighting, we also use adaptive targets to improve the performance. For each training instance (x, y), we maintain an adaptive moving average target t̃. t̃ is updated in an exponential average manner in each epoch t̃← ρt̃+ (1− ρ)o′ where ρ is the momentum factor. This is similar to the target in (Huang et al., 2020), but, similarly to the reweighting scheme, we use the adversarial output o′ instead of the clean output o to avoid an increase in computational complexity. The final adaptive target we use is t = β1y + (1 − β)t̃ and thus the loss objective is Lw(x′, t). The factor β controls how “adaptive” our target is: β = 0 yields a fully adaptive moving average target t̃ and β = 1 yields a one-hot target 1y . We provide the pseudocode as Algorithm 1 in Appendix C.2.
We run experiments on CIFAR10 using WRN34 models under the l∞ adversarial budget of size = 8/255, the standard setting where most fast adversarial training algorithms are benchmarked (Croce et al., 2020). We evaluate the model’s robust accuracy on the test set by AutoAttack (Croce & Hein, 2020b), the popular and reliable attack for evaluation. The results are provided in Table 2, where the results of the baseline methods are taken from RobustBench (Croce et al., 2020). We also report the number of epochs and the number of forward and backward passes in a mini-batch update of each method. The product of these two values indicates the training complexity.
We can clearly see that both reweighting and adaptive targets improve the performance on top of ATTA (Zheng et al., 2020). Note that our method based on adaptive targets achieve the best performance while needing only 1/4 of the training time of (Chen et al., 2021a), the strongest baseline. (Wong et al., 2020) is the only baseline consuming less training time than ours, but its performance is much worse than ours; it suffers from catastrophic overfitting when using a WRN34 model. In Appendix D.6, we provide the learning curves of our methods under different settings and show that both reweighting and adaptive targets mitigate adversarial overfitting. We also conduct an ablation study on the value of β and find that a decrease in β decreases the generalization gap. This indicates that the more adaptive the targets, the smaller the generalization gap.

heading: 6.2 ADVERSARIAL FINETUNING WITH ADDITIONAL DATA
text: We observe that adversarial overfitting occurs in the small learning rate regime in Section 4. To further study this, we propose to fine-tune an adversarially pretrained model using additional training data, because we also use small learning rate to fine-tune a model. While additional training data was
Method Model Epochs Complexity AA (Shafahi et al., 2019) WRN34 200 2 41.17 (Wong et al., 2020) RN18 15 4 43.21 (Zheng et al., 2020) WRN34 38 4 44.48 (Zhang et al., 2019a) WRN34 105 3 44.83 (Chen et al., 2021a) WRN34 100 7 51.12 Reweighting (Ours) WRN34 38 4 46.15 Adaptive Target (Ours) WRN34 38 4 51.17
Table 1: Comparison between different accelerated adversarial training methods in robust test accuracy against AutoAttack (AA). The baseline results are from RobustBench. Complexity shows the number of forward passes and backward passes in one mini-batch update.
Duration Method AA WRN34 on CIFAR10, = 8/255 No Fine Tuning 52.01 1 Epoch Vanilla AT 54.11Ours 54.69 5 Epoch Vanilla AT 55.49Ours 56.99 RN18 on SVHN, = 0.02 No Fine Tuning 67.77 1 Epoch Vanilla AT 70.81Ours 72.53 5 Epoch Vanilla AT 72.18Ours 73.35
Table 2: Robust accuracy of fine-tuned models against AutoAttack(AA).
shown to be beneficial in (Alayrac et al., 2019; Carmon et al., 2019), we demonstrate that letting the model adaptively fit the easy and hard instances can further improve the performance.
We conduct experiments on both CIFAR10 and SVHN, using WRN34 and RN18 models, respectively. The experimental settings are the same as (Carmon et al., 2019) except the learning rate. We tune the learning rate and find that fixing it to 10−3 is the best choice. The model is fine-tuned for either 1 epoch or 5 epochs, which means that each additional training instance is used either 5 times or only once. This is because we observed the performance of vanilla adversarial training to start decaying after 5 epochs. As such, methods requiring many epochs such as (Balaji et al., 2019) and (Huang et al., 2020) are not applicable here.
Our first technique, reweighting, is the same as in Section 6.1. In addition to reweighting, we can also add a KL regularization term measuring the KL divergence between the output probability of the clean instance and of the adversarial instance. The KL term encourages the adversarial output to be close to the clean one. In other words, the clean output probability serves as the adaptive target. For hard instances, the clean and adversarial inputs are usually both misclassified. Therefore, the clean outputs of these instances constitute simpler targets compared with the ground-truth labels. Ultimately, the loss objective of a mini-batch {xi}Bi=1 used for fine-tuning is expressed as LFT ({xi}Bi=1) = ∑B i=1 wi [Lw(x′i) + λKL(oi||o′i)] where wi is the adaptive weight when we use re-weighting, or 1/B otherwise. λ is 6 when using the regularization term and 0 otherwise.
We use both reweighting and KL regularization to fine-tune the model. Our results are shown in Table 2, where the robust test accuracy is also evaluated by AutoAttack. It is clear that our methods can improve the performance under all settings. We also conduct an ablation study in Appendix D.7. All these results show that avoiding fitting hard adversarial examples helps to improve the generalization performance in adversarial fine-tuning with additional training data.

heading: 7 CONCLUSION
text: We have investigated adversarial overfitting from the perspective of the easy and hard training instances. By introducing a quantitative, model-agnostic and normalized metric to measure the instance difficulty, we have shown that a model’s generalization performance under adversarial attacks degrades during the later phase of training as the model fits the hard adversarial instances. We have conducted theoretical analyses on both linear and nonlinear models. On an over-parameterized logistic regression model, we have shown that training on harder adversarial instances leads to poorer generalization performance. On general nonlinear models, we have proven that the lower bound of a well-trained model’s Lipschitz constant increases with the difficulty of the training instances. Finally, our experiments on fast adversarial training and adversarial fine-tuning with additional data have demonstrated that adaptively using the training instances mitigates adversarial overfitting and improves the model’s robustness.

heading: ETHICS STATEMENT
text: Adversarial attacks may cause unexpected failure of modern deep learning models, especially in some safety-critical applications such as self-driving and medical imaging. Our work studies the defense methods and focuses on how to improve training robust models to prevent such failure from happening. We are not aware of any ethics issues about our work, as we are using publicly available data and models.

heading: REPRODUCIBILITY STATEMENT
text: The experimental settings of our empirical study are demonstrated in detail in Appendix C. Especially, we also provide the pseudocode of our algorithm there. Our code is submitted anonymously on GoogleDrive3. It will be made publicly available when our work is published.

heading: A NOTATION

heading: B PROOFS IN THEORETICAL ANALYSIS

heading: B.1 PROOF OF THEOREM 1
text: Similar to (Soudry et al., 2018), we can assume all instances are positive without the loss of generality, this is because we can always redefine yixi as the input. In this regard, the loss to optimize in a logistic regression model under the adversarial budget S(2)( ) is:
Lw(X) = n∑ i=1 l(wTxi − ‖w‖) (8)
Here l(·) is the logistic function: l(x) = 11+e−x . We use X ∈ R n×m to represent the training set as said in Section 5, then the loss function L(w) is ‖X‖2-smooth, where ‖X‖2 is the maximal singular value of X. Since function Lw is convex onw, so gradient descent of step size smaller than 2‖X‖−2 will asymptotically converge to the global infimum of the function Lw on w.
Before proving Theorem 1, we first introduce the following lemma:
Lemma 1. Consider the max-margin vector ŵ of the vanilla case defined in Equation (2), we then introduce the max margin vector ŵ′ defined under the adversarial attack of budget S(2)( ) as follows:
ŵ′ = arg min w ‖w‖ s.t. ∀i ∈ {1, 2, ..., n}, wTxi − ‖w‖ ≥ 1 (9)
Then we have ŵ′ is collinear with ŵ, i.e., ŵ′ ‖ŵ′‖ = ŵ‖ŵ‖
Proof. We show that ŵ = 1 1+ ‖ŵ′‖ ŵ′ and prove it by contraction.
Let’s assume ∃v, s.t. ‖v‖ < ‖ŵ ′‖
1+ ‖ŵ′‖ and ∀i ∈ {1, 2, ..., n}, vTxi ≥ 1, then we can consider
v′ = (1 + ‖ŵ′‖)v. The l2 norm of v′ is smaller than that of ŵ′, and we have
∀i ∈ {1, 2, ..., n},v′Txi − ‖v′‖ = (1 + ‖ŵ′‖)vTxi − ‖v′‖ > (1 + ‖ŵ′‖)− ‖ŵ′‖ = 1 (10)
Inequality 10 shows we can construct a vector v′ whose l2 norm is smaller than ŵ′ and satisfying the condition (9), this contracts with the optimality of ŵ′. Therefore, there is no solution of condition (2) whose norm is smaller than ‖ŵ
′‖ 1+ ‖ŵ′‖ .
On the other hand, 1 1+ ‖ŵ′‖
ŵ′ satisfies the condition (2) and its l2 norm is ‖ŵ′‖
1+ ‖ŵ′‖ . As a result, we
have ŵ = 1 1+ ‖ŵ′‖ ŵ′. That means ŵ and ŵ′ are collinear.
With Lemma 1, Theorem 1 is more straightforward, whose proof is shown below. Regarding the convergence analysis of the logistic regression model in non-adversarial cases, we encourage the readers to find more details in (Ji & Telgarsky, 2019; Soudry et al., 2018).
Proof. Theorem 1 in (Ji & Telgarsky, 2019) and Theorem 3 in (Soudry et al., 2018) proves the convergence of the direction of the logistic regression parameters in different cases. In this regard, we can let w∞ = limu→∞ w(u) ‖w(u)‖ . That is to say, for sufficiently large u, the direction of the parameter w(u) can be considered fixed. As a result, the adversarial perturbations of each data instance xi is fixed, i.e., w∞.
We can then apply the conclusion of Theorem 3 in (Soudry et al., 2018) here, the only difference is the data points are {xi − w∞}ni=1. Therefore, the parameter w(u) will converge to the l2 max margin of the dataset {xi − w∞}ni=1. When t → ∞, we have w(u)T (xi − w∞) = w(u)Txi − ‖w(u)‖. This is exactly the adversarial max margin condition in (9). Based on Lemma 1, we have limu→∞ w(u) ‖w(u)‖ = ŵ′ ‖ŵ′‖ = ŵ‖ŵ‖

heading: B.2 PROOF OF THEOREM 2
text: Given the parameter w of the logistic regression model, we can first calculate the robust error for the k-th component of the GMM model defined in (3).
Lemma 2. The 0-1 classification error of a linear classifier w under the adversarial attack of the budget S(2)( ) for the k-th component of the GMM model defined in (3) is:
R̂k( ) = Φ( rkw
Tη
‖w‖ − ) (11)
where Φ(x) = P(Z > x), Z ∼ N (0, 1).
Proof. For a random drawn data instance (x, y), the adversarial perturbation is −y w‖w‖ . Let’s decompose x as rkyη + z, where z ∼ N (0, I). Then, we have
R̂k( ) = P(ywT (x− y w
‖w‖ ) < 0) = P(ywT (rkyη + z − y
w
‖w‖ ) < 0)
= P(−ywTz > rkwTη − ‖w‖) (12)
Since z ∼ N (0, I), we have −ywTz ∼ N (0, (−ywT )T (−ywT )) = N (0,wTw). Furthermore −ywT z ‖w‖ ∼ N (0, 1), and we can further simplify R̂k( ) as follows:
R̂k( ) = P( −ywTz ‖w‖ > rkw Tη ‖w‖ − ) = Φ(rkw Tη ‖w‖ − ) (13)
With Lemma 2, we can straightforwardly calculate the robust error for all components of the GMM model defined in (3):
R̂( ) = K∑ k=1 pkΦ( rkw Tη ‖w‖ − ) (14)
On the other hand, Theorem 1 indicates the parameter w will converge to the l2 max margin. However, for arbitrary training set, we do not have the closed form of w, which is a barrier for the further analysis. Nevertheless, results from (Wang & Thrampoulidis, 2020) indicates in the over-parameterization regime, the parameter w will converge to min-norm interpolation of the data with high probability. Lemma 3. (Directly from Theorem 1 in (Wang & Thrampoulidis, 2020)) Assume n training instances drawn from the l-th mode of the described distribution in (3) and each of them is a m-dimensional vector. If mn logn is sufficiently large
4, then the l2 max margin vector in Equation (2) will be the same as the solution of the min-norm interpolation described below with probability at least (1−O( 1n )).
w̄ = arg min w
‖w‖ s.t. ∀i ∈ {1, 2, ..., n}, yi = wTxi (15)
Since the min-norm interpolation has a closed solution w̄ = XT (XXT )−1y, Lemma 3 will greatly facilitate the calculation of R(w) in Theorem 2. To simplify the notation, we first define the following variables.
U = QQT , d = Qη, s = yTU−1y, t = dU−1d, v = yTU−1d (16) The proof of Theorem 2 is then presented below.
Proof. Based on (14), the key is to simplify the term w Tη ‖w‖ , let’s denote it by A, then we have:
A2 = ηTwwTη
wTw =
(yT (XXT )−1Xη)2
yT (XXT )−1y (17)
The key challenge here is to calculate the term (XXT )−1 where X = rlyηT +Q. Here we utilize Lemma 3 of (Wang & Thrampoulidis, 2020) and Woodbury identity (Horn & Johnson, 2012), we have:
yT (XX)−1 = yTU−1 − (r 2 l s‖η‖2 + r2l v2 + rlv − r2l st)yT + rlsdT
r2l s(‖η‖2 − t) + (rlv + 1)2 U−1 (18)
4Specifically, m and n need to satisfy m > 10n logn+ n− 1 and m > Cnrl √ log 2n‖η‖. The constant
C is derived in the proof of Theorem 1 in (Wang & Thrampoulidis, 2020).
Here, s, t, v, U and d are defined in Equation (16). The scalar divisor comes from the matrix inverse calculation. Base of Equation (18), we can then calculate yT (XXT )−1y and yT (XXT )−1Xη.
yT (XXT )−1y = s− (r 2 l s‖η‖2 + r2l v2 + rlv − r2l st)s+ rlsv
r2l s(‖η‖2 − t) + (rlv + 1)2
= s r2l s(‖η‖2 − t) + (rlv + 1)2 (19)
yT (XXT )−1Xη = yT (XXT )−1(rlyη T +Q)η
= rl‖η‖2yT (XXT )−1y + yT (XXT )−1d
= rls(‖η‖2 − t) + rlv2 + v r2l s(‖η‖2 − t) + (rlv + 1)2
(20)
Plug Equation (19) and (20) into (17), we have:
A2 =
( rls(‖η‖2 − t) + rlv2 + v )2 s (r2l s(‖η‖2 − t) + (rlv + 1)2)
= s(‖η‖2 − t) + v2 s − ‖η‖ 2 − t r2l s(‖η‖2 − t) + (rlv + 1)2 = s(‖η‖2 − t) + v2
s − 1(
s(‖η‖2−t)+v2 ‖η‖2−t ) r2l + 2v ‖η‖2−trl + 1 ‖η‖2−t
(21)
Plug (21) into (14), we then obtain the robust error on all components of the GMM defined in (3):
R(rl, ) = K∑ k=1 pkΦ (rkg(rl)− ) , g(rl) = (C1 − 1 C2r2l + C3 ) 1 2
C1 = s(‖η‖2 − t) + v2
s , C2 =
s(‖η‖2 − t) + v2
‖η‖2 − t , C3 =
2v
‖η‖2 − t rl +
1
‖η‖2 − t .
(22)
We study the sign of C1 and C2. Consider U = QQT is a positive semidefinite matrix, so s = yU−1yT ≥ 0. In addition, we have ‖η‖2 − t = ηT ( I− (QQT )−1 ) η. Since I − (QQT )−1 = (I− (QQT )−1)T (I− (QQT )−1) is a positive semidefinite matrix, we can obtain I− (QQT )−1 is also a positive semidefinite matrix. As a result, C1 and C2 are both non-negative.

heading: B.3 PROOF OF COROLLARY 1
text: To prove Corollary 1, we first prove the following lemma:
Lemma 4. Under the condition of Theorem 2 and R in Equation (4), ∂R(rl, )∂rl is negative and monotonically decreases with .
Proof. Based on Equation (22), we have:
∂R(rl, ) ∂rl = K∑ k=1 pkΦ ′(rkg(rl)− ) ∂g(rl) ∂rl (23)
Since the training data is separable, we have ∀k, rkwTη − ‖w‖ > 0, which is equivalent to the following:
∀k, rkg(rl)− > 0 (24)
First, pk is a positive number by definition. Consider function Φ(x) monotonically decrease with x and is convex when x > 0, so ∀k,Φ′(rkg(rl) − ) is negative and decreases with . In addition, g(rl) increases with rl and is independent on , so
∂g(rl) ∂rl can be considered as a positive constant.
Therefore, ∂R(rl, )∂rl is negative and monotonically decreases with .
Now, we are ready to prove Corollary 1:
Proof. We subtract the left hand side from the right hand side in the inequality of Corollary 1:
[R(rj , 1)−R(ri, 1)]− [R(rj , 2)−R(ri, 2)] = ∫ rj ri ∂R(rl, 1) ∂rl drl − ∫ rj ri ∂R(rl, 2) ∂rl drl
= ∫ rj ri [ ∂R(rl, 1) ∂rl − ∂R(rl, 2) ∂rl ] drl
> 0 (25)
The last inequality is based on rj > ri, 2 > 1, Lemma 4, which indicates [ ∂R(rl, 1)
∂rl − ∂R(rl, 2)∂rl ] is always positive. We reorganize (25) and obtainR(ri, 1)−R(rj , 1) < R(ri, 2)−R(rj , 2).

heading: B.4 PROOF OF THEOREM 3
text: We start with the following lemma.
Lemma 5. Given the assumptions of Theorem 3, we define g(x) = E(y|x), z(x) = y − g(x) and consider γ = σ2l + h 2(C, )− C, then the following inequality holds.
∀a ∈ (0, 1),P(∃fw ∈ F : 1
n n∑ i=1 (yi − fw(x′i))2 ≤ C)
≤ 2e− na2γ2 8 + P(∃fw ∈ F : 1
n n∑ i=1 fw(xi)z(xi) ≥ 1 2 (1− 3a)γ)
(26)
Proof. Given the definition of h(C, ), we have:
(yi − fw(x′i))2 = [(yi − fw(xi)) + (fw(xi)− fw(x′i))]2
≥ (yi − fw(xi))2 + (fw(xi)− fw(x′i))2
≥ (yi − fw(xi))2 + h2(C, ) (27)
For the first inequality, x′i is the adversarial example which tries to maximize the loss objective, yi ∈ {−1,+1} and the range of fw is [−1,+1], so 〈yi − fw(xi), fw(xi) − fw(x′i)〉 ≥ 0. The second inequality is based on the definition of h2(C, ) in Definition 1. As a result, we can simplify the left hand side of (26) as follows:
P(∃fw ∈ F : 1
n n∑ i=1 (yi − fw(x′i))2 ≤ C) ≤ P(∃fw ∈ F : 1 n n∑ i=1 (yi − fw(xi))2 ≤ C − h2(C, ))
(28)
We consider the sequence {z(xi)}ni=1, it is i.i.d with Eµl(z(x)2) = Eµl [V ar(y|x)] = σ2l . Since the range of the prediction is [−1,+1], so z2(x) ∈ [0, 4]. Then, we have the following inequality by Hoeffding’s inequality (Hoeffding, 1994).
∀a ∈ (0, 1),P( 1 n n∑ i=1 z2(xi) ≤ σ2l − aγ) ≤ e− na2γ2 8 (29)
Similarly, we consider the sequence {z(xi)g(xi)}ni=1, the following inequality holds based on the Hoeffding’s inequality and the fact E(z(x)g(x)) = 0, z(x)g(x) ∈ [−2,+2].
∀a ∈ (0, 1),P( 1 n n∑ i=1 z(xi)g(xi) ≤ aγ) ≤ e− na2γ2 8 (30)
Now we study the right hand side of (28):
1
n n∑ i=1 (yi − fw(xi))2 = 1 n n∑ i=1 ( z2(xi) + (g(xi)− fw(xi))2 + 2z(xi)(g(xi)− fw(xi)) ) ≥ 1 n n∑ i=1 ( z2(xi) + 2z(xi)g(xi)− 2z(xi)fw(xi) ) (31)
Consider the following reasoning:
 1 n n∑ i=1 (yi − fw(xi))2 ≤ C − h2(C, ) = σ2l − γ 1 n n∑ i=1 z2(xi) ≥ σ2l − aγ 1
n n∑ i=1 z(xi)g(xi) ≥ −aγ
=⇒ 1 n n∑ i=1 z(xi)fw(xi) ≥ 1 2 (1− 3a)γ
(32)
As a result, we have:
P(∃fw ∈ F : 1
n n∑ i=1 (yi − fw(xi) ≤ C − h2(C, )))
≤P(∃fw ∈ F : 1
n n∑ i=1 z2(xi) ≤ σ2l − aγ) + P(∃fw ∈ F : 1 n n∑ i=1 z(xi)g(xi) ≥ −aγ)+
P(∃fw ∈ F : 1
n n∑ i=1 z(xi)fw(xi) ≥ 1 2 (1− 3a)γ)
≤2e− na2γ2 8 + P(∃fw ∈ F : 1
n n∑ i=1 z(xi)fw(xi) ≥ 1 2 (1− 3a)γ)
(33)
The first inequality is based on the reasoning of (32). The second inequality is based on (29) and (30).
Based on the inequality (28) and (33), we conclude the proof.
To further simplify the right hand side of (26), P(∃fw ∈ F : 1n ∑n i=1 z(xi)fw(xi) ≥ 1 2 (1− 3a)γ) needs to be bounded, and this is solved by the following lemma. Lemma 6. Given the assumptions of Theorem 3 and the definition of g(x), z(x) in Lemma 5, then the following inequality holds.
∀a ∈ (0, 1), a1 > 0, a2 > 0 and a1 + a2 = 1
2 (1− 3a),
P(∃fw ∈ F : 1
n n∑ i=1 z(xi)fw(xi) ≥ 1 2 (1− 3a)γ) ≤ 2|F|e− nm 144cL2 a21γ 2 + 2e− n 8 a 2 2γ 2 (34)
Proof. We recall that the data points {xi, yi}ni=1 are sampled from the distribution µl, which is c-isoperimetric. For any L-Lipschitz function f , we have:
∀t,P[|fw(x)− Eµl(fw)| ≥ t] ≤ 2e − mt2 2cL2 (35)
Since z(x) = y − g(x) ∈ [−2,+2], we can then bound P[z(x)(fw(x)− Eµl(fw)) ≥ t]: ∀t,P[z(x)(fw(x)− Eµl(fw)) ≥ t] ≤ P[|z(x)(fw(x)− Eµl(fw))| ≥ t]
≤ P[|(fw(x)− Eµl(fw))| ≥ t 2 ] ≤ 2e− mt2 8cL2 (36)
Here we utilize the proposition in (Vershynin, 2018; Van Handel, 2014)5, which claims if {Xi}ni=1 are independent variables and all C-subgaussian, then 1√
n
∑n i=1Xi is 18C-subgaussian. Therefore,
we have:
∀t,P[ 1√ n n∑ i=1 z(xi)(fw(xi)− Eµl(fw)) ≥ t] ≤ 2e − mt2 144cL2 (37)
Let t = a1γ √ n, then we have:
P[ 1
n n∑ i=1 z(xi)(fw(xi)− Eµl(f)) ≥ a1γ] ≤ 2e − nm 144cL2 a21γ 2
(38)
In addition, we can bound P[ 1n ∑n i=1 z(xi)Eµl(fw) ≥ a2γ] by:
P[∃fw ∈ F : 1
n n∑ i=1 z(xi)Eµl(fw) ≥ a2γ] ≤ P[ 1 n n∑ i=1 |z(xi)| ≥ a2γ] ≤ 2e− n 8 a 2 2γ 2
(39)
The first inequality is based on the fact Eµl(fw) ∈ [−1,+1]; the second inequality is based on Hoeffding’s inequality.
Now, we are ready to bound the probability P(∃fw ∈ F : 1n ∑n i=1 z(xi)fw(xi) ≥ 1 2 (1− 3a)γ).
P(∃fw ∈ F : 1
n n∑ i=1 z(xi)fw(xi) ≥ 1 2 (1− 3a)γ)
≤P[∃fw ∈ F : 1
n n∑ i=1 z(xi)(fw(xi)− Eµl(f)) ≥ a1γ] + P[∃fw ∈ F : 1 n n∑ i=1 z(xi)Eµl(fw) ≥ a2γ]
≤2|F|e− nm 144cL2 a21γ 2 + 2e− n 8 a 2 2γ 2 (40) The first inequality is based on the fact a1 + a2 = 12 (1− 3a); the second inequality is based on the Boole’s inequality (Boole, 1847), inequality (38) and (39).
5Proposition 2.6.1 in (Vershynin, 2018) and Exercise 3.1 in (Van Handel, 2014)
To simplify the constant notation, we let a = 18 , a1 = 3 16 and a2 = 1 8 . We plug this into the inequality (26) and (34), then:
P(∃fw ∈ F : 1
n n∑ i=1 (yi − fw(x′i))2 ≤ C) ≤ 4e −nγ 2 29 + 2|F|e− nmγ2 212cL2 (41)
Now we turn to the proof of Theorem 3.
Proof. We let FL = {fw|w ∈ W, Lip(fw) ≤ L}, Fγ = {fw|w ∈ W,w = γ4J z, z ∈ Z b} and Fγ,L = Fγ ∩ FL. Correspondingly, we letWL = {w|w ∈ W, Lip(fw) ≤ L}, Wγ = {w|w ∈ W,w = γ4J z, z ∈ Z b} and Wγ,L = Wγ ∩ WL. Because the diameter of W is W , we have
|Fγ,L| ≤ |Fγ | ≤ ( 4WJ γ )b . Here, means the element-wise multiplication.
Note that the inequality (41) is valid for any values of C as long as it satisfies γ ≥ 0. Based on this,
we apply the substitution  C ← C + 1 2 γ
γ ← 1 2 γ
, then:
P(∃fw ∈ Fγ,L : 1
n n∑ i=1 (yi − fw(x′i))2 ≤ C + 1 2 γ) ≤ 4e− nγ2 211 + 2|F|e− nmγ2 214cL2
≤ 4e− nγ2 211 + 2eb log( 4WJ γ )− nmγ2 214cL2
(42)
Based on the definition ofWγ,L, we can conclude that ∀w1 ∈ WL,∃w2 ∈ Wγ,L s.t.‖w1−w2‖∞ ≤ γ 8J . Therefore, ∀fw1 ∈ FL,∃fw2 ∈ Fγ,Ls.t.‖fw1 − fw2‖∞ ≤ γ 8 . Let choose such fw2 ∈ Fγ,L given an arbitrary fw1 ∈ FL, then:
(y − fw1(x))2 = (y − fw2(x))2 + (2y − fw1(x)− fw2(x))(fw2(x)− fw1(x))
≥ (y − fw2(x))2 − γ
8 |(2y − fw1(x)− fw2(x))|
≥ (y − fw2(x))2 − γ
2
(43)
The first inequality in (43) is based on Hölder’s inequality; the second inequality is based on y ∈ {−1,+1} and the range of ∀fw ∈ F is [−1,+1]. We combine (41) with (43), then:
P(∃fw ∈ FL : 1
n n∑ i=1 (yi − fw(x′i))2 ≤ C) ≤ P(∃fw ∈ Fγ,L : 1 n n∑ i=1 (yi − fw(x′i))2 ≤ C + 1 2 γ)
≤ 4e− nγ2 211 + 2eb log( 4WJ γ )− nmγ2 214cL2
(44)
Note that FL is the set of functions in F whose Lipschitz constant is no larger than L. We set the right hand side of (44) to be δ and then get L = γ27
√ nm
c(b log(4WJγ−1)−log(δ/2−2e−2−11nγ2 )) . This
concludes the proof.

heading: C EXPERIMENTAL SETTINGS

heading: C.1 GENERAL SETTINGS
text: The ResNet-18 (RN18) architecture is same as the one in (Wong et al., 2020); the WideResNet-34 (WRN34) architecture is same as the one in (Madry et al., 2018). Unless specified, the l∞ adversarial budget used for CIFAR10 dataset (Krizhevsky et al., 2009) 6 is 8/255 and for SVHN dataset (Netzer et al., 2011) 7 is 0.02. In PGD adversarial training, the step size is 2/255 for CIFAR10 and 0.005 for SVHN; PGD is run for 10 iterations for both datasets. For adversarial attacks using a different adversarial budget, the step size is always 1/4 of the adversarial budget’s size, and we always run it for 10 iterations. To comprehensively and reliably evaluate the robustness of the model, we use AutoAttack (Croce & Hein, 2020b), which is an ensemble of 4 different attacks: AutoPGD on cross entropy, AutoPGD on difference of logits ratio, fast adaptive boundary (FAB) attack (Croce & Hein, 2020a) and square attack (Andriushchenko et al., 2020). Unless specified, we use stochastic gradient descent (SGD) with a momentum to optimize the model parameters, we also use weight decay whose factor is 0.0005. Unless specified, the momentum factor is 0.9, the learning rate starts with 0.1 and is divided by 10 in the 1/2 and 3/4 of the whole training duration. The size of the mini-batch is always 128.
We run the experiments on a machine with 4 NVIDIA TITAN XP GPUs. It takes about 6 hours to adversarially train a RN18 model for 200 epochs, and a whole day to adversarially train a WRN34 model for 200 epochs.

heading: C.2 SETTINGS OF EXPERIMENTS IN SECTION 6
text: Algorithm 1: One epoch of the accelerated adversarial training we use in Section 6.1. Input: training data D, model f , batch size B, PGD step size α, adversarial budget S(p)( ), coefficient ρ, β. for Sample a mini-batch {xi, yi}Bi=1 ∼ D do ∀i, obtain the initial perturbation ∆i as in (Zheng et al., 2020). ∀i, one step PGD update: ∆i ← ΠS(p)( ) [∆i + αsign(O∆iLθ(xi + ∆i, yi)]). ∀i, update the cached adversarial perturbation ∆i as in (Zheng et al., 2020). if use reweight then ∀i, weight wi = softmax[f(xi + ∆i)]yi
else ∀i, weight wi = 1 end if ∀i, query the adaptive target t̃i and update: t̃i ← ρt̃i + (1− ρ)softmax[f(xi + ∆i)]. ∀i, the final adaptive target ti = β1yi + (1− β)t̃i Calculate the loss 1∑B
i wi
∑B i wiLθ(xi + ∆i, ti) and update the parameters.
end for
Fast Adversarial Training Our experiment on fast adversarial training is on CIFAR10 and = 8/255. The pseudocode of our method is demonstrated as Algorithm 1. We use ATTA (Zheng et al., 2020) to initialize the perturbation of each training instance. The step size α of the perturbation update is 4/255, same as (Zheng et al., 2020). The average coefficient ρ and β is 0.9 and 0.1 unless explicitly stated. Our learning rate scheduler also follows (Zheng et al., 2020): we train the model for 38 epochs, the learning rate is 0.1 on the first 30 epochs, it decays to 0.01 in the next 6 epochs and further decays to 0.001 in the last 2 epochs. When we use adaptive targets, the first 5 epochs are the warmup period in which we use fixed targets. Since the goal here is to accelerate adversarial training, we do not use a validation set to do model selection as in (Rice et al., 2020). We use the standard data augmentation on CIFAR10: random crop and random horizontal flip.
6Data available for download on https://www.cs.toronto.edu/ kriz/cifar.html. MIT license. Free to use. 7Data available for download on http://ufldl.stanford.edu/housenumbers/. Free for non-commercial use.
Adversarial Finetuning with Additional Data For CIFAR10, we use 500000 images from 80 Million Tiny Images dataset (Torralba et al., 2008) with pseudo labels in (Carmon et al., 2019) 8. For SVHN, we use the extra held-out set provided by SVHN itself, which contains 531131 somewhat less difficult samples. When we construct a mini-batch, half of its instances are sampled from the original training set and the other half are sampled from the additional data. The learning rate in the fine-tuning phase is always 10−3 and is always fixed. Since we only fine-tune the model for only 1 or 5 epochs, we do not use a validation set for model selection.

heading: D ADDITIONAL EXPERIMENTS AND DISCUSSION

heading: D.1 PROPERTIES OF THE DIFFICULTY METRIC
text: To study the factors affecting the difficulty function defined in (1), let us denote by d1, d2 the difficulty functions obtained under two different training settings, such as different network architectures or adversarial attack strategies. We then define the difficulty distance (D-distance) between two such functions in the following equation. In this regard, the expected D-distance between two random difficulty functions is 0.375.
D(d1, d2) = Ex∼U(D)|d1(x)− d2(x)| . (45)
We then study the properties of the difficulty metric of Equation (1) by performing experiments on the CIFAR10 and CIFAR10-C (Hendrycks & Dietterich, 2019) dataset, varying factors of interest. In particular, we first study the influence of the network by using either a RN18 model, trained for either 100 or 200 epochs (RN18-100 or RN18-200), or a WRN34 model trained for 200 epochs (WRN34). To generate adversarial attacks, we make use of PGD with an adversarial budget based on the l∞ norm with = 8/255. This corresponds to the settings used in other works (Hendrycks & Dietterich, 2019; Madry et al., 2018). The other hyper-parameters follow the general settings in Appendix C In the left part of Table 4, we report the D-distance for all pairs of settings. Each result is averaged over 4 runs, and the variances are all below 0.012. The D-distances in all scenarios are all very small and close to 0, indicating the architecture and the training duration have little influence on instance difficulty based on our definition.
We then perform experiments by varying the attack strategy using a RN18 network. As shown by the D-distances reported in the right portion of Table 4, the discrepancy between values obtained with clean, FGSM-perturbed and PGD-perturbed inputs is much larger, thus indicating that our difficulty function correctly reflects the influence of an attack on an instance. In addition, Table 5 demonstrates the D-distance between the difficulty functions based on clean instances, FGSMperturbed instance, PGD-perturbed instances and different common corruptions from CIFAR10C (Hendrycks & Dietterich, 2019)9. Note that (Hendrycks & Dietterich, 2019) only provides corrupted instances on the test set, so we train models on the clean training set and test model on corrupted test set in these cases. We use RN18 architecture and train it for 100 epochs in all cases, results are reported on the test set. Compared with the results in the left half of Table 4, the D-distance is much larger here. This indicates the difficulty function depends on the perturbation type applied to the input, including the common corruptions.
The results in Table 4 and 5 demonstrate that our difficulty metric mainly depends on the data and on the perturbation type; not the model architecture or the training duration.
8Data available for download on https://github.com/yguooo/semisup-adv. MIT license. Free to use. 9Data available for download on https://github.com/hendrycks/robustness. Apache License 2.0. Free to use.
In the definition of our difficulty metric in Equation (1), the difficulty of one instance is based on its average loss values during the training procedure. It is intuitive, because the values of the loss objective represents the cost that model needs to fit the corresponding data point. The bigger this cost is, the more difficulty this instance will be. To make the metric stable and prevent the metric from being sensitive to the stochasticity in the training dynamics, we use the average value of the loss objective for each instance to define its difficulty. In addition to the average loss objectives, we can also use the average 0-1 error to define the difficulty function. In Figure 3, we plot the relationship between the difficulty metric based on the average loss values and the one based on the average 0-1 error for instances in the CIFAR10 training set when we train a RN18-100 model and a WRN34 model. We can see a strong correlation between them for both models. The correlation of the difficulty measured by two metrics for the same instance is 0.9466 in the RN18-100 case and 0.9545 in the WRN34 case. The high correlation indicates we can use either metric to measure the difficulty. Since the loss objective values are continuous and finer-grained, we choose it as the basis of the difficulty function we use in this paper.

heading: D.2 EXAMPLES OF EASY AND HARD INSTANCES OF CIFAR10 AND SVHN
text: Figure 20 and 21 demonstrate the easiest and the hardest examples of each class from CIFAR10 and SVHN, respectively. The difficulty of these instances is calculated based on PGD attacks. We can see most easy examples are visually consistent, while most hard examples are ambiguous or even incorrectly labeled.

heading: D.3 TRAINING ON A SUBSET
text: Different Optimization Method on Hard Instances We find the failure of PGD adversarial training on the hardest 10000 instances of CIFAR10 training set does not arise from the optimizers. In Figure 5, we use SGD with different initial learning rates (“SGD, lr=1e-2” and “SGD, lr=1e-3”) and the adaptive optimizer such as Adam (Kingma & Ba, 2014) (“Adam, lr=1e-4”). The learning rate of SGD optimizer decrease to its 1/10 in the 100th and 150th epoch, while the learning rate of Adam optimizer is fixed during training. Although optimizers like Adam can make the model fit the training subset better, none of these methods can make the robust test accuracy significantly above the chance of random guesses, i.e., 10%.
Longer Training Duration In Figures 7 and 8, we conduct adversarial training for a longer duration until the loss on the hard training instances converges. Specifically, the model is trained for 600 epochs, with a learning rate is initialized to 0.1 and divided by 10 after every 100 epochs. In Figure 7, we adversarially train a RN18 model on the hardest 10000 training instances. Our conclusions from Section 4.1 still hold: Adversarial training on the hard instances leads to much more severe overfitting, greatly widening the generalization gap. In Figure 8, we adversarially train a RN18 model on the whole training set and calculate the average loss on the groups G0, G3, G6 and G9. Similarly to training for 200 epochs, the model first fits the easy training instances and then the hard ones. This can be seen by the fact that the average loss of G9 decreases much faster in the beginning and quickly saturates. In other words, the harder the group, the later we see a significant decrease in its average loss value. This observation is also consistent with our findings in Section 4.2.
Results on SVHN dataset Figure 6 demonstrates the learning curves of PGD adversarial training based on a subset of the easiest, the random and the hardest instances of SVHN dataset. We let the size of each subset be 20000, because the training set of SVHN is larger than that of CIFAR10. The model architecture is RN18 in these cases. We have the same observations here: training on the hardest subset yields trivial performance, training on the random subset has significant generalization decay in the late phase of training while training on the easiest subset does not.
Different Values of and l2-based Adversarial Budget Figure 4 and Figure 9 demonstrate the learning curves of RN18 models under different adversarial budgets on CIFAR10, in both l∞ and l2 cases. In l∞ cases, the adversarial budgets are 2/255, 4/255 and 6/255; in l2 cases, the adversarial budgets are 0.5, 0.75 and 1. With the increase in the size of the adversarial budget, we can see a clear transition from the vanilla training: more and more severe generalization decay when training on the random or the hardest subset.
Training with Different Amount of Data In Figure 10, we compare the learning curves of PGD adversarial training on increasing more training data, with the easiest ones coming first. If we do model selection on a validation set as in (Rice et al., 2020), the selected models are still better on both CIFAR10 and SVHN when they are trained with more data, although the final models in these cases are not necessarily better. The results indicate the hard instances are still useful to improve the model’s performance, but we need to utilize them in a different way.

heading: D.4 LIPSCHITZ ANALYSIS
text: We conduct numerical analysis to validate Theorem 2 of Section 5.2. Calculating the exact Lipschitz constant of a neural network models is NP-hard, so we utilize the method introduced in (Scaman & Virmaux, 2018) to derive the upper bound of Lipschitz constants instead. We use CIFAR10 as the dataset and RN18 as the network architecture.
Table 6 demonstrates the upper bound of the Lipschitz constant of models trained in different settings. In the l∞ cases, we set to be 2/255, 4/255 and 8/255; in the l2 cases, we set to be 0.5, 0.75 and 1. Due to the stochasticity introduced by power method, we run the algorithm in (Scaman & Virmaux, 2018) for 20 times and report the average, we find the variance is negligible. Based on the results in Table 6, it is clear that models adversarially trained by the hard training instances have much larger Lipschitz constant than the ones by the easy training instances in all cases.
Figure 11 demonstrates the curves of the Lipschitz upper bound when the model is adversarially trained by the easiest, the random and the hardest 10000 instances. The adversarial budget is l∞ norm based and = 8/255. We can clearly see that as the training goes, the Lipschitz upper bound increases in all cases, which is consistent with our analysis in Section 5.2. In addition, compared with training on easy instances, the Lipschitz upper bound of the models adversarially trained on hard instances increases much faster.

heading: D.5 REVISITING EXISTING METHODS MITIGATING ADVERSARIAL OVERFITTING
text: Existing methods mitigating adversarial overfitting can be generally divided into two categories: one is to use adaptive inputs, such as (Balaji et al., 2019); the other is to use adaptive targets, such as (Chen et al., 2021b; Huang et al., 2020). Both categories aim to prevent the model from fitting hard input-target pairs. In this section, we pick one example from each category for investigation. We provide the learning curves of the methods we study in Figure 12. We use the same hyper-parameters as in these methods’ original paper, except for the training duration and learning rate scheduler, which follow our settings. These methods clearly mitigate adversarial overfitting: The robust test error does not increase much in the late phase of training, and the generalization gap is much smaller that that of PGD adversarial training.
Instance-Adaptive Training Using an instance-adaptive adversarial budget has been shown to mitigate adversarial overfitting and yield a better trade-off between the clean and robust accuracy (Balaji et al., 2019). In instance-adaptive adversarial training (IAT), each training instance xi maintains its own adversarial budget’s size i during training. In each epoch, i increases to i + ∆ if the instance is robust under this enlarged adversarial budget. By contrast, i decreases to i − ∆ if the instance is not robust under the original adversarial budget. Here, ∆ is the step size of the adjustment.
We use the same settings as in (Balaji et al., 2019) except that we use the same number of training epochs and learning rate scheduling as the one in other experiments for fair comparison. Specially, we set the value of and ∆ to be 8/255 and 1.9/255, respectively, same as in (Balaji et al., 2019). The first 5 epochs are warmup, when we use vanilla adversarial training (Madry et al., 2018).
Figure 13 demonstrate the relationship between the instancewise adversarial budget i and the corresponding instance’s difficulty d(xi). It is obvious that they are highly correlated: the correlation is 0.844. Therefore, instance-adaptive training adaptively uses smaller adversarial budgets for hard training instances, which prevents the model from fitting hard input-target pairs.
Self-Adaptive Training Self-adaptive training (SAT) (Huang et al., 2020) solves the adversarial overfitting issue by adapting the target. By contrast with common practice consisting of using a fixed target, usually the ground-truth, SAT adapts the target of each instance to the model’s output. Specifically, after a warm-up period, the target ti for an instance xi is initialized as a one-hot vector by its ground-truth label yi and updated in an iterative manner after each epoch as ti ← ρti + (1− ρ)oi. Here, ρ is a predefined momentum factor and oi is the output probability of the current model on the corresponding clean instance. SAT uses the loss of TRADES (Zhang et al., 2019b) but replaces the ground-truth label y with the adaptive target ti: LSAT (xi) = L(xi, ti) + λmax∆i∈S( )KL(oi||o′i), where KL refers to the Kullback–Leibler divergence and λ is the weight for the regularizer. Furthermore, SAT uses a weighted average to calculate the loss of a mini-batch; the weight assigned to each instance xi is proportional to the maximum element of its target ti but
normalized to ensure that all instances’ weights sum up to 1. By weighted averaging, the instances with confident predictions are strengthened, whereas the ambiguous instances are downplayed.
Similarly, we use the same settings as in (Huang et al., 2020) except we use the same number of training epochs and learning rate scheduling: we train the model for 200 epochs and the first 90 epochs are the warmup period.
Figure 14 demonstrates the average weight assigned to instances belonging to the group G0, G3, G6 and G9. It is clear that the hard instances are assigned much lower weights than the easy instances. For example, the weight assigned to G0, the easiest 10% training instances, is close to 1, while the weight assigned to G9, the hardest 10% training instances, is only around 0.4. Furthermore, Figure 15 shows the accuracy of the group G0, G3, G6 and G9 during training using the original ground-truth label 1y and the adaptive target t, respectively. For the adaptive target, one adversarial instance x′ is considered to be correctly classified if and only if arg maxi fw(x
′)i = arg maxi ti. For easy instances, 1y is mostly close to t, so accuracy in both cases is high and the gap between them is small. For hard instances, 1y is usually not consistent with t, while accuracy under the adaptive target t is much higher than the group-truth label y. This indicates self-adaptive training makes adaptive target easier to fit for the originally hard instances.

heading: D.6 EXTRA RESULTS AND DISCUSSION ON FAST ADVERSARIAL TRAINING
text: We also conduct ablation study in the context of fast adversarial training. In Figure 16, we change the value of β in our algorithm (pseudocode in Algorithm 1) and plot the learning curves. Lower the value of β is, more weights assigned to the adaptive part of the target: β = 0 means we directly utilize the moving average target as the final target, β = 1 means we use the one-hot groundtruth
label. Figure 16 clearly shows us the generalization gap decreases with the decrease in β. That is to say, the adaptive target can indeed improve the generalization performance.
Figure 17 compare the learning curves of ATTA (Zheng et al., 2020) with and without reweighting. The first 5 epochs are the warmup period. The results confirm that the reweighting scheme can prevent adversarial overfitting and decrease the generalization gap.
To confirm that the algorithm we use is consistent with our theoretical and empirical analysis in Section 4 and 5, we study the relationship between the instance difficulty and the weight assigned to them when using reweighting, as well as the soft target when using adaptive targets. Since the evaluation of model robustness is based on the PGD attack, the difficulty value here is based on the PGD perturbation. In Figure 18, we demonstrate the relationship between the difficulty value and the average assigned weight for each instance when using reweighting. We calculate the correlation between these two values on the training set, it is 0.8900. This indicates we indeed assign smaller weights for hard training instances and assign bigger weights for easy training instances. In Figure 19, we show the relationship between the difficulty value and the average value of the true label’s probability in the soft target when we use the adaptive targets. Similarly, we calculate the correlation between these two values on the training set, it is 0.9604. This indicates the adaptive target is similar to the ground-truth one-hot target for the easy training instances, while the adaptive target is very different from the ground-truth one-hot target for the hard training instances. This means, adaptive targets prevent the model from fitting hard training instances while encourage the model to fit the easy training instances.

heading: D.7 EXTRA RESULTS AND DISCUSSION ON ADVERSARIAL FINETUNING
text: We conduct ablation study and the results are demonstrated in Table 7. It is clear that both reweighting and the KL regularization term benefit the performance of the finetuned model.

Review summaries:
This paper proposes a metric to measure the difficulty of training examples and find that hard training examples influence the generalization of adversarial training and cause overfitting in adversarial training. The authors also provide a theoretical analysis. To mitigate the issue caused by hard training examples, the authors propose to assign different weights for training examples based on loss values. The evaluation results show that the proposed training methods can improve robustness in fast adversarial training and adversarial fine-tuning with additional data. 

This paper began by analyzing the influence of hard adversarial examples. And, they found that hard adversarial examples may be the major reason leading to robust overfitting. Then, based on these observations and analysis, the authors further introduced a Fast Adversarial Training scheme, which can achieve competitive results compared to baselines.  

This paper proposes a metric for measuring the difficulty of instances. The authors empirically show that hard instances lead to the issue of robust overfitting. Theoretical analysis on logistic regression and general nonlinear model indicates that as the increase of instance difficulty, the adversarial vulnerability becomes higher. Finally, this paper proposes a reweight strategy and the trick of adaptive label for improving the adversarial robustness.