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 constraints. First we prove that, for a broad set of classification tasks, the mere existence of a robust classifier implies that it can be found by a possibly exponential-time algorithm with relatively few training examples. Then we give a particular classification task where learning a robust classifier is computationally intractable. More precisely we construct a binary classification task in high dimensional space which is (i) information theoretically easy to learn robustly for large perturbations, (ii) efficiently learnable (non-robustly) by a simple linear separator, (iii) yet is not efficiently robustly learnable, even for small perturbations, by any algorithm in the statistical query (SQ) model. This example gives an exponential separation between classical learning and robust learning in the statistical query model. It suggests that adversarial examples may be an unavoidable byproduct of computational limitations of learning algorithms.
Introduction
Why are even our best neural networks so fragile? Since the discovery of adversarial examples—tiny, imperceptible perturbations that flip a model's prediction—the field has been locked in an arms race. We build better defenses; attackers find subtler holes.
A common intuition is that we simply lack enough data or that the "true" underlying function is just too complex. However, the paper "Adversarial examples from computational constraints" by Sébastien Bubeck, Eric Price, and Ilya Razenshteyn offers a more provocative thesis: Adversarial examples might be an unavoidable byproduct of the fact that our computers aren't infinitely fast.
What Problem Does This Paper Address?
The researchers tackle the "Why?" behind adversarial examples by identifying four potential reasons why all known algorithms seem vulnerable:
- No robust classifier exists for the task.
- We don't have enough training data to find the robust classifier.
- A robust classifier exists and we have enough data, but finding it is computationally impossible in a reasonable timeframe.
- We just haven't found the right algorithm yet.
Most previous research focused on the first two points. This paper provides the first rigorous evidence for the third: that computational constraints alone can prevent us from reaching a robust solution, even when that solution is "right there" in the data.
Methods and The Statistical Query Model
The authors use the Statistical Query (SQ) Model to build their case. This framework analyzes the complexity of learning algorithms by looking at the "average" value of a function over the data distribution rather than individual points. Most standard ML techniques, such as SGD and SVMs, fit into this model.
To prove their point, they mathematically construct a high-dimensional binary classification task where they "plant" a robust pattern in a specific $k$-dimensional subspace of a much larger $d$-dimensional space. They use Hermite polynomials and discretized Gaussians to create two distributions that look identical to a standard Gaussian in their first $m$ moments.
As shown in the figure above, the distributions $D_A$ and $D_B$ are composed of discrete spikes that mimic a standard normal distribution. This moment-matching makes the robust features "invisible" to any algorithm that doesn't spend an exponential amount of time searching for that specific hidden subspace.
Key Insights and Results
- Information vs. Computation: The paper's core realization is that a task can be "information-theoretically easy" but "computationally hard." They show that with just $O(d)$ samples, a robust classifier exists and could be found by an exhaustive (but impossibly slow) search.
- Robustness as a Search Problem: In high dimensions, there are exponentially many ways to separate data. Most are "fragile"—they work on training data but fail under small perturbations. The "robust" separator is like a needle in a haystack; the data tells you it's there, but the SQ model proves you can't find it efficiently.
- The SQ Gap: The authors demonstrate an exponential separation. An algorithm can learn to classify the data with high accuracy in polynomial time, but to learn to do so robustly requires $2^{d^{\Omega(1)}}$ queries.
- Debunking the "More Data" Myth: Theorem 3.1 proves that if a robust classifier exists, it can be found with relatively few samples using Empirical Risk Minimization on robust loss. This suggests that for many tasks, the bottleneck isn't the amount of data, but the algorithm's ability to process it robustly.
Limitations and Future Work
The biggest limitation is that the "hard" task is highly engineered. Proving a similar result for "natural" distributions (like photos of cats vs. dogs) remains difficult because we lack a formal mathematical definition of what a "natural" distribution is. Additionally, while the SQ model covers most of modern ML, it doesn't cover every possible algorithm (e.g., parity learning).
In short, this paper shifts the blame for adversarial vulnerability away from our datasets and onto our silicon. It suggests that being robust might simply be a luxury that polynomial-time algorithms cannot afford.
Summary updated