Interactive demo · Probabilistic Machine Learning: Advanced Topics · Chapter 19

Adversarial examples and the dimension of the input

Suppose the errors of a classifier near a clean input x0 form a half-space. Add Gaussian noise N(0, σ²I) in n dimensions: the noisy input lands in the error set with probability μ, whatever n is, because only the one-dimensional projection on the normal of the half-space matters, and that projection is N(0, σ²). The distance to the half-space is therefore d = −σ Φ−1(μ) (19.52), independent of n. But the noise vector itself has length about σ√n. The nearest error (the adversarial example) is closer than a typical noisy input by the factor σ√n / d, which grows without bound with the dimension.

Input dimension n

Noise sd σ

Error rate under noise μ

Try these

The distances are exact formulas. The histograms are 2000 simulated noise vectors: the projection on the normal is drawn from N(0, σ²) exactly; the length is σ times the square root of a chi-square variable with n degrees of freedom (exact for n ≤ 50, Wilson-Hilferty approximation above).

A real classifier: logistic regression on MNIST 3 versus 8 (784 pixels), worst-case l-infinity attack

For a linear model the worst-case margin is exact: the prediction survives every perturbation of l-infinity size ε iff y f(x) > ε‖w‖1, while random sign noise moves the score by only about ε‖w‖2 (normal approximation, computed from 50 quantiles of the test margins). Models are trained on 4000 images by adversarial training with the stated ε (closed-form inner maximum); accuracy is measured on 1500 test images, pixel values not clipped.

In the lecture notes