Certified Adversarial Robustness via Randomized Smoothing

Jeremy M CohenElan RosenfeldJ. Zico Kolter

article2019ICML2,648 citations

Proves a tight mathematical guarantee for Gaussian randomized smoothing, providing the first certified defense against L2-norm adversarial attacks that scales effectively to ImageNet.

Listen

Modern image classifiers achieve high accuracy on standard test sets but remain vulnerable to small adversarial perturbations that can change their predictions while remaining imperceptible to humans. Existing methods for training robust classifiers often fail against stronger attacks, and certified defenses that provide formal guarantees have struggled to scale to large networks needed for challenging tasks like ImageNet classification.

The article develops randomized smoothing as a technique to convert any base classifier into a new smoothed classifier that is certifiably robust to adversarial perturbations measured in the ℓ2 norm. The smoothed classifier outputs the class that the base classifier returns most often when its input is corrupted by isotropic Gaussian noise. The authors derive a tight robustness guarantee showing that the prediction remains constant inside an ℓ2 ball whose radius depends on the noise level and the base classifier's class probabilities under that noise; they also supply Monte Carlo algorithms that evaluate the smoothed classifier and certify its robustness with arbitrarily high probability.

On ImageNet, smoothed classifiers achieve, for example, 49 percent certified top-1 accuracy against perturbations of ℓ2 norm 0.5 and remain the only certified defense demonstrated at full scale on this dataset. On smaller datasets such as CIFAR-10 where competing certified methods are feasible, smoothing yields higher certified accuracies, largely because it places no restrictions on the architecture or training of the base classifier. Experiments further confirm that the derived bound is substantially tighter than previous analyses of randomized smoothing.

These results indicate that randomized smoothing offers a practical and scalable route to certified robustness. Because the approach reduces the adversarial-robustness problem to ordinary supervised learning under noise, it can leverage the largest available networks without custom verification procedures. Practitioners can therefore obtain meaningful robustness guarantees on large-scale tasks by training a base classifier with Gaussian data augmentation and then applying the provided certification procedure.

The main limitations are that certification remains probabilistic and that certifying large radii requires many Monte Carlo samples. The authors recommend exploring other noise distributions that might induce natural robustness guarantees for additional perturbation sets such as general ℓp balls, and they note that further gains may come from training the base classifier explicitly to maximize the smoothed classifier's certified accuracy at chosen radii.

Bosch Center for AI Carnegie Mellon University gaussians http svm Randomized Smoothing Certified Robustness Gaussian Noise

arXiv: 1902.02918 locuslab/smoothing

Paper: Intriguing properties of neural networks, Christian Szegedy et al. (2014). This seminal paper introduces the fundamental vulnerability of deep neural networks to tiny adversarial perturbations, providing the primary phenomenon and motivation that randomized smoothing aims to provably defend against.
Paper: Explaining and Harnessing Adversarial Examples, Ian J. Goodfellow et al. (2015). This foundational work formalizes adversarial examples and early empirical defenses like adversarial training, establishing the core challenge of securing models against bounded norm attacks.
Paper: Towards Deep Learning Models Resistant to Adversarial Attacks, A. Ma̧dry et al. (2017). This paper establishes the standard minimax robust optimization framework and projected gradient descent defense, representing the benchmark empirical defense compared against certified defenses.
Paper: Obfuscated Gradients Give a False Sense of Security: Circumventing Defenses to Adversarial Examples, Anish Athalye et al. (2018). This study demonstrates how heuristic and empirical defenses often provide a false sense of security via gradient obfuscation, directly highlighting the necessity for scalable, certified defense guarantees like randomized smoothing.
Paper: Towards Evaluating the Robustness of Neural Networks, Nicholas Carlini et al. (2016). This work introduces standard L2 and L-infinity optimization-based attacks, providing the threat models and evaluation metrics underpinning the certified L2 robustness radii in randomized smoothing.
Paper: SmoothGrad: removing noise by adding noise, Daniel Smilkov et al. (2017). This paper demonstrates how convolving input spaces with Gaussian noise effectively stabilizes model gradients and outputs, providing direct methodological intuition for smoothing deep neural networks.

Paper: Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attacks, Francesco Croce et al. (2020). This work develops AutoAttack, providing a rigorous and standardized benchmark ensemble to evaluate whether empirical and certified defenses genuinely withstand diverse adversarial attacks.
Paper: The Many Faces of Robustness: A Critical Analysis of Out-of-Distribution Generalization, Dan Hendrycks et al. (2021). This paper expands the evaluation of model robustness beyond formal norm-bounded adversarial perturbations to comprehensive real-world distribution shifts and natural corruptions.

Cover for Certified Adversarial Robustness via Randomized Smoothing

Abstract

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 this http URL.

Topics

gaussians http svm robust performance additive noise classification models noise removal computational efficiency impulsive noise

Keywords

Randomized Smoothing Certified Robustness Gaussian Noise ℓ2 Norm Smoothed Classifier Certifiable Radius Monte Carlo Algorithm Base Classifier Adversarial Perturbation Certifiable Accuracy

1 Introduction
2 Related Work
3 Randomized smoothing
3.1 Robustness guarantee
3.2 Practical algorithms
3.2.1 Prediction
3.2.2 Certification
3.3 Training the base classifier
4 Experiments
5 Conclusion
6 Acknowledgements
References
A Proofs of Theorems and
A.0.1 Deferred Algebra
B Smoothing a two-class linear classifier
C Practical algorithms
C.1 Prediction
C.2 Certification
D Estimating the certified test-set accuracy
E ImageNet and CIFAR-10 Results
E.1 Certification
E.2 Prediction
F Training with Noise
G Noise Level can Scale with Input Resolution
H Additional Experiments
H.1 Comparisons to baselines
H.2 High-probability guarantees
H.3 How much noise to use when training the base classifier?
I Derivation of Prior Randomized Smoothing Guarantees
I.1 Lecuyer et al. (2019)
I.2 Li et al. (2018)
J Experiment Details
J.1 Comparison to baselines
J.2 ImageNet and CIFAR-10 Experiments
J.3 Adversarial Attacks
K Examples of Noisy Images

Knowls

Knowl 1 — Tight Certified Robustness Guarantee in L2 Norm for Gaussian Randomized Smoothing
theoretical result
Let $f: \mathbb{R}^d \to \mathcal{Y}$ be any deterministic or randomized base classifier mapping inputs to a discrete set of classes $\mathcal{Y}$ . Let $\varepsilon \sim \mathcal{N}(0, \sigma^2 I)$ be isotropic Gaussian noise with standard deviation $\sigma > 0$ . Let $g: \mathbb{R}^d \to \mathcal{Y}$ be the smoothed classifier defined by:

$g(x) = \arg\max_{c \in \mathcal{Y}} \mathbb{P}(f(x + \varepsilon) = c)$

Suppose that for a given input $x \in \mathbb{R}^d$ , there exists a class $c_A \in \mathcal{Y}$ and probability bounds $\underline{p_A}, \overline{p_B} \in [0, 1]$ such that:

$\mathbb{P}(f(x + \varepsilon) = c_A) \ge \underline{p_A} \ge \overline{p_B} \ge \max_{c \ne c_A} \mathbb{P}(f(x + \varepsilon) = c)$

Then the prediction of the smoothed classifier is certifiably constant within an $\ell_2$ ball around $x$ :

$g(x + \delta) = c_A \quad \text{for all } \delta \in \mathbb{R}^d \text{ with } \|\delta\|_2 < R$

where $\Phi^{-1}$ denotes the inverse cumulative distribution function of the standard Gaussian distribution $\mathcal{N}(0, 1)$ , and the certified radius $R$ is given by:

$R = \frac{\sigma}{2}\left(\Phi^{-1}(\underline{p_A}) - \Phi^{-1}(\overline{p_B})\right)$

In the setting where $\overline{p_B} = 1 - \underline{p_A}$ and $\underline{p_A} > 1/2$ , the certified radius simplifies to:

$R = \sigma \Phi^{-1}(\underline{p_A})$

This guarantee requires no structural or architectural assumptions (such as linearity, activation type, or Lipschitz bounds) on the base classifier $f$ .
Knowl 2 — Tightness of the Gaussian Randomized Smoothing Robustness Radius
theoretical result
The certified $\ell_2$ radius obtained from randomized smoothing with isotropic Gaussian noise is mathematically tight. Under the condition that $\underline{p_A} + \overline{p_B} \le 1$ , for any perturbation $\delta \in \mathbb{R}^d$ with $\|\delta\|_2 > R$ , where

$R = \frac{\sigma}{2}\left(\Phi^{-1}(\underline{p_A}) - \Phi^{-1}(\overline{p_B})\right)$

there exists a base classifier $f^*: \mathbb{R}^d \to \mathcal{Y}$ consistent with the observed class probability bounds $\mathbb{P}(f^*(x + \varepsilon) = c_A) = \underline{p_A}$ and $\mathbb{P}(f^*(x + \varepsilon) = c_B) = \overline{p_B}$ for which the smoothed classifier $g$ fails to predict $c_A$ at $x + \delta$ , i.e., $g(x + \delta) \ne c_A$ .

The worst-case base classifier $f^*$ is a linear classifier whose decision boundary is an affine hyperplane normal to $\delta$ :

$f^*(z) = \begin{cases} c_A & \text{if } \delta^T (z - x) \le \sigma \|\delta\|_2 \Phi^{-1}(\underline{p_A}) \\ c_B & \text{if } \delta^T (z - x) \ge \sigma \|\delta\|_2 \Phi^{-1}(1 - \overline{p_B}) \\ \text{other class} & \text{otherwise} \end{cases}$

Consequently, without further assumptions on $f$ , the maximal certifiable robustness region induced by Gaussian smoothing is precisely an $\ell_2$ ball of radius $R$ .
Knowl 3 — Gaussian Randomized Smoothed Classifier
definition
Given a base classifier $f: \mathbb{R}^d \to \mathcal{Y}$ mapping $d$ -dimensional continuous inputs to a discrete set of classes $\mathcal{Y}$ , and a noise variance hyperparameter $\sigma > 0$ , the Gaussian randomized smoothed classifier $g: \mathbb{R}^d \to \mathcal{Y}$ is defined as:

$g(x) = \arg\max_{c \in \mathcal{Y}} \mathbb{P}_{\varepsilon \sim \mathcal{N}(0, \sigma^2 I)}(f(x + \varepsilon) = c)$

Equivalently, $g(x)$ assigns to $x$ the class $c$ whose pre-image region $\{z \in \mathbb{R}^d : f(z) = c\}$ has the highest probability measure under the isotropic Gaussian measure $\mathcal{N}(x, \sigma^2 I)$ . If the maximizing class is not unique, $g(x)$ is undefined. The standard deviation $\sigma$ is a constant hyperparameter controlling the trade-off between nominal accuracy and adversarial robustness.
Knowl 4 — Monte Carlo Robustness Certification Algorithm for Smoothed Classifiers
algorithm
The certification procedure evaluates whether a smoothed classifier $g$ robustly outputs class $\hat{c}_A$ within an $\ell_2$ ball around input $x$ , producing a certified radius $R$ that holds with probability at least $1 - \alpha$ .

The algorithm executes two sampling stages:
1. Selection Stage: It samples $n_0$ noise corruptions $\varepsilon \sim \mathcal{N}(0, \sigma^2 I)$ and evaluates $f(x + \varepsilon)$ to select candidate top class $\hat{c}_A = \arg\max_c \text{counts}_0[c]$ .
2. Estimation Stage: It draws an independent batch of $n$ noise corruptions $\varepsilon \sim \mathcal{N}(0, \sigma^2 I)$ and computes a one-sided Clopper-Pearson binomial lower confidence bound $\underline{p_A}$ for $\mathbb{P}(f(x + \varepsilon) = \hat{c}_A)$ at confidence level $1 - \alpha$ . Setting $\overline{p_B} = 1 - \underline{p_A}$ , if $\underline{p_A} > 1/2$ , the algorithm outputs $\hat{c}_A$ and certified radius $R = \sigma \Phi^{-1}(\underline{p_A})$ ; otherwise, it abstains.
Input: base classifier $f$ , noise parameter $\sigma$ , input $x$ , sample sizes $n_0$ and $n$ , error tolerance $\alpha$
Output: certified class $\hat{c}_A$ and radius $R$ , or ABSTAIN
counts0 = SAMPLEUNDERNOISE(f, x, n0, \sigma)
\hat{c}_A = argmax_c counts0[c]
counts = SAMPLEUNDERNOISE(f, x, n, \sigma)
\underline{p_A} = LOWERCONFBOUND(counts[\hat{c}_A], n, 1 - \alpha)
if \underline{p_A} > 0.5 then
    R = \sigma * \Phi^{-1}(\underline{p_A})
    return \hat{c}_A, R
else
    return ABSTAIN
The subroutine SAMPLEUNDERNOISE(f, x, m, \sigma) generates $m$ independent noise draws $\varepsilon_1, \dots, \varepsilon_m \sim \mathcal{N}(0, \sigma^2 I)$ and tallies the counts of each returned class $f(x + \varepsilon_i)$ . The helper function LOWERCONFBOUND(k, n, 1 - \alpha) computes the exact one-sided Clopper-Pearson lower confidence limit for binomial success parameter $p$ given $k$ successes out of $n$ independent trials.
Knowl 5 — Monte Carlo Prediction Algorithm with Abstention for Smoothed Classifiers
algorithm
The evaluation procedure PREDICT determines the output of a smoothed classifier $g(x) = \arg\max_{c \in \mathcal{Y}} \mathbb{P}(f(x + \varepsilon) = c)$ such that the probability of returning an incorrect class (a class other than $g(x)$ or abstaining) is guaranteed to be at most $\alpha$ .

The algorithm draws $n$ independent noise samples $\varepsilon_i \sim \mathcal{N}(0, \sigma^2 I)$ and evaluates $f(x + \varepsilon_i)$ . It identifies the class $\hat{c}_A$ with the highest count $n_A$ and class $\hat{c}_B$ with the second-highest count $n_B$ . It performs a two-sided binomial hypothesis test for whether $n_A \sim \text{Binomial}(n_A + n_B, 0.5)$ . If the resulting $p$ -value is at most $\alpha$ , it outputs $\hat{c}_A$ ; otherwise, it abstains.
Input: base classifier $f$ , noise level $\sigma$ , input $x$ , sample count $n$ , error tolerance $\alpha$
Output: predicted class $\hat{c}_A$ , or ABSTAIN
counts = SAMPLEUNDERNOISE(f, x, n, \sigma)
\hat{c}_A, \hat{c}_B = top_two_indices(counts)
n_A = counts[\hat{c}_A]
n_B = counts[\hat{c}_B]
p_val = BINOMPVALUE(n_A, n_A + n_B, 0.5)
if p_val <= \alpha then
return \hat{c}_A
else
return ABSTAIN
The function BINOMPVALUE(n_A, n_A + n_B, 0.5) computes the exact $p$ -value of the two-sided binomial test. With $n = 100$ and $\alpha = 0.001$ , PREDICT executes in approximately 0.15 seconds per ImageNet image.

Knowl 6 — Certified L2 Accuracy of Gaussian Randomized Smoothing on ImageNet

data/table

Randomized smoothing provides certifiable $\ell_2$ robustness on 1000-class full-resolution ImageNet. Using a ResNet-50 base classifier evaluated with $n = 100{,}000$ Monte Carlo samples and error tolerance $\alpha = 0.001$ over a 500-image test subsample, smoothed classifiers attain top-1 certified test accuracies across different $\ell_2$ perturbation radii $r$ :

$\sigma$	$r = 0.0$	$r = 0.5$	$r = 1.0$	$r = 1.5$	$r = 2.0$	$r = 2.5$	$r = 3.0$
0.25	0.67	0.49	0.00	0.00	0.00	0.00	0.00
0.50	0.57	0.46	0.37	0.29	0.00	0.00	0.00
1.00	0.44	0.38	0.33	0.26	0.19	0.15	0.12

The column $r = 0.0$ corresponds to standard accuracy without adversarial perturbation. Unconstrained random guessing on ImageNet attains 0.1% ( $0.001$ ) accuracy. A radius of $r = 0.5$ equates to an $\ell_2$ pixel distortion of $127/255$ . The choice of noise parameter $\sigma$ governs the robustness-accuracy tradeoff: $\sigma = 0.25$ yields the highest accuracy at small radii ( $49\%$ at $r = 0.5$ ), whereas $\sigma = 1.00$ enables certification at large radii ( $12\%$ at $r = 3.0$ ).

Knowl 7 — Certified L2 Accuracy of Gaussian Randomized Smoothing on CIFAR-10

data/table

Randomized smoothing applied to a 110-layer residual network on CIFAR-10 evaluated with $n = 100{,}000$ Monte Carlo samples and failure tolerance $\alpha = 0.001$ over the complete test set produces certified top-1 test accuracies across $\ell_2$ radii $r$ :

$\sigma$	$r = 0.00$	$r = 0.25$	$r = 0.50$	$r = 0.75$	$r = 1.00$	$r = 1.25$	$r = 1.50$
0.12	0.83	0.60	0.00	0.00	0.00	0.00	0.00
0.25	0.77	0.61	0.42	0.25	0.00	0.00	0.00
0.50	0.66	0.55	0.43	0.32	0.22	0.14	0.08
1.00	0.47	0.41	0.34	0.28	0.22	0.17	0.14

Random guessing accuracy on CIFAR-10 is $10\%$ ( $0.10$ ). As $\sigma$ increases from $0.12$ to $1.00$ , the maximum certifiable radius expands from $0.25$ to $1.50$ , at the expense of standard accuracy (which drops from $83\%$ to $47\%$ ).

Knowl 8 — Training Base Classifiers with Gaussian Data Augmentation as Approximate Likelihood Maximization
model/method
For a smoothed classifier $g(x) = \arg\max_{c \in \mathcal{Y}} \mathbb{P}(f(x+\varepsilon) = c)$ to classify a labeled example $(x, c)$ accurately and certifiably, the base classifier $f$ must classify random corruptions $x + \varepsilon$ (where $\varepsilon \sim \mathcal{N}(0, \sigma^2 I)$ ) consistently as $c$ .

Given training data $\{(x_i, c_i)\}_{i=1}^m$ and class scoring functions $f_c$ , the goal is to maximize the expected log-probabilities under Gaussian noise:

$\sum_{i=1}^m \log \mathbb{P}_{\varepsilon}(f(x_i + \varepsilon) = c_i) = \sum_{i=1}^m \log \mathbb{E}_{\varepsilon}\left[\mathbf{1}\left[\arg\max_{c} f_c(x_i + \varepsilon) = c_i\right]\right]$

Approximating the 0-1 argmax indicator with the softmax function and invoking Jensen's inequality on the concave logarithm yields the lower bound:

$\sum_{i=1}^m \log \mathbb{P}_{\varepsilon}(f(x_i + \varepsilon) = c_i) \ge \sum_{i=1}^m \mathbb{E}_{\varepsilon \sim \mathcal{N}(0, \sigma^2 I)}\left[\log \frac{\exp(f_{c_i}(x_i + \varepsilon))}{\sum_{c' \in \mathcal{Y}} \exp(f_{c'}(x_i + \varepsilon))}\right]$

This lower bound is the negative of the standard cross-entropy loss evaluated on Gaussian-corrupted training inputs. Consequently, minimizing cross-entropy loss under Gaussian data augmentation at variance $\sigma^2$ maximizes a surrogate lower bound to the smoothed classifier's log-likelihood.
Knowl 9 — Finite-Sample Lower Bound on True Certified Test-Set Accuracy
theoretical result
Let $S = \{(x_1, c_1), \dots, (x_m, c_m)\}$ be a test set of size $m$ , and let $z_i = \mathbf{1}[g(x_i + \delta) = c_i \; \forall \|\delta\|_2 < r]$ denote whether the smoothed classifier $g$ is truly correct and robust at radius $r$ on example $i$ . Let $Y_i \in \{0, 1\}$ indicate whether the Monte Carlo procedure CERTIFY with per-example failure rate $\alpha \le 1/2$ returns label $c_i$ with certified radius $R \ge r$ , and let $Y = \sum_{i=1}^m Y_i$ .

For any overall significance level $ho > 0$ , the true certified test-set accuracy $\frac{1}{m}\sum_{i=1}^m z_i$ is bounded below with probability at least $1 - \rho$ over the randomness in CERTIFY by:

$\frac{1}{m}\sum_{i=1}^m z_i \ge \frac{1}{1 - \alpha}\left(\frac{Y}{m} - \alpha - \sqrt{\frac{2\alpha(1 - \alpha)\log(1/\rho)}{m}} - \frac{\log(1/\rho)}{3m}\right)$

This bound, derived via Bernstein's inequality, establishes that for small per-example failure rates (such as $\alpha = 0.001$ ), the difference between the empirical certified accuracy $Y/m$ and the true certified test-set accuracy is statistically negligible.
Knowl 10 — Exact Robustness Certification of Binary Linear Classifiers under Gaussian Smoothing
theoretical result
When the base classifier is a binary linear classifier $f(x) = \text{sign}(w^T x + b)$ with weight vector $w \in \mathbb{R}^d$ and bias $b \in \mathbb{R}$ :
1. For any smoothing noise standard deviation $\sigma > 0$ , the smoothed classifier $g$ is identical to the base classifier: $g(x) = f(x)$ for all $x$ where $w^T x + b \ne 0$ .
2. Evaluating the certified radius via randomized smoothing using exact class probabilities $p_A = \mathbb{P}(f(x+\varepsilon) = g(x))$ yields:
$R = \sigma \Phi^{-1}(p_A) = \frac{|w^T x + b|}{\|w\|_2}$

which matches the exact Euclidean geometric distance from $x$ to the decision boundary. For any perturbation radius $r > R$ , there exists a perturbation $\delta$ with $\|\delta\|_2 = r$ such that $g(x + \delta) \ne g(x)$ .
Knowl 11 — Scaling of Certified L2 Radius with Image Resolution under Average Pooling
theoretical result
Let $\mathcal{X}$ denote the space of high-resolution images in $\mathbb{R}^{2k \times 2k \times 3}$ and $\mathcal{X}'$ denote low-resolution images in $\mathbb{R}^{k \times k \times 3}$ , with $\text{AVGPOOL}: \mathcal{X} \to \mathcal{X}'$ denoting the operation that averages each non-overlapping $2 \times 2$ square of pixels.

Given any smoothed classifier $g' = (f', \sigma')$ on low-resolution images $\mathcal{X}'$ , defining the high-resolution base classifier $f(x) = f'(\text{AVGPOOL}(x))$ and noise level $\sigma = 2\sigma'$ constructs a high-resolution smoothed classifier $g = (f, \sigma)$ such that for all $x \in \mathcal{X}$ :

$g(x) = g'(\text{AVGPOOL}(x))$

and $g$ is certifiably robust at $x$ with an $\ell_2$ radius exactly twice that of $g'$ at $\text{AVGPOOL}(x)$ :

$R_{\text{high}} = 2 R_{\text{low}}$

Because higher-resolution images can tolerate larger isotropic Gaussian noise variance without destroying visual semantic content, $\sigma$ can be chosen proportionally larger, naturally producing larger certified $\ell_2$ radii on higher-resolution inputs.
Knowl 12 — Sample Complexity Bottleneck for Certifying Large Radii with High Confidence
limitation
The certified radius $R = \sigma \Phi^{-1}(\underline{p_A})$ depends on the one-sided lower confidence bound $\underline{p_A}$ estimated from $n$ Monte Carlo noise evaluations. In the ideal scenario where the base classifier uniformly classifies all $n$ noisy samples as the top class ( $f(x+\varepsilon) = c_A$ identically), the Clopper-Pearson lower confidence bound at confidence level $1 - \alpha$ satisfies $\underline{p_A} = \alpha^{1/n}$ .

The maximum radius certifiable with $n$ unanimous Monte Carlo samples is therefore:

$R_{\max} = \sigma \Phi^{-1}\left(\alpha^{1/n}\right)$

Because $\Phi^{-1}(\alpha^{1/n})$ grows very slowly with sample count $n$ , certifying a radius of $R = 4\sigma$ at confidence $99.9\%$ ( $\alpha = 0.001$ ) requires approximately $n \approx 10^5$ Monte Carlo samples, creating a computational bottleneck when certifying large radii.

Coverage note — Omitted were intermediate lemma derivations of looser prior bounds (Lecuyer et al. and Li et al.) and auxiliary PGD attack optimization heuristics against smoothed models, as they represent prior art analysis or secondary empirical diagnostics.

References

1.Anil, C., Lucas, J., and Grosse, R. B. Sorting out lipschitz function approximation. In Proceedings of the 36th International Conference on Machine Learning, 2019.
2.Athalye, A. and Carlini, N. On the robustness of the cvpr 2018 white-box adversarial example defenses. The Bright and Dark Sides of Computer Vision: Challenges and Opportunities for Privacy and Security, 2018.
3.Athalye, A., Carlini, N., and Wagner, D. Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples. In Proceedings of the 35th International Conference on Machine Learning, 2018.
4.Biggio, B., Corona, I., Maiorca, D., Nelson, B., rndi, N., Laskov, P., Giacinto, G., and Roli, F. Evasion attacks against machine learning at test time. Joint European Conference on Machine Learning and Knowledge Discovery in Database, 2013.
5.Blanchard, G. Lecture Notes, 2007. URL http://www.math.uni-potsdam.de/~blanchard/lectures/lect_2.pdf.
6.Bunel, R. R., Turkaslan, I., Torr, P., Kohli, P., and Mudigonda, P. K. A unified view of piecewise linear neural network verification. In Advances in Neural Information Processing Systems 31. 2018.
7.Cao, X. and Gong, N. Z. Mitigating evasion attacks to deep neural networks via region-based classification. 33rd Annual Computer Security Applications Conference, 2017.
8.Carlini, N. and Wagner, D. Adversarial examples are not easily detected: Bypassing ten detection methods. In Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security, 2017.
9.Carlini, N., Katz, G., Barrett, C., and Dill, D. L. Provably minimally-distorted adversarial examples. arXiv preprint arXiv: 1709.10207, 2017.
10.Cheng, C.-H., Nhrenberg, G., and Ruess, H. Maximum resilience of artificial neural networks. International Symposium on Automated Technology for Verification and Analysis, 2017.
11.Cisse, M., Bojanowski, P., Grave, E., Dauphin, Y., and Usunier, N. Parseval networks: Improving robustness to adversarial examples. In Proceedings of the 34th International Conference on Machine Learning, 2017.
12.Clopper, C. J. and Pearson, E. S. The use of confidence or fiducial limits illustrated in the case of the binomial. Biometrika, 26(4):pp. 404–413, 1934. ISSN 00063444.
13.Croce, F., Andriushchenko, M., and Hein, M. Provable robustness of relu networks via maximization of linear regions. In Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, 2019.
14.Deng, J., Dong, W., Socher, R., Li, L.-J., Li, K., and Fei-Fei, L. ImageNet: A Large-Scale Hierarchical Image Database. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2009.
15.Dodge, S. and Karam, L. A study and comparison of human and deep learning recognition performance under visual distortions. 2017 26th International Conference on Computer Communication and Networks (ICCCN), 2017.
16.Dutta, S., Jha, S., Sanakaranarayanan, S., and Tiwari, A. Output range analysis for deep neural networks. arXiv preprint arXiv:1709.09130, 2017.
17.Dvijotham, K., Gowal, S., Stanforth, R., Arandjelovic, R., O’Donoghue, B., Uesato, J., and Kohli, P. Training verified learners with learned verifiers. arXiv preprint arXiv:1805.10265, 2018a.
18.Dvijotham, K., Stanforth, R., Gowal, S., Mann, T., and Kohli, P. A dual approach to scalable verification of deep networks. Proceedings of the Thirty-Fourth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-18), 2018b.
19.Ehlers, R. Formal verification of piece-wise linear feedforward neural networks. In Automated Technology for Verification and Analysis, 2017.
20.Fawzi, A., Moosavi-Dezfooli, S.-M., and Frossard, P. Robustness of classifiers: from adversarial to random noise. In Advances in Neural Information Processing Systems 29. 2016.
21.Fischetti, M. and Jo, J. Deep neural networks and mixed integer linear optimization. Constraints, 23(3):296–309, July 2018.
22.Ford, N., Gilmer, J., and Cubuk, E. D. Adversarial examples are a natural consequence of test error in noise. In Proceedings of the 36th International Conference on Machine Learning, 2019.
23.Franceschi, J.-Y., Fawzi, A., and Fawzi, O. Robustness of classifiers to uniform $\ell_p$ and gaussian noise. In 21st International Conference on Artificial Intelligence and Statistics (AISTATS). 2018.
24.Gehr, T., Mirman, M., Drachsler-Cohen, D., Tsankov, P., Chaudhuri, S., and Vechev, M. T. AI2: safety and robustness certification of neural networks with abstract interpretation. In 2018 IEEE Symposium on Security and Privacy, SP 2018, Proceedings, 21-23 May 2018, San Francisco, California, USA, pp. 3–18, 2018.
25.Goodfellow, I. J., Shlens, J., and Szegedy, C. Explaining and harnessing adversarial examples. In International Conference on Learning Representations, 2015.
26.Gouk, H., Frank, E., Pfahringer, B., and Cree, M. Regularisation of neural networks by enforcing lipschitz continuity. arXiv preprint arXiv:1804.04368, 2018.
27.Gowal, S., Dvijotham, K., Stanforth, R., Bunel, R., Qin, C., Uesato, J., Arandjelovic, R., Mann, T., and Kohli, P. On the effectiveness of interval bound propagation for training verifiably robust models, 2018.
28.Hein, M. and Andriushchenko, M. Formal guarantees on the robustness of a classifier against adversarial manipulation. In Advances in Neural Information Processing Systems 30. 2017.
29.Huang, X., Kwiatkowska, M., Wang, S., and Wu, M. Safety verification of deep neural networks. Computer Aided Verification, 2017.
30.Hung, K. and Fithian, W. Rank verification for exponential families. The Annals of Statistics, (2):758–782, 04 2019.
31.Kannan, H., Kurakin, A., and Goodfellow, I. Adversarial logit pairing. arXiv preprint arXiv:1803.06373, 2018.
32.Katz, G., Barrett, C., Dill, D. L., Julian, K., and Kochenderfer, M. J. Reluplex: An efficient smt solver for verifying deep neural networks. Lecture Notes in Computer Science, pp. 97117, 2017. ISSN 1611-3349.
33.Kolter, J. Z. and Madry, A. Adversarial robustness: Theory and practice. https://adversarial-ml-tutorial.org/adversarial_examples/, 2018.
34.Krizhevsky, A. Learning multiple layers of features from tiny images. Technical report, 2009.
35.Kurakin, A., Goodfellow, I. J., and Bengio, S. Adversarial machine learning at scale. 2017. URL https://arxiv.org/abs/1611.01236.
36.Lecuyer, M., Atlidakis, V., Geambasu, R., Hsu, D., and Jana, S. Certified robustness to adversarial examples with differential privacy. In IEEE Symposium on Security and Privacy (SP), 2019.
37.Levine, A., Singla, S., and Feizi, S. Certifiably robust interpretation in deep learning. arXiv preprint arXiv:1905.12105, 2019.
38.Li, B., Chen, C., Wang, W., and Carin, L. Second-order adversarial attack and certifiable robustness. arXiv preprint arXiv:1809.03113, 2018.
39.Liu, X., Cheng, M., Zhang, H., and Hsieh, C.-J. Towards robust neural networks via random self-ensemble. In The European Conference on Computer Vision (ECCV), September 2018.
40.Lomuscio, A. and Maganti, L. An approach to reachability analysis for feed-forward relu neural networks, 2017.
41.Madry, A., Makelov, A., Schmidt, L., Tsipras, D., and Vladu, A. Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations, 2018.
42.Mirman, M., Gehr, T., and Vechev, M. Differentiable abstract interpretation for provably robust neural networks. In Proceedings of the 35th International Conference on Machine Learning, 2018.
43.Moosavi-Dezfooli, S.-M., Fawzi, A., and Frossard, P. Deepfool: A simple and accurate method to fool deep neural networks. 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2016.
44.Neyman, J. and Pearson, E. S. On the problem of the most efficient tests of statistical hypotheses. Philosophical Transactions of the Royal Society of London. Series A, Containing Papers of a Mathematical or Physical Character, 231:289–337, 1933.
45.Raghunathan, A., Steinhardt, J., and Liang, P. Certified defenses against adversarial examples. In International Conference on Learning Representations, 2018a.
46.Raghunathan, A., Steinhardt, J., and Liang, P. Semidefinite relaxations for certifying robustness to adversarial examples. In Advances in Neural Information Processing Systems 31, 2018b.
47.Salman, H., Yang, G., Li, J., Zhang, P., Zhang, H., Razenshteyn, I., and Bubeck, S. Provably robust deep learning via adversarially trained smoothed classifiers. arXiv preprint arXiv:1906.04584, 2019.
48.Singh, G., Gehr, T., Mirman, M., Püschel, M., and Vechev, M. Fast and effective robustness certification. In Advances in Neural Information Processing Systems 31. 2018.
49.Smilkov, D., Thorat, N., Kim, B., Viégas, F., and Wattenberg, M. Smoothgrad: removing noise by adding noise. arXiv preprint arXiv:1706.03825, 2017.
50.Szegedy, C., Zaremba, W., Sutskever, I., Bruna, J., Erhan, D., Goodfellow, I., and Fergus, R. Intriguing properties of neural networks. In International Conference on Learning Representations, 2014.
51.Tjeng, V., Xiao, K. Y., and Tedrake, R. Evaluating robustness of neural networks with mixed integer programming. In International Conference on Learning Representations, 2019. URL https://openreview.net/forum?id=HyGIdiRqtm.
52.Tsipras, D., Santurkar, S., Engstrom, L., Turner, A., and Madry, A. Robustness may be at odds with accuracy. In International Conference on Learning Representations, 2019. URL https://openreview.net/forum?id=SyxAb30cY7.
53.Tsuzuku, Y., Sato, I., and Sugiyama, M. Lipschitz-margin training: Scalable certification of perturbation invariance for deep neural networks. In Advances in Neural Information Processing Systems 31. 2018.
54.Uesato, J., O’Donoghue, B., Kohli, P., and van den Oord, A. Adversarial risk and the dangers of evaluating against weak attacks. In Proceedings of the 35th International Conference on Machine Learning, 2018.
55.Wang, S., Chen, Y., Abdou, A., and Jana, S. Mixtrain: Scalable training of formally robust neural networks. arXiv preprint arXiv:1811.02625, 2018a.
56.Wang, S., Pei, K., Whitehouse, J., Yang, J., and Jana, S. Efficient formal safety analysis of neural networks. In Advances in Neural Information Processing Systems 31. 2018b.
57.Webb, S., Rainforth, T., Teh, Y. W., and Kumar, M. P. Statistical verification of neural networks. In International Conference on Learning Representations, 2019. URL https://openreview.net/forum?id=S1xcx3C5FX.
58.Weng, L., Zhang, H., Chen, H., Song, Z., Hsieh, C.-J., Daniel, L., Boning, D., and Dhillon, I. Towards fast computation of certified robustness for ReLU networks. In Proceedings of the 35th International Conference on Machine Learning, 2018a.
59.Weng, T.-W., Zhang, H., Chen, P.-Y., Yi, J., Su, D., Gao, Y., Hsieh, C.-J., and Daniel, L. Evaluating the robustness of neural networks: An extreme value theory approach. In International Conference on Learning Representations, 2018b.
60.Wong, E. and Kolter, J. Z. Provable defenses against adversarial examples via the convex outer adversarial polytope. In Proceedings of the 35th International Conference on Machine Learning, 2018.
61.Wong, E., Schmidt, F., Metzen, J. H., and Kolter, J. Z. Scaling provable adversarial defenses. In Advances in Neural Information Processing Systems 31, 2018.
62.Zantedeschi, V., Nicolae, M.-I., and Rawat, A. Efficient defenses against adversarial attacks. Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security - AISec 17, 2017.
63.Zhang, H., Weng, T.-W., Chen, P.-Y., Hsieh, C.-J., and Daniel, L. Efficient neural network robustness certification with general activation functions. In Advances in Neural Information Processing Systems 31. 2018.

Citation

MLA

Cohen, J., et al. “Certified Adversarial Robustness via Randomized Smoothing”. International Conference on Machine Learning, vol. 97, 2019, pp. 1310–20, https://proceedings.mlr.press/v97/cohen19c.html.

APA

Cohen, J., Rosenfeld, E., & Kolter, Z. (2019). Certified Adversarial Robustness via Randomized Smoothing. International Conference on Machine Learning, 97, 1310–1320. https://proceedings.mlr.press/v97/cohen19c.html

Chicago

Cohen, J., E. Rosenfeld, and Z. Kolter. 2019. “Certified Adversarial Robustness via Randomized Smoothing”. International Conference on Machine Learning 97: 1310–20. https://proceedings.mlr.press/v97/cohen19c.html.

Harvard

Cohen, J., Rosenfeld, E. and Kolter, Z. (2019) “Certified Adversarial Robustness via Randomized Smoothing”, International Conference on Machine Learning. PMLR, pp. 1310–1320. Available at: https://proceedings.mlr.press/v97/cohen19c.html.

Vancouver

1. Cohen J, Rosenfeld E, Kolter Z (2019) Certified Adversarial Robustness via Randomized Smoothing. In: International Conference on Machine Learning. PMLR, pp 1310–1320

BibTeX

@InProceedings{pmlr-v97-cohen19c,
  title = 	 {Certified Adversarial Robustness via Randomized Smoothing},
  author =       {Cohen, Jeremy and Rosenfeld, Elan and Kolter, Zico},
  booktitle = 	 {Proceedings of the 36th International Conference on Machine Learning},
  pages = 	 {1310--1320},
  year = 	 {2019},
  editor = 	 {Chaudhuri, Kamalika and Salakhutdinov, Ruslan},
  volume = 	 {97},
  series = 	 {Proceedings of Machine Learning Research},
  month = 	 {09--15 Jun},
  publisher =    {PMLR},
  pdf = 	 {http://proceedings.mlr.press/v97/cohen19c/cohen19c.pdf},
  url = 	 {https://proceedings.mlr.press/v97/cohen19c.html},
  abstract = 	 {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 L2 norm. While this "randomized smoothing" technique has been proposed before in the literature, we are the first to provide a tight analysis, which establishes a close connection between L2 robustness and Gaussian noise. We use the technique to train an ImageNet classifier with e.g. a certified top-1 accuracy of 49% under adversarial perturbations with L2 norm less than 0.5 (=127/255). Smoothing is the only approach to certifiably robust classification which has been shown feasible on full-resolution ImageNet. On smaller-scale datasets where competing approaches to certified L2 robustness are viable, smoothing delivers higher certified accuracies. The empirical success of the approach suggests that provable methods based on randomization at prediction time are a promising direction for future research into adversarially robust classification.}
}

Metadata:DOI registry

Source Code

This paper has an official code repository available. Click below to access the source code.

View Repository

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: https://creativecommons.org/licenses/by/4.0/

Certified Adversarial Robustness via Randomized Smoothing

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Tight Certified Robustness Guarantee in L2 Norm for Gaussian Randomized Smoothing

Knowl 2 — Tightness of the Gaussian Randomized Smoothing Robustness Radius

Knowl 3 — Gaussian Randomized Smoothed Classifier

Knowl 4 — Monte Carlo Robustness Certification Algorithm for Smoothed Classifiers

Knowl 5 — Monte Carlo Prediction Algorithm with Abstention for Smoothed Classifiers

Knowl 6 — Certified L2 Accuracy of Gaussian Randomized Smoothing on ImageNet

Knowl 7 — Certified L2 Accuracy of Gaussian Randomized Smoothing on CIFAR-10

Knowl 8 — Training Base Classifiers with Gaussian Data Augmentation as Approximate Likelihood Maximization

Knowl 9 — Finite-Sample Lower Bound on True Certified Test-Set Accuracy

Knowl 10 — Exact Robustness Certification of Binary Linear Classifiers under Gaussian Smoothing

Knowl 11 — Scaling of Certified L2 Radius with Image Resolution under Average Pooling

Knowl 12 — Sample Complexity Bottleneck for Certifying Large Radii with High Confidence

References

Citation

BibTeX

Source Code

Access the Paper