Source-linked AI summary
Adversarial Spheres
Justin Gilmer, Luke Metz, Fartash Faghri, Samuel S. Schoenholz, Maithra Raghu, Martin Wattenberg, Ian Goodfellow
TL;DR
Adversarial examples are observed in vision models, but their cause remains poorly understood. This paper studies a two-concentric-sphere task, proves an error–robustness relationship, and finds that trained networks approach its theoretical bound.
Problem
Vision models can classify most sampled images correctly while nearby visually similar inputs are misclassified, and the cause of this phenomenon remains poorly understood.
Source: §1 · p. 1Method
Results
Takeaways & Limitations
On this dataset, the theory makes vulnerability to small perturbations a consequence of the amount of test error and points to reducing that error to increase robustness.
Source: §7 · p. 8The relationship between generalization error and adversarial-example frequency may be more complicated on real-world datasets; on MNIST, observed distance and an assumption-free impossibility bound differ.
Source: §6 · p. 8
Abstract
from arXiv · showhide
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.
1 Introduction
The paper studies whether adversarial examples can arise from high-dimensional data-manifold geometry together with small but nonzero error, using classification between two concentric spheres as a tractable setting. It proves a relationship between error rate and distance to the nearest error, and reports that trained networks approach the theoretical bound.
1 Introduction
- The authors investigate high-dimensional manifold geometry and nonzero error as a possible explanation, studying two concentric spheres where the distribution and learned decision boundary can be characterized analytically.The sphere task is intended as a simplified setting for investigating the hypothesis.Source: §1 · p. 2
- Several trained models exhibit nearby misclassified inputs even when test error is below 1 in 10 million, including when adversarial search is restricted to the data manifold.The paper reports that most randomly chosen points are correctly classified yet close to an incorrectly classified input.Source: §1 · p. 2
- For this dataset, any model with error on a small constant fraction of the manifold is vulnerable to adversarial perturbations of size O(1/sqrt(n)).The paper bounds average distance to nearest error in terms of error rate.Source: §1 · p. 2
- Neural networks trained on the dataset approach the theoretical bound, so linearly increasing average distance to nearest error requires a significant decrease in classification error.The upper bound also implies that, for this dataset, significantly increasing adversarial robustness requires reducing test error.Source: §1 · p. 2
1.1 Related Work
- Unlike prior synthetic-dataset impossibility results, this work studies the relationship between out-of-sample error and l2 robustness, which it identifies as a first.The cited prior result applies even to perfect classifiers; this work instead bounds l2 robustness in terms of out-of-sample error rates.Source: §1.1 · p. 2
2 The Concentric Spheres Dataset
The paper defines a synthetic classification task on two concentric spherical shells and uses its controlled distribution to study adversarial examples. It also introduces a manifold-constrained attack to find nearby errors while remaining on the data support.
2 The Concentric Spheres Dataset
- The dataset samples points with equal probability from spheres of radii 1 and R=1.3, labeling them by radius.The distribution is uniform over its support, and input dimension can vary to control task difficulty.Source: §2 · p. 3
- The shells simplify analysis because the distribution is mathematically specified and models can be designed to learn a perfectly separating decision boundary.The dataset also permits uniform sampling and dimension-based control of difficulty.Source: §2 · p. 3
- The authors chose R=1.3 arbitrarily, did not explore how sphere separation relates to adversarial examples in detail, and restricted data to the shells for simplicity.These choices limit the settings explored by the dataset.Source: §2 · p. 3
2.1 Finding Adversarial Examples on the Data Manifold
- The manifold attack maximizes loss while constraining the perturbed input to retain its original norm, keeping it in the data support and on the same class.The attack uses 1,000 projected-gradient steps at step size 0.01 and stops at the first error when estimating distance to a nearby error.Source: §2.1 · p. 3
- Nearest-error distance is estimated with projected gradient descent because finding the nearest error is generally NP-hard; full-length runs instead seek worst-case examples.In the full-length setting, the attack may travel far along the sphere from the starting point.Source: §2.1 · p. 3
3 Adversarial Examples for a Deep ReLU Network
In a 500-dimensional ReLU-network experiment, adversarial errors were found on the data manifold despite no errors in 20 million evaluation samples. The observed errors were rare yet close to sampled points, and the phenomenon was not found by the attack in lower dimensions.
3 Adversarial Examples for a Deep ReLU Network
- Despite zero errors in 20 million evaluation samples, the trained model had errors discoverable by the manifold attack.The experiment used a two-hidden-layer ReLU network with 1,000 hidden units and input dimension 500.Source: §3 · p. 3
- A 2D slice along two orthogonal worst-case adversarial directions shows the entire outer-sphere slice misclassified, although the error region has exceedingly small volume in high dimensions.The figure contrasts random directions with adversarial directions; the manifold is black, the max-margin boundary red, and inner-sphere classifications green.Source: §3 · p. 4, Figure 1 · p. 4
- 0.18 was the mean l2 distance to the nearest error on the inner sphere, versus 1.25 for the nearest pair among 10,000 random inner-sphere samples.The misclassifications were extremely rare but appeared close to randomly sampled points.Source: §3 · p. 4
- The attack found no errors for the same model trained with n=2 or for tested dimensions below 100, which does not establish that adversarial examples do not exist there.The n=2 model was trained on 100 samples.Source: §3 · p. 4
4 Analytic Forms for a Simpler Network
The quadratic network provides an analyzable ellipsoid decision boundary, letting the authors connect its parameters to errors on the two spheres. Their analysis and experiments show that very low error can coexist with many incorrect parameters, and that continued average-loss minimization can restore adversarial examples.
4 Analytic Forms for a Simpler Network
- The quadratic network is a single-hidden-layer model with square activation, no hidden-layer bias, and summed hidden activations.With hidden dimension h, it has n · h + 2 learnable parameters; its ellipsoid boundary can be analyzed through a rotated input vector and scalar parameters.Source: §4 · p. 4
- The network has perfect accuracy only when every α_i lies in [1/R^2, 1]; any α_i outside that interval creates errors on the inner or outer sphere.An α_i > 1 creates inner-sphere errors, while an α_i < 1/R^2 creates outer-sphere errors.Source: §4 · p. 5
- With N = 10^6, 325 of 500 learned α_i fell outside the perfect-accuracy interval despite no errors among 10 million sampled points from either sphere.The ellipsoid decision boundary was badly warped in many dimensions; a CLT estimate put this model's error rate at approximately 10^-20.Source: §4 · p. 5
- From a perfect initialization, continued training lowers average test loss while worsening worst-case loss, and adversarial examples reappear after 1,000 steps.The authors attribute this divergence to average sigmoid cross-entropy loss not directly tracking model accuracy.Source: §4 · p. 5, Figure 2 · p. 5
4.1 Analytic Estimates of the Error Rate
- A Gaussian approximation based on the α_i shows that many parameter settings can yield very low but nonzero error rates.The authors use this approximation because it is simple and exact values are unnecessary for the section's purpose.Source: §4.1 · pp. 5–6
- When α_i are near (1 + R^-2)/2 and their variance is not too high, the model can remain extremely accurate even though 80% of its α_i are incorrect.For a typical sample, the model sums incorrect numbers together and obtains the correct answer.Source: §4.1 · p. 6
- The number of α_i settings that maintain good accuracy increases dramatically with input dimension.The authors suggest this flexibility may carry over to image datasets, where networks could learn feature correlations without human-level task understanding.Source: §4.1 · p. 6
5 A Small Amount of Classification Error Implies Local Adversarial Examples
The section proves that test error on the inner sphere bounds the average distance to the nearest error, regardless of the model. In experiments, three trained architectures approach the theoretical optimum, while increasing dimension makes the optimal distance shrink at fixed error-set measure.
5 A Small Amount of Classification Error Implies Local Adversarial Examples
- For inner-sphere accuracy p in [0.5, 1.0), the theorem bounds average nearest-error distance by d(E) ≤ O(Φ^-1(p)/√n), independent of the model.Here E is the set of misclassified inner-sphere points and µ(E) = 1 − p.Source: §5 · p. 6
- The error set of fixed measure that maximizes d(E) is a spherical cap, yet it must extend to the equator as dimension increases.Because sphere mass concentrates near the equator, the cap can have small measure while still approaching it, causing d(E) to shrink.Source: §5 · p. 6, Figure 3 · p. 7
- Across three architectures trained at d = 500, measured d(E) stayed close to the theoretical optimum for the observed error rate.The study used five training-set sizes and estimated error from 10^6 random samples; distances were estimated using PGD on the data manifold.Source: §5 · p. 6, Figure 4 · p. 7
- Despite their different architectures, the networks showed similar relationships between µ(E) and d(E), including an 8-layer ReLU network with 29 million parameters.The authors interpret this as evidence that the networks' decision-boundary geometry is similar.Source: §5 · p. 7
6 Implications for Real World Datasets
The sphere result links adversarial vulnerability to test error, but early MNIST evidence suggests the relationship may be more complicated on real-world data. The paper leaves transfer to other datasets open.
6 Implications for Real World Datasets
- For the idealized sphere dataset, reducing adversarial examples requires reducing generalization error; most errors are also adversarial relative to some example point.For a typical incorrectly classified point, a small perturbation can cause a correct classification, so the authors argue errors have no identifying marker of tampering or special construction.Source: §6 · p. 7
- The authors consider a similar result plausible for anisotropic Gaussian data with large variances across sufficiently many dimensions.They relate the sphere dataset to a standard Gaussian distribution of examples from a class, while describing real-world transfer as an open question.Source: §6 · p. 8
- On MNIST, a hypothetical set has µ(E) = .01 and d(E) = 6.59, while a vanilla CNN has µ(E) = .007 and d(E) = 1.3.The hypothetical set is a top-PCA-aligned halfspace, not an error set achieved by a machine-learning model; the gap leaves room to improve robustness at current out-of-sample error rates.Source: §6 · p. 8
- If similar results hold on real-world datasets, robustness would still be possible, but would require improved generalization.The authors note that early MNIST experiments suggest the relationship between generalization error and adversarial-example frequency may be more complicated.Source: §6 · p. 8
7 Conclusion and Takeaways
On the concentric-sphere dataset, several neural-network architectures approach a model-independent bound linking test error to distance from the nearest error. The paper discusses implications for robustness and examines how distance behaves during training.
7 Conclusion and Takeaways
- Several neural-network architectures closely match the theoretical upper bound relating test error µ(E) to average distance d(E) on the concentric-sphere dataset.The authors describe the bound as independent of the model and report that trained architectures' error sets approach it.Source: §7 · p. 8
- For the sphere dataset, the only way to significantly increase robustness to small perturbations is to significantly reduce µ(E).The authors frame the theorem as reducing the question of vulnerability to the question of why a small amount of classification error remains.Source: §7 · p. 8
- The authors present the sphere result as a counterexample to prior hypotheses and say similar bounds elsewhere would require better generalization, not make defense impossible.They report room for further MNIST robustness improvement at current out-of-sample error rates and call for investigation on other datasets.Source: §7 · p. 8
A Inspecting the Distribution Over Distances
- d(E) is the primary metric; because distances are tightly concentrated, its mean approximates the largest ε with 50% l2 robustness.The authors cite Figure A.1 for the concentration of distances.Source: A Inspecting the Distribution Over… · p. 10
- For n < 100, models improve until the attack algorithm finds no errors, after which Figure B.2 shows no points.Figure B.2 visualizes d(E) during training.Source: Figure B.2 · p. 11
- With n = 500, the ReLU network's out-of-sample cross-entropy falls below 10^-9, yet d(E) plateaus around .18 while errors remain.Figure B.3 shows the loss and distance over training; the caption states the low loss is not due to over-fitting.Source: Figure B.3 · p. 11
B Additional Results on Training
Training measurements show adversarial distance plateaus at small values even as the network becomes highly accurate. The quadratic network’s decision boundary can be expressed as an n-dimensional ellipsoid.
B Additional Results on Training
- For n = 500, the 2-layer ReLU network’s d(E) plateaus around .17 while its out-of-sample cross-entropy loss falls below 10^-9.The earlier training measurements report a plateau around .18 for n = 500 and around .7 for n = 100; attacks found no errors for n < 100, which does not establish that none exist.Source: B Additional Results on Training · p. 11
C The Decision Boundary of the Quadratic Network
- The quadratic network’s decision boundary is an n-dimensional ellipsoid.Its logit is simplified using the SVD of W1, whose matrix maps inputs to the hidden layer; w and b are scalars.Source: C The Decision Boundary of the… · p. 11
- Writing z = V^T x rotates the input, and the distribution of z is the same as that of x.The resulting decision boundary is a rotation of the expression in the coordinates of x.Source: C The Decision Boundary of the… · p. 12
D Estimating the Accuracy with the Central Limit Theorem
The section estimates quadratic-network accuracy using a central limit theorem approximation. It starts from a uniformly sampled point on the unit sphere and rewrites the calculation using Gaussian samples.
D Estimating the Accuracy with the Central Limit Theorem
- A uniform point z on the n-dimensional unit sphere can be generated by normalizing coordinates sampled independently from N(0, 1).This lets the accuracy calculation be rewritten using the normalized Gaussian vector.Source: D Estimating the Accuracy with the… · p. 12
- For sufficiently large n, the sum X is approximated by a normal distribution determined by its first two moments.The supplied passage states X ∼ N(µ, σ^2), then computes those moments separately.Source: D Estimating the Accuracy with the… · p. 12
- The accompanying projection plot relates the fraction k/n of input dimensions used by a classifier to its error rate.Its caption notes that high-dimensional inputs can permit high accuracy while most of the input is ignored.Source: Figure E.4 · p. 13
E A Model Can Be Extremely Accurate While Ignoring Most of the Input
The quadratic-network analysis shows that strong generalization can coexist with a model that misuses individual input contributions. A simplified model illustrates that high estimated accuracy can be achieved while ignoring many dimensions.
E A Model Can Be Extremely Accurate While Ignoring Most of the Input
- Theoretical analysis showed that a quadratic network can generalize impressively while fundamentally misunderstanding the task: on a typical example, it sums incorrect numbers together and obtains the correct answer.Source: E A Model Can Be Extremely Accurate… · p. 13
- For n = 2000, the simplified model can achieve estimated accuracy of 10^-14 while ignoring 62% of the input.The model uses k dimensions and a threshold b, with b chosen optimally for k.Source: E A Model Can Be Extremely Accurate… · p. 13
- A 1000-hidden-node quadratic network at n = 2000 has estimated generalization errors of 10^-21 on the inner sphere and 10^-9 on the outer sphere despite being half the size required for zero error.The section suggests that very low test error may require a smaller network than zero test error.Source: E A Model Can Be Extremely Accurate… · p. 13
F Proof of Theorem 5.1
The proof sketch bounds the average distance to a fixed-measure error set by considering spherical caps, which maximize that distance. A Gaussian approximation and empirical sampling are used to estimate the cap-distance relationship.
F Proof of Theorem 5.1
- Among error sets of a given measure on the sphere, a cap maximizes the average distance to the error set.A cap is the intersection of the sphere with a halfspace.Source: F Proof of Theorem 5.1 · p. 13
- As n grows, a single coordinate of a point on the sphere approaches N(0, 1/n), enabling a Gaussian approximation to the cap calculation.The approximation is empirically checked in Figure F.5.Source: F Proof of Theorem 5.1 · p. 13, Figure F.5 · p. 14
- Sampling 10^6 points on the sphere, the authors found that Φ^-1(µ(E))/√n closely matches empirical average distances to spherical caps.The empirical estimates and the function are plotted as the blue and black lines, respectively, in Figure 4.Source: F Proof of Theorem 5.1 · p. 14
G Does a variant of Theorem 5.1 hold on MNIST?
On MNIST, a constructed error set has measure 0.01 and average distance 6.59, showing that an error-rate-only bound like Theorem 5.1 cannot hold universally there. The construction also indicates room to improve adversarial robustness without reducing test error.
G Does a variant of Theorem 5.1 hold on MNIST?
- Testing whether Theorem 5.1 extends to real data is difficult without a mathematical characterization of the image distribution; the theorem itself assumes only test error, not decision-boundary structure.MNIST is treated as a finite iid sample from a theoretical image distribution.Source: G Does a variant of Theorem 5.1 hold… · pp. 14–15
- On MNIST, a constructed set has µ(E)=.01 and d(E)=6.59, so no universal bound can require d(E)<6.59 for every set of measure .01.The authors suggest stronger bounds may require assumptions about sets arising from model decision boundaries.Source: G Does a variant of Theorem 5.1 hold… · p. 15
- The construction searches halfspaces in R^784 for one with µ(E)=.01 that maximizes d(E), a natural choice for the sphere dataset.For that dataset, maximal-distance sets are halfspaces intersected with the data manifold.Source: G Does a variant of Theorem 5.1 hold… · p. 15
- MNIST's explained variance is dominated by its first 100 PCA directions, so the selected halfspace uses the top PCA coefficient and a threshold placing 1% of training data on one side.The test set estimates µ(E)=.01 and d(E)=6.59 for this construction.Source: G Does a variant of Theorem 5.1 hold… · p. 15
- A standard convolutional network has µ(E)=.007 and d(E)=1.3, while the network reported in [5] has empirically estimated µ(E)=.014 and d(E)=5.0.The true d(E) for [5] is difficult to calculate and may be somewhat smaller.Source: G Does a variant of Theorem 5.1 hold… · p. 15