Empirically Measuring Concentration: Fundamental Limits on Intrinsic Robustness

Saeed Mahloujifar, Xiao Zhang, Mohammad Mahmoody, David Evans

Introduction

In the cat-and-mouse game of adversarial machine learning, researchers continuously develop new "defenses" only to have them broken by novel "attacks." This cycle leads to a fundamental question: Is perfect robustness even possible?

Theoretical research, notably by Gilmer et al. (2018), suggests that adversarial examples—tiny, invisible perturbations that fool AI—might be an inevitable consequence of how data is distributed. If a data distribution is "concentrated," any subset of data (like the error region of a classifier) is mathematically "close" to almost every other point in the space. In such a concentrated space, even a tiny nudge ($\epsilon$) can push a sample into a region where the model fails.

However, these theories were previously applied mostly to abstract mathematical objects like $n$-dimensional spheres. It remained unclear if real-world image data was actually "concentrated," as measuring the density of high-dimensional, unknown distributions is notoriously difficult. This paper bridges that gap by providing the first practical framework to empirically estimate these fundamental limits on intrinsic robustness in real-world datasets.

Methodology

The authors introduce a framework to algorithmically bound the Concentration Function of a dataset. Their approach relies on two main pillars:

  1. Empirical Convergence: They prove that by simultaneously increasing the number of data samples ($m$) and the complexity of the search space ($T$), the concentration of the empirical measure (the available data) converges to the actual concentration of the underlying distribution.
  2. Restricted Subset Collections: To make the search for "error regions" computationally feasible, they limit their search to specific geometric shapes:
  3. For $\ell_\infty$ perturbations, they search the "complement of a union of hyperrectangles."
  4. For $\ell_2$ perturbations, they use a "union of balls."
Adversarial risk vs. number of hyperrectangles T

Algorithmically, the authors employ techniques like k-means clustering and greedy search to find the most "robust" possible error regions. Essentially, the method attempts to "pack" the model's errors into a region that is as far away from the rest of the data as possible. The study evaluates these intrinsic robustness limits on foundational computer vision benchmarks, primarily focusing on MNIST and CIFAR-10.

Key Insights: The Robustness Gap

The most significant takeaway from this work is a reality check on concentration: while concentration of measure does exist in real datasets, it is not the only reason models fail.

By finding a specific region with a certain concentration, the authors provide an upper bound on the concentration function. In the context of security, this acts as a lower bound on the best possible adversarial risk. It establishes a theoretical ceiling, stating that no matter how clever a model is, it will never achieve an adversarial risk lower than this bound.

Crucially, the paper reveals a massive discrepancy between the best "robust" models available today and these theoretical limits.

Key Results

The paper compares their estimated "intrinsic" limits against state-of-the-art robust models (such as those from Madry et al. and Schott et al.):

Comparison of empirical adversarial risk between state-of-the-art models and theoretical limits
  • MNIST ($\ell_\infty = 0.3$): The best robust model had an adversarial risk of 10.70%. The authors found a theoretical limit of 8.28%. This suggests that for MNIST, current architectures are getting relatively close to the "intrinsic" limit.
  • MNIST ($\ell_2 = 1.5$): The gap here is massive. Existing robust models show 20.00% risk, but the authors found a region suggesting the risk could theoretically be as low as 2.12%.
  • CIFAR-10 ($\ell_\infty = 8/255$): The gap widens significantly for more complex data. The best robust model had an adversarial risk of 52.96%, while the authors' estimated limit was only 29.21%.

The Takeaway: For complex datasets like CIFAR-10, current models are failing not because the underlying mathematics of the data distribution dictate they must, but because our current architectures or training methods are not yet capable of reaching the theoretical ceiling of robustness.

Limitations and Future Work

While groundbreaking, the framework has limitations:

  • Tightness of the Bound: The method provides an upper bound on concentration. With finite data and restricted shapes (rectangles/balls), the bound might still be "loose." There could be even more robust regions yet to be found.
  • Search Complexity: Finding the optimal robust error region is a combinatorial problem. The k-means heuristic works well but is not guaranteed to find the absolute global optimum.
  • From Theory to Practice: Knowing a robust classifier exists is entirely different from knowing how to train one. The paper proves there is substantial room for improvement but does not provide the blueprint for building the next generation of robust architectures.

Future work could involve using more complex subset collections—such as those defined by neural networks themselves—to find even tighter bounds, provided the mathematical complexity penalty can be adequately controlled.

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 Ω(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 and L<em>2 and L</em>infinity 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