How Benign is Benign Overfitting ?
Authors: Amartya Sanyal
Puneet K. Dokania
Varun Kanade
Philip Torr
Venue: ICLR 2021 Spotlight (2021)
Keywords: benign overfitting
adversarial robustness
memorization
generalization

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.

Published as a conference paper at ICLR 2021
HOW BENIGN IS BENIGN OVERFITTING?
Amartya Sanyal
Varun Kanade
Department of Computer Science, University of Oxford,
Department of Computer Science
University of Oxford,
Oxford, UK
Oxford, UK
The Alan Turing Institute, London, UK amartya. sanyal@cs. ox. ac uk
The Alan Turing Institute, London, UK varunkêcs ox. ac.
Puneet K.Dokania
Philip H.S. Torr
Department of Engineering Science University of Oxford, Oxford, UK
Department of Engineering Science University of Oxford, Oxford, UK phst @robots ox. ac uk
Five AI Limited
puneet t @ robots. ox. ac.uk uk
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 benign overfitting (Bartlett al., 2020) Chatterji & Long 2020). However, these models are vulnerable to adversarial attacks. We identity 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 '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.
INTRODUCTION
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. 22044] Biggio & Roli 2018 Goodfellow et al. (014)) This vulnerability poses serious security concerns when these models are deployed in real-world tasks (cf. (Papernot et al. 2017] Schönherr 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 (c.g. (Goodfellow al., 2014, Papernot et al. 2015; Tramer et al., 2018 Madry et al., 2018 Zhang et al. (019)). However, such defences have usually been broken by future attacks (Athalye et al. 22088; Tramer jet al.) 2020), This arms race between attacks and defenses suggests that to create truly robust model would require a deeper understanding of the source of this vulnerability.
Our goal in this paper not to propose new defenses, but to provide better answers to the question: what causes adversarial vulnerability? In doing so, 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, 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. (2066) 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 al. 2018h Hastie et al. 2019

---

Published as a conference paper at ICLR 2021
truck
plane
deer
truck
dog
bird
9
5
4
9
5
4
4
3
7
1
6 (
CIFARIO
MNIST
Figure 1: Label noise in CIFARIO and MNIST. Text above the image indicates the training set label.
Belkin et al. 2019a b. Bartlett et al. 2020, Muthukuma et al. 2020 Chatterji & Long 2020)) has also sought explain why fitting training data perfectly does not lead 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
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 least some of the noisy examples,bur but also on atypical examples from the classes (Zhang & Feldman 2020). Viewed differently, robust training methods unable 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 for slight drops in test accuracy, as the test set often contains similarly atypical (or even identical) examples in some cases Feldman (219)) Zhang Feldman (2020). We point this phenomenon for robust models through visual examples on MNIST, CIFARIO, and Imagenet (c.f. Figure 4.
an explanation
2019) and Zhang al. (2019) have argued that the trade-off between robustness and accuracy might be unavoidable. How- ever, their setting involves 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 well-separated at least in some representation space. fact, Yang et al. (2020) show that classes already well- sepaaaepa in the input space. In such situations, there is need for robustness to 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
Representation Learning and Robustness:
Recent works (Tsipras
trade-off may exist or can avoided. Recent empirical work (Sanyal et al.) 2020a Mao et al.) 2020) has also established that modifying the training objective 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, has been suggested in recent works that adversarially robust learning may require more "complex" decision boundaries, and as result may require more data (Shah et al., Schmidt al.,,220 2018 Yin et al.) 20199) Nakkiran 2019 Madry al. 2018). However, the question of decision boundaries in neural networks is subtle as the network learns a feature representation well 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.
Summary of Theoretical Contributions
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 representation, it is possible
2

---

Published as a conference paper at ICLR 2021
to have high natural and robust test accuracies but at the cost of having training error; (ii) using another representation, it 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 loss of robust accuracy.
Summary of Experimental Contributions
1. As predicted theoretically, neural nets trained to convergence with label noise have greater adversarial vulnerability. (See Section P.Ip.
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 ena-ina labels, subelasses within each class, leads to higher robust accuracy. (Due to lack of space we moved this to Appendix C.3
While primary contribution is showing the effect of overfitting label noise on adversarial bustness, we hope our theoretical and experimental evidences on the importance of representation learning for robustness will inspire further research in this direction.
THEORETICAL SETTING
We develop simple theoretical framework demonstrate how overfitting, even very minimal, label noise causes significant adversarial vulnerability. We also show in Theorem@land3 Soow how the choice of representation significantly affect robust accuracy. Although 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) E IR {0, 1) and any binary classifier f Rdd {0, 1}.
* the natural error is
R(J:D) P( [f (x) + y),
By (x) is a ball of radius 2 0 around x under some norm the 7-adversarial enror is
RAdv,, (f: P (xx,))>> Ez E By (x) (z) y).
In the rest of the section, provide theoretical results show the effect of overfitting label noise on the robustness of classifiers.
2.1 OVERFITTING LABEL NOISE
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 D states that if the data distribution has significant probability mass 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 vuinerable to adversarial attacks to classifiers that fit the training data perfectly.
Theorem 1. Let e be the target classifier, and let D be distribution over (x, y), such that = e (x) in its support. Using the notation P A] to denote P P(xxa)/D[x A] for any measurable subset
C gd, suppose that there exist Ci Z C2 > 0, p > O, and a finite set C Rdd satisfying
Po
U
1 (8)
2 and vs E IP
B
(3)
Throuuhout, will mostly the (most commonly used) foc norm, but the results hold for other
3

---

Published as a conference paper at ICLR 2021
0
D.S
0.01
0.00
9.
Tosa Text
Trckk Tock
Than Tral
Text
Tox
Text
A4
51
13
23
Cr 14
n (Sbcl noise)
/Jabel noiso)
(bbe noical
(a) Toy- MNIST
(b) Full-MNIST
2.021
0:004
0.001
0.004
004
ADt
Text
(c) ResNet18 (CIFARIO)
(d) DenseNet121 (CIFARIO)
(e) VGG19 (CIFARIO)
Figure 2: Adversarial Error increases with increasing label noise 7). Shaded region indicates 95%
confidence interval. Absence of shaded region indicates that it is invisible due to low variance.
where B% (s) represents Ey-ball of radius p around S. Further, suppose that each of these balls contain points from a single class i.e. for all s for all x, B% (s) c(x) cz)).
Let Sm be dataset of m i.i.d. samples drawn D, which subsequently has each label flipped independently with probability n. For any classifier f that perfectly fits the training data S..
i.e. V x, E Sm. f fx) y. wō > 0 and m 2 [cl log (14)). with probability at least 1 8, R2
1722
20 (f:D)= 2 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 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 p. with the classes being well-separated satisfies Eq. 33. The main idea of the proof is that there is sufficient probability mass for points which are within distance 2p 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 For instance, one could construct the classifier h, where h(x) = c(x), if (x, 6) & Sm for b = 0, 1, and h(x) y (x, y) E Sm.. Note that the classifier h agrees with the target e on every point of Rd except the mislabelled training examples, and result these examples are the only source of vulnerability. The complete proof is presented in Appendix B.I
There are few things note about Theorem 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 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 [c] 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 is concentrated around some points then for fixed C1, C22 a smaller value of would be required to satisfy (3) and thus a weaker adversary (smaller perturbation budget 2p) 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 [.T]s how label noise causes vulnerability in a toy MNIST model, the full MNIST and CIFARIO for a variety of architectures.
3 EXPERIMENTS ON OVERFITTING LABEL NOISE
In Section 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).
4

---

Published as a conference paper at ICLR 2021
Iter 0 Test Acc:51.3
Iter 20
Iter 120 Test Acc:86.3
Iter 160 Test Acc:85.9
Test Acc:96.6
Natural
Label
True 1; Label
Mislabelled
True 0; Label
Label
Adverserial
True 1: Pred
Figure 3: Two dimensional PCA projections of the original correctly labelled (blue and orange), original mis-labelled (green and red), and adversarial examples (purple and brown) at different stages of training. The correct label for True (blue), Noisy (green), Adv (purple +) are the same i.e. and similar for the other class.
and on a lesser scale Imagenet to support the theory. Further details about the experimental settings including model architectures in Appendix D
3.1 OVERFITTING LABEL NOISE DECREASES ADVERSARIAL ACCURACY
We design a simple binary classification problem, toy-MNIST, and show that when fitting a complex classifier training dataset with label noise, adversarial vulnerability increases with the amount of label noise, and that this vulnerability caused by the label noise. The problem 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.idd. Gaussian noise sampled from N (0, o²). We create a training dataset of 4000 samples by sampling uniformly from either class. Finally, fraction of the training data chosen randomly and its labels are flipped. We train a neural network with four fully connected layers followed by 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 PGD adversary (Madry al. 2018) with
strong loo
64 for 400 steps with step size of 0.01. 255
In Figure Za we plot the adversarial error, test error and training error as the amount of label noise (17) varies, for three different values of sample variance (a²). For low values of x² (o² 0.1), the training data from each class is all concentrated around the same point; as result these models are unable to memorize the label noise and the training error high. In this case, over-fitting label noise is impossible and the test error, as well as the adversarial error, is low. However, as 0² increases to x² 0.5, the neural network flexible enough to use the "noise component" 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 in line with Theorem
The case when o² 0.3 is particularly interesting: when the label noise 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 ervor still remains very low but adversarial error increases rapidly.
Remark 1.
We perform similar experiment on the full MNIST dataset trained on a 4-layered Convolutional Neural Network. For varying values of 7, for a uniformly randomly chosen 1) 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 l bounded PGD adversary for varying perturbation budget c, with a step size 0.01 and for 20 steps and plot the results in Figure 2b We repeat the same experiment for CIFAR 1 with a DenseNet121 (Huang et al., 2017), ResNetT8 (He) ct al., 2016), and VGG19 (Simonyan an & Zisserman 2014) to test the phenomenon across multiple state of the art architectures and plot the results in Figure 2c to 2c The results on both datasets show that the effect of over- wer-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 natural test error is much slower. This confirms the hypothesis that benign overfitting may not be benign when it comes to adversarial emor.
5

---

Published as a conference paper at ICLR 2021
6
5
S
9
4
6
6
5
3
3
4
8
4
4
9
2 2 7
8
4
8
7
CIFARIO
MNIST
ImageNet
Figure 4: Each pair is a training (left) and test (right) image mis-classified by the adversarially trained model. They were both correctly classified by the naturally-traine model.
For the toy-MNIST problem, we plot a 2-d projection (using PCA) of the learned representations (ac- tivations before the last layer) at various stages of training in Figure (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 label noise; however, the representations learned by 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 (*o""-es) of the opposite class. For example, the purple +-es (Adversarially perturbed: True: 0, Pred:1 ) are very close to the green o-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 created by moving towards that data point as predicted by Theorem [ (ii) The mis-labelled training data take longer to be fit by the classifier. For example by iteration 20, the network actually learns 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 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 al. 2020 Hendryeks al. (019a), as well as learning in the presence of label-noise (Li et al. 2019bb.. Our work provides an explanation regarding why early stopping may reduce adversarial vulnerability by avoiding fitting noisy training data.
much lower as
3.2 ROBUST TRAINING AVOIDS MEMORIZATION OF LABEL. NOISE AND ATYPICAL EXAMPI.ES
2019) commonly used techniques to increase adversarial robustness of deep neural networks. However, it has been pointed out that this comes a cost clean accuracy (Raghunathan 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 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 methods like AT (Madry et al. 2018 and TRADES (Zhang et al.
al. 2019 Tsipras et al.) 2019).
Robust training ignores label noise datasets like MNIST and CIFARIO. 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 I all examples that have wrong label in the training set, whereas natural training does. Thus, in line with Theorem robust training methods ignore fitting noisy labels.
shows that label noise is not uncommon in standard
6

---

Published as a conference paper at ICLR 2021
Mis clssiited
Naximum influcee
All
12 2 S
12
PLANES
CAR
BIRD
CAT
DEER
050
(b) Distribution of the influence of training point on all test points compared to the distribu- tion of influence test points mis-classified by adversarially trained points.
DOG
FROG
HORSE
SHIP
TRUCK
(a) Fraction of train points that have a self-influence greater than s is plotted versus s.
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 CIFARIO).
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 c = 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 sub- populations (eg. a special kind of cat) and this aob--opuaation 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 naturally trained model. As Feldman (2019) points out, if these sub- populations 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- sub-popus uub-oopulation 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, CIFARIO, and ImageNet We visually demonstrate this effect in Fig- ure with examples from CIFAR10, MNIST, and ImageNet and then provide more statistical evidence using the notions of memorization score and influence (Zhang & Feldman| (2200) in Figure 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 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, 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-popule tobb--poulatin.....
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 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 has a disproportionately higher influence on the corresponding test image compared to influences of other train-tes test image pairs in CIFARIO. A precise notion of measuring if a sample is rare is through the memorization.
concept of self-influence 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.
Self-influence for a example, that is unlike other
In Figure Sa we show that the self-influence of training samples that were classifed by adversar- ially trained models but correctly classified by naturally trained model is higher compared to the
7

---

Published as a conference paper at ICLR 2021
distribution of self-influence 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) higher on test images that mis-classified by
show that the influence of training images 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 heavily influenced by some particular training example. As we saw in Figure Sa 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 rure and thus has a particularly high influence from training image.
4 REPRESENTATION LEARNING AND ROBUSTNESS
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 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 (ef. (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 fixed permutation (Zhang et al.) 2016). This invariance worrying as means that such network can effectively classify a tensor that is visually nothing like a real image into an image category. While CNNs don't 't have this particular invariance, as Liu et al. (2018) shows, CNNs unable to predict where in the image 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 F will have good test accuracy and adversarial accuracy. On the other hand, when different ("incorrect") representation is used, find a classifier that has no training error, has good test accuracy, but has high adversarial error. We posit this least atypical examples) have good test accuracy, while still being vulnerable to adversarial attacks.
show that it is possible to
(partial) explanation of why classifiers trained on real data (with label noise, at
Theorem 2.
For any n E4, there exists family of distributions D over R. x {0, 1) and function classes C, H. such that for any P from D"d and for any O < T < 1/4, and 1J E (0, 1/2) if Sm, = {(x,, y1) 1m denotes sample of size drawn from P where
(1 (1-1) +1
m m- 0 max
12 g nloo
+1
n
log
{1 (1- 2n)
1772
70
and if Sm. denotes the sample where each label is flipped independently with probability 1).
(i) the classifier E C that minimizes the training error on Sma. has R(c;P) 0 and (e P) = =0for 0 S < 1/4.
(ii) there exist h H. h has zero training error Sm.y. and R(h; P) 0. However, for any y O. and for any E H with zero training error on Sm.m Radv, (h: P) 2 0.1.
Furthermore, the required
E C and h E H above can be computed in O (poly pnly (1))) .poly poly (t) time.
In Theorem we show similar result without the effect of label noise. In Appendix C 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.
Thiis referred the Empirical Risk Minimization (ERM) in the statistical learning theory literature.
8

---

Published as a conference paper at ICLR 2021
5 RELATED WORK
Montasser et al. 2019) established that there are concept classes with finite VC dimensions i.e. are properly PAC-leamable but are only improperly robustly PAC learnable. This implies that 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 training set induced with random classification noise and hypothesis class H obtains zero training on this noisy training set whereas the examples in Montasser et al. (219)) 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. (2119) 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.
6 CONCLUSION
Recent research has largely shone a positive light interpolation (zero training error) by highly over- wve-pprramterized 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 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.
7 ACKNOWLEDGEMENT
We thank Vitaly Feldman and Chiyuan Zhang for providing us with data that helped to signifi- cantly speed up some parts of this work. We also thank Nicholas Lord for feedback the draft. AS acknowledges support from The Alan Turing Institute under the Turing Doctoral Studentship grant TU/C/00002.. 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/NO194744 and FiveAI.

---

Published as a conference paper at ICLR 2021
REFERENCES
Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give a false sense of security: Cireumventing defenses to adversarial examples. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, July 2018. URL http://axiivv.ocoo abs/
1802. 00420
Peter I.. Bartlett, Philip M. Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, pp. 201907378, apr 2020. doi: 19tp:/paa..107378811
Mikhail Belkin, Daniel J Hsu, and Partha Mitra. Overfitting or perfect fitting? risk bounds for classifi- cation and regression rules that interpolate. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems 31, pp. 2300-2311. Curran Associates, Inc., 2018a. URL ht htt.t::/ppapee..iiis.ooo
7498 www-ooveefiiingnee or -ateag--r-peeeeeeeeee fitting risk forondo-foo-classiicccee ott.paasssffaattooooaaaereeeeooe pdf
Mikhail Belkin, Siyuan Ma, and Soumik Mandal. To understand deep learning we need to understand kernel learning. In Jennifer Dy and Andreas Krause (eds.). Proceedings of the 35th International Conference on Machine Learning. volume 80 of Proceedings of Machine Learning Research. pp. 541-549, Stockholmsmässan, Stockholm Sweden, 10-15 Jul 2018b. PMLR. http: l/proceedi ml press / vv00/bbeee kinkiinlll. ht.l
Mikhail Belkin, Daniel Hsu, and Ji Xu. Two models of double descent for weak features. arXiv:1903.07571, 2019a.
Mikhail Belkin, Alexander Rakhlin, and Alexandre B. Tsybakov. Does data interpolation contradict statistical optimality? In Kamalika Chaudhuri and Masashi Sugiyama (eds.), Proceedings of Machine Learning Research, volume 89 of Proceedings of Machine Learning Research, pp. 1611-161 16119 PMLR, 16-18 Apr 2019b. URL http::://pccceeei.iggg/n///////p
mlr www.mm..pp...weeee
bel kink 9a. html
Battista Biggio and Fabio Roli. Wild patterns. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security. ACM, jan 2018. doi: 10.1 (c.11///333744.224111
Niladri S. Chatterji and Philip M. Long. Finite-sample analysis of interpolating linear classifiers in the overparameterized regime. arXiv:2004.12111 2020.
Nilesh Dalvi, Pedro Domingos, Mausam, Sumit Sanghai, and Deepak Verma. Adversarial classifica- tion. In Proceedings of the 2004 ACM SIGKDD international conference on Knowledge discovery and data mining- KDD2004, ACM Press, 2004. doi: 10145//01402.111440000
Akshay Degwekar, Preetum Nakkiran, and Vinod Vaikuntanathan. Computational limitations in robust classification and win-win results. In Alina Beygelzimer and Daniel Hsu (eds.), Proceedings of the Thirty-Second Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pp. 994-1028, Phoenix, USA, 25-28 Jun 2019. PMLR. URL http:// proceedings mlr. press wttpeessvvv///dgweeeee 9a. html
Vitaly Feldman. Does learning require memorization? short tale about long tail. arXiv:1906.0527. 2019.
Robert Geirhos, Jömn-Henri. Jacobsen, Claudio Michaelis, Richard Zemel, Wieland Brendel, Matthias Bethge, and Felix A. Wichmann. Shortcut learning in deep neural networks.
Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and Hameessing Adversarial Examples. arXiv preprint arXiv:1412.6572 dec 2014. BRLLktt:://axxt org/ abs 1412 6572
Boris Hanin and David Rolnick. Complexity of linear regions in deep networks. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 2596-2604, Long Beach, California, USA, 09-15 Jun 2019. PMLR. URL http:tt:/pppccceeingg..... mlr Treas/v97/hant 9a. html
10

---

Published as a conference paper at ICLR 2021
Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J. Tibshirani. Surprises in high- dimensional ridgeless least squares interpolation. arXiv:1903.08560 2019.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep Residual Learning for Image Recognition. In 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 770-778. IEEE, jun 2016. ISBN 977-1-4673-885111 doi: 10.1 1..110/CVPRR2016..00. URL http: Stttp://eeese ore. eeee. (rceeorr///dcmmmme7777005555
Dan Hendrycks, Kimin Lee, and Mantas Mazeika. Using pre-training can improve model robustness and uncertainty. Proceedings the International Conference on Machine Learning, 2019a.
Dan Hendrycks, Kevin Zhao, Steven Basart, Jacob Steinhardt, and Dawn Song. Natural adversarial examples. arXiv:/907.07/74, 2019b.
Gao Huang, Zhuang Liu, Kilian Q Weinberger, and Laurens van der Maaten. Densely connected convolutional networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, volume 1, pp. 3, 2017.
Joern-Henrik Jacobsen, Jens Behrmann, Richard Zemel, and Matthias Bethge. Excessive invariance causes adversarial vulnerability. In International Conference on Learning Representations, 2019. URL.htttps://peerevveee wttp:///oorrrriiceebiaaa.ao
Sandesh Kamath, Amit Deshpande, and K Subrahmanyam. Invariance vs robustness of neural networks. 2020. URL httLhhhtss///perre. revileerreeiiee ew wtw.:m/mmmmi...0000.....
Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. Technical report, Citeseer, 2009.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278-25 1998.
Juncheng Li, Frank Schmidt, and Zico Kolter. Adversarial camera stickers: A physical camera- based attack on deep learning systems. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 3896-3904, Long Beach, California, USA, 09-15 Jun 2019a.
PMLR. URI.
m press /t9//119/..////.
Mingchen Li, Mahdi Soltanolkotabi, and Samet Oymak. Gradient descent with early stopping is provably robust to label noise for overparameterized neural networks. arXiv:/900. /680, 2019b.
Tengyuan Liang and Alexander Rakhlin. Just interpolate: Kernel "ridgeless" regression can generalize. arXiv:1808. 00387, 2018
Rosanne Liu, Joel Lehman, Piero Molino, Felipe Petroski Such, Eric Frank, Alex Sergeev, and Jason Yosinski. An intriguing failing of convolutional neural networks and the coordconv solution. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa- Bianchi, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurlPS 2018, 3-8 December 2018, Montréal, Canada, pp. 0628-96399 2018. URL 8169- 1169-an-2a an weniinnttiinnnn ooc.raaoo....aaooooooooooooooo.. www.:oooooooooooooooo wwwlllnnuraall. www.urrrl-tetwossss-aeee
nips wct paper/
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. To- wards deep learning models resistant to adversarial attacks. In International Conference on Learn-
ing Representations, 2018. htthhttt://// http::/://///eeeeeeeee// hwt.:nee/eeeeeeeee forum/rrmmmmmm wtt.:forummdddrt-f2aa..
Chengzhi Mao, Amogh Gupta, Vikram Nitin, Baishakhi Ray, Shuran Song. Junfeng Yang, and Carl Vondrick. Multitask learning strengthens adversarial robustness. 2020.
Omar Montasser, Steve Hanneke, and Nathan Srebro. Vc classes are adversarially robustly learnable, but only improperly. In Alina Beygelzimer and Daniel Hsu (eds.). Proceedings of the Thirry- Second Conference Learning Theory, volume 99 of Proceedings Machine Learning Research, pp. 2512 2530- Phoenix, USA, 25-28 Jun 2019. PMLR. URL /RL.Att:: htttp:://proceeeings. mlr preas/ v wwo 9a. html
11

---

Published as a conference paper at ICLR 2021
Vidya Muthukumar, Kailas Vodrahalli, Vignesh Subramanian, and Anant Sahai. Harmless interpola- tion of noisy data in regression. IEEE Journal on Selected Areas in Information Theory, pp. 1-1, 2020. doi:
Preetum Nakkiran. Adversarial robustness may be at odds with simplicity. arXiv preprint- arXiv:1901.00532, 2019.
Nicolas Papernot, Patrick McDaniel, Xi Wu, Somesh Jha, and Ananthram Swami. Distillation as a defense adversarial perturbations against deep neural networks. arXiv:/511.000 2015.
Nicolas Papernot, Patrick McDaniel, Ian Goodfellow, Somesh Jha, Z. Berkay Celik, and Ananthram Swami. Practical black-box attacks against machine learning. In Proceedings of the 2017 ACM on Asia Conference on Computer and Communications Security. ACM, apr 2017. doi: 10.1 10.11455/0533773335300009
Aditi Raghunathan, Sang Michael Xie, Fanny Yang, John C. Duchi, and Percy Liang. Adversarial training hurt generalization. arXiv: OrXiv:/906.000 0900096060000.. 2019.
Amartya Sanyal, Puneet Dokania, Varun Kanade, and Philip H.S. Torr. Robustness via deep low-rank representations. 2020a. MIXiv:800.00709)
Amartya Sanyal, Philip H. Torr, and Puneet K. Dokania. Stable rank normalization for improved generalization in neural networks and {gan}s. In International Conference on Learning Represen- tations, 2020b. URL http:ttttppeereeeeeeee wttp://wwww...tt..foooooooooaaaa
Ludwig Schmidt, Shibani Santurkar, Dimitris Tsipras, Kunal Talwar, and Aleksander Madry. Adver- sarially robust generalization requires more data. In Advances in Neural Information Processing Systems, pp. 5014-5026, 2018.
Lea Schönherr, Katharina Kohls, Steffen Zeiler, Thorsten Holz, and Dorothea Kolossa. Adversarial attacks against automatic speech recognition systems via psychoacoustic hiding. arXiv: 05665, 2018.
Harshay Shah, Kaustav Tamuly, Aditi Raghunathan, Prateek Jain, and Praneeth Netrapalli. The pitfalls of simplicity bias in neural networks.
Yanyao Shen and Sujay Sanghavi. Learning with bad training data via iterative trimmed loss minimization. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 5739-5748, Long Beach, California, USA, 09-15 Jun 2019. PMLR. URL m www..aaww..................m.. ptw.sp 19..hmml
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv: 1556, 2014.
Florian Tramer, Nicholas Carlini, Wieland Brendel, and Aleksander Madry. On adaptive attacks to adversarial example defenses. arXiv:2002.08347, 2020.
Florian Tramèr, Alexey Kurakin, Nicolas Papernot, Ian Goodfellow, Dan Boneh, and Patrick Mc- Daniel. Ensemble adversarial training: Attacks and defenses. In International Conference on Learn- ing Representations, 2018. URL
Dimitris Tsipras, Shibani Santurkar, Logan Engstrom, Alexander Turner, and Aleksander Madry. Ro- bustness may be odds with accuracy. In International Conference Learning Representations, 2019.
Eric Wong, Leslie Rice, and J. Zico Kolter. Fast better than free: Revisiting adversarial training. In International Conference on Learning Representations, 2020. URL /RL/ net. pett/forum21d==J00000000
Yao- Yuan Yang, Cyrus Rashtchian, Hongyang Zhang, Ruslan Salakhutdinov, and Kamalika Chaud- huri. Adversarial robustness through local lipschitzness. arXiv:2003.024660 2020.
12

---

Published as a conference paper at ICLR 2021
Dong Yin, Ramchandran Kannan, and Peter Bartlett. Rademacher complexity for adversarially robust generalization. Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.). Proceedings of the 36th International Conference Machine Learning. volume 97 of Proceedings of Machine Learning Research, pp. 7085-7094, Long Beach, California, USA, 09-15 Jun 2019. PMLR. URL http::/procceedngg ngs m1 www.srrssssee wwwps//re/sss////e / 9b. ht.ml
Chiyuan Zhang and Vitaly Feldman. What neural networks memorize and why: Discovering the long tail via influence estimation. Unpublished manuscript, 2020.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. International Conference on Learning Representations
(ICLR), nov 2016. URL http: http://rxvvv../.. org/ abs/161. 03530
Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric P. Xing, Laurent El Ghaoui, and Michael I. Jordan. Theoretically principled trade-off between robustness and accuracy. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pp. 7472-7482. PMLR, 2019. URL httlttt:pppppcceeeeiee m alr.pe p.r.ress/vv9. zhangl 9p. html
13

---

Published as a conference paper at ICLR 2021
Parity Classifier
Union of Intervals
H|
IH
H
HI IH
Parity Classifier
XXO
xOxOxxX
XOX*XOX
XXX+OXX
Linear Classifier
001
010
011
100
(a) Both Parity and Union of Interval classifier predicts red if inside any green interval and blue if outside all intervals. The x-es are correctly labelled and the c-cs are miselabelled points. Reference integer points on the line labelled in binary.
(b) Robust generalization needs more complex boundaries
Figure 6: Visualization of the distribution and classifiers used in the Proof of Theorem 2 and Red and Blue indicate the two classes.
3 The
A REPRESENTATION LEARNING AND ADVERSARIAL ROBUSTNESS
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 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
Theorem 3. For some universal constant e, and any 0 < 770 < 1/V2, there exists family of distributions D defined on X x {0, where X C R22 such that for all distributions E D, and denoting by Sm = {{x1, ((x1,81), ... (Xm: bm)) } a sample of size m drawn i..dd from P,
(i) For any m 2 0, Sm is linearly separable i.e., V(x,, y:) E Sm. there exist w R², wg E R. s.s. wo) 0. Furthermore, for every 7 "oo, any linear separator f that perfectly fits
Yi (w" the training data Sm has (f:v. 2 0.0005, even though R(f:P) + 0 as m + co.
(ii) There exists a function class H such that for some m E (log(6 ())) any E H that perfectly fas the Sm, satisfies with probability at least 8, R(;; P) and RAdv, (h; P) 0, for any E [0, 70 1/8].
complete proof of this result appears in Appendix B.2 but first, we provide a sketch of the key idea here.The The distributions in family will be supported on balls of radius at most 1/v2 on the integer lattice in R The true class label for any point x is provided by the parity of 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. distribution only supported on balls centered the points (a, a) and (a, a + 1) for some integer a (See Figure Visually learning the classification problem using the parity of a results in 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, is worth noting that this complexity is not rooted in any statistical theory, e.g. the VC dimension of the classes considered in Theorem essentially the same (even lower for H by 1). This visual complexity arises purely due to the fact that the linear classifier looks geometric representation of the data whereas the parity classifier looks at the binary representation of the sum the nearest integer of the coordinates. 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.
REPRESENTATION LEARNING IN THE PRESENCE OF LABEL NOISE
Here we restate Theorem 2 and present proof sketch for the result.
Theorem 2. For any n E Z4. there exists a family of distributions D over R x {0, 1) and function classes C, H. such that for any P from D", and for any 0 < 1/4, and 17 (0, 1/2) if
14

---

Published as a conference paper at ICLR 2021
S.. 31) denotes sample of size drawn from P where
(1 (1-1) +
m == max nog Th
n
log
δ (1- 2n) (1-2n)
1772
70
and if Sm. denotes the sample where each label is flipped independently with probability
(i) the classifier RAdv, (F; P)= = 0. 0 S < 1/44
C that minimizes the training error Sma. has R(c;P) -0 and
(i)) there exist E H. h has zero training error on Sm.y. and Rh; P) =. However, for any 7 > 0, and for any H with zero training error Sma. RAdv, (h; P) 0.1. Furthermore, the required
E C and h E H above can be computed in ) ppoly poly (t) time.
O (poly poly
We sketch the proof here and present the complete the proof in Appendix B.3 in Appendix we will make use of parity functions, though the key point is the representations used. Let = [0, N.. intervals (i 1/4, 1/4) for
where N 2n, consider distributions that supported i E {1..... - }} (See Figure 6a). but any such distribution will only have small number, (n)). intervals which it supported. The true class label is given by function that depends on the parity of some hidden subsets S of bits in the bit-representation of the closest integer i, c.g. as in Figure 6a if S {0, 2). then only the least significant and the third least significant bit of are examined and the class label is 1 if an odd number of them are and ( 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 is also possible to learn the function as a union of intervals, i.e. find intervals, I J2...... Jx such that any point that lies in one of these intervals is given the label 1 and any other point given the label By choosing intervals carcfully, it is possible to fit all the training data, including noisy examples, but yet not compromise vulnerable to adversarial examples by applying Theorem | classifier such as union of intervals (H in Theorem 2) is translation- -nvarriat,,, 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.
accuracy (Fig. 6a). Such classifier, however, will be
B PROOFS FOR SECTION 2
In this section, we present the formal proofs to the theorems stated in Section 2
B. PROOP OF THEOREM 1
Theorem 1. Let be the target classifier, and let D be distribution over (x, y), such that y c (x) in its support. Using the notation PP AA] to denote F(x,))D(Xx E A] for any measurable subset A C Rd. suppose that there exist e₁
C2 0, p O, and finite set Rd satisfying
Po
U 13
2 ci and
vs E S. PD BP
C2 [
(3)
SEC
where B. (s) represents ba-ball of radius p around s. Further, suppose that each of these balls contain points from a single class i.e. for all s e for all x, (s) cxx) = c (z).
Let Sm be dataset of m i.i.d. samples drawn from D, which subsequently has each label flipped independently with probability n, For any classifier f that perfectly fits the training data Sm
i.e. x, y E Sm, fxx) = y, wō > and m 2 1cl log (L) with probability at least RAdv.20 (J; 4
noz
Proof of Theorem
From 3.. for any ( and E C.
P ((x,))<D [x E B, (s)] 2
15

---

Published as a conference paper at ICLR 2021
As the sampling of the point and the injection of label noise are independent events,
22
P(x,)) (x E Bp (s) A x gets mislabelled]
K<l
Thus,
C27
Pmmmm (x, Sm x Bp (s) is mislabelled]
2 1
1
[<]
-227mm
2 1 exp
[4]
Substituting m
15 log [5] and applying the union bound over all E Ç. we get
PS Ns E S, 3 (x, y) E Sm x E B, (8) A x is mislabelled] 2 1
(4)
As for all s Rd and Vx, 2, E Bg (s), ||x z|lp 2p, have that
(A:i) Pmm.DD Dm P ((xx))D [2 E Bap (x)
A Λr + (z)]
2 Pm Dm
P (xxy)~D
X U 1 p
(s) {3z E B20 (x) f())
SEc
Psm Dn
[(xx)>> 3s E (: x: B% (s) E (x) (x) [z))]]
P PSmm Dm
P P(x.)>~
Es E x::x E B (8) A 22
Ps Dm
(xxy)>D
Is E ( x E B (s) (s) + (z))]
(x.))>D
x E U 1 (s)
w.p. atleast 1
C1
w.p.
1- 5
where is the true concept for the distribution D. Equality (1) follows from the fact that the event
x E Usec By (s) is equivalent to the event that there exists an i E {1,-., I.I} such that x E B% (s;). Equality (2) follows from the assumptions that each of the balls around E Ç are pure in their labels. Equality (3) follows from by using the x that is guaranteed exist in the ball around and be mis-labelled with probability atleast 1 - 5. To see how, replace the x in Assumption with z. The last equality follows from the first Assumption in
B.2 PROOFS OF APPENDIX
Theorem 3. For some universal constant c, and any < 7o 1/12, there exists family of distributions 'D defined on X x 1) where X C I22 such that for all distributions P E D, and denoting by Sm {[x1, y1) ..., (Xm: }m)} a sample of size m drawn ii.d from P.
(i) For any m 2 0, Sm is linearly separable i.e., v(x,, y1) E Sms there exist w E R², wo E R s.s. Vi (wTx, x; + wo) 2 Furthermore, for every 7 > "/o- any linear separator that perfectly fis the training data Sm has Radva Z 0.0005, even though R(f:P)
as m - oc.
(ii) There exists function class H such that for some
O(log(8-1)) 1), any h H that perfectly fits the Sm, satisfies with probability at least - 8, R(h; P) and R (h; P) = 0, for any 7. [0, 70 1/8).
Proof of Theorem 3 We define a family of distribution D, such that each distribution D is sup- ported balls of radius around (i, and (i + 1) 3) 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 example where the colors indicate the label.
16

---

Published as a conference paper at ICLR 2021
Formally, for > O, k Z+, the (r, k)-1 bit parity class conditional model is defined over (x), y) E R2 x {0. as follows. First, a label y is sampled uniformly from {0, 13. then and integer i is sampled uniformly from the set {1.... }} and finally is generated by sampling uniformly from the f2 ball of radius r around (i + v.
In Lemma we first show that set of m points sampled iid from any distribution defined above for < 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] [ also proves that there exists a range of 7,, r such that for any distribution defined with r in that range, though it is possible to obtain linear classifier with 0 training and test error, the minimum adversarial risk will be bounded from O.
However while it is possible to obtain linear classifier with 0 test error, all such linear classifiers has 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, y where the linear classifier's adversarial error was atleast a constant.
a large adversarial vulnerability. In Lemma 2
Lemma 1 (Linear Classifier). There exists universal constants "No: P. such that for any perturbation Y > No. radius r Z p. and l E Z4. the following holds. Let 'D be the family of (r, k)- 1-bit parity class conditional model, P E D and S.. ((xi.))).."" v1)} be a set of points sampled ii.d from P.
1) For any n. > 0, Sn, is linearly separable with probability 1 i.e. there exists h (W, wo), w E R2, wo E TR such that the linear hyperplane x - w x + wo separates Sn with probability 1:
V (xx Sn 2 x wo) >0 where -2y
2) Further there exists an universal constant e. such that for any e, 5> O with probability 1 ô for any Sn with n = C,2 log 1. any linear classifier h that separates Sn has R(h: S c.
3) Let h: (w,wy, wo) be any linear classifier that has R(h:Pp) = O. Then, Radv, (h; > 0.0005.
We will prove the first part for any r 1 by constructing a w, wy such that it satisfies the 2/2 constraints of linear separability. Let w = (1, wo = 0.5.. Consider any point (x, y) E S, and 2y Converting to the polar coordinate system there exists 6 E 2x] .j [0, [0,... such that x = (j + 2+1 rcos (0), + rsin (0))
1+1
2 (w x + wo) j +
2 rcos (0) - j - rsin (0) 0.5
w w= (1,
+ +0.5 + rcos (8) rsin (0) 0.5
2
(cos (0) sin (0))
|cos (0) - sin (0) < V2, 2 (-1,1)
> 2
-rv2
1
> 0
r < 2
Part 2 follows with simple VC bounds of linear classifiers.
Let the universal constants "Yo, P be 0.02 and 2/2 special about this constants except that some constant is required to bound the adversarial risk away from Now, consider distribution P 1-bit parity model such that the radius of each ball is atleast p. and thus satisfies the linear separability criterion.
1 0.008 respectively. Note that there is nothing
This is smaller than 2
Consider h to be hyper- that has 0 test error. Let the &g radius of adversarial perturbation be y > %o. 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
17

---

Published as a conference paper at ICLR 2021
segments be To- Thus, RAdv.-(h; is greater than the mass of the circular segment of radius ro- 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
V22 2 rr (Y
ro)
tr
ro 2r 2r +y
(5)
V2
To compute RAdv,7 (h; P) we need to compute the ratio of the area of a circular segment of height ro of circle radius r to the area of the circle. The ratio can be written
cos -1
(1
2u
2
4
A
(6)
As 6 is increasing with evaluate
2r
To
Using 5
0.02
2 2
v2
7 70 0.02
2 2
v2
0.02
0.01
p 2
1
0.008
0.008
Substituting > 0.01 into Eq. (6. we get that A (#) > 0.0005. Thus, for all 7 > 0.02, we have RAdv, (h;P) P) 0.0005.
Lemma (Robustness of parity classifier). There exists a concept class H. such that for any ? E [10. 70 11. h E Z,, P being the corresponding (p. k) 1-bit parity class distribution where p. "1o are the same as Lemma there exists E H. such that
Rig; P) = 0
RAdv, (g; (g: =
Proof of Lemma 2
We will again provide proof by construction. Consider the following class of concepts H such that go E H is defined as
(11,
if if[m]] + [x2]] = b (mod 2)
o.w.
where [æ]] rounds z to the nearest integer and b E {0, 1}. In Figure 6b the green staircase- like classifier belongs this class. Consider the classifier 91- Note that by construction R(gi: P) The decision boundary of 91 that are closest to ball in the support of P centered at (a, b) are the lines x + 0.5 and y = h + 0.5.
As < + 1. the adversarial perturbation is upper bounded by 50 The radius of the ball is upper bounded 1 and
noted the center of the ball is at distance of 0.5 from the decision boundary. 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 Substituting the values,
2
1
1
1
< 0.499
50
8
2/2
2
This completes the proof.
18

---

Published as a conference paper at ICLR 2021
B.3 PROOF OF APPENDIX A
Theorem 2. For any nt E Enp there exists family of distributions DD' over R x {0, 13 and function classes C, H. such that for any P from DD, and for any 0 < 1 and (0, 1/2) if
Sn = {(x, We denotes sample of size m. drawn from P where
n2 (1 (1-n) +
n
n 78
m m=
max
TI log
log
(1- 2n1)
and if Sm,y denotes the sample where each label is flipped independently with probability 1).
(i) the classifier Radv,y P) = for 0 S <<>> 1/4.
C that minimizes the training ervor Smmp has R(c 0 and
(ii) there exist E H. h has zero training error on Sm.n. and R(; P) 0. However, for any > 0, and for any H with zero training error on Smay. RAdv, (h; P) 0.1.
Furthermore, the required e E and h E H above can be computed in O (poly (n), poly
poly (t)) time.
Proof of Theorem 2 We will provide a constructive proof to this theorem by constructing distribu- tion D, two concept classes C and H 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 D such that Ds.c E D is defined on X₂ x {0, for S C (1. "nn.". , (1,...,2) - 1} such that the support of Xe is union of intervals.
supp (x) =U where IT = ( --- JEC
7. 1
We consider distributions with a relatively small support i.e. where |s| = (n). Each sample
(x, y) Ds.c is created by sampling uniformly from X and assigning cs (x) where es C is defined below (9.. We define the family of distributions D Unez. D Finally, we create S.c
-a noisy version of Ds.ç. by flipping y each sample (x. y) with probability 17 < 1. 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 FX" (Ds.c)
Concept Class C: We define the concept class C" of concepts cs [0,2*] - {0, 1) such that
1,
if ([x)),, XOR 8) is odd.
cs (x)
0 o.w.
where :] + E rounds a decimal to its nearest integer, (-)s (0, ... 2" + 10, returns the binary encoding of the integer, and ([x)) XOR S) Ejes (z)) [i] mod ([r])) [J] is the jt least significant bit the binary encoding of the nearest integer 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 x. For example, as in Figure Galif if {0, then only the least significant and the third least significant bit of are examined and the class label is if an odd number of them are 1 and otherwise.
Concept Class H: Finally, we define the concept class H = U Ht where Hr is the class of union of k intervals on the real line Ht, Each concept h4 E H² can be written as set of & disjoint intervals = (J, , on the real line i.e. for 1 S E k. I = (a, b) where 0 S a S b and
(1 if E i
ufx+U,4
h (x)
(10)
o.W.
Now, look at the algorithms to leam the concepts from C and H 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 minimize the test error. The intuition is that if we draw sufficiently large
19

---

Published as a conference paper at ICLR 2021
number of samples, then the majority of samples on each interval will have the correct label with
high probability.
Lemma proves that there exists algorithm A such that A draws m O (Isi ----) log 1
(1-2n)²
samples from the noisy oracle EX" (Da.c) and with probability 1 - 8 where the probability is over the randomization in the oracle, returns f E C such that Rf: Ds.c) = and RAdv,, (f: Ds.ç) = 0 for all y < 3. As Lemma 3 states, the algorithm involves gaussian climination over |s| variables and [c] majority votes (one in each interval) involving total of samples. Thus the algorithm runs in O (poly (m) + poly (Is1)) time. Replacing the complexity of m and the fact that |c| = O (n), the
complexity of the algorithm is (poly (nL 1-2.. :)
Lemma 4 proves that there exists an algorithm À such that A draws
m max { 2 log
21s| (1-1) +1 (1- - 2n)
0.1 ls mm
0.1 |s]
log
76
samples and returns h E 7 such that h has 0 training error, 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 This completes the proof. 0
of m, the complexity of the algorithm is O (poly n. 1'2
Lemma 3 (Parity Concept Class). There exists learning algorithm A such that given access to the noisy example oracle EX" (Ds.ç), A makes m = = (Is) (1 (1-2n)² log 15) calls to the oracle and returns a hypothesis J E C such that with probability RAdv,y Ds.c) 0 for all 7 <
we have that R(J; = 0 and
Proof. The algorithm A works as follows. It makes m calls to the oracle EX (Dm) to obtain a set of points {(11, ................................ (Im: }m)} where m 2 2|5| log 3k! (8 (1-))
(1-2n) + +1) Then, replaces each x; with [zv] (-- rounds a decimal to the nearest integer) and then removes du- plicate 248 by preserving the most frequent label yi associated with each zi. For example, if S3
8
(2, 0), 13,1, (3.2, 1). (3.9.0) then after this operation, we will have {(3. 1), (4,
As m 2 2 2| log 2kl (8 (1-w) + 1). using 52 = 1 and k = 8(1-1) 2kl in Lemma (1-2n)² log o
o
(1-2))²
guarantees that with probability 1 2 each interval will have atleast 8(1-n) log 21 (1-2n)²
samples.
5
Then for any specific interval, using 8 = 2k4 o in Lemma guarantees that with probability atleast
1 1- 2k<] the majority vote for the label in that interval will succeed in returning the de-noised label. 8
Applying a union bound over all [c] intervals, will guarantee that with probability atleast - 5, 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 [c] 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 polynomial algorithm using Gaussian Elimination that finds consistent hypothesis for this problem. We have already guaranteed that there is a point in S, from every interval in the support of Ds.c- Further, f is consistent on S., and f is constant in each of these we have that R(f;
intervals by design. Thus, with probability atleast
= O.
By construction, of makes a constant prediction on each interval (j - 1. + 1) for all E EC. Thus, for any perturbation radius < 1/ the adversarial risk RAdv Rddv,Ds.re (f) = 0. Combining everything,
we have shown that there is an algorithm that makes 2 |/| log 2K( (8 (1-v) + +1) calls to the
(1-21)²
EX (D',c) oracle, runs in time polynomial in Is), 1-27 1 to return f E C such that R(f: Ds.c) 0 and RAdv, (f: (sc)s = 0 for 7 <<4 1
20

---

Published as a conference paper at ICLR 2021
Lemma 4 (Union of Interval Concept Class). There exists a learning algorithm À such that given [1-m) access to noisy example oracle makes m = O (Is)² [I-2n)² log 44) calls to the oracle and returns a hypothesis h E 'H such that training evror is 0 and with probability 1 1 6, R(f; Ds.5) = 0.
Further for any h H that has zero training error m' samples drawn from EX" (Ds.s) for
m' 10ny
log T0y6
1cl and (0, 2) then RAava (f;Ds.c) 2 for all y > O.
Proof of Lemma 4 The first part of the algorithm works similarly to Lemma 3 The algorithm À makes calls to the oracle EX (D to obtain set of points S. {(21, /1) ,.).... (Tmm Vm }
where 2 2 < log 5
2(
8 (1-n)
(1-2x)² + +1) A computes h E H as follows. To begin, let the list of
intervals in be I and M, = O Then do the following for every (x, y) E Sm.
1. let 2 := [z].
2. L, S Sm. be the set of all (a, y) E Sm such that Jx - z/ < 0.5.
3. Compute the majority label i of N2.
4. Add all (2r, y) E N2 such that y # ì to M:
5. If t = then add the interval (z 0.5, + 0.5) to T.
6. Remove all elements of N₁ from Sn i.e. Sm := Sm \...
For reasons similar to Lemma 3 as m 2 2|(| log 2151 (8 [1-1) + 1). Lemma guarantees that
8
24)
with probability & each interval will have atleast 8(1-7) (1-2n) log 2k1 samples. Then for any specific
interval, Lemma 6 guarantees that with probability atleast 1 2141 the majority vote for the label in that interval will succeed in returning the de-noised label. Applying union bound over all intervals, will guarantee that with probability atleast - 5, 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
8. Thus, R(h; Ds.c) 0.
Now, for all (x. E M2,, add the interval [a]] to if = 1. If = 0 then x must lie a interval (a, b) E I. Replace that interval as follows I = I (a, b) U f(a, z), , (z, b)}. As only a finite number of sets with Lebesgue measure of O were added or deleted from I, the net test eтror of h doesn't t change and is still i.e. Rh; Ds,c)= =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 [and reserve ( for the support of interval of Ds,c- Let I be any
set of disjoint intervals of width such that [T] = 0.1|c| This is always possible as the total width of
all intervals in I' is 0.1151 = 0.1 2 which is less than the total width of the support IsI 2 c1, C2 from
Eq. 3 is
2 0.1 = 0.1, 02
27
41 PDS
[ 2 2|cl
151
=
2|c
Thus, if h has error of zero on of m' examples drawn from EX" (Ds.c) where ml 0.11gl log (.115) then by Theorem Radv, (1;; Ds.c) > 0.1.
70
Combining the two parts for
m max { 2 log
2151
8 (1-1)
0.1 K
0.1 [<|
+1
log
(1 27)
78
it is possible to obtain h H. such that h has zero training error, R(Ds,;:)) h) 0 and RAdv, Ds.c) > 0.1 for any > 0.
21

---

Published as a conference paper at ICLR 2021
Given & 24 and distribution Ds,ç- for any 82 > if m 2|5(2 k. 211 log Kl
Lemma 5.
samples are drawn from EX (Ps.c) then with probability atleast 82 there are atleast samples in each interval (j- 1. 1) for all j E E.
Proof of Lemma We will repeat the following procedure [c] times once for each interval in Ç and á the jth run will result in atleast k samples in the jth interval.
show that with probability [<|
Corresponding each interval Ç, we will sample atleast m' samples where m' 2 2|5| log 15_. If 2 is the random variable that is 1 when the 1th sample belongs to the jth interval, then 7th interval has atleast &o points out of the m' points sampled for that interval with probability less than [ci
8s
P
Σ
S
k
=
Σ
S
(1
8)
=
Σ
k.
2 1
exp
By Chernoff's 's inequality
p.
2
ml
k2a
[<]
m
exp
1o
+
1
2m
C
m'
82
exp
k
1
2 |
[<1
4l With probability atleast दिî every where the last step follows from m' > 2 [S| k + 2 lol b.. interval will have atleast & samples. Finally, 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
IC] m' 2 |5| k 2 |<| log [s]
Lemma (Majority Vote). For a given y E {0, 1}, let S (si,... Smm be a set of size m where each element is y with probability 1 - and probability atleast - ōn the majority of S is y.
1 8(1-n) log of then with otherwise. If m > (1-2n)²
Proof of Lemma 6 Without loss of generality let y = 1. For the majority to be I we need to show that there are more than v. "1"s i.e. we need to show that the following probability is less than
51.
IP
Σ
8
m1
IP
3
m
μ + P
E
2
2p
P
Σ
8
1
1
m1
2p
(1 - 27) 2
< exp
8 (1 1)) 2 M
By Chernoff's Inequality
(1 2n)
exp
8 - 1) m
p (1 - -7) m
8 - 77)
S 01
m. >
log
(1 - 2m)*
81
C ADDITIONAL EXPERIMENTS
C.1 ROBUST TRAINING IGNORES RARER SUB- POPULALNTSS (SYNTHETIC SETTING)
This phenomenon is demonstrated more clearly in a simpler distribution for different NN configura- tions in Figure 7 We create binary classification problem on R22 The data is uniformly supported
22

---

Published as a conference paper at ICLR 2021
6
Train-Ace. (%)
Test-Ace (%)
0.0
99.98
95.25
0.25
97.23
92.77
1.0
86.03
81.62
Table 1: Train and accuracies clean CIFARIO for ResNet-50 trained using Eg e-adversaries.
The E = setting represents the natural training.
on non-overlapping circles of varying radiuses. All points in one circle have the same label i.e. 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- Siiee NN) and 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 shows that the adversarially trained (AT) models ignore the smaller circles (i.e. rare sub sub-popllations and tries to get 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.
AT
NAT
AT
NAT
(a) Shallow Wide NN
(b) Deep NN
Figure 7: Adversarial training (AT) leads to larger margin, and thus adversarial robustness around high density regions (larger circles) but causes training error low density sub- aubpoopulations (smaller circles) whereas naturally trained models (NAT) minimizes the training error but leads to regions with very small margins.
C.2 COMPLEXITY OF DECISION BOUNDARIES
When neural networks are trained they create classifiers whose decisions boundaries are much simpler than they need 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 we discussed this theoretically and also why this might not violate the traditional wisdom of Occam's 's Razor. In particular, complex decision boundaries does not necessarily mean more complex classifiers in statistical notions of complexity like VC dimension.
this section, we show through 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 possible.
We train three different neural networks with ReLU activations, shallow network (Shallow NN) with layers and 100 neurons each layer, a shallow network with layers and 1000 neurons in each layer (ShallowWiid Wide NN), and a deep network with 4 layers and 100 neurons in each layer. We train them for 200 epochs on binary classification problem as constructed in Figure g The distribution supported on blobs and the color of each blob represent its label. On the right side, have the decision boundary of a large margin classifier, which is simulated using a 1-nearest neighbour.
From Figure g it is evident that the decision boundaries of neural networks trained with standard optimizers have far simpler decision boundaries than is needed to robust (eg. the nearest neighbour is much robust than the neural networks.)
23

---

Published as a conference paper at ICLR 2021
(a) Shallow NN
(b) Shallow-Wide NN
(c) Deep
(d) Large Margin
Figure 8: Decision boundaries of neural networks much simpler than they should be.
C.3 ACCOUNTING FOR FINE GRAINED PUB-LOPULAS LEADS TO BETTER ROBUSTNESS
One way to evaluate whether more meaningful representations lead to better robust accuracy is to use training data with more 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, CIFARI00 (Krizhevsky & Hinton 2009), and Restricted Imagenet (Tsipras et al. 2019) that training on fine- ine-grained labels does increase robust accuracy.
labels (e.g. subclasses of a class); for example, one would
We hypothesize that learning more meaningful representations by accounting for fine- fine-graine grained sub- populations within each class may lead to better robustness. We use the theoretical setup presented in Appendix and Figure 6b However, if each of the circles belonged to a separate class then the decision boundary would have be necessarily more complex it needs to, now, separate the balls that were previously within the same class. We test this hypothesis with two experiments. First, we test on the the distribution defined in Theorem 3 where for each ball with label it a different label (say a...... ag)) and similarly for balls with label O, we assign it a different label ($1, (²). Now, we solve multi-class classification problem for 2k classes with deep neural network and then later aggregate the results by reporting all a,s as 1 and all 3,s 0.The resulting decision boundary drawn in Figure Pa| 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.
assign
Second, also repeat the experiment with CIFAR-100. We train ResNet50 (He et al. 2016) the fine labels of CIFAR 100 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 layer 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 % shows that for all perturbation budgets, Coaree 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 There are 60 fine classes and 10 coarse classes with each coarse class having distinct fine classes in them. The train size is 77237 and the test set size is 3000. The fine classes within each coarse are balanced i.e. given coarse class all the fine classes are equally represented in this dataset.
D EXPERIMENTAL DETAILS
In this section, we will discuss details about the experiments and model architectures used to help make sure that the experiments are reproducible.
D.1 MODEL ARCHITECTURES IN SECTION 3.1
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
24

---

Published as a conference paper at ICLR 2021
AT
MULTICLASS
NATURAL
(a) Decision Region of neural networks are more complex for adversarially trained models. Treating it as multi-class classification problem, with natural training (MULTICLASS), also increases robustness by increasing the margin.
100
Adversarial Error
100
Adversarial Error
80
Fine2Coarse Coarse
FineeCoarse
60
Coarse
0.002
0.003
0.004
0.005
0.0
0.1
0.2
0.3 0.4
Perturbation
Perturbation
(b) CIFAR-100.
(c) Restricted Imagenet
Figure 9: Assigning separate class to each sub-population within the original class during training increases robustness by learning more meaningful representations.
Coarse Class
Fine Classes
Dog
Chihuahua, Japanese spaniel, Maltese dog, Pekinese, Shih-Tzu, Blenheim spaniel cock, hen, ostrich, brambling, goldfinch, house finch tiger beetle,ladyyug.gng ground beetle, long-horned beetle, leaf beetle, dung beetle guenon, patas, baboon, macaque, langur, colobus jeep, limousine,cab, beach wagon, ambulance, convertible leopard, snow leopard, jaguar, lion, cougar, lynx truck, moving van, fire engine, pickup, garbage truck, police van Granny Smith, rapeseed, corn, acorn, hip, buckeye agaric, gyromitra, stinkhorn, earthstar, hen-of-ther tte-thods. coral fungus gondola, fireboat, speedboat, lifeboat, yawl, canoe
Bird
Insect
Monkey
Car
Feline
Truck
Fruit
Fungus
Boat
Table 2: Fine-grained classes in Restricted Imagenet
and 3, 3,4,3,3 sized kernels respectively. This is followed by fully connected layers with a hidden dimension of 1024. The network is optimized with SGD with batch size of 128, learning rate 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.
D.2 DETAILS ON EXPERIMENTS MEMORIZATION AND INFLUENCE
For given dataset S, training algorithm A. Zhang & Feldman 2020) measure the label memorization by A on 5 using two related quantities memorization and influence. For a training example (2,,, v:) E S and test example (ar), v/)), the two quantities are special case of measuring the influence of (I,, ys) on the expected accuracy
example (xr 3). Influence test example
25

---

Published as a conference paper at ICLR 2021
measures the impact of (a'), u/) the expected aceuracy of vej. Memorization corresponds to the influence of example (T), 2/6 on the accuracy itself (or self-influence
Memorization or Self-Influence: Self influence of an example with respect to an algorithm (model, optimizer etc) can be defined how unlikely it is for the model learnt 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 followed which is borrowed from Eq (I) in Zhang & Feldman (2020)
Memorization by A on example (zi, yc) E E is defined
(A, P=-sss()))(( yel - PP ysl
where S denotes the dataset S with (r,, y1) removed, h + A(S) denotes the model h obtained by training using algorithm A (which includes the model architecture) on the dataset and the probability is taken over the randomization inherent in the training algorithm A.
Influence a training sample: Intuitively, it measures the probability that a certain test example would be classified correctly if the model were learned using 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 follows which is borrowed from Eq 2 in ZZang & Feldman (2020). Using similar notation as memorization the influence of (Ii, yt) on (1'z, U3)
can be measured as
i,,,, (I,, Mi). (4lg, uf)) = Pn- = PPlssPr-
s/1
We found the images in Figure 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 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 CIFARIO with Ez-adversary with an c <= 0.25 and model trained with TRADES for MNIST with À and 0.3. Zhang & Feldman (2020) had provided us the with the memorization scores for each image in CIFARIO 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
test image. We searched in the set
obtained from https:/ //p ripluue Lukki.. github. io/influence memor zat ton/ This was used obtain the figures for Imagenet in Figure
26


Reviews:
[{"review_id": "z-OIx9rc1LZ", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The main contribution of this paper as I see it is in pointing out that label noise can negatively affect the adversarial robustness of interpolating predictors, even when the standard 0-1 error is small. The paper supports this claim with a simple theoretical construction (Theorem 1) and several empirical experiments. The paper also argues that adversarial training techniques avoid memorizing noisy labeled examples and  rare examples which partly explains why adversarial training incurs higher standard 0-1 error. \n\nAnother result of this paper is Theorem 2, which exhibits an example of a learning problem and two function classes $C$ and $H$, where: (1)  there is a classifier in $C$ that interpolates the training data and furthermore achieves zero standard error and zero robust error, and (2) there is a classifier in $H$ that interpolates the training data and achieves zero standard error but has high robust error. The result would be stronger  if the quantifier in (1) is strengthened to: for any classifier in $C$ that interpolates the training data (rather than there exists). Furthermore, as the authors mention in related work, (Montasser, Hanneke, Srebro, 2019) have shown that there are function classes that are robustly learnable but only improperly. So, it is kind of already known that the representations used for learning matter for adversarial robustness. It would be good the authors could explain the difference between their contribution and what’s known before. \n \nSome questions:\nIt would be interesting to see if adversarial training can be made such that to achieve zero robust loss on the training data, which means that it interpolates the training data. What would be the standard 0-1 error of such predictors?\nWould it be possible to strengthen Theorem 1 by relaxing the condition in Equation (3) such that its only required that the mass of $\\zeta$ under $D$ is at least $c_1$ (rather than requiring union of the perturbation balls to have mass at least $c_1$)? \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "wqnZjOqb36K", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "### Summary\n\nThe 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.\n\n### Significance\n\nThe generalization properties of neural networks and adversarial robustness are two very fast-moving areas of machine learning.  This paper does a nice job revealing some properties of overfit networks.  These properties are intuitive (at least, I would have assumed them), but I have not seen them so nicely laid out, and it is important to not have to assume.  It does a great job of filling in these holes with evidence, and so I find it quite significant.\n\n### Originality\n\nTo my knowledge, the work is original.\n\n### Quality\n\nThe experiments are quite well designed and performed.  I find the second theoretical contribution too quickly discussed, and the \"unusual examples\" experiment insufficiently emphasized, but otherwise it is quite a good paper.  Graphs and figures are meaningful and well explained.  Theoretical results nicely support portions of the paper that might otherwise be criticized as anecdotal.\n\n### Clarity\n\nVery clearly written.", "extra_scores": {}, "extra_text": {}}, {"review_id": "gT2JcvpvHSg", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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. \n\nThe authors claim that one primary source of the lack of adversarial robustness is label noise. They show this via a simple construction. Suppose you have a sphere of instances of radius r that have the label y (true label). Suppose then that you flip some of the labels at random. Then, obviously, any algorithm that has a perfect training accuracy will not be robust because, by construction, there exists examples within a distance of 2r from each other that have different labels. The authors make this argument formal. This result by itself is not very interesting. What would be interesting is if label noise was indeed the main source of lack of robustness in models trained on standard datasets, e.g. CIFAR10 or ImageNet. The authors show that such datasets do contain a lot of label noise but, unfortunately, state that removing such label noise by itself is not sufficient to make the trained model robust. In fact, some of their results indicate that robustness is not caused by label noise. For example, all ResNet18, DenseNet121, and VGG19 trained on CIFAR10 have a large adversarial error even with zero label noise! (Figure 2 bottom) \n\nThen, the authors discuss a different argument: they show that adversarial training prevents memorization of mislabeled examples. This is interesting. However, it would be great if the author could clarify how they determined that 994 out of the 997 samples in CIFAR10 mentioned in Section 3.2 were mislabelled. Did they manually inspect all 994 examples? This would correspond to about 2% of CIFAR10 training examples. I find this number to be quite large. For instance, the BiT model (https://arxiv.org/pdf/1912.11370.pdf) achieves more than 99% test accuracy on CIFAR10. If you look into their analysis of errors in Fig 8, it suggests that the ratio of mislabeled examples in CIFAR10 is less than 0.5%, not 2%. I would appreciate it if the authors could clarify how they determined that 994 out of 997 were mislabelled. \n\nThe second main contribution of the paper is on the relation between adversarial training and representation. The main conclusion here is that if one chooses the hypothesis space carefully, the learner can achieve good generalization and robustness. But, if the hypothesis space is not chosen well, one can achieve good generalization but poor robustness. So, the choice of the hypothesis space matters. I find this result to be disappointing. Here is a much simpler example. Suppose we have two spheres that are well-separated from each other, each sphere corresponds to a class, and we add some small label noise. Now, consider the class of linear separators, e.g. using large-margin SVM. These will not fit the training data perfectly but will have a small excess Bayes risk (since the Bayes-optimal decision boundary are disjoint spheres) and are robust. On the other hand, let the second hypothesis space be the space induced by the kNN classifier. Both the training and test error will be small (since kNN averages the labels of neighbours and the label noise is small), but the adversarial error is large (with a high probability, there will be a small region in each sphere that is predicted differently by kNN). \n\nIn summary, I think the paper has an excellent motivation with useful empirical results (e.g. Figure 2), but the main results might not be interesting since one can arrive at such conclusions using much simpler arguments as I mentioned above.\n\nAdditional Remarks:\n- The authors suggest in the Introduction section that there is no fundamental tradeoff between robustness and accuracy. Later in Section 3.2, however, they point out that robust training ignores rare examples, which reduces the test accuracy. They argue for this using the notion of “self-influence”. I suggest revisiting that paragraph in the introduction. \n\n- The authors add a claim in the Conclusion section that is not discussed within the main text as far as I could tell. They state that some invariances can increase adversarial vulnerability. Where is this mentioned in the main text?\n \n- There are a few typos in the paper:\n\t* Abstract: “partsub-“optimal —> part sub-optimal \n\t* Page 4: “Thus, smaller the value of” —> “Thus, the smaller the value of”.\n\t* Page 6: “we found that that” —> “we found that”\n\t* Page 7: “that are are heavily” —> “that are heavily”", "extra_scores": {}, "extra_text": {}}, {"review_id": "FybrjFv5rRI", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\nThe 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. \n\nI find the paper very well written. In my opinion, it will be of interest for most participants of ICLR. It is of course not surprising that label noise memorization and poor representation learning cause adversarial vulnerability, but the way it is theoretically quantified and empirically demonstrated in this paper is worth being published.      \n\nMinor remarks\nAbstract : “in partsub-optimal” -> “in part sub-optimal”\nLine 2 of Thm 1: D in the subscript of P should be \\mathcal D.\nProof of Thm 1: in the lines below (4), “P_{S_m ∼D^m}” should be removed (4 occurrences) \nProof of Thm 1: in the chain of equalities/inequalities below eq (4), the fourth line should be an inequality.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper seeks to understand how training over-parametrized models (e.g., those based on neural networks) to zero training accuracy even when the test error is small (i.e., benign overfitting) can introduce vulnerabilities in the form of adversarial examples and how to remedy the situation. The paper implicates label noise as one of the causes of adversarial robustness, and suboptimal representations learned as part of the training as another. The claims are supported both theoretically and empirically. A good paper overall, accept! 
Decision: Accept (Spotlight)