On the Impact of Hard Adversarial Instances on Overfitting in Adversarial Training
Authors: Chen Liu
Zhichao Huang
Mathieu Salzmann
Tong Zhang
Sabine Süsstrunk
Venue: ICLR 2022 Submitted (2022)

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.
To this end, we provide a quantitative and model-agnostic 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.
In addition, this gap in generalization performance is larger in adversarial training.
Finally, we investigate solutions to mitigating 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 adaptively using training data can improve model's robustness.

Under review as a conference paper at ICLR 2022
ON THE IMPACT OF HARD ADVERSARIAL INSTANCES ON OVERFITTING IN ADVERSARIAL TRAINING
Anonymous authors Paper under double-blind review
ABSTRACT
Adversarial training is a popular method to robustify models against adversarial attacks. However, it exhibits much more severe overfitting than training on clean imputs. In this work, we investigate this phenomenon from the perspective of training instances, i.e., training input-target pairs. We provide quantitative metric measuring the difficulty of an instance in the training set and analyze the model's s behavior on instances of different difficulty levels. This lets us show that the decay in generalization performance of adversarial training is result of the model's 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 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.
INTRODUCTION
The existence of adversarial examples (Szegedy al. 2014) causes serious safety concerns when deploying modern deep learning models. For example, for classification tasks, imperceptible pertur- bations of the input instance can fool state-of-the-ar 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. (020), 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. 20 8)
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. (2019) as the most effective and popular approach
to construct robust models. Unfortunately, adversarial training yields much worse performance
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. (020) or model smoothing (Chen 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 quantitative metric 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 's Lipschitz constant when the model is well fit to the adversarial training examples. This bound increases with the

---

Under review as a conference paper at ICLR 2022
difficulty level of the training instances and the size of the adversarial budget. Since larger Lipschitz constant indicates a higher adversarial vulnerability (Ruan et al. 2018 Weng et al. 220 8a 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 avoid fitting hard input- target 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 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, and w' are the clean input and its adversarial counterpart. We use Su to represent a model parameterized by w and omit the subscript w unless ambiguous. o= fw fwx) and o' fw'( are the model's output of the clean input and the adversarial input. (x, y) and Cw (x', yy represent the loss of the clean and adversarial instances, receptively. in which we sometimes omit w and y for notation simplicity. We use || and ||]|| to represent the 12 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 O. 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) (e) = { ااا|ااك < e}, with e defining the budget size. Therefore, given the training set D, the robust learning problem can be formulated as the min-max optimization minw Eg max (e)) fw x + A). A notation table is provided in Appendix A
In this paper, vanilla training refers to training 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 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 overfutinng 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 anonymously
2 RELATED WORK
We concentrate on white-box attacks, where the attacker has access the model parame- ters. Such attacks are usually based on first-order information and stronger than black-box at- tacks (Andriuscchenko 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 's sign, i.c., A siiniiiviiaa Cv (z)) The iterative fast gradient sign method (IFGSM) (Kurakin et al. 2016) iteratively runs FGSM using smaller step size and projects the perturbation back to the ad 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 model against adversarial attacks (Buckman et al. 2018 Dhillon et al. 2018 Ma et al. 2018: Pang et al. 2020 2019: SSaaangouei et al. 2018 Xiao

---

Under review as a conference paper at ICLR 2022
et al. 2020). However, most of them were shown 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 al. 2019) Gowal et al.] 2019 RRahhunthhan al. 2018 Salman et al., 22199] WWong& & Kolter] 2018). Unfortunately, these methods either do not generalize to modern network architectures or have a prohibitively large computational complexity. As consequence,
adversarial training (Madry et al. 2018) and its variants (Alayrac et al. 2019: Carmon et al. 2019] Hendryckk et al., 10019]Kuman et al. 2019 Wu et al., 2020,[Zhang
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 poor convergence behavior (Liu 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 a separate validation set to improve the generalization performance in adversarial training. Furthermore, (Chen et al., (021b) 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 al., 2020; Zhang et al. 202I) but without solving the adversarial overfitting issue. By contrast, other works (Balaji et al. 2019 Huang et al. (2200) were empirically shown to mitigate adversarial overfitting but without providing any explanations as how this phenomenon was addressed. In this paper, we study the causes of adversarial overfitting from both an empirical and 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.
3 A METRIC FOR INSTANCE DIFFICULTY
Parametric models are trained to minimize 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, introduce 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 æ's corresponding perturbed input across all training epochs. We define the difficulty of an instance æ within a finite set D as
d(æ=) =P((()) < [ U(D) + P(C(z) (())
1
(I)
where ã ~ (DD indicates H uniformly sampled from the finite set D. d(xx) is 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. 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 æ within a set under a specific type of perturbation.
INSTANCE DIFFICULTY AND ADVERSARIAL OVERFITTING
The model-agnostic difficulty metric of Section 3 allows us to select training instances based on their difficulty. In Figures 20 and of of Appendix D.2. we show some samples of the easiest and the hardest instances of each class in CIFAR1O (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 much more diverse, some of them being ambiguous 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
4.1 USING A SUBSET OF TRAINING DATA
We start by training RN18 models for 200 epochs using either the 10000 easiest, random or hardest instances of the CIFARIO training set via either vanilla training, FGSM adversarial training or PGD)
3

---

Under review as a conference paper at ICLR 2022
adversarial training. The adversarial budget is based on the to norm and 8/255. Note that the instance's 's difficulty is defined under the corresponding perturbation type, and we enforce these subsets to be class-balancee For example, the easiest 10000 instances consist of the casiest 1000 instances in each class. We provide the learning curves under different settings in Figure
Easy 20k
6:2
150 175
355
1000
Epecn
Spech
Epech
(a) PGD Adversarial Training
(b) FGSM Adversarial Training
(c) Vanilla Training
Figure I: Learning curves obtained by training on the 10000 easiest, random and hardest instances of CIFARIO under different scenarios. The training error (dashed lines) is the error on the selected instances, and the test error (solid lines) is the error on the whole test set.
For PGD adversarial training, in Figure ((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 not due to improper optimization.
In contrast to PGD, FGSM adversarial training and vanilla training (Figure [(b)
[(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 c, and for adversarial budget based on the 12 norm. We show that more severe adversarial overfitting happens when the size of the adversarial budget increases. Furthermore, training instances, start with the easiest ones. Our results in Figure show that the models can benefit from using more data, but only using early stopping done in (Rice et al., 20220). This indicates that the hard instances can still benefit adversarial training, but need to be utilized in an adaptive manner.
experiment with training models using increasingly many
4.2 HARD INSTANCES LEAD TO OVERFITTING
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 {G, ) with G; = {æ E Djo.1 x i I d(xx) < 0.1 x (i ( 1))- That is, Go is the hardest group, whereas Go the easiest one. We then train an RNI8 model on the entire CIFAR10 10 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 Gu. Gs. Gs and Gy. The resulting curves show that, in the early training stages, the model first fits the easy instances, evidenced by the average loss of group Gy 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 Go 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 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, activations. As shown in Figure [66] the model first focuses on extracting robust features for the easy instances, evidenced by the comparatively large activations of the instances in Gg. In the late
monitor the group-wii wise average magnitudes of the penultimate layer's
4

---

Under review as a conference paper at ICLR 2022
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.
3.0
0.8
10%
0.8
Easiest 30% 400%
2.5
0.7
Festure Magnitude
Hardlest 30%--00%
0.7
Hardest top
2.0-
0.6
1.5
0.5
0.4
1.0-
0.3
0.3
0.2
0.2
0.0
0.1
1
150
175
Epoch
Epoch
(a) Average loss.
Average of extracted features.
Figure 2: Analysis the groups Go. G3. G6 and G9 in the training set. The right vertical axis corresponds to the training (dashed grey line) and test (solid grey line) error under adversarial attacks for both plots. Left plot: The left vertical axis represents the average loss of different groups. Right plot: The left vertical axis represents the average 12 norm of features extracted during training for different groups
THEORETICAL ANALYSIS
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 analytical expression, and then generalize our analysis to the nonlinear cases. We use (æ,, y: to represent the training data, and (X, v. its matrix form. {a/, Y1 1 N- and (X', y) are their adversarial counterparts. Here, I; E R",, ys E +1], X
R g and y f-1,,+11 +1}". The notation used for our theoretical
analysis is summarized in Table 3 of Appendix A
5.1 LOGISTIC REGRESSION
We study the logistic regression model under an l2 norm based adversarial budget. In this case, the model parameterized by RT and outputs sign(w" (a/x)) given the adversarial example 2 of the input æ4. The loss function for this instance 14 We assume over-parameterrzaaion,,
which means < m.
The following theorem shows that, under mild assumptions, the parameters of the adversarially trained logistic regression model converge to the la max-margin direction of the training data.
Theorem 1. For dataset (æ,, y/ ) that linearly separable under the adversarial budget S (2) (c), any initial point wy and step size a I 2 | the gradient descent Wa+1 = w., a w Lw.. (X')
converges asymptotically the 12 max-margin vector the training data. That is,
i0
lim 400
where in arg min [|w] w
8.1. Vi E (1,2,.., n), w 2; 21
(2)
The proof is deferred to Appendix B. Theorem I Textends the conclusion in (Soudry et al. 201 8),
which only studies the non-adversarial case. 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
definition in Section D
To further study how the training instances' difficulty influences the model's 's generalization perfor- mance, assume that the data points drawn from a K K-mdde Gaussian mixture model (GMM). Specifically, the k-th component has a probability of being sampled and is formulated as follows:
if y/ +1, æ; Arrr I); if y, -1, ((-rkn.
(3)
5

---

Under review as a conference paper at ICLR 2022
Here, 17 I. is the unit vector indicating the mean of the positive instances, and 1% E R+ controls the average distance between the positive and negative instances. The mean values of all modes in this GMM are colinear, Without the loss of generality, we assume r11 < 12 < < fr-- 1 < Tkk As in Section 4 we consider models trained with the subsets of the training data, e.g., instances from the 1-th component. / = 1 then indicates training on the hardest examples, while = K means using the easiest. In matrix form, we have X rryn" + Q for the instances sampled from the /-th component, where the rows of noise matrix Q are sampled from N(O, I).
rg. indicates the difficulty of instances sampled from the k-th component.
Although the max margin direction in Equation 2 where the parameters converge based on Theo- rem L does not have an analytical expression, the results in (Wang & Thrampoulidis (020) indicate that, in the over-parameteriiation regime and when the training data 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 X ("(X"")-1 y. we can then calculate the exact generalization performance of the trained model as stated in the following theorem.
Theorem 2. a logistic regression model is adversarially trained on n separable training instances sampled from the 1-th component of the GMM model described in (3). If n alog is suffiiiently large"
then with probability 1 - (2)), the expected adversarial test error R. under the adversarial budget s(2) (e), which is a function of ri and e, on the whole GMM model described in (3) is given by
K R(ri,)) e) = D (rug(n)) -),, g(ri) = -C1 C27 - o(17) =
)2, C1 C2 C2 20.
(4)
k=1
C1 C2 are independent of and rı. The function + defined as $ {(x) = P(Z > x), ~ NO 1).
We defer the proof of Theorem 2 to Appendix B.2 in which we calculate the exact expression of R(r1: e), C1, C2. and show that C1. C2 are positive numbers almost surely. Since C₁ and C2 are independent of rı, and (xx) is monotonically decreasing function, we conclude that the robust test error R(ri, E) becomes smaller when ri increases. That is, when the training instances become casier, the corresponding generalization error under the adversarial attack becomes smaller.
Theorem 2 holds for all e 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 of R in Equation 4 ifel E2.
then we have A S i < j < K, R(r,, - RR 61) < R(r,, 62) - R(r,,
The proof is in Appendix B.3 This indicates that, compared with training on clean inputs, i.e., the generalization performance of adversarial training with e >> 0 is more sensitive to the difficulty of the training instances. This is consistent with our empirical observations Figure
5.2 GENERAL NONLINEAR MODELS
In this section, we study the binary classification problem using general nonlinear model. We consider a model with b parameters, i.e., w E RR. Without loss of generality, we assume the output of the function fw to lie in [-1, +1]. Furthermore, Assumption 1. The data distribution μ is a composition of K c-isoperimetric distributions on Rmm each of which has positive conditional variance. That is, μ Σk= Oiklik, where ag > 0 K and Σk=1 ag 1. We define of
assume isoperimetry of the data distribution:
Eng [Varly|>]] and without loss of generality assume that oi 2 02 ... 2 Fo > O. Furthermore, given any LLipsschrz,functiin far i.e., Vz,, 22, (x
fu (2)) < L. .. æ211, we have
Vk E {1. 2, .... K} P(x pas (x) Ep (fw) |1 2 8) < 2e
2
(5)
This is a benign assumption; the data distribution a mixture of K components and each of them contains samples from sub-Gaussian distribution. These components correspond to training
Specifically, m and n need to satisfy m > 10m log n + and m Chriy/log 2mj mm/l The constant
C' is derived in the proof of Theorem 1 in (Wang & Thrampoulidis 2020

---

Under review as a conference paper at ICLR 2022
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 {æ,, Yi Yiy the model swo the udversarial budget S(z) and a positive constunt C, we define the function h(C,,) e)
1
n (ffu(())) - --) =0²=c0
e(C,e)= = min min hi,))) stt. T(C,c) - w (ET(C,e)
n
(6)
where hi maxç, s.t. (fw(()))) - C, (ao + 5) C [wo( + e
E (
Here, x; is the adversarial example of æ. We omit the superscript (p) for notation simplicity.
By definition, hi,w(() 2 0 depicts the bandwidth Ç of the model's output range in the domain of the adversarial budget on a training instance. h(C, e) is the minimum bandwidth among the models whose mean squared error on the adversarial training set smaller than C. Based on the definitions of T and hi and for fixed value of C, we have Ve, < 62, ( S ((22) and e2), C T(C, e1).
). As a result, Vei < E2, E1) S e2),, In addition, since VO1 < C2. e(C C T(C2, e) for a fixed value of e, we have VC1 < C2. e(C),e) 2 e(C2,e). That is to say, h(C, c) is a monotonically non- -endeeceaa function on and a monotonically non- non-increasing function on C. In practice, when fw represents deep neural network, h(C,e) e) 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 {æt; y/ Vi sampled from the l-th component pr of the distribution in Assumption I the parametric model fw. the adversarial budget S(P) (c) and the corresponding function h defined in Definition [ we assume that the model fw is in the function space F {fw: wD E W) with W C RK' having a finite diameter diam(W) S W and, Vwn, w2 E -W11lfu. We train the model fw adversarially using these n data points. Let x be the adversarial example of the data point x and 5 E (0, we have +. >i=( (fa((z)) 32 C 2 0, then with probability at least - 6, the Lipschitz constant of s is
f ol S Jlww 1aw1--wlleee
and y := of + (²(CC,) C
lower bounded as
Lip(Sw) Z 27 (bllgg (WW log(6/2- 2c-2 )))9))=
71772
where Lip(fw) is the Lipschitz constant of fw: Væi, Z2, fl (211 - fwo (I2)) S Lép(fw)]la x2I|
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 >> maxfc, m, n). In this case,
approximate the lower bound
(7) by Lip(fw) Z 27 V be bolo and the right hand side increases with y. Since ==
nm
oi + h²(C,e) C, the lower bound increases with both 0i and but decreases C' increeses.
The Lipschitz constant is widely used to bound model's 's adversarial vulnerability (Ruan et al. Weng et al. 2018a b): larger Lipschitz. constants indicate higher adversarial vulnerability. Recall that y 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 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 d in our theorem; using the same training instances, the adversarial vulnerability increases with the adversarial budget measured by e. 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.
2018
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).
7

---

Under review as a conference paper at ICLR 2022
6 MITIGATING ADVERSARIAL OVERHITTING
Existing methods mitigating adversarial overfitting study the standard adversarial training scenario: PGD adversarial training from scratch. In Appendix [D. we show that they use either adaptive inputs (Balaji et al. 2019) or adaptive targets (Huang et al. 2020: Chen et al. 202 to implicitly avoid fitting hard imput-tatee target pairs, thus providing an explanation for their success.
Below, we study two settings other than standard adversarial training: fast adversarial training and adversarial line-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
6.1 FAST ADVERSARIAL TRAINING
Adversarial training in (Madry et al. 2018) introduces a significant computational overhead. Thus is desirable to accelerate this method. Our experiments 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 ensure that the weights in 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 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 improve the performance. For each training instance (zr 3), we maintain an adaptive moving average target t. is updated in an exponential average manner in each epoch x- pt + (1 p)o' where p is the momentum factor. This similar to the target in (Huang et al. 2020). but, similarly to the reweighting scheme, we use the adversarial output of instead of the clean output o to avoid an increase in computational complexity. The final adaptive target we use
= B,, + (1 - B) and thus the loss objective is (x',,,, t). The factor
3 controls how "adaptive" " our target is: 3 = O yields a fully adaptive moving average target t and yields one-hot target 1y. We provide the pseudocode Algorithm
Appendix C.2
We run experiments on CIFARIO using WRN34 models under the L.c adversarial budget of size 8/255. the standard setting where most fast adversarial training algorithms are benchmarked (Croce ct al. (020).. We evaluate the model's '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 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 al. (020) 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 decrease in decreases the generalization gap. This indicates that the more adaptive the targets, the smaller the generalization gap.
6.2 ADVERSARIAL FINETUNING WITH ADDITIONAL DATA
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 traning data, because we also small learning rate to fine-tune model. While additional training data was
8

---

Under review as a conference paper at ICLR 2022
Duration
Method
AA
Method
Model
Epochs Complexity AA
WRN34 on CIFARIO, =
8/255
Shafahi et al.
2019)
WRN34
200
2
41.17
No Fine Tuning
52.01
Wong el al.
2020)
RN18
15
4
43,21
Vanillä AT
54.17
Epoch
Zheng
20220)
WRN34
38
4
44.48
Ours
54.69
Zhang al.
2019a)
WRN34
105
44.83
Vanilla AT
55.49
5 Epoch
CChen ct al
2021a)
WRN34
100
7
51.12
Ours
56.99
Reweighting (Ours)
WRN34
38
4
46.15
RNI8 on SVHN,
0.02
Adaptive Target (Ours)
WRN34
38
4
51.17
No Fine Tuning
67.77
Vanīllä AT
70.81
Table I: Comparison between different accelerated adver- sarial training methods in robust test accuracy against Au- toAttack (AA). The baseline results are from RobustBench. Complexity shows the number of forward passes and back- ward passes in one mini-batch update.
1 Epoch
Ours
72.53
Vanilla AT
72.18
5 Epoch
Ours
73.35
Table 2: Robust accuracy of fine-tuned models against AutAAAtack(AA).
shown be beneficial in (Alayrac al. 2019 Carmon 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 CIFARIO 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 to 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 al. 2019) and (Huang et al. 2020) are not applicable here.
the best choice. The model is fine-tuned for either
Our first technique, reweighting, is the same as in Section 6.1 In addition to reweighting, 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 usually both misclassified. Therefore, the clean outputs of these instances constitute simpler targets compared with the ground-truth labels. Ultimately, the loss objective of mini-batch L used for fine-tuning is expressed as = wi [e (xx) + XKL(o,, where w; is the adaptive weight when we use re- re-weighting, or 1/B otherwise. À is when using the regularization term and 0 otherwise.
(rr((x,) = i=
We use both reweighting and KL regularization to fine-tune the model. Our results are shown in Table where the robust test accuracy is also evaluated by AutoAttack. 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 improve the generalization performance in adversarial fine-tuning with additional training data.
7 CONCLUSION
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 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 ever-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 ''s robustness.

---

Under review as a conference paper at ICLR 2022
ETHICS STATEMENT
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, we are using publicly available data and models.
REPRODUCIBILITY STATEMENT
The experimental settings of our empirical study are demonstrated in detail in Appendix C Especially, we also provide the pscudocode our algorithm there. Our code is submitted anonymously on GoogleDrive It will be made publicly available when our work is published.
REFERENCES
Jean-Baptiste Alayrac, Jonathan Uesato, Po-Sen Huang, Alhussein Fawzi, Robert Stanforth, and Pushmeet Kohli. Are labels required for improving adversarial robustness? In Advances in Neural 2019.
Information Processing Systems, pp.
Maksym Andriushchenko, Francesco Croce, Nicolas Flammarion, and Matthias Hein. Square attack: query-efficient black-box adversarial attack via random search. In European Conference Computer Vision, pp. 484-501. Springer, 2020.
Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give false sense of security: Circumventing defenses to adversarial examples. arXiv preprint (002:008000042) 2018.
Yogesh Balaji, Tom Goldstein, and Judy Hoffman. Instance adaptive adversarial training: Improved accuracy tradeoffs in neural nets. arXiv preprint arXiv:1910.08055/ 2019.
George Boole. The mathematical analysis of logic. Philosophical Library, 1847.
Sébastien Bubeck and Mark Sellke. A universal law of robustness via isoperimetry. arXiv preprint trXiv:2105.12806 2021.
Jacob Buckman, Aurko Roy, Colin Raffel, and Ian Goodfellow. Thermometer encoding: One hot way to resist adversarial examples. In International Conference Learning Representations, 2018. URL httl:tttss//pppneeeett
Yair Carmon, Aditi Raghunathan, Ludwig Schmidt, John C Duchi, and Percy S Liang, Unlabeled data improves adversarial robustness. In Advances Neural Information Processing Systems, pp. 11190-11201 1201, 2019.
Jinghui Chen, Yu Cheng, Zhe Gan, Quanquan Gu, and Jingjing Liu. Efficient robust training via back- ward smoothing, 2021a. http:/pse/ooeeeeeeeieeeeeteeeeee
Loue
Tianlong Chen, Zhenyu Zhang, Sijia Liu, Shiyu Chang, and Zhangyang Wang. Robust overfitting may be mitigated by properly learned smoothening. International Conference on Learning Representations, 2021b. htt.::hts////cmmm //tp///eee////eeee..eee..roo wttp://wwwwwwwwweeeeeeeeeeee.eee www.ee/e//ooddddooooem wtt.::/eeeeorrmmiii--aoa//////2.
Jeremy M Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized
smoothing. arXiv preprint 1902.02990 2019.
Francesco Croce and Matthias Hein. Minimally distorted adversarial examples with fast adaptive boundary attack. In International Conference on Machine Learning, pp. 2196-2205. PMLR, 2020a.
Francesco Croce and Matthias Hein. Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attacks. In International Conference on Machine Learning, 2020b.
10

---

Under review as a conference paper at ICLR 2022
Francesco Croce, Maksym Andriushchenko, Vikash Sehwag. Edoardo Debenedetti, Nicolas Flam- marion, Mung Chiang, Prateek Mittal, and Matthias Hein, Robustbench: standardized adversarial robustness benchmark. arXiv preprint arXiv:2010.09670. 2020.
Guneet S. Dhillon, Kamyar Azizzadenesheli, Jeremy D. Bernstein, Jean Kossaifi, Aran Khanna, Zachary C. Lipton, and Animashree Anandkumar. Stochastic activation pruning for robust adversarial defense. In International Conference Learning Representations, 2018. URL
atttp:://ppenzete httppeerevveew.eeeeeeeeoeeeeeeee wotp://oormmm..
Yinpeng Dong, Fangzhou Liao, Tianyu Pang. Hang Su, Jun Zhu, Xiaolin Hu, and Jianguo Li. Boosting adversarial attacks with momentum. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 9185-9193, 2018.
lan J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. arXiv preprint arXiv:1412.6572, 2014.
Sven Gowal, Krishnamurthy Dj Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Uesato, Relja Arandjelovie, Timothy Mann, and Pushmeet Kohli. Scalable verified training for provably robust image classification. In Proceedings of the IEEE International Conference Computer Vision, pp. 4842-4851, 2019.
Sven Gowal, Chongli Qin, Jonathan Uesato, Timothy Mann, and Pushmeet Kohli. Uncovering the limits of adversarial training against norm-bounded adversarial examples. arXiv preprint arXiv:2010.03593, 2020.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Dan Hendrycks and Thomas Dietterich. Benchmarking neural network robustness common corruptions and perturbations. In International Conference on Learning Representations, 2019. URL htt.httss///ppeeeiiiiee
wwt id=
Dan Hendrycks, Kimin Lee, and Mantas Mazeika. Using pre-training can improve model robustness
and uncertainty. In International Conference on Machine Learning, pp. 2712-2721, 2019.
Wassily Hoeffding. Probability inequalities for sums of bounded random variables. In The collected works Wassily Hoeffdding, pp. 409-426. Springer, 1994.
Roger A Horn and Charles R Johnson. Matrix analysis. Cambridge university press, 2012.
Lang Huang, Chao Zhang, and Hongyang Zhang. Self-adaptive training: beyond empirical risk minimization. Advances in Neural Information Processing Systems, 33, 2020.
Andrew Ilyas, Shibani Santurkar, Dimitris Tsipras, Logan Engstrom, Brandon Tran, and Aleksander Madry. Adversarial examples are not bugs, they are features. In Advances in Neural Information Processing Systems, pp. 125-136, 2019.
Ziwei Ji and Matus Telgarsky. The implicit bias of gradient descent on nonseparable data. In Conference on Learning Theory, pp. 1772-1798. PMLR, 2019.
Matt Jordan and Alexandros G Dimakis. Exactly computing the local lipschitz constant of relu networks. arXiv preprint arXiv:2003.01219 2020.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Nupur Kumari, Mayank Singh, Abhishek Sinha, Harshitha Machiraju, Balaji Krishnamurthy, and Vineeth N Balasubramanian. Harnessing the vulnerability of latent layers in adversarially trained models. In Proceedings of the evvent--Eightt International Joint Conference on Artificial In- telligence, IJCAI-19, pp. 2779-2785. International Joint Conferences Artificial Intelligence Organization, 7 2019. doi: 10.24963/jccai.2111 2019/385.
URL https: /oi. org/10...1000 24963/
ficai. 2019/385
11

---

Under review as a conference paper at ICLR 2022
Alexey Kurakin, Ian Goodfellow, and Samy Bengio. Adversarial examples in the physical world. arXiv preprint 0.003,2,33, 2016.
Chen Liu, Mathieu Salzmann, Tao Lin, Ryota Tomioka, and Sabine Süsstrunk. On the loss landscape of adversarial training: Identifying challenges and how to overcome them. Advances in Neural Information Processing Systems, 33, 2020.
Xingjun Ma, Bo Li, Yisen Wang, Sarah M. Erfani, Sudanthi Wijewickrema, Grant Schoenebeck, Michael E. Houle, Dawn Song, and James Bailey. Characterizing adversarial subspaces using local intrinsic dimensionality. In International Conference on Learning Representations, 2018. URL
https::/oppereviiee www.:/eett.ouuummemee /
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. To- wards deep learning models resistant to adversarial attacks. In International Conference on Learn- ing Representations, 2018. /
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y Ng. Reading digits in natural images with unsupervised feature learning. 2011.
Tianyu Pang, Kun Xu, Chao Du, Ning Chen, and Jun Zhu. Improving adversarial robustness via promoting ensemble diversity. In International Conference on Machine Learning, pp. 4970-4979, 2019.
Tianyu Pang, Kun Xu, Yinpeng Dong, Chao Du, Ning Chen, and Jun Zhu. Rethinking softmax cross- entropy loss for adversarial robustness. In International Conference on Learning Representations 2020.
net forum By
Aditi Raghunathan, Jacob Steinhardt, and Perey Liang. Certified defenses against adversarial examples. arXiv preprint arXiv:1801.090 009444, 2018.
Leslie Rice, Eric Wong, and Zico Kolter. Overfitting in adversarially robust deep learning. In International Conference on Machine Learning, pp. 6093-8104 PMLR, 2020.
Wenjie Ruan, Xiaowei Huang, and Marta Kwiatkowska. Reachability analysis of deep neural networks with provable guarantees. In IJCAI, pp. 2651-2659, 2018. URL httpt::t/////...... /ooi: org/
10. 70.2449371 2C18/3333..
Hadi Salman, Greg Yang, Jerry Li, Pengchuan Zhang, Huan Zhang, Ilya Razenshteyn, and Sebastien Bubeck. Provably robust deep learning via adversarially trained smoothed classifiers. arXiv preprint arXiv:1906.04588 2019.
Pouya Samangouei, Maya Kabkab, and Rama Chellappa. Defense-GAN: Protecting classifiers against adversarial attacks using generative models. In International Conference Learning Representations, 2018 URL htt.::ttts///e https/////ppeeevveeeeee net/ forum fttee//oormmmmdBBJ333332 2id=Bk33ibbbbbb
Kevin Scaman and Aladin Virmaux. Lipschitz regularity of deep neural networks: analysis and efficient estimation. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pp. 3839-3848, 2018
Ali Shafahi, Mahyar Najibi, Amin Ghiasi, Zheng Xu, John Dickerson, Christoph Studer, Larry S Davis, Gavin Taylor, and Tom Goldstein. Adversarial training for free! arXiv preprint /904. 2019.
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The implicit bias of gradient descent on separable data. The Journal of Machine Learning Research, 19(1): 2822-2878, 2018.
Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In International Conference on Learning Representations, 2014. htRh:tp::// wawvvv.ivvvv. org/ /abs/111...m 6199
Antonio Torralba, Rob Fergus, and William T Freeman. 80 million tiny images: A large data set for nonparametric object and scene recognition. IEEE transactions on pattern analysis and machine intelligence, 30(1 1978- 2008
12

---

Under review as a conference paper at ICLR 2022
Florian Tramer, Nicholas Carlini, Wieland Brendel, and Aleksander Madry. On adaptive attacks to adversarial example defenses. Advances in Neural Information Processing Systems, 33, 2020.
Ramon Van Handel. Probability in high dimension. Technical report, PRINCETON UNIV NJ, 2014.
Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018.
Ke Wang and Christos Thrampoulidis. Benign overfitting in binary classification of gaussian mixtures. arXiv preprint arX1v:2011.09148, 2020.
Yisen Wang, Difan Zou, Jinfeng Yi, James Bailey, Xingjun Ma. and Quanquan Gu. Improving adver- sarial robustness requires revisiting misclassified examples. In International Conference on Learn- ing Representations, 2020. URL
net/ forum wwerrummmd=rrr.. 10gg6
Lily Weng, Huan Zhang, Hongge Chen, Zhao Song, Cho-Jui Hsieh, Luca Daniel, Duane Boning, and Inderjit Dhillon. Towards fast computation of certified robustness for relu networks. In International Conference on Machine Learning, pp. 5276-5285, PMLR, 2018a.
Tsui-W Tsu Weng, Huan Zhang, Pin-Yu Chen, Jinfeng Yi, Dong Su, Yupeng Gao, Cho-Jui Hsieh, and Luca Daniel. Evaluating the robustness of neural networks: An extreme value theory approach. In International Conference on Learning Representations, 2018b. URL/attss://ppeeeeeeaa
Deet/Eorrun:1dd33HH111
Eric Wong and Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In International Conference on Machine Learning, pp. 5286-5295. PMLR, 2018.
Eric Wong, Leslie Rice, and Zico Kolter. Fast is better than free: Revisiting adversarial training. In International Conference on Learning Representations, 2020, URL URRpstttp/////eeereviie net/ fowum:iddSDx00EEE
Dongxian Wu, Shu-Tao Xia, and Yisen Wang. Adversarial weight perturbation helps robust general- ization. Advances in Neural Information Processing Systems, 33, 2020.
Chang Xiao, Peilin Zhong, and Changxi Zheng. Enhancing adversarial defense by k-winners-take-all In International Conference on Learning Representations, 2020. URL htttps:/
met/forune id=Skgvy64tvs
Cihang Xie and Alan Yuille. Intriguing properties of adversarial training at scale. In International Conference Learning Representations, 2020. httppppp///ppeeeeeee.eeeeeeeeeee 1d Ed-HyxJhCEFDS
Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. arXiv preprint arXiv: 2016.
Dinghuai Zhang, Tianyuan Zhang, Yiping Lu, Zhanxing Zhu, and Bin Dong. You only propagate once: Accelerating adversarial training via maximal principle. In Advances in Neural Information Processing Systems, pp. 227-238, 2019a.
Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric Xing, Laurent El Ghaoui, and Michael Jordan. Theoretically principled trade-off between robustness and accuracy. In International Conference on Machine Learning, pp. 7472-7482, 2019b.
Jingfeng Zhang, Jianing Zhu, Gang Niu, Bo Han, Masashi Sugiyama, and Mohan Kankanhalli. Geometry-aware instance-reweighheed adversarial training. In International Conference Learning Representations, 2021. URL httpt:tt////ot http::::////eeeeieer/e/ .tt.:lewwweeeeeeeeeee. htte://oooumm11-1A1111162222
Haizhong Zheng, Ziqi Zhang, Juncheng Gu, Honglak Lee, and Atul Prakash. Efficient adversarial training with transferable adversarial examples. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 1181-1190, 2020.
13

---

Under review as a conference paper at ICLR 2022
A NOTATION
b
Section 5.2
The number of parameters a general nonlinear model. The coefficient in isoperimetry.
Assumption Section 5.2
Section
The mean squared error on the adversarial training set. The function introduced by the proposed difficulty metric. The data set.
d
Equation
Section 3
D
Section
Section
The model parameterized by w.
F
Theorem
Section 5.2
The function space of the model.
Section
Groups of the training divided by instance difficulty. The bandwidth of the model's output range.
h
Definition
Section 5
Theorem
Section 5.2
The Lipschitz constant of fw w.r.t w.
K
Section
The number of components in the data distribution.
1
Section
The component index where training data is sampled.
L
Assumptron
Section 5.2
The Lipschitz constant of fa w.r.t the input.
Section
The loss function.
Section
Dimension of the input data.
n
Section
The number of training instances.
o'
Section
Model's output of the clean and the adversarial input.
P
Section
Shape of the adversarial budget.
Equation
Section 5.1
The coefficient in the GMM model.
R
Theorem
Section 5.1
The robust test error.
t
Section 6.
The adaptive target and the moving average target. Model parameters.
ur
Section
W
Theorem
Section 5.2
The diameter upper bound of the parameter space.
W
Theorem Section
The space model parameters.
x'. X
Section & Section
Clean input, adversarial input and its matrix form.
y. y
Section Section
Label and its vector form.
Algorithm
The step size of the adversarial attacks.
Section 6.
The coefficient controlling how adaptive the target is.
Theorem
Section 5.2
The non-negative variable introduced in Theorem
8
Theorem
Section 5.2
The probability introduced in Theorem
e
Section
The size of the adversarial budget.
Equation
Section 5.1
The direction of the mean of each GMM's component.
p
Section 6.
The momentum calculating the moving average target.
Assumption Assumption
Section 5.2
Data distribution and its I-th component.
Section
The conditional variance of the data distribution.
Table 3: The notation in this paper. We provide the section of their definition or first appearance.
B PROOFS IN THEORETICAL ANALYSIS
B. PROOF THEOREM
Similar to (Soudry al. 2018), assume all instances positive without the loss of generality, this is because we can always redefine y;u; as the input, In this regard, the loss to optimize in logistic regression model under the adversarial budget S(2) is:
(X) Σ 1(wTax x, - e||w|])
Ite We use X E guxm to represent the training set as said in Section then the loss function L(w) is |mmothh where |||| is the maximal singular
Here ((-) is the logistic function: ((x)
value of X. Since function L., convex on w, so gradient descent step size smaller than 2 ||
will asymptotically converge the global infimum of the function L.
14

---

Under review as a conference paper at ICLR 2022
Before proving Theorem 1
first introduce the following lemma:
Lemma 1. Consider the max-margin vector i of the vanilla case defined in Equation we then introduce the max margin vector w defined under the adversarial attack of budget S12) (c) as follows:
W = arg min ||a 8.t. ViE (1,2,...,1 n), w x;
c||20|| 21
Then we have w is collinear with w. ie..
w
1|w'
Proof. We show that 1+]||irl
w and prove it by contraction.
Let's assume Ee, s.t. ||||||
1 and E 21, n), v x, 2 1, then we can consider
I+ will
o' (1 w'l) De. The la norm of ef is smaller than that of w', and we have
vi E (1,2, n), N a; - =<|lo11 = (1 + e|]"""|))"" x, - <||o'|| > (1 + +c|l00)))
<|
(10)
Inequality 10 shows can construct vector v' whose l2 norm is smaller than w and satisfying the
condition 9.. this contracts with the optimality of w'. Therefore, there is solution of condition (2
whose norm is smaller than w
[+c||""1
On the other hand,
w satisfies the condition (2) and its lg norm is | [+e||/00|
As result, we
|
have v
w/ That means t and w/ collinear.
1+e|lü0)
With Lemmal) [ Theorem is more straightforward, whose proof shown below. Regarding the convergence analysis of the logistic regression model in non-adversarial cases, we encourage the readers to find more details (Ji Telgarsky 2019: Soudry et al. 2018).
Proof. Theorem in (Ji & Telgarsky 2019) and Theorem 3 in (Soudry et al. 2018 proves the convergence of the direction of the logistic regression parameters different cases. In this regard, we can let wx = lim (w) That is to say, for sufficiently large u, the direction of the parameter ww)) can be considered fixed. As result, the adversarial perturbations of each data instance æ; is fixed, i.., <.
w(u)
We can then apply the conclusion of Theorem 3 in (Soudry et al. 2018) here, the only difference
the data points are {x; cw 1 Therefore, the parameter w(u) will converge to the la
max margin of the dataset (æ; o0 When - oc, we have w(u)² (ar. ew0x)
wu))" xt <l]w(w)]] This is exactly the adversarial max margin condition 9 Based on
Lemma we have lim w(u) wn
[w("]]
B.2 PROOF OF THEOREM 2
Given the parameter of the logistic regression model, we can first calculate the robust emror for the k-th component of the GMM model defined in (3).
Lemma 2. The 0-1 classification error of linear classifier w under the adversarial attack of the budget (2) (c) for the k-th component of the GMM model defined in 33) is:
Tkw 1
Rx(e)
c)
(11)
w
where ((x) = PP() 2), ~~
15

---

Under review as a conference paper at ICLR 2022
Proof. For random drawn data instance (xr y), the adversarial perturbation is -ye [ decompose æ as rwyn + 2, where 2 (0, I). Then, we have
Let's
(e(+) = P(yw" (x - ye ||
< 0) = Pyyw" (ramm + 2 y/ ||
< 0)
(12)
= IP -yww 2 > rw e||w|])
Since (0, I). we have -yw" " = N(, w" w).. Furthermore
yw (O, 1), and we can further simplify Rx((c) as follows:
[0]
-ww
r&w""
/.ww c)
(c(() PC( PP
-e)
(13)
|0
||m||
[
With Lemma 2 we can straightforwardly calculate the robust error for all components of the GMM model defined in 33:
R(() Σ Pk Φ uu |
c)
(14)
On the other hand, Theorem indicates the parameter will converge the 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-parameterizzaton 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 1-th mode of the described distribution in (3) and each of them is a m-dimensional vector. If n nlog a
is sufficiently large") 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(H))
arg min ||w|| s.t. Vi E {1.2, .... n). .............. y w² x;
(15)
Since the min-norm interpolation has a closed solution v X X"X y, Lemma will greatly facilitate the calculation of R(w) in Theorem To simplify the notation, we first define the following variables.
U- QQ" d = Qn. s = y = dU-'d, == --U
(16)
The proof of Theorem P is then presented below.
Proof. Based (4), the key is to simplify the term
w n w
let's denote by A, then have:
2 n7" www"
(XXT) Xn)²
(17)
w w
(XX")-I
The key challenge here is to calculate the term (XXT)-1 where X = ==rnnn +Q. Here we utilize
Lemma 3 of (Wang & Thrampoulidis 2020) and Woodbury identity (Hom & Johnson 2012). have:
(r] + r7uu + riv rt + ridd
-
U-1
(18)
rf t) (rio + 1)2
SSpecifically, m and n need to satisfy m > 10m log + and m Curiy 2n||mn/|. The constant C' is derived in the proof of Theorem in (Wang & T'rrampoliddi 2020
16

---

Under review as a conference paper at ICLR 2022
Here, t, 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 y² (XX") y and y (XX") Xny.
y" ('Xxx) y (1/5|1n) + rsuu + riv rf)()8 1780
rf 1) + (riv 1)2
(19)
r 1) + (r1o 1)2
y" (XX")
Xm v ) (mynn (mynn" + Q)
= -rilmll3y (XX*) ) + y" y" (xx")-
(20)
r|s[||||| mu=? +
( + (riv + +12
Plug Equation 19 and 20 into 17 we have:
(nis([]nl1 - t) + riu + u)²
A2
8 (r77(111)) t) + (riu 1)2)
s([1>]) - -) + u²
||
(21)
7 - 1) + (riv 1)2
[17]] u?
a< e((nm 1||
rी + |n
2v
Plug 21 into 14 we then obtain the robust on all components of the GMM defined in
R(ri,)) = Σ & (ruo(ri) - c), ((r))
[C1
Cari 0ss )
1
h=1
(22)
C1 <( <([n]|2 t) + 22
C2 s(|nn]2 + +
2u
||m|| - Cs
||0 1
||,|||
We study the sign of C and Cz. Consider U = QQ is positive semidefinite matrix, so s -リー 2 In addition, we have ||>||² = n [I - (QQ n. Since (QQ²) )
(I- (QQ")-1>7 (QQ7)-1) is a positive semidefinite matrix, we can obtain (QQ") is
also positive semidefinite matrix. As result, C1 and C2 are both non-negative.
B.3 PROOF OF COROLLARY
To prove Corollary D first prove the following lemma:
Lemma Under the condition of Theorem and R in Equation (4) monotonically decreases with
aR(r)e) is negative and dn
Proof. Based on Equation
22
we have:
OR(T,E)
K Σ
dg(ri)
Pa 0'(g((()))
(23)
dr:
dr:
k=1
Since the training data is separable, we have Vk, Ph w - c|| > 0, which is equivalent to the following:
vk,Tig(T)) -
(24)
17

---

Under review as a conference paper at ICLR 2022
First, Pk is positive number by definition. Consider function ((x) monotonically decrease with I and is convex when 2 > 0, so vk, (T() <) is negative and decreases with c. In addition,
g(ri) increases with and is independent on so dr: Therefore, @R(m.) is negative and monotonically decreases with e. dr
dg(rc) can be considered positive constant.
Now, we are ready prove Corollary
Proof.
We subtract the left hand side from the right hand side in the inequality of Corollary |
@R(r),))
Ōri dr. - Sr 1 OR(rI
(R(r) R(r,, (a) (R(r,, R(ri, c2)
dr Or
TOR(rie1) OR(Fi, dri
dr
dr
(25)
(R(()11)
aR (r)22
The last incquality is based on > Tú, 62 > E1, Lemma which indicates
dri
Gr:
always positive. We reorganize (25) and obtain R(r,, E1 R(ry. e1) < R(r,, R((r,
B.4 PROOF OF THEOREM 3
We start with the following lemma.
Lemma 5. Given the assumptions of Theorem 3 define g(x) = B(ylæ)), z(x) g(x)) and
consider 7 = of + (C,() C. then the following inequality holds.
Va (0, (0,1), F
Σ
wu soo C)
n
(26)
na2 < 2e
1 Σ
2 1 5 -1-130)) -3a)m)
8 + P(3f E
F
Iw
(1;
Proof. Given the definition of h(C, c), we have:
(yi - Sun (xx = [(ys - fmo ) + (fmo(x)) - mw (mx())
2 (ji fw )) + (fw( - fww (z)))
(27)
(y fao (m:))) (C,
For the first incquality, of is the adversarial example which tries to maximize the loss objective, Yi ([1,++1, +13 and the range of fwo is +-1, (yi ( (x; fww((() 0. The
second inequality is based on the definition of (C, in Definition [
As result, we can simplify
the left hand side of (26) as follows:
P(3f
F;
1 n 1=1
Σ vy ()) S E F; >0w (ti c
(28)
18

---

Under review as a conference paper at ICLR 2022
We consider the sequence {=(x;)); (- it ii.d with Eyg (z(xx)) En [ar(y] of. Since the
range of the prediction is 11,+1] so =²x)) E [0,4]. Then, we have the following inequality by
Hoeffding's s inequality (Hoeffding 1994).
Ya (0, P( -
Σ (x,) S of -a7) ee- 2,2
(29)
Similarly, we consider the sequence (z(2; 1 the following inequality holds based on the Hoeffding's 's inequality and the fact (2(2(())(()))))))) (x))((x) 1-2,+22
Va (0,
Σ
<<;))(<>;) S <ay) S e س
(30)
2=1
Now we study the right hand side of 28
Jw (xx)))
(x, + (g(2x) (wx)) 2z(xx))(((r.)) - (ao();)))
==1
(31)
(z))))) + +22(2:)((x.) - 2z0
Consider the following reasoning:
U: =c= -7
1
(ax) 2 of 07
Σ
2 (ww))f((x;) 2 2 (1 (1-3a)y
71
71
2 (()))(())))) 2 -ay
(32)
As result, have:
P(3fw E F 1
Σ (v: (xi) [C-
iml
<P(3f E F
(xx) S ay) + P(3fm E F: 1
Σ
2 x (xx,)) 2
-ay)+
n
i=1
(33)
1 F P(3
Σ
n
foo 2 (1 3a)))
n
na2,2 3 + P(3fu
1 ((x))f
<2c
E F
2 3a)))
The first inequality is based the reasoning of
32
The second inequality is based on
29 and 30)
Based on the inequality (28 and
33
we conclude the proof.
19

---

Under review as a conference paper at ICLR 2022
To further simplify the right hand side of (26 P
=F 2(zx) 2 2(1 - -3))))
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(æ), z(x) in Lemma 5 then the following inequality holds.
Va E (0,1), a1 > 0,a2 > O and 01 + + 2 - (1-3),,
(34)
P E F 1 Σ zi 2
1 (1-3a))) S 2| of + 2e 0027
Proof. We recall that the data points {æ,, yi 12=1 are sampled from the distribution 14,, which is c-isoperimetric. For any L-Lipschitz function f. we have:
1l. P (o)) - E (Sw)) 2 1) 2e
(35)
Since =(x) = y - g(x) E 2-2 we can then bound (fw E (fw)) 2 t]:
Vt, (f (z>) E, (fw))
P((=(()) Bape (fw)) )1 2 t)
me?
(36)
S {P(([m(<x)) - Epc (fw))) 2
< 2e
acl
2
Here we utilize the proposition in (Vershynin 2018 are independent variables and all C-subgaussian, then vn Ei=1 X, is 18C 18C-ssbgaussian Therefore,
Van Handel
2014 5 which claims if (X:)
we have:
Vt, Pl Vn
1
Σ
(f En (fw)) 2 E 2 14
m
(37)
Let f = /17/T1 then we have:
145e22 o7??
(fmn())) Enr 2 ai7) < 2e
(38)
In addition, we can bound P[ Ei 2(x; (fw) 2 a27/
PB E F; 2(2;) (fw) 2 a27l S P 1 Σ xxxx)| 2 a22l S 2e 2eeee=#00 -ga2>
(39)
The first inequality is based the fact E, (fwo E [-1, (-1,+1] +1}; the second inequality is based Hoeffding's 's inequality.
Now, we ready bound the probability P(3fmo E F: ) =w ] -3a)7)
1 1/ - (1-3))
P(3 FF:
z (xx; ). (2x
n
1
1 Σ (ax (fwr 2 a27)
F <P n0
Σ
2 (ffm (y)) 2 an7) + P/. F
n
52
143612
777 + 2e 3
(40)
The first inequality is based the fact 0; 02 = 1 (11); the second inequality is based on the Boole's inequality (Boole 1847), inequality (38) and (39).
3a);
Proposition 2.6.1 in Vershynin 2018 and Exercise 3.1 in Van Handel 2014
20

---

Under review as a conference paper at ICLR 2022
To simplify the constant notation, we let 3. 01 26 and (34. then:
3 and 02 8.
We plug this into the inequality
1 P E
Σ yi i=1
SC) S 4e # +
umrz 27
(41)
Now turn to the proof of Theorem
Proof. We let Fr. = [sule E W, Lip(fw) < = E W.w 3 0z,2 Ed and
Fr.1. F. Fr. Correspondingly, let Wr. {w kw/w W, Lip(Sw) L), W, {w wow
W, 47 ② 2, ) and Wy, Wy n WL- Because the diameter of W is W, have
| |F,1
Here, means the element-wise multiplication.
Note that the inequality (41
is valid for any values of C' as long as it satisfies y 2 0. Based on this,
1
C C
27
we apply the substitution
.then:
1 7
2"
n
FB3 E F
Σ
sC+
2)) $ 4e /7 + 2
214.13
umy?
71
(42)
=r + 2c log 2
mmn
S 4e
219027
Based on the definition of Wn,L. we can conclude that Van E Wz, Ewo E Wy. s.t. - -22l20 S 5. Therefore, Vfn FL, Ff FF,.s.t.llfuu swzl oc S 7. Let choose such fwo Fy.l
given an arbitrary fws E FL. then:
(y - fw, (x)) = (y - fw. (x)) + (2y - fw; (x) fw. (x)) (x) -ww((x) (x))
2 (y - fwz (x)) 2 (2y - fw, - fwz (x)))
(43)
( - swz (x))
The first inequality in 43 is based on Hölder's inequality; the second inequality is based on y E +1] and the range of Vfw E Fis [-1++11
We combine
41 with 43 then:
5 CC P(ff E F 1 Σ U1 fu 2C SC+ 5))
P(3 E Fr
(y fm (x))))
n
am 1=1
2222 4e
2 2c
log(
1W2)
(44)
Note that FL the of functions in F whose Lipschitz constant no larger than L. We set the right hand side of (44) be and then get 3 concludes the proof.
This
V c(blog(4W Jy /0gg 20 26-2- -1--2y
21

---

Under review as a conference paper at ICLR 2022
C EXPERIMENTAL SETTINGS
C.I GENERAL SETTINGS
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 al. 2018). Unless specified, the Loo adversarial budget used for CIFAR1O 10 dataset (Krizhevsky et al. 2009 is 8/ 6/255 and for SVHN dataset (Netzer et al. 2011) is 0.02. In PGD adversarial training, the step size is 2/255 for CIFARIO 10 and 0.005 for SV HVH;; PGD is run for 10 iterations for both datasets. For adversarial attacks using a different adversarial budget, the step size is always / of the adversarial budget's size, and always run it for 10 iterations. To comprchensively 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 divided by 10 in the 1/2 and 3/ /44 of the whole training duration. The size of the mini-batch is always 128.
We run the experiments 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.
C.2 SETTINGS OF EXPERIMENTS IN SECTION 6
Algorithm 1: One epoch of the accelerated adversarial training we in Section 6.1
Input: training data D, model f, batch size B, PGD step size a, adversarial budget ((P((e), coefficient p. B.
for Sample a mini-batch (az, y: |
'D do Vi, obtain the initial perturbation A as in Zheng et al. 2020).
Vi, one step PGD update: A; < (t A, + asign VA, Lg (z, + A, 11).
Vi, update the cached adversarial perturbation A, in Zheng et 2020
if use reweight then
Vi, weight w; = [ofttax[[[[ + A.))
else
Vi, weight wt;-
end if
Vi, query the adaptive target E, and update: i, t- ptq + (1 p)softmaals(a + A.)].
Vi, the final adaptive target L; = 31,, + (1 111-3)4 B)1
Calculate the loss
D. w. Σ w; Lo - D,, tt) and update the parameters.
end for
Fast Adversarial Training Our experiment on fast adversarial training is on CIFARIO and e 8/255. The pscudocode of our method is demonstrated Algorithm [ We use ATTA (Zheng et al. 2020) to initialize the perturbation of each training instance. The step size a of the perturbation update is 4/255, same as (Zheng al. 2020 The average coefficient p and B 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, 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 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 10: random crop and random horizontal flip.
Data available for download on https://www.cs.trrrrm. www.::/wwww.ooooooo.ooooo kriz/cifarr.htm MIT license. Free to use. Data available for download http://uukklkssaaooooc.ecueuunnn Free for non-commercial use.
22

---

Under review as a conference paper at ICLR 2022
Adversarial Finetuning with Additional Data For CIFARIO, use 500000 images from 80 Million Tiny Images dataset (Torralba et al. 2008 with pseudo labels in (Carmon et al. 2019 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 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.
D ADDITIONAL EXPERIMENTS AND DISCUSSION
D.1 PROPERTIES OF THE DIFFICULTY METRIC
To study the factors affecting the difficulty function defined in I 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.
Dd1, d2) (D)) (1) d2(x))
(45)
We then study the properties of the difficulty metric of Equation (I) by performing experiments on the CIFARIO and CIFAR 10-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- REN18-100 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 lxc norm with e 8/ /2255. This corresponds 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.
di \d2
RN18-100
RN18-200
WRN34
di
Clean
FGSM
PGD
RN18-100
0.0189
0.0232
0.0355
Clean
0.0189
0.0607
0.1713
RN18-200
0.0232
0.0159
0.0299
FGSM
0.0607
0.0843
0.1677
WRN34
0.0355
0.0299
0.0178
PGD
0.1713
0.1677
0.0857
Table 4: D-distances between difficulty functions in different settings, including different model architectures and training duration (left table), and different types of perturbations (right table).
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 instance. In addition, Table demonstrates the D-distance between the difficulty functions based on clean instances, FGSM- perturbed instance, DGDD-prturbed instances and different common corruptions from CIFARIO- C (Hendrycks & Dietterich 2019 2019 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 demonstrate that our difficulty metric mainly depends on the data and on the perturbation type; not the model architecture or the training duration.
Data available for download on https//ghhub..co//ooooo////maaap MIT license. Free to use. Apache License 2.0. Free to use.
Data available for download on htnps//sithaaccommccccyyyttsssss
23

---

Under review as a conference paper at ICLR 2022
di \d2
brightness
contrast
defocus
elastic
fog
gaussian blur
Clean
0.1279
0.3219
0.2616
0.2115
0.2321
0.3069
FGSM
0.1303
0.3128
0.26412
0.2098
0.2289
0.3064
PGD
0.1873
0.3082
0.2616
0.2319
0.2414
0.2959
di 1/22
glass blur
Jpeg
motion blur
pixelate
gaussian noise impulse noise
Clean
0.2809
0.1838
0.2520
0.2365
0.2999
0.2869
FGSM
0.2760
0.1853
0.2520
0.2417
0.2918
0.2807
PGD
0.2825
0.2026
0.2605
0.2551
0.2980
0.2866
di 1,22
saturate
shot noise
spatter
blur
speckle noise
Clean
0.1335
0.2832
0.2033
0.1930
0.2654
0.2829
FGSM
0.1329
0.2754
0.2003
0.1946
0.2657
0.2759
PGD
0.1932
0.2841
0.2148
0.2297
0.2711
0.2901
Table 5: D-distances between difficulty functions of vanilla FGSM PGD training and training based on 18 different corruptions on CIFAR1O-C. We run each experiment for times and report the
average value.
aificity Meauuee by Avenge 0-1 Enor
0.5
0.6
by
0.4
0.2
0.2
0.0
0.2
Diffcuity by Average
Average
Figure 3: The relationship between the difficulty function based on the average loss values and the one based on the average 0-1 errors. The left figure is based on the RN18-200 model; the right figure is based on the WRN34 model. The correlation between these two metrics are 0.9466 (left) and 0.9545 (right), respectively.
In the definition of our difficulty metric in Equation (T). the difficulty of one instance is based 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 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. relationship between the difficulty metric based on the average loss values and the one based on the average 0-1 error for instances the CIFARIO training set when we train a RN18- 100 model and WRN34 model. We can see strong correlation between them for both models. The correlation of the difficulty measured by two metrics for the same instance 0.9466 in the RN18-100 100 case and either metric to measure the
Figure 3 we plot the
0.9545 in the WRN34 case. The high correlation indicates we difficulty. Since the loss objective values are continuous and finer -rainer we choose it as the basis of the difficulty function
in this paper.
D.2 EXAMPLES OF EASY AND HARD INSTANCES OF CIFARIO AND SVHN
Figure 20 and 21 demonstrate the easiest and the hardest examples of each class from CIFARIO and SVHN. respectively. The difficulty of these instances is caleulated based on PGD attacks. We can see most easy examples are visually consistent, while most hard examples are ambiguous or even incorrectly labeled.
24

---

Under review as a conference paper at ICLR 2022
D.3 TRAINING ON SUBSET
Different Optimization Method on Hard Instances We find the failure of PGD adversarial training on the hardest 10000 instances of CIFARIO training set does not arise from the optimizers. In Figure we use SGD with different initial learning rates ("SGD, Ir=le-2" and "SGD, Ir=le33") and the adaptive optimizer such as Adam (Kingma & Ba 2014) ("Adam, Ir=le-4"). The learning rate of SGD optimizer decrease 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.c., 10%.
Longer Training Duration In Figures] 7 and g we conduct adversarial training for 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 0.1 and divided by 10 after every 100 epochs. In Figure 7 we adversarially train RN18 model on the hardest 10000 training instances. Our conclusions from Section still still hold: Adversarial training on the hard instances leads much more severe overfitting, greatly widening the generalization gap. In Figure 8 we adversarially train RNI8 model on the whole training set and calculate the average loss on the groups Go. G3. G6 and Go. 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 Gy decreases much faster in the beginning and quickly saturates. In other words, the harder the group, the later we see 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 larger than that of CIFARIO. 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 lz-based Adversarial Budget Figure 4 and Figure demonstrate the learning curves of RN18 models under different adversarial budgets on CIFARIÓ, in both 4x0 and l2 cases. 7o 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 the hardest subset.
Training with Different Amount of Data In Figure 10 we compare the learning curves of PGD adversarial training 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 CIFAR 10 and SVHN when they 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.
08-
08 Aapaopamony
0.2
0.2-
02-
Eesy 31h
0.0
175
275 200
Ea6ch
Fpech
Spach
(a) 2/255
(b) 4/255
(c) 6/255
Figure 4: Learning curves of training on PGD-perturbed inputs against different sizes of Lox norm based adversarial budgets using the easiest, the random and the hardest 10000 training instances. The instance difficulty is determined by the corresponding adversarial budget and is thus different under different adversarial budgets. The dashed lines are robust training error on the selected training set, the solid lines are robust test error the entire test set.
25

---

Under review as a conference paper at ICLR 2022
0.9
0.8
Errer Rate
0.6
0.7
Ir=1e2
Easy
SGD 1r=le-3
Random 20k
0.4
0.0
25
50
75
100
125
150
175
200
25
50
1.00
125
150
175
200
Epoch
Epoch
Figure 5: Learning curves of PGD adversari- ally trained models on the hardest 10000 in- stances in the CIFARIO training set by dif- ferent optimizers. The dashed lines are ro- bust training enror on the selected training instances, the solid lines are robust test error the entire test set.
Figure 6: Learning curves obtained by train- ing using the easiest, the random and the hard- est 20000 instances of the SVHN training set, The training error (dashed lines) the robust error on the selected instances, and the robust test error (solid lines) always the error on the entire test set.
1.0
3.0
Easiest top 10%
0.8
Easiest 30%
30%
Error
8
2.0
Hardest top 10%
0.6
0.4
0.4 m
0.5
Hard 10k
100
200
300
400
500
600
100
400
5.0
Epoch
Figure 7: Learning curves of PGD adversar- ial training on the hardest 10000 training in- stances. The model trained for 600 epochs. The training еттоr (dashed lines) is the robust error on the selected instances, and the robust test error (solid lines) is always the error on the entire test set.
Figure 8: The left vertical axis represents the average loss of the training instances in the groups Go- G3- Go and Gg. The right vertical axis represents the robust error for the whole training (dashed grey line) and test (solid grey line) set. The model is trained for 600 epochs.
08
2.3
0.0
62-
Eady 10k
Randon
Hard 10k
25
50
75
300
125
150
175
235
25
50
100
125
150
175
200
25
30
75
130
125
150
175
265
0.50
(b)
0.75
(c) 1.00
Figure 9: Learning curves of training on PGD-perturbed inputs against different size of l2 norm based adversarial budgets using the easiest, the random and the hardest 10000 training instances. The instance difficulty is determined by the corresponding adversarial budget and is thus different under different ad adversarial budgets. The dashed lines are robust training error on the selected training set, the solid lines are robust test error on the entire test set.
26

---

Under review as a conference paper at ICLR 2022
Easy 20k
0.8
Easy 30k
Easy
Error Rate
0.6
Error Rote
0.6
Total
0.4
Easy 10k
0.4
Easy
0.2
Easy 30k
Easy 40K
Total 50k
0.0
0.0
25
50
75
100
125
150
175
200
0
25
50
75
100
125
150
175
200
Epoch
Epoch
Figure 10:
Learning curves of PGD adversarial training using increasing more training data in CIFARIO and SVHN. The dashed lines represent the robust training error the selected training instances; the solid lines represent the robust test error on the entire test set. Left: we use the easiest 10000, 20000, 30000, 40000 and the whole training set of CIFAR1O. Right: the easiest 20000, 30000, 40000 and the whole training set of SVHN.
D.4 LIPSCHITZ ANALYSIS
Lipschitz in loc Cases (x 10*)
Lipschitz 1g Cases (x10*)
Training Set
2/255
<= 4/255
6= 8/255
= 0.50
<= 0.75
6 1.00
Easy I0K
5.91
6.06
14.54
3.34
3.67
2.91
RandomIOK
28.98
79.96
93.63
30.01
31.28
39.34
Hard1OK
72.42
117.60
567.24
60.62
80.06
77.55
Table 6: Upper bound the Lipschitz constant under different settings of and training instances.
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 CIFARIO as the dataset and RN18 as the network architecture.
demontadee the upper bound of the Lipschitz constant of models trained in different settings. In the Too cases, we set to be 2/255, 4/255 and 8/ 8/255; in the la 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 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 II demonstrates the curves of the Lipschitz upper bound when the model adversarially trained by the easiest, the random and the hardest 10000 instances. The adversarial budget is las. 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 analysis in Section 5.2 In addition, compared with training on easy instances, the Lipschitz upper bound of the models udversarially trained on hard instances increases much faster.
D.5 REVISITING EXISTING METHODS MITIGATING ADVERSARIAL. OVERFITTING
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. this section, we pick one example from each category for investigation. We provide the learning curves of the methods we study in Figure 22 We use the same hyper-parameters as in these methods' original paper, except for the training duration and learning rate scheduler, which follow 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.
27

---

Under review as a conference paper at ICLR 2022
Lipcchtz Conzamt
Easy 10k
200
Random 10k
Hard 10k
10
10*
10a
10a
100
150
Epoch
Figure 11: The curves the Lipschitz upper bound when the model is adversarially trained by the easiest, the random and the hardest 10000 instances. The y-axis is log-scale.
PGD AT
0.8
0.7
SAT
0.6
0.5
0.4
0.3
0.2
0.1
0
25
50
75
100
125
150
175
200
Epoch
Learning curves of PGD adversarial training (PGD AT), instance-adaptive training (IAT) and self-adaptive training (SAT), Dashed lines and solid lines represent the robust training error and the robust test error, respectively.
Figure 12:
Instance-Adaptive Training Using an instance- adaptive adversarial budget has been shown miti- gate adversarial overfitting and yield better trade-off between the clean and robust accuracy (Balaji (et al. 2019). In instance-adaptive adversarial training (IAT), each training instance æ; maintains its adversarial budget's size during training. In each epoch, e, increases to e, + EA if the instance is robust under this enlarged adversarial budget. By contrast, E, decreases to E; e. if the instance is not robust under the original adversarial budget. Here, ca 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 the in other experiments for fair comparison. Specially, we set the value of e and c to be 8/255 and 1.9 255, respectively, same as in (Balaji et al. 2019). The first 5 epochs are warmup, when
vanilla adversarial training (Madry al. 2018).
Figure 13 demonstrate the relationship between the instancewise adversarial budget 6 and the corresponding instance's difficulty d(x,). It 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 fixed target, usually the ground-truth. SAT adapts the target of each instance to the model's s output. Specifically, after a warm-up period, the target t, for an instance æ; initialized as one-hot vector by its ground-truth label and updated in an iterative manner after each epoch as
&; + pt; + (1 - -,,, Here, p is predefined momentum factor and o, is the output probability of the current model the corresponding clean instance. SAT uses the loss of TRADES (Zhang et al.) 2019b) but replaces the ground-trutt -trth label y with the adaptive target t,: LSAr(w = C(x;, t,) À AaxAA K [L(o, where K L refers to the Kullback-Leibe for the regularizer. Furthermore, SAT uses a weighted average to calculate the loss of a mini-batchh batch; the weight assigned to each instance æ; is proportional the maximum element of its target t, but
divergence and is the weight
28

---

Under review as a conference paper at ICLR 2022
1.0
0.9
Averege Weegge
0.8
0.7
0.6
Easiest top 10%
0.5
30%- 40%
Hardect 30%.400%
Hardest top 10%
0.25
0.75
80
100
120
140
160
180
200
d(x)
Fporh
Figure 14: Average weights of different groups in the training set of CIFARIO dur- ing training. During the warmup period (first 90 epochs), the weight for every training in- stance is The model architecture RN18.
Figure 13: The instance adaptive adversarial budget size 6j for the training set of CIFAR10 function of the instance difficulty di d(x;)). The model architecture is RN18 and the value of 8/255.
normalized to ensure that all instances' weights up 1. By weighted averaging, the instances with confident predictions are strengthened, whereas the ambiguous instances are downplayed.
the settings in (Huang et al. 2020) except use the number of training epochs and learning rate scheduling: we train the model for 200 epochs and the first 90 epochs are the warmup period.
Similarly,
Figure 14 demonstrates the average weight assigned to instances belonging to the group Go. G3. G6 and Gg- It clear that the hard instances are assigned much lower weights than the easy instances. For example, the weight assigned to Go. the easiest 10% training instances, is close to 1, while the weight assigned to Gg, the hardest 10% training instances, is only around 0.4.
Furthermore, Figure 15 shows the accuracy of the group Go. G3. G6 and Go during training using the original ground- label 1y and the adaptive target respectively. For the adaptive target, one adversarial instance x' is considered to be correctly classified if and only if arg max; fw (æ'), = arg max; t. For easy instances, I is mostly close to f,, so accuracy both cases high and the gap between them is small. For hard instances, 1 is usually not consistent with f, while accuracy under the adaptive target much higher than the group-truth label y. This indicates self-adaptive training makes adaptive target easier to fit for the originally hard instances.
Accuracy
0.6
Accurasy
0.6
0.4
0.4
top Easiest 30%-40%
Hardest 30%-40%
Hardest 10%
100
150
175
200
Epoch
Epoch
Figure 15: Robust training accuracy during training when we use the original groundtruth label (left) use the adaptive target calculated during training (right).
D.6 EXTRA RESULTS AND DISCUSSION ON FAST ADVERSARIAL TRAINING
We also conduct ablation study in the context of fast adversarial training. In Figure 16
we change
the value of 3 in algorithm (pseudocode in Algorithm I and plot the learning curves. Lower the value of is, more weights assigned to the adaptive part of the target: B means we directly utilize the moving average target as the final target, 3 means
the one-hot groundtruth
29

---

Under review as a conference paper at ICLR 2022
ATTA RM
07
32-
6. 0.5-
0:03
34-
Figure 16: The learning curves with different values of 3. The solid curve and the dashed curve represent the robust test error and the robust training error, respectively.
Figure 17: The learning curves of ATTA with and without reweighting, The solid curve and the dashed curve represent the robust test error and the robust training error, respectively.
1..
19.
Patrage Connet 1054
0.-
3.0
0.2
0.4
0.5
0.5
1.0
0.2
022
0.4
0.6
0.8
3.5
Dificatyy Level
Dificuty
Figure 18: The relationship between the dif- ficulty value and the weight assigned each instances when using reweighting. We use the average weight across epochs. The corre- lation between them is 0.8900.
Figure 19: The relationship between the dif- ficulty value and the average value of the true label's probability when using the adap- tive targets. The correlation between them 0.9604.
label. Figure clearly shows the generalization gap decreases with the decrease in 3. 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 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 [ 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 based on the PGD attack, the difficulty value here is based on the PGD perturbation. In Figure [8] 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 [9 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-trutt 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.
30

---

Under review as a conference paper at ICLR 2022
D.7 EXTRA RESULTS AND DISCUSSION ON ADVERSARIAL FINETUNING
We conduct ablation study and the results are demonstrated in T It is clear that both reweighting and the KL regularization term benefit the performance of the finetuned model.
Duration Method
AutoAttack: Duration Method
AutoAttack
WRN34 on CIFARIO, c = 8/255
RN18 on SVHN,
0.02
No Fine Tuning
52.01
Fine Tuning
67.77
Vanilla AT
54.11
Vanilla AT
70.88
RW
54.69
RW
70.83
Epoch
Epoch
KL
54.73
KL
72.29
RW + KKL
54.69
RW + KL
72.53
Vanilla AT
55.49
Vanilla AT
772.88
RW
56.41
RW
72.72
Epoch
5 Epoch
KL
56.55
73.17
RW KL
56.99
RW + KL
73.35
Table 7: Ablation study on the influence of reweighting (RW) and the KL regularization term (KL) in the performance of adversarial finetuning with additional data.
31

---

Under review as a conference paper at ICLR 2022
Plane, Easy.
(b) Plane, Hard.
(c) Car, Easy.
Car, Hard.
(c) Bird, Easy.
Bird, Hard.
(g) Cat, Easy.
(h) Cat, Hard.
(i) Deer, Easy.
Deer, Hard.
(k) Dog, Easy.
(1) Dog, Hard.
(m) Frog, Easy.
(n) Frog, Hard,
(o) Horse, Easy.
(p) Horse, Hard.
(q) Ship, Easy.
(r) Ship, Hard.
(s) Truck, Easy. (1) Truck, Hard.
Figure 20: Easy and hard examples in each category of CIFARIO dataset. In each subfigure, odd columns present the original images, and even columns present the PGD-perturbed images. Above each image, we provide the normalized difficulty defined in Equation (I) as well as the labels: true labels for the original images and the predicted labels for the perturbed images.
32

---

Under review as a conference paper at ICLR 2022
00
0
8
0
10
10
10
00
:0
10
0
10
10
80
80
80
150
(a) O, Easy
(b) Hard
Easy
(d) 1, Hard
2
3
3
3
6
9
2
2
2
2
2
3
3
3
3
3
3
2
2
2
2.
2
3
3
2
2
2
A
3:
3:
31
31
2
2
2
331
3
3
3
2
2
2
23
3
3
3
(c) 2, Easy
(f) 2, Hard
(g) 3, Easy
(h) 3, Hard
25
5
5
5
5
4
4
4
4
4
15
5
0
0
4
4
41
4
151
5
25
4
4
4
24
5
5
5
5
4
4
15
15
5
5
4
52
52
5
5
5
5
(i) 4, Easy
(i) 4. Hard
(k) 5, Easy
(I) Hard
16
16
6
6
66
6
6
6
6
7
6
6
16
161
761
37
ZZ
57
6
66
16
6
6
3
7
77
7
7
6
39
(m) 6, Easy
(n) 6. Hard
(o) 7, Easy
(p) 7, Hard
88
88
18
8
8
9
81
88
18
18
18C
180
9
99
99
99
9
9
180
184
8
8
69
39
9
9
9
8
8
8
99
9
9
39
18
8
8
8
8
9
9
9
9
9
8
&
88
1
8
19
19
(9) 8. Easy
(r) 8, Hard
(s) 9. Easy
(1) 9, Hard
Figure 21: Easy and hard examples in each category of SVHN dataset. In each subfigure, odd columns present the original images, and even columns present the PGD-perturbed images. Above each image, we provide the normalized difficulty defined in Equation (I) as well as the labels: true labels for the original images and the predicted labels for the perturbed images.
33


Reviews:
[{"review_id": "k1qs4I7z_xk", "reviewer": "Reviewer_oU1N", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n\nThe authors first gave experiments and theoretical analysis to illustrate the relationship between hard samples and robust over-fitting, which is an interesting observation. Then, the proposed algorithm is reasonable and makes sense.\n\nWeaknesses:\n\n1. My primary concern is about the novelty. The difficulty level of samples has been considered in the adversarial training, especially the strategy that considers the weight of examples (like MART and SAT). I understand that the author constructs a new adversarial training by observing the relationship between hard samples and robust over-fitting. However, the proposed algorithm is very similar to self-adaptive training (SAT). Even in the experiments, the author did not compare and analyze the SAT algorithm. \n\n2. It is not clear how to distinguish hard adversarial samples. The authors first said they provide a model-agnostic metric, which can measure the difﬁculty of an instance. But, it is hard to understand how to use this metric to guide adversarial training. In my opinion, section 6 does not seem to have much to do with the previous observation. \n\n3. I carefully compare and analyze the difference between the algorithm in this paper and SAT, and I think it is mainly on the final adaptive target. So, if we also add this line to SAT, what will be the result? ", "summary_of_the_paper": "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.  ", "summary_of_the_review": "Through experiments and theoretical analysis, this paper concludes that hard adversarial samples will lead to overfitting. However, the introduced algorithm is not novel enough, which is very similar to the existing self-adaptive training. Even in the experiments, the corresponding experiments are also missing. Based on these, I recommend ''marginally below the acceptance threshold''.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "XziKWWoMBE1", "reviewer": "Reviewer_crXx", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n\n1.\tThis paper shows that hard adversarial instances lead to degraded generalization performance in adversarial training based on the measurement of instance difficulty. \n\n2.\tThis paper provides extensive theoretical analysis that shows fitting hard adversarial data hurts adversarial robustness.\n\nQuestions:\n\n1.\tI am concerned about the meaning of 'model-agnostic' which is one of the property of the metric for instance difficulty.  The calculation of loss for each instance depends on the parameters and the optimization for each model. Therefore, how can you ensure for each model and each setting of training, the difficulty of a particular instance keep the same? \n\n2.\tIn Sec.4.2, this paper claims that adversarial overfitting arises from the model’s attempt to fit the hard adversarial instances. However, it is confusing that the easy instance (yellow lines in the right panel of Figure 2) has the similar behavior with the hard instance (red lines in the right panel of Figure 2) and the model fits the easy instances (yellow lines in the left panel of Figure 2) and hard instances (red lines in the left panel of Figure 2) almost simultaneously. Therefore, it seems that adversarial overfitting happens when the model’s attempt to fit the easy and hard adversarial instances.\n\n3.\tTheorem 2 and Theorem 3 both indicate that with the increase of instance difficulty, the adversarial robustness becomes lower. However, it is not clear how can those theorems show the relationship between robust overfitting and instance difficulty.\n\n4.\tAlthough the effectiveness of two tricks proposed in Sec.6 are empirically validated, the motivation for these two tricks is not clear. The reweight strategy gives lower weight for the instance whose predicted probability is lower. However, it is hard to say the instance whose predicted probability is low is the hard instance measured by the proposed metric. Therefore, the proposed method seems to be hardly related to the metric.\n", "summary_of_the_paper": "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.", "summary_of_the_review": "Overall, this paper investigates the impact of hard instance on adversarial training. However, I am not convinced of the novelty and the correctness of the proposed method.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Ef7ZBwzEoe", "reviewer": "Reviewer_dYnb", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength:\n+ The topic studied in this paper is interesting and important. It can help practitioners better understand how training data influences the overfitting of adversarial training.\n+ This paper provides a theoretical explanation for why hard examples hurt the generalization gap.\n+ The evaluation results empirically show that adaptive training examples can improve robustness.\n\nWeakness:\n- The paper is a little bit overclaimed in the abstract. By definition, the difficulties of training examples are defined with losses of corresponding models, which means that it is not model agnostic. Same training samples could have different difficulties for different models. The method to calculate the metric is model agnostic, but the metric is not model agnostic.\n\n- In Section 3, the authors define the difficulty metric for training samples. One of my recommendations is to explain more about how and why the metric is defined.\n\n- Figures 1(a) and 2(a) show average losses of models trained on data with different difficulties, but I find that models with harder training data don't reach a plateau. A potential reason could be that models need more training epochs to converge on hard training examples. With enough training epochs, it is possible for models training on hard examples to get similar average losses.\n\n- The proposed training method is only evaluated on fast adversarial training and adversarial fine-tuning with additional data, but not on standard adversarial training. From my understanding, we can also combine this method with standard adversarial training. If the evaluation results also show improvements on standard adversarial training, the paper will be more compelling.\n", "summary_of_the_paper": "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.\nTo 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.\n", "summary_of_the_review": "This paper studies an interesting topic. It will be great that the method is also evaluated with other SOTA standard adversarial training methods.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a metric to measure the difficulty of training examples. The main thesis is that hard training examples lead to bad test adversarial error. There are theoretical results on simple models establishing such claims. The paper also proposes a method to adaptively weight training examples to improve training which gives improvement for adversarial error. 

The reviewers have raised a number of questions and the rebuttal period has been useful. In particularly, I agree with the reviewers that 'model-agnostic' is misleading in this context and the authors have agreed to remove this in the future. It is felt that more experiments, comparison to adversarial training, etc. is needed and I think the paper will need to go through a proper review process again before acceptance.
Decision: Reject