Certified Adversarial Robustness via Randomized Smoothing

Introduction

Modern image classifiers achieve high accuracy on i.i.d. test sets but are not robust to small, adversarially-chosen perturbations of their inputs (Szegedy et al., 2014; Biggio et al., 2013). Given an image $x$ correctly classified by, say, a neural network, an adversary can usually engineer an adversarial perturbation $\delta$ so small that $x+\delta$ looks just like $x$ to the human eye, yet the network classifies $x+\delta$ as a different, incorrect class. Many works have proposed heuristic methods for training classifiers intended to be robust to adversarial perturbations. However, most of these heuristics have been subsequently shown to fail against suitably powerful adversaries (Carlini & Wagner, 2017; Athalye et al., 2018; Uesato et al., 2018). In response, a line of work on certifiable robustness studies classifiers whose prediction at any point $x$ is verifiably constant within some set around $x$ (Wong & Kolter, 2018; Raghunathan et al., 2018a, e.g.). In most of these works, the robust classifier takes the form of a neural network. Unfortunately, all existing approaches for certifying the robustness of neural networks have trouble scaling to networks that are large and expressive enough to solve problems like ImageNet.

Randomized smoothing has one major drawback. If $f$ is a neural network, it is not possible to exactly compute the probabilities with which $f$ classifies $\mathcal{N}(x,\sigma^{2}I)$ as each class. Therefore, it is not possible to exactly evaluate $g$’s prediction at any input $x$, or to exactly compute the radius in which this prediction is certifiably robust. Instead, we present Monte Carlo algorithms for both tasks that are guaranteed to succeed with arbitrarily high probability.

Despite this drawback, randomized smoothing enjoys several compelling advantages over other certifiably robust classifiers proposed in the literature: it makes no assumptions about the base classifier’s architecture, it is simple to implement and understand, and, most importantly, it permits the use of arbitrarily large neural networks as the base classifier. In contrast, other certified defenses do not currently scale to large networks. Indeed, smoothing is the only certified adversarial defense which has been shown feasible on the full-resolution ImageNet classification task.

Related Work

Many works have proposed classifiers intended to be robust to adversarial perturbations. These approaches can be broadly divided into empirical defenses, which empirically seem robust to known adversarial attacks, and certified defenses, which are provably robust to certain kinds of adversarial perturbations.

The most successful empirical defense to date is adversarial training (Goodfellow et al., 2015; Kurakin et al., 2017; Madry et al., 2018), in which adversarial examples are found during training (often using projected gradient descent) and added to the training set. Unfortunately, it is typically impossible to tell whether a prediction by an empirically robust classifier is truly robust to adversarial perturbations; the most that can be said is that a specific attack was unable to find any. In fact, many heuristic defenses proposed in the literature were later “broken” by stronger adversaries (Carlini & Wagner, 2017; Athalye et al., 2018; Uesato et al., 2018; Athalye & Carlini, 2018). Aiming to escape this cat-and-mouse game, a growing body of work has focused on defenses with formal guarantees.

Conservative certification is more scalable. Some conservative methods bound the global Lipschitz constant of the neural network (Gouk et al., 2018; Tsuzuku et al., 2018; Anil et al., 2019; Cisse et al., 2017), but these approaches tend to be very loose on expressive networks. Others measure the local smoothness of the network in the vicinity of a particular input $x$. In theory, one could obtain a robustness guarantee via an upper bound on the local Lipschitz constant of the network (Hein & Andriushchenko, 2017), but computing this quantity is intractable for general neural networks. Instead, a panoply of practical solutions have been proposed in the literature (Wong & Kolter, 2018; Wang et al., 2018a, b; Raghunathan et al., 2018a, b; Wong et al., 2018; Dvijotham et al., 2018b, a; Croce et al., 2019; Gehr et al., 2018; Mirman et al., 2018; Singh et al., 2018; Gowal et al., 2018; Weng et al., 2018a; Zhang et al., 2018). Two themes stand out. Some approaches cast verification as an optimization problem and import tools such as relaxation and duality from the optimization literature to provide conservative guarantees (Wong & Kolter, 2018; Wong et al., 2018; Raghunathan et al., 2018a, b; Dvijotham et al., 2018b, a). Others step through the network layer by layer, maintaining at each layer an outer approximation of the set of activations reachable by a perturbed input (Mirman et al., 2018; Singh et al., 2018; Gowal et al., 2018; Weng et al., 2018a; Zhang et al., 2018). None of these local certification methods have been shown to be feasible on networks that are large and expressive enough to solve modern machine learning problems like the ImageNet classification task. Also, all either assume specific network architectures (e.g. ReLU activations or a layered feedforward structure) or require extensive customization for new network architectures.

Prior works have proposed using a network’s robustness to Gaussian noise as a proxy for its robustness to adversarial perturbations (Weng et al., 2018b; Ford et al., 2019), and have suggested that Gaussian data augmentation could supplement or replace adversarial training (Zantedeschi et al., 2017; Kannan et al., 2018). Smilkov et al. (2017) observed that averaging a classifier’s input gradients over Gaussian corruptions of an image yields very interpretable saliency maps. The robustness of neural networks to random noise has been analyzed both theoretically (Fawzi et al., 2016; Franceschi et al., 2018) and empirically (Dodge & Karam, 2017). Finally, Webb et al. (2019) proposed a statistical technique for estimating the noise robustness of a classifier more efficiently than naive Monte Carlo simulation; we did not use this technique since it appears to lack formal high-probability guarantees. While these works hypothesized relationships between a neural network’s robustness to random noise and the same network’s robustness to adversarial perturbations, randomized smoothing instead uses a classifier’s robustness to random noise to create a new classifier robust to adversarial perturbations.

Randomized smoothing

We will first present our robustness guarantee for the smoothed classifier $g$. Then, since it is not possible to exactly evaluate the prediction of $g$ at $x$ or to certify the robustness of $g$ around $x$, we will give Monte Carlo algorithms for both tasks that succeed with arbitrarily high probability.

Then $g(x+\delta)=c_{A}$ for all $\|\delta\|_{2}<R$, where

Theorem 1 assumes nothing about $f$. This is crucial since it is unclear which well-behavedness assumptions, if any, are satisfied by modern deep architectures.

The certified radius $R$ is large when: (1) the noise level $\sigma$ is high, (2) the probability of the top class $c_{A}$ is high, and (3) the probability of each other class is low.

Assume $\underline{p_{A}}+\overline{p_{B}}\leq 1$. For any perturbation $\delta$ with $\|\delta\|_{2}>R$, there exists a base classifier $f$ consistent with the class probabilities (2) for which $g(x+\delta)\neq c_{A}$.

The complete proofs of Theorems 1 and 2 are in Appendix A. We now sketch the proofs in the special case when there are only two classes.

This “worst-case” $f^{*}$ classifies $\mathcal{N}(x+\delta,\sigma^{2}I)$ as $c_{A}$ with probability $\Phi\left(\Phi^{-1}(\underline{p_{A}})-\frac{\|\delta\|_{2}}{\sigma}\right)$. Therefore, to ensure that even the “worst-case” $f^{*}$ classifies $\mathcal{N}(x+\delta,\sigma^{2}I)$ as $c_{A}$ with probability $>\frac{1}{2}$, we solve for those $\delta$ for which

which is equivalent to the condition $\|\delta\|_{2}<\sigma\Phi^{-1}(\underline{p_{A}})$. ∎

Theorem 2 is a simple consequence: for any $\delta$ with $\|\delta\|_{2}>R$, the base classifier $f^{*}$ defined in (4) is consistent with (2); yet if $f^{*}$ is the base classifier, then $g(x+\delta)=c_{B}$.

2 Practical algorithms

We now present practical Monte Carlo algorithms for evaluating $g(x)$ and certifying the robustness of $g$ around $x$. More details can be found in Appendix C.

Evaluating the smoothed classifier’s prediction $g(x)$ requires identifying the class $c_{A}$ with maximal weight in the categorical distribution $f(x+\varepsilon)$. The procedure described in pseudocode as Predict draws $n$ samples of $f(x+\varepsilon)$ by running $n$ noise-corrupted copies of $x$ through the base classifier. Let $\hat{c}_{A}$ be the class which appeared the largest number of times. If $\hat{c}_{A}$ appeared much more often than any other class, then Predict returns $\hat{c}_{A}$. Otherwise, it abstains from making a prediction. We use the hypothesis test from Hung & Fithian (2019) to calibrate the abstention threshold so as to bound by $\alpha$ the probability of returning an incorrect answer. Predict satisfies the following guarantee:

With probability at least $1-\alpha$ over the randomness in Predict, Predict will either abstain or return $g(x)$. (Equivalently: the probability that Predict returns a class other than $g(x)$ is at most $\alpha$.)

The function SampleUnderNoise($f$, $x$, num, $\sigma$) in the pseudocode draws num samples of noise, $\varepsilon_{1}\ldots\varepsilon_{\text{num}}\sim\mathcal{N}(0,\sigma^{2}I)$, runs each $x+\varepsilon_{i}$ through the base classifier $f$, and returns a vector of class counts. BinomPValue($n_{A}$, $n_{A}+n_{B}$, $p$) returns the p-value of the two-sided hypothesis test that $n_{A}\sim\text{Binomial}(n_{A}+n_{B},p)$.

2.2 Certification

Evaluating and certifying the robustness of $g$ around an input $x$ requires not only identifying the class $c_{A}$ with maximal weight in $f(x+\varepsilon)$, but also estimating a lower bound $\underline{p_{A}}$ on the probability that $f(x+\varepsilon)=c_{A}$ and an upper bound $\overline{p_{B}}$ on the probability that $f(x+\varepsilon)$ equals any other class. Doing all three of these at the same time in a statistically correct manner requires some care. One simple solution is presented in pseudocode as Certify: first, use a small number of samples from $f(x+\varepsilon)$ to take a guess at $c_{A}$; then use a larger number of samples to estimate $\underline{p_{A}}$; then simply take $\overline{p_{B}}=1-\underline{p_{A}}$.

With probability at least $1-\alpha$ over the randomness in Certify, if Certify returns a class $\hat{c}_{A}$ and a radius $R$ (i.e. does not abstain), then $g$ predicts $\hat{c}_{A}$ within radius $R$ around $x$: $g(x+\delta)=\hat{c}_{A}\;\;\forall\;\|\delta\|_{2}<R$.

The function LowerConfBound($k$, $n$, $1-\alpha$) in the pseudocode returns a one-sided $(1-\alpha)$ lower confidence interval for the Binomial parameter $p$ given a sample $k\sim\text{Binomial}(n,p)$.

Recall from Theorem 1 that $R$ approaches $\infty$ as $\underline{p_{A}}$ approaches 1. Unfortunately, it turns out that $\underline{p_{A}}$ approaches 1 so slowly with $n$ that $R$ also approaches $\infty$ very slowly with $n$. Consider the most favorable situation: $f(x)=c_{A}$ everywhere. This means that $g$ is robust at radius $\infty$. But after observing $n$ samples of $f(x+\varepsilon)$ which all equal $c_{A}$, the tightest (to our knowledge) lower bound would say that with probability least $1-\alpha$, $p_{A}\geq\alpha^{(1/n)}$. Plugging $\underline{p_{A}}=\alpha^{(1/n)}$ and $\overline{p_{B}}=1-\underline{p_{A}}$ into (3) yields an expression for the certified radius as a function of $n$: $R=\sigma\,\Phi^{-1}(\alpha^{1/n})$. Figure 5 (right) plots this function for $\alpha=0.001,\sigma=1$. Observe that certifying a radius of $4\sigma$ with 99.9% confidence would require $\approx 10^{5}$ samples.

3 Training the base classifier

Theorem 1 holds regardless of how the base classifier $f$ is trained. However, in order for $g$ to classify the labeled example $(x,c)$ correctly and robustly, $f$ needs to consistently classify $\mathcal{N}(x,\sigma^{2}I)$ as $c$. In high dimension, the Gaussian distribution $\mathcal{N}(x,\sigma^{2}I)$ places almost no mass near its mode $x$. As a consequence, when $\sigma$ is moderately high, the distribution of natural images has virtually disjoint support from the distribution of natural images corrupted by $\mathcal{N}(0,\sigma^{2}I)$; see Figure 2 for a visual demonstration. Therefore, if the base classifier $f$ is trained via standard supervised learning on the data distribution, it will see no noisy images during training, and hence will not necessarily learn to classify $\mathcal{N}(x,\sigma^{2}I)$ with $x$’s true label. Therefore, in this paper we follow Lecuyer et al. (2019) and train the base classifier with Gaussian data augmentation at variance $\sigma^{2}$. A justification for this procedure is provided in Appendix F. However, we suspect that there may be room to improve upon this training scheme, perhaps by training the base classifier so as to maximize the smoothed classifier’s certified accuracy at some tunable radius $r$.

Experiments

In all experiments, unless otherwise stated, we ran Certify with $\alpha=0.001$, so there was at most a 0.1% chance that Certify returned a radius in which $g$ was not truly robust. Unless otherwise stated, when running Certify we used $n_{0}=$ 100 Monte Carlo samples for selection and $n=$ 100,000 samples for estimation.

In the figures above that plot certified accuracy as a function of radius $r$, the certified accuracy always decreases gradually with $r$ until reaching some point where it plummets to zero. This drop occurs because for each noise level $\sigma$ and number of samples $n$, there is a hard upper limit to the radius we can certify with high probability, achieved when all $n$ samples are classified by $f$ as the same class.

Figure 6 plots the certified accuracy attained by smoothing with each $\sigma$. The dashed black line is the empirical upper bound on the robust accuracy of the base classifier architecture; observe that smoothing improves substantially upon the robustness of the undefended base classifier architecture. We see that $\sigma$ controls a robustness/accuracy tradeoff. When $\sigma$ is low, small radii can be certified with high accuracy, but large radii cannot be certified. When $\sigma$ is high, larger radii can be certified, but smaller radii are certified at a lower accuracy. This observation echoes the finding in Tsipras et al. (2019) that adversarially trained networks with higher robust accuracy tend to have lower standard accuracy. Tables of these results are in Appendix E.

Figure 8 (left) plots the certified accuracy obtained using our Theorem 1 guarantee alongside the certified accuracy obtained using the analogous bounds of Lecuyer et al. (2019) and Li et al. (2018). Since our expression for the certified radius $R$ is greater (and, in fact, tight), our bound delivers higher certified accuracies. Figure 8 (middle) projects how the certified accuracy would have changed had Certify used more or fewer samples $n$ (under the assumption that the relative class proportions in counts would have remained constant). Finally, Figure 8 (right) plots the certified accuracy as the confidence parameter $\alpha$ is varied. Observe that the certified accuracy is not very sensitive to $\alpha$.

In Figure 7, we compare the largest publicly released model from Wong et al. (2018), a small resnet, to two randomized smoothing classifiers: one which used the same small resnet architecture for its base classifier, and one which used a larger 110-layer resnet for its base classifier. First, observe that smoothing with the large 110-layer resnet substantially outperforms the baseline (across all hyperparameter settings) at all radii. Second, observe that smoothing with the small resnet also outperformed the method of Wong et al. (2018) at all but the smallest radii. We attribute this latter result to the fact that neural networks trained using the method of Wong et al. (2018) are “typically overregularized to the point that many filters/weights become identically zero,” per that paper. In contrast, the base classifier in randomized smoothing is a fully expressive neural network.

It is computationally expensive to certify the robustness of $g$ around a point $x$, since the value of $n$ in Certify must be very large. However, it is far cheaper to evaluate $g$ at $x$ using Predict, since $n$ can be small. For example, when we ran Predict on ImageNet ($\sigma=0.25$) using $n=$ 100, making each prediction only took 0.15 seconds, and we attained a top-1 test accuracy of 65% (Appendix E).

As discussed earlier, an adversary can potentially force Predict to abstain with high probability. However, it is relatively rare for Predict to abstain on the actual data distribution. On ImageNet ($\sigma=0.25$), Predict with failure probability $\alpha=0.001$ abstained 12% of the time when $n=$ 100, 4% when $n=$ 1000, and 1% when $n=$ 10,000.

When $f$ is linear, there always exists a class-changing perturbation just beyond the certified radius. Since neural networks are not linear, we empirically assessed the tightness of our bound by subjecting an ImageNet smoothed classifier ($\sigma=0.25$) to a projected gradient descent-style adversarial attack (Appendix J.3). For each example, we ran Certify with $\alpha=0.01$, and, if the example was correctly classified and certified robust at radius $R$, we tried finding an adversarial example for $g$ within radius $1.5R$ and within radius $2R$. We succeeded 17% of the time at radius $1.5R$ and 53% of the time at radius $2R$.

Conclusion

Our strong empirical results suggest that randomized smoothing is a promising direction for future research into adversarially robust classification. Many empirical approaches have been “broken,” and provable approaches based on certifying neural network classifiers have not been shown to scale to networks of modern size. It seems to be computationally infeasible to reason in any sophisticated way about the decision boundaries of a large, expressive neural network. Randomized smoothing circumvents this problem: the smoothed classifier is not itself a neural network, though it leverages the discriminative ability of a neural network base classifier. To make the smoothed classifier robust, one need simply make the base classifier classify well under noise. In this way, randomized smoothing reduces the unsolved problem of adversarially robust classification to the comparably solved domain of supervised learning.

Acknowledgements

We thank Mateusz Kwaśnicki for help with Lemma 4 in the appendix, Aaditya Ramdas for pointing us toward the work of Hung & Fithian (2019), and Siva Balakrishnan for helpful discussions regarding the confidence interval in Appendix D. We thank Tolani Olarinre, Adarsh Prasad, Ben Cousins, Ramon Van Handel, Matthias Lecuyer, and Bai Li for useful conversations. Finally, we are very grateful to Vaishnavh Nagarajan, Arun Sai Suggala, Shaojie Bai, Mikhail Khodak, Han Zhao, and Zachary Lipton for reviewing drafts of this work. Jeremy Cohen is supported by a grant from the Bosch Center for AI.

References

Appendix A Proofs of Theorems 1 and 2

Here we provide the complete proofs for Theorem 1 and Theorem 2. We fist prove the following lemma, which is essentially a restatement of the Neyman-Pearson lemma (Neyman & Pearson, 1933) from statistical hypothesis testing.

Without loss of generality, we assume that $h$ is random and write $h(1|x)$ for the probability that $h(x)=1$.

First we prove part 1. We denote the complement of $S$ as $S^{c}$.

The inequality in the middle is due to the fact that $\mu_{Y}(z)\leq t\,\mu_{X}(z)\;\forall z\in S$ and $\mu_{Y}(z)>t\,\mu_{X}(z)\;\forall z\in S^{c}$. The inequality at the end is because both terms in the product are non-negative by assumption.

The proof for part 2 is virtually identical, except both “$\geq$” become “$\leq$.” ∎

Now we state the special case of Lemma 3 for when $X$ and $Y$ are isotropic Gaussians.

This lemma is the special case of Lemma 3 when $X$ and $Y$ are isotropic Gaussians with means $x$ and $x+\delta$.

By Lemma 3 it suffices to simply show that for any $\beta$, there is some $t>0$ for which:

The likelihood ratio for this choice of $X$ and $Y$ turns out to be:

where $a>0$ and $b$ are constants w.r.t $z$, specifically $a=\frac{1}{\sigma^{2}}$ and $b=\frac{-(2\delta^{T}x+\|\delta\|^{2})}{2\sigma^{2}}$.

Therefore, given any $\beta$ we may take $t=\exp(a\beta+b)$, noticing that

Finally, we prove Theorem 1 and Theorem 2.

Then $g(x+\delta)=c_{A}$ for all $\|\delta\|_{2}<R$, where

To show that $g(x+\delta)=c_{A}$, it follows from the definition of $g$ that we need to show that

We now restate and prove Theorem 2, which shows that the bound in Theorem 1 is tight. The assumption below in Theorem 2 that $\underline{p_{A}}+\overline{p_{B}}\leq 1$ is mild: given any $\underline{p_{A}}$ and $\overline{p_{B}}$ which do not satisfy this condition, one could have always redefined $\overline{p_{B}}\leftarrow 1-\underline{p_{A}}$ to obtain a Theorem 1 guarantee with a larger certified radius, so there is no reason to invoke Theorem 1 unless $\underline{p_{A}}+\overline{p_{B}}\leq 1$.

We re-use notation from the preceding proof.

Pick any class $c_{B}$ arbitrarily. Define $A$ and $B$ as above, and consider the function

This function is well-defined, since $A\cap B=\emptyset$ provided that $\underline{p_{A}}+\overline{p_{B}}\leq 1$.

By construction, the function $f^{*}$ satisfies (6) with equalities, since

Therefore, if $f^{*}$ is the base classifier for $g$, then $g(x+\delta)\neq c_{A}$. ∎

A.0.1 Deferred Algebra

Recall that $X\sim\mathcal{N}(x,\sigma^{2}I)$ and $A=\{z:\delta^{T}(z-x)\leq\sigma\|\delta\|\Phi^{-1}(\underline{p_{A}})\}$.

Recall that $X\sim\mathcal{N}(x,\sigma^{2}I)$ and $B=\{z:\delta^{T}(z-x)\leq\sigma\|\delta\|\Phi^{-1}(1-\overline{p_{B}})\}$.

Recall that $Y\sim\mathcal{N}(x+\delta,\sigma^{2}I)$ and $A=\{z:\delta^{T}(z-x)\leq\sigma\|\delta\|\Phi^{-1}(\underline{p_{A}})\}$.

Recall that $Y\sim\mathcal{N}(x+\delta,\sigma^{2}I)$ and $B=\{z:\delta^{T}(z-x)\geq\sigma\|\delta\|\Phi^{-1}(1-\overline{p_{B}})\}$.

Appendix B Smoothing a two-class linear classifier

In this appendix, we analyze what happens when the base classifier $f$ is a two-class linear classifier $f(x)=\text{sign}(w^{T}x+b)$. To match the definition of $g$, we take $\text{sign}(\cdot)$ to be undefined when its argument is zero.

Our first result is that when $f$ is a two-class linear classifier, the smoothed classifier $g$ is identical to the base classifier $f$.

If $f$ is a two-class linear classifier $f(x)=\text{sign}(w^{T}x+b)$, and $g$ is the smoothed version of $f$ with any $\sigma$, then $g(x)=f(x)$ for any $x$ (where $f$ is defined).

A similar calculation shows that $g(x)=-1\iff f(x)=-1$.

If $f$ is a two-class linear classifier $f(x)=\text{sign}(w^{T}x+b)$, and $g$ is the smoothed version of $f$ with any $\sigma$, then invoking Theorem 1 at any $x$ (where $f$ is defined) with $\underline{p_{A}}=p_{A}$ and $\overline{p_{B}}=p_{B}$ will yield the certified radius $R=\frac{|w^{T}x+b|}{\|w\|}$.

In binary classification, $p_{A}=1-p_{B}$, so Theorem 1 returns $R=\sigma\Phi^{-1}(\underline{p_{A}})$.

There are two cases: if $w^{T}x+b>0$, then

Therefore, the bound in Theorem 1 returns a radius of

The previous two propositions imply that when $f$ is a two-class linear classifier, the Theorem 1 bound is “tight” in the sense that there always exists a class-changing perturbation just beyond the certified radius.Note that this is a different sense of “tight” than the sense in which Theorem 2 proves that Theorem 1 is tight. Theorem 2 proves that for any fixed perturbation $\delta$ outside the radius certified by Theorem 1, there exists a base classifier $f$ for which $g(x+\delta)\neq g(x)$. In contrast, Proposition 5 proves that for any fixed binary linear base classifier $f$, there exists a perturbation $\delta$ just outside the radius certified by Theorem 1 for which $g(x+\delta)\neq g(x)$.

Let $f$ be a two-class linear classifier $f(x)=\text{sign}(w^{T}x+b)$, let $g$ be the smoothed version of $f$ for some $\sigma$, let $x$ be any point (where $f$ is defined), and let $R$ be the radius certified around $x$ by Theorem 1. Then for any radius $r>R$, there exists a perturbation $\delta$ with $\|\delta\|_{2}=r$ for which $g(x+\delta)\neq g(x)$.

By Proposition 3 it suffices to show that there exists some perturbation $\delta$ with $\|\delta\|_{2}=r$ for which $f(x+\delta)\neq f(x)$.

By Proposition 4, we know that $R=\frac{|w^{T}x+b|}{\|w\|_{2}}$.

If $w^{T}x+b>0$, consider the perturbation $\delta=-\frac{w}{\|w\|_{2}}r$. This perturbation satisfies $\|\delta\|_{2}=r$ and

Likewise, if $w^{T}x+b<0$, then consider the perturbation $\delta=\frac{w}{\|w\|_{2}}r$. This perturbation satisfies $\|\delta\|_{2}=r$ and $f(x+\delta)=-1$.

This special property of two-class linear classifiers is not true in general. In fact, it is possible to construct situations where $g$’s prediction around some point $x_{0}$ is robust at radius $\infty$, yet Theorem 1 only certifies a radius of $\tau$, where $\tau$ is arbitrarily close to zero.

For any $\tau>0$, there exists a base classifier $f$ and an input $x_{0}$ for which the corresponding smoothed classifier $g$ is robust around $x_{0}$ at radius $\infty$, yet Theorem 1 only certifies a radius of $\tau$ around $x_{0}$.

Let $t=-\Phi^{-1}(\frac{1}{2}\Phi(\tau))$ and consider the following base classifier:

Let $g$ be the smoothed version of $f$ with $\sigma=1$. We will show that $g(x)=1$ everywhere, implying that $g$’s prediction is robust around $x_{0}=0$ with radius $\infty$. Yet Theorem 1 only certifies a radius of $\tau$ around $x_{0}$.

Let $Z\sim\mathcal{N}(0,1)$. For any $x$, we have:

so by Theorem 1, the certified radius around $x_{0}$ is $R=\tau$.

The proof of Proposition 6 employed the following lemma, which formalizes the visually obvious fact that out of all intervals of some fixed width $2t$, the interval with maximal mass under the standard normal distribution $Z$ is the interval $[-t,t]$.

Let $\phi$ be the PDF of the standard normal distribution. Since $\phi$ is symmetric about the origin (i.e. $\phi(x)=\phi(-x)\;\forall x$),

where the inequality is because $\phi$ is monotonically decreasing on $[0,\infty)$.

Note that by construction, $a+b=2t$, and $0\leq a\leq t$ and $t\leq b\leq 2t$.

where the inequality is again because $\phi$ is monotonically decreasing on $[0,\infty)$. ∎

Appendix C Practical algorithms

In this appendix, we elaborate on the prediction and certification algorithms described in Section 3.2. The pseudocode in Section 3.2 makes use of several helper functions:

SampleUnderNoise($f$, $x$, num, $\sigma$) works as follows:

Draw num samples of noise, $\varepsilon_{1}\ldots\varepsilon_{\text{num}}\sim\mathcal{N}(0,\sigma^{2}I)$.

Run the noisy images through the base classifier $f$ to obtain the predictions $f(x+\varepsilon_{1}),\ldots,f(x+\varepsilon_{\text{num}})$.

Return the counts for each class, where the count for class $c$ is defined as $\sum_{i=1}^{\text{num}}\mathbf{1}[f(x+\varepsilon_{i})=c]$.

BinomPValue($n_{A}$, $n_{A}+n_{B}$, $p$) returns the p-value of the two-sided hypothesis test that $n_{A}\sim\text{Binomial}(n_{A}+n_{B},p)$. Using scipy.stats.binom_test, this can be implemented as: binom_test(nA, nA + nB, p).

LowerConfBound($k$, $n$, $1-\alpha$) returns a one-sided $(1-\alpha)$ lower confidence interval for the Binomial parameter $p$ given that $k\sim\text{Binomial}(n,p)$. In other words, it returns some number $\underline{p}$ for which $\underline{p}\leq p$ with probability at least $1-\alpha$ over the sampling of $k\sim\text{Binomial}(n,p)$. Following Lecuyer et al. (2019), we chose to use the Clopper-Pearson confidence interval, which inverts the Binomial CDF (Clopper & Pearson, 1934). Using statsmodels.stats.proportion.proportion_confint, this can be implemented as

The randomized algorithm given in pseudocode as Predict leverages the hypothesis test given in Hung & Fithian (2019) for identifying the top category of a multinomial distribution. Predict has one tunable hyperparameter, $\alpha$. When $\alpha$ is small, Predict abstains frequently but rarely returns the wrong class. When $\alpha$ is large, Predict usually makes a prediction, but may often return the wrong class.

We now prove that with high probability, Predict will either return $g(x)$ or abstain.

Proposition 1 (restated). With probability at least $1-\alpha$ over the randomness in Predict, Predict will either abstain or return $g(x)$. (Equivalently: the probability that Predict returns a class other than $g(x)$ is at most $\alpha$.)

We can describe the randomized procedure Predict as follows:

Sample a vector of class counts $\{n_{c}\}_{c\in\mathcal{Y}}$ from $\text{Multinomial}(\{p_{c}\}_{c\in\mathcal{Y}},n)$.

Let $\hat{c}_{A}=\operatorname*{arg\,max}_{c}n_{c}$ be the class whose count is largest. Let $n_{A}$ and $n_{B}$ be the largest count and the second-largest count, respectively.

If the p-value of the two-sided hypothesis test that $n_{A}$ is drawn from $\text{Binom}\left(n_{A}+n_{B},\frac{1}{2}\right)$ is less than $\alpha$, then return $\hat{c}_{A}$. Else, abstain.

The quantities $c_{A}$ and the $p_{c}$’s are fixed but unknown, while the quantities $\hat{c}_{A}$, the $n_{c}$’s, $n_{A}$, and $n_{B}$ are random.

We’d like to prove that the probability that Predict returns a class other than $c_{A}$ is at most $\alpha$. Predict returns a class other than $c_{A}$ if and only if (1) $\hat{c}_{A}\neq c_{A}$ and (2) Predict does not abstain.

Recall that Predict does not abstain if and only if the p-value of the two-sided hypothesis test that $n_{A}$ is drawn from $\textrm{Binom}(n_{A}+n_{B},\frac{1}{2})$ is less than $\alpha$. Theorem 1 in Hung & Fithian (2019) proves that the conditional probability that this event occurs given that $\hat{c}_{A}\neq c_{A}$ is exactly $\alpha$. That is,

C.2 Certification

Suppose for simplicity that we already knew $c_{A}$ and needed to obtain $\underline{p_{A}}$. We could collect $n$ samples of $f(x+\varepsilon)$, count how many times $f(x+\varepsilon)=c_{A}$, and use a Binomial confidence interval to obtain a lower bound on $p_{A}$ that holds with probability at least $1-\alpha$ over the $n$ samples.

However, estimating $\underline{p_{A}}$ and $\overline{p_{B}}$ while simultaneously identifying the top class $c_{A}$ is a little bit tricky, statistically speaking. We propose a simple two-step procedure. First, use $n_{0}$ samples from $f(x+\varepsilon)$ to take a guess $\hat{c}_{A}$ at the identity of the top class $c_{A}$. In practice we observed that $f(x+\varepsilon)$ tends to put most of its weight on the top class, so $n_{0}$ can be set very small. Second, use $n$ samples from $f(x+\varepsilon)$ to obtain some $\underline{p_{A}}$ and $\overline{p_{B}}$ for which $\underline{p_{A}}\leq p_{A}$ and $\overline{p_{B}}\geq p_{B}$ with probability at least $1-\alpha$. We observed that it is much more typical for the mass of $f(x+\varepsilon)$ not allocated to $c_{A}$ to be allocated entirely to one runner-up class than to be allocated uniformly over all remaining classes. Therefore, the quantity $1-\underline{p_{A}}$ is a reasonably tight upper bound on $p_{B}$. Hence, we simply set $\overline{p_{B}}=1-\underline{p_{A}}$, so our bound becomes

The full procedure is described in pseudocode as Certify. If $\underline{p_{A}}<\frac{1}{2}$, we abstain from making a certification; this can occur especially if $\hat{c}_{A}\neq g(x)$, i.e. if we misidentify the top class using the first $n_{0}$ samples of $f(x+\varepsilon)$.

Proposition 2 (restated). With probability at least $1-\alpha$ over the randomness in Certify, if Certify returns a class $\hat{c}_{A}$ and a radius $R$ (i.e. does not abstain), then we have the robustness guarantee

Appendix D Estimating the certified test-set accuracy

In this appendix, we show how to convert the “approximate certified test accuracy” considered in the main paper into a lower bound on the true certified test accuracy that holds with high probability over the randomness in Certify.

Consider a classifier $g$, a test set $S=\{(x_{1},c_{1})\ldots(x_{m},c_{m})\}$, and a radius $r$. For each example $i\in[m]$, let $z_{i}$ indicate whether $g$’s prediction at $x_{i}$ is both correct and robust at radius $r$, i.e.

For any $\rho>0$, with probability at least $1-\rho$ over the randomness in Certify,

Let $m_{\text{good}}=\sum_{i=1}^{m}z_{i}$ and $m_{\text{bad}}=\sum_{i=1}^{m}(1-z_{i})$ be the number of test examples on which $z_{i}=1$ or $z_{i}=0$, respectively. We model $Y_{i}\sim\text{Bernoulli}(p_{i})$, where $p_{i}$ is in general unknown. Let $Y_{\text{good}}=\sum_{i:z_{i}=1}Y_{i}$ and $Y_{\text{bad}}=\sum_{i:z_{i}=0}Y_{i}$. The quantity of interest, the certified accuracy $\frac{1}{m}\sum_{i=1}^{m}z_{i}$, is equal to $m_{\text{good}}/m$. However, we only observe $Y=Y_{\text{good}}+Y_{\text{bad}}$.

From now on, we manipulate this inequality — remember that it holds with probability at least $1-\rho$.

Since $Y=Y_{\text{good}}+Y_{\text{bad}}$, may write

Since $m_{\text{good}}\geq Y_{\text{good}}$, we may write

Since $m_{\text{good}}+m_{\text{bad}}=m$, we may write

Finally, in order to make this confidence interval depend only on observables, we use $m_{\text{bad}}\leq m$ to write

Dividing both sides of the inequality by $m$ recovers the theorem statement.

Appendix E ImageNet and CIFAR-10 Results

Tables 2 and 3 show the approximate certified top-1 test set accuracy of randomized smoothing on ImageNet and CIFAR-10 with various noise levels $\sigma$. By “approximate certified accuracy,” we mean that we ran Certify on a subsample of the test set, and for each $r$ we report the fraction of examples on which Certify (a) did not abstain, (b) returned the correct class, and (c) returned a radius $R$ greater than $r$. There is some probability (at most $\alpha$) that any example’s certification is inaccurate. We used $\alpha=0.001$ and $n=100000$. On CIFAR-10 our base classifier was a 110-layer residual network and we certified the full test set; on ImageNet our base classifier was a ResNet-50 and we certified a subsample of 500 points. Note that the certified accuracy at $r=0$ is just the standard accuracy of the smoothed classifier. See Appendix J for more experimental details.

E.2 Prediction

Table 4 shows the performance of Predict as the number of Monte Carlo samples $n$ is varied between 100 and 10,000. Suppose that for some test example $(x,c)$, Predict returns the label $\hat{c}_{A}$. We say that this prediction was correct if $\hat{c}_{A}=c$ and we say that this prediction was accurate if $\hat{c}_{A}=g(x)$. For example, a prediction could be correct but inaccurate if $g$ is wrong at $x$, yet Predict accidentally returns the correct class. Ideally, we’d like Predict to be both correct and accurate.

With $n=$ 100 Monte Carlo samples and a failure rate of $\alpha=0.001$, Predict is cheap to evaluate (0.15 seconds on our hardware) yet it attains relatively high top-1 accuracy of 65% on the ImageNet test set, and only abstains 12% of the time. When we use $n=$ 10,000 Monte Carlo samples, Predict takes longer to evaluate (15 seconds), yet only abstains 4% of the time. Interestingly, we observe from Table 4 that most of the abstentions when $n=100$ were for examples on which $g$ was wrong, so in practice we would lose little accuracy by taking $n$ to be as small as 100.

Appendix F Training with Noise

As mentioned in section 3.3, in the experiments for this paper, we followed Lecuyer et al. (2019) and trained the base classifier by minimizing the cross-entropy loss with Gaussian data augmentation. We now provide some justification for this idea.

Let $\{(x_{1},c_{1}),\ldots,(x_{n},c_{n})\}$ be a training dataset. We assume that the base classifier takes the form $f(x)=\operatorname*{arg\,max}_{c\in\mathcal{Y}}f_{c}(x)$, where each $f_{c}$ is the scoring function for class $c$.

Suppose that our goal is to maximize the sum of of the log-probabilities that $f$ will classify each $x_{i}+\varepsilon$ as $c_{i}$:

Recall that the softmax function can be interpreted as a continuous, differentiable approximation to $\operatorname*{arg\,max}$:

Therefore, our objective is approximately equal to:

By Jensen’s inequality and the concavity of $\log$, this quantity is lower-bounded by:

which is the negative of the cross-entropy loss under Gaussian data augmentation.

Therefore, minimizing the cross-entropy loss under Gaussian data augmentation will maximize (18), which will approximately maximize (17).

Appendix G Noise Level can Scale with Input Resolution

The argument above can be made rigorous, though we first need to decide what it means for two images to be high- and low-resolution versions of each other. Here we present one solution:

Let $\mathcal{X}$ denote the space of “high-resolution” images in dimension $2k\times 2k\times 3$, and let $\mathcal{X}^{\prime}$ denote the space of “low-resolution” images in dimension $k\times k\times 3$. Let $\textsc{AvgPool}:\mathcal{X}\to\mathcal{X}^{\prime}$ be the function which takes as input an image $x$ in dimension $2k\times 2k\times 3$, averages together every 2x2 square of pixels, and outputs an image in dimension $k\times k\times 3$.

Equipped with these definitions, we can say that $(x,x^{\prime})\in\mathcal{X}\times\mathcal{X}^{\prime}$ are a high/low resolution image pair if $x^{\prime}=\textsc{AvgPool}(x)$.

Given any smoothing classifier $g^{\prime}:\mathcal{X}^{\prime}\to\mathcal{Y}$, one can construct a smoothing classifier $g:\mathcal{X}\to\mathcal{Y}$ with the following property: for any $x\in\mathcal{X}$ and $x^{\prime}=\textsc{AvgPool}(x)$, $g$ predicts the same class at $x$ that $g^{\prime}$ predicts at $x^{\prime}$, but is certifiably robust at twice the radius.

Given some smoothing classifier $g^{\prime}=(f^{\prime},\sigma^{\prime})$ from $\mathcal{X}^{\prime}$ to $\mathcal{Y}$, define $g$ to be the smoothing classifier $(f,\sigma)$ from $\mathcal{X}$ to $\mathcal{Y}$ with noise level $\sigma=2\sigma^{\prime}$ and base classifier $f(x)=f^{\prime}(\textsc{AvgPool}(x))$. Note that the average of four independent copies of $\mathcal{N}(0,(2\sigma)^{2})$ is distributed as $\mathcal{N}(0,\sigma^{2})$. Therefore, for any high/low-resolution image pair $x^{\prime}=\textsc{AvgPool}(x)$, the random variable $\textsc{AvgPool}(x+\varepsilon)$, where $\varepsilon\sim\mathcal{N}(0,(2\sigma)^{2}I_{2k\times 2k\times 3})$, is equal in distribution to the random variable $x^{\prime}+\varepsilon^{\prime}$, where $\varepsilon^{\prime}\sim\mathcal{N}(0,\sigma^{2}I_{k\times k\times 3})$. Hence, $f(x+\varepsilon)=f^{\prime}(\textsc{AvgPool}(x+\varepsilon))$ has the same distribution as $f^{\prime}(x^{\prime}+\varepsilon^{\prime})$. By the definition of $g$, this means that $g(x)=g^{\prime}(x^{\prime})$, Additionally, by Theorem 1, since $\sigma=2\sigma^{\prime}$, this means that $g$’s prediction at $x$ is certifiably robust at twice the radius as $g^{\prime}$’s prediction at $x^{\prime}$. ∎

Appendix H Additional Experiments

H.2 High-probability guarantees

Appendix D details how to use Certify to obtain a lower bound on the certified test accuracy at radius $r$ of a randomized smoothing classifier that holds with high probability over the randomness in Certify. In the main paper, we declined to do this and simply reported the approximate certified test accuracy, defined as the fraction of test examples for which Certify gives the correct prediction and certifies it at radius $r$. Of course, with some probability (guaranteed to be less than $\alpha$), each of these certifications is wrong.

However, we now demonstrate empirically that there is a negligible difference between a proper high-probability lower bound on the certified accuracy and the approximate version that we reported in the paper. We created a randomized smoothing classifier $g$ on ImageNet with a ResNet-50 base classifier and noise level $\sigma=0.25$. We used Certify with $\alpha=0.001$ to certify a subsample of 500 examples from the ImageNet test set. From this we computed the approximate certified test accuracy at each radius $r$. Then we used the correction from Appendix D with $\rho=0.001$ to obtain a lower bound on the certified test accuracy at $r$ that holds pointwise with probability at least $1-\rho$ over the randomness in Certify. Figure 14 plots both quantities as a function of $r$. Observe that the difference is so negligible that the lines almost overlap.

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

In the main paper, whenever we created a randomized smoothing classifier $g$ at noise level $\sigma$, we always trained the corresponding base classifier $f$ with Gaussian data augmentation at noise level $\sigma$. In Figure 15, we show the effects of training the base classifier with a different level of Gaussian noise. Observe that $g$ has a lower certified accuracy if $f$ was trained using a different noise level. It seems to be worse to train with noise $<\sigma$ than to train with noise $>\sigma$.

Appendix I Derivation of Prior Randomized Smoothing Guarantees

In this appendix, we derive the randomized smoothing guarantees of Lecuyer et al. (2019) and Li et al. (2018) using the notation of our paper. Both guarantees take same general form as ours, except with a different expression for $R$:

Then $g(x+\delta)=c_{A}$ for all $\|\delta\|_{2}<R$.

For convenience, define the notation $X\sim\mathcal{N}(x,\sigma^{2}I)$ and $Y\sim\mathcal{N}(x+\delta,\sigma^{2}I)$.

Lecuyer et al. (2019) proved a version of the generic robustness guarantee in which

In order to avoid notation that conflicts with the rest of this paper, we use $\beta$ and $\gamma$ where Lecuyer et al. (2019) used $\epsilon$ and $\delta$.

Suppose that we have some $0<\beta\leq 1$ and $\gamma>0$ such that

The “Gaussian mechanism” from differential privacy guarantees that:

See Lecuyer et al. (2019), Lemma 2 for how to obtain this form from the standard form of the $(\beta,\gamma)$ DP definition.

Since the RHS is always positive, and the denominator on the LHS is always positive, this condition can only possibly hold if the numerator on the LHS is positive. Therefore, we need to restrict $\beta$ to

Since $\underline{p_{A}}\leq 1$ and $\overline{p_{B}}\geq 0$, the denominator in the LHS is $\leq 1$ which is in turn $\leq$ the numerator on the LHS. Therefore, the term inside the log in the LHS is greater than 1, so the log term on the LHS is greater than zero. Therefore, we may divide both sides of the inequality by the log term on the LHS to obtain:

Finally, we take the square root and maximize the bound over all valid $\beta$ (28) to yield:

Figure 16(a) plots this bound at varying settings of the tuning parameter $\beta$, while Figure 16(c) plots how the bound varies with $\beta$ for a fixed $\underline{p_{A}}$ and $\overline{p_{B}}$.

I.2 Li et al. (2018)

Li et al. (2018) proved a version of the generic robustness guarantee in which

A generalization of KL divergence, the $\alpha$-Renyi divergence is an information theoretic measure of distance between two distributions. It is parameterized by some $\alpha>0$. The $\alpha$-Renyi divergence between two discrete distributions $P$ and $Q$ is defined as:

In the continuous case, this sum is replaced with an integral. The divergence is undefined when $\alpha=1$ since a division by zero occurs, but the limit of $D_{\alpha}(P||Q)$ as $\alpha\to 1$ is the KL divergence between $P$ and $Q$.

Li et al. (2018) prove that if $P$ is a discrete distribution for which the highest probability class has probability $\geq\underline{p_{A}}$ and all other classes have probability $\leq\overline{p_{B}}$, then for any other discrete distribution $Q$ for which

the highest-probability class in $Q$ is guaranteed to be the same as the highest-probability class in $P$.

We now apply this result to the discrete distributions $P=f(X)$ and $Q=f(Y)$. If $D_{\alpha}(f(X)||f(Y))$ satisfies (33), then it is guaranteed that $g(x)=g(x+\delta)$.

The data processing inequality states that applying a function to two random variables can only decrease the $\alpha$-Renyi divergence between them. In particular,

There is a closed-form expression for the $\alpha$-Renyi divergence between two Gaussians:

Therefore, we can guarantee that $g(x+\delta)=c_{A}$ so long as

Finally, since this result holds for any $\alpha>0$, we may maximize over $\alpha$ to obtain the largest possible certified radius:

Figure 16(b) plots this bound at varying settings of the tuning parameter $\alpha$, while figure 16(d) plots how the bound varies with $\alpha$ for a fixed $\underline{p_{A}}$ and $\overline{p_{B}}$.

Appendix J Experiment Details

In image classification it is common practice to preprocess a dataset by subtracting from each channel the mean over the dataset, and dividing each channel by the standard deviation over the dataset. However, we wanted to report certified radii in the original image coordinates rather than in the standardized coordinates. Therefore, throughout most of this work we first added the Gaussian noise, and then standardized the channels, before feeding the image to the base classifier. (In the practical PyTorch implementation, the first layer of the base classifier was a layer that standardized the input.) However, all of the baselines we compared against provided pre-trained networks which assumed that the dataset was first preprocessed in a specific way. Therefore, when comparing against the baselines we also preprocessed the datasets first, so that we could report certified radii that were directly comparable to the radii reported by the baseline methods.

Following Wong et al. (2018), the CIFAR-10 dataset was preprocessed by subtracting $(0.485,0.456,0.406)$ and dividing by $(0.225,0.225,0.225)$.

For randomized smoothing we used $\sigma=0.6$ and a 20-layer residual network base classifier. We ran Certify with $n_{0}=100$, $n=$ 100,000 and $\alpha=0.001$.

For both methods, we certified the full CIFAR-10 test set.

Following Tsuzuku et al. (2018), the SVHN dataset was not preprocessed except that pixels were divided by 255 so as to lie within .

We compared against a pretrained network provided to us by the authors in which the hyperparameter of their method was set to $c=0.1$. The network was a wide residual network with 16 layers and a width factor of 4. We used the authors’ code at https://github.com/ytsmiling/lmt to compute the robustness radius of test images.

For randomized smoothing we used $\sigma=0.1$ and a 20-layer residual network base classifier. We ran Certify with $n_{0}=100$, $n=$ 100,000 and $\alpha=0.001$.

For both methods, we certified the whole SVHN test set.

Following Zhang et al. (2018), the CIFAR-10 dataset was preprocessed by subtracting 0.5 from each pixel.

We compared against the cifar_7_1024_vanilla network released by the authors, which is a 7-layer MLP. We used the authors’ code at https://github.com/IBM/CROWN-Robustness-Certification to compute the robustness radius of test images.

For randomized smoothing we used $\sigma=1.2$ and a 20-layer residual network base classifier. We ran Certify with $n_{0}=100$, $n=$ 100,000 and $\alpha=0.001$.

For randomized smoothing, we certified the whole CIFAR-10 test set. For Zhang et al. (2018), we certified every fourth image in the CIFAR-10 test set.

J.2 ImageNet and CIFAR-10 Experiments

Our code is available at http://github.com/locuslab/smoothing.

In order to report certified radii in the original coordinates, we first added Gaussian noise, and then standardized the data. Specifically, in our PyTorch implementation, the first layer of the base classifier was a normalization layer that performed a channel-wise standardization of its input. For CIFAR-10 we subtracted the dataset mean $(0.4914,0.4822,0.4465)$ and divided by the dataset standard deviation $(0.2023,0.1994,0.2010)$. For ImageNet we subtracted the dataset mean $(0.485,0.456,0.406)$ and divided by the standard deviation $(0.229,0.224,0.225)$.

For both ImageNet and CIFAR-10, we trained the base classifier with random horizontal flips and random crops (in addition to the Gaussian data augmentation discussed explicitly in the paper). On ImageNet we trained with synchronous SGD on four NVIDIA RTX 2080 Ti GPUs; training took approximately three days.

On ImageNet our base classifier used the ResNet-50 architecture provided in torchvision. On CIFAR-10 we used a 110-layer residual network from https://github.com/bearpaw/pytorch-classification.

On ImageNet we certified every 100-th image in the validation set, for 500 images total. On CIFAR-10 we certified the whole test set.

In Figure 8 (middle) we fixed $\sigma=0.25$ and $\alpha=0.001$ while varying the number of samples $n$. We did not actually vary the number of samples $n$ that we simulated: we kept this number fixed at 100,000 but varied the number that we fed the Clopper-Pearson confidence interval.

In Figure 8 (right), we fixed $\sigma=0.25$ and $n=$100,000 while varying $\alpha$.

J.3 Adversarial Attacks

As discussed in Section 4, we subjected smoothed classifiers to a projected gradient descent-style adversarial attack. We now describe the details of this attack.

In practice, our step size was $\eta=0.1$, we used $T=20$ steps of PGD, and we computed the stochastic gradient using $k=1000$ Monte Carlo samples.

Unfortunately, the objective we optimize (39) is not actually the attack objective of interest. To force a misclassification, an attacker needs to find some perturbation $\delta$ with $\|\delta\|_{2}<r$ and some class $c_{B}$ for which

Effective adversarial attacks against randomized smoothing are outside the scope of this paper.

Appendix K Examples of Noisy Images

We now show examples of CIFAR-10 and ImageNet images corrupted with varying levels of noise.