Adversarial examples from computational constraints

Sébastien Bubeck; Eric Price; Ilya Razenshteyn

Source-linked AI summary

Adversarial examples from computational constraints

Sébastien Bubeck, Eric Price, Ilya Razenshteyn

arXiv:1805.10204v1May 25, 2018stat.MLcs.CCcs.LG

TL;DR

The paper asks whether adversarial vulnerability reflects information-theoretic limits or computational constraints. It combines a general sample-based achievability result with an SQ lower-bound construction, showing robust learning can be easy in principle yet computationally hard. The construction separates efficient non-robust learning from robust learning and motivates adversarial examples as a possible consequence of computational limitations.

Problem
The paper studies why high-dimensional classifiers are vulnerable to adversarial perturbations despite the possibility that robust classifiers exist.
Method
The paper proves a general robust-learning achievability result and constructs high-dimensional distribution pairs with planted moment-matching structure to establish SQ hardness.
Results
Robust learning can require exponentially many SQ queries even with exponential precision, while a related task is efficiently learnable non-robustly and robustly learnable with polynomially many samples.
Takeaways & Limitations
The results support computational constraints as a possible source of adversarial examples rather than information-theoretic impossibility alone.
Takeaways & Limitations
Whether similar hardness holds for natural distributions remains an open problem, and nearest-neighbor methods are outside the SQ model.

Abstract

from arXiv · show

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.

1 Introduction

The paper argues that adversarial vulnerability may reflect computational constraints rather than information-theoretic impossibility. It presents a robust-learning task that is information-theoretically feasible but computationally hard in the SQ model, alongside evidence that robust classifiers can sometimes be found with few samples.

Motivation: Adversarial examples expose a gap between classical and robust classification, whose theoretical understanding remains comparatively rudimentary.The paper frames this gap through four possible explanations, including the absence of robust classifiers, excessive sample requirements, and computational intractability.
Main contributions: The paper’s primary result constructs robust classification tasks that are information-theoretically easy but computationally intractable under the statistical query model.This provides evidence for computational constraints as an explanation of adversarial vulnerability.
Main contributions: The secondary result shows that when a robust classifier exists under standard distributional assumptions, relatively few training examples suffice for an algorithm to find one.The argument uses sample-based elimination and a union bound over an exponentially sized family or net.
Main contributions: A classification task can be learnable in poly(d) time and poly(d) samples, robustly learnable with poly(d) samples for ℓ2 parameter M, yet require exponentially many SQ queries for robustness parameter ε.The same separation holds for ℓ∞ robustness, with diameter O(√d log d).
Limitations and open directions: The authors identify natural-algorithm scope limits: nearest neighbor is outside the SQ model, and hardness for natural distributions remains an open problem.They note that nearest-neighbor class distances have matching polynomially many moments, suggesting exponential sample requirements, but present this as a belief rather than a theorem.
Proof overview: The SQ lower bound uses high-dimensional Gaussian distributions with planted, moment-matching structure in a random k-dimensional subspace.Bounding a non-standard correlation quantity yields hardness, while allowing k ≫ 1 creates the separation needed for a large robustness parameter M.

2 Definitions

This section defines robust loss, robustness, feasibility, and learnability for binary classification tasks over distributions, while relating the framework to ordinary PAC learning.

Setup: The framework restricts attention to binary classifiers over R^d with balanced classes and a fixed norm defining perturbation balls.The perturbation set is B(ε) = {z ∈ R^d : ∥z∥ ≤ ε}.
Robust loss: The ε-robust zero-one loss is one when some perturbation within B(ε) changes the classifier’s output away from the target label.Formally, ℓ_ε(f, x, i) = 1{∃z ∈ B(ε) : f(x + z) ≠ i}.
Robustness: A classifier is (ε, δ)-robust for distributions (D0, D1) when, for each class, its adversarial error probability is at most δ.The definition evaluates robustness separately for both labels.
Learning tasks: A classification task is a family of distribution pairs, and a learning algorithm receives n i.i.d. samples from each class before outputting a classifier.The task is (ε, δ)-robustly learnable with n samples if it succeeds with probability at least 2/3 for every pair in the family.
Relation to PAC learning: Classical PAC learning is recovered by setting ε = 0 and δ = 1/3 in the robust-classification framework.A concept class corresponds to distribution pairs supported on the positive and negative regions of each concept.
Feasibility: Robust feasibility requires every distribution pair in the task to admit an (ε, δ)-robust classifier.The framework denotes one arbitrarily selected robust classifier for each pair by f_D.

3 Robust learning with few samples

The paper shows that robust feasibility can yield sample-efficient robust learning, first for finite classifier families and then for broader distribution families using covering arguments. These results extend to settings where distributions are approximated by generative models.

3.1 Robust empirical risk minimization: Robust feasibility is sufficient for robust learnability, even with relatively few training examples, when a finite classifier set suffices.The algorithm uses empirical risk minimization over the robust loss, though the resulting procedure may be computationally expensive.
3.1 Robust empirical risk minimization: Theorem 3.1 converts (ε, δ)-robust feasibility into (ε, δ + δ′)-robust learnability with a finite-family sample bound.
3.2 Robust covering number: Covering numbers extend the finite-family argument to continuous sets of distributions by replacing explicit enumeration with approximation by a manageable cover.The construction uses paired distances and corresponding neighborhoods to capture both distributional and perturbation structure.
3.2 Robust covering number: Total variation and Wasserstein-based coverings provide alternative ways to preserve robust learnability while allowing a small loss in robustness.The Wasserstein formulation permits moving a small amount of arbitrary mass rather than moving only a small amount of mass arbitrarily.
3.2 Robust covering number: Theorem 3.5 yields robust learnability with parameters (ε − ε′, δ + 2δ′) when robust feasibility is combined with the corresponding covering condition.
3.2 Robust covering number: Distributions approximated by bounded-weight neural generative models have bounded covering numbers, enabling Theorem 3.5 to provide sample-complexity guarantees.The stated setting uses an ℓ-layer network with at most d activations per layer and Lipschitz nonlinearities.

4 Lower bound for the SQ model

The paper constructs high-dimensional distribution pairs that are robustly learnable from few samples but require exponentially many highly precise SQ queries to learn robustly. A simple modification makes non-robust classification efficiently easy while preserving robust-learning hardness.

SQ model: The SQ model supplies approximate expectations of queried functions under each class distribution, with precision τ controlling oracle accuracy.Algorithms query h: X → [0,1] and receive estimates of its expectations under D0 and D1.
Main construction: Theorem 4.1 constructs 2^{dO(1)} distribution pairs in R^d whose robust classifier can be learned from O(d) samples, while a linear non-robust classifier is polynomial-time learnable.The robust-learning guarantee and efficient non-robust learning concern the modified distributions in the theorem.
SQ lower bound: For every ε > ρ, learning an (ε, 0.01)-robust classifier requires at least 2^{dΩ(1)} SQ queries with accuracy as good as 2^{-dΩ(γ)}.For small constant γ, the construction yields robustness to a large constant perturbation; larger robustness can reach Ω(log^{1/2−ε} d) with a weaker query-accuracy lower bound.
Hard family: The hard family is parameterized by near-orthogonal k-dimensional subspaces and one-dimensional distributions matching a Gaussian in their first m moments.The subspace family has size 2^{dΘ(1)}, while the auxiliary distributions have everywhere-positive densities and match N(0,1) in the first m moments.
Making classification non-robustly easy: The construction adds a distinguishing first coordinate, making the classes linearly separable while leaving the robust SQ lower bound intact for perturbations larger than ρ.The robust classifier can instead ignore the first coordinate and use the underlying robust structure, whereas the first coordinate enables trivial non-robust classification.
Norm transfer: A Hadamard transform transfers the construction from ℓ2 to ℓ∞ without changing the robustness parameters, while giving diameter O(√d log d).The transformation uses the relation between transformed ℓ∞ distances and original ℓ2 distances.

5 Conclusion and future directions

The paper argues that adversarial examples may reflect computational constraints rather than information-theoretic impossibility. It concludes with open questions about natural distributions, hardness beyond SQ, and the optimal perturbation scale.

Conclusion: The constructed task has a classifier robust to Euclidean perturbations of size log^{1/2−ε} d, while finding any nontrivial robust classifier is exponentially hard in the SQ model.This hardness holds even with a very high-precision statistical-query oracle and for correctness only slightly better than chance.
Future directions: A central open problem is proving comparable robust-learning hardness for natural distributions, whose definition remains unclear, especially for image data.The authors describe this as particularly challenging because there is no consensus about what natural image distributions should look like.
Future directions: The authors conjecture that their classification task is hard beyond the SQ model and call for studying robust learning across other computational hardness assumptions.They specifically mention cryptographic assumptions as an alternative direction for locating robust learning in the broader hardness landscape.
Future directions: The optimal perturbation scale remains open: the paper asks how quickly Ψ(d) must grow before polynomial-time learning of a stronger robust classifier is guaranteed.The question concerns tasks that are (Ψ(d), 0)-robustly feasible and seeks a polynomial-time (1, 1/3)-robust classifier.

A Proofs of properties of the SQ hard distribution

The construction builds two smooth, moment-matching one-dimensional distributions whose likely supports remain separated, then lifts them to separated sets in a random high-dimensional subspace family.

One-dimensional construction: Adding a small Gaussian perturbation with δ = 1/m^2 produces smooth distributions D_A and D_B that preserve the first m Gaussian moments.The perturbed distributions have everywhere-positive smooth densities and retain the separation properties with high probability.
One-dimensional construction: The sets S_A and S_B are Ω(1/√m)-separated and contain samples from D_A and D_B with probability at least 1 − e^−Ω(m), respectively.The sets are formed by enlarging the scaled supports by a radius Θ(1/√m).
One-dimensional construction: Hermite-root supports for consecutive polynomials are separated by Ω(1/√m), while matching N(0, 1) in at least m moments.The construction uses roots of H_m and H_{m+1}, whose induced discrete distributions match the first 2m − 1 Gaussian moments.
High-dimensional lifting: A family U of k-dimensional subspaces can have pairwise small cross-inner-products, with ε ≤ d^−0.49 and |U| = 2d^Θ(1) for k ≤ d^Ω(1).An ε′-net and a union bound establish the existence of exponentially many suitably separated subspaces.
High-dimensional lifting: For each subspace U, requiring at least 0.9 of the k coordinates to lie in S_A or S_B defines S_U,A and S_U,B.Because many corresponding coordinates are simultaneously separated, the lifted sets are Ω(√(k/m))-separated and capture their respective distributions with probability at least 1 − e^−Ω(km).

B.1 SQ lower bound

The SQ lower bound argues that a random hidden subspace makes the two labeled distributions statistically indistinguishable from a standard Gaussian unless the learner makes exponentially many sufficiently precise queries.

Hardness strategy: The hard-instance argument hides two moment-matching, well-separated distributions inside an unknown random k-dimensional subspace.The goal is to show that SQ algorithms cannot distinguish D_U,A from D_U,B through limited statistical queries.
Indistinguishability: For significantly fewer than the stated query threshold, all queries can be answered as if both D_U,A and D_U,B were N(0, I_d).This holds with high probability over the random choice of U.
Indistinguishability: Under m log d > Ck log m, precision τ = m^−Θ(k) still leaves D_U,A and D_U,B indistinguishable for 2d^Ω(1)m^−O(k) queries.When m^O(k) is at most 2d^σ, the required number of queries becomes 2d^Ω(1).

B.2 Upper bounding pairwise correlations

The correlation analysis bounds pairwise correlations between distributions planted in different subspaces by exploiting Gaussian independence, moment matching, and the small overlap between subspaces.

Correlation decomposition: The proof upper-bounds χ_N(0,I_d)(D_U1,A, D_U2,A) and analogously the corresponding B-distribution correlation.The analysis treats equal and distinct hidden subspaces separately.
Remainder control: The parameter condition m^Cεk ≤ d^−Ω(1) is satisfied when ε = d^−0.49 and m and k are sufficiently small powers of d.This connects the subspace-family construction to the correlation estimates.
Correlation decomposition: For distinct subspaces, vectors are decomposed into projected and residual components whose difference has norm at most ε.A Taylor expansion then relates evaluations in the two subspace coordinate systems.
Remainder control: The remaining terms are bounded using Lemma B.1, Cauchy–Schwarz, Gaussian moment bounds, and the condition (εm^Θ(1)k) = d^−Ω(1).The expansion contains at most m^O(k) terms, enabling the final correlation bound.
Moment cancellations: Gaussian independence and moment matching eliminate terms involving powers up to m, including expectations of t^l a(t) for l ∈ {1, 2, …, m}.These cancellations are applied after factoring expressions associated with independent Gaussian coordinates.

B.3 Setting parameters

Choosing m and k as suitable powers of d makes the robust classifier require exponentially many SQ queries even when query precision is exponentially small.

Parameter choice: For 0 < γ < 1/10, setting m = d^Θ(γ) and choosing k much smaller than m log d / log m yields the desired hardness regime.The construction supports a (k/m)-robust classifier in this parameter setting.
Parameter choice: The SQ lower bound remains exponential in d while query precision can be as good as 2^−d^Ω(γ).Thus, the hardness persists even for highly accurate statistical queries.

C Bound on covering number of generative models

The section bounds covering numbers for bounded-weight neural-network generative models by controlling output sensitivity to weight perturbations and discretizing the parameter space. The resulting cover has size determined by the network depth, width, weight bound, and discretization scale.

Lipschitz control: An ℓ-layer network with at most d activations per layer and Lipschitz nonlinearities has layerwise activation growth bounded by ∥x∥2(dB)^i.The proof uses ∥w_i∥≤∥w_i∥F≤dB for each layer.
Lipschitz control: Changing one weight by ∥w−w′∥1 changes the final-layer activation by at most ∥w−w′∥1·∥x∥2(dB)^(ℓ−1).The bound follows by propagating the perturbation through subsequent layers and extending to multiple coordinates by the triangle inequality.
Cover construction: The parameter cover discretizes [−B,B]^m on the grid αZ, and the induced generative-model cover is the Cartesian product of two such model sets.This construction applies to distribution pairs whose components are each within Wasserstein distance ε of a bounded-weight network distribution.
Cover construction: (1+2B/α)^(2m) is the size of the pair cover, which remains sufficiently small when α=(dB/δ)^−O(ℓ).Nearest-grid parameters differ from the target parameters by at most α in ℓ∞ norm.
Approximation guarantee: The network sensitivity bound implies D(g_w*)∈U_δ,δ(D(g_ŵ)), and the triangle inequality yields D_i∈U_(ε+δ),δ(D(g_ŵ)).This establishes that every target component is represented by a member of the discretized cover at the enlarged approximation radius.