Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: ### Summary

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

### Significance

The 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.

### Originality

To my knowledge, the work is original.

### Quality

The 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.

### Clarity

Very clearly written.
review_title: Easy to read paper clearly demonstrating some intuitive insights on generalization and adversarial robustness

final_score: rating: 7: Good paper, accept
review_content: 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. 

Another 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. 
 
Some questions:
It 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?
Would 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$)? 

review_title: Review

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

I 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.      

Minor remarks
Abstract : “in partsub-optimal” -> “in part sub-optimal”
Line 2 of Thm 1: D in the subscript of P should be \mathcal D.
Proof of Thm 1: in the lines below (4), “P_{S_m ∼D^m}” should be removed (4 occurrences) 
Proof of Thm 1: in the chain of equalities/inequalities below eq (4), the fourth line should be an inequality.
review_title: Nice attempt of exploring both theoretically and empirically the causes of lack of adversarial robustness of benign overfitting 

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

The 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) 

Then, 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. 

The 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). 

In 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.

Additional Remarks:
- 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. 

- 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?
 
- There are a few typos in the paper:
	* Abstract: “partsub-“optimal —> part sub-optimal 
	* Page 4: “Thus, smaller the value of” —> “Thus, the smaller the value of”.
	* Page 6: “we found that that” —> “we found that”
	* Page 7: “that are are heavily” —> “that are heavily”
review_title: Excellent motivation with useful empirical results but the main results might not be interesting

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)