How many dimensions are required to find an adversarial example?
This work addresses the problem of understanding adversarial robustness in constrained settings for machine learning practitioners, but it is incremental as it builds on existing theories of adversarial examples.
The paper investigates how adversarial vulnerability depends on the dimension of the subspace an adversary can perturb, showing that the success of PGD attacks increases monotonically with a function of the perturbation budget and the ratio of subspace to ambient dimensions, supporting the idea that adversarial examples are endemic to locally linear models in high-dimensional spaces.
Past work exploring adversarial vulnerability have focused on situations where an adversary can perturb all dimensions of model input. On the other hand, a range of recent works consider the case where either (i) an adversary can perturb a limited number of input parameters or (ii) a subset of modalities in a multimodal problem. In both of these cases, adversarial examples are effectively constrained to a subspace $V$ in the ambient input space $\mathcal{X}$. Motivated by this, in this work we investigate how adversarial vulnerability depends on $\dim(V)$. In particular, we show that the adversarial success of standard PGD attacks with $\ell^p$ norm constraints behaves like a monotonically increasing function of $ε(\frac{\dim(V)}{\dim \mathcal{X}})^{\frac{1}{q}}$ where $ε$ is the perturbation budget and $\frac{1}{p} + \frac{1}{q} =1$, provided $p > 1$ (the case $p=1$ presents additional subtleties which we analyze in some detail). This functional form can be easily derived from a simple toy linear model, and as such our results land further credence to arguments that adversarial examples are endemic to locally linear models on high dimensional spaces.