A Unified framework for randomized smoothing based certified defenses
Authors: Tianhang Zheng
Di Wang
Baochun Li
Jinhui Xu
Venue:  (2020)
Keywords: Certificated Defense
Randomized Smoothing
A Unified and Self-Contained Framework

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 $\ell_2$-normed robustness, and (ii) whether randomized smoothing can certify $\ell_\infty$-normed robustness (on high-dimensional datasets like ImageNet). To answer these questions, we introduce a {\em  unified} and {\em self-contained} framework to study randomized smoothing-based certified defenses, where we mainly focus on the two most popular norms in adversarial machine learning, {\em i.e.,} $\ell_2$ and $\ell_\infty$ norm. We answer the above two questions by first demonstrating that Gaussian mechanism and  Exponential mechanism are the (near) optimal options to certify the $\ell_2$ and $\ell_\infty$-normed robustness. We further show that the largest $\ell_\infty$ radius certified by randomized smoothing is upper bounded by $O(1/\sqrt{d})$, where $d$ is the dimensionality of the data. This theoretical finding suggests that certifying $\ell_\infty$-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.

Under review as a conference paper at ICLR 2020
A UNIFIED FRAMEWORK FOR RANDOMIZED SMOOTHING BASED CERTIFIED DEFENSES
Anonymous authors
Paper under double-blind review
ABSTRACT
Randomized smoothing, which was recently proved to be certified defen- sive 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 fn-noreed robustness, and (ii) whether random- ized smoothing can certify foe -ormedd robustness (on nigh-dimensional datasets like ImageNet). To answer these questions, we introduce a unified and self- contained framework to study randomized smoothing- based certified defenses, where we mainly focus on the two most popular norms in adversarial machine learning, i.e., l2 and to norm. We answer the above two questions by first demon- strating that Gaussian mechanism and Exponential mechanism are the (near) op- timal options to certify the lg and -ormeed robustness. We further show that the largest &oo radius certified by randomized smoothing is upper bounded by O(1/Vd), where d is the dimensionality of the data. This theoretical finding sug- gests that certifying -nomeed 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 CIFARIO 10 and ImageNet.
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. (016)). Nevertheless, major unresolved issue of deep learn- ing 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.) (2144). This phenomenon, referred to as adver- sarial attack, is considered to be one of the biggest threats to the deployment of many deep learning systems. Thus, 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 guarantecs), implying that they may be ineffective against stronger attacks. Recent works (He et al.) 2017 Athalye al. 2018 Uesato 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 they can classify all the samples in a predefined neighborhood of the natural samples with a setoreticalllgguraanteee 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 random- ized smoothing. [ohhn et al. (2019) successfully certify 49% accuracy on the original ImageNet dataset under adversarial perturbations with &g 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 no-moredd robustness, and is Gaussian mechanism the best option? Another important question is regarding the generalizability of this method other norms, especially the Exc norm. If randomized smoothing can be used to certify -noredd robustness, what mechanism is the optimal choice?
error bound. Among all existing certifiable
To shed light on the above questions, we propose in this paper unified and self-contained frame- work for randomized smoothing based certified defenses. We look at the problem from a differential privacy's 's point of view and present two types of robustness in this framework. One is motivated by

---

Under review as a conference paper at ICLR 2020
no-rmedd
foe normed
Mechanism
Doo Robustness
DaR Robustness
Doo Robustness
DMR Robustness
near optimal
optimal
Gaussian
unable to certify
unable to certify
scales in O(1)
scales O (1l//llog/
optimal scales ((1/d)
Exponential
not optimal
not optimal
not optimal
Table I: Summary of our framework
c-differential privacy (c-DP), which uses co-divergence to measure the distance between the prob- abilities of predictions on randomized natural samples and randomized adversarial samples and is therefore called Do robustness. The other is inspired by c-zero concentrated differential privacy (e-zCDP) that uses the Maximal Relative Rényi (MR) divergence as the probability distance mea- surement and is called DAR robustness. For both of them, we focus on certifying robustness in either & or lo norm by randomized smoothing. Specifically, our contributions are five-fold:
1. We propose unified and self-contained framework for certifying Doo and/or DaR robust- ness in f2 and to norms by randomized smoothing.
2. In our framework, we demonstrate that the Gaussian mechanism is a near optimal choice for certifying DMR robustness in & norm, and the robust radius O(1).
3. We also prove that an exponential mechanism is the optimal choice for certifying Doc robustness in &o norm, but the robust radius is only O(1/d), making it unscalable high- dimensional data.
4. We show that the Gaussian mechanism is also near optimal choice for certifying DMR ro- bustness in & norm, but the robust radius is O(1/ ((1/Vd logo making it also hardly scalable to -ige-nimensional data.
5. The largest robust lo radius that can be certified by randomized smoothing to achieve DMR robustness is upper bounded by O(1/vd).
Table 1 summarizes the (near) optimal mechanisms of framework for certifying the la and too- normed robustness.
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 tech- niques, 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 al.) 2018). The third approach uses randomized smoothing to certify robustness, and is gaining popular- ity recently due to its strong scalability (Lecuyer 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 random- ized smoothing
certify the & and en-ormed robustness by using inequalities from differential privacy. Li et al. 2018)) achieved a stronger guarantee on the fg-normed robustness using tools from information theory. Cohen et al. (2019) further obtained tight guarantee on the fn-normed robust- ness using Gaussian noise. A remaining issue in all of these works is that they did not give answers to questions like why Gaussian noise used to certify the En-noreed robustness and what is the best mechanism to certify the loo -ormed robustness. To answer these questions, we present in this paper a new general framework to study randomized smoothing based certified defenses.
ROBUSTNESS MOTIVATED BY DIFFERENTIAL PRIVACY
In this section, we introduce our framework. Let x be a data sample and y E y be its label, where y is the label set. We denote by f(-) deterministic classifier with prediction f(x) for any data sample x. If there exists an x' in a small I, ball centered at x and with f(x') + fxx), x' viewed as an adversarial sample.
2

---

Under review as a conference paper at ICLR 2020
Definition 1 (Randomized Classifier (Cohen et al. 2019)). Given input the prediction of randomized classifier g(.) is defined as
argmax P(g(x) c).
.EY
Specifically, for a randomized smoothing classifier g(x) f(x Z), where Z is a random vector and f(-) deterministic classifier, the prediction of x the class of whose region _ {ā R [(z) e} has the largest probability measure in the distribution of + Z (Ø p( + Z)).
Before introducing our framework, we first recall the definition of robustness for a deterministic classifier in (Diochnos al. 2018).
Definition 2 (Robustness (Diochnos et al., 2018).. For given classifier f. sample æ and some norm || 11. f is (r.ll ())r(error-region)) robust on the sample x if
Yal E f(x) f(x'),
where (Bx,r) r) is the ball centered at x and with norm
and radius r.
To generalize the concept of robustness randomized classifiers (see Definition [ define relaxed version of the (error- region) robustness. Since g(z) is a random value, instead using equality, we measure the dif- ference between ()x) and g(x') by certain divergence. This leads us the following definition, which is a basic concept in our framework that will be used throughout the paper.
Note that in Definition 2 the classifier assumed to be deterministic.
Definition (Relaxed Robustness). For a given (randomized) classifier g()), a sample x and some norm ||. the classifier g is (r, DI -1, rerror-rno))))) robust if
Val E B (a,, r), max (D(g(=)) D(g((')) g(x))} c.
(2)
where some divergence metric between two probability distributions. The max function used to ensure that the measurement is symmetric.
Compared with Definition] 2] there are two additional terms in Definition 3 represents the "dis- tance" or difference between the distributions of g(x) and g(x²). When small, expect that the distributions of predictions on æ and x', iee, g(x) and g(x'), are almost the same, which is just generalization of the equality in Definition two probability distributions. In this paper, we use two types of divergence, so-Divereence and Maximal Relative Rényi Divergence, to measure the distance between two probability distributions. Correspondingly, we have two types of robustness called D.c and DMR robustness.
D is some divergence measurement between
Definition (oc-Divergence), The oo-Divergence D of distributions P and Q is defined as
P(x)
(PI[()
sup log Q(x)* =EmpP(Q)
where supp(Q) is the support of the distribution Q.
Definition (Maximal Relative Rényi Divergence). The Maximal Relative Rényi Divergence D (MI(P))Q) of distributions and Q defined as
(P(I))
DMR(PI1Q)
max aE(1.0c)
where (a(l))Q) is the Rényi divergence between P and Q, which is defined
P(x)
Da(P((Q) = a log E.gl
Q(x)
Definition 6 (D Robustness). A randomized smoothing mechanism A(-) (including classifiers) is
Doo e)l mechanism
Vx' E B(x, r), max (Alz)) A(z)))(()())),, D(A(s)) Se,
(3)
where ||- || the norm of the ball B(x, r). If randomized smoothing classifier 9(-) satisfies Eq.
is (r, Docs -robust classifier it certifies Doc Robustness.
3

---

Under review as a conference paper at ICLR 2020
Do Robustness is motivated by the notion of e-differential privacy (c-DP) Dwork et al. 2006)_ To achieve e-DP for a randomized algorithm, we can use several mechanisms such as Laplacian mechanism Exponential mechanism (see (Dwork al. 2014) for details). However, it is known that adding Gaussian noise often does not lead to <-DP, but rather (e, (e,D) (Dwork et al. 2014) which has additional parameter 8 and thus is harder be incorporated in our framework. To alleivate this issue, we employ Maximal Relative Rényi Divergence as the the probability distance measurement define another type of robustness, namely DM robustness.
Definition 7 (DMR Robustness). A randomized smoothing mechanism A(-) is (r, DMR, ll el, robust mechanism if
Vx' E BBx, r), (anx)DM((A())).... A(x')) (ann(A(z)), Sc.
(4)
If a randomized smoothing classifier g(-) satisfies Eq. 4. it is (r, DMn, |I Il, c)-rouust classifier or it certifies DMR Robustness.
D MR Robustness is inspired by the notion of CereeCooneetteaeed Differential Privacy (zCDP) (Bun & Steinke, 2016), whose connection to DP is shown in the following theorem.
Theorem 8 (Bun & Steinke| 2016)). Let and Q two probability distributions satisfying the conditions of Dox (PIQ) S and (Q)PP) S Then, Pann(Pl(Q S 1/22.
Theorem indicates that robustttsssssss is a relaxed version of D -rbbsttess....
Remark (Connections between Do & DarR Robustness and Standard Definitions). Although Doc & DMR Robustness are seemingly new concepts defined in this paper, they actually have several connections with the existing fiistingrrmmeeer frameworks Lecuuy et al. (2018) and Cohen et al. al. (20T9). Specifically, as long as Deo robustness is certified. the expected output stability bound in Lecuyer et al. (2018) will be guaranteed with 8' 0. And if DMR robustness is certified, the expected output stability bound in Lecuyer et al. (0018) will be guaranteed with è' (c 1)ve and 8' =xx((=5 according to Theorem TO Besides, the "scale" " of the robust radius certified by our framework is similar the "scule" " of the robust radius in Cohhn el al.) (2019), according to Corollary [7]
Theorem 9 (Postprocessing Property). Let g(x) = f(A(z)) be a randomized classifier, where f()) any deterministic function (classifier). g(-) is (r, D, 11 ell,e) --robustt if A(.) is (r, D, (l,
(where D includes Dxx and DMR)
The above theorem 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, consider the cases of certifying Doc DMR robustness using & and norm.
3.1 CERTIFYING le- NORMED ROBUSTNESS
The following theorem shows that randomized smoothing by the Gaussian mechanism is (r, DMR, - e-robusst.
Theorem 10. Let be any classifier and g(x) = (xx+2) be its corresponding randomized classifier y²
for samples x E Rdd, where 2 ~ NO, o²Ia). Then, g(-) is (r, DMR, || l|2, 202 -rooustt on any x.
,2 20z. Then, for any and any measurable set S o 0, the following holds
Moreover, let e denote
with probability at least 1 exp(-12
P(g(x) E S)
log P(g(z') E
< <X+VE.
(5)
P(g(a)ES) That is, when X = cve, log P(g(a')ES) I (c+ 1) with probability 1- --expp--t +). In practice,
c = 3 is enough to achieve high probability.
Corollary 11. Adding Gaussian noise = E o2 can defend any x' E BB(x, = 22a) that satisfies the condition of DMa(g(=)]lo(2))) < with probability at least 1 - exp(- Further- (1))/(11) + c)
more, ve can be calculated (bounded) by (log Pa log pt) (21)22(11))) + c) or (binary case), where Pa and ps, are respectively the probabilities of the randomized classifier g(.)
returning the most probable class ca and the runner-up class es on input
4

---

Under review as a conference paper at ICLR 2020
Detailed proofs for Theorem 10 Corollary 11 and all the following theorems are provided in Appendix From Theorem we can see that for classifier like g(z) = f(x + z), we only need to prove that the randomized mechanism A(x) x + z(2 _N(0, 1a)) is (r, DM |12, 2 robust. Also, the connection between and Pa. Ph can be derived for all e or ve (in the certified radii) as in Corollary []] Note that a similar theorem has also been proved byyCohen et al. (2019). But there some major differences between
framework and theirs (Cohen et al. [0119). Specifically, our framework certifies the robustness with a probability of failure, and the certified radius r depends on that controls the probability of failure. A smaller yields larger r compared those in Cohen ett al. (211)) and vice versa. Moreover, in our framework, we show that the Gaussian mechanism is near optimal option, by providing a lower bound below for all possible noises that can certify the Eg-normed MRR robustness.
Next, we consider the following unanswered question (i.e., the first question). Since there are infinite ways of sampling 2, a natural problem is to determine whether Gaussian mechanism is the optimal option to certify the ég-normed DMR robustness. To answer this question, we first give a lower bound on the magnitude of the noise added in the randomized smoothing mechanism A(x) = z+ to ensure that A(x), as well as f(A(x)) (r: Dar || ||2, r)rroustt. 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 S (1)), if there is a (2r, DMa,, || ll2, 2)- robust randomized smoothing mechanism A(x) = + 2 [0, Va- 10, r such that for all
d
E 10, Val
[[]=]l=]==A|AA - x 21100 S a =
for some a S O(), then it must be true that a 2 (c)) In another word, S2 (+) is the lower bound of the expected foo norm of the random noise.
Theorem 12 indicates that the expected lor norm of the added random noise should be at least 2 (e) to guarantee (r, DMRRI |12, clobussssssssss For Gaussian mechanism, the expected & norm
is (logl ((Orabona & Pál 2015)), which is 0 /og d) according to Corollary 11 This
means that Gaussian mechanism is near optimal (i.e., up to an O(vlog d) factor) here. Equivalently. if we fix the magnitude of the expected -nom of the added noise a, the largest radius that can
be certified by any (r, DMR. || lla, e)-robust randomized smoothing mechanisms is upper bounded by Ve)y), which is also close the robust radius guaranteed by Gaussian mechanism (up to an O( OVVlog d) factor).
3.2 CERTIFYING NNRRMED ROBUSTNESS
Previous work on the randomized smoothing- based certified defenses (Cohen et al. 2019 Li et al., 2018) mainly uses Gaussian noise certify the E2-normed robustness. Thus, another natural ques- tion (i.e., the second question) is to determine whether randomized smoothing can use some mech- anism certify the Ex 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 fz-normed case and inves- tigate the form of the density function of Gaussian noise: p(z) exp(- a2 we conjecture that, to certify -ormedd robustness, we can sample the noise using an exponential mechanism:
-
Based on this,
|
p(z) exp
(6)
We show in the following theorem that randomized smoothing by (6) certifies (r, DMR: || lloo, )- robustness. which could be considered as an extension of the fo-noreed case. Moreover, we can prove that it is (r, Doe : || Iloo, --rousst However, the certified radius is O(1/d), which implies that it is unscalable to high-dimensional data.
Theorem 13. Let be any classifier and g(x) = f(x+z) be its corresponding randomized classifier for sample x E Rdd, where the noise z ~ p(2) in 16. Then, g(-) is (r. DMRs ll Iloe: 2gz --rousst. Moreover, it is (r, Doc; Il ||oo; -robust.
5

---

Under review as a conference paper at ICLR 2020
Remark 14. Due to the high dimensionality of samples in real world applications. directly sampling 2 ~ p(2) by the Markov Chain Monte Carlo (MCMC) algorithm requires a large number of random- walks that can incur high computational cost. To alleviate this issue, we adopt efficient sampling method from (Steinke & Ullman 2015) that first samples R from Gomma(d+ (d-1, a)) and then samples from | R, RJ uniformly. The complexity of this sampling algorithm is only ((d).
Comparing Theorems and [3] we can see that randomized smoothing via (6 can certify region that has (almost) the same radius as that of Gaussian distribution in the ég-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 & n-normed case.
Theorem 15. For the distribution that can guarantee Theorem
13 the following theorem holds
E [=] = do.
Note that compared with the Gaussian noise added in Theorem T0 which satisfies the condition of E. [=] = Vlog d), the expected -nom 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 da, which will completely ruin the accuracy of the classification network. However, if we want the noise to have magnitude of (1)), needs to be ((/d)), and so does the robust radius.
Theorem 15 is a somewhat negative result for randomized smoothing using distribution (6 cer- tify the normed robustness. Thus, an immediate question is whether exponential mechanism is the right choice certify the fo -nrmed robustness. The following theorem shows that for any (r, Doe. || |lse. -robust randomized smoothing mechanism, the expected los -norm of the added noise is lower bounded by (ddr).. Thus, combining the following theorem with Theorem [5 we can conclude that the exponential mechanism is actually an optimal choice to certify D= robustness.
Theorem 16. For any (2r, Doe; |l |l,o, )-rbusst mechanism A(x) = r + 2: [0, r] + [0, such that
E |||aa| = AallA(x) 21100 Sa Va E [0, r)
must be true that a 2 m.
From Theorem 16 we see that, for any (o, || 1l.o -robust randomized smoothing mech- anism, if we fix the expectation of the -nom of the added noise in the exponential mechanism a, the largest fx radius that can be certified is upper bounded by O(ac/ /d). Compared with the fn-normed case in Theorem 11 we can see that there an additional factor of O(1/d), which makes unscalable high-dimensional data. Equivalently, if we want the same radius to be certified in the Theorem 10 the expected foe -norm of the added noise needs to be at least Q m which will be too large for any image data.
The less than ideal lower bound in Theorem 16 is for Doc rrobustness. Since D -oobustness is more relaxed than -obbuusus,s,,, a natural question is thus determine whether the lower bound can be improved by switching to Dar robusstess.s Unfortunately, the following theorem shows that a similar phenomenon still holds for -oboustsstsss..
Theorem 17. For any (2r, DMR, such that
|loo ) -robust mechanism A(x) =x+2 r], r]
E ||||=||d] A()) æl1>0 S a [0,r]*
must be true that a 2 20 2 Tv
From Theorems 17 and 15 we can see that in the definition of (2r, Darn -1 -robustness, adding noise according to 6 is not near optimal. The following theorem shows that in this case, Gaussian mechanism is actually near optimal choice.
dr² Theorem 18. Let r, > be some fixed number and A(x) = x + with & ~ NO, 2c Then, A(-) is (r, DMRRI |l Iloo, ro-rousst. E|]| All) x zo/o0 is upper bounded by O( O(rValogd) /e
From Theorem and 18 we can conclude that for all randomized smoothing mechanisms that are (,,0, PMRs
rrobsst if the expected fxx -orm of the added noise is fixed to be a, the

---

Under review as a conference paper at ICLR 2020
1.0
train a 0.25
train a 0.25
train a 0.50
train a 0.50
0.8
0.8
certified accuracy
train a 1.00
certified accuracy
train a 1.00
0.6
0.6
0.2
0.0
0.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4 0.6
0.8
1.0
radiuss (Duc c=
f radius (Dim C=3)
Figure 1: Certifying DM robustness in l2 norm CIFAR-10: vary the Gaussian noise used in the training process and fix the a of the Gaussian mechanism as o = 0.5. c c (left) and c = 3 (right)
largest radius that can be certified is upper bounded by O VEa and the largest radius that can be <a
certified by Gaussian mechanism is O(1/vdlogu (and is Q ((ggg)) a and are both set to be (1), the largest radius that can be certified using Gaussian mechanism to achieve DM robustness is greater than the largest radius that can be certified to achieve Doo-rouuss by at least a factor O(vd/ log d). This is reasonable since the definition D 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 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 two widely-used datasets, i.e., CIFARIO and Im- a Following Cohen et al. (2019), we use a 110-layer residual network and the classical ResNet-50 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, 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 e in all our derived certified radii can be calculated by Pa (or Pa and p6) as shown in the proof of Corollary II It is also worth noting that we do not compare our results with (Cohen 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 guar- antee on the fz-noreed robustness but aims at presenting a general and self-contained framework to study some remaining issues, such the optimality of the Gaussian mechanism, and the specific mechanisms to certify the -nomeed robustness.
4.2 EMPIRICAL RESULTS
Certifying the fn-noreed Robustness To certify the no-neeedd Robustness, in previous section, Gaussian mechanism is a near optimal option. Thus, we mainly evaluate the performance of Gaussian mechanism in 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 [ As shown in Figure 1 using a 0.50 Gaussian noise train the classifier is good setting here. So in Figure 2 we evaluate the Gaussian mechanism with different a values on the classifier trained by σ 0.50 Gaussian noise. Overall, on CIFAR-I0, our framework can certify
explained
approximately 20% accuracy under & = 1.0 perturbation!] We also show the results on ImageNet
by Figures and 5 Appendix
* Pixel value range [0.0, 1.0]
I For more details, please refer to (Cohen et al. 2019)
Onn CIFAR- 10, & 1.0 perturbation allows 4/255 perturbation every pixel
7

---

Under review as a conference paper at ICLR 2020
1.0
a 0.25
0
0.25
a 0.50
O 0.50
certified accuracy
0.8
o 1.00
certified accuracy
0.8
o 1.00
0.6
0.6
0.2
0.2
0.0
0.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
raddiuss (Duc c=
f radius (Dim c=3)
Figure 2: Certifying DM robustness in & norm on CIFAR-10: vary the in the Gaussian mecha- nism and fix a of the training noise as a 0.50. c = (left) and = 3 (right)
1.0
0.25
o= 4
0.50
certifed accuracy
certified accuracy
1.00
0.6
0.6
0.4
0.4
0.2
0.2
0.00
1.00 1.25
2.00
15.0 17.5 Gaussian mechanism (Dwx C=3): & radius (1e-3)
2.5
5.0
Exponetial mechanism (D.): fa radius (1e-3)
Figure 3: Certifying Da robustness and DAR robustness foo norm on CIFAR-10: vary the a in the Exponential mechanism (left) vary the in the Gaussian mechanism (right). The classifier is trained with a = 0.50 Gaussian noise.
Certifying the normee Robustness To certify the lx normed robustness, we evaluate the performance of the Exponential mechanism in the definition of -ob-ustusss and the Gaussian mechanism the definition of moggrobustssss. As shown in Figure 3 the fop radii that can be certified by Gaussian mechanism are about 10 ~ 20 times (i.e., O(yd/ log with = 3072 as shown in our theories) larger than the log radii certified by the exponential mechanism. On ImageNet, as shown in Figure in Appendix C the robust radii are less than 1/255 (due to scaling in ((1/d) or (1/v/d d)), indicating that certifying the lo normed robustness by randomized smoothing may not be applicable to high-dimensional data.
CONCLUSION
In this paper, we present a general framework for certifying two types of robustness (Doc and D Ma robustness) in the and fo norms by randomized smoothing. Under our framework, first give the answers to the remaining questions in the previous studies on randomized smoothing-bar certifiable defenses, i.e., the optimality of Gaussian mechanism and the possibility certify the normed robustness. Specifically, we demonstrate that (i) Gaussian mechanism is near optimal option to certify Dobuuuuusssssss lg norm by giving lower bound on all D As R-rouust mecha- nisms, with certified radii scaling in O(1); ); (ii) an exponential mechanism is the optimal choice for certifying -rbbuutusssssss in foo norm, with certified radii scaling in (1/d);: (iii) Gaussian mech- anism is a near optimal option to certify DM g-rbuustness in loo norm, with certified radii scaling in (11/ / log d); (iv) the largest loo radius that can be certified by randomized smoothing in our framework is upper bounded by (1/Vd)) indicating that randomized smoothing may not be scal- able to high-dimensional data in terms of certifying the normedd robustness.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give false sense of security: Circumventing defenses to adversarial examples. arXiv preprint (adi:0/802.0022.0 2018.
Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Thheory of Cryptography Conference, pp. 635-658. Springer, 2016.
Mark Bun, Jonathan Ullman, and Salil Vadhan. Fingerprinting codes and the price of approximate differential privacy. SIAM Journal on Computing, 1785):1888-1933 2018.
Kyunghyun Cho, Bart Van Merriënboer, Caglar Gulcchre, Dzmitry Bahdanau, Fethi Bougares, Hol- ger Schwenk, and Yoshua Bengio. Learning phrase representations using rnn encoder-decoder for statistical machine translation. arXiv preprint arXiv: /406. /078, 2014.
Jeremy M Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. arXiv preprint arXiv: /902: /902.02918, 2019.
Dimitrios Diochnos, Saeed Mahloujifar, and Mohammad Mahmoody. Adversarial risk and robust- ness: General definitions and implications for the uniform distribution. In Advances in Neural Information Processing Systems, pp. 10359-10368, 2018
Krishnamurthy Dvijotham, Robert Stanforth, Sven Gowal, Timothy A Mann, and Pushmeet Kohli. A dual approach to scalable verification of deep networks. In UAI, pp. 550-559, 2018.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. Theory of cryptography conference, pp. 265-284. Springer, 2006.
Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 9(3-4):211-407) 2014.
lan J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. arXiv preprint arXiv:1442..66. 2014.
Sven Gowal, Krishnamurthy Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Ue- sato, Timothy Mann, and Pushmeet Kohli. On the effectiveness of interval bound propagation for training verifiably robust models. arXiv preprint arXiv: 1810. 12715, 2018.
Moritz Hardt and Kunal Talwar. On the geometry of differential privacy. In Proceedings of the forty-second ACM symposium on Theory of computing, pp. 705-714. ACM, 2010.
Warren He, James Wei, Xinyun Chen, Nicholas Carlini, and Dawn Song. Adversarial example defense: Ensembles of weak defenses are not strong. In Ithh USENIX Workshop on Offensive Technologies (WOOT 17), 2017.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey Hinton. Imagenet classification with deep convo- lutional neural networks. In Advances in neural information processing systems, pp. 1097-1105, 2012.
Mathias Lecuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified robustness adversarial examples with differential privacy. arXiv preprint arXiv.1802.03471, 2018.
Bai Li. Changyou Chen, Wenlin Wang, and Lawrence Carin. Second-order adversarial attack and certifiable robustness. arXiv preprint arXiv:1809.00 2018
Matthew Mirman, Timon Gehr, and Martin Vechev. Differentiable abstract interpretation for prov- ably robust neural networks. In International Conference on Machine Learning, pp. 3575-3583, 2018.
Francesco Orabona and Dávid Pál. Optimal non-asymptotic lower bound on the minimax regret of learning with expert advice. arXiv preprint 15X 2015.

---

Under review as a conference paper at ICLR 2020
Aditi Raghumathan, Jacob Steinhardt, and Percy Liang. Certified defenses against adversarial exam- ples. arXiv preprint arXiv:1801.09344 2018.
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, al. Mastering
the game of go with deep neural networks and tree search. nature, 529(7587):444488, 2016.
Thomas Steinke and Jonathan Ullman. Between pure and approximate differential privacy. arXiv preprint arXiv: 10005, 2015.
Thomas Steinke and Jonathan Ullman. Between pure and approximate differential privacy. Journal of Privacy and Confidentiality, 7(2), 2016.
Christian Szegedy, Wojciech Zaremba, Ila Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. arXiv preprint arXiv:1312.619 6199 2013.
Jonathan Uesato, Brendan ODonoghue, Pushmeet Kohli, and Aaron Oord. Adversarial risk and the dangers of evaluating against weak attacks. In International Conference on Machine Learning. pp. 5032-5041, 2018.
Roman Vershynin. High-ddmensional probability: An introduction with applications in data science, volume 47. Cambridge University Press, 2018.
Shiqi Wang, Kexin Pei, Justin Whitehouse. Junfeng Yang, and Suman Jana. Efficient formal safety analysis of neural networks. In Advances in Neural Information Processing Systems, pp. 6367- 6377, 2018.
Eric Wong and Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In International Conference on Machine Learning, pp. 5283-5292, 2018.
10

---

Under review as a conference paper at ICLR 2020
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. (0066). Given data universe X, we say that two datasets D, D' S are neighbors if they differ by only one entry, which is denoted by D ~ D'. A randomized algorithm A is e-differentially private (DP) if for all neighboring datasets D, D' the following holds
(=(A(I)))((")) Se
Intuitively, DP ensures that adversary cannot infer whether 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 I-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 Doc robustness in Definition 6
participant (data sample) is
Definition 20 (Zero-Concentrule called e-PD for all D D
Differential Privacy (zCDP)), A randomized mechanism A is
max Maxx(DM(((DD))A)) DMR((A(D))))))) Sc.
(8)
zCDP is relaxed version of DP according to Theorem g robustness in Definition
Motivated by zCDP, we define DMR
B OMITTED PROOFS
Proof of Theorem This theorem can easily proved by the following lemma,
Lemma 21 ((Bun& & Steinke, 2016)). Let P and Q be two distributions on Q and let f S2 + θ be deterministic function. Let f(P) and f(Q) denote the distributions on θ induced by applying to P and Q respectively. Then we have
Da(f(P)[((()) - (a(P)))..
Similar post-processing property also holds when co (Dwork al. 2006). Therefore, if A(-) satisfies Definition 6 or then f(A(-)) will satisfy Definition 6 or for any deterministic function
(classifier) f()).
Proof of Theorem 10 By Theorem 9 we only need to show that the randomized smoothing mecha-
nism A(x) 2 (r, MR robustt which can be proved by the following lemma.
Lemma 22 (BBun & Steinke, 2016).. Let x. E Rd, and E [1. 30). Then
a o - 2'11
Da o (a))
20
Thus for all x' E BB(xr)) r). we have DMm(A()))LA(T)) S 26
Next we prove
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 (Yoss""l follows: Define a function F(Y=vl F 12:4+R F(y) = log FLY Fl Then Z is distributed according to F(Y).
By this we can write Z Loss(g(z)llo(z)) and rewrite (MR(o()))lo((') as
Va E (1, oo]. (ac(a-1)22 1)2] (a--) (1)
This implies that Z is sub-Gaussian By using the tail- fail-bound of Buu-Gaussiin (Vershynin 2018 have
plz > x+e s
(9)
7 where
25
11

---

Under review as a conference paper at ICLR 2020
20 the certified radius is r V2co. Now prove the upper bound of ve for classifier g()). Given Theorem 10 should have
Proof of Corollary 17] Since fix r²
P(g(z) ca) log P(g(x') ca)
(cc
and
P(g(z') = cb)
log P(g(z) ct)
S {(c+
since x also in [a(,, r). Then we have log P(a(e' )cca) log P(ola)=ca) 2(c+ 1)ve. According P(g(z)=as
P(g(=")=oo)
to Definition
as long as log P(a(a')=ca) P( > 0, g(-) can correctly classify x'. Thus, as long as 2(c+1)/e>>> 0 (i.e. vc Po logpb))/(11) cc), g()) classifies x' as Ca-
log P(a(z)=o)
Proof of Theorem 12
Let (
122 {0, ld For each zi, use the same adversarial
Vdl
example x' derive the lower bound. Since is (2r, DMn. || l12, 2 --robust, we have for all Ti, F,. 2,j [2d),
max max (Ox(MR(((())))) (A(r)) ( < =6
That is A is e-CDDP on the dataset X' = {0, 12. Next we will prove the lower bound for all e-zCDP mechanisms.
first consider the case where r = vd, 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 e-zCDP, For n-size dataset X Rexd, the one-way marginal is just h(D) = Σー= X,, where X, is the i-th row of X. Specifically, when 1, one-way marginal just the data point itself. We show the following theorem,
Theorem 24. If there exists e-CDDP mechanism A 10, [0, 1] such that for all (0, 1)dd
BJ|A(x) - x/loc S a,
(10)
then 2 MW
Proof of Theorem and (c, DP.
24
To prove this theorem, idea is first the connection between 6-ZCDP
Lemma 25 (Prop.1.3 in Bun Steinke (2016)) If A is e-cCDP, then it is (e + 2//e log 5)
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 < 0(1), every ((()m < <
14001 and every a < 1 if A: (10, 1 1 is (e, 8D and E[][A(D) - h(D) a
10
then
dog 1
2 n
(11)
Ea
Setting n = 2 clog in Lemma 26 we can see that [[][((r) - xo|ool s a then
1 1 01 /dllgg Q
Sa
where the last inequality due the fact that /log
(ct2//log log 1)aa
Va?.
c+2//clog]
2 1.
12

---

Under review as a conference paper at ICLR 2020
Now come back to the proof for any If A
{0,
10, -0,-51 Va is e-zCDP, where
va
ExllA(zz)) zu Σ a, then we have EAl Vd A(T,)
Ld x21100 I dda. Thus, A is an e-
zCDP mechanism on (0, 10, + [0, 1]". By Theorem 24 with a vda I 0(1,, we have
2 S Vea²"
i.e. a a 2 V
(12)
Proof of Theorem 13
We will first prove that A(x) Z is (r, Doo: Io =) -robust.. Then
by Theorems
can easily show that g(-) is (r, DMR: |1 Il 2 -robust. Consider 000 r. Then, for any y we have
8 and
I, x', ||
x
ply 2)
exp( |yحسوم
1ly 10 1ly x S exp( || 1 S exp(
I exp(
p(y x') exp( y-
Thus, for any subset we have
A(x) ES = log A(x') E Jzp(z - ed)dz
Jsp(z -x)d2
log
Proof of Theorem 15
Define the distribution D on [0, oo) to be Z D. meaning 2 = ||=||00 for
p(z), where p(z) is in (). The probability density function of D is given by
pD(2) d-1 eep(p==
which is obtained by integrating the probability density function 66 over the infinity ball of radius with surface area d2d 2 dd1 x =d-1 pD is the Gamma distribution with shape d and mean and thus ][z] do.
Proof of Theorem 16 Let X' fx1, ,T2a r) be the set of samples. Since A is
(2r, ... 1 rrobust and ||I; - 2jil0c xc S 2r, we know that (ixx(DxxAAzxi
DA <..
Thus, A: + Rd is e-D on X. Similar to the proof for Theorem 12 we can reduce our problem studying the lower bound of one-way marginal for 1-size data problem in the c-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 e-DP mechanism A (0,1) + [0, 11 satisfying the following inequality for all a E {0, 1]d
BI(A(z) xlloc Sa,
(13)
then 2 ( ).
Now we consider any e-DP mechanism A: r0, dd + [0, r] If
E[[[A()) - x||oo| S a,
then E|[| ((xx) - ].0]boo] S. That is, ..(()) (0, 13 + [0, 1]d Thus, by lemma 26
we can see
that 2 2 dr).
Proof of Theorem 17
The proof almost the same as that Theorem 12 Assume that we have
set of data points X
{x1,
22
F24 r0, _ A will also be c-zCDP X' as in the proof of
Theorem [2 Thus, if
E [(())())) 37 x0llo]] a,
13

---

Under review as a conference paper at ICLR 2020
then
1
B|| A(x)
r x - a
This means that tA(x)) 10, + [0, 11dh e-zCDP. Thus, by Theorem 24 we must have
dr Ea?
1 2 2(
Proof of Theorem
18 The proof is almost the as that of Theorem
TO Lemma
22
have
dr
dr))
dr
ac|
ade
|
x
11
(N
2
26
dr
dr
Therefore, A(x) = x with = N(O,
dr² 2x
is (r. DMR, || bo,o, robust. The bound of [[[]=]|
can be easily proved by substituting a in O llg (Orabona & Pál
2015)) with dr2
2c
14

---

Under review as a conference paper at ICLR 2020
C
MORE EXPERIMENTAL RESULTS (IMAGENET)
C.1 CERTIFYING & ROBUSTNESS
1.0
train
train 0.25
train
train
0.8
certifled accuracy
train
certified accuracy
=.00
0.6
0.4
0.2
0.0
0.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
radius (Dion C=1)
8 radius (Due c=3)
Figure 4: Certifying DAR robustness in lg norm ImageNet: vary the the Gaussian noise in the training process and fix the a of the Gaussian mechanism as a 0.5. = 1 (left) and c= 3 (right).
1.0
1.0
0= a 0.50
0.8
certified accuracy
o 1.00
certified accuracy
0 1.00
0.2
0.6
0.8
1.0
0.0
0.4 0.6 fg radius (Dow C-3)
1.0
radius (Din c-1)
Figure 5: Certifying DMR robustness &2 norm on ImageNet: vary the a in Gaussian mecha- nism and fix the of the training noise 0.5. == (left) and = 3 (right). There is green line because the accuracy is when adding a 1.0 Gaussian noise to the images.
C.2 CERTIFYING to ROBUSTNESS
1.0
1.0
0.8
certified accuracy
o=
certified accuracy
0=
0.0
0.00 0.25 0.50
0.75
1.00
1.25
1.50 1.75 2.00
50
100
150
200
250
300
Exponetial mechanism (O.): f. radius (1e-5)
Gaussian mechanism (Due c=3): f.. radius (1e-5)
Figure 6: Certifying D robustness and DMR robustness in loo norm by the Exponential mech- anism and the Gaussian mechanism on ImageNet: vary the a in the exponential mechanism (left) vary the a the Gaussian mechanism (right). The classifier trained with 0.50 Gaussian noise, As we can see, the certified radius is smaller than 1/255.
15


Reviews:
[{"review_id": "rklU2Gp6FH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary of the paper's contributions:\n\nThis paper introduces two new notions of robustness for randomized classifiers, which are based on the notions of differential privacy (DP) of randomized mechanisms. Specifically, the D_\\infty robustness and D_{MR} robustness of a random classifier are defined based on \\epsilon-DP and \\epsilon-zCDP, respectively.\n\nThe paper proves lower bounds on the noise level of a random classifier for which it can be certified D_\\infty robust and D_{MR} robust. Further, it is shown that the lower bounds are achieved by random classifiers constructed using Gaussian noise and exponential noise for l_2 and l_\\infty robustness, respectively.\n\nMajor criticisms: (1) The paper does not give sufficient motivation for studying D_\\infty robustness and D_{MR} robustness. (2) The paper makes several unsubstantiated claims regarding the optimality of different noise models for adversarial robustness.\n\nDetailed comments:\n\n- All the claims made in the paper regarding the optimality of different noise models  are specific to D_\\infty and D_{MR} robustness. However, they are written in a way to imply that the claims also hold for the standard l_2/l_\\infty robustness which is studied in adversarial ML literature (especially in the abstract and intro section). The authors should make clear the relation between D_\\infty and D_{MR} robustness and the standard notion of robustness of a classifier. Does one imply the other?\n\n- Does the relaxed notion of robustness of a random classifier g (Definition 3) imply a robustness guarantee for the final output of the random classifier, i.e., \\argmax_c P(g(x) = c) ?\n\n- The experiments use the same setup as in Cohen et al, but the results are not compared with those in Cohen et al. It is not clear how to judge the significance of these results without comparison to any other method of evaluating robustness.\n\n- \"However, it is known that adding Gaussian noise often does not lead to \\epsilon-DP, but rather (\\epsilon; \\delta)-DP (Dwork et al., 2014) which has an additional parameter \\delta and thus is harder to be incorporated in our framework. To alleviate this issue, we employ Maximal Relative Renyi Divergence as the probability distance measurement to define another type of robustness, namely D_{MR} robustness.\" - This does not provide sufficient justification for studying D_{MR} robustness.\n\n- A comparison is made between Theorem 10 & Corollary 11 in the paper to Theorem 1 in Cohen et al. However, it is not clear how the result in the paper is better or even equivalent to the one in Cohen et al. D_{MR} robustness seems to be an approximate notion of robustness, while the result in Cohen et al gives perfect robustness within a ball of a certain radius. The radius r in both papers scales linearly with \\sigma. It is said that \"a smaller c yields a larger r compared to Cohen et al.\" It is not clear why that is useful.\n\n- In Theorem 12, each entry in x is restricted to be in the range [0, r/\\sqrt{d}]. This means the l_2 norm of x cannot be more than r. Then, how is it meaningful to discuss the (2r, D_{MR}, l_2, \\epsilon/2) robustness of an algorithm on this data, with the radius of the robust guarantee being 2r?\n\n- In Theorem 12, the lower bound on the expected l_\\infty norm of the random noise is shown to be independent of d, while the expected l_\\infty norm for Gaussian noise scales with \\sqrt{\\log d}. I don't think it is correct to claim that Gaussian noise is \"near\" optimal from this analysis.\n\n-  In Definition 23, it is not clear what Loss(Y||Y') is.\n\nSuggestions for improvement:\n\n- The authors should make it clear in the abstract that the optimality of the noise models is with regards to the newly defined notions of robustness.\n\n- It would be worthwhile to discuss how D_\\infty and D_{MR} robustness differ from standard notions of minimax robustness.\n\n- One possible way to motivate the relaxed robustness introduced in Definition 3 is to link it to the robustness of the randomized classifier in Definition 1.\n\n- Please consider using \\left( \\right) instead of ( ).\n\n- For experiments, it would help to compare D_\\infty and D_{MR} robustness alongside the standard l_2 robustness. In addition to training the network on Gaussian augmented dataset, it might be worthwhile to compare it to other baseline approaches as done in Cohen et al.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "rkg0VfQCYH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary.\nThe 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.\n\n\n\nI find the paper very interesting and the approach is novel and generic. I do not have any major criticism.\n\nMinor comments.\n1) Equation 3 \"D(A(x'),A(x))\" >> \"D_\\infty(A(x'),A(x))\"\n2) Page 6 third line below Theorem 16. Reference of Theorem 11 should be Corollary 11.\n3) The authors should report the certified accuracy of the undefended baseline classifier over varying radius in Figures 1 and 2 and 3.\n4) Running experiments on ImageNet following Cohen et al. should make the paper stronger.\n4) Can the authors comment on is the certified accuracy for \\sigma=0.5 at radius = 0 is better than the unsmoothned classifier a sigma 1.0. I expect that the radius of certification is larger for larger sigma.\n5) The authors should explain how does the new definition of robustness relate to the common robustness definitions as the one by Cohen et al.  More discussion is necessary for this and more justification. \n6) Why is the D_MR defined as maximum over $\\alpha$? It seems it is only sufficient to define it as the ratio over $\\alpha$. It seems that this is only needed for Theorem 8 to hold.\n\n\n------------------------------------------------------------------------\n\nAfter further careful read of several relevant papers, e.g. Bun et. al 2016 and the work of Dwork \"Concentrated Differential Privacy\", I have several questions I would like to ask for some further clarifications.\n\n\n\n1) Showing that a network is robust under $D_{\\infty}$ robustness, implies very strong results. The type of results that are common in the literature. This is since $D_{\\infty}$ robustness, implies $\\epsilon$ DP networks (see Lemma 3.2 and proposition 3.3 of Bun et al.). Once $\\epsilon$ DP is guaranteed identical results of Lecurer et al. can be derived immediately as this implies separation in expectation (Lecurer et al.) where one can study directly the deterministic classifier $\\mathbb{E}g(\\mathbf{x})$ and not the random $g$ studied in this work.\n\n2) The authors rely on the lower bounds of Bun et al. to find the average maximum energy that preserves the $D_{\\infty}$ robustness (Thm 15 and 16). Authors show that indeed exponential smoothing is optimal. This is significant but the analysis was intensively based on Bun et al.\n\n\n3) The relaxation to $D_{MR}$ robustness results into improvement of the dependency on the dimension to $\\sqrt{d}$ instead of $d$ for under $\\ell_\\infty$. This should not be surprising at all and in fact is identical to the results of Bun et al. Note that the zCDP proposed by Bun et al, is a relaxed version of DP where $\\epsilon$-DP for some radius $r$ implies zCDP with radius $r^2$. See proposition 3.3. Therefore, Theorem 6 and 17 are not surprising nor are they new.\n\n\n4) My major concern was with the results relating to Gaussian smoothing. I do understand that since Gaussian smoothing only implies high probability result of DP which is often referred to as ($\\epsilon$,$\\delta$)-DP which happens to be a equivalent to zCDP proposed by Bun et. al. Therefore, I have no issues of using $D_{MR}$ to analyzing the robustness for Gaussian smoothing since it was always analyzed in the DP community with the $\\epsilon,\\delta$-DP and not the stronger $\\epsilon$-DP. However, the statement of the result (Theorem 12) confused me vastly. Let me clarify.\n\n\nTheorem 12 seems to be too good to be true. How is it possible that one can guarantee $D_{MR}$ robustness without any dimensionality dependence. Using Gaussian smoothing the $D_{MR}$ can depend on $\\sqrt{\\log{d}}$. While $\\sqrt{\\log{d}}$ may seem small; improving this to a constant in dimension is still a very big gap from $\\sqrt{\\log{d}}$. This may raise several questions whether one can actually find this optimal smoothing distribution. However, with a careful read of Theorem 12, the range of the input decreases as a function of $\\sqrt{d}$. That is for a given range of input (independent from d), the energy in fact is NOT constant but scales with $\\sqrt{d}$. In such a case, the Gaussian smoothing is now of order $\\sqrt{d \\log{d}}$. Now, the factor is still $\\log{d}$, but now this is very different as indeed improving the Gaussian to $\\sqrt{d}$ may not be of significant interest as the energy still depends in the optimal sense on $\\sqrt{d}$ which does not allow it to scale for larger problems. Moreover, Cohen et al results show that with Gaussian smoothing the energy of the noise scales $\\sqrt{d}$ since the noise energy $\\|n\\| = \\mathcal{O}(\\sqrt{d} \\sigma)$ where $\\sigma$ is std of Gaussian. Therefore, it seems that there is nothing surprising about such a result at all. The statement of the Theorem is very misleading and confusing.\n\nOverall, I like this new approach of analyzing the random smoothed classifier; however, the poor presentation of the work and the mis-represented Theorems that seem to over claim are a major reason for my rating. In addition, the paper should be self-contained in which one should not need to read 2-3 other works to figure out the details in this work and the meaning of the several robustness metrics and their direct relations to DP and Lecuer et al. results. The statement of constant in dimension lower bound on the energy of the noise under $D\\_{MR}$ was to me the major contribution; however, I found now that the statement is misleading and that in fact it is $\\sqrt{d}$ reduces the contribution of the paper particularly after learning that such lower bounds are already derived in Bun et al.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "SkeCKq0oYH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nIn 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.\n\nI 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.\n\nI 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.\n\nFinally, 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.\n\nSome additional feedback:\n\n- “the Lp-normed robustness” can be replaced with “Lp-norm robustness” everywhere\n- Page 1, say “the Gaussian mechanism” instead of “Gaussian mechanism” (toward the end of the first paragraph)\n- Table 1’s formatting can be improved (maybe have a box around the whole table)\n- Theorem 12 - use “In other words” instead of “In another word”", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: After the rebuttal, the reviewers agree that this paper would benefit from further revisions to clarify issues regarding the motivation of the DP-based security definition,  any relationship it may have to standard definitions of privacy, and the role of dimensionality in the theoretical guarantees.
Decision: Reject