Original "male" Adversarial "female" Adversarial "female" Adversarial "female" Adversarial "female" Asymmetric dataset We analyze conditions on the data distribution under which the Bayes-Optimal classifier may be vulnerable to adversarial attacks and present realistic image datasets for which the BayesOptimal classifier can be calculated efficiently. When the data distribution satisfies certain asymmetries, the Bayes-Optimal classifier is vulnerable (b), but when the distribution is symmetric, the optimal classifier is robust and adversarial attacks are perceptually meaningful (c). Our experiments with these datasets show that CNN training consistently fails to find a robust classifier even when the optimal classifier is robust (d), while large-margin methods often succeed (e).
Adversarial attacks on CNN classifiers can make an imperceptible change to an input image and alter the classification result. The source of these failures is still poorly understood, and many explanations invoke the "unreasonably linear extrapolation" used by CNNs (Goodfellow et al., 2018) along with the geometry of high dimensions. In this paper we show that similar attacks can be used against the Bayes-Optimal classifier for certain class distributions, while for others the optimal classifier is robust to such attacks. We present analytical results showing conditions on the data distribution under which all points can be made arbitrarily close to the optimal decision boundary and show that this can happen even when the classes are easy to separate, when the ideal classifier has a smooth decision surface and when the data lies in low dimensions. We introduce new datasets of realistic images of faces and digits where the Bayes-Optimal classifier can be calculated efficiently and show that for some of these datasets the optimal classifier is robust and for others it is vulnerable to adversarial examples. In systematic experiments with many such datasets, we find that standard CNN training consistently finds a vulnerable classifier even when the optimal classifier is robust while large-margin methods often find a robust classifier with the exact same training data. Our results suggest that adversarial vulnerability is not an unavoidable consequence of machine learning in high dimensions, and may be the result of the specific distributions of commonly used datasets or of suboptimal training methods used in current practice.
This paper proposes studying adversarial examples from the perspective of Bayes-optimal classifiers. They construct a pair of synthetic but somewhat realistic datasets—in one case, the Bayes-optimal classifier is *not* robust, demonstrating that the Bayes-optimal classifier may not be robust for real-world datasets. In the other case, the Bayes-optimal classifier is robust, but neural networks fail to learn the robust decision boundary. This demonstrates that even when the Bayes-optimal classifier is robust, we may need to explicitly regularize/incentivize neural networks to learn the correct decision boundary.
The contribution of the two datasets (the symmetric and asymetric CelebA) is, in my opinion, an extremely important contribution in studying adversarial robustness and on their own these datasets warrant further study. Previously, all studies of this sort had to be done with small-scale classifiers and simplistic datasets such as Gaussians. The paper also definitively proves that there are realistic datasets where the Bayes-optimal classifier is non-robust, which goes against quite a bit of conventional wisdom in the field and opens up many new paths for research. However, there are a few (in my opinion) critical concerns that currently bar me from strongly recommending acceptance of the paper. I outline these below.
1. Prior work: the paper seems to ignore a plethora of prior work around studying adversarial robustness and understanding its roots. For example, a few very closely related works are as follows:
   - Adversarial examples are not Bugs, they are Features (https://arxiv.org/abs/1905.02175): Ilyas et al (2019) demonstrate that adversarial perturbations are not in meaningless directions with respect to the data distribution, and in fact a classifier can be recovered from a labeled dataset of adversarial examples. While not in conflict with this work, it does closely relate and discuss many of the same issues discussed in this work, so relating them would be fruitful.
   - A Discussion of Adversarial Examples are not Bugs they are Features (https://distill.pub/2019/advex-bugs-discussion/): Nakkiran (2019) actually constructs a dataset (called adversarial squares) where the Bayes-optimal classifier is robust but neural networks learn a non-robust classifier due to label noise and overfitting. Interestingly, they also construct a dataset where they Bayes-optimal classifier is robust and neural networks *do* learn a robust classifier (adversarial squares sans label noise). While I think the datasets presented in this work are much more interesting and certainly more realistic, this work should be put in context.
    - Excessive Invariance causes Adversarial Vulnerability (https://arxiv.org/abs/1811.00401v3): Jacobsen et al offers an explanation for adversarial examples based on the fact that NNs are not sensitive to many task-relevant changes in inputs, which seems to tie in nicely to the discussion in this paper, as under the presented setup the Bayes-optimal classifier will certainly exploit (and be somewhat sensitive) to such changes.
    - Adversarially robust generalization requires more data (https://arxiv.org/abs/1804.11285): Schmidt et al show a setup where many more samples are required for adversarial robustness than for standard classification error. And it seems to have very relevant connections to your work.
    - In general this list is not comprehensive either: there are many relevant connections to the robustness-accuracy tradeoff (https://arxiv.org/abs/1901.08573, https://arxiv.org/abs/1805.12152), and other works. 
2. Discussion/interpretation of the results: 
    - Sufficient vs necessary: While the experimental design and results are both of very high quality, I am slightly confused about the interpretation of the results. First, if my understanding of the paper is correct, the experiments show that (a) the Bayes-optimal classifier can be non-robust in real-world settings, and (b) even when the Bayes-optimal classifier is robust, NNs can learn a non-robust decision boundary. In particular, (b) indicates that it may be *necessary* to design regularization methods that steer NNs towards the correct decision boundary—it says nothing about whether these regularization methods will be *sufficient*, which the paper seems to suggest, e.g. in the abstract "our results suggest that adversarial vulnerability is not an unavoidable consequence of machine learning in high dimensions, and may often be a result of suboptimal training methods used in current practice." In fact, if real-world datasets end up being like the asymmetric dataset, then the results of this paper would actually indicate the *opposite* of the above statement. It is unclear on what basis one can say that real-world datasets are more like the symmetric case or the asymmetric case. I believe a more measured conclusion (perhaps that we *need* more regularization methods, but even then we may not be able to get perfect robustness and accuracy) would better fit the strong results presented in the paper.
    - CNN vs Linear SVM: I am confused about why we would expect a CNN to be able to learn the Bayes-optimal decision boundary but not the Linear SVM. The paper justifies the adversarial vulnerability of the Linear SVM by arguing that the Bayes-optimal classifier is not in the Linear SVM hypothesis class, which makes sense. The RBF SVM, for small enough bandwidth can express any function and is convex, so no argument needs to be made about its ability to find the Bayes-optimal classifier. For CNNs, however, it is unclear if the Bayes-optimal classifier lies in the hypothesis class (there are "universal approximation" arguments but these usually require arbitrarily wide networks and are non-constructive)—couldn't it be that the CNNs used here is in the same boat as the Linear SVM (i.e. the Bayes-optimal decision boundary is not expressible by the CNN?) 
3. Experimental setup: 
    - One somewhat concerning (but perhaps unavoidable) thing about the experimental setup is that all the considered datasets are not perfectly linearly separable, i.e. the Bayes-optimal classifier has non-zero test error in expectation, and moreover the data variance is full-rank in the embedded space. This is in stark contrast to real datasets, where there seem to be many different ways to perfectly separate say, dogs from cats, and the variance of the data seems to be very heavily concentrated in a small subset of directions. I am concerned that these properties are what drive the Bayes-optimal classifier for the symmetric dataset to be robust (concretely, if 0.01 * Identity was not added to the covariance matrix of the symmetric model and the covariance was left to be low-rank, then any classifier which was Bayes-optimal along the positive-variance directions would be Bayes-optimal, and could behave arbitrarily poorly along the zero-variance directions, still being vulnerable). This concern does not make the contribution of the symmetric dataset less valuable, but a discussion of such caveats would help further elucidate the similarities and differences of this setup from real datasets. 
    - It is unclear if what is lacking from the NN is explicit regularization, or just more data. In particular, with such low-variance directions, at standard dataset sizes the distributions generated here are most likely statistically indistinguishable from their robust/non-robust counterparts (you can see hints of this in the fact that the CNN gets . While completely alleviating this concern may once again be quite difficult/impossible, it could be significantly alleviated by generating training samples dynamically (at every iteration) instead of generating a dataset in one shot and training on it. It would be very interesting to see whether these results differ at all from the one-shot approach here.
4. A suggestion rather than a concern and not impacting my current score: but it would be very interesting to see what happens for robustly trained classifiers on the symmetric and asymmetric datasets.
Overall, this paper is a very promising step in studying adversarial robustness, but concerns about discussion of prior work, discussion of experimental setup, and conclusions drawn, currently bar me from recommending acceptance. I would be more than happy to significantly improve my score if these concerns can be addressed in the revision and corresponding rebuttal.