Empirically Measuring Concentration: Fundamental Limits on Intrinsic Robustness
arXiv:1905.12202
Abstract
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 (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 and perturbations of several image classification benchmarks. Code for our experiments is available at https://github.com/xiaozhanguva/Measure-Concentration.
arXiv comment17 pages, 3 figures, 5 tables; NeurIPS final version
References in corpus (11)
- Scikit-learn: Machine Learning in Python
- Wild Patterns: Ten Years After the Rise of Adversarial Machine Learning
- Provable defenses against adversarial examples via the convex outer adversarial polytope
- Certified Defenses against Adversarial Examples
- Towards the first adversarially robust neural network model on MNIST
- Motivating the Rules of the Game for Adversarial Example Research
- Adversarial vulnerability for any classifier
- Adversarial Training Can Hurt Generalization
- VC Classes are Adversarially Robustly Learnable, but Only Improperly
- Lower Bounds on Adversarial Robustness from Optimal Transport
- Understanding the (un)interpretability of natural image distributions using generative models