    State of the art computer vision models have been shown to be vulnerable to small adversarial perturbations of the input. In other words, most images in the data distribution are both correctly classified by the model and are very close to a visually similar misclassified image. Despite substantial research interest, the cause of the phenomenon is still poorly understood and remains unsolved. We hypothesize that this counter intuitive behavior is a naturally occurring result of the high dimensional geometry of the data manifold. As a first step towards exploring this hypothesis, we study a simple synthetic dataset of classifying between two concentric high dimensional spheres. For this dataset we show a fundamental tradeoff between the amount of test error and the average distance to nearest error. In particular, we prove that any model which misclassifies a small constant fraction of a sphere will be vulnerable to adversarial perturbations of size $O(1/\sqrt{d})$. Surprisingly, when we train several different architectures on this dataset, all of their error sets naturally approach this theoretical bound. As a result of the theory, the vulnerability of neural networks to small adversarial perturbations is a logical consequence of the amount of test error observed. We hope that our theoretical analysis of this very simple case will point the way forward to explore how the geometry of complex real-world data sets leads to adversarial examples. There has been substantial work demonstrating that standard image models exhibit the following phenomenon: most randomly chosen images from the data distribution are correctly classified and yet are close to a visually similar nearby image which is incorrectly classified BID22 . This is often referred to as the phenomenon of adversarial examples. These adversarially found errors can be constructed to be surprisingly robust, invariant to viewpoint, orientation and scale BID3 . Despite some theoretical work and many proposed defense strategies BID6 BID18 BID20 ) the cause of this phenomenon is still poorly understood.There have been several hypotheses proposed regarding the cause of adversarial examples. We briefly survey some of them here. One common hypothesis is that neural network classifiers are too linear in various regions of the input space, BID17 . Another hypothesis is that adversarial examples are off the data manifold BID2 a; BID16 . BID6 argue that large singular values of internal weight matrices may cause the classifier to be vulnerable to small perturbations of the input.Alongside works endeavoring to explain adversarial examples, others have proposed defenses in order to increase robustness. Some works increase robustness to small perturbations by changing the non-linearities used BID14 , distilling a large network into a small network BID20 , or using regularization BID6 . Other works explore detecting adversarial examples using a second statistical model BID7 BID0 BID11 BID19 . However, many of these methods have been shown to fail BID4 BID7 . Finally, adversarial training has been shown in many instances to increase robustness BID18 BID15 BID22 . Despite some progress on increasing robustness to adversarial perturbations, local errors have still been shown to appear for distances just beyond what is adversarially trained for BID21 . This phenomenon is quite intriguing given that these models are highly accurate on the test set. We hypothesize that this behavior is a naturally occurring result of the high dimensional nature of the data manifold. In order to begin to investigate this hypothesis, we define a simple synthetic task of classifying between two concentric high dimensional spheres. This allows us to study adversarial examples in a setting where the data manifold is well defined mathematically and where we have an analytic characterization of the decision boundary learned by the model. Even more importantly, we can naturally vary the dimension of the data manifold and study the effect of the input dimension on the geometry of the generalization error of neural networks. Our experiments and theoretical analysis on this dataset demonstrate the following:• A similar behavior to that of image models occurs: most randomly chosen points from the data distribution are correctly classified and yet are "close" to an incorrectly classified input. This behavior occurs even when the test error rate is less than 1 in 10 million.• For this dataset, there is a fundamental tradeoff between the amount of generalization error and the average distance to the nearest error. In particular, we show that any model which misclassifies a small constant fraction of the sphere will be vulnerable to adversarial perturbations of size O(1 DISPLAYFORM0 • Neural networks trained on this dataset naturally approach this theoretical optimal tradeoff between the measure of the error set and the average distance to nearest error. This implies that in order to linearly increase the average distance to nearest error, the error rate of the model must decrease exponentially.• We also show that models trained on this dataset may become extremely accurate even when ignoring a large fraction of the input.We conclude with a detailed discussion about the connection between adversarial examples for the sphere and those for image models. In this work we attempted to gain insight into the existence of adversarial examples for image models by studying a simpler synthetic dataset. After training different neural network architectures on this dataset we observe a similar phenomenon to that of image models -most random points in the data distribution are both correctly classified and are close to a misclassified point. We then explained this phenomenon for this particular dataset by proving a theoretical tradeoff between the error rate of a model and the average distance to nearest error independently of the model. We also observed that several different neural network architectures closely match this theoretical bound.Theorem 5.1 is significant because it reduces the question of why models are vulnerable to adversarial examples to the question of why is there a small amount of classification error. It is unclear if anything like theorem 5.1 would hold for an image manifold, and future work should investigate if a similar principal applies. Our work suggests that even a small amount of classification error may sometimes logically force the existence of many adversarial examples. This could explain why fixing the adversarial example problem has been so difficult despite substantial research interest. For example, one recent work uses adversarial training to increase robustness in the L ∞ metric BID18 . Although this did increase the size, , of the perturbation needed to reliably produce an error, local errors still remain for larger than those adversarially trained for BID21 .Several defenses against adversarial examples have been proposed recently which are motivated by the assumption that adversarial examples are off the data manifold BID2 a; BID16 . Our results challenge whether or not this assumption holds in general. As shown in section 3 there are local errors both on and off the data manifold. Our results raise many questions as to whether or not it is possible to completely solve the adversarial example problem without reducing test error to 0. The test error rate of state of the art image models is non-zero, this implies that a constant fraction of the data manifold is misclassified and is the unbiased estimate of µ(E). Perhaps this alone is an indication that local adversarial errors exist.The concentric spheres dataset is an extremely simple problem which is unlikely to capture all of the complexities of the geometry of a natural image manifold. Thus we cannot reach the same conclusions about the nature of adversarial examples for real-world datasets. However, we hope that the insights gained from this very simple case will point the way forward to explore how complex real-world data sets leads to adversarial examples.
We hypothesize that the vulnerability of image models to small adversarial perturbation is a naturally occurring result of the high dimensional geometry of the data manifold. We explore and theoretically prove this hypothesis for a simple synthetic dataset.
{"src": "scitldr-AIC_train", "paper_id": "SyUkxxZ0b"}