Empirically Measuring Concentration: Fundamental Limits on Intrinsic Robustness
This work addresses the gap between theoretical adversarial robustness limits and practical applications for machine learning researchers and practitioners, though it is incremental as it builds on prior theoretical results.
The paper tackles the problem of determining whether theoretical limits on adversarial robustness apply to real image datasets by developing a method to empirically measure dataset concentration, and it estimates the intrinsic robustness of several image classification benchmarks to l∞ and l2 perturbations.
Many recent works have shown that adversarial examples that fool classifiers can be found by minimally perturbing a normal input. Recent theoretical results, starting with Gilmer et al. (2018b), show that if the inputs are drawn from a concentrated metric probability space, then adversarial examples with small perturbation are inevitable. A concentrated space has the property that any subset with $Ω(1)$ (e.g., 1/100) measure, according to the imposed distribution, has small distance to almost all (e.g., 99/100) of the points in the space. It is not clear, however, whether these theoretical results apply to actual distributions such as images. This paper presents a method for empirically measuring and bounding the concentration of a concrete dataset which is proven to converge to the actual concentration. We use it to empirically estimate the intrinsic robustness to $\ell_\infty$ and $\ell_2$ perturbations of several image classification benchmarks. Code for our experiments is available at https://github.com/xiaozhanguva/Measure-Concentration.