Title: A UNIFIED FRAMEWORK FOR RANDOMIZED SMOOTHING BASED CERTIFIED DEFENSES

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.

1. INTRODUCTION:

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

Mechanism 2 -normed ∞ -normed D ∞ Robustness D M R Robustness D ∞ Robustness D M R Robustness

Gaussian unable to certify near optimal unable to certify near optimal r scales in O(1) r scales in O(1/ √ d log d)

Exponential not optimal not optimal optimal not optimal r scales in O(1/d) Table 1 : Summary of our framework -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 Rényi (MR) divergence as the probability distance measurement and is called D M R 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 certifying D ∞ and/or D M R 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 D M R 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 certifying

D M R ro- bustness in ∞ norm, but the robust radius is O(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

D M R 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.

2. RELATED WORK:

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.

3. ROBUSTNESS MOTIVATED BY DIFFERENTIAL PRIVACY:

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 l p ball centered at x and with f (x ) = 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 ∈ R d , 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

EQUATION

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

EQUATION

)

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 Rényi Divergence, to measure the distance between two probability distributions. Correspondingly, we have two types of robustness called D ∞ and D M R 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 Rényi Divergence). The Maximal Relative Rényi Divergence D M R (P Q) of distributions P and Q is defined as

D M R (P Q) = max α∈(1,∞) D α (P Q) α ,

where D α (P Q) is the Rényi divergence between P and Q, which is defined as

EQUATION

)

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 Rényi Divergence as the the probability distance measurement to define another type of robustness, namely D M R robustness.

EQUATION

)

If a randomized smoothing classifier g(•) satisfies Eq. ( 4), it is a (r,

D M R , • , )-robust classifier or it certifies D M R Robustness.

D M R 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, D M R (P Q) ≤ 1 2 2 . Theorem 8 indicates that D M R -robustness is a relaxed version of D ∞ -robustness. Remark (Connections between D ∞ & D M R Robustness and Standard Definitions). Although D ∞ & D M R

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 D M R 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 D M R ).

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 D M R robustness using 2 and ∞ -norm.

3.1. CERTIFYING 2 -NORMED ROBUSTNESS:

The following theorem shows that randomized smoothing by the Gaussian mechanism is (r, D M R , • , )-robust. Theorem 10. Let f be any classifier and g(x) = f (x+z) be its corresponding randomized classifier for samples x ∈ R d , where z ∼ N (0,

σ 2 I d ). Then, g(•) is (r, D M R , • 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 = ∅, the following holds with probability at least 1 -exp(-

EQUATION

)

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, 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(

σ 2 I d ) can defend any x ∈ B(x, r = √ 2 σ) that satisfies the condition of D M R (g(x) g(x )) ≤ with probability at least 1 -exp(-c 2 4 ).

x) = x + z(z ∼ N (0, σ 2 I d )) is (r, D M R , • 2 , r 2

2σ 2 )robust. Also, the connection between and p a , p b 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 D M R 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 D M R robustness. To answer this question, we first give a lower bound on the magnitude of the noise z added in the randomized smoothing mechanism A(x) = x+z to ensure that A(x), as well as

f (A(x)), is (r, D M R , • 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 1), then it must be true that α ≥ Ω( r √ ). In another word, Ω( r √ ) is the lower bound of the expected ∞ norm of the random noise.

≤ O(1), if there is a (2r, D M R , • 2 , 2 )- robust randomized smoothing mechanism A(x) = x + z : [0, r √ d ] d → [0, r √ d ] d such that for all x ∈ [0, r √ d ] d , E[ z ∞ ] = E A A(x) -x ∞ ≤ α, for some α ≤ O(

Theorem 12 indicates that the expected ∞ norm of the added random noise should be at least 

EQUATION

3.2. CERTIFYING ∞ -NORMED ROBUSTNESS:

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:

EQUATION

We show in the following theorem that randomized smoothing by ( 6) certifies (r, D M R , • ∞ , •)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 ∈ R d , where the noise z ∼ p(z) in ( 6). Then,

g(•) is (r, D M R , • ∞ , 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 samples R from Gamma(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

EQUATION

Note that compared with the Gaussian noise added in Theorem 10 which satisfies the condition of

E z [ 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 mechanism A(x) = x + z : [0, r] d → [0, r] d such that E[ z ∞ ] = E A 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 of O(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 D M R -robustness is more relaxed than D ∞ -robustness, a natural question is thus to determine whether the lower bound can be improved by switching to D M R -robustness. Unfortunately, the following theorem shows that a similar phenomenon still holds for D M R -robustness. Theorem 17. For any (2r,

D M R , • ∞ , 2 )-robust mechanism A(x) = x + z : [0, r] d → [0, r] d such that E[ z ∞ ] = E A 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, D M R , • ∞ )-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, D M R , • ∞ , )-robust. E[ z ∞ ] = E A 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, D M R , • ∞ , 2 )-robust, if the expected ∞ -norm of the added noise is fixed to be α, the 1), the largest radius that can be certified using Gaussian mechanism to achieve D M Rrobustness 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 D M R -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.

4. EXPERIMENTS:



4.1. DATASETS AND MODELS:

The performance of our framework is verified on two widely-used datasets, i.e., CIFAR10 and Im-ageNet * . 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 p a (or p a and p b ) 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.

4.2. EMPIRICAL RESULTS:

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 

5. CONCLUSION:

In this paper, we present a general framework for certifying two types of robustness (D ∞ and D M Rrobustness) 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 D M R -robustness in 2 norm by giving a lower bound on all D M R -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 D M R -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.

A DIFFERENTIAL PRIVACY BACKGROUND:

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 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, D M R , • 2 )-robust, which can be proved by the following lemma.

Lemma 22

((Bun & Steinke, 2016)). Let x, x ∈ R d , and α ∈ [1, ∞). Then D α (N (x, σ 2 I d ) N (x , σ 2 I d )) = α x -x 2 2 2σ 2 .

Thus for all x ∈ B(x, r), we have

D M R (A(x) A(x )) ≤ r 2 2σ 2 .

Next we prove (5). To prove this inequality, we first define the loss random variable. By this we can write Z = Loss(g(x) g(x )) and rewrite D M R (g(x) g(x )) as ∀α ∈ (1, ∞], E[e (α-1)Z ] ≤ e (α-1) r 2 2σ 2 α . This implies that Z is sub-Gaussian. By using the tail-bound of sub-Gaussian (Vershynin, 2018) , we have

EQUATION

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

EQUATION

log P (g(x ) = c b ) P (g(x) = c b ) ≤ (c + 1) √ ,

since x is also in B(x , r). Then we have log P (g(x )=ca) P (g(x )=c b ) ≥ log P (g(x)=ca) P (g(x)=c b ) -2(c + 1)

√:

. According

to Definition 1, as long as log P (g(x )=ca) P (g(x )=c b ) > 0, g(•) can correctly classify x . Thus, as long as log P (g(x)=ca) P (g(x)=c b ) -2(c + 1)

√ > 0 (i.e., √ < (log p a -log p b )/2(1 + c)), g(•) classifies x as c a . Proof of Theorem 12. Let {x 1 , x 2 , • • • , x 2 d } = {0, r √ d } d .

For each x i , we use the same adversarial example x = 0 to derive the lower bound. Since A is (2r, D M R , • 2 , 2 )-robust, we have for all

x i , x j , i, j ∈ [2 d ], max{D M R (A(x i ) A(x j )), D M R (A(x j ) A(x i ))} ≤ 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 ∈ R n×d , the one-way marginal is just h(D) = 1 n n i=1 X i , where X i 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,

EQUATION

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) . 

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, D M R , • ∞ , 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 Proof of Theorem 16. Let X = {x 1 , x 2 , • • • , x 2 d } = {0, r} d be the set of samples. Since A is (2r, • • • ∞ )-robust and x i -x j ∞ ≤ 2r, we know that max{D ∞ (A(x i ) A(x j )), D ∞ (A(x j ) A(x i ))} ≤ .

Thus, A : R d → R d 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 → [0, 1] d satisfying the following inequality for all x ∈ {0, 1} d

EQUATION

then 1 ≥ Ω( d α ).

Now we consider any -DP mechanism:

A : {0, r} d → [0, r] d . If E[ A(x) -x ∞ ] ≤ α, then E[ 1 r A(x) -1 r x ∞ ] ≤ α r .

That is, 1 r A(x) : {0, 1} d → [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 = {x 1 , x 2 • • • , x 2 d } = {0, r} d . A will also be -zCDP on X as in the proof of Theorem 12. Thus, if

E[ A(x) -x ∞ ] ≤ α,

:



Figures and Tables:

Furthermore, √ can be calculated (bounded) by (log p a -log p b )/2(1 + c) or (log p a /(1 -p a ))/2(1 + c) (binary case), where p a and p b are respectively the probabilities of the randomized classifier g(•) returning the most probable class c a and the runner-up class c b on input x.

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, D M R , • 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).

Figure 1: Certifying D M R robustness in 2 norm on CIFAR-10: vary the Gaussian noise used in the training process and fix the σ of the Gaussian mechanism as σ = 0.5. c = 1 (left) and c = 3 (right)

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

Figure 2: Certifying D M R robustness in 2 norm on CIFAR-10: vary the σ in the Gaussian mechanism and fix σ of the training noise as σ = 0.50. c = 1 (left) and c = 3 (right)

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{D M R (A(D) A(D )), D M R (A(D ) A(D))} ≤ . (8) zCDP is a relaxed version of DP according to Theorem 8. Motivated by zCDP, we define D M R robustness in Definition 7.B OMITTED PROOFSProof 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 : Ω → Θ 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).

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 functionF : Ω → R by F (y) = log P[Y =y] P[Y =y] .Then Z is distributed according to F (Y ).

Theorem 1.1 in Steinke & Ullman (2016)). For every ≤ O(1), every 2 -Ω(n) ≤ δ ≤ 1 n 1+Ω(1) and every α ≤ 1 10 , if A : ({0, 1} d ) n → [0, 1] d is ( , δ)-DP and E[ A(D) -h(D) ∞ ] n = 1, = + 2 log 1 δ in Lemma 26, we can see that if E[ A(x) -x ∞ ] ≤ α then 1 ≥ Ω( 2 ), where the last inequality is due to the fact that √

Now we come back to the proof for any r.If A : {0, r √ d } d → [0, r √ d ] d is -zCDP, where E A A(x i ) -x i ∞ ≤ α,then we have E an -zCDP mechanism on {0, 1} d → [0, 1] d . By Theorem 24 with α =

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 byp D (z) ∝ z d-1 exp(-z σ ),which is obtained by integrating the probability density function (6) over the infinity ball of radius z with surface area d2 d z d-1 ∝ z d-1 . p D is the Gamma distribution with shape d and mean σ, and thus E[z] = dσ.

Peer review (iclr2020):
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. In its current state, I would vote to weakly reject this paper for one key reason. The notions of robustness defined by the authors (Definitions 3/7/8) is not the same as standard adversarial robustness (Definition 2), and the authors do not explain clearly how to translate their results back to adversarial robustness. Proving results about their own version of robustness is interesting, but it must be related back to the standard notion of adversarial robustness so that the broader machine learning community can understand how the authors’ contributions fit in the literature. It may in fact be quite straightforward to relate the two notions, but I think the authors should explain how to do so clearly. I am happy to reconsider if the authors can address this (and other comments below) in a satisfactory manner. I did not check the authors’ theoretical proofs, but I find the statements of the theorems interesting, especially the results about the maximum certifiable radius for L_inf robustness. This provides significant new insight about the fact that L_inf robustness may not be easy to certify using randomized smoothing methods. However, it is not clear to me how best to translate the authors’ results to a result for the standard notion of adversarial robustness, which I believe would be interesting to present clearly. I would encourage the authors’ to clarify (and tone down) their statement about the “optimality” of Gaussian noise for L2 robustness. Theorem 12 provides a lower bound on the L_inf norm of the noise added, and they show that Gaussian noise is close to “optimal” in terms of expected L_inf norm. I am a bit confused as to why are we providing bounds on the L_inf norm of the added noise (especially since we are verifying L2 robustness) - in what other ways is Gaussian noise (near) optimal? Does it also have the expected lowest L2 norm? Also, why do we want the noise to have low norm? I feel that “optimal” should mean being able to prove the largest possible robust radius, and if that is not what you are proving, I would encourage you to try to avoid overclaiming. Finally, the experimental results should also not just be in terms of D_MR robustness. Otherwise, it is hard to compare with prior work like Cohen et. al. Some additional feedback: - “the Lp-normed robustness” can be replaced with “Lp-norm robustness” everywhere - Page 1, say “the Gaussian mechanism” instead of “Gaussian mechanism” (toward the end of the first paragraph) - Table 1’s formatting can be improved (maybe have a box around the whole table) - Theorem 12 - use “In other words” instead of “In another word”