A UNIFIED FRAMEWORK FOR RANDOMIZED SMOOTHING BASED CERTIFIED DEFENSES
Year: 2019

Abstract:
Randomized smoothing, which was recently proved to be a certified defensive technique, has received considerable attention due to its scalability to large datasets and neural networks. However, several important questions still remain unanswered in the existing frameworks, such as (i) whether Gaussian mechanism is an optimal choice for certifying `2-normed robustness, and (ii) whether randomized smoothing can certify `∞-normed robustness (on high-dimensional datasets like ImageNet). To answer these questions, we introduce a unified and selfcontained framework to study randomized smoothing-based certified defenses, where we mainly focus on the two most popular norms in adversarial machine learning, i.e., `2 and `∞ norm. We answer the above two questions by first demonstrating that Gaussian mechanism and Exponential mechanism are the (near) optimal options to certify the `2 and `∞-normed robustness. We further show that the largest `∞ radius certified by randomized smoothing is upper bounded by O(1/ √ d), where d is the dimensionality of the data. This theoretical finding suggests that certifying `∞-normed robustness by randomized smoothing may not be scalable to high-dimensional data. The veracity of our framework and analysis is verified by extensive evaluations on CIFAR10 and ImageNet.

text: √ d), where d is the dimensionality of the data. This theoretical finding sug-
gests that certifying `∞-normed robustness by randomized smoothing may not be scalable to high-dimensional data. The veracity of our framework and analysis is verified by extensive evaluations on CIFAR10 and ImageNet.

heading: 1 INTRODUCTION
text: The past decade has witnessed tremendous success of deep learning in handling various learning tasks like image classification (Krizhevsky et al., 2012), natural language processing (Cho et al., 2014), and game playing (Silver et al., 2016). Nevertheless, a major unresolved issue of deep learning is its vulnerability to adversarial samples that are almost indistinguishable from natural samples to humans but can mislead deep neural networks (DNNs) to make wrong predictions with high confidence (Szegedy et al., 2013; Goodfellow et al., 2014). This phenomenon, referred to as adversarial attack, is considered to be one of the biggest threats to the deployment of many deep learning systems. Thus, a great deal of effort has been devoted to developing defensive techniques for it. However, the majority of the existing defenses are of heuristic nature (i.e., without any theoretical guarantees), implying that they may be ineffective against stronger attacks. Recent works (He et al., 2017; Athalye et al., 2018; Uesato et al., 2018) have confirmed this concern, and showed that most of those heuristic defenses actually fail to defend stronger adaptive attacks. This forces us to shift our attentions to certifiable defenses as they can classify all the samples in a predefined neighborhood of the natural samples with a theoretically-guaranteed error bound. Among all existing certifiable defensive techniques, randomized smoothing emerges as the most popular one due to its scalability to large datasets and arbitrary networks. Remarkably, using the Gaussian mechanism for randomized smoothing, Cohen et al. (2019) successfully certify 49% accuracy on the original ImageNet dataset under adversarial perturbations with `2 norm less than 0.5. Despite these successes, there are still several unanswered questions regarding randomized smoothing based certified defenses. One of such questions is, why should Gaussian noise be used for randomized smoothing to certify `2-normed robustness, and is Gaussian mechanism the best option? Another important question is regarding the generalizability of this method to other norms, especially the `∞ norm. If randomized smoothing can be used to certify `∞-normed robustness, what mechanism is the optimal choice?
To shed light on the above questions, we propose in this paper a unified and self-contained framework for randomized smoothing-based certified defenses. We look at the problem from a differential privacy’s point of view and present two types of robustness in this framework. One is motivated by
-differential privacy ( -DP), which uses∞-divergence to measure the distance between the probabilities of predictions on randomized natural samples and randomized adversarial samples and is therefore called D∞ robustness. The other is inspired by -zero concentrated differential privacy ( -zCDP) that uses the Maximal Relative Rényi (MR) divergence as the probability distance measurement and is called DMR robustness. For both of them, we focus on certifying robustness in either `2 or `∞ norm by randomized smoothing. Specifically, our contributions are five-fold:
1. We propose a unified and self-contained framework for certifyingD∞ and/orDMR robustness in `2 and `∞ norms by randomized smoothing.
2. In our framework, we demonstrate that the Gaussian mechanism is a near optimal choice for certifying DMR robustness in `2 norm, and the robust radius is O(1).
3. We also prove that an exponential mechanism is the optimal choice for certifying D∞ robustness in `∞ norm, but the robust radius is only O(1/d), making it unscalable to highdimensional data.
4. We show that the Gaussian mechanism is also a near optimal choice for certifyingDMR robustness in `∞ norm, but the robust radius isO(1/ √ d log d), making it also hardly scalable
to high-dimensional data. 5. The largest robust `∞ radius that can be certified by randomized smoothing to achieve DMR robustness is upper bounded by O(1/ √ d).
Table 1 summarizes the (near) optimal mechanisms of our framework for certifying the `2 and `∞- normed robustness.

heading: 2 RELATED WORK
text: There are three main approaches for certified defenses. The first approach formulates the task of adversarial verification as an optimization problem and solves it by relaxations (Dvijotham et al., 2018; Raghunathan et al., 2018; Wong & Kolter, 2018). The second approach uses different techniques, such as interval analysis and abstract interpretations, to maintain an outer approximation of the output at each layer through the network. (Mirman et al., 2018; Wang et al., 2018; Gowal et al., 2018). The third approach uses randomized smoothing to certify robustness, and is gaining popularity recently due to its strong scalability (Lecuyer et al., 2018; Li et al., 2018; Cohen et al., 2019) to large datasets and arbitrary networks. For this approach, Lecuyer et al. (2018) showed that randomized smoothing can certify the `2 and `1-normed robustness by using inequalities from differential privacy. Li et al. (2018) achieved a stronger guarantee on the `2-normed robustness using tools from information theory. Cohen et al. (2019) further obtained a tight guarantee on the `2-normed robustness using Gaussian noise. A remaining issue in all of these works is that they did not give answers to questions like why Gaussian noise is used to certify the `2-normed robustness and what is the best mechanism to certify the `∞-normed robustness. To answer these questions, we present in this paper a new general framework to study randomized smoothing based certified defenses.

heading: 3 ROBUSTNESS MOTIVATED BY DIFFERENTIAL PRIVACY
text: In this section, we introduce our framework. Let x be a data sample and y ∈ Y be its label, where Y is the label set. We denote by f(·) a deterministic classifier with prediction f(x) for any data sample x. If there exists an x′ in a small lp ball centered at x and with f(x′) 6= f(x), x′ is viewed as an adversarial sample.
Definition 1 (Randomized Classifier (Cohen et al., 2019)). Given an input x, the prediction of a randomized classifier g(·) is defined as
argmax c∈Y P (g(x) = c).
Specifically, for a randomized smoothing classifier g(x) = f(x + Z), where Z is a random vector and f(·) is a deterministic classifier, the prediction of x is the class of c whose region S , {x̃ ∈ Rd, f(x̃) = c} has the largest probability measure in the distribution of x+ Z (x̃ ∼ p(x+ Z)).
Before introducing our framework, we first recall the definition of robustness for a deterministic classifier in (Diochnos et al., 2018). Definition 2 (Robustness (Diochnos et al., 2018)). For a given classifier f , a sample x and some norm ‖ · ‖. f is (r, ‖ · ‖)-(error-region) robust on the sample x if
∀x′ ∈ B(x, r), f(x) = f(x′), (1)
where B(x, r) is the ball centered at x and with norm ‖ · ‖ and radius r.
Note that in Definition 2, the classifier is assumed to be deterministic. To generalize the concept of robustness to randomized classifiers (see Definition 1), we define a relaxed version of the (errorregion) robustness. Since g(x) is a random value, instead of using equality, we measure the difference between g(x) and g(x′) by a certain divergence. This leads us to the following definition, which is a basic concept in our framework that will be used throughout the paper. Definition 3 (Relaxed Robustness). For a given (randomized) classifier g(·), a sample x and some norm ‖ · ‖, the classifier g is (r,D, ‖ · ‖, )-(error-region) robust on x if
∀x′ ∈ B(x, r),max{D(g(x), g(x′)), D(g(x′), g(x))} ≤ . (2)
where D is some divergence metric between two probability distributions. The max function is used to ensure that the measurement is symmetric.
Compared with Definition 2, there are two additional terms in Definition 3: represents the “distance” or difference between the distributions of g(x) and g(x′). When is small, we expect that the distributions of predictions on x and x′, i.e., g(x) and g(x′), are almost the same, which is just a generalization of the equality in Definition 2. D is some divergence measurement between two probability distributions. In this paper, we use two types of divergence, ∞-Divergence and Maximal Relative Rényi Divergence, to measure the distance between two probability distributions. Correspondingly, we have two types of robustness called D∞ and DMR robustness. Definition 4 (∞-Divergence). The∞-Divergence D∞ of distributions P and Q is defined as
D∞(P‖Q) = sup x∈supp(Q)
log P (x)
Q(x) ,
where supp(Q) is the support of the distribution Q. Definition 5 (Maximal Relative Rényi Divergence). The Maximal Relative Rényi Divergence DMR(P‖Q) of distributions P and Q is defined as
DMR(P‖Q) = max α∈(1,∞) Dα(P‖Q) α ,
where Dα(P‖Q) is the Rényi divergence between P and Q, which is defined as
Dα(P‖Q) = 1
α− 1 logEx∼Q(
P (x) Q(x) )α.
Definition 6 (D∞ Robustness). A randomized smoothing mechanism A(·) (including classifiers) is a (r,D∞, ‖ · ‖, )-robust mechanism if
∀x′ ∈ B(x, r),max{D∞(A(x),A(x′)), D(A(x′),A(x))} ≤ , (3)
where ‖ · ‖ is the norm of the ball B(x, r). If a randomized smoothing classifier g(·) satisfies Eq. (3), it is a (r,D∞, ‖ · ‖, )-robust classifier or it certifies D∞ Robustness.
D∞ Robustness is motivated by the notion of -differential privacy ( -DP) (Dwork et al., 2006). To achieve -DP for a randomized algorithm, we can use several mechanisms such as Laplacian mechanism or Exponential mechanism (see (Dwork et al., 2014) for details). However, it is known that adding Gaussian noise often does not lead to -DP, but rather ( , δ)-DP (Dwork et al., 2014) which has an additional parameter δ and thus is harder to be incorporated in our framework. To alleivate this issue, we employ Maximal Relative Rényi Divergence as the the probability distance measurement to define another type of robustness, namely DMR robustness. Definition 7 (DMR Robustness). A randomized smoothing mechanism A(·) is a (r,DMR, ‖ · ‖, )- robust mechanism if
∀x′ ∈ B(x, r),max{DMR(A(x),A(x′)), DMR(A(x′),A(x))} ≤ . (4) If a randomized smoothing classifier g(·) satisfies Eq. (4), it is a (r,DMR, ‖ · ‖, )-robust classifier or it certifies DMR Robustness.
DMR Robustness is inspired by the notion of zero-Concentrated Differential Privacy (zCDP) (Bun & Steinke, 2016), whose connection to DP is shown in the following theorem. Theorem 8 ((Bun & Steinke, 2016)). Let P and Q be two probability distributions satisfying the conditions of D∞(P‖Q) ≤ and D∞(Q‖P ) ≤ . Then, DMR(P‖Q) ≤ 12 2.
Theorem 8 indicates that DMR-robustness is a relaxed version of D∞-robustness. Remark (Connections between D∞ & DMR Robustness and Standard Definitions). Although D∞ & DMR Robustness are seemingly new concepts defined in this paper, they actually have several connections with the existing frameworks Lecuyer et al. (2018) and Cohen et al. (2019). Specifically, as long as D∞ robustness is certified, the expected output stability bound in Lecuyer et al. (2018) will be guaranteed with δ′ = 0. And if DMR robustness is certified, the expected output stability bound in Lecuyer et al. (2018) will be guaranteed with ′ = (c + 1) √ and δ′ = exp(− c 2
4 ), according to Theorem 10. Besides, the “scale” of the robust radius certified by our framework is similar the “scale” of the robust radius in Cohen et al. (2019), according to Corollary 11. Theorem 9 (Postprocessing Property). Let g(x) = f(A(x)) be a randomized classifier, where f(·) is any deterministic function (classifier). g(·) is (r,D, ‖ · ‖, )-robust if A(·) is (r,D, ‖ · ‖, )-robust (where D includes D∞ and DMR).
The above theorem is derived from the post-processing properties of DP and zCDP. A detailed proof (explanation) is given in Appendix B. This property allows us to concentrate only on the randomized smoothing mechanism A without needing to consider the specific form of the deterministic function (classifier) f(·). Next, we consider the cases of certifying D∞ or DMR robustness using `2 and `∞-norm.
3.1 CERTIFYING `2-NORMED ROBUSTNESS
The following theorem shows that randomized smoothing by the Gaussian mechanism is (r,DMR, ‖ · ‖, )-robust. Theorem 10. Let f be any classifier and g(x) = f(x+z) be its corresponding randomized classifier for samples x ∈ Rd, where z ∼ N (0, σ2Id). Then, g(·) is (r,DMR, ‖ · ‖2, r 2
2σ2 )-robust on any x. Moreover, let denote r 2
2σ2 . Then, for any λ > 0 and any measurable set S 6= ∅, the following holds with probability at least 1− exp(−λ 2
4 ),
log P (g(x) ∈ S) P (g(x′) ∈ S) ≤ λ+ √ . (5)
That is, when λ = c √ , log P (g(x)∈S)P (g(x′)∈S) ≤ (c + 1) √ with probability 1 − exp(− c 2
4 ). In practice, c = 3 is enough to achieve a high probability. Corollary 11. Adding Gaussian noise z ∈ N (0, σ2Id) can defend any x′ ∈ B(x, r = √
2 σ) that satisfies the condition of DMR(g(x)‖g(x′)) ≤ with probability at least 1 − exp(− c 2
4 ). Furthermore, √ can be calculated (bounded) by (log pa − log pb)/2(1 + c) or (log pa/(1− pa))/2(1 + c) (binary case), where pa and pb are respectively the probabilities of the randomized classifier g(·) returning the most probable class ca and the runner-up class cb on input x.
Detailed proofs for Theorem 10, Corollary 11, and all the following theorems are provided in Appendix B. From Theorem 9, we can see that for classifiers like g(x) = f(x + z), we only need to prove that the randomized mechanism A(x) = x+ z(z ∼ N (0, σ2Id)) is (r,DMR, ‖ · ‖2, r 2
2σ2 )- robust. Also, the connection between and pa, pb can be derived for all or √ (in the certified radii) as in Corollary 11. Note that a similar theorem has also been proved by Cohen et al. (2019). But there are some major differences between our framework and theirs (Cohen et al., 2019). Specifically, our framework certifies the robustness with a probability of failure, and the certified radius r depends on c that controls the probability of failure. A smaller c yields a larger r compared to those in Cohen et al. (2019), and vice versa. Moreover, in our framework, we show that the Gaussian mechanism is a near optimal option, by providing a lower bound below for all possible noises that can certify the `2-normed DMR robustness.
Next, we consider the following unanswered question (i.e., the first question). Since there are infinite ways of sampling z, a natural problem is to determine whether Gaussian mechanism is the optimal option to certify the `2-normed DMR robustness. To answer this question, we first give a lower bound on the magnitude of the noise z added in the randomized smoothing mechanismA(x) = x+z to ensure that A(x), as well as f(A(x)), is (r,DMR, ‖ · ‖2, )-robust. If the magnitude of Gaussian noise is close to the lower bound, then Gaussian mechanism is considered as “near optimal”.
Theorem 12 (Lower Bound of the Noise). For any ≤ O(1), if there is a (2r,DMR, ‖ · ‖2, 2 )- robust randomized smoothing mechanism A(x) = x + z : [0, r√
d ]d 7→ [0, r√ d ]d such that for all
x ∈ [0, r√ d ]d, E[‖z‖∞] = EA‖A(x)− x‖∞ ≤ α, for some α ≤ O(1), then it must be true that α ≥ Ω( r√ ). In another word, Ω( r√ ) is the lower
bound of the expected `∞ norm of the random noise.
Theorem 12 indicates that the expected `∞ norm of the added random noise should be at least Ω( r√ ) to guarantee (r,DMR, ‖ ·‖2, )-robustness. For Gaussian mechanism, the expected `∞ norm is O(σ √ log d) ((Orabona & Pál, 2015)), which is O( r√ √ log d) according to Corollary 11. This means that Gaussian mechanism is near optimal (i.e., up to an O( √
log d) factor) here. Equivalently, if we fix the magnitude of the expected `∞-norm of the added noise as α, the largest radius r that can be certified by any (r,DMR, ‖ · ‖2, )-robust randomized smoothing mechanisms is upper bounded by O(α √ ), which is also close to the robust radius guaranteed by Gaussian mechanism (up to an O( √ log d) factor).

heading: 3.2 CERTIFYING `∞-NORMED ROBUSTNESS
text: Previous work on the randomized smoothing-based certified defenses (Cohen et al., 2019; Li et al., 2018) mainly uses Gaussian noise to certify the `2-normed robustness. Thus, another natural question (i.e., the second question) is to determine whether randomized smoothing can use some mechanism to certify the `∞-normed robustness. In this section, we consider this question using our general framework.
Before extending our result to the `∞-normed case, we first recall the `2-normed case and investigate the form of the density function of Gaussian noise: p(z) ∝ exp(−‖z‖ 2 2
σ2 ). Based on this, we conjecture that, to certify `∞-normed robustness, we can sample the noise using an exponential mechanism:
p(z) ∝ exp (−‖z‖∞ σ ). (6)
We show in the following theorem that randomized smoothing by (6) certifies (r,DMR, ‖ · ‖∞, ·)- robustness, which could be considered as an extension of the `2-normed case. Moreover, we can prove that it is (r,D∞, ‖ · ‖∞, ·)-robust. However, the certified radius r is O(1/d), which implies that it is unscalable to high-dimensional data.
Theorem 13. Let f be any classifier and g(x) = f(x+z) be its corresponding randomized classifier for sample x ∈ Rd, where the noise z ∼ p(z) in (6). Then, g(·) is (r,DMR, ‖ · ‖∞, r 2
2σ2 )-robust. Moreover, it is (r,D∞, ‖ · ‖∞, rσ )-robust.
Remark 14. Due to the high dimensionality of samples in real world applications, directly sampling z ∼ p(z) by the Markov Chain Monte Carlo (MCMC) algorithm requires a large number of randomwalks that can incur high computational cost. To alleviate this issue, we adopt an efficient sampling method from (Steinke & Ullman, 2015) that first samplesR fromGamma(d+1, σ) and then samples z from [−R,R]d uniformly. The complexity of this sampling algorithm is only O(d).
Comparing Theorems 10 and 13, we can see that randomized smoothing via (6) can certify a region that has (almost) the same radius as that of Gaussian distribution in the `2-normed case, due to similarity in their density functions and the robustness guarantees. In the following theorem we show that the magnitude of the noise added by (6) is much larger than that of Gaussian distribution in the `2-normed case. Theorem 15. For the distribution that can guarantee Theorem 13, the following theorem holds
Ez[‖z‖∞] = dσ. (7)
Note that compared with the Gaussian noise added in Theorem 10 which satisfies the condition of Ez[‖z‖∞] = O(σ √ log d), the expected `∞-norm of the distribution in (6) is proportional to the dimensionality d of the data, which is quite large. This means that for any image data, at least one pixel will be perturbed by the magnitude of dσ, which will completely ruin the accuracy of the classification network. However, if we want the noise to have a magnitude of O(1), σ needs to be O(1/d), and so does the robust radius.
Theorem 15 is a somewhat negative result for randomized smoothing using distribution (6) to certify the `∞-normed robustness. Thus, an immediate question is whether exponential mechanism is the right choice to certify the `∞-normed robustness. The following theorem shows that for any (r,D∞, ‖ · ‖∞, rσ )-robust randomized smoothing mechanism, the expected `∞-norm of the added noise is lower bounded by Ω(dσ). Thus, combining the following theorem with Theorem 15, we can conclude that the exponential mechanism is actually an optimal choice to certify D∞ robustness. Theorem 16. For any (2r,D∞, ‖ · ‖∞, 2 )-robust mechanismA(x) = x+ z : [0, r]
d 7→ [0, r]d such that E[‖z‖∞] = EA‖A(x)− x‖∞ ≤ α,∀x ∈ [0, r]d, it must be true that α ≥ Ω( rd ).
From Theorem 16 we can see that, for any (·, D∞, ‖ · ‖∞, 2 )-robust randomized smoothing mechanism, if we fix the expectation of the `∞-norm of the added noise in the exponential mechanism as α, the largest `∞ radius that can be certified is upper bounded by O(α /d). Compared with the `2-normed case in Theorem 11, we can see that there is an additional factor ofO(1/d), which makes it unscalable to high-dimensional data. Equivalently, if we want the same radius to be certified as in the Theorem 10, the expected `∞-norm of the added noise needs to be at least Ω( rd ), which will be too large for any image data.
The less than ideal lower bound in Theorem 16 is for D∞-robustness. Since DMR-robustness is more relaxed than D∞-robustness, a natural question is thus to determine whether the lower bound can be improved by switching toDMR-robustness. Unfortunately, the following theorem shows that a similar phenomenon still holds for DMR-robustness. Theorem 17. For any (2r,DMR, ‖ · ‖∞, 2 )-robust mechanism A(x) = x + z : [0, r]
d 7→ [0, r]d such that
E[‖z‖∞] = EA‖A(x)− x‖∞ ≤ α,∀x ∈ [0, r]d,
it must be true that α ≥ Ω( r √ d√ ).
From Theorems 17 and 15 we can see that in the definition of (2r,DMR, ‖ · ‖∞)-robustness, adding noise according to (6) is not near optimal. The following theorem shows that in this case, Gaussian mechanism is actually a near optimal choice.
Theorem 18. Let r, > 0 be some fixed number and A(x) = x + z with z ∼ N (0, dr 2
2 ). Then, A(·) is (r,DMR, ‖ · ‖∞, )-robust. E[‖z‖∞] = EA‖A(x)−x‖∞ is upper bounded by O( r √ d log d√ ).
From Theorem 17 and 18, we can conclude that for all randomized smoothing mechanisms that are (·, 0, DMR, ‖ · ‖∞, 2 )-robust, if the expected `∞-norm of the added noise is fixed to be α, the
largest radius that can be certified is upper bounded by O( √ α√ d
), and the largest radius that can be certified by Gaussian mechanism is O(1/ √ d log d) (and σ is Ω( α√
log d )). If α and are both set
to be O(1), the largest radius that can be certified using Gaussian mechanism to achieve DMRrobustness is greater than the largest radius that can be certified to achieve D∞-robustness by at least a factor of O( √ d/ log d). This is reasonable since the definition of DMR-robustness is more relaxed. Obviously, there is some trade-off between the rigorousness of the notion of robustness and the largest certified robust radius, i.e., when the robustness is relaxed, the largest certified radius increases. We will investigate this trade-off more in the future research.

heading: 4 EXPERIMENTS

heading: 4.1 DATASETS AND MODELS
text: The performance of our framework is verified on two widely-used datasets, i.e., CIFAR10 and ImageNet∗. Following Cohen et al. (2019), we use a 110-layer residual network and the classical ResNet-50 as the base models for CIFAR10 and ImageNet respectively. Note that it may be difficult for the models to classify noisy images without seeing any noisy samples in the training stage. Thus, we train all the models by adding appropriate Gaussian noise on the training images. The certified accuracy for radius R is defined as the fraction of the test set whose certified radii are larger than R †. The value of in all our derived certified radii can be calculated by pa (or pa and pb) as shown in the proof of Corollary 11. It is also worth noting that we do not compare our results with (Cohen et al., 2019) in the experiments because our framework and (Cohen et al., 2019) endow robustness with different definitions. Moreover, our work does not aim at improving the tightness of the guarantee on the `2-normed robustness but aims at presenting a general and self-contained framework to study some remaining issues, such as the optimality of the Gaussian mechanism, and the specific mechanisms to certify the `∞-normed robustness.

heading: 4.2 EMPIRICAL RESULTS
text: Certifying the `2-normed Robustness To certify the `2-normed Robustness, as we explained in previous section, Gaussian mechanism is a near optimal option. Thus, we mainly evaluate the performance of Gaussian mechanism in our framework. We first fix the value of σ in Gaussian mechanism and show the certified accuracy of the classifiers trained by varied Gaussian noises in Figure 1. As shown in Figure 1, using σ = 0.50 Gaussian noise to train the classifier is a good setting here. So in Figure 2, we evaluate the Gaussian mechanism with different σ values on the classifier trained by σ = 0.50 Gaussian noise. Overall, on CIFAR-10, our framework can certify approximately 20% accuracy under `2 = 1.0 perturbation‡. We also show the results on ImageNet by Figures 4 and 5 in Appendix C.
∗Pixel value range is [0.0, 1.0] †For more details, please refer to (Cohen et al., 2019) ‡On CIFAR-10, `2 = 1.0 perturbation allows 4/255 perturbation on every pixel
Certifying the `∞-normed Robustness To certify the `∞-normed robustness, we evaluate the performance of the Exponential mechanism in the definition of D∞-robustness and the Gaussian mechanism in the definition of DMR-robustness. As shown in Figure 3, the `∞ radii that can be certified by Gaussian mechanism are about 10 ∼ 20 times (i.e., O( √ d/ log d) with d = 3072 as shown in our theories) larger than the `∞ radii certified by the exponential mechanism. On ImageNet, as shown in Figure 6 in Appendix C, the robust radii are less than 1/255 (due to scaling in O(1/d) or O(1/ √ d log d)), indicating that certifying the `∞-normed robustness by randomized smoothing may not be applicable to high-dimensional data.

heading: 5 CONCLUSION
text: In this paper, we present a general framework for certifying two types of robustness (D∞ andDMRrobustness) in the `2 and `∞ norms by randomized smoothing. Under our framework, we first give the answers to the remaining questions in the previous studies on randomized smoothing-based certifiable defenses, i.e., the optimality of Gaussian mechanism and the possibility to certify the `∞-normed robustness. Specifically, we demonstrate that (i) Gaussian mechanism is a near optimal option to certify DMR-robustness in `2 norm by giving a lower bound on all DMR-robust mechanisms, with certified radii scaling in O(1); (ii) an exponential mechanism is the optimal choice for certifying D∞-robustness in `∞ norm, with certified radii scaling in O(1/d); (iii) Gaussian mechanism is a near optimal option to certify DMR-robustness in `∞ norm, with certified radii scaling in O(1/ √ d log d); (iv) the largest `∞ radius that can be certified by randomized smoothing in our
framework is upper bounded by O(1/ √ d), indicating that randomized smoothing may not be scalable to high-dimensional data in terms of certifying the `∞-normed robustness.

heading: A DIFFERENTIAL PRIVACY BACKGROUND
text: In this section, we briefly introduce the concepts of differential privacy used in this paper. Definition 19 (Differential Privacy (DP) (Dwork et al., 2006)). Given a data universe X , we say that two datasets D,D′ ⊆ X are neighbors if they differ by only one entry, which is denoted by D ∼ D′. A randomized algorithm A is -differentially private (DP) if for all neighboring datasets D,D′ the following holds
D∞(A(D)‖A(D′)) ≤ .
Intuitively, DP ensures that an adversary cannot infer whether or not a participant (data sample) is participating in dataset D due to the fact that the distribution of A(D) is almost the same as that of A(D′), which means that DP-mechanisms are robust to 1-sample change. Now consider the case where D is some 1-size dataset (i.e., one data sample). Then, DP ensures that the distribution of A(D) and A(D′) are almost the same, where D′ is just any other data sample. Inspired by notion of DP, we define D∞ robustness in Definition 6. Definition 20 (Zero-Concentrated Differential Privacy (zCDP)). A randomized mechanism A is called -zCDP, if for all D ∼ D′
max{DMR(A(D)‖A(D′)), DMR(A(D′)‖A(D))} ≤ . (8)
zCDP is a relaxed version of DP according to Theorem 8. Motivated by zCDP, we define DMR robustness in Definition 7.

heading: B OMITTED PROOFS
text: Proof of Theorem 9. This theorem can be easily proved by the following lemma,
Lemma 21 ((Bun & Steinke, 2016)). Let P and Q be two distributions on Ω and let f : Ω 7→ Θ be a deterministic function. Let f(P ) and f(Q) denote the distributions on Θ induced by applying f to P and Q respectively. Then we have
Dα(f(P )‖f(Q)) ≤ Dα(P‖Q).
Similar post-processing property also holds when α = ∞ (Dwork et al., 2006). Therefore, if A(·) satisfies Definition 6 or 7, then f(A(·)) will satisfy Definition 6 or 7 for any deterministic function (classifier) f(·).
Proof of Theorem 10. By Theorem 9, we only need to show that the randomized smoothing mechanism A(x) = x+ z is (r,DMR, ‖ · ‖2)-robust, which can be proved by the following lemma. Lemma 22 ((Bun & Steinke, 2016)). Let x, x′ ∈ Rd, and α ∈ [1,∞). Then
Dα(N (x, σ2Id)‖N (x′, σ2Id)) = α‖x− x′‖22
2σ2 .
Thus for all x′ ∈ B(x, r), we have DMR(A(x)‖A(x′)) ≤ r 2
2σ2 .
Next we prove (5). To prove this inequality, we first define the loss random variable.
Definition 23 ((Bun & Steinke, 2016)). Let Y and Y ′ be random variables on Ω. We define the loss random variable between Y and Y ′, denoted by Z = Loss(Y ‖Y ′), as follows: Define a function F : Ω 7→ R by F (y) = log P[Y=y]P[Y ′=y] . Then Z is distributed according to F (Y ).
By this we can write Z = Loss(g(x)‖g(x′)) and rewrite DMR(g(x)‖g(x′)) as
∀α ∈ (1,∞],E[e(α−1)Z ] ≤ e(α−1) r2 2σ2 α.
This implies that Z is sub-Gaussian. By using the tail-bound of sub-Gaussian (Vershynin, 2018), we have
P[Z > λ+ ] ≤ exp(−λ 2
4 ), (9)
where r 2
2σ2 = .
Proof of Corollary 11. Since we fix = r 2 2σ2 , the certified radius is r = √
2 σ. Now we prove the upper bound of √ for a classifier g(·). Given Theorem 10, we should have
log P (g(x) = ca)
P (g(x′) = ca) ≤ (c+ 1)
√ ,
and
log P (g(x′) = cb)
P (g(x) = cb) ≤ (c+ 1)
√ ,
since x is also in B(x′, r). Then we have log P (g(x ′)=ca)
P (g(x′)=cb) ≥ log P (g(x)=ca)P (g(x)=cb) −2(c+1)
√ . According
to Definition 1, as long as log P (g(x ′)=ca)
P (g(x′)=cb) > 0, g(·) can correctly classify x′. Thus, as long as
log P (g(x)=ca)P (g(x)=cb) −2(c+1) √ > 0 (i.e., √ < (log pa− log pb)/2(1+c)), g(·) classifies x′ as ca.
Proof of Theorem 12. Let {x1, x2, · · · , x2d} = {0, r√d} d. For each xi, we use the same adversarial example x′ = 0 to derive the lower bound. Since A is (2r,DMR, ‖ · ‖2, 2 )-robust, we have for all xi, xj , i, j ∈ [2d],
max{DMR(A(xi)‖A(xj)), DMR(A(xj)‖A(xi))} ≤ 2 ·
2 = .
That is A is -zCDP on the dataset X = {0, r√ d }d. Next we will prove the lower bound for all
-zCDP mechanisms.
We first consider the case where r = √ d, and then generalize it to any r. Before that we will first prove the lower bound of one-way marginal (i.e., mean estimation) under -zCDP. For an n-size dataset X ∈ Rn×d, the one-way marginal is just h(D) = 1n ∑n i=1Xi, where Xi is the i-th row of X . Specifically, when n = 1, one-way marginal is just the data point itself. We show the following theorem,
Theorem 24. If there exists an -zCDP mechanism A : {0, 1}d 7→ [0, 1]d such that for all x ∈ {0, 1}d
E‖A(x)− x‖∞ ≤ α, (10) then 1 ≥ Ω( √
d α2 ).
Proof of Theorem 24. To prove this theorem, our idea is to first use the connection between -zCDP and ( , δ)-DP.
Lemma 25 (Prop.1.3 in Bun & Steinke (2016)). If A is -zCDP, then it is ( + 2 √ log 1δ , δ)differentially private.
Bun et al. (2018) first give the optimal rate of one-way marginal estimation which is improved by Steinke & Ullman (2016).
Lemma 26 (Theorem 1.1 in Steinke & Ullman (2016)). For every ≤ O(1), every 2−Ω(n) ≤ δ ≤ 1 n1+Ω(1) and every α ≤ 110 , if A : ({0, 1}
d)n 7→ [0, 1]d is ( , δ)-DP and E[‖A(D)− h(D)‖∞] ≤ α, then
n ≥ Ω(
√ d log 1δ
α ). (11)
Setting n = 1, = + 2 √ log 1δ in Lemma 26, we can see that if E[‖A(x) − x‖∞] ≤ α then 1 ≥ Ω( √ d log 1δ
( +2 √ log 1δ )α ) ≥ Ω( √ d√ α2
), where the last inequality is due to the fact that √ log 1δ
+2 √ log 1δ ≥
Ω( 1√ ).
Now we come back to the proof for any r. If A : {0, r√ d }d 7→ [0, r√ d ]d is -zCDP, where EA‖A(xi) − xi‖∞ ≤ α, then we have EA‖ √ d r A(xi) − √ d r xi‖∞ ≤ √ d r α. Thus, √ d r A is an - zCDP mechanism on {0, 1}d 7→ [0, 1]d. By Theorem 24 with α = √ d r α ≤ O(1), we have
1 ≥ Ω( r√ α2 ), i.e., α ≥ Ω( r√ ). (12)
Proof of Theorem 13. We will first prove that A(x) = x + Z is (r,D∞, ‖ · ‖∞, rσ )-robust. Then by Theorems 8 and 9, we can easily show that g(·) is (r,DMR, ‖ · ‖∞, r 2
2σ2 )-robust. Consider x, x′, ‖x′ − x‖∞ ≤ r. Then, for any y we have
p(y − x) p(y − x′) = exp(−‖y−x‖∞σ ) exp(−‖y−x
′‖∞ σ )
≤ exp(‖y − x ′‖∞ − ‖y − x‖∞ σ ) ≤ exp(‖x ′ − x‖∞ σ ) ≤ exp( r σ ).
Thus, for any subset S we have
log A(x) ∈ S A(x′) ∈ S = log
∫ S p(z−x)d z∫
S p(z−x′)d z
≤ r σ .
Proof of Theorem 15. Define the distribution D on [0,∞) to be Z ∼ D, meaning Z = ‖z‖∞ for z ∼ p(z), where p(z) is in (6). The probability density function of D is given by
pD(z) ∝ zd−1 exp(− z
σ ),
which is obtained by integrating the probability density function (6) over the infinity ball of radius z with surface area d2dzd−1 ∝ zd−1. pD is the Gamma distribution with shape d and mean σ, and thus E[z] = dσ.
Proof of Theorem 16. Let X = {x1, x2, · · · , x2d} = {0, r}d be the set of samples. Since A is (2r, ‖ · · · ‖∞)-robust and ‖xi − xj‖∞ ≤ 2r, we know that
max{D∞(A(xi)‖A(xj)), D∞(A(xj)‖A(xi))} ≤ .
Thus, A : Rd 7→ Rd is -DP on X . Similar to the proof for Theorem 12, we can reduce our problem to studying the lower bound of one-way marginal for 1-size data problem in the -DP model. Now we first consider the case of r = 1. We have the following lemma which is given by Hardt & Talwar (2010).
Lemma 27 (Theorem 1.1 in (Hardt & Talwar, 2010)). If there exists an -DP mechanism A : {0, 1}d 7→ [0, 1]d satisfying the following inequality for all x ∈ {0, 1}d
E‖A(x)− x‖∞ ≤ α, (13)
then 1 ≥ Ω( d α ).
Now we consider any -DP mechanism A : {0, r}d 7→ [0, r]d. If
E[‖A(x)− x‖∞] ≤ α,
then E[‖ 1rA(x)− 1 rx‖∞] ≤ α r . That is, 1 rA(x) : {0, 1} d 7→ [0, 1]d. Thus, by lemma 26 we can see that 1 ≥ Ω( dr α ).
Proof of Theorem 17. The proof is almost the same as that of Theorem 12. Assume that we have a set of data points X = {x1,x2 · · · , x2d} = {0, r}d. A will also be -zCDP on X as in the proof of Theorem 12. Thus, if
E[‖A(x)− x‖∞] ≤ α,
then E[‖1
r A(x)− 1 r x‖∞] ≤ 1 r α.
This means that 1rA(x) : {0, 1} d 7→ [0, 1]d is -zCDP. Thus, by Theorem 24 we must have 1 ≥ Ω( √ dr2
α2 ).
Proof of Theorem 18. The proof is almost the same as that of Theorem 10. By Lemma 22, we have
Dα(N (x, dr2 2 )‖N (x′, dr 2 2 )) = α ‖x− x′‖22 dr2 ≤ αd ‖x− x ′‖2∞ dr2 ≤ α .
Therefore,A(x) = x+ z with z ∼ N (0, dr 2
2 ) is (r,DMR, ‖ · ‖∞, )-robust. The bound of E[‖z‖∞]
can be easily proved by substituting σ in O(σ √ log d) ((Orabona & Pál, 2015)) with √ dr2
2 .

heading: C MORE EXPERIMENTAL RESULTS (IMAGENET)
text: C.1 CERTIFYING `2 ROBUSTNESS
C.2 CERTIFYING `∞ ROBUSTNESS

Review summaries:
This work examines the recently proposed randomized smoothing method for certifying the robustness of neural networks. The authors explain a theoretical framework for analyzing randomized smoothing as a certification method, propose two alternative definitions of robustness (D_MR and D_inf), and prove that using Gaussian noise for smoothing is near “optimal” for L2 robustness, while using exponential noise for smoothing is optimal for L_inf robustness (the authors do this by establishing a lower bound on the noise necessary for smoothing to work). This also leads the authors to the interesting conclusion that randomized smoothing may not be scalable to high dimensional data for L_inf robustness.

The authors propose a new definition for robustness of random functions. This definition is ideal for analyzing the certified robustness under randomized smoothing techniques. They analyze and show that the Gaussian smoothing is near optimal for \ell_2 smoothing as the mean maximum error is only off by a factor of log d where d is the dimension from the optimal mean maximum energy. This is the case even under a more strict definition of robustness defined as D_\infty. Moreover, the authors show that indeed smoothing with an exponential family  is optimal under D_\infty robustness metric with radius measured in \ell_\infty.