$\ell_1$ Adversarial Robustness Certificates: a Randomized Smoothing Approach
Authors: Jiaye Teng
Guang-He Lee
Yang Yuan
Venue:  (2020)

Abstract: Robustness is an important property to guarantee the security of machine learning models. It has recently been demonstrated that strong robustness certificates can be obtained on ensemble classifiers generated by input randomization. However, tight robustness certificates are only known for symmetric norms including $\ell_0$ and $\ell_2$, while for asymmetric norms like $\ell_1$, the existing techniques do not apply. By converting the likelihood ratio into a one-dimensional mixed random variable, we derive the first tight $\ell_1$ robustness certificate under isotropic Laplace distributions. Empirically, the deep networks smoothed by Laplace distributions yield the state-of-the-art certified robustness in $\ell_1$ norm on CIFAR-10 and ImageNet.  

Under review as a conference paper at ICLR 2020
1 ADVERSARIAL ROBUSTNESS CERTIFICATES:
A RANDOMIZED SMOOTHING APPROACH
Anonymous authors
Paper under double-blind review
ABSTRACT
Robustness is important property guarantee the security of machine learning models. has recently been demonstrated that strong robustness certificates can be obtained on ensemble classifiers generated by input randomization. However, tight robustness certificates are only known for symmetric norms including &o and f2 while for asymmetric norms like &,. the existing techniques do not apply. By converting the likelihood ratio into a one dimensional mixed random variable, we derive the first tight & robustness certificate under isotropic Laplace distributions in binary case. Empirically, the deep networks smoothed by Laplace distributions yield the state-of-the-ar certified robustness in l norm on CIFAR-10 and Ima- geNet.
INTRODUCTION
have done series of nice works in practical sights or theoretical sights (Zheng et al. 2016 Gouk et (018). Among them, certifiably robustness is valuable, since it can withstand all attacks within a norm ball and has a nice theoretical and practical outcome. However, most work cannot deal with the case for general neural networks.
Deep networks are flexible models that are widely adopted various applications. However, has been shown that such models are vulnerable against adversary (Szegedy et 2014). Concretely, an unnoticeable small perturbation on the input can cause a typical deep model to change predictions arbitrarily. The phenomenon raises the concerns of the security of deep models, and hinders its deployment in creiision-critice applications. Indeed, the certification of robustness is a pre-requisite when AI- Al-generated decisions may have important consequences.
Certifying the robustness of a machine learning model challenging, especially for modern wver-parameterized and effectively black-box. Hence, the exist-
deep learning models that ing approaches mainly rely on empirical demonstration against specific adversarial attack algo- rithms (Goodfellow al. 2015 Madry al. 2018 Finlay al. 2019). However, this line of works can give a false sense of security. Indeed, successful defense against the existing attack algorithms does not guarantee actual robustness against any adversaries that may appear in the future.
Recently, the adversarial robustness community has shifted the focus towards establishing certifi- cates that prove the robustness of deep learning models. The certificate can be either exact or conservative, so long as the certified region cannot exhibit any adversarial examples. Given the over-paree werrpaaaaeeerrized deep models and modern high- high-dimensional datasets, scalability becomes a key property for the certification algorithms, as many methods are computationally intractable.
Our work based on the novel modeling scheme that generates ensembles of a fixed black-box classifier based on input randomization (Cohen et al. 2019). Under this framework, tight robustness certificates can be obtained with only the ensemble prediction values and randomization parameters. Given appropriate choices of distributions, the robustness guarantee
be derived for l or to norms (Cohen et al. 2019 Lee et al.) 2019). The tightness simply implics that any point outside the certified region adversarial example in the worst case. However, the derivations of the previous results heavily relies on the fact that the target norm (&2 or tu) is symmetric, therefore analyzing any perturbation direction for attacking the model gives the same certification guarantee.
In contrast, é norm is asymmetric. That is, for a given é ball centered at the origin, if we move another e ball also from the origin by a distance 6, where ||0|) is fixed, then the overlapped region

---

Under review as a conference paper at ICLR 2020
Figure I: & case, if we perturb the input with such that | is fixed, we may get very different overlapped regions with different size. Notice that this is different from &g (or lo, not shown), where the overlapped regions are always symmetric and of the same size.
between the two l balls may have different shapes and sizes (See Figure D]. The characterization of this overlapped region the key step for proving tight certificates, hence the existing techniques do not apply for f norm.
In this work, we derive tight l robustness guarantee under isotropic Laplace distributions. The Laplace distribution can be interpreted as an infinite mixture of uniform distributions over l--ormm balls, which is a natural "conjugate" distribution for & norm. Due to asymmetry, we first identified the tight robustness certificate for attacking the model in particular direction, = (168) |1, 0, ................... O). To show that other perturbation directions cannot lead to worse results, we convert the d dimensional likelihood function into relaxation for various 5 and show that the worst case result is bounded by the specific direction 0,,
dimensional function, where apply
Theoretically, our certificate right in the binary classification setting. the multi-class classi- fication setting, our certificate is always tighter than the previous certificate proposed by Lecuyer et al. (2019). The theoretical improvement always leads to superior empirical results on certifying the same model, where we demonstrate the result on CIFAR-10 and ImageNet with ResNet models. Moreover, the proposed robustness certificate on models smoothed by Laplace distributions also outperforms the same models trained and certified using Gaussian distributions (Cohen et al., 2019) in l certified robustness, where the Gaussian- robustness certificate is adapted from Eg norm.
RELATED WORK
Robustness a model can be defined in various aspects. For example, Feynman-Kat Formalism can be used improve robustness (Wang et al. 2018). In this paper, we focus on the classification setting, where the goal is to provide guarantee of constant prediction among a small region spec- or conservative, so long
ified via some metrie. The robustness certificate can be either constant prediction is guaranteed in the certified region. Note that the certification of completely black-bor model requires checking the prediction values every point around the point of interest, which is clearly infeasible. A practical certification algorithm inevitably has to specify and leverage the functional structure the classifier in use to reduce the required computation.
Exact certificates. The exact certificate of deep networks is typically derived for the networks with a piecewise linear activation function such as ReLU. Such networks have an equivalent mixed integer linear representation (Cheng et al.] 2017 Lomuscio & Maganti 2017: Dutta et al.) 2017 Bunel et al. 2018). Hence, one may apply mixed integer linear programming to find the worst case adversary within any convex polyhedron such an balll or -all. Despite the elegant solution, the complexity is, in general, NP-hard and the algorithms are not scalable to large problems Tjeng al. 2017).
2

---

Under review as a conference paper at ICLR 2020
Conservative certificates. A conservative certificate can be more scalable than the exact methods, since one can trade-off the accuracy of certification with efficiency (Gouk et al. 2018 Tsuzuuu et al. 2018 Cisse al. 2017 Anil et al. 2018 Hein & Andriushchennko 2017). For example, one can relax the search of the worst case adversary as simpler optimization problem that only bounds the effect of such adversary. Alternatively, people also consider the robustness problem in modular way, where the robustness guarantee can be derived iteratively for each layer in the deep networks by considering the feasible values for each hidden layer (Gowal et al. 2018 Weng et al. 2018 Zhang et al. 2018 Mirman et al. 2018; Singh et al., 2018). However, this line of works have not yet been demonstrated to be feasible to realistic networks in high dimensional problems like ImageNet.
Randomized smoothing. Randomized smoothing has been proved to be closely related to robust-
ness. Although similar techniques have been tried by (Liu et al. 2018 Cao & Gongg 2017), no corresponding proofs have been given: [ivenn:Liie et al. (2018) Cnden et al. (2019) have proved certified robustness of E norm under isotropic Gaussian noise, and al. (2019) proved robustness for to form. Lecuyer al. (019)) use techniques from differential privacy to prove E robustness under Gaussian and Laplace noise respectively, but the bounds are not tight. Li et al. (2018); Pinot et al.) 2019) use Rényi divergence framework without tightness proof. Our results synthesize the ideas in Cohen et al.] [019;] Lee et al.] 2019;; Lecuyer et al.) 2019: Li et al.) (0018) [Pioot et al. 2019) and prove the tight robustness radius under the binary classification setting.
3 PRELIMINARIES
Definition 1 (Laplace distribution) Given À E IRt, d E Z+, we use L(()) to denote the Laplace distribution in dimension d with parameter X. The p.d.f. of L(A) is denoted Lix; X) &
(2X)a exp( [1=]la)
As we will see in Lemma 3.1 in smoothing analysis, we are interested in the likelihood ratio of two random variables X e and = 5 + e (here ~ ((A) and E Rd a fixed vector). Specifically,
py px exp (- 81|1 - -
px (x)
Therefore, the likelihood ratio between two d dimensional random variables is controlled by a one dimensional random variable T(x) & xx - 51/, ||æ]||,, where x ~ L()). This transformation is erucial in analysis, and it is easy to see that T(x) is mixed random variable, since P Px (T (| > 0.
In our analysis, we need calculate the inverse of c.d.f. of T(x). However, since T(x) is mixed random variable, sometimes the inverse may not exist. See Figure 3 for illustration, where the inverse of the probability 0.85 does not exist. To deal with this case, we have the following modified version of Neyman-Pearse Pearson Lemma, with the proof in Appendix A
Lemma 3.1 (Neyman-Pearson Lemma for mixed random variables). Let X ~ ( and Y ~ (A) + 8. Let h Rd {0, 1} be any deterministic or random function. Given any B R, and S' C E Rd 122- 1211 || B):
1. If (2 Rd : 1|z--6] 811, ||||| > 3] US and P(h(X) 1) 2 P(X S) then P(h(Y)-
1) S)
2. 2 f= Rd || -==- 811 |=||1 < B US, and ((N(X) = 1) < P( E S), then P(L(Y) P(Y E S)
4 MAIN RESULTS
In this paper, we apply the randomized smoothing technique (Cohen et al. 2019) for getting robustness certificates, which works as follows. Given an input x, we perturb it with e, s.t. (()). Then instead of evaluating the robustness of the original function f(x), we evaluate g(m) A arg max, (f + e) = c), which is effectively the smoothed version of f(x:).
3

---

Under review as a conference paper at ICLR 2020
044
Improvement
0.5
0.2
6.1
1
2
0.5
0.6
0.7 0.8
X
P
Figure For mixed random variables, some- times the inverse of the probability does not ex- ist. E.g., see the solid blue line.
Figure 4: Comparison for Eqn. Green re- gion shows that baseline is better, while red re- gion shows our new bound is better.
4.1 ROBUSTNESS CERTIFICATES FOR GENERAL CASES
Our first theorem proves that for the smoothed classifier 9, and given input there always exists a robust radius R, such that any perturbation s.t. ||ô|| S R, does not alter the prediction of g(æ).
Theorem
Let f Rd Y be deterministic random function, and let L(A). Let g(w)
arg max, P. (f(
c). Suppose PA, PB 10,1] such that
PP [[ = ca) 2 PA 2 PB 2 max P(f(x +
cFCA
Then g(x + = || S R, where
max log Log(PA/PP) -AloP)))
-Alog(1 - PA + PB)
(I)
Some Remarks:
1. When PA + or PB - O, we can get R - x.. It is reasonable since the Laplace
distribution is supported over Rd. PA is equivalent
almost everywhere.
2. Compared with (Lecuyer et al. 2019 where they have R log( PAPPPAPP PBB). our bound
is better if (--PA(1-PA)--) (1 < PB 1-2PA P 1PA PA) See
2P4
2P
Figure 4 for illustration, where
baseline denote the bound R log (PA (og(PA/P)) Pn).
Proof sketch: (The full proof is in Appendix B For arbitrarily classifier f. we can transform it into random smoothing classifier y using random smoothing technique, where g returns class ca with probability no less than PA. and class eg with probability no more than PB. Below we list the three main ideas we used our proof:
1. How to deal with an arbitrary f with PA and PB?
Following Cohen et al. (2019),
Sermmnn-Pearson Lemma transform the relation between ((f(X) CA) and P(J(Y CA) into the relation between P(X A) and P(Y E A). From Lemma 3.1 Neyman Pearson Lemma still holds for mixed random variables.
2. How to deal with the relation between X = and Y = = 8?
Inspired by Lecuyer al. (2019), we use the DP-form inequality (P(Y E A) P E A)) to deal with the relation between P(X E A) and P(Y e A). In Laplace distribution, < [|8|]
Take complements get tighter bound.
When PA < 1/2, the above DP-form inequality gets tighter. Therefore, we analyze A when PA 1/2 to get bound, and compare it with the baseline expression.
We derive this bound by Soyman-Pearsonn Lemma in this work, but an alternative approach using Rényi Divergence (L. et al. 2018).

---

Under review as a conference paper at ICLR 2020
4.2 TIGHT ROBUSTNESS CERTIFICATES FOR BINARY CASE
Although we gel improved result over Lecuyer et al. (019)) the bound in Theorem i is not tight since it considers the general case with multiple categories. In this section, we first present result for binary classification (Theorem 2) which further improves over Theorem
Theorem 2 (binary case) Let f R + Y be deterministic or random function, and let C()). Let (xx) = arg max, Pe(f(x + E) = c). Suppose there are only two classes Ca and cB. and PA 2 s.L.
( + +) caa 2 PA
Then g(x +) -) v|ol1 & for
R = - - PA)l
(2)
Scretch of the proof: (The full proof is in Appendix C Theorem is special binary case of Theorem [ We can use method similar to Theorem to get the results. However, is worth noting that in binary cases, our new improved bound in Theorem aaaway dominates the bound by Lecuyer et al. (2019). Moreover, our bound Eqn. (2 is tight, as shown below.
Theorem (tight bound in binary case) In the same setting as Theorem 2 assume PA + PB < and PA 2 1. AR' -Xlog]2(1 PA)]. 3 base classifier f and perturbation 8* with g (x) arg max, P. cc) = and |ō|| R', s.t. g" (x:) + g" 8*).
Scretch of the (The full proof is in Appendix C) For Theorem 3 prove that the bound in Theorem is tight by calculating the results in one-dimensional case, where ō = ([ol||,, O, .)....
By caleulating, show that when 8 (116 .,..,
||8]] + lox(2PB]
[ dx
P(Y B)
2A exp
exp( [18]]]
PP
when ||01/ S -Xlog|2Pp
8 111
exp(
O.W.
Therefore, when ||ō]] one-dimension case.
Alog|2PB] the DP-inequality is tight. The worst-case appears in the
P/Y
Robustress Radius
Lecuyer at Cohen etal.s
-0.5
0.5
-1
P
Figure 5: When d is small, we will take the red part to construct P(X E B), and blue part to construct P(Y E B). The difference between them meets the condition that T(x) = - ||1|1 which leads tight bound.
Figure 6: Comparing different methods un- der different PA- Our model always gives the largest radius compared with the other models, because our bound tight.
Figure shows the reason why the inequality is tight. When ò is small, for P(X E B), the set B we selected satisfies Vz E B, T(x) -1001 (red part). When P(Y B) is considered, it moves set towards left by step 8. However, due to the small 8, S after moving still satisfies the requirement of Va E S, T(x) -|00% (blue part). Therefore, the inequality is tight.
5

---

Under review as a conference paper at ICLR 2020
4.3 METHOD COMPARISON
We compared our method with Cohen et al.'s and Lecuyer et al.'s in binary case, see Table [ We plot the curves in Figure 6 As we can see, under the variance of each noise, our method can reach better robustness radius. Below we show simple derivations of the bounds in Table T
Table Robustness Radius Comparison
Method
Noise
Radius
Our
Laplace L(O, X) X log (2(1 PA)
Lecuyer et al.'s
Laplace L(O,
log PA/L 2//1= 10-PA. PA)
Cohen et al.'s
Gaussian (0,
o (PA)
Robustness radius of Lecuyer et al. (2019)
Using the basic inequality from differential privacy, have:
(f(x) CA) I exp(3)P (f(Y) CA)
IP (J(Y) cB) < exp(3)P (f(X) cB)
where B ||0|1/A. The above two inequalities show that to guarantee P (J((Y = =CA) >
(f((Y) = CB ). it suffices to show that:
(f((X) = cA) > exp(28)P (f(X) = cB)
So plug in / we have || S (Pg PB). Furthermore, in binary case, we can plug in PA = 1 - PA. and get the robustness radius: R = log Pa/1 - PA).
Robustness radius Cohen et al. (2019)
Denote (c) fx || - clpp I r). Since we know that (c) C (2,r(c), so the radius in Cohen et al. 2019) can be directly used & form, which is oth (PA).
Besides, since (e(c) of (2,r(c) whatever > 0 is. And (Cohen et al. 2019) is exact robust- ness guarantce, so we have that the best & form that isotropic Gaussian noise random smoothing can get is σ 1 (PA).
PA). For simple denotion, we just set PA = p 2 0.5. So it is sufficient to show that - log 22 - p)] 2 à log(p/(1 - -p)) By applying exponential operation, it suffices to show that 2(1-p)
Finally we will prove that AXlog|2 PA)l 2 log(
2
1 2 V 1-p' which simply p(1 p) S }.
p
EXPERIMENTS
5.1 IMPLEMENTATION DETAILS
Monte Carlo. Since we cannot get the exact value of PA. we have to use Monte Carlo method to get the approximate value of PA- More specifically, we take multiple random samples from the Laplace distribution to estimate PA- One way to do it is grouping the samples and get PA using non-parametric estimation.
In our experiments, we applied two different types of training, described below.
The first method is intuitive, and was applied in (Cohen al. 2019). In the training process, we add into inputs:
inputs inputs + noise
where the noise sampled from isotropic Laplace distribution.
Type2-Training:
The second method was recently proposed by Salman et al. (019)) The idea is to use adversarial noise samples instead of the raw noise samples neighborhood to train the base classifier. Each training sample can be decomposed to
inputs inputs + noise + perturbation

---

Under review as a conference paper at ICLR 2020
where the noise comes from an isotropic Laplace distribution, and the perturbation is found approx- imately by the gradient of loss with respect to the input. Concretely, we denote the loss as L and the imput x, the perturbation A can be calculated by A sign V L(0, z, y)), where is constant.
Evaluation Index. In this paper, we choose certified accuracy certified accuracy at radius r refers to the proportion of correctly classified samples with at least robustness radius r. Specifically, if group of samples with capacity is { 1,2,................. 2.,,,.... n, its corresponding certified robustness radius is Ra. An index I; represent if the sample is classified correctly. If the sample is correctly classified, 2; = 1, otherwise Ie corresponding robustness certified accuracy is defined as = Ei=1 (R, 2 r)/n, where 1(-) is an indicator function.
evaluation index. Robustness
For given r, the
However, from Section 5.1 we know that we cannot calculate the exact robustness radius R, so we use its R to approximate R, which leads to "approximate robustness certified accuracy"(()) which is calculated by
à Iel(ARe 2 r)/n
Cohen et al. (2019) demonstrates that when significance level of Å is small, the difference between these two quantities negligible. In practice, we plot approximate certified accuracy & function of radius r. From Eqn. (3 we know that à is non-increasing w.r.t. r. And when r + co, â + 0.
Hyperparameters. In our paper, we set all hyperparameters following Cohen al. 2019), Specifically, we set significance level to 0.001. nn = 100 in Monte Carlo simulation (used to get bound for à) and n = 100, 000 in estimation part (used to estimate å). Moreover, we test three parameters in CIFAR-I0 dataset and ImageNet dataset (a = 0.25, 0.50, 1.00), Since (Cohen et al.) 2019) use Gaussian noise and we use Laplace noise, they should have the same standard deviation during comparison. This requires that 22X.
5.2 EXPERIMENTAL RESULTS
Results on ImageNet and CIFAR-10. We applied random smoothing on CIFAR-10 (Krizheskky (2009) and ImageNet (Deng al. (2009) respectively. On each data set, we trained several random smoothing models with differential standard deviation for Laplace noise. In order to keep in line with Cohen et al.'s method and make a comparison, we select a 0.25, 0.50, 1.00 on CIFAR-10, and ImageNet, corresponding parameter À =/V2..
Figure 6 draws the certified accuracy achieved by smoothing with each sigma. For the ImageNet dataset, we only use the most basic training method (Typel Training). For the CIFAR- 10 data set, we use two training methods (Type and Type 2 Training). We can see that the smaller sigma performs better when the radius is smaller. As the noise gets bigger, the accuracy becomes lower, but the robustness guarantee becomes higher. The dashed black line shows the empirical robust accuracy of an undefended classifier from Cohen et al. 2019).
0.12
0.25
a 0.25
a 0.25
= 0.50 undefended
0.50
0.50
3.6
1.00
8.4
1.00
0.6
undefended
undefended
corciled
0.4
0.4
0.2
69
radiuts
radius
radios
(a) Cifar(Typell)
(b) Cyfar(Type2)
(c) ImageNet
Figure 6: Approximate certified accuracy on CIFAR-I0 and ImageNet.
Comparison with baseline.
7

---

Under review as a conference paper at ICLR 2020
We will show comparison results in the following. Based Table. will test our method on CIFAR-10 10 with the ResNetl 10 architecture as well as Type1 and Type2 training, and ImageNet with well as Type1 training. We will compare results with (Cohen et al. 2019) and eeuuee et al. 2019) under the same standard deviation a. For base classifiers, ours and Lecuyer et al.'s share the same base classifier with Laplace training noise, and Cohen et al.'s uses the base classifier with Gaussian training noise.
ResNet50 architecture
Ours, typel
Ours, typel
Ours, typel
Lecuyer et typel
Lecuyer et typel
Lecuyer et type]
Lacuyer et type?
corthed
Lacuyer et type?
Lacuyer type2
Cohen
certieed
3.8
68
0.3
radius
radius
radius
(a) 0.25
(b) 0.50
(c) 1.00
Figure 7: Approximate certified accuracy attained by randomized smoothing on CIFAR-10. 10.
3.0
3.8
3.3
Ours
Ours
Ours
2.8
0.8
0.8
Lecuyer et
contrcedaccurrr
Lecuyer et al
Lecuyer et al
contees
8.6
0.6
0.4
0.4
(a)
0.25
(b)
0.50
(c) 1.00
Figure 8: Approximate certified accuracy attained by randomized smoothing ImageNet.
CONCLUSION
In this paper, we combine the inequality from differential privacy and the classic Neyman-Pearson Lemma to resolve the challenging asymmetry of f metric and the mixed discrete-continuous prop- erty of the likelihood ratios under isotropic Laplace distributions. In addition, by comparing the high-dimennsonal case with a special edge case, we prove the tight é robustness guarantec for binary classification problems, and obtain the state-of-the-art certified accuracy large scale experiments.
The establishment of & certificate via Laplace distributions and the prior result of la certificate via Gaussian distributions may be extended certificate via the associated realization of the generalized Gaussian distribution, where the afore- mentioned results are special cases of the general scheme. The introduction of the mixed random variable analysis and lp geometry analysis may serve valuable extension of existing works towards such general goal.
generic theorem for general E, norm robustness
REFERENCES
Cem Anil, James Lucas, and Roger B Grosse. Sorting out lipschitz function approximation. arXiv: Learning, 2018
Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Gesa-Bianchi. and Roman Garnett (eds.). Advances in Neural Information Processing Systems 31: Annual Con- ference on Neural Information Processing Systems 2018, NeurlPS 2018, 3-8 December 2018,
8

---

Under review as a conference paper at ICLR 2020
Montréal, Canada, 2018. URL http://papers.niig httpp//p..//ooooo////aaeeee----a
Rudy Bunel, Ilker Turkaslan, Philip H. S. Torr, Pushmeet Kohli, and Pawan Kumar Mudigonda. A
unified view of piecewise linear neural network verification. In Bengio et al. (2018), pp- 4795- httpaappwrs..nisssccppaaeeeeeeee cewise- linear- wew.aaan-neeeeeaaaaaaaeeeee---ee
4804. URL
a uni f fied view wwwwwwwfoooo of pip
Xiaoyu Cao and Neil Zhenqiang Gong, Mitigating evasion attacks deep neural networks via region-based classification. In Proceedings of the 33rd Annual Computer Security Applications
Conference, Orlando, FL. USA, December 4-8, 2017, pp. 278-287. ACM, 2017. ISBN 978- 144503-335-8. doi: 10. 10.1145/31
URL https: //cp::://cc...o org /o. 1145/
$134600 34666
Chih- Chih-Hong Cheng, Georg Nührenberg, and Harald Ruess. Maximum resilience of artificial neu- ral networks. In Deepak D' D'Suz and K. Narayan Kumar (eds.), Automated Technology for Verification and Analysis 15th International Symposium, ATVA 2017, Pune, India, October 3-6, 2017, Proceedings, volume 10482 of Lecture Notes in Computer Science, pp. 251-268. 000007/9788-311-688811
Springer, 2017. ISBN 978-3-319-68166-35 https::/dot waa.li.org//00 1007 3-11---8-33--111-------------
doi:
18. URL
Moustapha Cisse, Piotr Bojanowski, Edouard Grave, Yann N Dauphin, and Nicolas Usunier. Parse- val networks: Improving robustness to adversarial examples. arXiv: Machine Learning, 2017.
Jeremy M Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized
smoothing. international conference on machine learning, 2019.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Fei-Fei Li. Imagenet: A large-scale hierarchical image database. In 2009 IEEE Computer Society Conference on Computer Vision and Pottern Recognition (CVPR 2009), 20-25 June 2009, Miami, Florida, USA, pp. 248-255. IEEE Computer Society, 2009. ISBN 978 1 4244 3992-8 doi: 10.1 2.1109CCVRR..2099526666
URL https://doli www.oorg/.ooo...ooo 1109/ CVPRW. 2009. 5206848
Souradeep Dutta, Susmit Jha, Sriram Sankaranarayanan, and Ashish Tiwari. Output range analysis for deep neural networks. arXiv: Learning, 2017.
Chris Finlay, Aram-Alexandee Pooladian, and Adam M Oberman. The logbarrier adversarial attack: making effective use decision boundary information. arXiv preprint arXiv: 10396, 2019.
Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. international conference on learning representations, 2015.
Henry Gouk, Eibe Frank, Bernhard Pfahringer, and Michael J Cree. Regularisation of neural net-
works by enforcing lipschitz continuity. arXiv: Machine Learning, 2018.
Sven Gowal, Krishnamurthy Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Ue- sato, Relja Arandjelovic, Timothy A Mann, and Pushmeet Kohli. On the effectiveness of interval bound propagation for training verifiably robust models. arXiv: Learning, 2018
Matthias Hein and Maksym Andriushchenko. Formal guarantees on the robustness of a classifier against adversarial manipulation. arXiv: Learning, 2017.
Alex Krizhevsky. Learning multiple layers of features from tiny images. In Technical report, 2009.
Mathias Lecuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified robustness to adversarial examples with differential privacy. ieee symposium security and privacy, 2019.
Guang-He Lee, Yang Yuan, Shiyu Chang, and Tommi S. Jaakkola. A stratified approach to robust- ness for randomly smoothed classifiers. In Advances in neural information processing systems, 2019.
Bai Li, Changyou Chen, Wenlin Wang, and Lawrence Carin. Second-order adversarial attack and certifiable robustness. arXiv: Learning, 2018.

---

Under review as a conference paper at ICLR 2020
Xuanqing Liu, Minhao Cheng, Huan Zhang, and Cho-Jui Hsich. Towards robust neural networks via random self-ensemble. In Vittorio Ferrari, Martial Hebert, Cristian Sminchisescu, and Yair Weiss (eds.), Computer Vision ECCV 2018 15th European Conference, Munich, Germany, September 8-14, 2018, Proceedings, Part VII, volume 1 1121 of Lecture Notes in Computer Science, pp. 381- 191- 397. Springer, 2018 ISBN 978-3-030-0123333 233-5. doi:
23. URL]
https://doi.com //:::///o....
030 01234-22-2 2
Alessio Lomuscio and Lalit Maganti. An approach to reachability analysis for feed-forward relu neural networks. arXiv: Artificial Intelligence, 2017.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. To- wards deep learning models resistant to adversarial attacks. international conference on learning representations, 2018.
Matthew Mirman, Timon Gehr, and Martin T. Vechev. Differentiable abstract interpretation for provably robust neural networks. In Jennifer G. Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning. ICML 2018, Stockholmsmüsssan, Stockholm, Sweden, July 10-15, 2018. volume 80 of Proceedings of Machine Learning Research, pp. 3575- 3583. PMLR, 2018. URL http: http://proceeddnggs mlr prw.sresss/seeeec v80 v800mi0mmmmmmmmmm rman 8b. htm
Rafael Pinot, Laurent Meunier, Alexandre Araujo, Hisashi Kashima, Florian Yger, Cédric Gouy- Pailler, and Jamal Atif. Theoretical evidence for adversarial robustness through randomization: the case of the exponential family. CoRR, abs/1902.01148, 2019. URL http:
g/ alabs/ 190//1902.00 01148
Hadi Salman, Greg Yang. Jerry Li, Pengchuan Zhang, Huan Zhang, llya Razenshteyn, and Sebastien Bubeck. Provably robust deep learning via adversarially trained smoothed classifiers. arXiv preprint 1906::9906.04555 2019.
Gagandeep Singh, Timon Gehr, Matthew Mirman, Markus Püschel, and Martin T. Vechev. Fast and effective robustness certification. In Bengio et al. (2018), pp. 10825-10836.
URL http: nips. wwwps.ccppppp.......peppppppppee 8278-2888888 -ndes---n--fffetiveeee robustn cas-ceerfiicaiioo.
Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian J Good- fellow, and Rob Fergus. Intriguing properties of neural networks. international conference on learning representations, 2014.
Vincent Tjeng, Kai Y Xiao, and Russ Tedrake. Evaluating robustness of neural networks with mixed integer programming. arXiv: Learning, 2017.
Yusuke Tsuzuku, Issei Sato, and Masashi Sugiyama. Lipschitz-margin training: Scalable certifica- tion of perturbation invariance for deep neural networks. In Bengio et al. (2018), pp. 6542-6551.
URL
http: httpa//aaaaaaaaaooaaa/aaaaaaaaaa
sca
eural -utao-networs
Bao Wang, Binjie Yuan, Zuoqiang Shi, and Stanley J. Osher. Enresnet: Resnet ensemble via the feynman-kac formalism. CoRR, abs/1811.10744 2018. URL http://arxiv.org/aat
181 1B11.100 10745
Tsuiwei Weng, Huan Zhang, Hongge Chen, Zhao Song, Chojui Hsieh, Duane S Boning, Inderjit S Dhillon, and Luca Daniel. Towards fast computation of certified robustness for relu networks. arXiv: Machine Learning. 2018.
Huan Zhang, Tsui-Wei Weng, Pin-Yu Chen, Cho-Jui Hsieh, and Luca Daniel. Efficient neural net- work robustness certification with general activation functions. In Bengio et 2018)) pp. 4944 4953.
nips wttpppppsw.pppppppaaaaaeeeeeeiie wwwpiieett-uuua-n-eeee rk robuuutneessss.. www.teeettttiioooo with general -at.eerraaactivaiio........ aetivatioon-unntioon functions
activation.
Stephan Zheng, Yang Song, Thomas Leung, and lan J Goodfellow. Improving the robustness of deep neural networks via stability training. computer vision and pattern recognition, pp. 4480- 2016.
10

---

Under review as a conference paper at ICLR 2020
A PROOF OF LEMMA 1
In this section, we will prove that Neyman-Pearson Lemma holds with mixed random variable.
WLOG, 0, X L (A) and Y L (A) 6. We will firstly introduce Neyman-Pearser Lemma, which plays an important role in our proof.
Lemma 3.1
(restated). X L (A) and Y f (A) Leth Rd {0, 1} be any deterministic
random function. Given any B E R, and 5' _ { E Rd || 8||1 ||=||= B):
If {=ER* 1) 2 PPY E)
81[1 ||||1 B} US" and P(h(X) 1) 2 P(X S) then P(N(Y)
2. I = f
: 8111 - 1 < US and ((h(X) = 1) - ( E S), then P(h(Y) =
1) S PS
Proof of Lemma 3./ First, notice that P(X S) can be regarded mixed random variable.
We want to prove that as long as we can choose a 5' that satisfies P(X E S) & P(h(X) = 1), Neyman-Pearson Lemma can always hold.
Let's first see what happens in the proof of Neyman-Pearson Lemma. Notice that X and Y are continuous variables, but X and Y E S can be regarded mixed continuous-discrte event. Then we can choose a reasonable S' for X and Y. We will prove case and the other one can be proved with similar method.
P()(Y) 1) P(Y E)
h(1)2)ar(3)dz -
ux(2)dz
Rd
h(11)))r(2))) + ge -1 -1f.
s h(1)z)px(z)dz)) 1/ h(1zz)px(2)dz++ I ((0)2))x(()dd))
h(1)=)ux(z)dd
h(0)))x((xdd
2t( S:
4(11=)xx(()) (z)dz
h(0)z))x(2)dz)
[1(12))xxxx)d) 1/ h(00))xx)))x++ / h(112))x(2)dd))
=1(
h(1l=)px(( +
=((P(((X) = 1) - P(X E S))
20
(x The first inequality holds due to the construction of mixed definition S. If x S, #x(=) 2 If t. Compared with continuous set, the only difference appears in the equal sign.
St.
(x) (x(x)
should be noted that P(X E S) and P(Y E 5) should keep consistent, which means that they should have the same S'. In this derivation, can find that P(X S)) and P(Y E SS) use the same set S" in Eqn.
Next, we will plug in the condition that X and isotropic Laplaces.
Then we just need to prove that
z E Rd pY(2) (x(x) _ (ZER": 5112 11112 }}}
When X and Y are isotropic Laplaces, the likelihood ratio turns out to be:
(2) exp( + |= 0111)
px(=) expl (xp(-++1=1111) x111111)
= =cxp(- [||= - -8112 - -11=|1))))
11

---

Under review as a conference paper at ICLR 2020
By choosing -Alog(t), we can derive that
(z)
|| 8||1
--||=|1
St
(x
nz
| 8||1 |=|||
3
21
(x
B PROOF OF THEOREM
Theorem ((restated) Let Rd Y be deterministic random function, and let L()). Let g(x) = arg max, P. (f( + e) c). Suppose PA, [o, 1] are such that
PP (f + +) ca) 2 Pn 2 max P( [a(++e)]) +
c#cA
Then g(x + 8) g(x), 61 < R. where
A log PA PB)P -Alog(1 PA + PB)
R max
(5)
2
Proof of Theorem bound for Tx)):
7
Denote T(x)
|| 8|11 ||]||| Use Triangle Inequality we can derive
-|61| S (())) S ||,||
(6)
Pick 31, B2 such that there exists A' C (z: =(=)= B C (2: B2). and
P(X E {2 :(z) > {) & P(f(X) = ca))
P(X E (z T(2) < P 2 P(f(X) = CB)
Define
A: (x: U
:: (x:T(z) < UB'
Thus, apply Lemma
3.1
we have
P(Y A) s P((()) CA) P(Y B) 2 P(f(Y) = CB)
Then consider P(Y A) and P(Y B)
# 8111 )dx
P(Y E A) =
[2X] exp(
A
= / [2A]_ exp(
|
T(x)
A exp(
dx
X
(8)
|1011
||=011
2 exp(
[2X]
exp(
ddx
X
|1ō|1
exp(
PP
The inequality is derived by Eqn. 6
Similarly, we can get
1 8111
P(Y B)
[2A] d exp(
dx
A
|2 eex(( T(x) dxx
[2A]
exp(
||8111,
/ [2A]]
|201| )xx
< expl
"exp(-
X
||0||1
exp(
}P
A
12

---

Under review as a conference paper at ICLR 2020
First, would like to show that robustness can be guaranteed when R 2/2 Log(Pa/PB). || S 2 log(Pa/PP)) by Eqn. 7 we have
P(f(Y) ca) 2 P(Y E A) 2
P((()) = cB)
Then, would like show that robustness can be guaranteed when R S -X -PA+PB))
From Eqn. (9) we know that P(Y E B) v exp( 1111 Pn. Besides, by applying Eqn. (9) in set A we can get that P(Y E A) 2 1 - exp( )(1 Pa). So we can calculate that if ||0| S
-X loog PA + PB). we have
P(J()) ca) P(Y A) 2 P(Y E B) P(S(Y) CB)
Moreover, by simple algebraic operation, derive that- À log PA PB) 1- PA
1/ log PA PB)
1-2Pa Pa)
-1 < PB
PP PA)
requires
2P'
21a
The proof for Theorem is finished.
C PROOF OF THEOREM 2 AND THEOREM
Theorem 2(restated) (binary case) Let ʃ IRd + Y be deterministic or random function, and let (()). Let g(x) = arg max, P. Pf(f(x + E) = c). Suppose there are only two classes Ca and cp.
and PA E 12 s.t.
P( + 6) = ca) 2 PA
Then g(x + 8) g(x), 1l
R, for
R logg(221 PA))
(10)
Proof of Theorem
It is similar to the proof of Theorem
Pick B3 such that there exists B' C (2: T(2) f3), and
P(X E (z T(z) < 8z) UB) Pn = P((()=
Define
S S (())
So we also have P(X ES) P = P(S(X) = ca). Plug into Lemma 3.1
we can get
P(Y $ 8) S P(f(Y) cA)
P(Y e 8) 2 P(f(Y) = CB)
Using similar method as Eqn.
9
we can get that
|0||1 PB
P(Y E S) E expl
Since have
PB = P(f(X) = = = PA &
PA
Thus, if || - R- -Xlog/211 - PA)], it holds that
||8|| PPB
P(Y E S) exp(
-X 2(1 PA)
< expl
)11 -PA)
2
13

---

Under review as a conference paper at ICLR 2020
That is to say, P(f(Y) CA) P(Y $ 2 2 P(Y 8) P(f(Y) cg).
The proof for Theorem 2 is finished.
Theorem 3(restated) (tight bound in binary case) In the same setting Theorem 2 assume PA + PB and PA 2 $. VR > lo 2 PA)l. base classifier f and perturbation with g (z) arg max P (f + c) and ||6|| R', s.t. g (a) # g" 8*).
Proof of Theorem Ann define
Here, first set 8 (1 11, ..........) 0). For simplification, we denote ő
A {2: 81 |2| max(ō 2A [2 -PP)) -83}
Then, we can calculate that
P(X E A) = (I - |x| 2 max + 22 loggog/1 -A)l - 88)
A 1og(2(1-Pa)]
| )dr
2X exp
(11)
1
exp
)dx
2X
Alogg221 PA)]
= PA
where x
2X exp (-
|01|
Notice that if 5 + 2A log/2(1 PA)] & -ō, we will get the
integral equation by choosing S With Eqn. 11
we have
P(X E A) = PA S P(J(X)
(12)
Thus, plug Eqn.
(12 into the results of Lem. 3.1 we have
P(Y A) S P(f(Y) = cA)
(13)
Also, since Y X + 5, it can be derived that
P(Y E A) Alog(2(1-Pa)] PP)]- 1
|
2X exp
dx
(14)
Here we use the consistency of X and E A. Since can be regarded as an offset of X, the integral limit should be translated into the same length. So, if || = 3 s -Alog[2(1 PA)), by
Eqn. and Eqn. (14), we have
1 P(f(Y) = P(Y E A) 2 2
This means that the results we get binary case is tight bound, and the worst-case 5 appears when 6 (6. O. ... 0). Furthermore, if slightly enlarge 8, there would be case that the robustness is destroyed.
The proof for Theorem 3 finished.
D WHY LAPLACE NOISE INSTEAD OF GAUSSIAN
In this section, we theoretically analyze the certification capabilities of Gaussian and Laplace noises. We will show that, given the same base classifier f the parameter of Laplace distributions À is less sensitive than the parameter of Gaussian distributions a. Given a base classifier f. where
CA
f(x)
CB
o.w.
14

---

Under review as a conference paper at ICLR 2020
and two random smoothing functions
91 (x) = arg max =)) (),
c
(2(x) = arg max =))
we aim to prove that Laplace noises will better protect the original prediction than Gaussian noises. Formally, we compare their Rectified Optional Parameter Space (ROPS), defined as A {v2A= (x; X) f())} and = for : ge(a;; σ) = fx)). Note that the rectified term v2 is due to the fact that a = v2x yield the same variance. Essentially, ROPS indicates the feasible region where the smoothing distribution does not negatively impact the base classifier, thus measuring the sensitivity of the smoothing distribution (the larger the better).
First, we would like to compare its prediction given point (xx) (0, ca) We have
(0) = CA + P(f(0 + e) = =x)= 1
1
P([e| - 1) = -exp--
-
2
-
2
2
log 2
1
+ P(Id S 1) = 2 - -1 2
1
1
02( = CA = P( = cA)
T (3/4)
Since
v2 log 2
+ (3/4) Laplace noises have a larger ROPS than Gaussian noises at the point x = 0.
The analysis can be further extended in two cases.
First, if we have x * 0, what is the corresponding ROPS that leads to the desired result (g(x) f(x))? We show in Fig. 10 that we will have larger ROPS under Laplace noises.
Second, if we have a fixed x but fixed a desired certified radius, what is the corresponding ROPS? We show in Fig. 11 that Laplace noises again have a larger ROPS.
We empirically validate this finding with ResNetl on CIFAR-10. The resulting smoothed model has 24.8% clean accuracy under Laplace noise, and 73.7% clean accuracy under Gaussian noise (with the same variance as the Laplace noise). Here the accuracy is computed with respect to pre- dictions of the base classifier instead of the labels (to illustrate how the smoothing impacts the predictions).
2.5
sup ROPS implies Σ/A [0. sup ROPS!
sup ROPS implies sup ROPS)
Laplace Gaussian
Laplace
sup ROPS
1.5
ROPS
1.5
Gaussian
0.5
%
0
0.2
0.4
0.5
0.8
0
0.2
0.4
0.6 0.8
Location of
Certified Robusthess Radius
Figure 10: The ROPS under various x. Here sup ROPS), and similarly for A. Laplace noises are less sensitive than Gaussian noises in terms of ROPS.
Figure 11: The ROPS under various certified robustness radii with a fixed x 0.3 (other yields similar results). Laplace noises are less sensitive than Gaussian noises in terms of ROPS.
Σ
15


Reviews:
[{"review_id": "rkgZIzOmqS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "The paper provides a random smoothing technique for L1 perturbation and proves the tightness results for binary classification case. Overall, there are some new results in this paper -- establishing a new certificate bounds for L1 perturbation model. However, I have several concerns about whether this contribution is significant enough: \n\nRandom smoothing has been studied extensively recently and the proof technique in this paper is not so different from previous papers (Cohen et al, Li et al). Also, there were L0 perturbation bounds proposed by (Leet et al). Therefore, although I agree that a tighter certified bound compared to (Lecuyer et al) is new, the paper seems to be a bit incremental. It will be more interesting to see if the proposed technique/theorem can be used for a wider range of norms. \n\nAlso, it may be more interesting to add some discussions about why L1 perturbation is important for image classification (is it more human-imperceptible?)\n\n=======\n\nI have checked the rebuttal and other reviewers' comments. Although there are interesting components in this paper, I do agree that the paper is incremental given that many random smoothing methods have been proposed recently for L2, L_infty norms. Therefore I think this is a borderline case and will be ok with rejection. ", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "rJxnt1oTtB", "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.\n\nThe authors propose a new certified classifier in \\ell_1 norm that is tight. That is to say, upon smoothing a given classifier f with Laplacian noise, a smoothed version of that classifier (probabilistic maximum majority vote) is certified with a radius measured in \\ell_1 norm. The authors show that this bound is tight for binary classifiers. These results are complementary to Cohen et al. results.\n\nMajor comments.\n\n1) The major contribution of this paper is the tightness under the \\ell_1 norm for a binary classifier. I do not find this particularly significant. The question is of what value is such a result other than a mathematical exercise. For instance a good justification that the paper is lacking could be one where authors show that their radius is indeed tighter than all other works. The paper still lacks this (I will elaborate on this later), although, their bounds are indeed tighter than Lecure's et al. Since it is not clear whether or not the new certified smoothed classifier has indeed the largest radius among all other works, then at least a justification for why would one prefer a Laplacian noise of a Gaussian noise. Why is Gaussian smoothing sufficient for this purpose given that we do not know for sure that the radius is larger?  What value/advantages does this add? The authors motivate their work by saying deriving the tightest \\ell_1 is difficult due to the \"asymmetry\"  of the norm. While I do agree on this; however, this is not enough motivation as we we are doing doing abstract maths here.\n\nThe new derived radius is not really comparable to the Gaussian radius with \\ell_2 radius and this is my major concern. By norm equivalence, we have that \\ell_2 \\leq \\ell_1 \\leq \\sqrt{n} \\ell_2 where n is the dimension. That is to say that the radius computed with \\ell_1 is larger than the \\ell_2 in some cases by a square root of dimension. The authors can correct me on this if I'm wrong, but for a fair comparison in worst case sense the radius of Cohen et al. should be scaled by \\sqrt{n}. In such a scenario, it is really difficult to understand when does it make sense to tackle such a smoothing technique as opposed to Gaussian smoothing.\n\nI would not have asked the authors about such a question if the authors derived generic radius under \\ell_p smoothing (which is difficult of course). To this end, I believe since the motivation is not clear nor the results are generic enough, I find the work incremental specifically after noting that the radius can be deduced from the work of Li et al. where the main contribution here is the tightness of the radius for a binary classifier.\n\n\nMoreover, I believe the paper still requires some polishing in terms of writing and presentation.\n\nSome more comments.\n\nI believe the paper can benefit from some rewriting. Here is a list of things the authors can do to improve the paper.\n\n1) Define what M is, page 3 \"and it is easy to see that M is a mixed random variable\". I believe the authors meant T(x).\n2) The figures are hardly readable. For instance, authors can perhaps increase the legend's font size in figures 4. Also the chosen colors are suboptimal (perhaps the line width of the plots) should be increased. \n3) The section below Theorem 3 should be moved up to before Theorem 3 as this discusses the proof of Theorem 2. Once a Theorem is presented, the proof sketch should follow.\n4) Experiments on the undefended classifier has to be in Figures 6  7 and 8.\n5) Lastly, why are comparison between Cohen et. al. and Lecuyer et. al. in Figure 6 inconsistent with Figure 5 of Cohen 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 carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "SklWazkntr", "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": "In this paper, the author derived a tight ell_1, which is not the symmetric norm, robustness certificates under isotropic Laplace distributions. Experimentally, the authors showed that the deep networks smoothed \nby Laplace distributions yield the state-of-the-art certified robustness in ell_1 norm on the CIFAR-10 \nand ImageNet. To find the ell_1 certificate, the authors first identified the tight robustness certificate, for attacking the model in one particular direction, say the first direction. To show that any other perturbation directions cannot lead to a worse result, the authors convert the d dimensional likelihood function into a one-dimensional function, and the authors used relaxation for different perturbations and show that the worst-case result is bounded by the previously identified direction.  However, I have the following concerns about this work:\n\n1. Theoretically, the authors only showed the certificate is tight for binary classification. I would suggest\nthe author change their claim in the abstract.\n\n2. What is M on page 3 which is used without definition after definition 1?\n\n3. Can you give a concrete continuous probability distribution that leads to the scenario in Fig.~3?\n\n4. Can you extend the analysis to a multi-class classification scenario?\n\n5. Besides randomized smoothing on the input images, recently Wang et al showed that randomize the deep nets can\nalso improve the deep nets and they gave it a nice theoretical interpretation. Here is the reference: Bao Wang, Binjie Yuan, Zuoqiang Shi, Stanley J. Osher. ResNets Ensemble via the Feynman-Kac Formalism to Improve Natural and Robust Accuracies, arXiv:1811.10745, NeurIPS, 2019\n\nOverall, since this work is a straightforward integration of some existing work, I think this\npaper lack novelty. Please address the above questions in rebuttal.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}]

Author rebuttal:

Meta-review: After reading the author's response, all the reviewers agree that this paper is an incremental work. The presentation need to be polished before publish.
Decision: Reject