Year: 2021

Abstract:
We investigate two causes for adversarial vulnerability in deep neural networks: bad data and (poorly) trained models. When trained with SGD, deep neural networks essentially achieve zero training error, even in the presence of label noise, while also exhibiting good generalization on natural test data, something referred to as benign overfitting (Bartlett et al., 2020; Chatterji & Long, 2020). However, these models are vulnerable to adversarial attacks. We identify label noise as one of the causes for adversarial vulnerability, and provide theoretical and empirical evidence in support of this. Surprisingly, we find several instances of label noise in datasets such as MNIST and CIFAR, and that robustly trained models incur training error on some of these, i.e. they don’t fit the noise. However, removing noisy labels alone does not suffice to achieve adversarial robustness. We conjecture that in part sub-optimal representation learning is also responsible for adversarial vulnerability. By means of simple theoretical setups, we show how the choice of representation can drastically affect adversarial robustness.

heading: 1 INTRODUCTION
text: Modern machine learning methods achieve a very high accuracy on wide range of tasks, e.g. in computer vision, natural language processing etc. However, especially in vision tasks, they have been shown to be highly vulnerable to small adversarial perturbations that are imperceptible to the human eye (Dalvi et al., 2004; Biggio & Roli, 2018; Goodfellow et al., 2014) . This vulnerability poses serious security concerns when these models are deployed in real-world tasks (cf. (Papernot et al., 2017; Schönherr et al., 2018; Hendrycks et al., 2019b; Li et al., 2019a)). A large body of research has been devoted to crafting defences to protect neural networks from adversarial attacks (e.g. (Goodfellow et al., 2014; Papernot et al., 2015; Tramèr et al., 2018; Madry et al., 2018; Zhang et al., 2019)). However, such defences have usually been broken by future attacks (Athalye et al., 2018; Tramer et al., 2020). This arms race between attacks and defenses suggests that to create a truly robust model would require a deeper understanding of the source of this vulnerability.
Our goal in this paper is not to propose new defenses, but to provide better answers to the question: what causes adversarial vulnerability? In doing so, we also seek to understand how existing methods designed to achieve adversarial robustness overcome some of the hurdles pointed out by our work. We identify two sources of adversarial vulnerability that, to the best of our knowledge, have not been properly studied before: a) memorization of label noise, and b) improper representation learning.
Overfitting Label Noise: Starting with the celebrated work of Zhang et al. (2016) it has been observed that neural networks trained with SGD are capable of memorizing large amounts of label noise. Recent theoretical work (e.g. (Liang & Rakhlin, 2018; Belkin et al., 2018b;a; Hastie et al., 2019;
Belkin et al., 2019a;b; Bartlett et al., 2020; Muthukumar et al., 2020; Chatterji & Long, 2020)) has also sought to explain why fitting training data perfectly does not lead to a large drop in test accuracy, as the classical notion of overfitting might suggest. This is commonly referred to as memorization or interpolation. We show through simple theoretical models, as well as experiments on standard datasets, that there are scenarios where label noise causes significant adversarial vulnerability, even when high natural (test) accuracy can be achieved. Surprisingly, we find that label noise is not at all uncommon in datasets such as MNIST and CIFAR-10 (see Figure 1).
Our experiments show that robust training methods like Adversarial training (AT) (Madry et al., 2018) and TRADES (Zhang et al., 2019) produce models that incur training error on at least some of the noisy examples,but also on atypical examples from the classes (Zhang & Feldman, 2020). Viewed differently, robust training methods are unable to differentiate between atypical correctly labelled examples (rare dog) and a mislabelled example (cat labelled as dog) and end up not memorizing either; interestingly, the lack of memorizing these atypical examples has been pointed out as an explanation for slight drops in test accuracy, as the test set often contains similarly atypical (or even identical) examples in some cases Feldman (2019); Zhang & Feldman (2020). We point out this phenomenon for robust models through visual examples on MNIST, CIFAR10, and Imagenet (c.f. Figure 4).
Representation Learning and Robustness: Recent works (Tsipras et al., 2019) and Zhang et al. (2019) have argued that the trade-off between robustness and accuracy might be unavoidable. However, their setting involves a distribution that is not robustly separable by any classifier. In such a situation there is indeed a trade-off between robustness and accuracy. In this paper, we focus on settings where robust classifiers exist, which is a more realistic scenario for real-world data. At least for vision, one may well argue that “humans” are robust classifiers, and as a result we would expect that classes are well-separated at least in some representation space. In fact, Yang et al. (2020) show that classes are already well-separated in the input space. In such situations, there is no need for robustness to be at odds with accuracy. A more plausible scenario which we posit, and provide theoretical evidence in support of in Theorem 2, is that depending on the choice of representations, the trade-off may exist or can be avoided. Recent empirical work (Sanyal et al., 2020a; Mao et al., 2020) has also established that modifying the training objective to favour certain properties in the learned representations can automatically lead to improved robustness. However, we show in Section 3.2 that some training algorithms can create an apparent trade-off even though the trade-off might not necessarily be fundamental to the problem.
On a related note, it has been suggested in recent works that adversarially robust learning may require more “complex” decision boundaries, and as a result may require more data (Shah et al.; Schmidt et al., 2018; Yin et al., 2019; Nakkiran, 2019; Madry et al., 2018). However, the question of decision boundaries in neural networks is subtle as the network learns a feature representation as well as a decision boundary on top of it. We develop concrete theoretical examples in Theorem 2 and 3 to establish that choosing one feature representation over another may lead to visually more complex decision boundaries on the input space, though these are not necessarily more complex in terms of statistical learning theoretic concepts such as VC dimension.

heading: Summary of Theoretical Contributions
text: 1. We provide simple sufficient conditions on the data distribution under which any classifier that fits the training data with label noise perfectly is adversarially vulnerable. 2. There exists data distributions and training algorithms, which when trained with (some fraction of) random label noise have the following property: (i) using one representation, it is possible
to have high natural and robust test accuracies but at the cost of having training error; (ii) using another representation, it is possible to have no training error (including fitting noise) and high test accuracy, but low robust accuracy. (See Theorem 2).
The second example shows that the choice of representation matters significantly when it comes to adversarial accuracy, and that memorizing label noise directly leads to loss of robust accuracy.

heading: Summary of Experimental Contributions
text: 1. As predicted theoretically, neural nets trained to convergence with label noise have greater adversarial vulnerability. (See Section 3.1).
2. Robust training methods, such as AT and TRADES that have higher robust accuracy, avoid overfitting (some) label noise. This behaviour is also partly responsible for their decrease in natural test accuracy. (See Section 3.2).
3. To demonstrate the benefit of representation learning for adversarial robustness, we show that learning richer representation by training with more fine-grained labels, subclasses within each class, leads to higher robust accuracy. (Due to lack of space we moved this to Appendix C.3).
While our primary contribution is showing the effect of overfitting label noise on adversarial robustness, we hope our theoretical and experimental evidences on the importance of representation learning for robustness will inspire further research in this direction.

heading: 2 THEORETICAL SETTING
text: We develop a simple theoretical framework to demonstrate how overfitting, even very minimal, label noise causes significant adversarial vulnerability. We also show in Theorem 2 and 3 how the choice of representation can significantly affect robust accuracy. Although we state the results for binary classification, they can easily be generalized to multi-class problems. We formally define the notions of natural (test) error and adversarial error. Definition 1 (Natural and Adversarial Error). For any distribution D defined over (x, y) ∈ Rd × {0, 1} and any binary classifier f : Rd → {0, 1},
• the natural error is R(f ;D) = P(x,y)∼D [f (x) 6= y] , (1)
• if Bγ (x) is a ball of radius γ ≥ 0 around x under some norm1, the γ-adversarial error is RAdv,γ(f ;D) = P(x,y)∼D [∃z ∈ Bγ (x) ; f (z) 6= y] , (2)
In the rest of the section, we provide theoretical results to show the effect of overfitting label noise on the robustness of classifiers.

heading: 2.1 OVERFITTING LABEL NOISE
text: The following result provides a sufficient condition under which even a small amount of label noise causes any classifier that fits the training data perfectly to have significant adversarial error. Informally, Theorem 1 states that if the data distribution has significant probability mass in a union of (a relatively small number of, and possibly overlapping) balls, each of which has roughly the same probability mass (cf. Eq. (3)), then even a small amount of label noise renders this entire region vulnerable to adversarial attacks to classifiers that fit the training data perfectly. Theorem 1. Let c be the target classifier, and let D be a distribution over (x, y), such that y = c (x) in its support. Using the notation PD[A] to denote P(x,y)∼D[x ∈ A] for any measurable subset A ⊆ Rd, suppose that there exist c1 ≥ c2 > 0, ρ > 0, and a finite set ζ ⊂ Rd satisfying
PD ⋃ s∈ζ Bpρ (s)  ≥ c1 and ∀s ∈ ζ, PD [Bpρ (s)] ≥ c2|ζ| (3) 1Throughout, we will mostly use the (most commonly used) `∞ norm, but the results hold for other norms.
(a) Toy-MNIST , = 64 255
(b) Full-MNIST
where Bpρ (s) represents a `p-ball of radius ρ around s. Further, suppose that each of these balls contain points from a single class i.e. for all s ∈ ζ, for all x, z ∈ Bpρ (s) : c (x) = c (z). Let Sm be a dataset of m i.i.d. samples drawn from D, which subsequently has each label flipped independently with probability η. For any classifier f that perfectly fits the training data Sm i.e. ∀ x, y ∈ Sm, f (x) = y, ∀δ > 0 and m ≥ |ζ|ηc2 log ( |ζ| δ ) , with probability at least 1 − δ, RAdv,2ρ(f ;D) ≥ c1.
The goal is to find a relatively small set ζ that satisfies the condition as this will mean that even for modest sample sizes, the trained models have significant adversarial error. We remark that it is easy to construct concrete instantiations of problems that satisfy the conditions of the theorem, e.g. each class represented by a spherical (truncated) Gaussian with radius ρ, with the classes being well-separated satisfies Eq. (3). The main idea of the proof is that there is sufficient probability mass for points which are within distance 2ρ of a training datum that was mislabelled. We note that the generality of the result, namely that any classifier (including neural networks) that fits the training data must be vulnerable irrespective of its structure, requires a result like Theorem 1. For instance, one could construct the classifier h, where h(x) = c(x), if (x, b) 6∈ Sm for b = 0, 1, and h(x) = y if (x, y) ∈ Sm. Note that the classifier h agrees with the target c on every point of Rd except the mislabelled training examples, and as a result these examples are the only source of vulnerability. The complete proof is presented in Appendix B.1.
There are a few things to note about Theorem 1. First, the lower bound on adversarial error applies to any classifier f that fits the training data Sm perfectly and is agnostic to the type of model f is. Second, for a given c1, there maybe multiple ζs that satisfy the bounds in (3) and the adversarial risk holds for all of them. Thus, smaller the value of |ζ| the smaller the size of the training data it needs to fit and it can be done by simpler classifiers. Third, if the distribution of the data is such that it is concentrated around some points then for a fixed c1, c2, a smaller value of ρ would be required to satisfy (3) and thus a weaker adversary (smaller perturbation budget 2ρ) can cause a much larger adversarial error.
In practice, classifiers exhibit much greater vulnerability than purely arising from the presence of memorized noisy data. Experiments in Section 3.1 show how label noise causes vulnerability in a toy MNIST model, the full MNIST and CIFAR10 for a variety of architectures.

heading: 3 EXPERIMENTS ON OVERFITTING LABEL NOISE
text: In Section 2, we provided theoretical settings to highlight how fitting label noise hurts adversarial robustness. In this section, we provide empirical evidence on synthetic data inspired by the theory and on the standard datasets: MNIST (LeCun et al., 1998), CIFAR10 (Krizhevsky & Hinton, 2009),
and on a lesser scale Imagenet to support the theory. Further details about the experimental settings including model architectures are in Appendix D.

heading: 3.1 OVERFITTING LABEL NOISE DECREASES ADVERSARIAL ACCURACY
text: We design a simple binary classification problem, toy-MNIST, and show that when fitting a complex classifier on a training dataset with label noise, adversarial vulnerability increases with the amount of label noise, and that this vulnerability is caused by the label noise. The problem is constructed by selecting two random images from MNIST: one “0” and one “1”. Each training/test example is generated by selecting one of these images and adding i.i.d. Gaussian noise sampled from N ( 0, σ2 ) . We create a training dataset of 4000 samples by sampling uniformly from either class. Finally, η fraction of the training data is chosen randomly and its labels are flipped. We train a neural network with four fully connected layers followed by a softmax layer and minimize the cross-entropy loss using an SGD optimizer until the training error becomes zero. Then, we attack this network with a strong `∞ PGD adversary (Madry et al., 2018) with = 64255 for 400 steps with a step size of 0.01.
In Figure 2a, we plot the adversarial error, test error and training error as the amount of label noise (η) varies, for three different values of sample variance (σ2). For low values of σ2 (σ2 = 0.1), the training data from each class is all concentrated around the same point; as a result these models are unable to memorize the label noise and the training error is high. In this case, over-fitting label noise is impossible and the test error, as well as the adversarial error, is low. However, as σ2 increases to σ2 = 0.5, the neural network is flexible enough to use the “noise component” to extract features that allow it to memorize label noise and fit the training data perfectly. This brings the training error down to zero, while causing the test error to increase, and the adversarial error even more so. This is in line with Theorem 1.
Remark 1. The case when σ2 = 0.3 is particularly interesting; when the label noise is low and the training error is high, there is no overfitting and the test error and the adversarial error is zero. When the network starts memorizing label noise (i.e. train error gets lesser than label noise), test error still remains very low but adversarial error increases rapidly.
We perform a similar experiment on the full MNIST dataset trained on a 4-layered Convolutional Neural Network. For varying values of η, for a uniformly randomly chosen η fraction of the training data we assigned the class label randomly. We compute the natural test accuracy and the adversarial test accuracy for when the network is attacked with a `∞ bounded PGD adversary for varying perturbation budget , with a step size of 0.01 and for 20 steps and plot the results in Figure 2b. We repeat the same experiment for CIFAR10 with a DenseNet121 (Huang et al., 2017), ResNet18 (He et al., 2016), and VGG19 (Simonyan & Zisserman, 2014) to test the phenomenon across multiple state of the art architectures and plot the results in Figure 2c to 2e. The results on both datasets show that the effect of over-fitting label noise on adversarial error is even more clearly visible here; for the same PGD adversary the adversarial error jumps sharply with increasing label noise, while the growth of natural test error is much slower. This confirms the hypothesis that benign overfitting may not be so benign when it comes to adversarial error.
For the toy-MNIST problem, we plot a 2-d projection (using PCA) of the learned representations (activations before the last layer) at various stages of training in Figure 3. (We remark that the simplicity of the data model ensures that even a 1-d PCA projection suffices to perfectly separate the classes when there is no label noise; however, the representations learned by a neural network in the presence of noise maybe very different!) We highlight two key observations: (i) The bulk of adversarial examples (“+”-es) are concentrated around the mis-labelled training data (“◦”-es) of the opposite class. For example, the purple +-es (Adversarially perturbed: True: 0, Pred:1 ) are very close to the green ◦-es (Mislabelled: True:0, Pred: 1). This provides empirical validation for the hypothesis that if there is a mis-labelled data-point in the vicinity that has been fit by the model, an adversarial example is created by moving towards that data point as predicted by Theorem 1. (ii) The mis-labelled training data take longer to be fit by the classifier. For example by iteration 20, the network actually learns a fairly good representation and classification boundary that correctly fits the clean training data (but not the noisy training data). At this stage, the number of adversarial examples are much lower as compared to Iteration 160, by which point the network has completely fit the noisy training data. Thus early stopping helps in avoiding memorizing the label noise, and consequently also reduces adversarial vulnerability. Early stopping has indeed been used as a defence in quite a few recent papers in context of adversarial robustness (Wong et al., 2020; Hendrycks et al., 2019a), as well as learning in the presence of label-noise (Li et al., 2019b). Our work provides an explanation regarding why early stopping may reduce adversarial vulnerability by avoiding fitting noisy training data.

heading: 3.2 ROBUST TRAINING AVOIDS MEMORIZATION OF LABEL NOISE AND ATYPICAL EXAMPLES
text: Robust training methods like AT (Madry et al., 2018) and TRADES (Zhang et al., 2019) are commonly used techniques to increase adversarial robustness of deep neural networks. However, it has been pointed out that this comes at a cost to clean accuracy (Raghunathan et al., 2019; Tsipras et al., 2019). When trained with these methods, both the training and test accuracy (on clean data) for commonly used deep learning models drops with increasing strength of the PGD adversary used (see Table 1). In this section, we provide evidence to show that robust training avoids memorization of label noise and this also results in the drop of clean train and test accuracy.
Robust training ignores label noise Figure 1 shows that label noise is not uncommon in standard datasets like MNIST and CIFAR10. In fact, upon closely monitoring the mis-classified training set examples for both AT and TRADES, we found that neither predicts correctly on the training set labels for any of the examples identified in Figure 1, all examples that have a wrong label in the training set, whereas natural training does. Thus, in line with Theorem 1, robust training methods ignore fitting noisy labels.
PLANES CAR BIRD CAT DEER
DOG FROG HORSE SHIP TRUCK
(a) Fraction of train points that have a self-influence greater than s is plotted versus s. (b) Distribution of the influence of training point on all test points compared to the distribution of influence on test points mis-classified by adversarially trained points.
Figure 5: The blue represents the points mis-classified by an adversarially trained model. The orange represents the distribution for all points in the dataset (of the concerned class for CIFAR10).
We also observe this in a synthetic experiment on the full MNIST dataset where we assigned random labels to 15% of the dataset. A naturally trained CNN model achieved 100% accuracy on this dataset whereas an adversarially trained model (standard setting with = 0.3 for 30 steps) mis-classified 997 examples in the training set after the same training regime. Out of these 997 samples, 994 examples were mislabelled in the dataset.
Robust training ignores rare examples Certain examples in the training set belong to rare subpopulations (eg. a special kind of cat) and this sub-population is sufficiently distinct from the rest of the examples of that class in the training dataset (other cats in the dataset). Next, we show that though ignoring rare samples helps in adversarial robustness, it hurts the natural test accuracy. Our hypothesis is that one of the effects of robust training is to not memorize rare examples, which would otherwise be memorized by a naturally trained model. As Feldman (2019) points out, if these subpopulations are very infrequent in the training dataset, they are indistinguishable from data-points with label noise with the difference being that examples from that sub-population are also present in the test-set. Natural training by memorizing those rare training examples reduces the test error on the corresponding test examples. Robust training, by not memorizing these rare samples (and label noise), achieves better robustness but sacrifices the test accuracy on the test examples corresponding to those training points.
Experiments on MNIST, CIFAR10, and ImageNet We visually demonstrate this effect in Figure 4 with examples from CIFAR10, MNIST, and ImageNet and then provide more statistical evidence using the notions of memorization score and influence (Zhang & Feldman, 2020) in Figure 5. Each pair of images contains a mis-classified (by robustly trained models) test image and the mis-classified training image “responsible” for it (see Appendix D.2 for details on how they were found and further details on memorization and influence.). Importantly both of these images were correctly classified by a naturally trained model. Visually, it is evident that the training images are extremely similar to the corresponding test image. Inspecting the rest of the training set, they are also very different from other images in the training set. We can thus refer to these as rare sub-populations.
The notion that certain test examples were not classified correctly due to a particular training examples not being classified correctly is measured by the influence a training image has on the test image (c.f. defn 3 in Zhang & Feldman (2020)). We obtained the influence of each training image on each test image for that class from Zhang & Feldman (2020) and the training images in Figure 4 has a disproportionately higher influence on the corresponding test image compared to influences of other train-test image pairs in CIFAR10. A precise notion of measuring if a sample is rare is through the concept of self-influence or memorization. Self-influence for a rare example, that is unlike other examples of that class, will be high as the rest of the dataset will not provide relevant information that will help the model in correctly predicting on that particular example.
In Figure 5a, we show that the self-influence of training samples that were mis-classified by adversarially trained models but correctly classified by a naturally trained model is higher compared to the
distribution of self-influence on the entire train dataset. In other words, it means that the self-influence of the training examples mis-classified by the robustly trained models is larger than the average self-influence of (all) examples belonging to that class. This supports our hypothesis that adversarial training excludes fitting these rare (or ones that need to be memorized) samples. In Figure 5b, we show that the influence of training images are higher on test images that are mis-classified by adversarially trained models as compared to an average test image from the dataset. In other words, this means that adversarially trained models mis-classify test examples that are heavily influenced by some particular training example. As we saw in Figure 5a, AT models do not memorize atypical train examples; consequently they misclassify test examples that are heavily influenced by those atypical train examples (visualized in Figure 4). This confirms our hypothesis that the loss in test accuracy of robustly trained models are due to test images that are rare and thus has a particularly high influence from a training image.

heading: 4 REPRESENTATION LEARNING AND ROBUSTNESS
text: Label noise by itself is not the sole cause for adversarial vulnerability especially in deep learning models trained with standard optimization procedures like SGD. A second cause is the choice of representation of the data, which in turn affects the shape of the decision boundary. The choice of model affects representations and introduces desirable and possibly even undesirable (cf. (Liu et al., 2018)) invariances; for example, training convolutional networks are invariant to (some) translations, while training fully connected networks are invariant to permutations of input features. This means that fully connected networks can learn even if the pixels of each training image in the training set are permuted with a fixed permutation (Zhang et al., 2016). This invariance is worrying as it means that such a network can effectively classify a tensor that is visually nothing like a real image into an image category. While CNNs don’t have this particular invariance, as Liu et al. (2018) shows, CNNs are unable to predict where in the image a particular object is.
In Theorem 2, we show that for one (”correct”) choice of representation, it will be impossible to fit the training data perfectly in the presence of label noise, but the classifier that best fits the training data, in that restricted class of classifiers,2 will have good test accuracy and adversarial accuracy. On the other hand, when a different (“incorrect”) representation is used, we show that it is possible to find a classifier that has no training error, has good test accuracy, but has high adversarial error. We posit this as an (partial) explanation of why classifiers trained on real data (with label noise, or at least atypical examples) have good test accuracy, while still being vulnerable to adversarial attacks.
Theorem 2. For any n ∈ Z+, there exists a family of distributions Dn over R × {0, 1} and function classes C,H, such that for any P from Dn, and for any 0 < γ < 1/4, and η ∈ (0, 1/2) if Sm = {(xi, yi)}mi=1 denotes a sample of size m drawn from P where
m = O ( max { n log n
δ
( (1− η)
(1− 2η)2 + 1
) , n
ηγ2 log
( n
γδ
)})
and if Sm,η denotes the sample where each label is flipped independently with probability η.
(i) the classifier c ∈ C that minimizes the training error on Sm,η, has R(c;P) = 0 and RAdv,γ(c;P) = 0 for 0 ≤ γ < 1/4.
(ii) there exist h ∈ H, h has zero training error on Sm,η, andR(h;P) = 0. However, for any γ > 0, and for any h ∈ H with zero training error on Sm,η ,RAdv,γ(h;P) ≥ 0.1.
Furthermore, the required c ∈ C and h ∈ H above can be computed in O ( poly (n) ,poly (
1 1 2−η
) ,poly ( 1 δ )) time.
In Theorem 3, we show a similar result without the effect of label noise. In Appendix C.3, we provide experimental results learning more meaningful representations by training on more fine-grained labels (instead of the relevant coarse labels directly) can improve adversarial robustness.
2This is referred to as the Empirical Risk Minimization (ERM) in the statistical learning theory literature.

heading: 5 RELATED WORK
text: Montasser et al. (2019) established that there are concept classes with finite VC dimensions i.e. are properly PAC-learnable but are only improperly robustly PAC learnable. This implies that to learn the problem with small adversarial error, a different class of models (or representations) needs to be used whereas for small natural test risk, the original model class (or representation) can be used. Recent empirical works have also shown evidence towards this (eg. (Sanyal et al., 2020a)). In particular, the examples from Montasser et al. (2019) that uses improper learning to learn a robust classifier has a much higher sample complexity. In our example, learning algorithms for both the hypotheses classes that we use have polynomial sample complexity. Another point of distinction is that Theorem 2 uses a training set induced with random classification noise and hypothesis classH obtains zero training on this noisy training set whereas the examples in Montasser et al. (2019) do not have any label noise.
Hanin & Rolnick (2019) have shown that though the number of possible linear regions that can be created by a deep ReLU network is exponential in depth, in practice for networks trained with SGD this tends to grow only linearly thus creating much simpler decision boundaries than is possible due to sheer expresssivity of deep networks. Experiments on the data models from our theoretical settings indeed show that adversarial training indeed produces more “complex” decision boundaries
Jacobsen et al. (2019) have discussed that excessive invariance in neural networks might increase adversarial error. However, their argument is that excessive invariance can allow sufficient changes in the semantically important features without changing the network’s prediction. They describe this as Invariance based adversarial examples as opposed to perturbation based adversarial examples. We show that excessive (incorrect) invariance might also result in perturbation based adversarial examples.
Another contemporary work (Geirhos et al.) discusses a phenomenon they refer to as Shortcut Learning where deep learning models perform very well on standard tasks like reducing classification error but fail to perform in more difficult real world situations. We discuss this in the context of models that have small test error but large adversarial error and provide and theoretical and empirical to discuss why one of the reasons for this is sub-optimal representation learning.

heading: 6 CONCLUSION
text: Recent research has largely shone a positive light on interpolation (zero training error) by highly over-parameterized models even in the presence of label noise. While overfitting noisy data may not harm generalisation, we have shown that this can be severely detrimental to robustness. This raises a new security threat where label noise can be inserted into datasets to make the models learnt from them vulnerable to adversarial attacks without hurting their test accuracy. As a result, further research into learning without memorization is ever more important (Sanyal et al., 2020b; Shen & Sanghavi, 2019). Further, we underscore the importance of proper representation learning in regards to adversarial robustness. Representations learnt by deep networks often encode a lot of different invariances, e.g., location, permutation, rotation, etc. While some of them are useful for the particular task at hand, we highlight that certain invariances can increase adversarial vulnerability. Thus we believe that making significant progress towards training robust models with good test error requires us to rethink representation learning and closely examine the data on which we are training these models.

heading: 7 ACKNOWLEDGEMENT
text: We thank Vitaly Feldman and Chiyuan Zhang for providing us with data that helped to significantly speed up some parts of this work. We also thank Nicholas Lord for feedback on the draft. AS acknowledges support from The Alan Turing Institute under the Turing Doctoral Studentship grant TU/C/000023. VK is supported in part by the Alan Turing Institute under the EPSRC grant EP/N510129/1. PHS and PD acknowledges support from the Royal Academy of Engineering under the Research Chair and Senior Research Fellowships scheme, EPSRC/MURI grant EP/N019474/1 and FiveAI.

heading: A REPRESENTATION LEARNING AND ADVERSARIAL ROBUSTNESS
text: In this section we present another result to show that there exists a data distribution where proper representation is necessary even in the absence of label noise for small adversarial error as well as small test error whereas another representation can provide low test error but necessarily have large adversarial error. Interestingly, the representation that can achieve small adversarial error can look visually more complex due to larger number of distinct linear regions in its decision boundary. However, statistically it will have a smaller VC dimension than its counterpart.
We first present the theorems with a proof sketch for ease of understanding and the more detailed proofs in Appendix B. Theorem 3. For some universal constant c, and any 0 < γ0 < 1/ √
2, there exists a family of distributions D defined on X × {0, 1} where X ⊆ R2 such that for all distributions P ∈ D, and denoting by Sm = {(x1, y1) , · · · , (xm, ym)} a sample of size m drawn i.i.d. from P , (i) For any m ≥ 0, Sm is linearly separable i.e., ∀(xi, yi) ∈ Sm, there exist w ∈ R2, w0 ∈ R s.t.
yi ( w>xi + w0 ) ≥ 0. Furthermore, for every γ > γ0, any linear separator f that perfectly fits
the training data Sm hasRAdv,γ(f ;P) ≥ 0.0005, even thoughR(f ;P)→ 0 as m→∞. (ii) There exists a function class H such that for some m ∈ O(log(δ−1)), any h ∈ H that perfectly
fits the Sm, satisfies with probability at least 1− δ,R(h;P) = 0 andRAdv,γ(h;P) = 0, for any γ ∈ [0, γ0 + 1/8].
A complete proof of this result appears in Appendix B.2, but first, we provide a sketch of the key idea here.The distributions in family D will be supported on balls of radius at most 1/ √ 2 on the integer lattice in R2. The true class label for any point x is provided by the parity of a+ b, where (a, b) is the lattice point closest to x. However, the distributions in D are chosen to be such that there is also a linear classifier that can separate these classes, e.g. a distribution only supported on balls centered at the points (a, a) and (a, a+ 1) for some integer a (See Figure 6b). Visually learning the classification problem using the parity of a+ b results in a seemingly more complex decision boundary, a point that has been made earlier regarding the need for more complex boundaries to achieve adversarial robustness (Nakkiran, 2019; Degwekar et al., 2019). However, it is worth noting that this complexity is not rooted in any statistical theory, e.g. the VC dimension of the classes considered in Theorem 3 is essentially the same (even lower forH by 1). This visual complexity arises purely due to the fact that the linear classifier looks at a geometric representation of the data whereas the parity classifier looks at the binary representation of the sum of the nearest integer of the coordinates. In the case of neural networks, recent works (Kamath et al., 2020) have indeed provided empirical results to support that excessive invariance (eg. rotation invariance) increases adversarial error.

heading: REPRESENTATION LEARNING IN THE PRESENCE OF LABEL NOISE
text: Here we restate Theorem 2 and present a proof sketch for the result.
Theorem 2. For any n ∈ Z+, there exists a family of distributions Dn over R × {0, 1} and function classes C,H, such that for any P from Dn, and for any 0 < γ < 1/4, and η ∈ (0, 1/2) if
Sm = {(xi, yi)}mi=1 denotes a sample of size m drawn from P where
m = O ( max { n log n
δ
( (1− η)
(1− 2η)2 + 1
) , n
ηγ2 log
( n
γδ )}) and if Sm,η denotes the sample where each label is flipped independently with probability η.
(i) the classifier c ∈ C that minimizes the training error on Sm,η, has R(c;P) = 0 and RAdv,γ(c;P) = 0 for 0 ≤ γ < 1/4.
(ii) there exist h ∈ H, h has zero training error on Sm,η, andR(h;P) = 0. However, for any γ > 0, and for any h ∈ H with zero training error on Sm,η ,RAdv,γ(h;P) ≥ 0.1.
Furthermore, the required c ∈ C and h ∈ H above can be computed in O ( poly (n) ,poly (
1 1 2−η
) ,poly ( 1 δ )) time.
We sketch the proof here and present the complete the proof in Appendix B.3; as in Appendix A we will make use of parity functions, though the key point is the representations used. Let X = [0, N ], where N = 2n, we consider distributions that are supported on intervals (i − 1/4, i + 1/4) for i ∈ {1, . . . , N − 1} (See Figure 6a), but any such distribution will only have a small number, O(n), intervals on which it is supported. The true class label is given by a function that depends on the parity of some hidden subsets S of bits in the bit-representation of the closest integer i, e.g. as in Figure 6a if S = {0, 2}, then only the least significant and the third least significant bit of i are examined and the class label is 1 if an odd number of them are 1 and 0 otherwise. Despite the noise, the correct label on any interval can be guessed by using the majority vote and as a result, the correct parity learnt using Gaussian elimination. (This corresponds to the class C in Theorem 2.) On the other hand it is also possible to learn the function as a union of intervals, i.e. find intervals, I1, I2, . . . , Ik such that any point that lies in one of these intervals is given the label 1 and any other point is given the label 0. By choosing intervals carefully, it is possible to fit all the training data, including noisy examples, but yet not compromise on test accuracy (Fig. 6a). Such a classifier, however, will be vulnerable to adversarial examples by applying Theorem 1. A classifier such as union of intervals (H in Theorem 2) is translation-invariant, whereas the parity classifier is not. This suggests that using classifiers, such as neural networks, that are designed to have too many built-in invariances might hurt its robustness accuracy.

heading: B PROOFS FOR SECTION 2
text: In this section, we present the formal proofs to the theorems stated in Section 2.

heading: B.1 PROOF OF THEOREM 1
text: Theorem 1. Let c be the target classifier, and let D be a distribution over (x, y), such that y = c (x) in its support. Using the notation PD[A] to denote P(x,y)∼D[x ∈ A] for any measurable subset A ⊆ Rd, suppose that there exist c1 ≥ c2 > 0, ρ > 0, and a finite set ζ ⊂ Rd satisfying
PD ⋃ s∈ζ Bpρ (s)  ≥ c1 and ∀s ∈ ζ, PD [Bpρ (s)] ≥ c2|ζ| (3) where Bpρ (s) represents a `p-ball of radius ρ around s. Further, suppose that each of these balls contain points from a single class i.e. for all s ∈ ζ, for all x, z ∈ Bpρ (s) : c (x) = c (z). Let Sm be a dataset of m i.i.d. samples drawn from D, which subsequently has each label flipped independently with probability η. For any classifier f that perfectly fits the training data Sm i.e. ∀ x, y ∈ Sm, f (x) = y, ∀δ > 0 and m ≥ |ζ|ηc2 log ( |ζ| δ ) , with probability at least 1 − δ, RAdv,2ρ(f ;D) ≥ c1.
Proof of Theorem 1. From (3), for any ζ and s ∈ ζ,
P(x,y)∼D [x ∈ Bρ (s)] ≥ c2 |ζ|
As the sampling of the point and the injection of label noise are independent events,
P(x,y)∼D [x ∈ Bρ (s) ∧ x gets mislabelled] ≥ c2η
|ζ|
Thus, PSm∼Dm [∃ (x, y) ∈ Sm : x ∈ Bρ (s) ∧ x is mislabelled] ≥ 1− (
1− c2η |ζ| )m ≥ 1− exp ( −c2ηm |ζ| )
Substituting m ≥ |ζ|ηc2 log ( |ζ| δ ) and applying the union bound over all s ∈ ζ, we get
PSm∼Dm [∀s ∈ ζ, ∃ (x, y) ∈ Sm : x ∈ Bρ (s) ∧ x is mislabelled] ≥ 1− δ (4)
As for all s ∈ Rd and ∀x, z,∈ Bpρ (s) , ‖x− z‖p ≤ 2ρ, we have that RAdv,2ρ(f ;D) = PSm∼Dm [ P(x,y)∼D [∃z ∈ B2ρ (x) ∧ y 6= f (z)] ] ≥ PSm∼Dn P(x,y)∼D x ∈ ⋃
s∈ζ
Bpρ (s) ∧ {∃z ∈ B2ρ (x) : y 6= f (z)}  (1) = PSm∼Dn [ P(x,y)∼D [ ∃s ∈ ζ : x ∈ Bpρ (s) ∧ {∃z ∈ B2ρ (x) : y 6= f (z)}
]] ≥ PSm∼Dm [ P(x,y)∼D [ ∃s ∈ ζ : x ∈ Bpρ (s) ∧ {∃z ∈ Bρ (s) : y 6= f (z)}
]] (2) = PSm∼Dm [ P(x,y)∼D [ ∃s ∈ ζ : x ∈ Bpρ (s) ∧ {∃z ∈ Bρ (s) : c (z) 6= f (z)}
]] (3) = P(x,y)∼D
x ∈ ⋃ s∈ζ Bpρ (s)  w.p. atleast 1− δ ≥ c1 w.p. 1− δ
where c is the true concept for the distribution D. Equality (1) follows from the fact that the event x ∈ ⋃ s∈ζ Bpρ (s) is equivalent to the event that there exists an i ∈ {1, .., |ζ|} such that x ∈ Bpρ (si). Equality (2) follows from the assumptions that each of the balls around s ∈ ζ are pure in their labels. Equality (3) follows from 4 by using the x that is guaranteed to exist in the ball around s and be mis-labelled with probability atleast 1− δ. To see how, replace the x in Assumption 4 with z. The last equality follows from the first Assumption in 3.

heading: B.2 PROOFS OF APPENDIX A
text: Theorem 3. For some universal constant c, and any 0 < γ0 < 1/ √
2, there exists a family of distributions D defined on X × {0, 1} where X ⊆ R2 such that for all distributions P ∈ D, and denoting by Sm = {(x1, y1) , · · · , (xm, ym)} a sample of size m drawn i.i.d. from P , (i) For any m ≥ 0, Sm is linearly separable i.e., ∀(xi, yi) ∈ Sm, there exist w ∈ R2, w0 ∈ R s.t.
yi ( w>xi + w0 ) ≥ 0. Furthermore, for every γ > γ0, any linear separator f that perfectly fits
the training data Sm hasRAdv,γ(f ;P) ≥ 0.0005, even thoughR(f ;P)→ 0 as m→∞. (ii) There exists a function class H such that for some m ∈ O(log(δ−1)), any h ∈ H that perfectly
fits the Sm, satisfies with probability at least 1− δ,R(h;P) = 0 andRAdv,γ(h;P) = 0, for any γ ∈ [0, γ0 + 1/8].
Proof of Theorem 3. We define a family of distribution D, such that each distribution in D is supported on balls of radius r around (i, i) and (i+ 1, i) for positive integers i. Either all the balls around (i, i) have the labels 1 and the balls around (i+ 1, i) have the label 0 or vice versa. Figure 6b shows an example where the colors indicate the label.
Formally, for r > 0, k ∈ Z+, the (r, k)-1 bit parity class conditional model is defined over (x, y) ∈ R2 × {0, 1} as follows. First, a label y is sampled uniformly from {0, 1}, then and integer i is sampled uniformly from the set {1, · · · , k} and finally x is generated by sampling uniformly from the `2 ball of radius r around (i+ y, i).
In Lemma 1 we first show that a set of m points sampled iid from any distribution as defined above for r < 1
2 √ 2 is with probability 1 linear separable for any m. In addition, standard VC bounds show that any linear classifier that separates Sm for large enough m will have small test error. Lemma 1 also proves that there exists a range of γ, r such that for any distribution defined with r in that range, though it is possible to obtain a linear classifier with 0 training and test error, the minimum adversarial risk will be bounded from 0.
However while it is possible to obtain a linear classifier with 0 test error, all such linear classifiers has a large adversarial vulnerability. In Lemma 2, we show that there exists a different representation for this problem, which also achieves zero training and test error and in addition has zero adversarial risk for a range of r, γ where the linear classifier’s adversarial error was atleast a constant.
Lemma 1 (Linear Classifier). There exists universal constants γ0, ρ, such that for any perturbation γ > γ0, radius r ≥ ρ, and k ∈ Z+, the following holds. Let D be the family of (r, k)- 1-bit parity class conditional model, P ∈ D and Sn = {(x1, y1) , · · · , (xn, y1)} be a set of n points sampled i.i.d. from P .
1) For any n > 0, Sn is linearly separable with probability 1 i.e. there exists a h : (w, w0), w ∈ R2, w0 ∈ R such that the linear hyperplane x → w>x + w0 separates Sn with probability 1:
∀ (x, y) ∈ Sn z ( w>x + w0 ) > 0 where z = 2y − 1
2) Further there exists an universal constant c such that for any , δ > 0 with probability 1− δ for any Sn with n = c 1 2 log 1 δ , any linear classifier h̃ that separates Sn hasR(h̃;P) ≤ . 3) Let h : (w, w0) be any linear classifier that has R(h;PP ) = 0. Then, RAdv,γ(h;P) > 0.0005.
We will prove the first part for any r < 1 2 √ 2 by constructing a w, w0 such that it satisfies the constraints of linear separability. Let w = (1,−1) , w0 = −0.5. Consider any point (x, y) ∈ Sn and z = 2y − 1. Converting to the polar coordinate system there exists a θ ∈ [0, 2π] , j ∈ [0, · · · , k] such that x = ( j + z+12 + rcos (θ) , j + rsin (θ)
) z ( w>x + w0 ) = z ( j + z + 1
2 + rcos (θ)− j − rsin (θ)− 0.5
) w = (1,−1)>
= z (z
2 + 0.5 + rcos (θ)− rsin (θ)− 0.5 ) = 1
2 + zr (cos (θ)− sin (θ)) |cos (θ)− sin (θ)| <
√ 2, z ∈ {−1, 1}
> 1 2 − r √ 2 > 0 r < 1
2 √ 2
Part 2 follows with simple VC bounds of linear classifiers.
Let the universal constants γ0, ρ be 0.02 and 12√2 − 0.008 respectively. Note that there is nothing special about this constants except that some constant is required to bound the adversarial risk away from 0. Now, consider a distribution P 1-bit parity model such that the radius of each ball is atleast ρ. This is smaller than 1
2 √ 2 and thus satisfies the linear separability criterion.
Consider h to be a hyper-plane that has 0 test error. Let the `2 radius of adversarial perturbation be γ > γ0. The region of each circle that will be vulnerable to the attack will be a circular segment with the chord of the segment parallel to the hyper-plane. Let the minimum height of all such circular
segments be r0. Thus, RAdv,γ(h;P) is greater than the mass of the circular segment of radius r0. Let the radius of each ball in the support of P be r. Using the fact that h has zero test error; and thus classifies the balls in the support of P correctly and simple geometry
1√ 2 ≥ r + (γ − r0) + r
r0 ≥ 2r + γ − 1√ 2
(5)
To computeRAdv,γ(h;P) we need to compute the ratio of the area of a circular segment of height r0 of a circle of radius r to the area of the circle. The ratio can be written
A (r0 r ) = cos−1 ( 1− r0r ) − ( 1− r0r )√ 2 r0r − r20 r2 π (6)
As (6) is increasing with r0r , we can evaluate
r0 r ≥
2r − 1√ 2 + γ
r Using (5)
≥ 2− 1√ 2 − 0.02 r
γ > γ0 = 0.02
≥ 2− 1√ 2 − 0.02
1√ 2 − 0.008
> 0.01 r > ρ = 1
2 √ 2 − 0.008
Substituting r0r > 0.01 into Eq. (6), we get that A ( r0 r ) > 0.0005. Thus, for all γ > 0.02, we have RAdv,γ(h;P) > 0.0005. Lemma 2 (Robustness of parity classifier). There exists a concept class H such that for any γ ∈[ γ0, γ0 + 1 8 ] , k ∈ Z+, P being the corresponding (ρ, k) 1-bit parity class distribution where ρ, γ0 are the same as in Lemma 1 there exists g ∈ H such that
R(g;P) = 0 RAdv,γ(g;P) = 0
Proof of Lemma 2. We will again provide a proof by construction. Consider the following class of conceptsH such that gb ∈ H is defined as
g ( (x1, x2) > ) = { 1 if [x1] + [x2] = b (mod 2) 1− b o.w. (7)
where [x] rounds x to the nearest integer and b ∈ {0, 1}. In Figure 6b, the green staircase-like classifier belongs to this class. Consider the classifier g1. Note that by constructionR(g1;P) = 0. The decision boundary of g1 that are closest to a ball in the support of P centered at (a, b) are the lines x = a± 0.5 and y = b± 0.5. As γ < γ0 + 18 , the adversarial perturbation is upper bounded by 1 50 + 1 8 . The radius of the ball is upper bounded by 1 2 √ 2
, and as we noted the center of the ball is at a distance of 0.5 from the decision boundary. If the sum of the maximum adversarial perturbation and the maximum radius of the ball is less than the minimum distance of the center of the ball from the decision boundary, then the adversarial error is 0. Substituting the values,
1
50 +
1 8 + 1 2 √ 2 < 0.499 < 1 2
This completes the proof.

heading: B.3 PROOF OF APPENDIX A
text: Theorem 2. For any n ∈ Z+, there exists a family of distributions Dn over R × {0, 1} and function classes C,H, such that for any P from Dn, and for any 0 < γ < 1/4, and η ∈ (0, 1/2) if Sm = {(xi, yi)}mi=1 denotes a sample of size m drawn from P where
m = O ( max { n log n
δ
( (1− η)
(1− 2η)2 + 1
) , n
ηγ2 log
( n
γδ )}) and if Sm,η denotes the sample where each label is flipped independently with probability η.
(i) the classifier c ∈ C that minimizes the training error on Sm,η, has R(c;P) = 0 and RAdv,γ(c;P) = 0 for 0 ≤ γ < 1/4.
(ii) there exist h ∈ H, h has zero training error on Sm,η, andR(h;P) = 0. However, for any γ > 0, and for any h ∈ H with zero training error on Sm,η ,RAdv,γ(h;P) ≥ 0.1.
Furthermore, the required c ∈ C and h ∈ H above can be computed in O ( poly (n) ,poly (
1 1 2−η
) ,poly ( 1 δ )) time.
Proof of Theorem 2. We will provide a constructive proof to this theorem by constructing a distribution D, two concept classes C andH and provide the ERM algorithms to learn the concepts and then use Lemma 3 and 4 to complete the proof.
Distribution: Consider the family of distribution Dn such that DS,ζ ∈ Dn is defined on Xζ ×{0, 1} for S ⊆ {1, · · · , n} , ζ ⊆ {1, · · · , 2n − 1} such that the support of Xζ is a union of intervals.
supp (X )ζ = ⋃ j∈ζ Ij where Ij := ( j − 1 4 , j + 1 4 ) (8)
We consider distributions with a relatively small support i.e. where |ζ| = O (n). Each sample (x, y) ∼ DS,ζ is created by sampling x uniformly from Xζ and assigning y = cS (x) where cS ∈ C is defined below (9). We define the family of distributions D = ⋃ n∈Z+ D
n. Finally, we create DηS,ζ -a noisy version of DS,ζ , by flipping y in each sample (x, y) with probability η < 12 . Samples from DS,ζ can be obtained using the example oracle EX (DS,ζ) and samples from the noisy distribution can be obtained through the noisy oracle EXη (DS,ζ) Concept Class C: We define the concept class Cn of concepts cS : [0, 2n]→ {0, 1} such that
cS (x) = { 1, if (〈[x]〉b XOR S) is odd. 0 o.w.
(9)
where [·] : R→ Z rounds a decimal to its nearest integer, 〈·〉b : {0, · · · , 2n} → {0, 1}n returns the binary encoding of the integer, and (〈[x]〉b XOR S) = ∑ j∈S〈[x]〉b [j] mod 2. 〈[x]〉b [j] is the jth least significant bit in the binary encoding of the nearest integer to x. It is essentially the class of parity functions defined on the bits corresponding to the indices in S for the binary encoding of the nearest integer to x. For example, as in Figure 6a if S = {0, 2}, then only the least significant and the third least significant bit of i are examined and the class label is 1 if an odd number of them are 1 and 0 otherwise.
Concept Class H: Finally, we define the concept class H = ⋃∞ k=1Hk where Hk is the class of union of k intervals on the real lineHk. Each concept hI ∈ Hk can be written as a set of k disjoint intervals I = {I1, · · · , Ik} on the real line i.e. for 1 ≤ j ≤ k, Ij = [a, b] where 0 ≤ a ≤ b and
hI (x) =
{ 1 if x ∈ ⋃ j Ij
0 o.w. (10)
Now, we look at the algorithms to learn the concepts from C andH that minimize the train error. Both of the algorithms will use a majority vote to determine the correct (de-noised) label for each interval, which will be necessary to minimize the test error. The intuition is that if we draw a sufficiently large
number of samples, then the majority of samples on each interval will have the correct label with a high probability.
Lemma 3 proves that there exists an algorithm A such that A draws m = O ( |ζ|2 (1−η)
(1−2η)2 log |ζ| δ ) samples from the noisy oracle EXη (Ds,ζ) and with probability 1− δ where the probability is over the randomization in the oracle, returns f ∈ C such thatR(f ;DS,ζ) = 0 andRAdv,γ(f ;DS,ζ) = 0 for all γ < 14 . As Lemma 3 states, the algorithm involves gaussian elimination over |ζ| variables and |ζ| majority votes (one in each interval) involving a total of m samples. Thus the algorithm runs in O (poly (m) + poly (|ζ|)) time. Replacing the complexity of m and the fact that |ζ| = O (n), the complexity of the algorithm is O ( poly ( n, 11−2η , 1 δ )) .
Lemma 4 proves that there exists an algorithm Ã such that Ã draws
m > max { 2 |ζ|2 log 2 |ζ|
δ
( 8
(1− η) (1− 2η)2 + 1
) ,
0.1 |ζ| ηγ2 log ( 0.1 |ζ| γδ )} samples and returns h ∈ H such that h has 0 training error, 0 test error and an adversarial test error of atleast 0.1. We can replace |ζ| = O (n) to get the required bound on m in the theorem. The algorithm to construct h visits every point atmost twice - once during the construction of the intervals using majority voting, and once while accommodating for the mislabelled points. Replacing the complexity of m, the complexity of the algorithm is O ( poly ( n, 11−2η , 1 γ , 1 δ )) . This completes the proof.
Lemma 3 (Parity Concept Class). There exists a learning algorithm A such that given access to the noisy example oracle EXη (DS,ζ), A makes m = O ( |ζ|2 (1−η) (1−2η)2 log |ζ| δ ) calls to the oracle and returns a hypothesis f ∈ C such that with probability 1− δ, we have thatR(f ;DS,ζ) = 0 and RAdv,γ(f ;DS,ζ) = 0 for all γ < 14 .
Proof. The algorithm A works as follows. It makes m calls to the oracle EX (Dms ) to obtain a set of points {(x1, y1) , · · · , (xm, ym)} where m ≥ 2 |ζ|2 log 2|ζ|δ ( 8 (1−η) (1−2η)2 + 1 ) . Then, it replaces each xi with [xi] ([·] rounds a decimal to the nearest integer) and then removes duplicate xis by preserving the most frequent label yi associated with each xi. For example, if S5 = {(2.8, 1) , (2.9, 0) , (3.1, 1) , (3.2, 1) , (3.9, 0)} then after this operation, we will have {(3, 1) , (4, 0)}.
As m ≥ 2 |ζ|2 log 2|ζ|δ ( 8 (1−η) (1−2η)2 + 1 ) , using δ2 = δ2 and k = 8(1−η) (1−2η)2 log 2|ζ| δ in Lemma 5 guarantees that with probability 1− δ2 , each interval will have atleast 8(1−η) (1−2η)2 log 2|ζ| δ samples.
Then for any specific interval, using δ1 = 2|ζ| δ in Lemma 6 guarantees that with probability atleast 1− 2|ζ|δ , the majority vote for the label in that interval will succeed in returning the de-noised label. Applying a union bound over all |ζ| intervals, will guarantee that with probability atleast 1− δ, the majority label of every interval will be the denoised label.
Now, the problem reduces to solving a parity problem on this reduced dataset of |ζ| points (after denoising, all points in that interval can be reduced to the integer in the interval and the denoised label). We know that there exists a polynomial algorithm using Gaussian Elimination that finds a consistent hypothesis for this problem. We have already guaranteed that there is a point in Sm from every interval in the support of DS,ζ . Further, f is consistent on Sm and f is constant in each of these intervals by design. Thus, with probability atleast 1− δ we have thatR(f ;DS,ζ) = 0.
By construction, f makes a constant prediction on each interval ( j − 12 , j + 1 2 ) for all j ∈ ζ. Thus, for any perturbation radius γ < 14 the adversarial risk RAdv,DS,′ζ (f) = 0. Combining everything, we have shown that there is an algorithm that makes 2 |ζ|2 log 2|ζ|δ ( 8 (1−η) (1−2η)2 + 1 ) calls to the
EX ( DηS,ζ ) oracle, runs in time polynomial in |ζ| , 11−2η , 1 δ to return f ∈ C such thatR(f ;DS,ζ) = 0 andRAdv,γ(f ;DS,ζ) = 0 for γ < 14 .
Lemma 4 (Union of Interval Concept Class). There exists a learning algorithm Ã such that given access to a noisy example oracle makes m = O ( |ζ|2 (1−η)
(1−2η)2 log |ζ| δ
) calls to the oracle and returns
a hypothesis h ∈ H such that training error is 0 and with probability 1− δ,R(f ;DS,ζ) = 0. Further for any h ∈ H that has zero training error on m′ samples drawn from EXη (DS,ζ) for m′ > |ζ|10ηγ2 log |ζ| 10γδ and η ∈ ( 0, 12 ) thenRAdv,γ(f ;DS,ζ) ≥ 0.1 for all γ > 0.
Proof of Lemma 4. The first part of the algorithm works similarly to Lemma 3. The algorithm Ã makes m calls to the oracle EX (Dms ) to obtain a set of points Sm = {(x1, y1) , · · · , (xm, ym)} where m ≥ 2 |ζ|2 log 2|ζ|δ ( 8 (1−η) (1−2η)2 + 1 ) . Ã computes h ∈ H as follows. To begin, let the list of intervals in h be I andMz = {} Then do the following for every (x, y) ∈ Sm.
1. let z := [x],
2. Let Nz ⊆ Sm be the set of all (x, y) ∈ Sm such that |x− z| < 0.5. 3. Compute the majority label ỹ of Nz . 4. Add all (x, y) ∈ Nz such that y 6= ỹ toMz 5. If ỹ = 1, then add the interval (z − 0.5, z + 0.5) to I . 6. Remove all elements of Nz from Sm i.e. Sm := Sm \ Nz . For reasons similar to Lemma 3, as m ≥ 2 |ζ|2 log 2|ζ|δ ( 8 (1−η) (1−2η)2 + 1 ) , Lemma 5 guarantees that with probability 1− δ2 , each interval will have atleast 8(1−η) (1−2η)2 log 2|ζ| δ samples. Then for any specific interval, Lemma 6 guarantees that with probability atleast 1− 2|ζ|δ , the majority vote for the label in that interval will succeed in returning the de-noised label. Applying a union bound over all intervals, will guarantee that with probability atleast 1 − δ, the majority label of every interval will be the denoised label. As each interval inζ has atleast one point, all the intervals in ζ with label 1 will be included in I with probability 1− δ. Thus,R(h;DS,ζ) = 0. Now, for all (x, y) ∈ Mz , add the interval [x] to I if y = 1. If y = 0 then x must lie a interval (a, b) ∈ I . Replace that interval as follows I := I \ (a, b) ∪ {(a, x), (x, b)}. As only a finite number of sets with Lebesgue measure of 0 were added or deleted from I , the net test error of h doesn’t change and is still 0 i.e. R(h;DS,ζ) = 0 For the second part, we will invoke Theorem 1. To avoid confusion in notation, we will use Γ instead of ζ to refer to the sets in Theorem 1 and reserve ζ for the support of interval of DS,ζ . Let Γ be any set of disjoint intervals of width γ2 such that |Γ| = 0.1|ζ| γ . This is always possible as the total width of all intervals in Γ is 0.1|ζ|γ γ 2 = 0.1 |ζ| 2 which is less than the total width of the support |ζ| 2 . c1, c2 from Eq. (3) is
c1 = PDS,ζ [Γ] = 2 ∗ 0.1 |ζ|
2 |ζ| = 0.1, c2 =
2γ
2 |ζ| |ζ| = γ
Thus, if h has an error of zero on a set of m′ examples drawn from EXη (DS,ζ) where m′ > 0.1|ζ| ηγ2 log ( 0.1|ζ| γδ ) , then by Theorem 1,RAdv,γ(h;DS,ζ) > 0.1.
Combining the two parts for
m > max { 2 |ζ|2 log 2 |ζ|
δ
( 8
(1− η) (1− 2η)2 + 1
) ,
0.1 |ζ| ηγ2 log ( 0.1 |ζ| γδ )} it is possible to obtain h ∈ H such that h has zero training error, R(DS,ζ ;h) = 0 and RAdv,γ(h;DS,ζ) > 0.1 for any γ > 0.
Lemma 5. Given k ∈ Z+ and a distribution DS,ζ , for any δ2 > 0 if m > 2 |ζ|2 k + 2 |ζ|2 log |ζ|δ2 samples are drawn from EX (DS,ζ) then with probability atleast 1− δ2 there are atleast k samples in each interval ( j − 14 , j + 1 4 ) for all j ∈ ζ.
Proof of Lemma 5. We will repeat the following procedure |ζ| times once for each interval in ζ and show that with probability δ|ζ| the j th run will result in atleast k samples in the jth interval.
Corresponding to each interval in ζ, we will sample atleast m′ samples where m′ = 2 |ζ| k + 2 |ζ| log |ζ|δ2 . If z j i is the random variable that is 1 when the i
th sample belongs to the jth interval, then jth interval has atleast k points out of the m′ points sampled for that interval with probability less than δ2|ζ| .
P [∑ i zji ≤ k ] = P [∑ i zji ≤ (1− δ)µ ] δ = 1− k µ , µ = E [∑ i zji ]
≤ exp ( − (
1− k µ
)2 µ
2
) By Chernoff’s inequality
≤ exp ( − ( m′
2 |ζ| − k + k 2 |ζ| 2m′
)) µ = m′
|ζ| ≤ exp ( k − m ′
2 |ζ| ) ≤ δ2 |ζ|
where the last step follows from m′ > 2 |ζ| k + 2 |ζ| log |ζ|δ2 . With probability atleast δ |ζ| , every interval will have atleast k samples. Finally, an union bound over each interval gives the desired result. As we repeat the process for all |ζ| intervals, the total number of samples drawn will be atleast |ζ|m′ = 2 |ζ|2 k + 2 |ζ|2 log |ζ|δ2 .
Lemma 6 (Majority Vote). For a given y ∈ {0, 1}, let S = {s1, · · · , sm} be a set of size m where each element is y with probability 1 − η and 1 − y otherwise. If m > 8(1−η)
(1−2η)2 log 1 δ1 then with probability atleast 1− δ1 the majority of S is y.
Proof of Lemma 6. Without loss of generality let y = 1. For the majority to be 1 we need to show that there are more than m2 “1”s in S i.e. we need to show that the following probability is less than δ1.
P [∑
si < m1 2
] = P [∑ si <
m1 2µ ∗ µ+ µ− µ
] µ = E [∑ si ] = P [∑ si < ( 1− ( 1− m1
2µ
)) µ ] ≤ exp ( − (1− 2η) 2
8 (1− η)2 µ
) By Chernoff’s Inequality
= exp ( − (1− 2η) 2
8 (1− η) m
) ∵ µ = (1− η)m
≤ δ1 ∵ m > 8 (1− η) (1− 2η)2 log 1 δ1

heading: C ADDITIONAL EXPERIMENTS

heading: C.1 ROBUST TRAINING IGNORES RARER SUB-POPULATIONS (SYNTHETIC SETTING)
text: This phenomenon is demonstrated more clearly in a simpler distribution for different NN configurations in Figure 7. We create a binary classification problem on R2. The data is uniformly supported
on non-overlapping circles of varying radiuses. All points in one circle have the same label i.e. it is either blue or red depending on the color of the circle. We train a shallow network with 2 layers and 1000 neurons in each layer (Shallow-Wide NN) and a deep network with 4 layers and 100 neurons in each layer using cross entropy loss and SGD. The background color shows the decision region of the learnt neural network. Figure 7 shows that the adversarially trained (AT) models ignore the smaller circles (i.e. rare sub-populations) and tries to get a larger margin around the circles it does classify correctly whereas the naturally trained (NAT) models correctly predicts every circle but ends up with very small margin around a lot of circles.

heading: C.2 COMPLEXITY OF DECISION BOUNDARIES
text: When neural networks are trained they create classifiers whose decisions boundaries are much simpler than they need to be for being adversarially robust. A few recent papers (Nakkiran, 2019; Schmidt et al., 2018) have discussed that robustness might require more complex classifiers. In Theorem 2 and 3 we discussed this theoretically and also why this might not violate the traditional wisdom of Occam’s Razor. In particular, complex decision boundaries does not necessarily mean more complex classifiers in statistical notions of complexity like VC dimension. In this section, we show through a simple experiment how the decision boundaries of neural networks are not “complex” enough to provide large enough margins and are thus adversarially much more vulnerable than is possible.
We train three different neural networks with ReLU activations, a shallow network (Shallow NN) with 2 layers and 100 neurons in each layer, a shallow network with 2 layers and 1000 neurons in each layer (Shallow-Wide NN), and a deep network with 4 layers and 100 neurons in each layer. We train them for 200 epochs on a binary classification problem as constructed in Figure 8. The distribution is supported on blobs and the color of each blob represent its label. On the right side, we have the decision boundary of a large margin classifier, which is simulated using a 1-nearest neighbour.
From Figure 8, it is evident that the decision boundaries of neural networks trained with standard optimizers have far simpler decision boundaries than is needed to be robust (eg. the 1- nearest neighbour is much more robust than the neural networks.)

heading: C.3 ACCOUNTING FOR FINE GRAINED SUB-POPULATIONS LEADS TO BETTER ROBUSTNESS
text: One way to evaluate whether more meaningful representations lead to better robust accuracy is to use training data with more fine-grained labels (e.g. subclasses of a class); for example, one would expect that if different breeds of dogs are labelled differently the network will learn features that are relevant to that extra information. We show both using synthetic data, CIFAR100 (Krizhevsky & Hinton, 2009), and Restricted Imagenet (Tsipras et al., 2019) that training on fine-grained labels does increase robust accuracy.
We hypothesize that learning more meaningful representations by accounting for fine-grained subpopulations within each class may lead to better robustness. We use the theoretical setup presented in Appendix A and Figure 6b. However, if each of the circles belonged to a separate class then the decision boundary would have to be necessarily more complex as it needs to, now, separate the balls that were previously within the same class. We test this hypothesis with two experiments. First, we test it on the the distribution defined in Theorem 3 where for each ball with label 1, we assign it a different label (say α1, · · · , αk) and similarly for balls with label 0, we assign it a different label (β1, · · · , βk). Now, we solve a multi-class classification problem for 2k classes with a deep neural network and then later aggregate the results by reporting all αis as 1 and all βis as 0.The resulting decision boundary is drawn in Figure 9a along with the decision boundary for natural training and AT. Clearly, the decision boundary for AT is the most complex and has the highest margin (and robustness) followed by the multi-class model and then the naturally trained model.
Second, we also repeat the experiment with CIFAR-100. We train a ResNet50 (He et al., 2016) on the fine labels of CIFAR100 and then aggregate the fine labels corresponding to a coarse label by summing up the logits. We call this model the Fine2Coarse model and compare the adversarial risk of this network to a ResNet-50 trained directly on the coarse labels. Note that the model is end-to-end differentiable as the only addition is a layer to aggregate the logits corresponding to the fine classes pertaining to each coarse class. Thus PGD adversarial attacks can be applied out of the box. Figure 9b shows that for all perturbation budgets, Fine2Coarse has smaller adversarial risk than the naturally trained model.
We also repeat the experiment with Restricted Imagenet (Tsipras et al., 2019) where we obtain the fine and coarse class as mentioned in Table 2. There are 60 fine classes and 10 coarse classes with each coarse class having 6 distinct fine classes in them. The train set size is 77237 and the test set size is 3000. The fine classes within each coarse are balanced i.e. given a coarse class all the fine classes in it are equally represented in this dataset.

heading: D EXPERIMENTAL DETAILS
text: In this section, we will discuss details about the experiments and model architectures used to help make sure that the experiments are reproducible.

heading: D.1 MODEL ARCHITECTURES IN SECTION 3.1
text: The model architecture used for MNIST experiments has four convolutional layers, followed by two fully connected layers. The first four convolutional layers have 32, 64, 128, 256 output filters
and 3, 4, 3, 3 sized kernels respectively. This is followed by a fully connected layers with a hidden dimension of 1024. The network is optimized with SGD with a batch size of 128, learning rate of 0.1 for 60 epochs and learning rate is decreased to 0.01 after 50epochs.
For experiments on CIFAR we use standard VGG19, ResNet18 and DenseNet architectures and training procedures.

heading: D.2 DETAILS ON EXPERIMENTS ON MEMORIZATION AND INFLUENCE
text: For a given dataset S , training algorithmA, Zhang & Feldman (2020) measure the label memorization by A on S using two related quantities of memorization and influence. For a training example (xi, yi) ∈ S and a test example (x′j , y′j), the two quantities are a special case of measuring the influence of (xi, yi) on the expected accuracy at some example z = (x, y). Influence on test example
measures the impact of (x′j , y ′ j) on the expected accuracy of (x ′ j , y ′ j). Memorization corresponds to the influence of example (xi, yi) on the accuracy on itself (or self-influence).
Memorization or Self-Influence: Self influence of an example with respect to an algorithm (model, optimizer etc) can be defined as how unlikely it is for the model learnt by that algorithm to be correct on an example if it had not seen that example during training compared to if it had seen the example during training. It can be formalized as followed which is borrowed from Eq (1) in Zhang & Feldman (2020)
Memorization by A on example (xi, yi) ∈ S is defined as
mem(A,S, i) := Ph←A(S)[h(xi) = yi]− Ph←A(S\i)[h(xi) = yi]
where S\i denotes the dataset S with (xi, yi) removed, h ← A(S) denotes the model h obtained by training using algorithm A (which includes the model architecture) on the dataset S and the probability is taken over the randomization inherent in the training algorithm A.
Influence of a training sample: Intuitively, it measures the probability that a certain test example would be classified correctly if the model were learned using a training set that did not contain the training point compared to if the training set did contain that particular training point. This can be defined as follows which is borrowed from Eq 2 in Zhang & Feldman (2020). Using a similar notation as memorization the influence of (xi, yi) on (x′j , y ′ j) can be measured as
infl(A,S, (xi, yi), (x′j , y′j)) := Ph←A(S)[h(x′j) = y′j ]− Ph←A(S\i)[h(x′j) = y′j ]
We found the images in Figure 4 by manually searching for each test image, the training image that is misclassified and is visually close to it. Our search space was shortened with the help of the influence scores each training image has on the classification of a test image. We searched in the set of top-10 most influential mis-classified train images for each mis-classified test image. The model used for Figure 4 is a AT model for CIFAR10 with `2-adversary with an = 0.25 and a model trained with TRADES for MNIST with λ = 16 and = 0.3. Zhang & Feldman (2020) had provided us the with the memorization scores for each image in CIFAR10 as well as the influence score of each training image on each test image for each class in CIFAR-10. High Influence pairs of Imagenet were obtained from https://pluskid.github.io/influence-memorization/. This was used to obtain the figures for Imagenet in Figure 4.

Review summaries:
The main contribution of the paper is to study the connection between adversarial robustness, on the one hand, and label noise & data representation on the other hand. Here, an algorithm is said to be robust if for every training example xi with label yi, one cannot find an instance x within a small distance of xi that is assigned a different label from yi by the model. This is a standard definition of robustness in the literature. 

The goal of the paper is to investigate both theoretically and empirically the reasons of vulnerability of overparameterized classifiers obtained by the so called “benign overfitting”. More precisely, two causes of adversarial vulnerability are underlined: label noise memorization and sub-optimal representation learning. The first theorem of the paper shows that for some data generating distributions, even a small fraction of label noise leads to an adversarial prediction risk bounded away from zero for any classifier having zero training error and for any sufficiently large sample size. The second theorem shows that in the presence of label noise the choice of the overparameterized family (the representation) is very important. Namely, while for a good representation one may have “training error = test error = adversarial error = 0”, for another representation it holds that “training error = test error = 0” but “adversarial error > 0.1”. This theoretical results are illustrated by extensive experimental results. 

The generalization ability of networks with zero training error has been heavily studied.  This paper extends beyond generalization to test sets to study the network's robustness to adversarial examples.  The paper provides two theoretical contributions demonstrating that a very low training error can indicate poor robustness under reasonable conditions.  They illustrate this with experiments using label noise, demonstrating that adversarially robust networks spurn overfitting on incorrectly labelled data.  They additionally experimentally demonstrate that unusual training examples, even if correctly labelled, are unlikely to be correctly predicted by adversarially robust networks.