Year: 2021

Abstract:
Deep learning models have a propensity for fitting the entire training set even with random labels, which requires memorization of every training sample. In this paper, we explore the memorization effect in adversarial training (AT) for promoting a deeper understanding of model capacity, convergence, generalization, and especially robust overfitting of the adversarially trained models. We first demonstrate that deep networks have sufficient capacity to memorize adversarial examples of training data with completely random labels, but not all AT algorithms can converge under the extreme circumstance. Our study of AT with random labels motivates further analyses on the convergence and generalization of AT. We find that some AT approaches suffer from a gradient instability issue and most recently suggested complexity measures cannot explain robust generalization by considering models trained on random labels. Furthermore, we identify a significant drawback of memorization in AT that it could result in robust overfitting. We then propose a new mitigation algorithm motivated by detailed memorization analyses. Extensive experiments on various datasets validate the effectiveness of the proposed method.

heading: 1 INTRODUCTION
text: Deep neural networks (DNNs) usually exhibit excellent generalization ability in pattern recognition tasks, despite their sufficient capacity to overfit or memorize the entire training set with completely random labels (Zhang et al., 2017). The memorization behavior in deep learning has aroused tremendous attention to identifying the differences between learning on true and random labels (Arpit et al., 2017; Neyshabur et al., 2017), and examining what and why DNNs memorize (Feldman, 2020; Feldman & Zhang, 2020; Maennel et al., 2020). This phenomenon has also motivated a growing body of works on model capacity (Arpit et al., 2017; Belkin et al., 2019), convergence (Allen-Zhu et al., 2019; Du et al., 2019; Zou et al., 2020), and generalization (Neyshabur et al., 2017; Bartlett et al., 2017), which consequently provide a better understanding of the DNN working mechanism.
In this paper, we explore the memorization behavior for a different learning algorithm—adversarial training (AT). Owing to the security threat of adversarial examples, i.e., maliciously generated inputs by adding imperceptible perturbations to cause misclassification (Szegedy et al., 2014; Goodfellow et al., 2015), various defense methods have been proposed to improve the adversarial robustness of DNNs (Kurakin et al., 2017; Madry et al., 2018; Liao et al., 2018; Wong & Kolter, 2018; Cohen et al., 2019; Zhang et al., 2019b; Pang et al., 2019; 2020; Dong et al., 2020a). AT is arguably the most effective defense technique (Athalye et al., 2018; Dong et al., 2020b), in which the network is trained on the adversarially augmented samples instead of the natural ones (Madry et al., 2018).
Despite the popularity, the memorization behavior in AT is less explored. Schmidt et al. (2018) show that a model is able to fully (over)fit the training set against an adversary, i.e., reaching almost 100% robust training accuracy, while the performance on test data is much inferior, witnessing a significant generalization gap. The overfitting phenomenon in AT is further investigated in Rice et al. (2020). However, it is not clear whether DNNs could memorize adversarial examples of training data with completely random labels. Answering this question could help to examine the effects of memorization in AT under the “extreme” circumstance and facilitate a deeper understanding of capacity, convergence, generalization, and robust overfitting of the adversarially trained models. In general, it is difficult for a classifier to memorize adversarial examples with random labels since the model entails a much more complicated decision boundary, as illustrated in Fig. 1. Even though the networks have sufficient capacity, AT may not necessarily converge. Therefore, we aim to comprehensively study this problem and explore how the analysis can motivate better algorithms.
Our contributions. We first empirically investigate the memorization behavior in AT by performing PGD-AT (Madry et al., 2018) and TRADES (Zhang et al., 2019b) with random labels sampled uniformly over all classes. Different from standard training (ST) that can easily memorize random labels (Zhang et al., 2017), AT may fail to converge, with PGD-AT being a typical example. Nevertheless, TRADES can converge under this circumstance. It demonstrates that DNNs have sufficient capacity to memorize adversarial examples of training data with completely random labels. This phenomenon is commonly observed on multiple datasets, network architectures, and threat models.
The memorization analysis has further implications for understanding the convergence and generalization of AT. We conduct a convergence analysis on gradient magnitude and stability to explain the counter-intuitive different convergence properties of PGD-AT and TRADES with random labels since they behave similarly when trained on true labels (Rice et al., 2020). We corroborate that PGD-AT suffers from a gradient instability issue while the gradients of TRADES are relatively stable thanks to its adversarial loss. Moreover, by considering models trained on random labels, our generalization analysis indicates that several recently suggested complexity measures are inadequate to explain robust generalization, which is complementary to the findings in ST (Neyshabur et al., 2017). Accordingly, an appropriate explanation of robust generalization remains largely under-addressed.
Lastly, but most importantly, we identify a significant drawback of memorization in AT that it could result in robust overfitting (Rice et al., 2020). We argue that the cause of robust overfitting lies in the memorization of one-hot labels in the typical AT methods. The one-hot labels can be inappropriate or even noisy for some adversarial examples because some data may naturally lie close to the decision boundary, and the corresponding adversarial examples should be assigned low predictive confidence (Stutz et al., 2020; Cheng et al., 2020). When the network starts to memorize these noisy examples, robust overfitting occurs, as revealed by the learning curves. To address this problem, we propose a new mitigation algorithm that impedes over-confident predictions by a regularization term for avoiding the excessive memorization of adversarial examples with possibly noisy labels. Experiments validate that our approach can eliminate robust overfitting to a large extent across multiple datasets, network architectures, threat models, and AT methods, achieving better robustness under a variety of adversarial attacks than the baselines.

heading: 2 BACKGROUND

heading: 2.1 ADVERSARIAL TRAINING
text: Adversarial training is a commonly used technique to learn robust DNN classifiers against adversarial examples. We let D = {(xi, yi)}ni=1 denote the training dataset with n samples, where xi ∈ Rd is a natural example and yi ∈ {1, ..., C} is its true label often encoded as an one-hot vector 1yi with totally C classes. AT can be formulated as a robust optimization problem (Madry et al., 2018):
min θ n∑ i=1 max x′i∈S(xi) L(fθ(x′i), yi), (1)
where fθ is a DNN classifier with parameters θ that predicts probabilities over all classes, L is the classification loss (i.e., the cross-entropy loss as L(fθ(x), y) = −1>y log fθ(x)), and S(x) = {x′ : ‖x′ − x‖p ≤ } is an adversarial region centered at x with radius > 0 under the `p-norm threat models (e.g., `2 and `∞ norms that we consider). The robust optimization problem (1) is solved by using adversarial attacks to approximate the inner maximization and updating the model parameters
θ via gradient descent. A typical method uses projected gradient descent (PGD) (Madry et al., 2018) for the inner problem, which starts at a randomly initialized point in S(xi) and iteratively updates the adversarial example under the `∞-norm threat model by
x′i = ΠS(xi) ( x′i + α · sign(∇xL(fθ(x′i), yi)) ) , (2)
where Π(·) is the projection operator and α is the step size. Besides PGD-AT, another typical AT method is TRADES (Zhang et al., 2019b), which balances the trade-off between robustness and natural accuracy by minimizing a different adversarial loss
min θ n∑ i=1 { L(fθ(xi), yi) + β · max x′i∈S(xi) D(fθ(xi)‖fθ(x′i)) } , (3)
where L is the clean cross-entropy loss on the natural example, D is the Kullback–Leibler divergence, and β is a balancing parameter. The inner maximization of TRADES is also solved by PGD.
Recent progress of AT includes designing new adversarial losses (Mao et al., 2019; Qin et al., 2019; Pang et al., 2020; Wang et al., 2020; Dong et al., 2020a) and network architecture (Xie et al., 2019), training acceleration (Shafahi et al., 2019; Zhang et al., 2019a; Wong et al., 2020), and exploiting more training data (Hendrycks et al., 2019; Alayrac et al., 2019; Carmon et al., 2019; Zhai et al., 2019). Recent works highlight the training tricks in AT (Gowal et al., 2020; Pang et al., 2021).

heading: 2.2 RELATED WORK ON DNN MEMORIZATION
text: It has been observed that DNNs can easily memorize training data with random labels (Zhang et al., 2017), which requires “rethinking” of conventional techniques (e.g., VC dimension) to explain generalization. Arpit et al. (2017) identify qualitative differences between learning on true and random labels. Further works attempt to examine what and why DNNs memorize (Feldman, 2020; Feldman & Zhang, 2020; Maennel et al., 2020). Motivated by the memorization phenomenon in deep learning, convergence of training has been analyzed in the over-parameterized setting (Allen-Zhu et al., 2019; Du et al., 2019; Zou et al., 2020), while generalization has been studied with numerous theoretical and empirical complexity measures (Neyshabur et al., 2015; 2017; Bartlett et al., 2017; Novak et al., 2018; Arora et al., 2018; Cao & Gu, 2019; Jiang et al., 2020; Chen et al., 2020).
In contrast, the memorization behavior in AT has been less explored. The previous works demonstrate that DNNs can fit training data against an adversary (Madry et al., 2018; Schmidt et al., 2018; Rice et al., 2020), e.g., achieving nearly 100% robust training accuracy against a PGD adversary, but this behavior is not explored when trained on random labels. This paper is dedicated to investigating the memorization in AT under the extreme condition with random labels, while drawing connections to capacity, convergence, generalization, and robust overfitting, with the overarching goal of better understanding the AT working mechanism.

heading: 3 MEMORIZATION IN AT AND IMPLICATIONS
text: In this section, we first explore the memorization behavior in AT through an empirical study. Our analysis raises new questions about the convergence and generalization of AT, many of which cannot be answered by existing works. Thereafter, we provide further analytical studies on the convergence and generalization of AT by considering models trained on random labels particularly.

heading: 3.1 AT WITH RANDOM LABELS
text: We explore the memorization behavior of PGD-AT (Madry et al., 2018) and TRADES (Zhang et al., 2019b) as two studying cases. The experiments are conducted on CIFAR-10 (Krizhevsky & Hinton, 2009) with a Wide ResNet model (Zagoruyko & Komodakis, 2016) of depth 28 and widen factor 10 (WRN-28-10). Similar to Zhang et al. (2017), we train a network on the original dataset with true labels and on a copy of the dataset in which the true labels are corrupted by random ones. For training and robustness evaluation, a 10-step `∞ PGD adversary with = 8/255 and α = 2/255 is adopted. For TRADES, the PGD adversary maximizes the KL divergence during training, while maximizes the cross-entropy loss for robustness evaluation, as common practice (Zhang et al., 2019b). We set β = 6.0. In the sequel, we denote accuracy of a classifier against the 10-step PGD adversary as “robust accuracy”, and accuracy on natural examples as “natural accuracy”.
Fig. 2(a) and Fig. 2(b) show the learning curves of PGD-AT and TRADES without explicit regularizations. Both methods achieve almost 100% natural and robust training accuracies when trained on true labels. When the labels are random, we observe the totally different behaviors between PGDAT and TRADES—PGD-AT fails to converge while TRADES still reaches nearly 100% training accuracies. This phenomenon is somewhat striking because PGD-AT and TRADES perform similarly on true labels (Rice et al., 2020). We find that the different memorization behaviors between PGD-AT and TRADES when trained on random labels can commonly be observed across a variety of datasets, model architectures, and threat models (shown in Appendix A.1, indicating that it is a general phenomenon of memorization in the two AT methods. Therefore, our finding is:
DNNs have sufficient capacity to memorize adversarial examples of training data with completely random labels, but the convergence depends on the AT algorithms.
Partially corrupted labels. We then inspect the behavior of AT under varying levels of label noise from 0% (true labels) to 100% (completely random labels). The generalization gap (i.e., difference between training and test accuracies) presented in Fig. 2(c) grows steadily as we increase the noise rate before the network fails to converge. The learning curves are provided in Appendix A.1.
Explicit regularizations. We study the role of common regularizers in AT memorization, including data augmentation, weight decay, and dropout (Srivastava et al., 2014). We train TRADES on true and random labels with several combinations of regularizers. We observe the explicit regularizers do not significantly affect the model’s ability to memorize adversarial examples, similar to the finding in ST (Zhang et al., 2017; Arpit et al., 2017). The detailed results are provided in Appendix A.1.

heading: 3.2 CONVERGENCE ANALYSIS OF AT WITH RANDOM LABELS
text: Since we have observed a counter-intuitive fact that PGD-AT and TRADES exhibit different convergence properties with random labels, it is necessary to perform a convergence analysis to understand this phenomenon. Note that our finding can hardly be explained by previous works (Gao et al., 2019; Wang et al., 2019; Zhang et al., 2020).
We first study the effects of different training settings on PGD-AT with random labels. We conduct experiments to analyze each training factor individually, including network architecture, attack steps, optimizer, and perturbation budget. We find that tuning the training settings cannot make PGD-AT converge with random labels (Appendix A.2 details the results). Based on the analysis, we think that the convergence issue of PGD-AT could be a result of the adversarial loss function in Eq. (1) rather than other training configurations. Specifically, TRADES in Eq. (3) minimizes a clean cross-entropy (CE) loss on natural examples, making DNNs memorize natural examples with random labels before fitting adversarial examples. As seen in Fig. 2(b), at the very early stage of TRADES training (the first 25 epochs), the natural accuracy starts to increase while the robust accuracy does not. However, PGD-AT in Eq. (1) directly minimizes the CE loss on adversarial samples with random labels, which can introduce unstable gradients with large variance, making it fail to converge. To corroborate the above argument, we analyze the gradient magnitude and stability below.
Gradient magnitude. First, we calculate the average gradient norm of the adversarial loss in Eq. (1) w.r.t. model parameters over each training sample for PGD-AT, and similarly calculate the average gradient norm of the clean CE loss (the first term) and the KL loss (the second term) in Eq. (3) w.r.t. parameters for TRADES to analyze their effects, respectively. We present the gradient norm along with training in Fig. 3(a). We can see that at the initial training epochs, the gradient norm of the KL loss in TRADES is much smaller than that of the CE loss, which indicates that the CE
loss dominates TRADES training initially. With the training progressing, the KL loss has a larger gradient norm, making the network memorize adversarial examples. However, it is still unclear why PGD-AT does not rely on a similar learning tactic for convergence. To make a direct comparison with TRADES, we rewrite the adversarial loss of PGD-AT in Eq. (1) as
max x′i∈S(xi)
L(fθ(x′i), yi) = L(fθ(xi), yi) +R(xi, yi,θ),
where R(xi, yi,θ) denotes the difference between the CE loss on adversarial example x′i and that on natural example xi. Hence we can separately calculate the gradient norm of L(fθ(xi), yi) and R(xi, yi,θ) w.r.t. parameters θ to find out the effect of R(xi, yi,θ) on training. Specifically, we measure the relative gradient magnitude, i.e., in PGD-AT we calculate the ratio of the gradient norm ‖∇θR(xi,yi,θ)‖2 ‖∇θL(fθ(xi),yi)‖2 ; while in TRADES, we similarly calculate the ratio of the gradient norm of the KL loss to that of the CE loss. Fig. 3(b) illustrates the ratio of PGD-AT and TRADES during the first 1000 training iterations. The ratio of PGD-AT is consistently higher than that of TRADES, meaning thatR(xi, yi,θ) has a non-negligible impact on training. Gradient stability. Then, we analyze the gradient stability to explain why PGD-AT cannot converge. We denote the adversarial loss of PGD-AT as J (x, y,θ) = maxx′∈S(x) L(fθ(x′), y) with the subscript i omitted for notation simplicity. We have a theorem on gradient stability. Theorem 1. Suppose the gradient of the clean cross-entropy loss is locally Lipschitz continuous as
‖∇θL(fθ(x′), y)−∇θL(fθ(x), y)‖2 ≤ K‖x′ − x‖p, (4) for any x ∈ Rd, x′ ∈ S(x), and any θ, where K is the Lipschitz constant. Then we have ‖∇θJ (x, y,θ1)−∇θJ (x, y,θ2)‖2 ≤ ‖∇θL(fθ1(x), y)−∇θL(fθ2(x), y)‖2 + 2 K. (5)
We provide the proof in Appendix B, where we show the upper bound in Eq. (5) is tight. Theorem 1 indicates that the gradient of the adversarial loss J (x, y,θ) of PGD-AT will change more dramatically than that of the clean CE loss L(fθ(x), y). When θ1 and θ2 are close, the difference between the gradients of L at θ1 and θ2 is close to 0 due to the semi-smoothness of over-parameterized DNNs (Allen-Zhu et al., 2019), but that of J is relatively large due to 2 K in Eq. (5). To validate this, we visualize the change of gradient when moving the parameters θ along a random direction d with magnitude λ. In particular, we set θ as initialization, d is sampled from a Gaussian distribution and normalized filter-wise (Li et al., 2018). For PGD-AT and TRADES, we craft adversarial examples on-the-fly for the model with θ + λd and measure the change of gradient by the `2 distance to gradient at θ averaged over all data samples. The curves on gradient change of PGD-AT, TRADES, and the clean CE loss are shown in Fig. 4(a). In a small neighborhood of θ (i.e., small λ), the gradient of PGD-AT changes abruptly while the gradients of TRADES and the clean CE loss are more continuous. The gradient instability leads to a lower cosine similarity between the gradient directions w.r.t. the same data in each two successive training epochs of PGD-AT, as illustrated in Fig. 4(b). Therefore, the training of PGD-AT would be rather unstable that the gradient exhibits large variance, making it fail to converge.
Clean CE loss helps PGD-AT converge. To further verify our argument, we add the clean CE loss into the PGD-AT objective to resemble the learning of TRADES with random labels, as
min θ n∑ i=1 { (1− γ) · L(fθ(xi), yi) + γ · max x′i∈S(xi) L(fθ(x′i), yi) } , (6)
where γ is gradually increased from 0 to 1. By using Eq. (6), the gradient would be stabler at the initial stage and training on random labels can successfully converge, as shown Fig. 5.
In summary, our convergence analysis identifies the gradient instability issue of PGD-AT, provides new insights on the differences between PGD-AT and TRADES, and partially explain the failures of AT under other realistic settings beyond the scope of this section as detailed in Appendix A.2.

heading: 3.3 GENERALIZATION ANALYSIS OF AT WITH RANDOM LABELS
text: As our study demonstrates DNNs’ ability to memorize adversarial examples with random labels, we raise the question of whether DNNs rely on a similar memorization tactic on true labels and how to explain/ensure robust generalization. Although many efforts have been devoted to studying robust generalization of AT theoretically or empirically (Yin et al., 2018; Schmidt et al., 2018; Bubeck et al., 2019; Tu et al., 2019; Wu et al., 2020), they do not take the models trained on random labels into consideration. As it is easy to show that the explicit regularizations are not the adequate explanation of generalization in ST (Zhang et al., 2017; Arpit et al., 2017) and AT (see Appendix A.3, people resort to complexity measures of a model to explain generalization (i.e., a lower complexity should imply a smaller generalization gap). Here we show how the recently proposed complexity measures fail to explain robust generalization when comparing models trained on true and random labels.
We consider several norm-based and sharpness/flatness-based measures. We denote the parameters of a network by θ := {Wi}mi=1. The norm-based measures include spectral norm 1γmargin ∏m i=1 ‖Wi‖2
and `1 norm 1γmargin ∑m i=1 ‖Wi‖1 of model parameters, where γmargin is a margin on model output to make them scale-insensitive (Neyshabur et al., 2017). The spectral norm appears in the theoretical robust generalization bounds (Yin et al., 2018; Tu et al., 2019) and is related to the Lipschitz constant of neural networks (Cisse et al., 2017). The `1 norm is adopted to reduce the robust generalization gap (Yin et al., 2018). The sharpness/flatness-based measures include the curvature of input loss landscape (Moosavi-Dezfooli et al., 2019) as the dominant eigenvalue of the Hessian matrix, as well as the flatness of weight loss landscape (Wu et al., 2020) related to the change of adversarial loss when moving the weights along a random direction. Fig. 6 plots the four complexity measures w.r.t. robust generalization gap of several models trained with various combinations of regularizations on true or random labels. The results show that the first three measures can hardly ensure robust generalization, that lower complexity does not necessarily imply smaller robust generalization gap, e.g., the models trained on random labels can even lead to lower complexity than those trained on true labels. Among them, the flatness of weight loss landscape (Wu et al., 2020) is more reliable.
In summary, the generalization analysis indicates that the previous approaches, especially various complexity measures, cannot adequately explain and ensure the robust generalization performance in AT. Our finding of robust generalization in AT is complementary to that of standard generalization in ST (Zhang et al., 2017; Neyshabur et al., 2017; Jiang et al., 2020). Accordingly, robust generalization of adversarially trained models remains an open problem for future research.

heading: 4 ROBUST OVERFITTING ANALYSIS
text: Rice et al. (2020) have identified robust overfitting as a dominant phenomenon in AT, i.e., shortly after the first learning rate decay, further training will continue to decrease the robust test accuracy. They further show that several remedies for overfitting, including explicit `1 and `2 regularizations, data augmentation, etc., cannot gain improvements upon early stopping. Although robust overfitting has been thoroughly investigated, there still lacks an explanation of why it occurs. In this section, we draw a connection between memorization and robust overfitting in AT by showing that robust overfitting is caused by excessive memorization of one-hot labels in the typical AT methods. Motivated by the analysis, we then propose an effective strategy to eliminate robust overfitting.

heading: 4.1 EXPLAINING ROBUST OVERFITTING
text: The typical AT approaches (e.g., PGD-AT, TRADES) commonly adopt one-hot labels as the targets for training, as introduced in Sec. 2.1. The one-hot labels could be inappropriate for some adversarial examples because it is difficult for a network to assign high-confident one-hot labels for all perturbed samples within the perturbation budget (Stutz et al., 2020; Cheng et al., 2020). Intuitively, some examples may naturally lie close to the decision boundary and should be assigned lower predictive confidence for the worst-case adversarial examples. It indicates that one-hot labels of some training data may be noisy in AT1. After a certain training epoch, the model memorizes these “hard” training examples with possibly noisy labels, leading to the reduction of test robustness, as shown in Fig. 7(a). Thus, we hypothesize the cause of robust overfitting lies in the memorization of one-hot labels.
Our hypothesis is well supported by two pieces of evidence. First, we find that when the perturbation budget is small, robust overfitting does not occur, as shown in Fig. 7(b). This observation implies that the one-hot labels are more appropriate as the targets for adversarial examples within a smaller neighborhood while become noisier under a larger perturbation budget and lead to overfitting. Second, we validate that the “hard” training examples with higher adversarial loss values are consistent across different models. We first train two independent networks (using the same architecture and different random seeds) by PGD-AT and calculate the adversarial loss for each training sample. We show the adversarial losses on 500 samples sorted by the loss of the first model in Fig. 7(c). It can be seen that the samples with lower adversarial losses of the first model also have relatively lower losses of the second one and vice versa. We further quantitatively measure the consistency of the adversarial losses of all training samples between the two models using the Kendall’s rank coefficient (Kendall, 1938), which is 0.85 in this case. A similar result can be observed for two different model architectures (see Appendix C.1). The results verify that the “hard” training examples with possibly noisy labels are intrinsic of a dataset, supporting our hypothesis on why robust overfitting occurs.

heading: 4.2 MITIGATING ROBUST OVERFITTING
text: Based on the above analysis, we resort to the methods that are less prone to overfit noisy labels for mitigating robust overfitting in AT. Although learning with noisy labels has been broadly studied in ST (Natarajan et al., 2013; Patrini et al., 2017; Jiang et al., 2018; Han et al., 2018; Zhang & Sabuncu, 2018), we find that most of these approaches are not suitable for AT. For example, a typical line of methods filter out noisy samples and train the models on the identified clean samples (Jiang et al., 2018; Han et al., 2018; Ren et al., 2018). However, they will neglect a portion of training data with noisy labels, which can lead to inferior results for AT due to the reduction of training data (Schmidt et al., 2018). Table 2 shows the results to validate this.
To address this problem, we propose to regularize the predictions of adversarial examples from being over-confident by integrating the temporal ensembling (TE) approach (Laine & Aila, 2017) into the AT frameworks. TE maintains an ensemble prediction of each data and penalizes the difference between the current prediction and the ensemble prediction, which is effective for semi-supervised learning and learning with noisy labels (Laine & Aila, 2017). We think that TE is suitable for AT since it enables to leverage all training samples and hinders the network from excessive memorization of one-hot labels with a regularization term. Specifically, we denote the ensemble prediction of
1Note that we argue the one-hot labels are noisy when used in AT, but do not argue the ground-truth labels of the dataset are noisy, which is different from a previous work (Sanyal et al., 2021).
a training sample xi as pi, which is updated in each training epoch as pi ← η ·pi+(1−η) ·fθ(xi), where η is the momentum term. The training objective of PGD-AT with TE can be expressed as
min θ n∑ i=1 max x′i∈S(xi) { L(fθ(x′i), yi) + w · ‖fθ(x′i)− p̂i‖22 } , (7)
where p̂i is the normalization of pi as a probability vector and w is a balancing weight. TE can be similarly integrated with TRADES with the same regularization term. The network would learn to fit relatively easy samples with one-hot labels in the initial training stage, as shown in Fig. 7(a). After the learning rate decays, the network can keep assigning low confidence for hard samples with the regularization term in Eq. (7) and avoid fitting one-hot labels. Therefore, the proposed algorithm enables to learn under label noise in AT and alleviates the robust overfitting problem.

heading: 5 EMPIRICAL EVALUATION ON MITIGATING ROBUST OVERFITTING
text: In this section, we provide the experimental results on CIFAR-10, CIFAR-100 (Krizhevsky & Hinton, 2009), and SVHN (Netzer et al., 2011) datasets to validate the effectiveness of our proposed method on mitigating robust overfitting in AT.
Training details. We adopt the common setting that the perturbation budget is = 8/255 under the `∞ norm in most experiments. We consider PGD-AT and TRADES as two typical AT baselines and integrate the proposed TE approach into them, respectively. We use the ResNet-18 (He et al., 2016) model as the classifier in most experiments. In training, we use the 10-step PGD adversary with α = 2/255. The models are trained via the SGD optimizer with momentum 0.9, weight decay 0.0005, and batch size 128. For CIFAR-10/100, we set the learning rate as 0.1 initially which is decayed by 0.1 at 100 and 150 epochs with totally 200 training epochs. For SVHN, the learning rate starts from 0.01 with a cosine annealing schedule for a total number of 80 training epochs. In our method, We set η = 0.9 and w = 30 along a Gaussian ramp-up curve (Laine & Aila, 2017).
Evaluation results. We adopt PGD-10, PGD-1000, C&W-1000 (Carlini & Wagner, 2017), and AutoAttack (Croce & Hein, 2020b) for evaluating adversarial robustness rigorously. AutoAttack is a strong attack to evaluate model robustness, which is composed of an ensemble of diverse attacks, including APGD-CE (Croce & Hein, 2020b), APGD-DLR (Croce & Hein, 2020b), FAB (Croce
& Hein, 2020a), and Square attack (Andriushchenko et al., 2020). To show the performance of robust overfitting, we report the test accuracy on the best checkpoint that achieves the highest robust test accuracy under PGD-10 and the final checkpoint, as well as the difference between these two checkpoints. The results of PGD-AT, TRADES, and the combinations of them with our proposed approach (denoted as PGD-AT+TE and TRADES+TE) on the CIFAR-10, CIFAR-100, and SVHN datasets are shown in Table 1.
We can observe that the differences between best and final test accuracies of our method are reduced to around 1%, while the accuracy gaps of PGDAT and TRADES are much larger. It indicates that our method largely eliminates robust overfitting. Due to being less affected by robust overfitting, our method achieves higher robust accuracies than the baselines. We also show the learning curves of these methods in Fig. 8. We consistently demonstrate the effectiveness of our method on different network architectures (including WRN-34-10
and VGG-16) and threat models (including `2 norm), which will be shown in Appendix C.2.
Discussion and comparison with related works. Our method is kind of similar to the label smoothing (LS) technique, which is studied in AT (Pang et al., 2021). Recent works have also introduced the smoothness in training labels and model weights (Chen et al., 2021; Huang et al., 2020), which can alleviate robust overfitting to some extent. The significant difference between our work and them is that we provide a reasonable explanation for robust overfitting—one-hot labels are noisy for AT, while previous methods did not give such an explanation and could be viewed as solutions to our identified problem. To empirically compare with these methods, we conduct experiments on CIFAR-10 with the ResNet-18 network. Under the PGD-AT framework, we compare with the baseline PGD-AT, PGD-AT+LS, self-adaptive training (SAT) (Huang et al., 2020), and knowledge distillation with stochastic weight averaging (KD-SWA) (Chen et al., 2021). We also adopt the Coteaching approach (Han et al., 2018) adapted to PGD-AT, which jointly trains two models using the filtered samples given by each other. The results under the adopted attacks are presented in Table 2. Although various techniques can alleviate robust overfitting, our method achieves better robustness than the others, validating its effectiveness. For Co-teaching, though robust overfitting is alleviated, the performance is worse than our proposed method due to the reduction of training data.

heading: 6 CONCLUSION
text: In this paper, we demonstrate the capacity of DNNs to fit adversarial examples with random labels by exploring memorization in adversarial training, which also poses open questions on the convergence and generalization of adversarially trained models. We validate that some AT methods suffer from a gradient instability issue and robust generalization can hardly be explained by complexity measures. We further identify a significant drawback of memorization in AT related to the robust overfitting phenomenon—robust overfitting is caused by memorizing one-hot labels in adversarial training. We propose a new mitigation algorithm to address this issue, with the effectiveness validated extensively.

heading: ETHICS STATEMENT
text: The existence of adversarial examples can pose severe security threats to machine learning and deep learning models when they are deployed to real-world applications. The vulnerability to adversarial examples could also lower the confidence of the public on machine learning techniques. Therefore, it is important to develop more robust models. As the most effective method for promoting model robustness, adversarial training (AT) has not been fully investigated. This paper aims to investigate the memorization effect of AT to facilitate a better understanding of its working mechanism. Some findings in this paper can be analyzed more deeply, including theoretical analysis of AT convergence, generalization, etc., which we leave to future work.

heading: REPRODUCIBILITY STATEMENT
text: Most of the experiments are easily reproducible. We provide the code for reproducing the results in the supplementary material.

heading: A ADDITIONAL EXPERIMENTS ON MEMORIZATION IN AT
text: In this section, we provide additional experiments on the memorization behavior in AT. All of the experiments are conducted on NVIDIA 2080 Ti GPUs. The source code of this paper is submitted as the supplementary material, and will be released after the review process.

heading: A.1 MEMORIZATION OF PGD-AT AND TRADES

heading: A.1.1 DIFFERENT TRAINING SETTINGS
text: We first demonstrate that the different memorization behaviors between PGD-AT and TRADES can be generally observed under various settings.
Datasets. Similar to Fig. 2, we show the accuracy curves of PGD-AT and TRADES when trained on true or random labels on CIFAR-100 (Krizhevsky & Hinton, 2009) in Fig. A.1 and on SVHN (Netzer et al., 2011) in Fig. A.2. We consistently observe that PGD-AT fails to converge with random labels, while TRADES can successfully converge, although it does not reach 100% accuracy on SVHN.
Model architectures. We then consider other network architectures, including the DenseNet-121 model (Huang et al., 2017) and the deep layer aggregation (DLA) model (Yu et al., 2018). The corresponding results are shown in Fig. A.3. The similar results can be observed, although it may take more training epochs to make TRADES converge with the smaller DenseNet-121 network.
Threat models. We further consider the `2-norm threat model, in which we set = 1.0 and α = 0.25 in the 10-step PGD adversary. The learning curves of PGD-AT and TRADES are shown in Fig. A.4, which also exhibit similar results.
Perturbation budget. We study the memorization behavior in AT with different perturbation budgets . In Fig. A.5, we show that when the perturbation budget is = 16/255 (`∞ norm), TRADES trained on random labels can still converge. But when we set a larger budget (e.g., = 32/255), both PGD-AT and TRADES cannot obtain near 100% robust training accuracy. We also find under this condition, even AT trained on true labels cannot get 100% robust training accuracy, indicating that the gradient instability issue discussed in Sec. 3.2 results in the convergence problem.
In summary, our empirical observation that PGD-AT and TRADES perform differently when trained on random labels is general across multiple datasets, network architectures, and threat models.

heading: A.1.2 LEARNING CURVES UNDER DIFFERENT NOISE RATES
text: We show the learning curves of PGD-AT and TRADES under varying levels of label noise in Fig. A.6 and Fig. A.7, respectively. In this experiment, we adopt the weight decay and data augmentation for regularizations. We can see that the network achieves maximum accuracy on the test set before fitting the noisy training set. Thus the model learns easy and simple patterns first before fitting the noise, similar to the finding in ST (Arpit et al., 2017). It can also be observed that under 80% noise rate, PGD-AT fails to converge. Note that when the noise rate is 0%, the network is trained on true labels, but the robust test accuracy also decreases after a certain epoch. This phenomenon is called robust overfitting (Rice et al., 2020), which is studied in Sec. 4.

heading: A.1.3 EXPLICIT REGULARIZATIONS
text: We consider three common regularizers, including data augmentation, weight decay, and dropout (Srivastava et al., 2014). We train the models based on TRADES on true and random labels with several combinations of explicit regularizers. As shown in Table A.1, the explicit regularizations do not significantly affect the model’s ability to memorize adversarial examples with random labels.

heading: A.2 MORE RESULTS ON THE CONVERGENCE OF AT

heading: A.2.1 TRAINING CONFIGURATIONS
text: We study different training configurations on PGD-AT with random labels. We consider various factors as follows. These experiments are conducted on CIFAR-10.
• Model capacity. Recent work suggests that model size is a critical factor to obtain better robustness (Madry et al., 2018; Xie & Yuille, 2020). A possible reason why PGD-AT fails to converge with random labels may also be the insufficient model capacity. Therefore, we try to use larger models, including WRN-34-20 (which is used in Rice et al. (2020)) and WRN-70-16 (which is used in Gowal et al. (2020)). However, using larger models under this setting cannot solve the convergence problem.

heading: A.2.2 GRADIENT STABILITY UNDER COSINE SIMILARITY
text: In Fig. 4(a), we show the gradient change of PGD-AT, TRADES, and the clean CE loss under the `2 distance. We further show the cosine similarity between the gradients at θ and θ + λd in Fig. A.8. The cosine similarity is also averaged over all data samples. The results based on cosine similarity are consistent with the results based on the `2 distance, showing that the gradient of PGD-AT changes more abruptly.

heading: A.2.3 THE FAILURES OF AT UNDER REALISTIC SETTINGS
text: We find that some AT methods (e.g., PGD-AT) suffer from a gradient instability issue, which results in the convergence problem when trained on random labels. Under other realistic setting, our analysis may also be valuable.
First, PGD-AT fails to converge under 80% noise rate. We think that the unstable gradients can overwhelm the useful gradients given by clean examples. To prove it, we train the models under 80% uniform label noise, by either PGD-AT or standard training (ST) on natural examples. We then select 100 training images with wrong labels and another 100 training images with true labels for evaluation. Similarly, we calculate the gradient norm of the cross-entropy loss w.r.t. model parameters of each method. We show the results in Fig. A.9. For AT, the gradient norm of clean examples is larger than that of noisy examples at beginning, which makes the model learn to classify. However, for PGD-AT, the gradient norm of clean examples is almost the same as that of noisy examples (the two curves overlap together). And the unstable gradients provided by noisy examples would overwhelm the useful gradients given by clean examples, making the network fail to converge.
Second, when the perturbation budget is large (e.g., = 64/255), PGD-AT cannot converge with true labels, while TRADES can achieve about 50% training accuracies. This can also be explained by our convergence analysis that the gradient is very unstable in PGD-AT with a larger perturbation budget, making it fail to converge.

heading: A.3 MORE DISCUSSIONS ON THE GENERALIZATION OF AT
text: As shown in Table A.1, when trained on true labels, although the regularizers can help to reduce the generalization gap, the model without any regularization can still generalize non-trivially. The three explicit regularizations do not significantly affect the model’s ability to memorize adversarial examples with random labels. In consequence, the explicit regularizers are not the adequate explanation of generalization. By inspecting the learning dynamics of AT under different noise rates in Fig. A.6 and Fig. A.7, the network achieves maximum accuracy on the test set before fitting the noisy training set, meaning that the model learns simple patterns (i.e., clean data) before memorizing the hard examples with wrong labels, similar to the observation in standard training (Arpit et al., 2017). The results suggest that optimization by itself serves as an implicit regularizer to find a model with good generalization performance.
A recent work (Liu et al., 2020b) points out that in standard training, pre-training on random labels can lead to substantial performance degeneration of subsequent SGD training on true labels, while adding regularizations can overcome the bad initialization caused by pre-training with random labels. In this paper, we further investigate whether this finding can generalize to adversarial training.
As PGD-AT cannot converge with random labels, we adopt TRADES to conduct experiments. Following Liu et al. (2020b), we consider two initialization strategies — random initialization and adversarial initialization generated by training on random labeling of the training data. We also consider two training methods — vanilla SGD training and SOTA SGD training with data augmentation (random crops and flips), weight decay, and momentum. The results are shown in Fig. A.10. It can be seen that with vanilla SGD, the adversarial initialization can lead to worse performance than the random initialization. But with the regularization techniques, the models with different initializations converge to nearly the same test accuracy. The results are consistent with the findings in Liu et al. (2020b).

heading: B PROOF OF THEOREM 1
text: Proof. Recall that J (x, y,θ) = maxx′∈S(x) L(fθ(x′), y) is the adversarial loss of PGD-AT. First, we have
‖∇θJ (x, y,θ1)−∇θJ (x, y,θ2)‖2 =‖∇θJ (x, y,θ1)−∇θL(fθ1(x), y)− ∇θJ (x, y,θ2) +∇θL(fθ2(x), y)+ ∇θL(fθ1(x), y)−∇θL(fθ2(x), y)‖2 ≤‖∇θJ (x, y,θ1)−∇θL(fθ1(x), y)‖2+ ‖∇θJ (x, y,θ2)−∇θL(fθ2(x), y)‖2+ ‖∇θL(fθ1(x), y)−∇θL(fθ2(x), y)‖2.
(B.1)
From the assumption, for any x ∈ Rd and x′ ∈ S(x), we have
‖∇θL(fθ(x′), y)−∇θL(fθ(x), y)‖2 ≤ K‖x′ − x‖p ≤ K,
due to the definition of S(x). We also note that J (x, y,θ) is the maximal cross-entropy loss L within S(x), such that we have
‖∇θJ (x, y,θ)−∇θL(fθ(x), y)‖2 ≤ K. (B.2)
Combining Eq. (B.1) and Eq. (B.2), we can obtain Eq. (5).
Note that the bound is tight since the all the equalities can be reached.
Remark 1. We note that a recent work (Liu et al., 2020a) gives a similar result on gradient stability. The difference is that they assume the loss function satisfies an additional Lipschitzian smoothness condition as ‖∇θL(fθ1(x), y)−∇θL(fθ2(x), y)‖2 ≤ Kθ‖θ1 − θ2‖2, where Kθ is another constant. Then they prove that
‖∇θJ (x, y,θ1)−∇θJ (x, y,θ2)‖2 ≤ Kθ‖θ1 − θ2‖2 + 2 K.
It can be noted that with this new assumption, we can simply obtain this result by Theorem 1. Therefore, Theorem 1 is a more general result of the previous one.

heading: B.1 THEORETICAL ANALYSIS FOR TRADES
text: Note that TRADES adopts the KL divergence in its adversarial loss. The KL divergence is defined on two predicted probability distributions over all classes, as
D(fθ(x)‖fθ(x′)) = ∑
y∈{1,...,C}
fθ(x)y · log fθ(x)y fθ(x′)y .
However, based on the local Lipschitz continuity assumption of the clean cross-entropy loss (which is only concerned with the predicted probability of the true class) in Eq. (4), we cannot derive a similar theoretical bound on the gradient stability of TRADES as in Eq. (5). Therefore, we need to make a different assumption on the KL divergence. For example, suppose the gradient of the KL divergence satisfies
‖∇θD(fθ(x)‖fθ(x′))‖2 ≤ K ′‖x′ − x‖p,
for any x ∈ Rd, x′ ∈ S(x), and any θ, where K ′ is another constant. We denote the adversarial loss of TRADES as J ′(x, y,θ), then we have
‖∇θJ ′(x, y,θ1)−∇θJ ′(x, y,θ1)‖2 ≤‖∇θL(fθ1(x), y)−∇θL(fθ2(x), y)‖2+ β‖∇θ max
x′∈S(x) D(fθ1(x)‖fθ1(x′))‖2+
β‖∇θ max x′∈S(x) D(fθ2(x)‖fθ2(x′))‖2
≤‖∇θL(fθ1(x), y)−∇θL(fθ2(x), y)‖2 + 2β K ′.
Although we can derive a similar bound on gradient stability of TRADES, this bound is not directly comparable to Eq. (5) since we cannot find the relationship between K and K ′. However, our empirical analysis on gradient magnitude in Sec. 3.2 has shown that TRADES is dominated by the clean cross-entropy loss at the initial training epochs, thus the gradient stability of the TRADES loss will be similar to that of the clean cross-entropy loss, as also revealed in Fig. 4(a). Therefore, the gradient of TRADES would be relatively stable.

heading: C FULL EXPERIMENTS ON ROBUST OVERFITTING

heading: C.1 ADDITIONAL EXPERIMENTS ON EXPLAINING ROBUST OVERFITTING
text: First, we show the robust test accuracy curves of TRADES under various perturbation budgets in Fig. C.1. It can also be observed that when the perturbation budget is small, robust overfitting does not occur.
Second, we show that the “hard” training examples with higher adversarial loss values are consistent across different model architectures. We train one WRN-28-10 model and one ResNet-18 model based on PGD-AT. We then calculate the adversarial loss for each training sample for these two models. We show the adversarial loss on 500 samples sorted by the loss of the first model (i.e., WRN28-10) in Fig. C.2. It can be seen that the samples with lower adversarial losses of the first model also have relatively lower losses of the second one and vice versa. The Kendall’s rank coefficient of the adversarial loss between the two models is 0.78 in this case.
Third, we visualize the hard training examples with high adversarial loss values in Fig. C.3. It can be seen that these examples are difficult to recognize and their labels may be wrong. Therefore, the one-hot labels for these hard training examples can be noisy for AT, leading to the robust overfitting problem.

heading: C.2 ADDITIONAL EXPERIMENTS ON MITIGATING ROBUST OVERFITTING
text: We show the results of our proposed methods on other network architectures (including WRN34-10 and VGG-16) and threat models (including `2 norm) in Table C.1. The results consistently demonstrate the effectiveness of the proposed method.
We further show the results of PGD-AT, PGD-AT+TE, TRADES, and TRADES+TE on CIFAR-10 over 3 runs in Table C.2.

Review summaries:
This paper presents a thorough investigation of the dynamics of adversarial training (AT) when a network is trained on a dataset with random labels. This methodology was very successful at identifying theoretical gaps in our understanding of neural networks for standard training, so here the authors propose to replicate those experiments in the context of adversarial robustness. Surprisingly, the authors find that PGD-AT is incapable of fitting random labels when trained from scratch, while TRADES or a warmed-start version of PGD-AT can. They also suggest plausible explanations for this behavior. Finally, the authors use their novel findings to explore the reasons behind robust overfitting, and propose a new method to prevent it. 

This paper presents the memorization effect/behavior in adversarial training in perspective of model capacity, convergence and generalization. They first investigate the difference of memorization behavior between two adversarial training methods, PGD-AT and TRADES, with random labels and provide the proof of gradient instability for PGD-AT in terms of Lipschitz constant. Also they suggest that previous complexity measures are inadequate to explain robust generalization. Lastly, they investigate the cause of robust overfitting in AT and propose a mitigation algorithm by a regularization term for avoiding the excessive memorization of adversarial examples.

This paper provides comprehensive studies on several facts about the memorization of adversarial training algorithms (AT). Specifically, the authors uncover two findings: (1) Given a sufficient model capacity, PGD Adversarial Training cannot fit the whole training set (with 100% labels flipped). While, TRADES can fit the whole random flipped set. It may be because the objective function of TRADES has a clean loss, which can improve the stability of training. (2) Memorization of one-hot labels in AT methods can be one important factor to the robust overfitting issues. Based on these findings, the authors propose a method Temporal Ensembling (TE) approach to avoid fitting all adversarial examples with one-hot labels. 

Memorization has been investigated in deep neural network classifiers but not that much in adversarial training. The authors investigate the ability of adversarial training to memorize random datasets. They use PGD-AT and TRADES to do the adversarial training and see different convergence properties, which differs significantly from training on true labels. They also discover that robust overfitting can occur in adversarial training with memorization and use temporal ensembling to mitigate it.