Adversarial examples from computational constraints

Sébastien Bubeck, Yin Tat Lee, Eric Price, Ilya P. Razenshteyn

In the ongoing arms race between adversarial attackers and defenders, attackers currently have the upper hand. We can train a model to achieve 95% accuracy on datasets like CIFAR-10, but a tiny, human-imperceptible tweak to those same images can often drop that accuracy to below 50%.

Why is this? Is it because robust classifiers simply don't exist? Is it because we don't have enough training data? In this paper, Bubeck et al. propose a more provocative answer: Robust classifiers exist and we have enough data to find them, but doing so is computationally "hard."

This paper argues that adversarial vulnerability may be an unavoidable byproduct of computational constraints. The authors prove that even for tasks that are easy to learn "normally," finding a robust version of that same classifier can require exponential time or the ability to break cryptographic codes.

The Core Problem

The "adversarial example" phenomenon—where small perturbations to an input cause a model to fail—is well-documented but theoretically poorly understood. Researchers generally point to four possible reasons for this fragility:

  1. No robust classifier exists for the task.
  2. We need a massive, unrealistic amount of training data to find one.
  3. Finding the robust classifier is computationally intractable.
  4. We just haven't found the right algorithm yet.

This paper focuses on Hypothesis 3. The authors investigate whether there are classification tasks where a robust solution is "mathematically there" (information-theoretically learnable) but "practically hidden" (computationally impossible to find).

Theoretical Frameworks

Because this is a theoretical paper, it does not rely on standard image benchmarks for its proofs. Instead, it constructs synthetic high-dimensional tasks (such as near-orthogonal subspaces and pseudo-random generator-based distributions) and analyzes them using two primary frameworks:

  • Statistical Query (SQ) Model: This is a standard framework for studying the complexity of learning algorithms. Instead of looking at individual data points, an algorithm asks for the average value of a function over the data distribution. The authors prove an "exponential separation": a task that is easy for a standard algorithm becomes exponentially difficult for any SQ algorithm when robustness is required.
  • Cryptographic Hardness: They construct a classification task based on the Blum-Blum-Shub (BBS) pseudo-random generator. In this setup, a robust classifier exists and is efficient to run if you know a secret key (the prime factors of a large number). Without that key, finding the robust classifier is as hard as factoring large integers—a problem central to modern cryptography.
  • Robust Covering Numbers: To rule out the "lack of data" argument (Hypothesis 2), they use PAC-learning theory and covering numbers to show that if a robust classifier exists, it can generally be found with a number of samples that scales linearly with the dimension ($O(d)$), provided you have infinite computing power.

Key Insights and Ideas

The "Easy to Learn, Hard to Secure" Paradox

The authors demonstrate a task that a simple linear separator (like an SVM) can solve perfectly in polynomial time. However, to make that same separator robust to small perturbations, an algorithm would need to solve a problem that is essentially impossible for modern computers.

1D illustration of interleaved distributions that are easy to distinguish standardly but hard to distinguish robustly, as small perturbations easily cross class boundaries.

Computation as the Bottleneck

The paper shifts the blame from "data quality" to "algorithmic limits." It suggests that the reason our current defenses (like adversarial training) are struggling is that they are trying to solve a computationally hard problem using simple gradient-based tools.

Generative Models and Data

They show that if your data comes from a "well-behaved" generative model (like a GAN with Lipschitz constraints), you don't actually need much data to be robust. This further reinforces that the "missing piece" is likely compute, not more data.

Main Results

  • Exponential SQ Lower Bound: There exists a task that is learnable in polynomial time and samples ($poly(d)$), but requires an exponential number of queries to learn robustly in the SQ model.
  • Cryptographic Separation: Under the quadratic residuosity assumption, they prove there is a task where a robust classifier is efficient to use, but no polynomial-time algorithm can find it from training data.
  • Sample Complexity: They provide a "positive" result showing that for a broad set of tasks, the mere existence of a robust classifier implies it can be found with relatively few training examples—if you are willing to wait an exponential amount of time for the training to finish.

Limitations and Future Directions

The authors acknowledge a significant gap: Natural Distributions.

The "hard" tasks they constructed are mathematical abstractions involving prime factors and high-dimensional geometry. Whether "natural" images (like cats vs. dogs) share these same cryptographic-like properties is still an open question.

The concept of a "natural distribution" is notoriously fuzzy. Future work must determine if the computational barriers identified here are actually what is stopping us from securing real-world vision models, or if those models face different, perhaps simpler, hurdles.

Summary updated

Abstract

Why are classifiers in high dimension vulnerable to “adversarial” perturbations? We show that it is likely not due to information theoretic limitations, but rather it could be due to computational ...
BibTeX
@inproceedings{bubeck2019adversarial,
  author = {Sébastien Bubeck and Yin Tat Lee and Eric Price and Ilya P. Razenshteyn},
  title = {{Adversarial examples from computational constraints}},
  booktitle = {International Conference on Machine Learning},
  year = {2019},
  url = {https://openreview.net/forum?id=B1WrVhbd-B},
}
Figure