Filling the Soap Bubbles: Efficient Black-Box Adversarial Certification with Non-Gaussian Smoothing
Authors: Dinghuai Zhang*
Mao Ye*
Chengyue Gong*
Zhanxing Zhu
Qiang Liu
Venue:  (2020)
Keywords: Adversarial Certification
Randomized Smoothing
Functional Optimization

Abstract: Randomized classifiers have been shown to provide a promising approach for achieving certified robustness against adversarial attacks in deep learning. However, most existing methods only leverage Gaussian smoothing noise and only work for $\ell_2$ perturbation. We propose a general framework of adversarial certification with non-Gaussian noise and for more general types of attacks, from a unified functional optimization perspective. Our new framework allows us to identify a key trade-off between accuracy and robustness via designing smoothing distributions, helping to design two new families of non-Gaussian smoothing distributions that work more efficiently for $\ell_2$ and $\ell_\infty$ attacks, respectively. Our proposed methods achieve better results than previous works and provide a new perspective on randomized smoothing certification.

Under review as a conference paper at ICLR 2020
FILLING THE SOAP BUBBLES: EFFICIENT BLACK-BOX ADVERSARIAL CERTIFICATION WITH NON-GAUSSIAN SMOOTHING
Anonymous authors Paper under double-blind review
ABSTRACT
Randomized classifiers have been shown to provide promising approach for achieving certified robustness against adversarial attacks deep learning. How- ever, most existing methods only leverage Gaussian smoothing noise and only work for & perturbation. We propose a general framework of adversarial cer- tification with non-Gaussian noise and for more general types of attacks, from a unified variational optimization perspective. Our new framework allows us to identify key trade-off between accuracy and robustness via designing smooth- ing distributions, helping to design two new families non-Gaussian smoothing distributions that work more efficiently for &z and for attacks, respectively. Our proposed methods achieve better results than previous works and provide a new perspective on randomized smoothing certification.
INTRODUCTION
Deep neural networks have achieved state-of-the-art performance on many tasks such image clas- sification (He et al., 2016 Lu et al. 2018) and language modeling (Devlin et al., (2019). Nonethe- less, modern deep learning models have been shown to be highly sensitive to small and adversarially crafted perturbations on the inputs (Goodfellow et al.] 2015), which means a numan-imperceptible changes on inputs could cause the model to make dramatically different predictions. Although many robust training algorithms have been developed to overcome adversarial attacking, most heuristically developed methods can shown to broken by more powerful adversaries eventually, (e.g., (e.g..(Atha- Atta- Iye et al.) 2018: Madry et al.] 2018 Zhang al. 2019 Wang al.) (019). This casts urgent demand for developing robust classifiers with provable worst case guarantees.
One promising approach for certifiably robustness is the recent randomized smoothing method (e.g.. Cohen et al. 2019; Salman et al. 2019 Lee et al. 2019 Li et al. 2019; Lecuyer et al., 2018), which constructs smoothed classifiers with certifiable robustness by introducing noise the inputs. Compared with the other more traditional verification approaches (e.g. Wong & Kolter] 2017 Jordan al. 2019 Dvijotham al., (2018) that exploits special structures of the neural networks (such as the properties of ReLU), the randomized smoothing methods work more flexibly on general black- box classifiers and is shown be more scalable and provide tighter bounds on challenging datasets such as ImageNet (Deng et al. 2009).
However, the existing randomized smoothing methods can only work against & attack, in which the perturbations are allowed within an & ball of certain radius. A stronger type of attack, such as the lo attacks, much more challenging defense and verify due the larger set of perturbations, but is more relevant in practice.
In addition, all the existing randomized smoothing methods use Gaussian noise for smoothing. Al- though appearing to be a natural choice, one of our key observations is that Gaussian distributions in fact a rather sub-optimal choice in high dimensional spaces, even for & attack. This due to counter-intuitive phenomenon in high dimensional spaces (Vershynin) 2018) that almost all of the probability mass of standard Gaussian distribution concentrates around the sphere of radius one (and hence "soap bubble" in the title), instead of the center point (which corresponds the original input). As a result, the variance of the Gaussian noise needs to be sufficiently small to yield good approximation the original classifiers (by squeezing the "soap bubble" towards the center point),

---

Under review as a conference paper at ICLR 2020
which, however, makes it difficult to verify due to the small noise. Further, for the more challenging so attack, Gaussian smoothing provably degenerates in high dimensions.
Our contribution We propose a general framework of adversarial certification using non- Gaussian smoothing noises, based new perspective from variational optimization. Our frame- work re-derives the method of Cohhn et al. (2019) as special case, and is applicable to more general families of non-Gaussian smoothing distributions and more types of attacks beyond &g norm. Im- portantly, our new framework reveals a fundamental trade-off between accuracy and robustness for guiding better choices of smoothing distributions. Leveraging our insight, develop two new fam- ilies of distributions for better certification results on & and &ox attacks, respectively. Efficient com- putational approaches
developed to enable method in practice. Empirical results show that our new framework and smoothing distributions significantly outperform the existing approaches for both lg and lo attacking, on challenging datasets such as CIFAR-10 and ImageNet.
2 RELATED WORKS
Empirical Defenses Since Szegedy et al. (0133) and Goodfellow et al. (015)) many previous works have focused on utilizing small perturbation ò under certain constraint, e.g. in a Ep norm ball, attack a neural network. Adversarial training (Madry et al.] 2018) and its variants (Kannan al.] 2018 Zhang & Wang 2019] ZZhai et al.] (2199) are the most successful defense methods to date, in which the network forced to solve a mini-max game between the defender and attacker with adversarial examples as data augmentation. However, these empirical defense methods are still easy to be broken and cannot provide provable defense.
Certified Defenses Unlike the empirical defense methods, once classifier can guarantee a con- stant classification within local region, it is called robust certificate. Exact certification methods provide the minimal perturbation condition which leads to a different classification result. This line of work focus on deep neural networks with ReLU-like activation that makes the classifier piece-wise linear function. This enables researchers to introduce satisfiability modulo theories (Car- lini et al., 2017 Ehlers 2017) or mix integer linear programming (Cheng et al., 2017: Dutta et al., 2018). Sufficient certification methods take a conservative way and try to bound the Lipschitz con- stant or other information of the network (Jordan et al. 2019 WWng & Kolter 2017 Raghunathan jet al., 22118] Zhang et al., 2018). However, these certification strategies share a drawback that they are not feasible on large-scale scenarios, e.g. large enough practical networks, large enough datasets.
Randomized Smoothing To mitigate this limitation of previous certifiable defenses, improving network robustness via randomness has been recently discussed (Xie et al. 2018 Liu et al. 2018).
In certification community, Lecuyer al. (2018) first introduced randomization with technique in differential privacy. Li et al. (2019) improved their work with bound given by Rényi divergence. In succession. [ohhn et al. (2019) firstly provided a tight bound for arbitrary Gaussian smoothed
classifiers based on previous theorems found by Li & Kuelbs ( (998). Salman et al. (2019 combined the empirical and certification robustness, by applying adversarial training on randomized smoothed
classifiers to achieve a higher certified accuracy. Lee et al. (2019) focused on 6, norm perturbation setting, and proposed a discrete smoothing distribution to beat the Gaussian distribution baseline.
Similar to (Lee et al. (2019), we also focus on finding a suitable distribution to trade-off accuracy and robustness for different types of adversarial attacks, such as &g and Lee.
3 BLACK-BOX CERTIFICATION WITH VARIATIONAL OPTIMIZATION
We start with introducing the background of adversarial certification problem and and randomized smoothing method. We then introduce in Section 3.] our general framework of adversarial cer- tification using non-Gaussian smoothing noises, from a new variational optimization perspective. Our framework includes the method of Cohen al. (219)) special case, and reveals critical trade-off berween accuracy and robustness that provides important guidance for better choices of smoothing distributions in Section 4
2

---

Under review as a conference paper at ICLR 2020
A Adversarial Certification We consider binary classification of predicting binary labels y {0, 1 from feature vectors 2 E R for simplicity. The extension to multi-class cases is straightforward, and is discussed in Appendix() D Assume f²: R - [0, 1] is pre- pre-trained binary classifier (I means the classifier is given), which maps from the feature space Rd to either the class probability in interval [0, 1] or the binary labels in {0, 1]. In the robustmess certification problem, testing data point zo E R4 is given, and one is asked to verify if the classifier outputs the same prediction when we perturb the input æ arbitrarily in B, a given neighborhood of 2o. Specifically, let B be a set of possible perturbation vectors, e.g., B = {ō E R ||ól1, S r) for lp norm with radius If the classifier predicts y 1 on Vo. i.c. (xo) > 1/2, we want to verify if f( + 8) > 1/2 holds for any E B. In this paper, we consider two types of attacks, including the &g attack Beg, def {8 ||0l|2 S r). and the loo attack B def {ō: : ||0]1 I r}. More general lp attack can also be handled by framework but is left future works.
Black-box Certification with Randomness Directly verifying ft heavily relies on the smooth- ness of f3, which has been explored in a series of recent works (Lecuyer et al., 2018 Wong & Kolter, 2017). These methods typically depend on the special structure property (e.g., the use of ReLU units) of ft, and thus can not serve as general purpose algorithms. We are instead interested in black-box verification methods that could work for arbitrary classifiers. One approach to en- able this, as explored in recent works (Cohen al., 2019 Lee al., 2019). to replace fä with a smoothed classifier by convovling with Gaussian noise, and verify the smoothed classifier.
Specifically, assume To is a smoothing distribution with zero mean and bounded variance, e.g., To = -0000 The randomized smoothed classifier is defined by
fr (xo) := Ex~so [x0 + +)]]+
which returns the averaged probability of æo + under the perturbation of wo- Assume we replace the original classifier with fEa then the goal becomes verifying f using its inherent smoothness. Specifically, if f². (mo) > 1/2, we want to verify that fh. (æo + 6) > 1/2 for every
E B, that is,
min f (Iu + 5) min Ez~ro lf + + 5) 1/2. SEB
(1)
SEB
In this case, is sufficient to obtain guaranteed lower bound of minses f (mo + 6) and check is larger than 1/2. When To is Gaussian No, o²) and for lg attack, this problem was studied in Cohen et al. (2019), which shows that lower bound of
min E Eg- E + =)] 2 ( (ao) - r/a), zEB
where (-)) is the cumulative density function (CDF) of standard Gaussian distribution, and o (.) represents its inverse function. The proof of this result in Cohen al. (2019) uses Neyman- Pearson lemma (Li & Kuelbs] [1998). while in the following section another derivation using variational optimization is provided.
Note that the bound in Equation ( is tractable since it only requires to evaluate the smoothed clas- sifier fi (mo) at the original image 2o, instead of solving the difficult adversarial optimization over perturbation z in Equation (1). In practice, fi, (zo) is approximated by Monte Carlo approximation with noy-asympo confidence bound.
3.1 VARIATIONAL ADVERSARIAL CERTIFICATION
We propose variational adversarial certification (AVC) framework, which yields a guaranteed lower bound for Equation (T) based on variational optimization. The main idea is simple: assume F is a function class which is known to include ft, then the following optimization immediately yields a guaranteed lower bound,
min f (xo 8) > min min fno (No + 8) BEB
s.t. fro (xo f% (300
fer BEB
where we define fra (xn) = Ef + 2)] for any f. and search for the minimum value of Sro (mr + 5) for all classifiers in F and satisfies Szo (mo) = fī (mo). This obviously yields lower
3

---

Under review as a conference paper at ICLR 2020
bound once f F. If F includes only f², then the bound is exact, but is computationally pro- hibitive due to the difficulty of optimizing 6. The idea is then to choose F properly to incorporate rich information of fe, while allowing to calculate the lower bound in Equation (3 computation- ally tractably. In this paper, we consider the set of all functions bounded in [0, 1]. that is,
Fi0.11 = {s f())) [0, E R
(4)
which guarantees include f² by definition. There are other JF that also yields computationally tractable bounds, including the Ipp space F = [f: Ilfll,, S v), which we leave for future work.
Denote by V (F, the lower bound in Equation (3). We can rewrite it into the following minimax form using the Lagrangian function,
((f.8.A) def fro (xo + +5 X(foo - (zoo)
To (F, B) min min max
FEF BEB XER
where À is the Lagrangian multiplier. Exchanging the min and max yields the following dual form. Theorem 1. 1) (Dual Form) Denote by T the distribution of 2 + ô when z wo. Assume F and B compact set. We have the following dual form V (F,B) via strong duality:
\ (200) - max Dy (ATO || m (5)
V (F, 2
max min min L(S,8,)) X20 fEF DEB
-nax X20
BEB
where we define
Dy (ATO m8) max {AE feF
[f + +z)] = [f(2o + z)]}
which measures the difference of Amo and n by seeking the maximum discrepancy of the expectation for I E F. As we show later, the bound in (5) is compulationally tractable with proper (F, B, mo).
II) When F F(o.1) == {s= [(x) E [0, 1),
RRd), we have in particular
BF (ATO ll TT)) / (ATO(Z) - TT(2)) dz, where (1)+ = max(0, 1).
In addition, we have S DF (ATTO TT) s for any To, w8 and Di (Aro || m8) coincides with the total variation distance between To and ws when X =
Note that
III) Suppose Fio11) and suppose that for any minjeT L 8*, N), for some 8 E BB we have
z 0, minsgs minseFo.. L (f.5,A)
VT (F,B) = max max min L (f,
A20 BEB FEF
Remark We will show later that the proposed methods and the cases we study satisfy the condition in part IIII of the theorem and thus all the lower bounds of the proposed method are tight.
First, observe that the constraint in Equation (3) can be equivalently replaced by an inequality constraint fno (2a) 2 f², (zo). Therefore, the Lagrangian multiplier can be restricted to be 2 0. We have
Proof.
VFFBB) min min max E,, (xx + =)] + (ft, (xo) Exo Ix + =)])
8EB JEF X
max min min E,, [x + =)] + > (ft (x:) Exo (2 + z)]) Mexchange min and max
X BEB JEF
max min X 8EB
A/2 (mr) (aro)
+ min E [ (ar + +z) AE (5 2)]} JEF
max min {Xf (ma) DD nT)}
A20 SEB
The proof of the strong duality is in Appendix
A.1 II) follows straightforward calculation.
4

---

Under review as a conference paper at ICLR 2020
Although the lower bound in Equation ( still involves an optimization on ô and X. both of them much easier than the original adversarial optimization in Equation (T). With proper choices of F, B
and To. the optimization of ô can be shown to provide simple closed form solutions by exploiting the symmetry of B, and the optimization of À is a very simple one-dimensional searching problem. As corollary of Thhorem [
can exactly recover the bound derived by byCChhen et et. 2019).
Corollary 1. With isotropic Gaussian noise =N(0, Laxx)) l2 attack B = {ō: 6 S r
and F Fl..1) the lower bound Equation (5) equals the bound in Equation (2) by Cohen et al. (2019) that is,
25 (zo)
(3o)
max Di (AmollmT) ( ( (fo)(x))) r/o).
max X20
See Appendix A.2 for more details. key step of the proof is to show that max (5 Srr 13 Do (TT) is achieved when 5 is on the bound- ary of the l ball B = {1151| I r). which can be, for example, 5 = [r. .r,0,...0)... OJ_ due to symmetry of B (see figure on the right).
B
Trade-off' between Accuracy and Robustness The lower bound in Equation (5) reflects an intuitive trade-off between the robustness and accuracy,
max X20
A (200) no
max Dy (ATo T&) SEB
Accuracy
Robustness
where the first term reflects the accuracy of the smoothed classifier (assuming the true label is y 1), while the second term maxses D> (ATo || ms) measures the robustness of the smoothed classifier, via the maximum difference between the original smoothing distribution To and perturbed distribu- tion Tg for E B. The scalar can be viewed as looking for a best balance between these two terms to achieve the largest lower bound.
More critically, different choices of smoothing distributions also yields a fundamental trade-off be- tween accuracy and robustness in Equation (7). If mo has large variance or high tail probability, the distance (ATO || Tτ&) will tend to be large and the model is robust. However, if the variance of To is too large, we may obtain a low value of f (zo) and hence less accurate model. The opti- mal choice of the smoothing distribution should optimally balance the accuracy and robustness, by distribute its mass properly to yield small maxses D (Amo || T8) and large fř, (xa) simultaneously.
FILLING THE SOAP BUBBLES: NEW FAMILIES OF NON-GAUSSIAN SMOOTHING DISTRIBUTIONS
In this section, we identify a key problem of using Gaussian smoothing noise in high dimensional space, due to the "thin shell" phenomenon that the probability mass of Gaussian distributions con- centrates on a sphere far away from the center points in high dimensional spaces. Motivated by this observation, we propose in Section [4. a new family of non-Gaussian smoothing distributions that alleviate this problem for f2 attack, and also in Section 4.2 another mixed norm smoothing distribution designed specifically for foo attack.
4.1 E REGION CERTIFICATION
Although isotropic Gaussian distributions appears to be natural choice of smoothing distributions, they are in fact sub-optimal for trading-off accuracy and robustness in Equation (7). especially in high dimensions. The key problem is that, in high dimensional spaces, the probability mass of Gaussian distributions concentrates on a thin shell away from the center, and hence looks like "soap bubbles", instead of "solid balls" as what it appears in low dimension spaces.
Lemma 1 Vershynin (2018), Section 3.1). Lei z ~ NO, Taxa) be a d-dimensional standard Gaussian random variable. Then there exists a constant e, such that for ö E (0, 1).
Prob ( VV - (elog(2/8) < | 5 vd + Velog(2/0)) 2 11 1-6 6.
5

---

Under review as a conference paper at ICLR 2020
This suggests that with high probability (e.g. 1- = 0.99), takes values very close to the sphere of radius vd. within a constant distance from that sphere! See Vershynin (2018) for more discussion.
This phenomenon makes it problematic to use standard Gaussian distribution for adversarial certi- fication, because one would expect that the smoothing distribution should concentrate around the center (the original image) order to make the smoothed classifier close to the original classifier (and hence accurate). To illustrate the problem, consider simple example when the true classifier is f+)) I[] æoll2 S e evd) for constant < 1, where is the indicator function. Then when the dimension d is large, would have (xx) 1 while füu (2x) 0 when To -0, Laxa). It is of course possible to decrease the variance of To to improve the accuracy of the smoothed classi- fier f However, this would significantly improve the distance term in Equation (7 and does not yield an optimal trade-off on accuracy and robustness.
In this work, we introduce new family of non- -aussaan distributions to address this curse of dimen- sionality. To motivate our method, it is useful to examine the density function of the distributions of the radius of spherical distributions in general.
Lemma 2. Assume z a spherically symmetric random variable on Rd with a probability density function (PDF) of form (2(2) x <([[=12)) where Φ: oo) + (0, is a univariate function, then the PDF of the norm of is P||x||2 (r) xx yo-l<b()) The term اd- arises due to the integration on the sphere of radius r in R.
In particular, when Pilz (r) -d- cxp(-r"/200)), which scaled Chi distribution, also known as Nakagami distribution. Examining this P.D.F., we can see that the concentration of the norm is caused by the pd-1 term, which makes the density to highly peaked when d is large. To alleviate the concen- tration phenomenon, need to have way to cancel out the effect of pd-1, This motivates the following family of smoothing distributions:
No ON Laxa), we have Φ(r) = exp(-r²/(2o") and hence
| 20²
p2
(z) x ||=||=* exp
and hence
Pllella (r) x d-k exp
(8)
2o
where we introduce ||=||, kk term in no, with i positive parameter, make the radius distribution less concentrated when k is large.
( is controlled by two pa- rameters (a, k). where a controls the scale of the distribution (and is hence the scale parameter), while controls the shape of the distribution (and hence the shape parameter). The key idea is that adjusting k allows us trade-off the accuracy and robustness much more optimally. As shown in Figure [1] ad- justing a enables us to move the mean close to zero (hence yielding higher accuracy), but at cost of decreasing the vari- ance quadratically (hence more less robust). In contrast, ad- justing k allows to decrease the mean without significantly impacting the variance, and hence yield a much better trade-off on the accuracy and robustness.
The radius distribution in Equation
0.5-
Variance
0.4
Inereasing k
0.3
0.
0.1
Decreasing
5
10
15
20
25
30
Mean
Figure 1: Starting from radius distri-
bution in Equation { with d 100 1 and k = (black start), increas- ing & (green curve) allows us to move the mean towards zero without signifi- cantly reducing the variance. Decreas- ing (red curve) can also decrease the mean, but with a cost of decreasing the variance quadratically.
Computational Method With the more general non- Gaussian smoothing distribution, no longer have the closed form solution of the bound like Equation (6). However, efficient computational methods can be still developed for calculating the bound in Equation (5) with To in Equa- tion (8). The key is that the maximum of the distance term Di (ATo || TT) over d e B is always achieved on the boundary of B as we show in the sequel, while the optimization on À 2 0 is one-dimensionall and can be solved numerically efficiently.
Theorem 2. Consider the lg attack with B {6 ||0 S r) and smoothing distribution To(2) xc
||
exp
(-1 ||=1| with l > and > 0. Define 8 [r. 0 T have
20
D Diooa (XTo T max ID Fo.a (Amoo || (T)) dEB

---

Unfortunately, this seemingly natural choice does not work efficiently for lo attacks (even worse than the & family Equation (8). This because the volume the foo ball is in some sense "too large" (e.g., compared with the volume of & ball). As result, in order to make the probability Under review as a conference paper at ICLR 2020
we can compute Equation (5) with δ 8". We then caleulate Dioo,1 (ATO (T-)) using Monte Carlo approximation. Note that
With Theorem 2
Foo (ATO |l (T-) - (ATO(z)) TTS (z)) dz = BBEsTo [(~-
T (z)
To(2)
which can be approximated with Monte Carlo method with Hoeffding concentration bound. Let { be an ii.d. sample from To. then we can approximate Dzp.11 (ATo TT-) with Because O S (A- T8- T8- (Zz)/To(z)) I A, we have
D n Li (A T8- Dion (Amo ll T [D Aogo (2))2//)/(2nn) D + log(2/6)/
with probability å for EE 1). Drawing sufficiently large number samples allows us to achieve approximation with arbitrary accuracy.
4.2 for REGION CERTIFICATION
Going beyond the & attack, we consider the loo attack, whose attacking region is Br {ő: |öll S. r). This is a far more difficult problem, because the &oo ball is substantially larger than the lg ball of the same radius in high dimensional space. This makes the Gaussian smooth-
ing distribution, as well as our fz-based smoothing distribution in Equation (8) unsuitable for fo
attack. In fact, as shown in the following negative result, if we use Equation (8) as the smoothing
distribution for loo attack, the bound we obtain is effectively the bound we would get for verifying l ball with radius vdr, which is too large to give meaningful results when the dimension is high.
Theorem 3. With the smoothing distribution To in Equation (8) for k 2 0, > 0, and F = F shown in Equation ( the bound we get for certifying the fox attack on Bi = {Ō || S r} is equivalent to that for certifying the l2 attack on B2,var {8 ||0112 v dr), that is,
Vn (F1o.11, Bin,r) Vno ( B var)
The key reason of this negative result is that the furthest points to the origin (vertexes) in Be..r have lz radius of vdr, illustrated as the "pointy" points in Figure [ Thus, the maximum distance maxseB (Doo || RT8 is achieved one of these pointy points, mak- ing it equivalent to optimizing in the lz ball with radius vdr.
Va
In order address this problem, we propose the following mixed norm family of smoothing distribution that uses a mix of lg and foo norms:
Figure 2: foo and &2 balls in high dimension.
|
<o( & || exp
20
in which we replace the ||=||= term in Equation (8) with || |== The motivation is that this allows us allocate more probability mass along the "pointy" directions with larger foo norm, and hence decrease the maximum distance term maxseB, I || TT8). See Figure 2 for an illustration.
In practice, we find that this mixed norm smoothing distribution Equation 9 work much more efficiently than the & norm-based family in Equation (8)
Given the difference of & and lo norms, it is also natural to consider the following pure foo norm distributions, which uses fo norm in both of the terms of the distribution,
| 20
To(2) x || exp
(10)
mass of Equation (00) in reasonable scale, one has to choose very small value of a, which makes maximum distance term too large to be practically useful.

---

Under review as a conference paper at ICLR 2020
(Eq.)
Mixed and (Eq
Pure c., (Eq.10)
1.0
Accuracy
08
0.64
0.67
TV Distance (Robustness)
Figure 4: The Pareto frontier accuracy and robustness (in the sense of Equation 77) of the three smoothing fam- ilies in Equation (8). Equation (9), and Equation (TO) for lo attacking, when search for the best parameters (h, for each of them. The mixed norm family Equation yields the best trade-off than other two. We assume (*( = I[[|=]|2 I r) and dimension = 5. The case when (*( I(] ze ol I r) has similar result (not shown).
Figure 3: For to attacking, the mixed norm distribution (right) yields smaller TV distances (larger overlap areas), and hence higher robustness.
Theorem 4. Consider the adversarial attacks the loc. ball B (6 1101 Sr.. Suppose we use the smoothing distribution To in Equation (1O) and choose the parameters (ki such that
1) ||= is stochastic bounded when To. in that for any that P (1= M) E;
there exists finite M >> Oscch
2) the mode of || lo under To equals Cr, where C is some fixed positive constant,
then for any E (0, 1) and sufficiently large dimension d, there exists constant & > 1, such that, have
max {Dron (ATO ll TT) (A (
BE
This shows that, in very high dimensions, the maximum distance term is arbitrarily close to which is the maximum possible value of Darp. (Amo || T8) (see Theorem D- In particular, this implies that in high dimensional scenario, once fi, (Io) I (1 for some small e, we have Vs (Fi.1.
Bi r) = O(t and thus fail to certify.
Remark The condition 1) and 2) Theorem 4 Mrre used ensure that the magnitude of the random perturbations generated by To is within reasonable range such that the value of f (xo) is not too small, in order to have high accuracy in the trade-off in Equation (7). Note that the natural images are often contained in cube [0, 11d. If ||*|| so is too large to exceed the region of natural images, the accuracy will be obviously rather poor. Note that we use variants of Gaussian distribution, we only need ||~||// /d be not too large. Theorem says that once || is in reasonably small scale, the maximum distance term must be unreasonably large in high dimensions, yielding vacuous lower bound.
Empirical Justification We construct simple toy example to verify the advantages of the mixed norm family Equation 9 overall the & family in Equation
(8) and the Eoo family Equation (0). 0.65, in Figure 4 the Pareto frontier of the accuracy and robustness terms in Equation 7 for the three families of smoothing distributions,
We assume that the true classifier is (=) I([[æ=|| I r) in
5 case and plot
search for the best combinations of parameters (k, a). We can see that the mixed norm smoothing distribution clearly obtain the best trade-off on accuracy and robustness, and hence guarantees tighter lower bound for certification.
Computational Method In order to compute the lower bound when using the mixed norm fam- 9 we need establish the closed form solution of the maximum distance term maxses ID Fi. (ATo mτ) similar to Theorem 2 The following result shows that the optimal 8 achieved at one vertex (the pointy points) of the foo ball.
ily Equation
Theorem 5. Consider the loo attack with Bt {6 ||01| S r) and the mixed norm smoothing distribution in Equation
9 with k. 2 0 and 0. Define 8* (r,,,..,,) T We have for any
8

---

Under review as a conference paper at ICLR 2020
2g RADIUS (CIFAR-10) 10)
0.25
0.5
0.75
1.0
1.25
1.5
1.75
2.0
2.25
Cohen et al.
2019) (%)
60
43
34
23
17
14
12
10
OURS (%)
61
46
37
19
16
14
11
Table 1: Certified top-1 accuracy the best classifiers with various radius CIFAR-10.
l RADIUS (ImageNet)
0.5
1.0
1.5
1.0
2.0
2.5
3.0
Cohen (0199) (%)
49
37
29
19
15
12
9
OURS (%)
50
39
31
21
17
13
10
Table Certified top-1 accuracy of best classifiers with various & radius on ImageNet.
A > 0,
Dijo. (ATo TT-) = max D (Amo 6EB
|| TT))
The proof of Theorem 2 and 5 is non-trivial, thus we defer the details to Appendix A.3 With the optimal 8" found above, calculate the bound with similar Monte Carlo approximation outlined in Section
EXPERIMENTS
We evaluate new bound and smoothing distributions for both lg and for attacks. We compare with the randomized smoothing method of Cohen et al. (2019) with Gaussian smoothing distribu- tion. For fair comparisons, we use the same model architecture and pre-trained models provided by Cohen et al. (2099) and Salman et al. (2019), which are ResNetl 10 on CIFAR10 and ResNet50 on ImageNet.
The details our method are shown Algorithm 2 in Appendix. Since our method requires Monte Carlo approximation, we draw 0.1M samples from and con- struct = 99.9% confidence lower bounds of that in Equation 7 The optimization on is solved using grid search. For & attacks, we set k = 500 for CIFAR 10 and l: 50000 for ImageNet in our non-Gaussian smoothing distribution Equation (8) If the used model was trained with a Gaus- sian perturbation noise of N (0, (0,oī), then the parameter of smoothing distribution is set to be V(d- 1)/(d - k)oo. such that the expectation of the norm ||2||| under our Gaussian dis- tribution Equation matches with the norm of (1, (0) For lox situation, set & 250 and also equals / (d [)
Settings and Hyperparameters
k)on for the mixed norm smoothing distribution Equation (9). In both cases, the baseline algorithm uses a Gaussian smoothing distribution o(0,o)). More ablation study about k is deferred to Appendix
The methods are evaluated using the certified accuracy defined in Cohen al. (2019). Given input image x and perturbation region B, the smoothed classifier is called certified correct if its prediction is correct and has a guaranteed lower bound larger than 1/2 for 8 B. The certified accuracy is the percentage of images that are certified correct. Following Salman et al. (2019), we calculate the certified accuracy of all the classifiers in Cohen et al. (2019) or Salman al. (2019) for various radius, and report the best results over all of classifiers.
Evaluation Metrics
5.1 E2 CERTIFICATION
We test our method on CIFARIO and ImageNet for & certification. For fair comparison, we use the same pre-trained models Cohen al. (2019), which is trained with Gaussian noise both CI- FAR10 and ImageNet dataset. The readers are referred to Appendix Cfor detailed ablation studies.
Table and Table report the certified accuracy of our method with the non-Gaussian smoothing distribution in Equation (8) and the baseline on CIFAR10 and ImageNet, respectively. We find that method consistently outperforms the baseline.

---

Under review as a conference paper at ICLR 2020
1. RADIUS (CIFAR-I0)
2/255
4/255
6/255
8/255
10/255
12/255
Salman et al. (2099) (%)
58
42
31
25
18
13
OURS (%)
60
47
38
32
23
17
Table 3:
Certified top-1 accuracy of the best classifiers with various L. radius CIFAR-10.
1.00
= 0.50
= 0.25
Log [Accuracy (%)]
Gaussian
4
3
Ours
0
12 20
12
16
2
6
Lx radius X 255
Figure 5: Results of foo verification on CIFARIO, on models trained with Gaussian noise data augmentation with different variances dg. Our method obtains consistently better results.
5.2 foo CERTIFICATION
We test our lower bound based on the mixed norm family in Equation (9) for verifying & attacking on CIFARIO, using the models trained by Salman et al. (2019). The certified accuracy of our method and the baseline using Gaussian smoothing distribution are shown Table 3 We can see that our method consistently outperforms the Gaussian distribution baseline by large margin, which empirically shows our distribution a more suitable distribution for to perturbation.
To further confirm the advantage of our method, we plot in Figure the certified accuracy of our method and Gaussian baseline using models trained with Gaussian perturbation of different vari- ances do. under different &oo radius. We again find that consistently, especially when the & radius is large. We also experimented our method and baseline on ImageNet, but did not obtain non-trivial results. This is because foo verification is extremely hard with very large dimensions. Future work will investigate how to obtain non-trivit con-trivial bounds for foc. attacking ImageNet scales with smoothing classifiers.
approach outperforms the baseline
6 CONCLUSIONS
We propose general variational optimization based framework of adversarial certification with non-Gaussian smoothing distributions. Based on the insights from our new framework and high di- mensional geometry, we propose two new families of non-Gaussian smoothing distributions, which significantly outperform the Baussiann-bsse smoothing for l and foo attacking, respectively. Our work provides basis for a variety of future directions, including improved methods for Ép attacks, and tighter bounds based on adding additional constraints to our optimization framework.
REFERENCES
Anish Athalye, Nicholas Carlini, and David A. Wagner. Obfuscated gradients give false sense of security: Circumventing defenses to adversarial examples. pp. 274-283, 2018.
Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, New York, NY, USA, 2004. ISBN 0521833787.
Nicholas Carlini, Guy Katz, Clark Barrett, and David L. Dill. Provably minimally-distorted adver- sarial examples, 2017.
10

---

Under review as a conference paper at ICLR 2020
Chih-Hong Cheng, Georg Nührenberg, and Harald Ruess. Maximum resilience of artificial neural networks. In Automated Technology for Verification and Analysis 15th International Symposium, ATVA 2017, Pune, India, October 3-6, 2017, Proceedings, pp- 251-268, 2017.
Jeremy M Cohen, Elan Rosenfeld, and J Zico Kolter. Certified adversarial robustness via randomized smoothing. arXiv preprint arXiv: 1902.0298,, 2019.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hi- erarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pp. 248-255, Icee, 2009.
Jacob Devlin, Ming-Woi Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguisties: Human Lan- guage Technologies, NAACL-HLT 2019, Minneapolis, MN, USA, June 2-7, 2019, Volume I (Long and Short Papers), pp. 4171-4186, 2019, BRLhhtps::/ /wwp:://wwwwwo.. www.a//wwwww.r//ttaoooo.oooo..o. N19- 1423/
Souradeep Dutta, Susmit Jha, Sriram Sankaranarayanan, and Ashish Tiwari. Output range analysis for deep feedforward neural networks, 2018.
Krishnamurthy Dvijotham, Robert Stanforth, Sven Gowal, Timothy A. Mann, and Pushmeet Kohli. A dual approach to scalable verification of deep networks. In Proceedings of the Thirty- Fourth Conference on Uncertainty in Artificial Intelligence, UAI 2018, Monterey, Califormia, USA, Au- gust 6-10, 2018, pp. 550-559, 2018. BtLhhttp://aat http:///aaaaaacooaaaa///////ooor papers/ 204. pd.
Ruediger Ehlers. Formal verification of piece-wise linear feed-forward neural networks. In Interna- tional Symposium on Automated Technology for Verification and Analysis, pp. 269-286. Springer, 2017.
lan Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. 2015.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp- 770-778, 2016.
Matt Jordan, Justin Lewis, and Alexandros G Dimakis. Provable certificates for adversarial exam- ples: Fitting a ball in the union of polytopes. arXiv preprint 1rXiv:1903.08773, 2019.
Harini Kannan, Alexey Kurakin, and Ian Goodfellow. Adversarial logit pairing. arXiv preprint 18X3v:803.0660 2018.
Mathias Lecuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified robustness to adversarial examples with differential privacy. arXiv preprint 1eXiv:1802.03:
2018.
Guang-He Lee, Yang Yuan, Shiyu Chang, and Tommi S Jaakkola. stratified approach to robustness for randomly smoothed classifiers. Advances in neural information processing systems (NeurIPS), 2019.
Bai Li, Changyou Chen, Wenlin Wang, and Lawrence Carin. Second-order adversarial attack and certifiable robustness. Advances in neural information processing systems (NeurIPS), 2019.
Wenbo Li and James Kuelbs. Some shift inequalities for gaussian measures. In High dimensional probability, pp. 233-243. Springer, 1998.
Xuanqing Liu, Minhao Cheng, Huan Zhang, and Cho-Jui Hsich. Towards robust neural networks via random self-ensemble. In Proceedings the European Conference Computer Vision (ECCV), pp. 369-385, 2018.
Yiping Lu, Aoxiao Zhong, Quanzheng Li, and Bin Dong. Beyond finite layer neural networks: Bridging deep architectures and numerical differential equations. 2018.
11

---

Under review as a conference paper at ICLR 2020
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. 2018.
Aditi Raghunathan, Jacob Steinhardt, and Percy Liang. Semidefinite relaxations for certifying ro- bustness adversarial examples, 2018.
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 arXiv:/906.00 04584, 2019.
Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, lan Goodfellow, and Rob Fergus. Intriguing properties of neural networks. arXiv preprint arXiv: 1312.6199, 2013.
Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge University Press, 2018.
Dilin Wang, Chengyue Gong, and Qiang Liu. Improving neural language modeling via adversarial training. pp. 6555-6565, 2019.
Eric Wong and Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. arXiv preprint arXiv:1711.0085/1 2017.
Cihang Xie, Jianyu Wang, Zhishuai Zhang, Zhou Ren, and Alan Yuille. Mitigating adversarial effects through randomization, 2018.
Runtian Zhai, Tianle Cai. Di He, Chen Dan. Kun He, John Hopcroft, and Liwei Wang. Adversarially robust generalization just requires more unlabeled data. arXiv preprint arXiv:/906. 1906.0055,5 2019.
Dinghuai Zhang, Tianyuan Zhang, Yiping Lu, Zhanxing Zhu, and Bin Dong. You only propagate once: Accelerating adversarial training via maximal principle. Advances in neural information processing systems (NeurIPS), 2019.
Haichao Zhang and Jianyu Wang. Defense against adversarial attacks using feature scattering-based adversarial training. 2019.
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 Advances in neural information processing systems, pp. 4939-4948, 2018
12

---

Under review as a conference paper at ICLR 2020
A PROOFS
A.1 PROOF FOR THE STRONG DUALITY IN THEOREM 1
We first introduce the following lemma, which is a straight forward generalization of the strong Lagrange duality to functional optimization case.
Lemma 3. Given some 6", we have
max min Eng- [f + 2)] + A (f (2o) ErO [f + =)l)
XER fEF
max min Eng- [f + x)] + A (f (zo) - Ero [f(20 + =]])
AER fE/
The proof Lemma 3 is standard. However, for completeness, we include here.
Proof.
Without loss of generality, we assume fi. (ax) (0, 1), otherwise the feasible set trivial.
Let a" be the value of the optimal solution of the primal problem. We define fto (2o)
Emo [x00 + +]] = h[f] and gff] Exg- [f + =)]. We define the following two sets:
A= e 3f Fio.11 hlfl v, [fffstt B (0, E
a"}
Notice that both sets A and B are convex. This is obvious for B. For any (e1, 11) E A and (U2, 12) E A, we define E Fio.1j such that h[fi]= = v1 g[fi] S (and similarly define f2). Notice that for any y [0, 1], we have
7f1 = (1- E F(..1]
>h + (1 (1-))b(f2] = = + (1-7)02
>9 [i][ [ (1- S 5 + (1 7
E A and thus A is convex. Also notice that by definition, A n B 0. Using separating hyperplane theorem, there exists a point (91, 92) * (0, 0) and value such that for any tv, E A. qıu + 22t 2 and for any (0, s) E B, 828 a. Notice that we must have q2 2 0, otherwise, for sufficient 8, we will have g2s > a. thus have, for any 1j,,1), we have
which implies that y(11 (1) +
hn + (29 2 o² 2 920"
If (/2 > 0, we have
max min glfl + Ah[f 2 min glf] + AER fEF
11 h[fl 2 a', q2
fEF
which gives the strong duality. If d22 = 0, we have for any f E F1o.11. dn [ 2 and by the separating hyperplane theorem, 91 0. However, this case is impossible: If q1 0, choosing
= gives qı [f]] = 41 (ft, (z))= - 1) < 0; If qı < 0, by choosing f 0, we have q: =
(ft, (xo) - 0) < 0. Both cases give contradiction.
Based on Lemma 3 we have the proof of the strong duality as follows. Notice that by Lagrange multiplier method, our primal problem can be rewritten as follows:
min min max Ex [f + 2)1 + > (#o) -Es [f + +)]]]
BEB pe XER
and the dual problem
max min min Erg [s(20 + 2)] + (JH, (wo) - E [f(00 + =)])
Xek BEB feP
max min min Er, [s z)] A (Jz (m:) - Ero [ʃ + z)))
A SEB fEF
13

---

Under review as a conference paper at ICLR 2020
By the assumption that for any À 2 O, we have
max min min Exs [f + x)] + A (ft (xo) - Ex [f + x]])
X20 BEB (EF(..))
min Emg- [f =)] (f (wo) - 1Eroo (f + z)])
fe
for some 8* E B. We have
max min min XER BEB /EFio,1
Ems [/(an + z)] + X (Jio (20)) - ET [5 + +)]])
max min Egg- [f(x + =)] + À (f (2x) E,rO [f(2 + z)])
A20 fEF(a.1)
max min Eng- [ + =]]+ + X (f (xo) Eno (f(20 + x)])
XER fE/
= min max [s + 2)] À (f (2r) Emo (5(20 + z)])
fefjo. AER
2in min max Emg. [s + =)] + A (J (mo) - TTT [f + z)])
8EB (EF(o.1) AER
where the second equality (*) is by Lemma
A.2 PROOF FOR COROLLARY 1
Proof. Given our confidence lower bound
/ ( (T]( dz
min max Apo [6 25 X
define C2 = { 2 {^(=}} = TT= s
|1811
2 + o² ln }} and ((-) to be the edf of
standard gaussian distribution, then
/ (ATO(z) TT(22) dz
= [ (ATo(2) - Tz(2)) de
cs
- (N( 0, 0 Cx) - (N 02 E EX)
||01|
o In X
1 10l12
In A |
= +
+
+b
2a
||0||
20
Define
F(5, A) = Apo - (XTo(2) -=())) ( dz Xpo A
| 2x
o In A
+
(-166l|2 2x
o In A
|
| 1|
For V6, F' a concave function w.r.t. as /' is actually summation many concave piece wise linear function. See Boyd & Vandenberghe (2004) for more discussions of properties of concave functions.
Define As exp means
2r| |r||||||20 1 (po) [611]
20
simple calculation can show 0F(6.)) 82
A=
0, which
min max F(8,)) = min | A20
F().A8)
1101:.51
-|10||2
In A
min
0+ ②b
+
2x
| 2
|
min
+b
4 (p-((p))
1|
Φb ④ (pn) -)
14

---

Under review as a conference paper at ICLR 2020
This tells
min max F(6, > + (po) 1/2 (/)))//(000 ( |r A20
i.e. the certification radius is 0 -b-(p)). This is exactly the core theoretical contribution of Cohen
et al. (2019). This bound has straight forward expansion for multi-class classification situations, we refer interesting readers to Appendix D
A.3 PROOF FOR THEBRRE AND 5
In this subsection, we give the proof of theorem
and Here consider general smooth || for some k1, l2 2 0 and a > O. We first gives
distribution x=( x || || exp
2
the following key theorem shows that ID DF... dimension
(Arr T&) increases as |6,| becomes larger for every
Theorem 6. Suppose (z) || ki 1==1|2
k2 exp
| 20
). for some k1, 22 2 0 and a >> 0, for
any x 2 0 we have
sgn(0;
D Fo. (ATO || TT) 0,
06;
for any i E f1.2..... d}.
Theorem and 5 directly follows the above theorem. Notice that in Theorem 2 as our distribution is spherical symmetry, it is equivalent to set B
{8 : Ia, O, ... 0] a S r by rotating the axis.
Proof. Given A, 1 and l2, we define Φ (s) = 8 -h, Φ2(5) 8 ke Notice that Φ1 and de are monotone decreasing for non-negative s. By the symmetry, without loss generality, we assume 6 = [ō1.... dd] for 8, 2 0, i E [d]. Notice that
ao ع11 = T( 811:0 |x;
-8:l
V (x; - 5z)²
08,
06,
(.r - 5.)
= I{ll=0
511o0 =|x; 5:13 2co 1o
And also
[00 11l2
Σ
(x; 12)
06,
05,1 /
(x; Mii
12:00 11l1
We thus have
(Amo(ar)) (T())))) day
05,
0
II (ATT((Z0)= 2 =2(2)))
To (xo))
05,
I (ATo(To)= 2 ()()) Fi (1|=)) 8 ōllao ||2 5112) dxy
f (ATo(wF)= 2 TT()))) xι 11 Fi (I|æ 01 ||000 8112) da
1 (TTO(Wo)= 2 Ts( < 31) Fi (1|00 01
| 8112) dx
where we define
Fi (1 811 1 0112)
(x) - 81)
= # (I|æo 81 011ac) Φ (1 2 8 [[] 611 =|xr -811)
a00 ol
(x1 11)
+ Φ1 (1|20 pl1bo) 02 [1:00 elll2)
xD 11
15

---

Under review as a conference paper at ICLR 2020
Notice that as 0f 0 and 0 S 0 and we have
/ I 1(ATO(Z0) 2 TT (2)), 21 > 613 Pi (1/20 - 811,0 || - 8112) dat S 0
/ [ 2 To (20): 21 < 6,) Fi (1 - 9 - 5112) dæ 2 0.
Our target is to prove that
a I (ATO - To (20)) dxo 2 O. Now define the set
861
Hi (0o (mo 2 TT x1 > m1)
H₂ {25] 3 .2,. ..... Ftd] 20 (.1, -..y rdd] E Hi}- Here the set H2 is defined as a image bijection
proj(20) = [25] 21, ..... Fal = :z:
that is constrained on the set H1. Notice that under our definition,
f (T) 2 (x0)) x1 > 61) F1 (11=0 - 81loc 1|200 6 8112) dao
= =/ Fi (1/20 61..o, 11=00 (1)) dxo.
H1
Now we prove that
I (ATO(zO)) 2 (x(x))) < $0) Fi (1120 -011z0, 8112) dx
Fi (1|200 -01lo0 |1:00 8|12) dxo
H2
Fi (|
8l1.0
||:00
6112) dxy
H1
Property of the projection Before we prove the (1) and (2), we give the following property of the
defined projection function. For any zo proj(=o). wo H1. we have
|20 8 01100
120 ø||,
1200 8|1,
| 2 |
|oollo 2 100l
This is because
24 E [d] {1}
3 = 26 21:
and by the fact that æ1 2 51 O, we have | |<|| and |
811
S [ 6,1.
Proof of Equality (2) By the fact that proj is bijective constrained on the set H1 and the property
of proj. we have
Fi (115
8 8llmm
| -8112) dazn
Hg
/ oi (1|ãg - 5 511.c) t2 20 5112) [[ - -511o0 = =Iā1 811}
(51 51)
=
|200 5 511.0
dzo
He
{ Φi (1lão - 511.c) 0h (1
(ī1 81)
+
6112)
100 5|12 d2o0
Hg
(
{ oi (||=00 5 5l1.c) tr (|
(6) x1)
5 5112) I(| (1|10o - 811.0 = |.11
811}
det (J) dæ
I 8
Hi
(01 - Iz daco
+
Φi (11200
8 511,c) 2h (1/00 8 ö1l2)
|m0 0112
Fi (1|20o 511,01 ||:00 8 da
16

---

Under review as a conference paper at ICLR 2020
where (*) is by change of variable zo proj( and J is the Jacobian matrix J
and here have the fact that क - 61 -28 x1) -81 - -d1).
Proof of Inequality (1) This can be done by verifying that H2 S {wo ATo( 2 To (xo)) < 51}. By the property of the projection, for any Do E H1. let 2o proj(2n), then A (Zo) 2 (2n) 2 (
(Ta) (by the fact that t Φ1 and Φ2 are monotone decreasing). It implies that for any Ho E H2, we have (To( 2 TT(2u) and thus H2 C {Zg (o(2)) 2 T ( < 61}.
Final statement
By the above result, we have
a5, f (ATo(Za)) (2000))) dar 2 0,
and the same result holds for any 26. (AToo(zo) mm(==o)) dro, E [d]. which implies our result.
0
A.3.1 PROOF FOR THEOREM
First notice that the distribution of z can be factorized by the following hierarchical scheme:
a ~ T((a) x ad-1-
2. Ila 2 0}
Unit (-1,1)
(11,)
2 + 8
||||00
Without loss of generality, we assume 8* = [r:...,.] TT_ (see Theorem 6)
DAo. (ATo || TT-) Ex (x πо
(z)
Notice that as the distribution is symmetry.
P Too (I|= + 8011 aatr
|| = =)=
Define (²)(0 is the i-th order statistics of 12yl. 1,.... d conditioning on || factorization above and some algebra, we have, for any e E (0, 1).
By the
1 (d-1) (d) (1 (1-6) 12 =a 1 -)
And
(d-1) [2|(05
(d) Now estimate Di (ATO || TT-).
T8 (2)
E Eguto
A
15
+
TT8 (z)
E, ENNno
|||
E. E.gREaa EZnTo
(z)
||| a,
8011 +r
no
+
EgEEsTo
x
(2)
||
a,
8*
#
+
17

---

Under review as a conference paper at ICLR 2020
Conditioning on |=0100 a.
|| + +
11
+ 7, we have
TT 1
2n (2ratr2)
(z)
To
d11t (2++1).
26
Here the second equality is because we choose mode([|z]loo) v - ko Cr. And thus we have
Cr, which implies that
( (A- [()))
Eg EgEEzwoo
(z)
1| = =a,1 + + 1oo a tr
To
-/ A- 1
(22+())2))
26
T(a)da
/ x
a - (1 + 2) -k
2a/r+1 20
-
x(a)da
=x
=x- - O(
for some / 1>1 1. Here the last equality is by the assumption that ||=1|00 = Op(1).
[A--=0 =e (z)) | || = a, 1| + +6 1lo #atr By
Next we bound the second term E,
the property of uniform distribution, we have
|
P
(1 (1-6) || = 1| + + X #atr)
| (d)
|2| (d-1)
(1 (1-c) |1=1)1 =a) =a)
=P
|2| (d)
21 (1 c)u-1
And thus, for any E [0, 1),
(II= 50 100 2 ((1 - e) )a + r)2 ||=1|00 = =a, + 100 # a #a+r)
2 2 (1 - -(1 - -))--)).
It implies that
Ex (x-
To (z)
|| = =a, [l, + +001 = =atr
T
+
1 (1 - (1 - -)-
1 (1 (1- 2) xk
E 2 (ele-2)a2+2rl 1 (1-)0)))+)))
2
2 (1 (1 d) 1) { 11-(1-00 (1- 2) - بي (cle-2)a² /r2 +2(1 +2(1-0)//1+1))
1
log(2/6') for large enough d, we have For any 6' E (0, 1), by choosing 6 d-1
A [^~
EzaTo
To
(z)
(z)
|| = 1| + 8011 +
To
1 (1 - (1 - () a - (1 (1-c+ 2) e (2(--)
2
-1 (1- (1- (1 log(2/e)) yd-1)
(1_ (1 log(2/6)
+ =1)
م - (2(1 (20-00/11))) aloogt/dd)
F2
d-1
1-1
1 (1 )) (A (1 (1-e
- 2) + -يي (2(1 -c)aar-ca 11
logra/e's
e
2
18

---

Under review as a conference paper at ICLR 2020
Thus have
(^~ (^-20) _6=26 (z)
Eg 18 zn0ta
|||=||0 a, al 8011 # a a--1
To
(1 -(--) O(t (A-O
Combine the bounds, for large d, we have
Dy (ATO mT.) = (1=)==(1)(--0((())
B PRACTICAL ALGORITHM
In this section, we give our algorithm for certification. Our target is to give high probability bound for the solution of
VE (Fiu,1), Bi max (Aft. DFo. (Amo || mT)
given some classifier f Following Cohen al. (2019), the given classifier here has binary output {0, 1]. Computing the above quantity requires us to evaluate both f and D (Aro || π&). lower bound po of the former term is obtained through binominal test as Cohen et al. (2019) do, while the second term be estimated with arbitrary accuracy using Monte Carlo samples. We perform grid search to optimize and given X, we draw N i.idd samples from the proposed smoothing distribution To estimate Aft. DF. (ATo w&). This can be achieved by the following importance sampling manner:
AS
DFo.. (ATo T&)
Año
/
T5
(z)
To(2)dz
To
N
2
Año
1
Σ 1=1
X
T8 (zi)
-c
N
no
And we use reject sampling to obtain samples from To- Notice that, we restrict the search space of finite compact the importance samples is bounded. Since the Monte Carlo estimation is not exact with an eтror c, we give high probability concentration lower bound of the estimator. Algorithm summarized our algorithm.
Algorithm 1 Certification algorithm
Input:
input image zo: original classifier: f*; smoothing distribution тo; radius r; search interval [Asuu, Xend] of X; search precision for optimizing A; number of samples N₂ for testing Po: pre-defined error threshold significant level a;
compute search space for A =range(A (Astarts Aend. ht)
compute N2: number of Monte Carlo estimation given e, a and A
compute optimal disturb: depends on specific setting
for À in A do sample 21,- 2N, To
compute n1 = n; Σn f (mo + 23)
compute Pu =LowerConfBoumn [11, N1, 1 ax)
sample -.. NN2 To
compute Dioo (Amo T8) NrZ ΣN' (2-
(zi)
no
compute confidence lower bound by Apo 1 Jo.1 (ATo || T8)
end
maxxaa 0y > 1/2 then Co can be certified
else
Zp cannot be certified end
19

---

Under review as a conference paper at ICLR 2020
The LowerConfBound function performs binominal test described in Cohen et al. (201)) The é in Algorithm D is given by concentration inequality.
Theorem 7. Let " ; # Ei= (A mol=.) we yield
Pr[[ ,NN (x)) - / (ATT(()) - (T)())) dzl 2 of exp
2N
X2
Proof. Given McDiarmid's Inequality, which says
sup I (21, T2....... Fn) - h (21, ... 24- 2 Zu)) sc
for 1 1sis n,
A and then obtain we have Gi N.
(ATo())-TT(s)) Pr[[h(21, ... ,2N) - ( - TT(2)) d2l 2 t) S
-2NE² A2
exp
The above theorem tells us that, once c, X, N is given, can yield bound with high-probabilityy 1- a. One can also get N when e, A, a is provided. Note that this is the same as the Hoeffding bound mentioned in Section 4.1 Micdiarmid bound is generalization of Hoeffding bound.
However, in practice we can use small trick as below to certify with much less comupation:
Algorithm Practical certification algorithm
Input: input image æo; original classifier: fF; smoothing distribution no: radius r; search interval for A: [Ammit Aend]; search precision h for optimizing A; number of Monte Carlo for first estimation: No. NN;; number of samples N1 for second test of pu: pre-defined error thresh- old significant level a; optimal perturbation (ő [r. O..... 0] for l attacking and 8 [r,...,,r]] for lo attacking).
for À in A do sample "1, 2NT To
compute n 1 Σ f Eo + 2;)
No
No
compute Po =LowerCon/Bound (n), No. - aa)
sample -.. No To
compute D Dy (Amo T8) = No. Ein No (1- Io (zi)
compute confidence lower bound by Apo 1D TD. end
(ATO || 18)
compute À = arg maxxea bx compute Ng: number of Monte Carlo estimation given e, a and Ā
sample 21, ... NN ~ TD compute N, Σi compute Po =LowerConfBound/n N,, ac)
Ni i=1 f#o + z;)
sample ø1, ................................ N,₂ ~ Tо
compute DDFo..) (Amo T8) = Ny Em² (2- Iz (2())
compute 2po DDF (ATo l| TT) -
if 2 1/2 then
Zp can be certified
else
end 2o cannot be certified
Algorithm 2 allow one to begin with small No, Nº obtain the first estimation and choose a Â. Then rigorous lower bound can be achieved with À with enough (i.e. N1, N₂) Monte Carlo samples.
20

---

Under review as a conference paper at ICLR 2020
C ABALATION STUDY
On CIFARIO, we also do ablation study to show the influence of different & for the l certification case as shown Table
2 RADIUS (CIFAR-10)
0.25
0.5
0.75
1.0
1.25
1.5
1.75
2.0
2.25
Cohen et al. (0199) (%)
60
43
34
14
12
10
(%)
60
43
34
23
18
15
12
10
200 (%)
60
44
36
24
18
15
13
10
k 500 (%)
61
46
37
25
19
16
14
11
1000 (%)
59
44
36
19
16
14
11
k 2000 (%)
56
41
35
24
19
16
15
12
Table 4: Certified top-1 accuracy of the best classifiers at various &g radius. We use the same model
as Cohen al. 2019 and do not train any new models.
D ILLUMINATION ABOUT BILATERAL CONDITION
The results in the main context is obtained under binary classfication setting. Here show it has natural generalization to multi-elass classification setting. Suppose the given classifier f² classifies an input 2n correctly class A, i.e.,
(x0)) > max (mo)
(11)
B&A
where (wo) denotes the prediction confidence of any class B different from ground truth label A. Notice that f (xx) + Σ B f (xo) = 1, so the necessary and sufficient condition for correct binary classification S (ar) > 1/2 becomes sufficient condition for multi-class prediction.
Similarly, the necessary and sufficient condition for correct classification of the smoothed classifier
min
Ex (fA - 5 +)]
s.t. ErolfA(Zo)] =
JEF
max
E Ex (x0 (2o + z)]
s.t. Ex.lfo((o) = ff B B(x)))
fEF
for VB # A and any perturbation 5 E B. Writing out their Langragian forms makes things clear:
max A/$ A (wo) 1D (Aro || ms) > min max >ʃt ((0o) DFo., (лo || Amo)
B=A
Thus the overall necessary and sufficient condition
min max (ASho: - Drjo.a (Amo T&)) BEB
max min (N/ :( + DD (TT Xmoo)
0
B
Optimizing this bilateral object will theoretically give a better certification result than our method in main context, especially when the number of classes is large. But do not use this bilateral formulation as reasons stated below.
When both To and w gaussian, which is Cohen at. to:
2019)'s setting, this condition is equivalent
|81|
④ Φ-1(/2 (( (xo)) ||0| } 0
min
+
④ ④
(Jto:((200)
max &b B=A
(f2orA(Zo))
> ((.))
YB + A
x
( - x - (xn))) VB + A
2
21

---

Under review as a conference paper at ICLR 2020
with similar derivation process like Appendix A.2 This is exactly the same bound in the (restated) theorem Cohen et al. (2019).
Cohen et al. 2019) use 1 PA naive estimate of the upper bound of (zx). where PA is a lower bound of A ( (zu). This leads the confidence bound decay the bound one can get in binary case, i.c. r S σ 11---1(
As the two important baselines (Cohen et al. 2019; Salman et al. 2019) do not take the bilateral form, we also do not use this form in experiments for faimess.
22


Reviews:
[{"review_id": "rJejRI6aKS", "reviewer": "AnonReviewer1", "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:\n\nThis paper investigates the choice of noise distributions for smoothing an arbitrary classifier for defending against adversarial attacks.  The paper focuses on the two major adversaries: \\ell_2 adversaries and \\ell_\\infty adversaries. Theorem 1 quantifies the tradeoff between the choice of smoothing distribution which (1) has clean accuracy close to the original classifier and (2) promotes the smoothness of smoothed classifier (and hence adversarial accuracy).  For the \\ell_2 adversary, the paper argues that Gaussian distribution is not the right choice, because the distribution is concentrated on the spherical shell around the x. Instead, the authors propose using a new family of distributions, with the norm square  (p_{|z|_2^2}) following the scaled \\chi^2 distribution with degree d-k (Eq. 8). This allows an extra degree of freedom, and setting k=0 recovers the Gaussian distribution. For \\ell_\\infty perturbations, the paper suggests another family of distributions combining the \\ell_2 and \\ell_\\infty norm (Eq. 9), and argues that it outperforms the natural choice of \\ell_\\infty norm-based distributions (Eq. 10).\n\nI think the paper should be rejected because (1) For \\ell_2 perturbations, there is no major difference between this new family of distributions (d-k \\chi^2) and a Gaussian with different variance. (2) For \\ell_\\infty distributions, the motivation of mixed norm distributions (Eq. 9) over \\ell_\\infty based distributions (Eq. 10) is not very clear. (3) The experimental evidence is also weak (see below).\n\nMain arguments:\n\n1. The distribution of the norm \\|z\\|_2 in Eq. (8) would be concentrated on a thin spherical shell of radius about \\sqrt{d-k}\\sigma. As the Gaussian distribution with standard deviation \\sigma' is supported on a shell of radius about \\sqrt{d} \\sigma', for each (k,\\sigma) in the family of Eq. 8, there is an equivalent Gaussian with appropriate \\sigma' (Theorem 3 now just compares the radius of the spherical shell). Therefore, I don't see the benefit of this extra degree of freedom of k: the noise distribution is again a \"soap bubble\" of a different radius. Thus, a grid search over \\sigma' for a Gaussian should be the same as a grid search over (k,\\sigma) in Eq. 8.\n\nEven the experimental experiments are a marginal improvement over Cohen et al.  I don't see why the value of (k,\\sigma) was not provided in Table 1 and only \\sigma was provided. Also, the table of Cohen et al. was only calculated for specific values of \\sigma for Gaussian distributions (0.12, 0.25, 0.5, 1.00). For a fair comparison, comparable values of \\sigma's must be calculated, and then the best choice should be selected. \n\n2. In the light of previous arguments, I don't think the choice of Eq. (9) or Eq. (10) is well motivated. \nWhy not smooth it with a cube of appropriate radius? Also, not enough experimental details are provided for Table 3.  Salman et al. (2019) reports the accuracy of 68.2% for \\ell_infty perturbations (Table 3, Salman et al. (2019)), whereas the value reported in your Table 3 for at the same radius is 58%. Is it a typo? In any case, the values reported for the proposed model in Table 3 are only a marginal improvement over Figure 1 (left) in Salman et al. (2019), just going by the trivial \\ell_2 to \\ell_\\infty certificate.\n\nOther areas for improvement:\n\n1. The paper contains numerous grammatical errors, confusing statements, and nonstandard phrases.  For example: (i) more less robust, (ii) black start, (iii) pointy points, etc.  I suggest that the authors spend more time clarifying their manuscript.\n\n2. The paragraph starting with \"Trade-off between Accuracy and Robustness\": I think this paragraph should be reworded for clarification.  It is not robustness but rather the lack thereof -- say, sensitivity.\n\n3. On p.5, why was the toy classifier sphere-based? The toughest classifier for Gaussian smoothing (the one achieving the lower bound for Gaussian smoothing) is actually a linear classifier.\n\n\n", "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": "ByllmnE6tH", "reviewer": "AnonReviewer3", "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": "The paper introduces an improvement to the randomized smoothing analysis in Cohen et al. (2019), using Lagrangian relaxation to achieve a more general lower bound. Using this, it considers different adversarial smoothing distributions that yield some increase in certified adversarial accuracy.\n\nOverall assessment: While the Lagrangian relaxation idea is interesting and could yield interesting follow-up work, the paper is sloppy in several respects and needs to be tightened before it can be considered for publication.\n\nKey issues:\n1. Proof of main theorem (strong duality) is incorrect. Likely the statement itself is also incorrect. Fortunately the most important direction (lower bound) is still true, so this isn't a fatal flaw to the approach.\n2. The paper makes several references (in italics) to a \"fundamental trade-off between accuracy and robustness\". But a fundamental trade-off means that *any* method that attains good accuracy must sacrifice robustness and vice versa; this requires a \"for all\" statement, i.e. a lower bound. All the paper shows is that the *particular upper bound* exhibits a trade-off (and even then, the notions of \"accuracy\" and \"robustness\" are merely interpretations of quantities in the bound; it's not clear why the robustness term in particular is tied to more standard notions of robustness).\n3. The justification for why the particular smoothing distributions are good ideas is sketchy.\n\nI elaborate on 1 and 3 below. Addressing 1-3 effectively will improve my score.\n\n#1 (main theorem is incorrect): Claim 3 in the appendix is wrong. The fact that (delta', f') outperforms (delta-bar, f-bar) with respect to lambda* does not imply that (delta', f', lambda*) is a better solution to the primal problem, because we must take max over lambda and the maximizing lambda need not be lambda*. In particular if f' doesn't satisfy the constraint we would instead take lambda to infinity.\n\n#3 (sketchy justification): The paper justifies a smoothing distribution that concentrates more mass around the center as follows: \"This phenomenon makes it problematic to use standard Gaussian distribution for adversarial certification, because one would expect that the smoothing distribution should concentrate around the center (the original image) in order to make the smoothed classifier close to the original classifier (and hence accurate).\" I don't see why we should want more mass near the center---in the limit as we move all the mass towards the center and get the original classifier, our certified bound will be terrible, so it's not clear why moving in that direction should be expected to help. Indeed, the experimental gains are minimal (1 to 3 percentage points) and on methods that were not carefully tuned, so one could imagine that the baseline method could be improved by that much just with careful tuning.\n\nI similarly didn't understand the justification for the mixed L-inf / L-2 distribution for L-infinity verification. The main justification was \"The motivation is that this allows us to allocate more probability mass along the “pointy” directions with larger`∞norm, and hence decrease the maximum distance term max δ∈B`∞,rDF(λπ0‖πδ).\" This is at the very least too brief for justifying the main experimental innovation in the paper (here at least the empirical improvements are bigger, although still not huge).\n\nMinor but related: Why is the x-axis in Figure 4 so compressed? This is also in a regime where all 3 methods fail to certify so not clear it's meaningful.\n\nWriting comment: Change some of the Theorems to Propositions. Theorems should be for key claims in paper (there shouldn't be 4 of them in one 8-page paper).", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "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_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": "B1lWEtgb9B", "reviewer": "AnonReviewer2", "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 paper presents a new method for adversarial certification using non-Gaussian noise. A new framework for certification is proposed, which allows to use different distributions compared to previous work based on Gaussian noise. From this framework, a trade-off between accuracy and robustness is identified and new distributions are proposed to obtain a better trade-off than with Gaussian noise. Using these new distributions, they re-certify models obtained in previous work.\n\nI am hesitating between a weak reject and a weak accept. The theoretical results are interesting, showing a clear trade-off between robustness and accuracy with a new lower bound and deriving better smoothing distributions. However, the experimental results are lacking, and do not support much the proposed method. Training with this new distribution would have been a natural experiment given the argument. Moreover, the results for L_inf are partial and it would be expected to have some results for ImageNet as claimed in the introduction. I would have given an accept if the previous points had been addressed and I feel that with some more work on it, it would become an excellent paper.\n\nMain arguments:\nMy main concern is about the experiments: Why were Cohen et al.’s models used instead of Salman et al.’s? Salman et al.’s have achieved better certified accuracy under the L_2 norm so it would only seem natural to use their model.\nAbout the main results: there seems to be a discrepancy between the results reported for Cohen et al. and the original paper for both CIFAR-10 and ImageNet L2 certification. Also, the reported certified accuracy for Salman et al.’s model for L_inf on CIFAR-10 reported in the original paper is 68.2 at 2/255, which is very far from the 58 in Table 3. What is the reason for these differences?\n\nMinor comments:\nIn the third paragraph, it is claimed that L_inf attacks are a stronger and more relevant type of attacks than L_2 attacks. These two different objectives cannot be compared in those terms.\nDefenses such as adversarial training have not been “broken” as claimed in section 2 in the sense that the claims made in the original paper still hold true. The term broken is used for defenses in which the claimed accuracy against stronger attacks were found to be much lower than what was claimed in the original paper.\nIt is claimed that “if ||z||_inf is too large to exceed the region of natural images, the accuracy will be obviously rather poor”; however, the common practice is to clip to the input space bounds. How would that affect the method?\n\nThings to improve the paper that did not impact the score:\nIn the first paragraph, Goodfellow et al., 2015 is cited, however, papers on adversarial attacks were published earlier than that such as Szegedy et al., 2014 or Biggio et al., 2013.\nVershynin, 2018 is cited about the distribution of a gaussian in high-dimensional spaces. However, this is a very well known result and does not need any citation (or if any, Bellman, 1961).\nTypo after equation 4: ||f||_{L_p}\nTypo in “Black-box Certification with Randomness” paragraph: “by convovling”\nTypos in Table 2.: the columns 2.0 to 3.5 are mislabeled\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "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_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": {}}]

Author rebuttal:

Meta-review: The authors extend the framework of randomized smoothing to handle non-Gaussian smoothing distribution and use this to show that they can construct smoothed models that perform well against l2 and linf adversarial attacks. They show that the resulting framework can obtain state-of-the-art certified robustness results improving upon prior work.

While the paper contains several interesting ideas, the reviewers were concerned about several technical flaws and omissions from the paper:

1) A theorem on strong duality was incorrect in the initial version of the paper, though this was fixed in the rebuttal. However, the reasoning of the authors on the "fundamental trade-off" is specific to the particular framework they consider, and is not really a fundamental trade-off.

2) The justification for the new family of distributions constructed by the author is not very clear and the experiments only show marginal improvements over prior work. Thus, the significance of this contribution is not clear.

Some of the issues were clarified during the rebuttal, but the reviewers remained unconvinced about the above points.

Thus, the paper cannot be accepted in its current form.

Decision: Reject