A Bayes-Optimal View on Adversarial Examples
Authors: Eitan Richardson
Yair Weiss
Venue:  (2020)
Keywords: Adversarial Examples
Generative Models

Abstract: 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 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 often be a result of suboptimal training methods used in current practice.

Under review as a conference paper at ICLR 2020
A BAYES-OPTIMAL VIEW ON ADVERSARIAL EXAMPLES
Anonymous authors Paper under double-blind review
Original "male"
Adversarial "female" Asymmetric dataset
Adversarial "female" Symmetric dataset Bayes-Optimal
Adversarial "female" Symmetric dataset CNN
Adversarial "female" Symmetric dataset SVM (RBF)
Bayes-Optimal
b
d
Figure I: We analyze conditions on the data distribution under which the Soyes-Optimal classifier may be vulnerable to adversarial attacks and present realistic image datasets for which the Bayes- Optimal classifier can be calculated efficiently. When the data distribution satisfies certain asym- metries, the Bayes-Optimal classifier 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 find robust classifier even when the optimal classifier is robust (d), while large-margin methods often succeed (e).
ABSTRACT
Adversarial attacks 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 ex- trapolation" used by CNNs (Goodfellow al., 2018) along with the geometry high dimensions.
In this paper show that similar attacks can be used against the Bayes- Opttiall classifier for certain class distributions, while for others the optimal classifier is the
robust such attacks. We present analytical results showing conditions data distribution under which all points can be made arbitrarily close to the opti- mal decision boundary and show that this happen even when the classes are easy to separate, when the ideal classifier has smooth decision surface and when the data lies 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 vul- nerable classifier even when the optimal classifier is robust while large-margin methods often find a robust classifier with the exact same training data. Our re- sults suggest that adversarial vulnerability is not unavoidable consequence of machine learning in high dimensions, and may be the result of the specific dis- tributions of commonly used datasets of suboptimal training methods used in current practice.
INTRODUCTION
Perhaps the most intriguing property of modern machine learning methods is their susceptibility to adversarial examples (Szegedy et al. 2014 Goodfellow et al. 2018): for many powerful classifiers it

---

Under review as a conference paper at ICLR 2020
is possible to change the input by imperceptible amount and change the decision of the classifier. While adversarial examples were most famously reported for Neural Network classifiers (Szegedy et al.] 2014), subsequent research has shown that other classifiers can also fall prey to similar at- tacks Goodfflloo et al. 2018). Attempts to make classifiers robust to these attacks have generated tremendous amount of interest (e.g. (Schott et al., (2T9)) and references within), although a recent survey argued that "There has been much work showing that basically all defenses suggested so far in the literature do not substantially increase robustness over undefended neural networks." (Schott et al. 2019)
As first step towards solving the problem, many authors have attempted to understand the source of the failure (Goodfellow et al. 2018] Szegedy et al.) [014]] Tanay & Griffin [016 Fawzi et al. 2018)) Intuitively the failure suggests that the decision surface learned by neural networks is "discontinuous to significant extent", analogous to an attempt to discriminate the rational numbers from the rest of the real numbers (Szegedy et al., a 2014). The most prominent theory suggests that the problem is that neural network classifiers are "unreasonably linear" combined with the fact that they operate in high dimensions (Goodfellow et al. 2018: 2015). In high dimensions the output of a random linear classifier can be changed by making small change in the & norm of an example. (Fawzi et al., 2018) show a connection between the error rate of linear and quadratic classifiers and the adversarial vulnerability and show that linear classifiers in high dimensions must be vulnerable for data that is not linearly separable. (Ford et al., (019) show that adversarial vulnerability is closely related to the lack of generalization to random perturbations and that in high dimensions even moderate failures to generalize to high amounts of noise imply the existence of adversarial examples. |Shamir al. (201)) have also focused on the geometry of high dimensions arguing that adversarial attacks may be a "natural consequence of the geometry of R" with the La (Hamming) metric". Pacobsen al.] (2018) connect the problem of adversarial examples with the excessive invariance modern CNNs to large image transformations. (Zhang et al. (2019) discuss the tradeoff between robustness and accuracy and show a very discontinuous toy distribution where the Bayes-Optime classifier is not robust. Most recently. (Ilyas et al., 2019) have argued that adversarial examples a feature, not bug, and showed that one can in fact obtain information about the true decision boundary from adversarial examples. Their analysis suggests that vulnerability results from the presence of predictive features that are not robust. They presented a synthetic dataset which was constructed to not contain such features, and showed that CNN training on that dataset was robust. In (Nakkiran) 2019) a similar dataset was presented without nonrobust features, but CNN training did lead to non robust classifiers when the dataset was noisy, leading the authors to conclude that "Adversarial Examples are Just Bugs, Too". This result is consistent with Tanay & Griffin (2016) who show that adversarial vulnerability related to overfitting in learning algorithms that are not sufficiently regularized. Similarly, Lyu & Li (2019) show theoretically and experimantally that the the details of the training procedure can significantly change the robustness of CNNs.
In this paper we give an alternative perspective on adversarial examples by focusing on Bayes- Optimal classifiers. We ask: under what conditions on the data distribution will a large fraction of the points be close to the optimal decision boundary? We show that it is easy to construct data distributions which this happens (bottom of figure 2) and seemingly similar distributions which this does not happen (top of figure 2). Contrary previous explanations, adversarial attacks may succeed when the optimal decision surface is continuous and the data does not need to lie in high dimensions. Rather we show that the susceptibility to adversarial examples is related to the pres- ence of asymmetries in the predictive power of different features in the data distribution, and we show analytically that when such asymmetries exist, optimal classifiers will suffer from adversarial examples. We introduce new datasets of realistic images for which the Bayes-Optimal classifier can be calculated efficiently and show that for some of these datasets the optimal classifier is robust to adversarial examples and in others it is not In systematic experiments with datasets where the opti- mal classifier is robust, we show that standard CNN training methods consistently find a non non-robust classifier even though the optimal classifier is robust, while large-margin methods often find a robust classifier using exactly the same training data. Our results suggest that adversarial vulnerability is not an unavoidable consequence of machine learning in high dimensions, and in many cases may be a result of suboptimal training methods.
'The datasets and models will he made publicly available after publication.
2

---

Under review as a conference paper at ICLR 2020
Spherical Gaussians
Elliptical Gaussians
Discrete
Mixtures
h
Figure 2: Top: examples of 2D distribution where the optimal decision boundary is far from the datapoints. Bottom: distribution where the optimal boundary is close many of the datapoints.
2 ANALYSIS: IS THE OPTIMAL CLASSIFIER NECESSARILY ROBUST?
We focus on two class classification problem and denote by (z) the distribution of x when is in the first class, and similarly p2()) for the second class. We assume that p1 (2))) are known and that the two classes have equal priors, the Bayes-Optimas classifier simply classifies x as be- longing to class 1 if Pı (x) > p2 (x) and to class 2 otherwise. It is well known that this classification rule is optimal and no other classification rule can achieve higher accuracy (assuming of course that Pi (I), P2 (z) are correct) (Duda et al. 1973). A textbook example of Bayes-Optimal classification when both classes are generated with Gaussian with the same spherical covariance matrix. in which case the optimal classifier is a linear discriminant which is orthogonal to the difference be- tween the two means (figure2a). to the covariance, then almost all points are far from the decision boundary and so an adversarial attack which only makes small changes to the input will typically fail. But as shown in the bottom of figure 2 there are other examples where the decision boundary is close to many of the datapoints and an adversarial attack which only makes small changes to the input will often succeed. What distinguishes these two cases?
this case, the distance between the two means is large relative
To gain intuition, consider the images shown in the left side figure 3 Assume we have infinite examples of images of Cindy Crawford and denote by p1 (I)) the probability of generating an image under this distribution. Denote by p2(#) the probability of generating an image of a different person. Under pı (x) all images have mole, while under (z) this probability is very low. Thus an optimal classifier will assign an extremely high weight to the presence of mole in an image. This means that
by making tiny change in the image and erasing the mole (right side of figure 3 we can drastically change the output of the optimal classifier (and in fact drive P1 (x) down to zero). Note that this is not the same as the standard definition of overfitting (i.e. a difference between performance on the training samples and test samples): even unseen images of Cindy Crawford that are generated from Pi (r()) will have mole present, so giving this feature high weight will not hurt generalization, but will make the classifier susceptible to adversarial attacks. This intuition is similar to that used in the recent work of (Ilyas et al. 2019) who argue that adversarial vulnerability is a feature, not a bug, and results from the presence of predictive features that not robust. The way formalize this intuition, below, is quite different from that of (Ilyas et al. 2019) (whose analysis focused on linear classifiers) and also leads to quite different conclusions.
We first focus on the case where both class distributions are Gaussians, iec. (1()), Pa (2 are both Gaussian with means 11, /22 and covariances Σ,, Ez.
3

---

Under review as a conference paper at ICLR 2020
Figure 3: Intuition behind our analysis. When the distribution of one of the classes includes an extremely predictive feature (e.g. the mole in images of Cindy Crawford), then the optimal classifier assigns this feature an extremely large weight. This means that by changing, just that one feature, an adversary can drastically lower the probability that it be classified correctly, In the text we formalize this intuition.
Observation Let d be a direction of minimal variance under E1 d = arg min E E,d'. Let of be the variance projecting I onto that direction when comes from class 1. 01 - and Eg is full rank then almost any point in class arbitrarily close to the optimal decision surface.
Proof: We denote by d2 d' E2d the variance of the data in direction d under the distribution of the second class p2. Note that by the assumption that Σg is full rank, this variance must be nonzero. We write the vector x: as (f, 8) where / is the projection in direction d and is vector of projections in directions orthogonal to d. We denote by & the projection of 14 in direction d. The decision surface as a function of is a solution to:
1 (
2/2
1 0 03
2
12 1
12
log = log (2gg)((]() - po
o
Now since d' is direction of minimal variance independent under P1 and we can write log li (slt) = log (s). Using the standard equation for conditional Gaussians we see that P2(s|t) is Gaussian with the following means and variances.
be an eigenvector of E1 so that s and f are
14. + (2 (1-12)
Maje
1
Edee = Σ2 D2
(3)
02
where Eg Eg are the appropriate submatrices of the covariance matrix Σg.
As 0 then we can approximate log (oggp()))) with Gaussian with the following means and variances:
Palt
14, + Σg (t1 t2) 2
(4)
Egje
tt 22
(5)
02
Note that now neither the mean nor the variances depend on L. This means that the decision surface for is solution the following equation:
( ( (
12
41 o
1+
2
2 o + log
C(s)
(6)
03
where the right hand side is a constant that does not depend on & or 01. As g1 approaches zero, the solutions of this equation approach 4, And because oi - 0 almost all samples from the first Gaussian will be close to l so moving x by tiny amount in direction d will change the optimal decision.
As can be seen from equation 6 we do not need a to be exactly equal to zero for the decision surface to be close to the datapoints. It is enough for σ to be significantly smaller than the mini- mal variance of Σg. Figures b.e. illustrate this dependence: when the minimal variances both Gaussians is similar then the decision boundary is far from most points (top), but when there is strong asymmetry in the minimal variances then the decision boundary becomes close to the data- points in one of the classes. In (Tanay & Griffin 2016), the existence of directions of small variance
4

---

Under review as a conference paper at ICLR 2020
was suggested as possible explanation for adversarial examples by invoking overfitting: when such directions exist, a linear classifier may fail to learn the optimal decision boundary. Our analysis, on the other hand, is for the Bayes-Optima classifier which by definition does not overfit.
We now assume that the distribution in each class can be represented as a mixture model:
pr(
Σ
where Tik represent the prior probability of component k in ps and Pix. is the probability distribution of that component.
We also assume that within each class, the components are well separated, i.e. that for each datapoint the assignment probabilities put all their mass on one of the components. More formally, denote by gs (x) the assignment probability of datapoint æ to component k:
(2)
(r)(z)) Σ, (()
then we assume that for each æ. 9s (x) = 8(k: (x)) where k (I) is the index of the component that is most likely to have generated under probability (x))) Under this assumption the probability of generating a point x under p1 is simply:
We will also assume that for well separated components, within each distribution, the assigned component does not change when we perturb x by a small amount (x()) = kg (x + +c) where is a small perturbation.
Observation 2: Assume that both classes are generated by well separated Gaussian mixtures. Let Ei be the covariance matrix of the kth Gaussian in the mixture for class 1. If there exists Gaussian j in class such that Σι and Σgj satisfy the asymmetry conditions of observation 1, then almost any point generated by that Gaussian is close the optimal decision boundary.
Proof: We simply apply observation to the two Gaussians, Σi in class 1 and Dا in class 2. By observation 1, we can make all points generated by the Gaussian in class more likely to have been generated by the Gaussian in class 2, by moving a tiny amount. By the well separatedness asssumption, the original Gaussian in class is still more probable than all the other Gaussians in the same class, so the point will now be classified as coming from class 2 by the classifier.
Figures 2i.h illustrate the importance of asymmetry in data generated from a Gaussian Mixture Model. In the top figure, both classes are generated from mixture two Gaussians, whose min- imal variance in the same. In the bottom figure, each class data is generated by mixture of three Gaussians: the two original Gaussian plus a third isotropic Gaussian that has low mixing proportion but very large variance. Once this third Gaussian is present in the other class, the Bayes-Optimal decision surface becomes very close to all points in both classes (except for those generated by the rare, broad Gaussian).
2.1 NON GAUSSIAN DISTRIBUTIONS
A natural question following observation is to what extent the result depends on the Gaussian distribution. To address this, we now consider discrete distributions. We assume that every instance is described by quantized features that can take on discrete number of values. For example, the features can be wavelet coefficients of an image that are discretized into 256 possible values. This means that ()())p2() are simply very large tables that give the probability of observing a particular discrete set of image features given each of the classes. Of course learning such a large table is infeasible without additional assumptions, but recall that we analyzing the Bayes- Optimal case, where we assume P1 (f)). P2( are known.
Observation 3: Assume there exists feature and a quantization level k that pı (f. k) 1. Assume also that for any feature vector f. (f( > 0. Then almost any point in class is one quantization level away from the optimal decision boundary.
5

---

Under review as a conference paper at ICLR 2020
Proof: We again write f t) where is the ith feature and are all other features.
(s t) pi (s)p1 (t]s);
(10)
Now assume that pi (8) approaches 1 for = k and 0 otherwise. This means that for almost any point in class 1 the value of that feature is equal to k. We now change the feature by one quantization
level and obtain new feature vector (š, t) and pı (3,t) p1 (5))p (t] O. On the other hand, by
the assumption p2(8, 1) > so that this point would now be classified as belonging to class 2. D
As in the Gaussian case, we do not need pı (s) to be exactly equal to delta function for the decision surface to be close to most points. It is enough that (1(8) be much smaller than the minimal values of P2 for the decision to be flipped when we replace s with s. Figures [2g.e illustrate this depen- dence. In both cases, the data is sampled from a discrete distribution where the features are simply discretization of the two spatial coordinates into 100 levels each. In other words, and p2 are tables of size 10, 000 and each entry in the table represents the probability of generating a point at one of the 10, 000 possible locations. In the top example, the minimal value of the probability table approximately the same in both classes, while in the bottom example, there is a strong asymmetry and the decision boundary becomes close to all points in one of the classes.
(B)
Observation Assume that both classes are generated by well separated discrete feature distribu- tions. Let Pıs (f) be be the kth table of feature distributions under class 1. If there exists a j in class such that pıa (f), (f).P2,(J) (J) satisfy the asymmetry conditions of observation 2, then almost any point generated by that component is close to the optimal decision boundary.
The proof is identical to the proof of observation 2.
3. DATASETS OF REALISTIC IMAGES WITH EFFICIENT CALCULATION OF THE BAYES-OPTIMAL CLASSIFIER
In order to connect the discussion of optimal classifiers with datsets that can be used with modern classifiers, we introduce new datasets of realistic images of faces and digits for which the Bayes- Optimal classifier can be calculated efficiently. We do this by leveraging recent advances in genera- tive modeling of full images (Goodfellow) 2016; Richardson & Weiss/ 2018).
To create these datasets, we start with labeled training set (e.g. MNIST) with two classes. We then train separate Mixture of Factor Analyzers (MFA) model pi (Ir), (2()) on images from the two classes. The MFA model (Ghahramani et al. 1996) is a standard density model: it models each density as a mixture of Gaussians where the covariance of each Gaussian is the sum of a low rank matrix and a diagonal one (see appendix for details). We now create a new training set by sampling images from the two models, and similarly new test set. Since these datasets were created by sampling from a known model, we can calculate the Bayes-Optima classifier. At the same time, the images are realistic and MFA models have been shown to capture much of the variability of the images in the original data (Richardson & Weiss 2018). The top of figure shows samples from the pi (x),, pa())) when the MFA were learned separately from the "male" and "female" attributes in the CelebA dataset (Liu et al. 2015). More samples from other datasets including digits and faces can be found in the appendix. While these samples are typically somewhat blurred, can be seen they are realistic and highly variable. In fact, in many real world applications one needs to classify somewhat blurry images (e.g. analyzing faces in surveillance videos).
In order to investigate the importance of asymmetry in the variances, we created symmetric and asymmetric variants of these datasets. In the symmetric version, we regularized the MFA so that all covariance matrices had the same minimal variance. In the asymmetric version, we added to each MFA model one additional "outlier" component: it had a diagonal covariance with much larger minimal variance than all the other covariances and mean which is close to the mean of the data.
The advantage of using a MFA model over other generative models such as VAEs or GANs (Kingma) & Welling, 2014 Gulrajani et al. 2017) is that the log likelihood of any image can be calculated efficiently. Specifically we follow (Richardson & Weiss 2018) and find the Gaussian component that is most likely to have generated the image, and then evaluate the likelihood of the image given that Gaussian. We can then use this log likelihood to classify an image as belonging to one of the two classes (e.g. "male" or "female"). Since the data were generated by the assumed distributions,

---

Under review as a conference paper at ICLR 2020
Male/Female Asymmetrie: (L2
0.9)
25
50
100
125
Male/Female Symmetric: (L2 3.3)
25
50
125
Figure 4: We introduce new datasets of realistic images for which the Bayes-Optimal classifier can be calculated efficiently. The vulnerability of the optimal classifier depends the presence of asym- metries. Each result shows the original images, adversarial images and perturbations (magnified for visibility necessary). Histogram of the perturbations in pixel values (0-255) are the right.
this classifier is Bayes-Optimal. Indeed in all datasets created, the accuracy of the classifier was close to 100%. We now asked: is this Bayes-Optimal classifier robust to adversarial attacks?
Unlike our theoretical results, deciding whether or not real classifier is robust not requires an operational definition of what constitutes a "tiny" or "imperceptible" perturbation. We follow the standard practice of calculating the mean 1.2 perturbation we allow the adversary an unlimited budget in attacking the classifiers, and we then measure how large (in terms Euclidean norm) a perturbation was required to cross the decision boundary. The correctly classified
an adversarial attack. In other words,
mean is calculated only over successful attacks, when the original sample and the adversarial example was not. Since this definition sensitive to outliers and the particular choice of Euclidean norm, also examined the histograms of changes made each pixel in the adversarial attack. Finally, we visually inspected the adversarial images.
In all 15 datasets, found that these three methods of defining robustness consistent. For the face images, when the mean I.2 is less than 1.5, then the adversarial images are almost indistinguish- able from the original images, and the vast majority of the pixels in the adversarial images within 5/255 intensity levels from their original value. On the other hand, when the mean L2 is around 3, then the adversarial images perceptually quite different from the original ones, and many pixels differ by more than 5/255 from their original values, Similar definitions of robustness were used in previous reports (Schott al. 2019 Carlini et al.) 2019).
We used simple gradient attack in which we take a small step in the direction of the gradient of the MFA log likelihood (see appendix for details). Similar results are achieved with a standard implementation (Papernot et al. (0166) of the CW-L2 attack (Carlini & Wagner 2017).
As shown in figure 4 the difference between the symmetric datasets and asymmetric datasets is dramatic (see appendix for similar results on other classes). When there exists a large asymmetry between the minimal variances of different Gaussians, the conditions of observation 3 hold, and tiny imperceptible change is sufficient to fool the Bayes-Optimal classifier. However, when all Gaussians have the same minimal variance, the adversary needs to make much larger changes and the adversarial examples become perceptually meaningful.
4 EXPERIMENTS: WHY ARE CNNS SO BRITTLE?
Given our analysis, the fact that modern machine learning methods are often susceptible to tiny adversarial attacks may be due to two very different reasons (figure (5). One reason could be that the data distribution is asymmetric, so that the Bayes-Optimal classifier is not robust, and hence it not surprising that CNN is also not robust. A second possible reason is illustrated in figure Sp: here the data distribution is symmetric and the Bayes-Optimat classifier is robust, yet SGD starting from a bad initial condition finds a brittle classifier. this is the case, then the brittleness is not due the data distribution but rather failure of the learning method. Indeed (Tanay & Griffin

---

Under review as a conference paper at ICLR 2020
Asymmetric distributions
Non- Non-Optimal Learning
Figure 5: Why are CNNs so brittle? Is it because the data distributions are asymmetric that the optimal classifier is also brittle (left) or is due to non optimal learning in cases where the optimal classifier is robust (right)?
2016 Nakkiran 2019) have presented toy distributions where the optimal classifier is robust but suboptimal learning fails to find it.
In order to separate the contribution of the dataset from the estimation method in the vulnerability of machine learning methods, we trained a CNN on samples from all 15 "symmetric" datasets de- scribed in section 3 and measured the vulnerability on the learned CNN. We used the standard CNN implementation available as part of the CleverHans library. We asked: will the CNN find a brittle classifier even though the optimal one is robust?
Results are shown in figure 6 In all 15 cases, the CNN found high accuracy classifier that was vulnerable to small adversarial attacks, even though the optimal classifier is robust. The difference is most dramatic in the celebA tasks, where the CNN adversarial examples are almost indistin- guishable from the original images (examples of the attacks on different datasets are shown in the appendix). In the easier, MNIST tasks, the CNN adversarial perturbations are still significantly smaller than those of the Bayes-Optimal classifier and less perceptually meaningful. While there are many possible architectures and optimization methods for CNNs. did not find any improvement in the CNN robustness in our attempts to change the number of filters, layers, training iterations etc. In particular, (Schmidt et al. 2018 have argued that one needs more training examples achieve robust classification, so we systematically varied the amount of training images (generated dynam- ically each SGD iteration), and found no significant improvement in robustness as we increased the number of training examples up to million examples (see appendix for details). Even adver- sarial training of the CNN (using the method of (Zhang al. 2019h) did not significantly improve robustness.
possible to learn robust classifier for these datasets from finite training data? To answer that question, we then trained linear and RBF support vector machine classifiers on exactly the same datasets. The linear SVM attempts to maximize the margin while maintaining high accuracy, but since the optimal classifier is nonlinear it ends up learning a brittle classifier. More importantly, with an appropriate bandwidth parameter RBF SVMs often find robust classifier when trained on exactly the same data (when the bandwidth parameter is too large, the RBF performs similarly to linear SVM), Returning to figure 5 our results strongly support the hypothesis that for these cases brittleness is due to suboptimal learning methods, even when the data distributions symmetric and the optimal classifier robust.
DISCUSSION
Since the initial discovery of adversarial examples for CNNs there has been much discussion whether they are a "bug" that is specific to neural networks or a "feature" of high dimensional geometry. On the one hand, our results show that even the Bayes-Optima classifier may suscep- tible to tiny adversarial perturbations, and this can happen in low dimensions and when the optimal classification function is smooth. Perhaps more significantly, our analysis has also enabled us to construct realistic datasets for which the Bayes-Optimal classifier is robust. We find that standard CNN training consistently fail to find a robust classifier for these datasets, while aarge-margin meth- ods succeed when training on exactly the same data. This suggests that in some situations, the presence of adversarial examples represents a failure of current, suboptimal, learning methods, rather than being unavoidable property of learning in high dimensions.
8

---

Under review as a conference paper at ICLR 2020
CelebA
MNIST
4.0
3.0
Brown_Hii
Heavy,
2.5
Hiph Cheetbones
2.5
Hala
Hightt Open
2.0
2.0
Smilnng
No Beard
1.5
1.5
Weering Eartings
Wearing Unetic
1.0
Eyeglazzes
1.0
0.5
0.5
0.0
0.0
Bayes Optimal
CNN
Linear SVM
RBF SVM
Bayes Optimal CNN
Linear RBF SVM
Figure 6: Adversarial attack perturbation sizes (mean L2 norm) for different models for all symmet- ric datasets.
We are by no means advocating a return using RBF SVMs rather than CNNs. Rather, we believe that explicit regularization methods for CNNs may enable learning robust classifiers while maintain- ing the power deep architectures. Recent theoretical work on gradient descent methods suggests that they implicitly reward large margin classifiers in both shallow and deep architectures (Soudry) iet al. 2018; Poggio et al. [2017] Lyu & 2019) although convergence to a large margin classifier may require exponential time.
While our experiments have focused on the "symmetric" datasets, where there no tradeoff between accuracy and robustness, there is reason to believe that real datasets will be symmetric rather than asymmetric. As our analysis has shown, if the real datasets do have strong asymmetries, then the Bayes-Optimal classifier will not be robust. Nevertheless, improved learning algorithms should allow us to trade off robustmess and accuracy in a principled manner, as can currently be done in the training of shallow architectures such SVMs. In the appendix, models on real data for the CelebA Male/Female task. Although we cannot calculate the Bayes Optimal classifier, the trend is similar what we saw in the synthetic data: CNNs and Linear SVMs learn very vulnerable models, while the RBF SVM learns classifier that is robust and can only be fooled when the adversary makes perceptually meaningful changes.
show results with trained
In general, when trying to understand a complex effect, it is often useful to disentangle the different causes. The Payes-Optimal perspective on adversarial examples identifies two possible causes: asymmmetries in the datasets and suboptimal learning. Furthermore, it allows to disentangle these two possible causes by creating synthetic datasets which one of the two causes can be clearly implicated. We are optimistic that such approach will be of great use in developing new learning algorithms that are practical and robust.
REFERENCES
Nicholas Carlini and David A. Wagner. Towards evaluating the robustness of neural networks. In 2017 IEEE Symposium on Security and Privacy, SP 2017, San Jose, CA, USA, May 22-26, 2017, pp. 39-57,77777 2017. doi: 10. 10.1109/SP2011..99 URL
/ttt:::://oo..0r//10.110// 10..///.........PP... 22017 2017.
49
Nicholas Carlini, Anish Athalye, Nicolas Papernot, Wieland Brendel, Jonas Rauber, Dimitris Tsipras, Ian J. Goodfellow, Aleksander Madry, and Alexey Kurakin. On evaluating adversarial robustness. CoRR, abs/1902.06705, 2019.
19705
Richard O Duda, Peter Hart, and David G Stork. Pattern classification. Wiley, New York, 1973.
Alhussein Fawzi, Omar Fawzi, and Pascal Frossard. Analysis of classifiers' robustness to adversarial perturbations. Machine Learning, 107(3)488 2018. doi: 10. 10.10077/1199444----66333 URL http:///....o//..11....0/0.3353.
Nicolas Ford, Justin Gilmer, and Ekin D. Cubuk. Adversarial examples are a natural consequence of test error in noise, 2019. URL

---

Under review as a conference paper at ICLR 2020
Zoubin Ghahramani, Geoffrey E Hinton, et al. The EM algorithm for mixtures of factor analyzers. Technical report, Technical Report CRG-TR-96-I University of Toronto, 1996.
Ian Goodfellow. NIPS 2016 tutorial:
Generative adversarial networks. arXiv preprint
arXiv:1701.00160, 2016.
Ian Goodfellow, Patrick McDaniel, and Nicolas Papernot. Making machine learning robust against adversarial inputs. Commun. ACM, 61(7):56 66, June 2018. ISSN 0001-0782. doi: 10.1 145/ 3134599. URL http:://oi...... acm. www.///////o /etp//...11/33345595
lan J. Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015. URL httt:://axxiv.o/
abs/ 1412. 6572
Ishaan Gulrajani, Faruk Ahmed, Martin Arjovsky, Vincent Dumoulin, and Aaron C Courville. Im- proved training of wasserstein GANs. In Advances Neural Information Processing Systems, pp. 5769-5779, 2017.
Trevor Hastie, Saharon Rosset, Robert Tibshirani, and Ji Zhu. The entire regularization path for the support vector machine. Journal of Machine Learning Research, ((Oct):1331-441)) 2004.
Andrew llyas, Shibani Santurkar, Dimitris Tsipras, Logan Engstrom, Brandon Tran, and Aleksander Madry. Adversarial examples are not bugs, they are features. arXiv preprint arXiv:1905.0211 2019.
Jörn-Henrik Jacobsen, Jens Behrmann, Richard S. Zemel, and Matthias Bethge. Excessive invari- ance causes adversarial vulnerability. CoRR, abs/1811.00401, 2018. URL http::/arxiv..
org/abs/1811. 00401
Diederik Kingma and Max Welling. Auto-encoding variational Bayes. International Conference on Learning Representations, 2014.
Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang. Deep learning face attributes in the wild. In Proceedings of International Conference on Computer Vision (ICCV), 2015.
Kaifeng Lyu and Jian Li. Gradient descent maximizes the margin of homogeneous neural networks. CoRR, abs/1906.05889 05890, 2019. URL
wwwpili..rg/a/booo. 1906. 05890
Preetum Nakkiran. A discussion of 'adversarial examples are not bugs, they are features': Adversarial examples are just bugs, too. Distill, 2019. doi: 10.23915/disiil..00195.
Nicolas Papernot, Ian Goodfellow, Ryan Sheatsley, Reuben Feinman, and Patrick McDaniel. clev- erhans vl. 0.0: an adversarial machine learning library. arXiv preprint arXiv:1610.00768 10, 2016.
Tomaso Poggio, Kenji Kawaguchi, Qianli Liao, Brando Miranda, Lorenzo Rosasco, Xavier Boix, Jack Hidary, and Hrushikesh Mhaskar. Theory of deep learning ii:: explaining the non-overfitting puzzle, 2017.
Eitan Richardson and Yair Weiss. On gans and gmms. In 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. 5852-5863, 2018. hRhhttp: 7/papers nips cc cwtppppr//ececccecceeecccc 7826 on gans- and-anndnen
Ludwig Schmidt, Shibani Santurkar, Dimitris Tsipras, Kunal Talwar, and Aleksander Madry. Ad- versarially robust generalization requires more data. CoRR, abs/1804.112885 2018. URL
http:://rxii .rg...orrgggoo www.org///b/////e abs//aas//11 11285
L. Schott, J. Rauber, W. Brendel, and M. Bethge. Towards the first adversarially robust neural network model on mnist. May 2019. URL https :ecttss//arxite http:///wwwww.ooo/////////////// 091 90. pdf
10

---

Under review as a conference paper at ICLR 2020
Adi Shamir, Itay Safran, Eyal Ronen, and Orr Dunkelman. A simple explanation for the existence of adversarial examples with small hamming distance. CoRR, 00s//901.10861,, 2019. URL http:
//
10861
Daniel Soudry, Elad Hoffer, Mor Shpigel Naeson, Suriya Gunasekar, and Nathan Srebro. The im- plicit bias of gradient descent on separable data. J. Mach. Learn. Res., 19:70:1-70:37,200 2018. URL http:/ /mmrr org. wttpg//appes//vs//1Seeee 18m.mmml
Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian J. Goodfel- low, and Rob Fergus. Intriguing properties of neural networks. In 2nd International Conference on Learning Representations, ICLR 2014, Banff, AB, Canada, April 14-16, 2014, Conference Track Proceedings. 2014. wtt.ttpp://axxi.oorr.
tbss/111... 6199
Thomas Tanay and Lewis D. Griffin. A boundary tilting persepective on the phenomenon of ad- versarial examples. CoRR, (Bs//600,,7690, 2016. URL
07690
Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric P. Xing, Laurent El Ghaoui, and Michael Jor- dan. Theoretically principled trade-off between robustness and accuracy. CoRR, abs/ abs/1901 /e///991..056 1901.08573, 2019. URL http:t/t://aae /ttp://awwvv.oraaaa/111......
org
A SYMMETRIC VS. ASYMMETRIC
Figure presents additional examples comparing symmetric and asymmetric datasets and the rela- tive robustness of their Bayes-Optimal classifiers to adversarial examples.
Smiling/NotSmlling Asymmetric: (L2 0.8)
Smiling/ Soilingg Symmetric: (L2 3.1)
0/6 Asymmetric: (I.2 0.5)
Symmetric: (L2 3.0)
O
Figure 7: The vulnerability of the optimal classifier depends on the presence of asymmetries. Each result shows the original images, adversarial images and perturbations (magnified for visibility as necessary). In the symmetric datasets, attacking the optimal classifier requires large and perceptually meanigfull perturbations.
B MODELS
In this section we provide additional information about the different classification models archi- tecture, hyper-parameters and training procedure.
11

---

Under review as a conference paper at ICLR 2020
E
Figure 8: A Mixture of Factor Analyzers (MFA) model for toy data in E2 (sampled 3D helix blue points), The latent dimension is - each component is a Gaussian on a learned 2-dimensional hyperplane with added axis-aligned noise.
B. MFA
A Mixture of Factor Analyzers (MFA) (Ghahramani al. 1996) is Gaussian Mixture Model where each component is a Factor Analyzer parameterized by low rank plus diagonal covariance matrix. MIA provides a good tradeoff between the non-expressive diagonal-covariance model and a full- covariance model, which is too computationally expensive for high-dimennional data such as full images.
The model for single Factor Analyzer component is:
== u N(O, N
(11)
where A is the rectangular factor loading matrix, z is a low-dimensional latent factors vector, f is the mean and is the added noise with diagonal covariance D. This results in the Gaussian distribution x ~ [(H, AAT + the MFA model for toy data.
AAT++)) D). The MFA a mixture of such Gaussians. Figure demonstrates
The MFA model was trained using the code provided by Richardson Weiss 2018 The models are trained using Stochastic Gradient Descent. The training data (CelebA, MNIST) is first split by the desired binary attribute (e.g. Smiling/ Not Smiling) and then a separate MFA model was trained independently for each subset of training samples. Because of imbalance in the number of samples per class in CelebA, we set the number of components as the number of samples divided by 1000. For MNIST used fixed value of 25 components per class. We chose an MFA latent dimension of 10 for CelebA and for MNIST.
To allow attacking the MFA model with standard adversarial attacks such as CW-L2, we imple- mented it TensorFlow as a standard CleverHans (Papernot et al. 2016) model.
B.2 BAYES-OPTIMAL
The MFA model is the Bayes-Optimal classifier when the data sampled from the model. We modified the trained MFA models to define pairs of Bayes-optimal models.
single Factor Analyzer component defined by mean vector 14, a rectangular matrix and per-pixel noise variance D (diagonal). The component distribution is then N(p, AAT + D).
For the symmetric models, we simply fixed noise variance values in D to a small value (std of 0.001). For the asymmetric case we added two outlier components (one for each class) that are modifications from the dataset global mean directions low-variance: We performed PCA over the entire dataset and took the eigenvector for the 50th largest eigenvalue this direction, where the mean of one outlier is the positive direction and the mean of the other in the negative one. We set A = 0 and D 0.5 for both outliers, making them spherical gaussians around the means.
12

---

Under review as a conference paper at ICLR 2020
B.3 CNN
We used the reference fully-convolutional network implemented as part of the CleverHans library (Mode/Al(Comwolutiondd) The architecture consists of 2D convolution layers with kernel size of 3 followed by Leaky ReLU activations and average pooling. We set the basic number of fil- ters (nb filters) to the minimal required number that achieves 100% classification accuracy on our datasets. All other hyper-parameters were left at their default values (calculated automatically by the library according to the image resolution), Optimization method is Adam. The reported results not sensitive to the specific architecture (e.g. number of layers, channel depth) and training parameters.
B.4 LINEAR SVM
We used the standard 2-class linear SVC implementation provided by sklearn (no pyyee--arametted Linear SVM is trained directly on the vectorized image samples. The learned model consists of weight vector W and a scalar bias b. The decision for a sample æ is simply signWW=x. +b..
B.5 RBF SVM
We used sklearn for the Radial Basis Function (RBF) kernel SVM as well. A single hyper- prpeemerrreeter required, y 1. We chose the highest value that still provides high classification accuracy.
C ATTACKS
C.I CW-L2
The Carlini & Wagner L2 attack (Carlini Wagner 2017) is a recommended strong attack that minimizes the perturbation L2 norm. The attack minimizes weighted combination of classifi- cation loss with the perturbation L2 size. The relative weight is a parameter that is found using a binary-search. We used the CleverHans implementation with the following hyper-parameters. 500 iterations, 3 binary-searches and learning rate 0.01.
C.2 LD-GRAD
Since the MFA and SVM models provides a simple closed-form expression for the likelihood and its gradient, we implemented simple and fast version gradient-attack for these models. Our attack performs multiple (typically 3) steps in the direction of the gradient of the difference in log- likelihood between the source and target Gaussian components. We compute the required step size to cross the gap in the log-likelihooe some of the experiments with the (much slower) CW-L2 attack and verified that the results are similar (i.e. models that are shown to be robust to the LD-Grad attack are also robust to the CW-L2 attack with similar perturbation magnitudes).
between the source and the target components. We repeated
D ADDITIONAL RESULTS
In this section we provide additional experimental results for the different datasets, attributes and models. Table lists the clean and adversarial classification accuracy of all models for all datasets and attributes.
D.1 CNN LONGER TRAINING AND WIDER NETWORKS
As shown in Figure 6 unlike the Bayes-optimal and the SVM RBF classifiers, CNNs trained on the symmetric datasets are vulnerable to adversarial examples (required perturbation size small). Here investigate the effect of longer training with additional training samples and of wider networks.
We trained a CNN with convolution layers and tested different values for the width (number of output channels) of the first layer. Each second layer has stride of 2 and the width doubled, so
13

---

Under review as a conference paper at ICLR 2020
Dataset Attribute
Bayes-Optimal
CNN
Linear SVM
RBF SVM
CelebA Bangs
100% (0%
100% (0%)
100% (0%)
96% (18%)
CelebA Black Hair
100% (0%)
98% (2%)
100% (0%)
96% (26%)
CelebA Brown Hair
100% (0%)
99% (1%)
100% (0%)
86% (16%)
CelebA Heavy Makeup
100% (0%)
100% (0%)
100% (0%)
96% (14%)
CelebA High Cheekbones
100% (0%)
100% (0%)
100% (0%)
96% (10%)
CelebA Male
100% (0%)
100% (0%)
100% (0%)
100% (8%)
CelebA / Mouth Slightly Open
100% (0%)
100% (0%)
100% (0%)
94% (8%)
CelebA No Beard
100% (0%)
100% (0%)
100% (0%)
94% (10%)
CelebA Smiling
100% (0%)
100% (0%)
100% (0%)
96% (10%)
CelebA Wearing Earrings
100% (0%)
99% (1%)
100% (0%)
94% (16%)
CelebA / Wearing Lipstick
100% (0%)
100% (0%)
100% (0%)
92% (18%)
CelebA Eyeglasses
100% (0%)
100% (0%)
100% (0%)
100% (22%)
MNIST / 06
100% (0%)
100% (0%)
100% (0%)
100% (4%)
MNIST
100% (0%)
100% (0%)
100% (0%)
100% (7%)
MNIST 45
100% (0%)
100% (0%)
100% (0%)
100% (8%)
Table 1: Classification accuracy values for the different symmetrie datasets for the original and adversarial (in brackets) samples.
4.0
4.0
3.5
3.5
Male
Male
Smiling
Smiling
2.0
2.0
Heavyy Makeup
Mean
Heatyy Makeup
1.5
Eyeglasses
2.5
Eyeglasses
1000
Trraining Samples
layer filbers)
Figure 9: Training wider CNNs with more samples does not improve the adversarial robustness.
The Bayes-optimal classifiers are shown as dashed lines.
the width of the final layer was 16 times that of the first layer. To test the effect of longer training with samples, modified the training procedure that samples from the symmetric dataset were generated dynamically. We trained the networks for total of million samples, in mini-batches of 50. The results are shown in Figure indicating that wider networks and more data does not improve robustness.
D.2 INCREASING THE DATA NOISE VARIANCE
As described in Appendix B. in the main experiments fixed the noise standard deviation (the added diagonal part of the MFA covariance) of all Gaussians in the model that generated the sym- metric dataset to increased the noise std to 50 times the original value. At these levels (Figure 10 left) the noise is clearly visible in the data samples. As be seen (Figure 10 right), the effect on the robustness of trained CNN models is minor. As expected, the Bayes-Optimal model does not change its decision boundary and remains robust.
0.001. Here verify that results not sensitive this value. We
D.3 ROBUST (ADVERSARIAL) CNN TRAINING
To test the effect of adversarial training on the CNN model for the symmetric dataset, we used the method proposed by Zhang et al. (2019), which the NeurIPS 2018 Adversarial Vision Challenge (Robust Model Track). Although slightly more robust, the robustified CNN is still far from the Bayes-optimal model (Figure 11).
14

---

Under review as a conference paper at ICLR 2020
3.5
Moen etteck
2.5
Male
Smiling
Bangs
Heavy, Makeup
1.5
Eyaglasses
0.0
0.001
0.010
0.025
0.050
standard deviation
Figure 10: Increasing the noise standard deviation by a factor of 50 has no effect on the robustness of the Bayes- Bayes-Optimal Optimal models (dashed lines) and only small effect on the robustness CNNs trained on the noisy samples.
Henay Histrup
Cyeglumme
2,5
2.0
1.5
0.0
Bayos-optimal
CNN
Rolust-CNN
Figure 11: The effect of robust (adversarial) training per Zhang et 2019 with 3 (favouring robustness), shown together with the Bayes-optimal for reference.
D.4 RESULTS ON REAL DATA
D.4.1 TRAINING ON SYMMETRIC DATA AND TESTING REAL DATA
To estimate how close our symmetric datasets are to the real datasets, we tested the CNNs that were trained on the symmetric dataset real test samples and compared the test accuracy that of CNNs that were trained on the real training data. As can be seen in Table 2 there is an average accuracy reduction of just 5%, indicating that the symmetric datasets are that far from the original data.
D.4.2 TRAINING AND TESTING ON REAL DATA
Our experiments on the symmetric data (Figure 6) showed that, on all tested datasets, SVM with RBF kernel manage to find decision boundary that is almost as robust the optimal one. while CNNs and Linear SVMs find (probably due to two different reasons) a vulnerable boundary, which be attacked with much smaller perturbation size.
One can ask, do these results represent the real data? To answer this questions we trained the three models of the real datasets CelebA Male/Female and indeed, shown in Figure 12 the
Dataset / Attribute
Real Train Data
Symmetric Train Data
CelebA Male
92,3%
88%
CelebA / Smiling
89.5%
85.6%
CelebA / Bangs
94.3%
90.4%
CelebA / Heavy Makeup
86.3%
79.9%
CelebA Eyeglasses
98.4%
91.7%
Table 2: Real test images classification accuracy for CNNs trained on real training data vs CNNs trained on samples from the symmetric dataset. Accuracy shown for the robust CNNs.
15

---

Under review as a conference paper at ICLR 2020
Original Image
Adversarial CNN
Adversarial Linear SVM
Adversarial RBF SVM
Model:
CNN
Lin. SVM
RBE SVM
Clean accuracy
96.3%
90.0%
89.3%
Adversarial accuracy
3.7%
16% 10%
Mean attack 1.2
0.59
0.15
2.99
Figure 12: Results of trained models and adversarial attacks on real data.
Orig
3.34
Optimal
0.86
CNN
0.50
Lin. SVM
2,23
RBF SVM
Figure 13: Samples, perturbations and histograms for CelebA attribute 'Smiling"
results are similar to the synthetic symmetric dataset CNN and Linear SVM are vulnerable and RBF SVM is robust.
Note that unlike our proposed symmetric data, in which the "gold standard" optimal classifier is both robust and accurate, on real data, which may contains variance asymmetries, different models might reach different trade-off points between accuracy and robustness. In particular, it is known that RBF SVM accuracy is highly influenced by the hyperparameters C, y and we performed only minimal search to obtain these results, In future work, it would be interesting to explore the full regularization path as in (Hastie et al. 2004).
D.5 ADDITIONAL RESULTS FOR THE SYMMETRIC DATASET
show original and adversarial samples and perturbations as well as histograms of the perturbations in pixel values for all models in different symmetric datasets (the number at the top of each histogram is the mean perturbation L2 over all test samples).
Figures 13 18
16

---

Under review as a conference paper at ICLR 2020
Orig
Optimal
CNN
Lin. SVM
2.39
RBF SVM
Figure 14: Samples, perturbations and histograms for CelebA attribute 'Eyeglasses'
Orig
3.15
Optimal
0.58
CNN
0.31
Lin. SVM
2.53
RBF SVM
Figure 15: Samples, perturbations and histograms for CelebA attribute 'No Beard'
Orig
Optimal
CNN
Lin. SVM
RBF SVM
Figure 16: Samples, perturbations and histograms for CelebA attribute 'Heavy Makeup"
17

---

Under review as a conference paper at ICLR 2020
0
0
6
6
Orig
6
6
0
2.98
Optimal
6
1.84
CNN
6
1.29
Lin. SVM
2.89
RBF SVM
Figure 17: Samples, perturbations and histograms for MNIST digits 0 vs. 6
4
4
5
5
Orig
3,16
9
5
4
5
Optimal
4
4
5
2.22
CNN
4
4
5
1.02
Lin. SVM
2.83
RBF SVM
Figure 18: Samples, perturbations and histograms for MNIST digits 4 vs. 5
18


Reviews:
[{"review_id": "rJxFL5b0YB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "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.\n\nThe 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.\n\n1. 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:\n   - 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.\n\n   - 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.\n\n    - 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.\n\n    - 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.\n\n    - 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. \n\n2. Discussion/interpretation of the results: \n    - 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.\n\n    - 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?) \n\n3. Experimental setup: \n    - 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. \n\n    - 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.\n\n4. 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.\n\nOverall, 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.", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}, {"review_id": "SyxjYpuXqH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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 paper studies the adversarial robustness of the Bayes-optimal classifier (i.e., optimal for the standard \"benign\" risk). To do so, the authors construct various synthetic distributions and show that in some cases the Bayes-optimal classifier is also adversarially robust, while in other cases it is not. In the main experiment, the authors construct two high-dimensional synthetic distributions of human faces via a generative model. In one of the distributions, even the Bayes-optimal classifier is vulnerable to adversarial examples. In the other distribution (where the Bayes-optimal classifier is robust), CNNs do not achieve high robustness while other approaches such as an RBF SVM are more robust.\n\nOverall I find the experiment in the paper interesting, but it is unclear how representative the experiments are for adversarial robustness on real data. There are natural follow-up experiments that would shed some light on this question and could substantially strengthen the paper. Hence I unfortunately recommend to reject the paper at this point and encourage the authors to deepen their experimental investigation. For instance, the following points would be relevant:\n\n- Does adversarial training / robust optimization result in a robust neural network on the synthetic data distribution where the Bayes-optimal classifier is robust (and the RBF SVM is more robust than a CNN)?\n\n- Do RBF SVMs also exhibit higher adversarial robustness than CNNs on comparable real datasets? This would indicate to what extent the synthetic distributions are representative of real data w.r.t. adversarial robustness.\n\n\nAdditional comments:\n\n- Briefly defining the MFA model in the main text would provide helpful context.\n\n- A few more details about the experiments could be informative in the main text, e.g., the CNN architecture and the accuracies the various methods achieve.\n\n- An end-of-proof symbol at the end of proofs would be helpful to the reader.\n\n- Is there an index i missing in \\pi in Equation (8)?\n\n- Is the probability given in (9) exact? Gaussians are supported on all of R^d, so even a Gaussian component far away will contribute to the probability of a point under p_1, at least a (very) small amount.\n\n- The proof of Observation 2 is more a sketch. It would be good to include a more formal proof in the appendix.", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HJeV9gIkqr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "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 paper analyzed the adversarial examples from the Bayes-optimal view. Specifically, the authors analyzed the relationship between the symmetry of covariance of data distribution and the amount of data which are close to the decision boundary. The authors proved that when the covariance of data distribution is asymmetric, a large amount of data will be close to the decision boundary (easy to be attacked). The authors also provided the new datasets which is easy to compute for the bayes-optimal classifier so as to verify the effect of symmetry of covariance on vulnerability of classifier. Moreover, the paper indicated that the vulnerability of CNNs is due to asymmetric distributions or non-optimal learning. \n\nIt is interesting that the paper investigated the adversarial examples from the Bayes-optimal view. However, there are some drawbacks: \n\n1.\tThe motivation of this paper is not clear to me. In other words, what is the benefit of analyzing the adversarial examples from the Bayes-optimal viewpoint, since Bayes model mentioned in this paper is easy to attack. I am not fully convinced by the presentation of the paper.\n\n2.\tThe theorem or the observation in the paper appears too straightforward. And the ‘observation 1’is not general. The authors may need to consider more general cases that when the standard deviation of eigen value of covariance matrix is large, the Bayes model will be easily attacked. (not just the case that one of eigen value is zero). \n\n3.\tOne minor point, it appears somewhat strange that “observations” were proved. It is better to change observations to theorems or lemmas.\n\n4.\tThe authors tried to explain directly the vulnerability of CNN in a same way. However, CNN is a totally different model compared with the Bayes model (one is a discriminative model and the other is a generative model). For generative models, the classification boundary is closely related to all training samples. Therefore, the variance of data distribution is important for attack. For discriminative models, the decision boundary is related to local information. It may not be proper to analyze CNN in the way same as the Bayes model. This should be further clarified and discussed. \n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies how adversarial robustness and Bayes optimality relate in a simple gaussian mixture setting. The paper received two recommendations for rejection and one weak accept. One of the central complaints was whether the study had any bearing on "real world" adversarial examples. I think this is a fair concern, given how limited the model appears on the surface, although perhaps the model is a good model of any local "piece" of a decision boundary in a real problem. That said, I do not agree with the strong rejection (1) in most places. The weak reject asked for some experiments. The revision produced these experiments, but I'm not sure how convincing these are since only one robust training method was used, and it's not clear that it's the best one could do among SOTA methods. For whatever reason, the reviewers did not update their scores. I am not certain that they reviewed the revision, despite my prodding.
Decision: Reject