Random smoothing achieves certified adversarial robustness

1. 01What problem does this paper attempt to solve?

   Provide ℓ2 certified robustness that scales to ImageNet for any classifier, and prove that the certified radius of randomized smoothing is tight.

   Core question: how to construct classifiers that are certifiably robust under ℓ2-norm adversarial perturbations and can scale to ImageNet-scale networks.

   • Problem setting: modern image classifiers have high accuracy on i.i.d. test sets but are not robust to small adversarial perturbations imperceptible to humans; the authors note that many heuristic defenses were subsequently broken by stronger attackers (Carlini & Wagner, 2017; Athalye et al., 2018; Uesato et al., 2018).
   • Shortcomings of existing methods: the authors state that existing neural network certification methods (exact or conservative) are difficult to scale to networks large and expressive enough to solve ImageNet, and most assume a specific architecture or require substantial customization.
   • Core observation: randomized smoothing proposed by Lecuyer et al. (2019) and Li et al. (2018) can turn any base classifier into an ℓ2-certifiably robust smoothed classifier, but the guarantees of both are loose; the authors prove that the ℓ2 guarantee of Gaussian noise smoothing can be tight, and suggest that other noise distributions may induce robustness to other perturbation sets (e.g., general ℓp balls).
   • Contributions of the paper: prove a tight ℓ2 certified radius formula (Theorem 1, 2), give Monte Carlo prediction and certification algorithms that succeed with high probability, and run experiments on ImageNet, CIFAR-10, SVHN.
   • Threat model:
     • Attacker goal: add a perturbation δ to input x to change the prediction of the smoothed classifier g.
     • Perturbation constraint: ℓ2 norm bounded; prediction is guaranteed unchanged within the certified radius R.
     • Defender setting: any base classifier f (deterministic or random) is smoothed with Gaussian noise N(0, σ²I) to obtain g; no assumption is made about the architecture of f.
     • Victim system: image classifiers (ImageNet, CIFAR-10, SVHN); the guarantee holds with high probability 1−α, and is not a deterministic guarantee.

   Collapse this answer

2. 02What related research exists?

   Related work falls into four categories: empirical defenses, certified defenses, noise-related research, and randomized smoothing; this paper compares against three certified baselines including Wong et al. (2018).

   Empirical defenses

   • Adversarial training (Goodfellow et al., 2015; Kurakin et al., 2017; Madry et al., 2018) — adds adversarial examples generated by attacks such as PGD during training; the paper points out that it cannot determine whether predictions are truly robust, and that many heuristic defenses were later broken by stronger attackers.

   Certified defenses

   • Exact (complete) methods — based on SMT or mixed-integer programming (Katz et al., 2017; Tjeng et al., 2019, etc.); the paper points out that they cannot scale to medium-sized networks with more than about 100,000 activations.
   • Conservative (sound but incomplete) methods — including global/local Lipschitz bounds (Gouk et al., 2018; Tsuzuku et al., 2018; Hein & Andriushchenko, 2017), convex relaxations and duality (Wong & Kolter, 2018; Raghunathan et al., 2018a; Dvijotham et al., 2018b) and layer-by-layer abstract interpretation (Mirman et al., 2018; Gehr et al., 2018; Weng et al., 2018a; Zhang et al., 2018); the paper points out that these methods have not been shown to be feasible on ImageNet-scale networks and mostly assume specific architectures.

   Related work involving noise

   • Using Gaussian noise robustness as a proxy for adversarial robustness (Weng et al., 2018b; Ford et al., 2019), Gaussian data augmentation to supplement adversarial training (Zantedeschi et al., 2017; Kannan et al., 2018), SmoothGrad (Smilkov et al., 2017), etc.; the paper points out that these works assume a relationship between random noise and adversarial robustness, whereas randomized smoothing uses noise robustness to construct new adversarially robust classifiers.

   Randomized smoothing

   • Liu et al. (2018), Cao & Gong (2017) — proposed similar techniques as heuristic defenses without guarantees.
   • Lecuyer et al. (2019) — used differential privacy inequalities to prove ℓ2/ℓ1 guarantees for Gaussian/Laplacian noise, and trained the first ImageNet certified robust classifier.
   • Li et al. (2018) — used information-theoretic tools to prove a stronger Gaussian ℓ2 guarantee; the paper points out that both guarantees are loose, whereas this paper proves a tight guarantee.

   Comparison baselines and benchmarks: the baselines are Wong et al. (2018) (duality method, CIFAR-10), Tsuzuku et al. (2018) (Lipschitz method, SVHN), Zhang et al. (2018) (CIFAR-10), all compared using the pretrained networks released by the authors.

   The authors position this paper as: building on the frameworks of Lecuyer et al. and Li et al. to give the first tight ℓ2 guarantee, making randomized smoothing feasible on ImageNet and achieving higher certified accuracy than competing methods on small datasets.

   Collapse this answer

3. 03How does the paper address this problem?

   Smooth any base classifier with Gaussian noise, prove a tight ℓ2 certified radius, and predict and certify with high probability using Monte Carlo algorithms.

   Overall idea: take the majority prediction of any base classifier f on the input plus isotropic Gaussian noise as the smoothed classifier (randomized smoothing) g, prove a tight expression for its ℓ2 certified radius, and then give Monte Carlo prediction and certification algorithms that succeed with arbitrarily high probability.

   Problem setup and smoothed classifier

   • Definition: g(x) = argmax_{c∈ Y} P(f(x+ε)=c), where ε ~ N(0, σ²I); that is, g returns the class most likely to be predicted by f on the Gaussian-perturbed x.
   • Hyperparameter σ: controls the robustness/accuracy trade-off and does not vary with input x; when the argmax is not unique, the behavior of g is undefined.
   • No assumption on f: f can be any deterministic or random function; this is a key property of the method.

   Tight robustness guarantee

   • Theorem 1: if P(f(x+ε)=cA) ≥ pA ≥ pB ≥ max probability of other classes, then for all ||δ||₂ < R 有 g(x+δ)=cA，其中 R = σ/2(Φ⁻¹(p_A) − Φ⁻¹(p_B))，Φ⁻¹ 为标准高斯 CDF 的逆；pA、pB 可用下界/上界替代。
   • Theorem 2（紧性）：在 pA+pB ≤ 1 下，对任何 ||δ||₂ > R, there exists a base classifier consistent with (pA, pB) such that g(x+δ) ≠ cA; on this basis the authors state that the certified set naturally induced by Gaussian smoothing is exactly an ℓ2 ball.
   • Proof idea: in the binary case, an argument similar to the Neyman-Pearson lemma is used; the worst-case base classifier is a linear classifier whose decision boundary is perpendicular to δ; the full proof is in Appendix A.
   • Linear base classifier: Appendix B proves that when f is a binary linear classifier, g is the same as f, and the radius certified by Theorem 1 equals the true robust radius |wᵀx+b|/||w||.

   Monte Carlo algorithms

   • PREDICT: draw n noise samples and pass them through f; if the two-sided binomial test p-value of the most-counted class relative to the second-most-counted class is ≤ α, return that class, otherwise abstain; Proposition 1 guarantees that with probability at least 1−α it either abstains or returns g(x).
   • CERTIFY: first use n0 samples to guess the top class ĉA, then use n samples to estimate a lower bound pA via a Clopper-Pearson interval, and set pB = 1−pA; if pA > 1/2, return ĉA and radius σΦ⁻¹(pA), otherwise abstain; Proposition 2 guarantees that certification holds with probability at least 1−α.
   • Sample complexity: the authors note that certifying large radii requires many samples—even if f predicts correctly everywhere, certifying radius 4σ with 99.9% confidence requires about 10⁵ samples (Figure 5 right).

   Base classifier training

   • Gaussian data augmentation: following Lecuyer et al. (2019), f is trained with cross-entropy under Gaussian data augmentation with variance σ²; the authors' rationale is that in high dimensions the distributions of natural images and noisy images barely overlap, so a standard-trained f has never seen noisy images.
   • The authors believe this training scheme may have room for improvement, for example directly maximizing the smoothed classifier's certified accuracy at some tunable radius.

   Collapse this answer

4. 04What experiments did the paper conduct?

   Certified smoothed classifiers on ImageNet, CIFAR-10, and SVHN, with 49% certified accuracy at radius 0.5 on ImageNet, outperforming three certified baselines.

   Experimental setup

   • Models tested: the base classifier is ResNet-50 on ImageNet; a 110-layer residual network on CIFAR-10; a 20-layer residual network when comparing with baselines (Appendix H, J).
   • Datasets: ImageNet (500 subsampled test samples certified), CIFAR-10 (full test set certified), SVHN (full test set, Appendix H).
   • Baselines: Wong et al. (2018) (CIFAR-10, small resnet with three ε settings), Tsuzuku et al. (2018) (SVHN), Zhang et al. (2018) (CIFAR-10, 7-layer MLP), all using the networks released by the authors.
   • Metric: approximate certified test accuracy—the proportion of test samples that CERTIFY predicts correctly with certified radius R ≥ r; Appendix H.2 states that its difference from the high-probability lower bound is negligible.
   • Certification parameters: default α = 0.001 (certification error probability at most 0.1%), n0 = 100, n = 100,000; certification takes about 15 seconds per sample on CIFAR-10 and about 110 seconds on ImageNet (RTX 2080 Ti).
   • Training: the base classifier is trained with Gaussian data augmentation at the same σ as smoothing.

   Main results

   According to the approximate certified accuracies in Table 1 (ImageNet, 500 samples) and Table 3 (CIFAR-10, full test set):

   Swipe horizontally to read the table

   Dataset	σ	r=0	r=0.5	r=1.0	r=2.0	r=3.0
   ImageNet	0.25	0.67	0.49	0.00	0.00	0.00
   ImageNet	0.50	0.57	0.46	0.37	0.00	0.00
   ImageNet	1.00	0.44	0.38	0.33	0.19	0.12
   CIFAR-10	0.25	0.77	0.42	0.00	—	—
   CIFAR-10	0.50	0.66	0.43	0.22	—	—
   CIFAR-10	1.00	0.47	0.34	0.22	—	—

   (The columns for CIFAR-10 are r ∈ {0, 0.25, 0.5, 0.75, 1.0, 1.25, 1.5}; only some columns are taken here; see Table 3 for the full data.)

   • The authors state that σ controls the robustness/accuracy trade-off: low σ gives high certified accuracy at small radii but cannot certify large radii, while high σ does the opposite (Figure 6).
   • The authors state that smoothing improves over the empirical robust accuracy upper bound of the undefended architecture (DeepFool ℓ2 attack, dashed line in the figure) (Figure 6).
   • The authors state that this trade-off echoes the finding of Tsipras et al. (2019) that robust accuracy and standard accuracy trade off against each other.

   Comparison with certified baselines

   • What was measured: Figure 7 compares, on CIFAR-10, Wong et al. (2018)'s small resnet (three ε settings) with smoothed classifiers (the same small resnet as base classifier, and a 110-layer resnet as base classifier).
   • Results: the authors state that the smoothed classifier with the 110-layer resnet is higher than all hyperparameter settings of the baseline at all radii; the smoothed classifier with the same small resnet is higher than Wong et al. (2018) at all radii except the smallest radius.
   • Authors' interpretation: the authors attribute the latter to the fact that the network trained by Wong et al. (2018) is "often over-regularized to the point where many filters/weights are identically zero" (quoted from that paper), whereas the base classifier for smoothing is a fully expressive network; Figure 13 in Appendix H.1 shows that the smoothed classifier with a 20-layer resnet is higher than Tsuzuku et al. (2018) on SVHN and higher than Zhang et al. (2018) on CIFAR-10 (note that the base classifier is larger than the networks of the compared methods).

   Prediction cost and abstention rate

   • What was measured: the performance of PREDICT as n varies on ImageNet (σ = 0.25, α = 0.001) (Table 4).
   • Results: at n = 100, top-1 accuracy 65%, abstention rate 12%, 0.15 seconds per prediction; at n = 1000, accuracy 68%, abstention 4%; at n = 10,000, accuracy 69%, abstention 1%.
   • Authors' interpretation: the authors state that most abstentions at n = 100 occur on samples where g itself predicts incorrectly, so in practice using n = 100 loses little accuracy.

   Other ablations and analyses

   • Comparison with prior guarantees: Figure 8 (left) shows that under the same σ = 0.25, the certified accuracy of this paper's Theorem 1 is higher than that obtained using the guarantees of Lecuyer et al. (2019) and Li et al. (2018).
   • Number of samples n: Figure 8 (middle) projects how certified accuracy changes as n goes from 1,000 to 10,000,000 (assuming class proportions stay fixed).
   • Confidence parameter α: Figure 8 (right) shows that certified accuracy is insensitive to α.
   • Training noise: Figure 15 shows that certified accuracy is lower when the base classifier is trained with noise different from the smoothing σ, and that training noise smaller than σ is worse than larger than σ.
   • Empirical tightness of the bound: a PGD-style attack on the ImageNet smoothed classifier (σ = 0.25) finds adversarial examples for 17% of samples within 1.5R and 53% within 2R (α = 0.01, Appendix J.3); the authors note that this attack objective is not the true optimal attack objective, and that effective attacks are beyond the scope of this paper.

   Collapse this answer

5. 05What are some points that can be further explored?

   The authors note that sample complexity, the PREDICT abstention attack, and the training scheme could be improved; the experiments cover only three image classification datasets.

   Limitations and future directions noted by the authors

   • Other noise distributions: the authors suggest that other, as-yet-unknown noise distributions may induce robustness to other perturbation sets such as general ℓp balls (§1, §5).
   • Training scheme: the authors suggest that training with Gaussian data augmentation may have room for improvement, for example training the base classifier to directly maximize the smoothed classifier's certified accuracy at a tunable radius r (§3.3).
   • Abstention attack on PREDICT: the authors note that even if g is robust within radius R, an attacker can construct perturbations that make PREDICT abstain at a high rate; to guard against this, one could prove a variant of Theorem 1 that certifies a radius for the top-class probability with a margin (§3.2.1).
   • Effective attacks not studied: Appendix J.3 notes that the objective optimized by the PGD attack used is not the true attack objective, and that effective adversarial attacks against randomized smoothing are beyond the scope of this paper.
   • Certification cost: the authors note that certifying large radii requires many Monte Carlo samples (radius 4σ at 99.9% confidence requires about 10⁵ samples), and that certification is far more expensive than prediction (§3.2.2, §4).

   Scope of experiments

   • The architectures tested are ResNet-50 (ImageNet), a 110-layer residual network (CIFAR-10), and a 20-layer residual network (baseline comparison), all convolutional image classification networks (§4, Appendix J).
   • The datasets are ImageNet (500 test subsamples certified), CIFAR-10 (full test set), and SVHN (full test set, compared with Tsuzuku et al. only in Appendix H.1).
   • The perturbation model covers only ℓ2-norm-bounded perturbations; the guarantee holds with high probability (α = 0.001) and is not deterministic.
   • The baseline comparison covers three certified methods, Wong et al. (2018), Tsuzuku et al. (2018), and Zhang et al. (2018), all using the pretrained networks released by the authors (Appendix J.1).
   • The paper does not report the number of repetitions of the certification experiments; the empirical attack is run under only one setting, ImageNet σ = 0.25 (§4).

   Collapse this answer

6. 06Summarize the main content of the paper

   Tight ℓ2 certification for randomized smoothing: wrap any classifier into a certifiably robust smoothed classifier, and scale to ImageNet.

   A defense paper on certified adversarial robustness: it defines the smoothed classifier g as the majority prediction of any base classifier under Gaussian noise, proves that its ℓ2 certified radius R = σ/2·(Φ⁻¹(pA)−Φ⁻¹(pB)) is tight, and gives Monte Carlo prediction (PREDICT) and certification (CERTIFY) algorithms that succeed with high probability.

   • Problem addressed: existing neural network certification methods cannot scale to ImageNet scale; the randomized smoothing guarantees of Lecuyer et al. (2019) and Li et al. (2018) were loose.
   • Method highlights: no assumption is made about the base classifier architecture; σ controls the robustness/accuracy trade-off; the base classifier is trained with Gaussian data augmentation at the same σ; certification defaults to α = 0.001, n = 100,000.
   • ImageNet results (ResNet-50, 500 test samples, Table 1): at σ = 0.25, certified accuracy at radius 0.5 is 49% and standard accuracy is 67%; at σ = 0.50, radius 1.0 is 37%; at σ = 1.00, radius 3.0 is 12%.
   • CIFAR-10 results (110-layer resnet, Table 3): at σ = 0.25, certified accuracy at radius 0.5 is 0.42; Figure 7 shows that under the same architecture smoothing is higher than Wong et al. (2018) at all radii except the smallest radius, and higher at all radii with the large network.
   • Prediction cost: on ImageNet at σ = 0.25, PREDICT with n = 100 takes only 0.15 seconds, with top-1 accuracy 65% and abstention rate 12% (Table 4).
   • Authors' conclusion: the authors state that randomized smoothing is currently the only certified defense proven feasible on full-resolution ImageNet, reducing the open problem of adversarially robust classification to the relatively solved problem of supervised learning, and is a promising research direction; the authors also note that certifying large radii requires many samples, that PREDICT can be forced to abstain, and that the training scheme can be improved.

   Collapse this answer

Related papers