PaperlayerView exact revision on arXiv

Source-linked AI summary

Adversarially Robust Generalization Requires More Data

Ludwig Schmidt, Shibani Santurkar, Dimitris Tsipras, Kunal Talwar, Aleksander Mądry

arXiv:1804.11285v2cs.LGcs.NEstat.ML

TL;DR

Adversarially robust classification requires stronger generalization than standard classification, but its statistical requirements are not well understood. The paper analyzes sample complexity in simple distributional models and evaluates the resulting picture on image datasets. It finds that robust learning can require significantly more data, with the gap applying independently of the algorithm or model family and appearing empirically as well.

  • Problem

    The paper addresses the limited understanding of how adversarially robust generalization compares statistically with standard generalization.

  • Method

    The paper derives information-theoretic sample-complexity bounds in two distributional models and complements them with dataset-subsampling experiments on MNIST, CIFAR10, and SVHN.

  • Results

    Robust generalization requires significantly more samples than standard generalization in a Gaussian model for every model and learning algorithm, with analogous gaps observed in image experiments.

  • Takeaways & Limitations

    The difficulty of training robust classifiers may partly stem from inherently larger sample complexity, while data properties and classifier nonlinearities can affect the gap.

Abstract

from arXiv · show

Machine learning models are often susceptible to adversarial perturbations of their inputs. Even small perturbations can cause state-of-the-art classifiers with high "standard" accuracy to produce an incorrect prediction with high confidence. To better understand this phenomenon, we study adversarially robust learning from the viewpoint of generalization. We show that already in a simple natural data model, the sample complexity of robust learning can be significantly larger than that of "standard" learning. This gap is information theoretic and holds irrespective of the training algorithm or the model family. We complement our theoretical results with experiments on popular image classification datasets and show that a similar gap exists here as well. We postulate that the difficulty of training robust classifiers stems, at least partially, from this inherently larger sample complexity.

1 Introduction

Adversarial robustness is a stronger generalization requirement than standard accuracy, and its sample complexity can be substantially larger. The paper studies this gap theoretically and experimentally, finding that it can persist across simple models and image datasets.

  • Motivation: Adversarial examples can cause highly accurate models to misclassify inputs with high confidence, motivating robustness as a generalization problem.The paper distinguishes standard accuracy from robustness to small input perturbations.
  • Research question: The paper asks how the sample complexity of standard generalization compares with adversarially robust generalization.It frames sample complexity as the statistical question of when robust classifiers can be learned.
  • Theoretical results: Even for a mixture of two class-conditional Gaussians, robust generalization requires significantly more samples than standard generalization, regardless of the model or learning algorithm.The lower bound is information theoretic, so algorithmic improvements cannot remove this limitation.
  • Theoretical results: For binary-feature data, linear classifiers retain the larger robust sample complexity, whereas thresholding can recover the smaller standard-generalization sample complexity.This result helps explain why ℓ∞-robustness can be easier on mostly binary datasets such as MNIST.
  • Empirical evidence: Experiments show that standard accuracy can plateau before adversarial accuracy, while CIFAR10 exhibits a much larger robust generalization gap than MNIST.On CIFAR10, the model reaches 47% adversarial test accuracy despite fitting the adversarially perturbed training set; MNIST reaches around 90% adversarial accuracy with a relatively small gap.
  • Implications: The results suggest that insufficient dataset size may fundamentally limit robust training on datasets such as CIFAR10, and that adversarial examples need not reflect a defect of a particular classifier.In the simple data model, adversarial examples can occur for any learning approach even when standard accuracy is high.

2 Theoretical Results

The paper studies adversarially robust generalization in simple Gaussian and Bernoulli models, showing that robustness can require substantially more samples than standard generalization. The gap is information-theoretic in the Gaussian model, while thresholding can reduce it in the Bernoulli model and on MNIST.

  • Theoretical setup: The theoretical analysis uses two simple distributional models to compare standard and ℓ∞-robust sample complexity.The models are a mixture of two spherical Gaussians and a Bernoulli model.
  • Experiments: On MNIST, adding an explicit thresholding layer significantly reduces robust-training sample complexity and yields nearly state-of-the-art robustness at ε = 0.1.The improvement requires no further change to the model architecture or training algorithm.
  • Gaussian model: In the Gaussian model, standard classification can achieve error at most 1% from a single sample, whereas robust classification requires significantly more samples.The robust classifier can be obtained with sufficient data when ε is bounded by a small constant.
  • Gaussian model: The Gaussian lower bound applies to every learning algorithm and shows that robust sample complexity exceeds standard sample complexity by a polynomial factor in dimension d.The bound is nearly tight in the stated regime and remains relevant for restricted adversaries using one perturbation per class.
  • Bernoulli model: In the Bernoulli model, linear classifiers also require many samples for small robust error, but nonlinear thresholding can substantially improve robustness.Both models have similar standard generalization behavior, yet their robust sample complexities differ substantially.

3 Lower Bounds for the Gaussian Model

The Gaussian-model lower bound shows that no learning algorithm can generally obtain high ℓ∞-robust accuracy from too few samples. The proof constructs a transferable perturbation that makes posterior class distributions sufficiently similar to create unavoidable error.

  • Lower-bound statement: The main theorem lower-bounds expected robust error for any learning algorithm, regardless of its computational power.The result also implies a minimax robust-error lower bound over unknown model parameters.
  • Interpretation: The lower bound is information-theoretic: even an unrestricted learning procedure cannot avoid the robust-error barrier when the sample size is insufficient.The proof fixes an arbitrary algorithm and analyzes its expected robust classification error.
  • Transferability: A single perturbation applies across learning algorithms and causes a constant fraction of fresh examples to be misclassified.This establishes transferability across examples, architectures, and learning procedures.
  • Proof idea: Given the samples, the posterior class distributions are Gaussians with opposite means and equal variance, and the adversary exploits their similarity.The proof shifts both class posteriors toward a centered Gaussian while controlling the relevant classification-set measures.

4 Lower Bounds for the Bernoulli Model

The Bernoulli model separates linear and nonlinear robust learning: linear classifiers face a larger sample requirement, whereas thresholding can remove the effect of ℓ∞ perturbations. This contrasts with the Gaussian model despite similar standard generalization behavior.

  • Scope of the lower bound: The Bernoulli lower bound applies only to linear classifiers, because nonlinear classifiers can achieve significantly improved robustness in this model.The proof analyzes uncertainty in the estimated class-vector coordinates and relates prediction to the classifier’s ℓ1 norm.
  • Linear robustness: For linear classifiers, the relevant ℓ∞-robustness scale is Θ(τ), and small robust error is impossible when ε > 3τ.The analysis focuses on the regime τ = Θ(d^-1/4).
  • Thresholding: Thresholding maps each coordinate to its sign and, for ε < 1, undoes any ℓ∞-bounded adversary’s action.The operation is applied element-wise before the linear classifier.

5 Experiments

Experiments on MNIST, CIFAR-10, and SVHN show that robust generalization generally needs more training data than standard generalization. On MNIST, explicitly encoded thresholding filters substantially reduce the samples needed for robust generalization.

  • Experimental setup: Experiments on MNIST, CIFAR-10, and SVHN evaluate adversarially robust generalization across varying training-set sizes.Models use standard convolutional architectures or ResNet, with PGD-based ℓ∞ adversarial training and evaluation.
  • Experimental setup: Training subsets are class-balanced random subsamples nested so that each larger dataset contains the preceding one.Performance is evaluated across test perturbation magnitudes and maximized over training perturbations and model sizes.
  • Sample complexity: For any fixed test accuracy, robust generalization requires significantly more samples than standard generalization.This pattern is observed across the three datasets, with SVHN additionally showing that natural accuracy plateaus earlier than adversarial accuracy.
  • Thresholding experiments: Adding explicit thresholding filters significantly reduces the number of samples needed for good adversarial generalization on MNIST.The thresholding layer uses two ReLU channels based on εtrain; the effect is reported for both naturally and adversarially trained networks.
  • Thresholding experiments: On CIFAR-10, thresholding filters produce no significant difference from the standard architecture.The authors relate this result to thresholding helping primarily for approximately binary datasets.

6 Related Work

Related work explains adversarial examples through classifier limits, fixed-model analyses, robustness conditions, or other theoretical frameworks. This paper differs by studying finite-sample generalization and the inherent sample complexity of robust learning.

  • Positioning: The paper’s main distinction from prior theoretical work is its focus on adversarially robust generalization and finite-sample effects.Much prior work studies robustness without learning or in the infinite-sample limit.
  • Algorithm-independent analysis: Unlike guarantees for nearest-neighbor classifiers, the paper studies inherent robust-learning sample complexity independently of the learning algorithm.Its results hold for finite sample sizes, whereas the cited nearest-neighbor results are asymptotic.
  • Theoretical scope: Unlike analyses of fixed classifiers or specific neural-network settings, this work gives upper and lower sample-complexity bounds for robust generalization.The authors frame adversarial examples as potentially arising from statistical generalization rather than necessarily from a concrete classifier model.
  • Positioning: The paper differs from population-level impossibility results by studying generalization from finite training data rather than assuming robustness is impossible for every hypothesis.It contrasts its setting with bounds independent of training data and with adversaries that can increase loss for any hypothesis.
  • Margin-based theory: Standard margin-based bounds do not demonstrate a gap between robust and benign sample complexity in the studied distributional models.In the Gaussian example, such bounds can already suggest large standard-learning complexity, obscuring the distinction.
  • Robust statistics: Robust statistics addresses corruption of training data, which is distinct from the adversarial-perturbation robustness studied here.The cited robust-statistics work is described as orthogonal to the paper’s questions.

7 Discussion and Future Directions

The paper argues that adversarial robustness depends on the interaction between classifier, data distribution, and perturbation set, while identifying several boundaries and open directions for its results.

  • Discussion: Robustness depends on the underlying data distribution: linear classifiers are optimal in the Gaussian model, whereas nonlinearities help on MNIST and Bernoulli data.The paper concludes that defenses should be tailored to specific datasets rather than relying on one broad approach.
  • Discussion: The Gaussian lower bound suggests that strong ℓ∞-robustness may require a sample complexity increase polynomial in dimension for real-image settings.The authors note that smaller noise in real images or additional prior information could make robust classification easier.
  • Scope: The paper studies test-time adversarial perturbations with matching pre-adversary training and test distributions, not every robustness or distribution-shift setting.The authors note that distribution-shift robustness is another relevant setup and that their proof can transfer in a stated case.
  • Future Directions: The experiments and theory motivate studying less adversarial perturbations, such as rotations and translations, in benign settings related to transfer learning and domain adaptation.The paper identifies sample complexity for different perturbation sets as an important direction for future work.
  • Future Directions: The results directly cover two concrete distributional models, leaving broader distribution classes and the properties that make robust generalization hard or easy open.The authors view the simple models as informative but not comprehensive.
  • Future Directions: Larger gaps between standard and robust sample complexity remain open, especially when robust separability holds and trivial impossibility gaps are excluded.For sufficiently large perturbations, data may cease to be robustly separable, making the robust problem impossible.

A.1 Upper bounds

The upper-bound analysis studies standard and robust generalization in the Gaussian model using the class-weighted sample mean. It shows that sufficient samples yield robust classifiers, whereas standard classification can already succeed with very little data.

  • A.1 Upper bounds: The analysis uses Gaussian concentration to control the sample mean and its alignment with the unknown mean vector.The class-weighted samples are Gaussian, and their average is analyzed through tail bounds for Gaussian norms and inner products.
  • A.1 Upper bounds: The class-weighted sample mean defines a linear classifier whose standard classification error is bounded through its inner product with the Gaussian mean.The proof combines concentration of the sample mean with a lemma relating mean alignment to classification accuracy.
  • A.1 Upper bounds: A single sample suffices for the stated standard-generalization bound for the Gaussian linear classifier.The single-sample classifier uses the normalized labeled example as its weight vector.
  • A.1 Upper bounds: Robust error is bounded by relating adversarial perturbations to the classifier’s margin and dual norm, then applying the sample-mean concentration result.The robust bound is formulated for ℓp perturbations and specialized to ℓ∞ robustness in the subsequent theorem.
  • A.1 Upper bounds: The Gaussian upper bound establishes that the normalized class-weighted sample mean achieves ℓ∞-robust classification guarantees when the perturbation radius satisfies the theorem’s stated condition.The result holds with the theorem’s stated high-probability guarantee and error bound.

A.2 Lower bound

The lower-bound analysis applies to any learning algorithm in the Gaussian model. It shows that adversarially robust generalization remains difficult even when the learner and hypothesis class are unrestricted.

  • A.2 Lower bound: The theorem is simplified into a form directly comparable with the Gaussian upper bound, establishing the paper’s lower-bound separation between standard and robust learning.The comparison is the stated purpose of the corollary simplification.
  • A.2 Lower bound: The main lower bound analyzes the expected ℓ∞-robust classification error of an arbitrary learning algorithm trained on Gaussian-model samples.The algorithm is represented as a function mapping samples to a binary classifier.
  • A.2 Lower bound: The proof rewrites labeled Gaussian samples as class-adjusted observations, allowing expectations over labels and the unknown parameter to be rearranged.This produces a posterior-Gaussian calculation for the unknown mean conditioned on the observations.
  • A.2 Lower bound: The lower-bound argument conditions on the observed data, treats the classifier’s decision regions as fixed, and evaluates their Gaussian probability under the posterior-induced distribution.Complementary decision regions are used to relate the two class cases.
  • A.2 Lower bound: The conditional sample mean has a Gaussian distribution whose covariance reflects both observation noise and the number of samples.Integrating over the Gaussian parameter yields the marginal distribution used in the final bound.

B.1 Upper bounds

The Bernoulli-model upper bounds show that a classifier formed from a single labeled sample can already generalize well under suitable conditions. The proof uses concentration and inner-product bounds to control classification error.

  • B.1 Upper bounds: The upper-bound proofs center z around its mean and apply sub-Gaussian concentration to control deviations of weighted coordinate sums.The centered vector has zero-mean sub-Gaussian coordinates, enabling the required tail bounds.
  • B.1 Upper bounds: The analysis relates the inner product of a linear classifier with the unknown mean vector to its classification accuracy.Lemma 26 supplies this bridge after the sample-dependent inner-product bounds are established.
  • B.1 Upper bounds: A single-sample classifier is defined in the direction of z = yx and achieves a bounded classification error with high probability.The bound is formalized through Theorem 27 and simplified in Corollary 28.
  • B.1 Upper bounds: Corollary 28 simplifies the theorem to a generalization guarantee from a single sample in the Bernoulli model.The corollary directly yields the corresponding main-text theorem.

B.2 Lower bounds

The lower-bound analysis shows that linear classifiers require many samples to achieve adversarial robustness in the Bernoulli model. For perturbations beyond the relevant regime, robust low-error linear classification is impossible regardless of sample count.

  • B.2 Lower bounds: Any linear classifier-learning algorithm requires many samples to achieve robust generalization in the Bernoulli model.The main lower bound is stated for algorithms receiving n samples and producing a linear classifier.
  • B.2 Lower bounds: The lower-bound proof controls the likelihood ratio of the latent parameter using conditional probabilities and concentration inequalities.The argument assumes τ ≤ 1/4 and, in an intermediate bound, n ≤ 1/τ^2.
  • B.2 Lower bounds: For ε > 3τ, no linear classifier can achieve small robust classification error, regardless of the number of samples.Thus the meaningful robustness regime for linear classifiers is ε = O(τ).
  • B.2 Lower bounds: The proof uses posterior uncertainty about each coordinate of θ⋆ to show that the learned classifier’s alignment with θ⋆ is small relative to its ℓ1 norm.The argument connects coordinate uncertainty to the adversarial geometry through ℓ1–ℓ∞ duality.
  • B.2 Lower bounds: ℓ1–ℓ∞ duality gives an adversarial perturbation of size ε∥w∥1, which can force misclassification when the learned margin is insufficient.The resulting event occurs with probability at least 1 − γ under the theorem’s conditions.

C Omitted Figures

Figure 4 compares performance across datasets, training perturbation sizes, and testing perturbation sizes. Natural training favors natural accuracy, whereas training with the largest considered perturbation favors adversarial performance.

  • C Omitted Figures: For each dataset and training ε, the experiments report classifier performance across testing ε values.The figure organizes the comparison by training and evaluation perturbation strengths.
  • C Omitted Figures: Natural training achieves the best performance on natural examples.
  • C Omitted Figures: Training with the largest considered ε_train achieves the best adversarial performance.
Loading 1804.11285v2…