Empirically Measuring Concentration: Fundamental Limits on Intrinsic Robustness

Saeed Mahloujifar, Xiao Zhang, Mohammad Mahmoody, David Evans

Abstract: Many recent works have shown that adversarial examples that fool classifiers can be found by minimally perturbing a normal input. Recent theoretical results show that if the inputs are drawn from a concentrated metric probability space, then adversarial examples with small perturbation are inevitable. 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.

Introduction

In the ongoing "arms race" of adversarial machine learning, theoretical work has suggested a sobering possibility: if a data distribution is "concentrated," adversarial examples might be mathematically inevitable for any classifier with even minimal error. However, these theories typically rely on idealized mathematical shapes like high-dimensional spheres. This paper addresses whether real-world image datasets are actually concentrated enough to make robustness impossible by establishing fundamental, data-dependent limits on classifier robustness.

Methodology

The authors propose a framework to algorithmically estimate the concentration function of a distribution using a finite set of samples. To make the search through high-dimensional space tractable, they restrict their search to specific "geometric collections" of subsets:

  • $\ell_\infty$ perturbations: Complements of unions of hyperrectangles.
  • $\ell_2$ perturbations: Unions of balls.

The paper provides a mathematical proof (Theorem 3.5) showing that as sample size and subset complexity increase, the empirical estimate converges to the true concentration. In practice, they use heuristic searches—such as $k$-means clustering for hyperrectangles—to find the most robust regions of the data.

Sensitivity of empirical risk estimates to the initial covered percentage (q) and the number of hyperrectangles (T).

Key Results and the "Robustness Gap"

The most significant takeaway is the discovery of a large "robustness gap" between current state-of-the-art (SOTA) robust models and the theoretical intrinsic limits.

Comparison of empirical adversarial risk between state-of-the-art robust models and the intrinsic limits (Ours) found in this study.
  • MNIST is "Tight": On MNIST, the best robust models are relatively close to the theoretical limit for $\ell_\infty$ perturbations (10.70% vs 8.28%). This suggests that for simpler datasets, we may be approaching the best possible robustness.
  • CIFAR-10 Room to Grow: On CIFAR-10, the gap is massive. The theoretical limit suggests an adversarial risk of ~29%, yet the best models at the time achieved only ~53%. This implies that current vulnerabilities are not solely due to the concentration of measure, and better training techniques could significantly improve robustness.
  • $\ell_2$ Disparity: The results for $\ell_2$ on MNIST are even more striking, showing a potential limit of ~2% risk compared to the 20% achieved by models at the time.

Limitations and Future Work

While the paper proves a gap exists, it doesn't explain why models cannot yet reach these limits. The current search methods are heuristics; while effective, they provide an upper bound that might be looser than the true concentration. Future research is needed to optimize these search algorithms and determine if the bottleneck lies in model architecture, training algorithms, or the metrics themselves (as $\ell_p$ norms do not perfectly capture human perception).

Summary updated

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 $\Omega(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.
BibTeX
@inproceedings{mahloujifar2019empirically,
  author = {Saeed Mahloujifar and Xiao Zhang and Mohammad Mahmoody and David Evans},
  title = {{Empirically Measuring Concentration: Fundamental Limits on Intrinsic Robustness}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=G2Gp1WjM66g},
}
Figure