PaperlayerView exact revision on arXiv

Source-linked AI summary

Certified Adversarial Robustness via Randomized Smoothing

Jeremy M Cohen, Elan Rosenfeld, J. Zico Kolter

arXiv:1902.02918v2cs.LGstat.ML

TL;DR

Modern classifiers remain vulnerable to small adversarial perturbations, while existing certified neural-network defenses struggle to scale. The paper uses Gaussian randomized smoothing to transform arbitrary classifiers into certifiably ℓ2-robust classifiers, proving a tight guarantee and achieving 49% provable ImageNet top-1 accuracy below radius 127/255. Certification relies on Monte Carlo estimation, and large certified radii can require many samples.

  • Problem

    Modern image classifiers are vulnerable to small adversarial perturbations, while existing certified neural-network approaches struggle to scale to large, expressive networks.

  • Method

    Randomized smoothing defines predictions from the most likely class under Gaussian corruptions and uses estimated class probabilities to certify an ℓ2-robust radius.

  • Results

    49% provable top-1 accuracy is achieved on ImageNet under adversarial perturbations with ℓ2 norm less than 127/255, and smoothing is reported as feasible on full-resolution ImageNet.

  • Takeaways & Limitations

    Gaussian smoothing naturally induces certifiable ℓ2 robustness while allowing arbitrarily large neural networks to serve as base classifiers.

  • Takeaways & Limitations

    Exact probabilities, predictions, and certified radii are unavailable for neural-network base classifiers, and certifying large radii can require many samples.

Abstract

from arXiv · show

We show how to turn any classifier that classifies well under Gaussian noise into a new classifier that is certifiably robust to adversarial perturbations under the $\ell_2$ norm. This "randomized smoothing" technique has been proposed recently in the literature, but existing guarantees are loose. We prove a tight robustness guarantee in $\ell_2$ norm for smoothing with Gaussian noise. We use randomized smoothing to obtain an ImageNet classifier with e.g. a certified top-1 accuracy of 49% under adversarial perturbations with $\ell_2$ norm less than 0.5 (=127/255). No certified defense has been shown feasible on ImageNet except for smoothing. On smaller-scale datasets where competing approaches to certified $\ell_2$ robustness are viable, smoothing delivers higher certified accuracies. Our strong empirical results suggest that randomized smoothing is a promising direction for future research into adversarially robust classification. Code and models are available at http://github.com/locuslab/smoothing.

1. Introduction

Randomized smoothing converts an arbitrary classifier into a Gaussian-noise smoothed classifier with certifiable ℓ2 robustness. The paper proves a tight guarantee and reports strong ImageNet and smaller-dataset results, while certification requires probabilistic estimation.

  • Small adversarial perturbations can change modern image-classifier predictions despite being imperceptible to humans, while many empirical defenses fail against stronger attacks.
  • Randomized smoothing defines g(x) as the most probable prediction of base classifier f on Gaussian-corrupted versions of x.
  • Higher probability for the most likely noisy prediction yields a larger certified ℓ2 radius around the input.
  • The paper proves the first tight ℓ2 robustness guarantee for Gaussian randomized smoothing, improving on earlier loose guarantees.
  • Exact class probabilities and certified radii are unavailable for neural-network base classifiers, so Monte Carlo algorithms provide arbitrarily high-probability guarantees.
  • 49% provable top-1 accuracy is achieved on ImageNet against adversarial perturbations with ℓ2 norm less than 127/255.

2. Related Work

Certified defenses provide formal guarantees, but existing neural-network certification methods face scalability and architecture constraints. Randomized smoothing offers a distinct noise-based route, culminating here in a tight Gaussian ℓ2 guarantee.

  • Certified defenses guarantee that a classifier’s prediction remains constant within a specified perturbation set, unlike empirical defenses evaluated mainly against known attacks.
  • Exact certification decides whether any perturbation within a radius changes the prediction, whereas conservative methods may decline certification even when robustness holds.
  • Existing local certification methods have not been shown feasible for ImageNet-scale networks and often assume specific architectures or require extensive customization.
  • Prior noise-based work used Gaussian or Laplace smoothing for heuristic defenses or guarantees, but its robustness guarantees were loose.
  • This paper proves a tight ℓ2 robustness guarantee for randomized smoothing with Gaussian noise.

3. Randomized smoothing

Randomized smoothing converts an arbitrary classifier into a Gaussian-noise-based smoothed classifier whose prediction can be certified within an ℓ2 radius. The paper derives a tight radius, explains practical Monte Carlo certification, and examines its empirical and sampling trade-offs.

  • Randomized smoothing: The smoothed classifier g predicts the class that the base classifier f most likely returns under isotropic Gaussian noise around x.The noise level σ is fixed across inputs and controls the robustness/accuracy trade-off.
  • Robustness guarantee: Theorem 1 certifies g as cA within radius R = σ/2 (Φ^-1(pA) − Φ^-1(pB)), using top-class and runner-up probabilities.The guarantee also applies when pA is a lower bound and pB is an upper bound.
  • Robustness guarantee: The guarantee assumes nothing about f and grows with higher σ, higher top-class probability pA, and lower competing-class probabilities pB.The radius approaches infinity as pA approaches 1 and pB approaches 0.
  • Robustness guarantee: Theorem 2 shows the radius is tight: beyond R, a base classifier consistent with the observed probabilities can make g(x + δ) differ from cA.The worst-case classifier is linear with a decision boundary normal to δ, matching the geometric construction in Figure 3.
  • Comparisons and observations: The proposed radius is much larger than Lecuyer et al.'s guarantee and moderately larger than Li et al.'s guarantee.For linear base classifiers, smoothing leaves the classifier unchanged and certifies its true distance to the decision boundary.
  • Certification: Higher-resolution images can tolerate larger Gaussian noise before class-distinguishing content is destroyed, allowing smoothing with larger σ.This addresses concerns that a fixed ℓ2 radius is less meaningful at higher image resolution.
  • Certification: Monte Carlo procedures predict or certify g with arbitrarily high probability, but certification becomes sample-intensive for large radii.Certifying radius 4σ with 99.9% confidence requires approximately 10^5 samples, even when f(x) = cA everywhere.

4. Experiments

The experiments evaluate approximate certified accuracy, robustness–accuracy tradeoffs, sampling effects, and comparisons with prior certified-robustness methods on CIFAR-10 and ImageNet.

  • Evaluation: Approximate certified test accuracy is the fraction of examples that CERTIFY classifies correctly with a certified ℓ2-robust prediction.Exact evaluation is unavailable for randomized smoothing, so the experiments use CERTIFY-based approximate accuracy.
  • Evaluation: Certified accuracy decreases gradually with radius before collapsing to zero at a sampling-dependent hard upper limit.The limit occurs when all n samples are classified by the base classifier as the same class.
  • ImageNet and CIFAR-10 results: σ controls a robustness/accuracy tradeoff: lower noise favors high accuracy at small radii, whereas higher noise enables certification at larger radii with lower small-radius accuracy.Smoothing substantially improves robustness over the undefended base-classifier architecture.
  • Theorem comparison: Theorem 1 yields higher certified accuracies than the analogous guarantees of Lecuyer et al. (2019) and Li et al. (2018).The improvement follows from the paper’s larger, tight certified-radius expression.
  • Comparison to baselines: Randomized smoothing outperforms Wong et al. (2018) across all radii with a larger 110-layer ResNet and at all but the smallest radii with a small ResNet.The authors attribute the small-ResNet difference to overregularization in Wong et al., whereas smoothing retains a fully expressive base classifier.
  • Prediction: On ImageNet with σ = 0.25, PREDICT took 0.15 seconds per example with n = 100 and achieved 65% top-1 test accuracy.With failure probability α = 0.001, PREDICT abstained on 12% of examples at n = 100, decreasing to 1% at n = 10,000.

5. Conclusion

Gaussian smoothing naturally provides ℓ2 robustness, while randomized smoothing offers a scalable alternative to reasoning directly about large neural-network decision boundaries.

  • Conclusion: Without assumptions beyond the base classifier’s class probabilities, the provably robust perturbation set for Gaussian smoothing is exactly an ℓ2 ball.The authors conjecture that other noise distributions may induce guarantees for other perturbation sets, such as general ℓp balls.
  • Conclusion: Randomized smoothing is presented as a promising direction because empirical defenses can be broken and neural-network certification has not scaled to modern expressive networks.The method avoids sophisticated direct reasoning about large neural-network decision boundaries.

A. Proofs of Theorems 1 and 2

The appendix proves the randomized-smoothing robustness theorems using Neyman–Pearson arguments for shifted isotropic Gaussians, then establishes that the resulting radius is tight.

  • Proof setup: The proofs invoke the Neyman–Pearson lemma, including its Gaussian special case for distributions with different means.The argument compares measurable regions under X ∼ N(x, σ2I) and Y ∼ N(x + δ, σ2I).
  • Theorem 1: Theorem 1 states that if cA has probability at least pA and every competing class has probability at most pB under Gaussian smoothing, then g(x + δ) = cA for all ∥δ∥2 < R.The theorem defines g as the class with maximum smoothed prediction probability.
  • Theorem 1: The proof constructs regions A and B whose Gaussian probabilities match pA and pB, then transfers their probability ordering from X to the shifted variable Y.This yields P(f(Y) = cA) ≥ P(Y ∈ A) > P(Y ∈ B) ≥ P(f(Y) = cB).
  • Theorem 2: Theorem 2 assumes pA + pB ≤ 1 and constructs a base classifier f* consistent with the observed probabilities that changes its smoothed prediction beyond radius R.For any ∥δ∥2 > R, the construction makes cB more probable than cA after shifting.

B. Smoothing a two-class linear classifier

For a two-class linear base classifier, Gaussian smoothing leaves the classifier unchanged and certifies exactly its distance-based ℓ2 robustness radius. The guarantee is tight: every larger radius admits a class-changing perturbation.

  • The appendix establishes the linear result by analyzing Gaussian mass on the classifier’s two half-spaces and corresponding perturbations toward the decision boundary.
  • For any σ, smoothing a two-class linear classifier produces g(x) = f(x) wherever f is defined.
  • The certified radius equals the distance from x to the linear decision boundary, rather than a smaller conservative bound.This radius is (w^T x+b)/∥w∥2 as stated for the relevant side of the boundary.
  • For every r > R, some perturbation δ with ∥δ∥2 = r changes the smoothed classifier’s prediction.
  • The tightness claim is specific: for a fixed binary linear classifier, a class-changing perturbation exists just beyond the certified radius.This differs from a worst-case guarantee over classifiers, where the base classifier may vary with the perturbation.

C.1. Prediction

Prediction and certification use Monte Carlo samples of the noise-corrupted base classifier. Statistical tests and confidence bounds control errors, while certification may abstain when the evidence is insufficient.

  • With probability at least 1 − α, PREDICT either abstains or returns g(x).
  • PREDICT samples noisy inputs, selects the most frequent class, and returns it only when a hypothesis test rejects the null; otherwise it abstains.
  • CERTIFY first guesses the top class using n0 samples, then estimates lower and upper probability bounds from n additional samples.
  • Setting pB = 1 − pA yields a reasonably tight upper bound because non-top-class probability often concentrates in one runner-up class.
  • If the estimated top-class probability is below 1/2, CERTIFY abstains rather than returning a certification.This can occur when the initial sample-based guess misidentifies the top class.
  • With probability at least 1 − α, any returned class and radius satisfy the stated robustness guarantee.

E.2. Prediction

PREDICT trades computation against abstention and prediction performance through the Monte Carlo sample count. On ImageNet, even a small sample budget gives fast, relatively accurate predictions.

  • Table 4 varies n from 100 to 10,000 on ImageNet with σ = 0.25 and α = 0.001, distinguishing correct predictions from accurate predictions matching g(x).
  • 65% top-1 accuracy is achieved on ImageNet with n = 100 samples and α = 0.001.At this setting, evaluation takes 0.15 seconds on the reported hardware and abstention occurs 12% of the time.
  • 15 seconds of evaluation with n = 10,000 samples reduces abstention to 4%.
  • Most n = 100 abstentions occurred on examples where g was wrong, so increasing the sample count was observed to lose little practical accuracy.

F. Training with Noise

The paper motivates Gaussian data augmentation as a training objective for the base classifier. Minimizing cross-entropy under Gaussian noise lower-bounds and therefore approximately optimizes the desired noisy-classification objective.

  • The base classifier is trained by minimizing cross-entropy loss with Gaussian data augmentation.
  • The training objective seeks high log-probability for the correct class on noise-corrupted training inputs.
  • Softmax provides a differentiable approximation to the arg max classifier used in the objective.
  • Jensen’s inequality makes the Gaussian-augmentation cross-entropy objective a lower bound on the desired expected log-probability.
  • Minimizing this loss therefore approximately maximizes the probability objective for classifying Gaussian-corrupted inputs correctly.

G. Noise Level can Scale with Input Resolution

Higher-resolution images can tolerate larger isotropic Gaussian noise while preserving content, allowing smoothing classifiers to retain the same predictions with doubled certified radius.

  • The resolution argument addresses concerns that a dimension-independent certified radius is less meaningful for 224x224 images than for 56x56 images.
  • Higher-resolution images preserve class content better under isotropic Gaussian noise than lower-resolution images.Figure 12 shows hummingbird images at 56x56 and 224x224; the noisy high-resolution image is easier to distinguish.
  • A high-resolution image can be paired with a low-resolution image by average-pooling each 2x2 pixel block.
  • Twice the noise scale yields the same prediction as the corresponding low-resolution smoothing classifier while doubling the certified radius.Proposition 7 constructs the high-resolution classifier with noise level 2σ′ and certifies robustness at twice the radius.
  • Experiments compare a smoothed 20-layer ResNet with released certified-robustness models on CIFAR-10 and SVHN.The comparison uses Zhang et al. (2018) on CIFAR-10 and Tsuzuku et al. (2018) on SVHN.

H.3. How much noise to use when training the base classifier?

Training the base classifier with Gaussian noise matched to the smoothing noise produces higher certified accuracy than using a different training noise level.

  • A different training-noise level lowers the smoothed classifier’s certified accuracy when prediction noise is fixed.
  • Training with noise below the prediction noise appears worse than training with noise above it.Figure 15 varies training noise while holding prediction noise fixed at σ = 0.50.
  • The approximate certified accuracy and its high-probability lower bound differ negligibly in the reported experiment.

I. Derivation of Prior Randomized Smoothing Guarantees

Prior randomized-smoothing guarantees establish robustness by comparing noisy class probabilities, while the paper derives and evaluates those guarantees in its notation.

  • Lecuyer et al. and Li et al. provide guarantees with the same general form but different expressions for R.
  • The generic guarantee certifies that g(x + δ) = cA for all perturbations with ∥δ∥2 < R.
  • The derivation compares class probabilities under Gaussian perturbations centered at x and x + δ.
  • The derivations use data processing and closed-form Gaussian α-Renyi divergence to relate noisy inputs to certification conditions.
  • Li et al.’s result preserves the highest-probability class when the transformed distributions satisfy its probability conditions.
  • Figures 16a–d visualize how the prior bounds vary with their tuning parameters and show numerical pointwise suprema.
  • On SVHN and CIFAR-10, smoothing uses a 20-layer residual base classifier and CERTIFY with n = 100,000 and α = 0.001.The comparisons use the full SVHN test set and either the full CIFAR-10 test set or every fourth image for the competing method.

J.2. ImageNet and CIFAR-10 Experiments

The experiments document implementation, certification, and attack procedures for ImageNet and CIFAR-10, while noting that effective attacks against randomized smoothing remain outside scope.

  • The code for the experiments is publicly available at github.com/locuslab/smoothing.
  • Noise is added before channel-wise standardization so certified radii are reported in original image coordinates.
  • ImageNet uses a torchvision ResNet-50, while CIFAR-10 uses a 110-layer residual network.
  • ImageNet certification covers 500 validation images, whereas CIFAR-10 certification covers the whole test set.
  • CERTIFY experiments vary confidence-interval sample inputs and α while keeping the simulated sample count fixed at 100,000 in one analysis.
  • The adversarial evaluation uses projected-gradient updates constrained to an ℓ2 ball, with η = 0.1, T = 20, and k = 1000.
  • The optimized attack objective does not equal the misclassification objective required to find a competing class with greater noisy prediction probability.
  • Effective adversarial attacks against randomized smoothing are outside the paper’s scope.
Loading 1902.02918v2…