Title: FILLING THE SOAP BUBBLES: EFFICIENT BLACK-BOX ADVERSARIAL CERTIFICATION WITH NON-GAUSSIAN SMOOTHING

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 2 perturbation. We propose a general framework of adversarial certification with non-Gaussian noise and for more general types of attacks, from a unified variational 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 2 and ∞ attacks, respectively. Our proposed methods achieve better results than previous works and provide a new perspective on randomized smoothing certification.

1. INTRODUCTION:

Deep neural networks have achieved state-of-the-art performance on many tasks such as image classification (He et al., 2016; Lu et al., 2018) and language modeling (Devlin et al., 2019) . Nonetheless, 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 human-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 be shown to be broken by more powerful adversaries eventually, (e.g., Athalye et al., 2018; Madry et al., 2018; Zhang et al., 2019; Wang et al., 2019) . This casts an 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 on the inputs. Compared with the other more traditional verification approaches (e.g. Wong & Kolter, 2017; Jordan et al., 2019; Dvijotham et 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 blackbox classifiers and is shown to 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 2 attack, in which the perturbations are allowed within an 2 ball of certain radius. A stronger type of attack, such as the ∞ attacks, is much more challenging to defense and verify due to the larger set of perturbations, but is more relevant in practice.

In addition, all the existing randomized smoothing methods use Gaussian noise for smoothing. Although appearing to be a natural choice, one of our key observations is that Gaussian distributions is in fact a rather sub-optimal choice in high dimensional spaces, even for 2 attack. This is due to a 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 to the original input). As a result, the variance of the Gaussian noise needs to be sufficiently small to yield good approximation to the original classifiers (by squeezing the "soap bubble" towards the center point), which, however, makes it difficult to verify due to the small noise. Further, for the more challenging ∞ attack, Gaussian smoothing provably degenerates in high dimensions.

Our contribution We propose a general framework of adversarial certification using non-Gaussian smoothing noises, based on a new perspective from variational optimization. Our framework re-derives the method of Cohen et al. (2019) as a special case, and is applicable to more general families of non-Gaussian smoothing distributions and more types of attacks beyond 2 norm. Importantly, our new framework reveals a fundamental trade-off between accuracy and robustness for guiding better choices of smoothing distributions. Leveraging our insight, we develop two new families of distributions for better certification results on 2 and ∞ attacks, respectively. Efficient computational approaches are developed to enable our method in practice. Empirical results show that our new framework and smoothing distributions significantly outperform the existing approaches for both 2 and ∞ attacking, on challenging datasets such as CIFAR-10 and ImageNet.

2. RELATED WORKS:

Empirical Defenses Since Szegedy et al. (2013) and Goodfellow et al. (2015) , many previous works have focused on utilizing small perturbation δ under certain constraint, e.g. in a p norm ball, to attack a neural network. Adversarial training (Madry et al., 2018) and its variants (Kannan et al., 2018; Zhang & Wang, 2019; Zhai et al., 2019) are the most successful defense methods to date, in which the network is 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 a classifier can guarantee a constant classification within a local region, it is called a 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 a piece-wise linear function. This enables researchers to introduce satisfiability modulo theories (Carlini 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 constant or other information of the network (Jordan et al., 2019; Wong & Kolter, 2017; Raghunathan et al., 2018; 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 et al. (2018) first introduced randomization with technique in differential privacy. Li et al. (2019) improved their work with a bound given by Rényi divergence. In succession, Cohen et al. (2019) firstly provided a tight bound for arbitrary Gaussian smoothed classifiers based on previous theorems found by Li & Kuelbs (1998) . 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 0 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 2 and ∞ .

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.1 our general framework of adversarial certification using non-Gaussian smoothing noises, from a new variational optimization perspective. Our framework includes the method of Cohen et al. (2019) as a special case, and reveals a critical trade-off between accuracy and robustness that provides important guidance for better choices of smoothing distributions in Section 4.

Adversarial Certification:

We consider binary classification of predicting binary labels y ∈ {0, 1} from feature vectors x ∈ R d for simplicity. The extension to multi-class cases is straightforward, and is discussed in Appendix D. Assume f : R d → [0, 1] is a pre-trained binary classifier ( means the classifier is given), which maps from the feature space R d to either the class probability in interval [0, 1] or the binary labels in {0, 1}. In the robustness certification problem, a testing data point x 0 ∈ R d is given, and one is asked to verify if the classifier outputs the same prediction when we perturb the input x 0 arbitrarily in B, a given neighborhood of x 0 . Specifically, let B be a set of possible perturbation vectors, e.g., B = {δ ∈ R d : δ p ≤ r} for p norm with a radius r. If the classifier predicts y = 1 on x 0 , i.e. f (x 0 ) > 1/2, we want to verify if f (x 0 + δ) > 1/2 holds for any δ ∈ B. In this paper, we consider two types of attacks, including the 2 attack B 2 ,r def = {δ : δ 2 ≤ r}, and the ∞ attack B ∞ ,r def = {δ : δ ∞ ≤ r}. More general p attack can also be handled by our framework but is left as future works.

Black-box Certification with Randomness Directly verifying f heavily relies on the smoothness of f , 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 f , 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 enable this, as explored in recent works (Cohen et al., 2019; Lee et al., 2019) , is to replace f with a smoothed classifier by convovling with Gaussian noise, and verify the smoothed classifier. Specifically, assume π 0 is a smoothing distribution with zero mean and bounded variance, e.g., π 0 = N (0, σ 2 ). The randomized smoothed classifier is defined by

f π0 (x 0 ) := E z∼π0 f (x 0 + z) ,

which returns the averaged probability of x 0 + z under the perturbation of z ∼ π 0 . Assume we replace the original classifier with f π0 , then the goal becomes verifying f π0 using its inherent smoothness. Specifically, if f π0 (x 0 ) > 1/2, we want to verify that f π0 (x 0 + δ) > 1/2 for every δ ∈ B, that is,

min δ∈B f π0 (x 0 + δ) = min δ∈B E z∼π0 [f (x 0 + z + δ)] > 1/2.

(1)

In this case, it is sufficient to obtain a guaranteed lower bound of min δ∈B f π0 (x 0 + δ) and check if it is larger than 1/2. When π 0 is Gaussian N (0, σ 2 ) and for 2 attack, this problem was studied in Cohen et al. (2019) , which shows that a lower bound of

EQUATION

where Φ(•) is the cumulative density function (CDF) of standard Gaussian distribution, and Φ -1 (•) represents its inverse function. The proof of this result in Cohen et 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 ( 2) is tractable since it only requires to evaluate the smoothed classifier f π0 (x 0 ) at the original image x 0 , instead of solving the difficult adversarial optimization over perturbation z in Equation (1). In practice, f π0 (x 0 ) is approximated by Monte Carlo approximation with a non-asymptotic confidence bound.

3.1. VARIATIONAL ADVERSARIAL CERTIFICATION:

We propose a variational adversarial certification (AVC) framework, which yields a guaranteed lower bound for Equation (1) based on variational optimization. The main idea is simple: assume F is a function class which is known to include f , then the following optimization immediately yields a guaranteed lower bound,

EQUATION

where we define f π0 (x 0 ) = E z∼π0 [f (x 0 + z)] for any f , and search for the minimum value of f π0 (x 0 + δ) for all classifiers in F and satisfies f π0 (x 0 ) = f π0 (x 0 ). This obviously yields a lower bound once f ∈ F. If F includes only f , then the bound is exact, but is computationally prohibitive due to the difficulty of optimizing δ. The idea is then to choose F properly to incorporate rich information of f , while allowing us to calculate the lower bound in Equation (3) computationally tractably. In this paper, we consider the set of all functions bounded in [0, 1], that is,

EQUATION

which guarantees to include f by definition. There are other F that also yields computationally tractable bounds, including the L p space F = {f : f Lp ≤ v}, which we leave for future work.

Denote by V π0 (F, B) the lower bound in Equation (3). We can rewrite it into the following minimax form using the Lagrangian function,

V π0 (F, B) = min f ∈F min δ∈B max λ∈R L(f, δ, λ) def = f π0 (x 0 + δ) -λ(f π0 (x 0 ) -f π0 (x 0 )) ,

where λ is the Lagrangian multiplier. Exchanging the min and max yields the following dual form. Theorem 1. I) (Dual Form) Denote by π δ the distribution of z + δ when z ∼ π 0 . Assume F and B are compact set. We have the following dual form of V π0 (F, B) via strong duality:

EQUATION

where we define

D F (λπ 0 π δ ) = max f ∈F {λE z∼π0 [f (x 0 + z)] -E z∼π δ [f (x 0 + z)]} ,

which measures the difference of λπ 0 and π δ by seeking the maximum discrepancy of the expectation for f ∈ F. As we show later, the bound in ( 5) is computationally tractable with proper (F, B, π 0 ).

II) When F = F [0,1] := {f : f (x) ∈ [0, 1], x ∈ R d }, we have in particular D F [0,1] (λπ 0 π δ ) = (λπ 0 (z) -π δ (z)) + dz,

where (t) + = max(0, t).

In addition, we have 0 ≤ D F [0,1] (λπ 0 π δ ) ≤ λ for any π 0 , π δ and λ > 0. Note that D F [0,1] (λπ 0 π δ ) coincides with the total variation distance between π 0 and π δ when λ = 1.

III) Suppose F = F [0,1] and suppose that for any λ ≥ 0, min δ∈B min f ∈F [0,1] L (f, δ, λ) = min f ∈F [0,1] L (f, δ * , λ), for some δ * ∈ B, we have V π0 (F, B) = max λ≥0 min δ∈B min f ∈F L (f, δ, λ) .

Remark We will show later that the proposed methods and the cases we study satisfy the condition in part III of the theorem and thus all the lower bounds of the proposed method are tight.

Proof. First, observe that the constraint in Equation ( 3) can be equivalently replaced by an inequality constraint f π0 (x 0 ) ≥ f π0 (x 0 ). Therefore, the Lagrangian multiplier can be restricted to be λ ≥ 0.

We have

V (F, B) = min δ∈B min f ∈F max λ≥0 E π δ [f (x 0 + z)] + λ f π0 (x 0 ) -E π0 [f (x 0 + z)] ≥ max λ≥0 min δ∈B min f ∈F E π δ [f (x 0 + z)] + λ f π0 (x 0 ) -E π0 [f (x 0 + z)] //exchange min and max = max λ≥0 min δ∈B λf π0 (x 0 ) + min f ∈F E π δ [f (x 0 + z)] -λE π0 [f (x 0 + z)]) = max λ≥0 min δ∈B λf π0 (x 0 ) -D F (λπ 0 π δ )

The proof of the strong duality is in Appendix A.1. II) follows a straightforward calculation.

Although the lower bound in Equation ( 5) still involves an optimization on δ and λ, both of them are much easier than the original adversarial optimization in Equation ( 1 (2019) , that is, Trade-off between Accuracy and Robustness The lower bound in Equation ( 5) reflects an intuitive trade-off between the robustness and accuracy,

EQUATION

EQUATION

where the first term reflects the accuracy of the smoothed classifier (assuming the true label is y = 1), while the second term max δ∈B D F (λπ 0 π δ ) measures the robustness of the smoothed classifier, via the maximum difference between the original smoothing distribution π 0 and perturbed distribution π δ for δ ∈ 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 between accuracy and robustness in Equation ( 7). If π 0 has large variance or high tail probability, the distance D F (λπ 0 π δ ) will tend to be large and the model is robust. However, if the variance of π 0 is too large, we may obtain a low value of f π0 (x 0 ) and hence less accurate model. The optimal choice of the smoothing distribution should optimally balance the accuracy and robustness, by distribute its mass properly to yield small max δ∈B D F (λπ 0 π δ ) and large f π0 (x 0 ) simultaneously.

4. 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 concentrates on a sphere far away from the center points in high dimensional spaces. Motivated by this observation, we propose in Section 4.1 a new family of non-Gaussian smoothing distributions that alleviate this problem for 2 attack, and also in Section 4.2 another mixed norm smoothing distribution designed specifically for ∞ attack.

4.1. 2 REGION CERTIFICATION:

Although isotropic Gaussian distributions appears to be a 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). Let z ∼ N (0, I d×d ) be a d-dimensional standard Gaussian random variable. Then there exists a constant c, such that for δ ∈ (0, 1),

Prob √ d -c log(2/δ) ≤ z 2 ≤ √ d + c log(2/δ) ≥ 1 -δ.

This suggests that with high probability (e.g, 1-δ = 0.99), z takes values very close to the sphere of radius √ d, 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 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). To illustrate the problem, consider a simple example when the true classifier is f (x) = I( xx 0 2 ≤ √ d) for a constant < 1, where I is the indicator function. Then when the dimension d is large, we would have f (x 0 ) = 1 while f π0 (x 0 ) ≈ 0 when π 0 = N (0, I d×d ). It is of course possible to decrease the variance of π 0 to improve the accuracy of the smoothed classifier f π0 . 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 a new family of non-Gaussian distributions to address this curse of dimensionality. 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 is a spherically symmetric random variable on R d with a probability density function (PDF) of form π 0 (z) ∝ φ( z 2 ), where φ : [0, ∞) → [0, ∞) is a univariate function, then the PDF of the norm of z is p z 2 (r) ∝ r d-1 φ(r). The term r d-1 arises due to the integration on the sphere of radius r in R d .

In particular, when z ∼ π 0 = N (0, σ 2 I d×d ), we have φ(r) = exp(-r 2 /(2σ 2 )) and hence p z 2 (r) ∝ r d-1 exp(-r 2 /(2σ 2 )), which is a 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 r d-1 term, which makes the density to be highly peaked when d is large. To alleviate the concentration phenomenon, we need to have a way to cancel out the effect of r d-1 . This motivates the following family of smoothing distributions:

π 0 (z) ∝ z -k 2 exp - z 2 2 2σ 2 ,

and hence

EQUATION

)

where we introduce a z -k 2 term in π 0 , with k a positive parameter, to make the radius distribution less concentrated when k is large. 8) with d = 100 σ = 1 and k = 0 (black start), increasing k (green curve) allows us to move the mean towards zero without significantly reducing the variance. Decreasing σ (red curve) can also decrease the mean, but with a cost of decreasing the variance quadratically.

The radius distribution in Equation ( 8) is controlled by two parameters (σ, k), where σ controls the scale of the distribution (and is hence the scale parameter), while k controls the shape of the distribution (and hence the shape parameter). The key idea is that adjusting k allows us to trade-off the accuracy and robustness much more optimally. As shown in Figure 1 , adjusting σ enables us to move the mean close to zero (hence yielding higher accuracy), but at cost of decreasing the variance quadratically (hence more less robust). In contrast, adjusting k allows us to decrease the mean without significantly impacting the variance, and hence yield a much better trade-off on the accuracy and robustness.

Computational Method With the more general non-Gaussian smoothing distribution, we 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 π 0 in Equation (8). The key is that the maximum of the distance term D F [0,1] (λπ 0 || π δ ) over δ ∈ B is always achieved on the boundary of B as we show in the sequel, while the optimization on λ ≥ 0 is one-dimensional and can be solved numerically efficiently. Theorem 2. Consider the 2 attack with B = {δ : δ 2 ≤ r} and smoothing distribution π 0

(z) ∝ z -k 2 exp - z 2 2 2σ 2

with k ≥ 0 and σ > 0. Define δ * = [r, 0, ..., 0] , we have

D F [0,1] (λπ 0 π δ * ) = max δ∈B D F [0,1] (λπ 0 π δ ) .

With Theorem 2, we can compute Equation ( 5) with δ = δ * . We then calculate D F [0,1] (λπ 0 π δ * ) using Monte Carlo approximation. Note that

D F [0,1] (λπ 0 π δ * ) = (λπ 0 (z) -π δ * (z)) + dz = E z∼π0 λ - π δ * (z) π 0 (z) + ,

which can be approximated with Monte Carlo method with Hoeffding concentration bound.

Let {z i } n i=1 be an i.i.d. sample from π 0 , then we can approximate 2n), D + λ log(2/δ)/(2n)] with probability 1 -δ for δ ∈ (0, 1). Drawing sufficiently large number of samples allows us to achieve approximation with arbitrary accuracy.

D F [0,1] (λπ 0 π δ * ) with D := n -1 n i=1 (λ -π δ * (z i )/π 0 (z i )) + . Because 0 ≤ (λ -π δ * (z i )/π 0 (z i )) + ≤ λ, we have D F [0,1] (λπ 0 π δ * ) ∈ [ D -λ log(2/δ)/(

4.2. ∞ REGION CERTIFICATION:

Going beyond the 2 attack, we consider the ∞ attack, whose attacking region is B ∞ ,r = {δ : δ ∞ ≤ r}. This is a far more difficult problem, because the ∞ ball is substantially larger than the 2 ball of the same radius in high dimensional space. This makes the Gaussian smoothing distribution, as well as our 2 -based smoothing distribution in Equation ( 8), unsuitable for ∞ attack. In fact, as shown in the following negative result, if we use Equation ( 8) as the smoothing distribution for ∞ attack, the bound we obtain is effectively the bound we would get for verifying a 2 ball with radius √ dr, which is too large to give meaningful results when the dimension is high.

Theorem 3. With the smoothing distribution π 0 in Equation ( 8) for k ≥ 0, σ > 0, and

F = F [0,1]

shown in Equation ( 4), the bound we get for certifying the ∞ attack on B ∞,r = {δ : δ ∞ ≤ r} is equivalent to that for certifying the 2 attack on B 2, The key reason of this negative result is that the furthest points to the origin (vertexes) in B ∞ ,r have an 2 radius of √ dr, illustrated as the "pointy" points in Figure 2 . Thus, the maximum distance max δ∈B ∞ ,r D F (λπ 0 π δ ) is achieved at one of these pointy points, making it equivalent to optimizing in the 2 ball with radius

√ dr = {δ : δ 2 ≤ √ dr}, that is, V π0 (F [0,1] , B ∞,r ) = V π0 (F [0,1] , B 2 , √ dr ).

√:

dr.

In order to address this problem, we propose the following new mixed norm family of smoothing distribution that uses a mix of 2 and ∞ norms:

EQUATION

in which we replace the z

-k 2 term in Equation (8) with z -k ∞ .

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 ∞,r D F (λπ 0 π δ ). See Figure 2 for an illustration. In practice, we find that this mixed norm smoothing distribution in Equation ( 9) work much more efficiently than the 2 norm-based family in Equation (8).

Given the difference of 2 and ∞ norms, it is also natural to consider the following pure ∞ norm distributions, which uses ∞ norm in both of the terms of the distribution,

EQUATION

)

Unfortunately, this seemingly natural choice does not work efficiently for ∞ attacks (even worse than the 2 family Equation ( 8)). This is because the volume of the ∞ ball is in some sense "too large" (e.g., compared with the volume of 2 ball). As a result, in order to make the probability mass of Equation ( 10) in a reasonable scale, one has to choose a very small value of σ, which makes maximum distance term too large to be practically useful. Mixed `1 and `2 (Eq.9) Pure `1 (Eq.10)

TV Distance (Robustness)

Figure 4 : The Pareto frontier of accuracy and robustness (in the sense of Equation ( 7)) of the three smoothing families in Equation ( 8), Equation ( 9), and Equation ( 10) for ∞ attacking, when we search for the best parameters (k, σ) for each of them. The mixed norm family Equation ( 9) yields the best trade-off than the other two. We assume f (x) = I( x 2 ≤ r) and dimension d = 5. The case when f (x) = I( x ∞ ≤ r) has similar result (not shown).

Theorem 4. Consider the adversarial attacks on the ∞ ball B ∞ ,r = {δ : δ ∞ ≤ r}. Suppose we use the smoothing distribution π 0 in Equation ( 10) and choose the parameters (k, σ) such that 1) z ∞ is stochastic bounded when z ∼ π 0 , in that for any > 0, there exists a finite M > 0 such that P π0 (|z| > M ) ≤ ;

2) the mode of z ∞ under π 0 equals Cr, where C is some fixed positive constant, then for any ∈ (0, 1) and sufficiently large dimension d, there exists a constant t > 1, such that , we have

max δ∈B ∞ ,r D F [0,1] (λπ 0 π δ ) ≥ (1 -) λ -O(t -d ) .

This shows that, in very high dimensions, the maximum distance term is arbitrarily close to λ which is the maximum possible value of D F [0,1] (λπ 0 π δ ) (see Theorem 1). In particular, this implies that in high dimensional scenario, once f π0 (x 0 ) ≤ (1 -) for some small , we have V π0 (F [0,1] , B ∞,r ) = O(t -d ) and thus fail to certify.

Remark The condition 1) and 2) in Theorem 4 are used to ensure that the magnitude of the random perturbations generated by π 0 is within a reasonable range such that the value of f π0 (x 0 ) is not too small, in order to have a high accuracy in the trade-off in Equation ( 7). Note that the natural images are often contained in cube [0, 1] d . If z ∞ is too large to exceed the region of natural images, the accuracy will be obviously rather poor. Note that if we use variants of Gaussian distribution, we only need ||z|| 2 / √ d to be not too large. Theorem 4 says that once z ∞ is in a reasonably small scale, the maximum distance term must be unreasonably large in high dimensions, yielding a vacuous lower bound.

Empirical Justification We construct a simple toy example to verify the advantages of the mixed norm family Equation ( 9) overall the 2 family in Equation ( 8) and the ∞ family in Equation ( 10). We assume that the true classifier is f (x) = I( x 2 ≤ r) in r = 0.65, d = 5 case and plot in Figure 4 the Pareto frontier of the accuracy and robustness terms in Equation (7) for the three families of smoothing distributions, as we search for the best combinations of parameters (k, σ). We can see that the mixed norm smoothing distribution clearly obtain the best trade-off on accuracy and robustness, and hence guarantees a tighter lower bound for certification.

Computational Method:

In order to compute the lower bound when using the mixed norm family Equation ( 9), we need to establish the closed form solution of the maximum distance term max δ∈B D F [0,1] (λπ 0 || π δ ) similar to Theorem 2. The following result shows that the optimal δ is achieved at one vertex (the pointy points) of the ∞ ball. Theorem 5. Consider the ∞ attack with B ∞,r = {δ : δ ∞ ≤ r} and the mixed norm smoothing distribution in Equation ( 9) with k ≥ 0 and σ > 0. Define δ * = [r, r, ..., r] . We have for any 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. ( 2019 

λ > 0, D F [0,1] (λπ 0 π δ * ) = max δ∈B D F [0,1] (λπ 0 π δ ) .

The proof of Theorem 2 and 5 is non-trivial, thus we defer the details to Appendix A.3. With the optimal δ * found above, we can calculate the bound with similar Monte Carlo approximation outlined in Section 4.1.

5. EXPERIMENTS:

We evaluate our new bound and smoothing distributions for both 2 and ∞ attacks. We compare with the randomized smoothing method of Cohen et al. ( 2019 

Settings and Hyperparameters:

The details of our method are shown in Algorithm 2 in Appendix.

Since our method requires Monte Carlo approximation, we draw 0.1M samples from π 0 and construct α = 99.9% confidence lower bounds of that in Equation ( 7). The optimization on λ is solved using grid search. For 2 attacks, we set k = 500 for CIFAR10 and k = 50000 for ImageNet in our non-Gaussian smoothing distribution Equation ( 8). If the used model was trained with a Gaussian perturbation noise of N (0, σ 2 0 ), then the σ parameter of our smoothing distribution is set to be (d -1)/(d -1 -k)σ 0 , such that the expectation of the norm z 2 under our non-Gaussian distribution Equation ( 8) matches with the norm of N (0, σ 2 0 ). For ∞ situation, we set k = 250 and σ also equals to (d -1)/(d -1 -k)σ 0 for the mixed norm smoothing distribution Equation ( 9). In both cases, the baseline algorithm uses a Gaussian smoothing distribution N (0, σ 2 0 ). More ablation study about k is deferred to Appendix C.

Evaluation Metrics:

The methods are evaluated using the certified accuracy defined in Cohen et al. (2019) . Given an input image x and a 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 δ ∈ 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 et al. (2019) for various radius, and report the best results over all of classifiers.

5.1. 2 CERTIFICATION:

We test our method on CIFAR10 and ImageNet for 2 certification. For fair comparison, we use the same pre-trained models as Cohen et al. (2019) , which is trained with Gaussian noise on both CI-FAR10 and ImageNet dataset. The readers are referred to Appendix C for detailed ablation studies.

Table 1 and Table 2 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 our method consistently outperforms the baseline. 

Gaussian Ours:

∞ radius × 255 Figure 5 : Results of ∞ verification on CIFAR10, on models trained with Gaussian noise data augmentation with different variances σ 0 . Our method obtains consistently better results.

5.2. ∞ CERTIFICATION:

We test our lower bound based on the mixed norm family in Equation ( 9) for verifying ∞ attacking on CIFAR10, using the models trained by Salman et al. (2019) . The certified accuracy of our method and the baseline using Gaussian smoothing distribution are shown in Table 3 . We can see that our method consistently outperforms the Gaussian distribution baseline by a large margin, which empirically shows our distribution is a more suitable distribution for ∞ perturbation.

To further confirm the advantage of our method, we plot in Figure 5 the certified accuracy of our method and Gaussian baseline using models trained with Gaussian perturbation of different variances σ 0 , under different ∞ radius. We again find that our approach outperforms the baseline 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 ∞ verification is extremely hard with very large dimensions. Future work will investigate how to obtain non-trivial bounds for ∞ attacking at ImageNet scales with smoothing classifiers.

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 δ * , we have

max λ∈R min f ∈F [0,1] E π δ * [f (x 0 + z)] + λ f π0 (x 0 ) -E π0 [f (x 0 + z)] = max λ∈R min f ∈F [0,1] E π δ * [f (x 0 + z)] + λ f π0 (x 0 ) -E π0 [f (x 0 + z)] .

The proof of Lemma 3 is standard. However, for completeness, we include it here.

Proof. Without loss of generality, we assume f π0 (x 0 ) ∈ (0, 1), otherwise the feasible set is trivial.

Let α * be the value of the optimal solution of the primal problem. We define

f π0 (x 0 ) - E π0 [f (x 0 + z)] = h[f ] and g[f ] = E π δ * [f (x 0 + z)].

We define the following two sets:

A = (v, t) ∈ R × R : ∃f ∈ F [0,1] , h[f ] = v, g[f ] ≤ t B = {(0, s) ∈ R × R : s < α * } .

Notice that both sets A and B are convex. This is obvious for B. For any

(v 1 , t 1 ) ∈ A and (v 2 , t 2 ) ∈ A, we define f 1 ∈ F [0,1] such that h[f 1 ] = v 1 , g[f 1 ] ≤ t 1 (

and similarly we define f 2 ). Notice that for any γ ∈ [0, 1], we have

γf 1 + (1 -γ)f 2 ∈ F [0,1] γh[f 1 ] + (1 -γ)h[f 2 ] = γv 1 + (1-γ)v 2 γg[f 1 ] + (1 -γ)g[f 2 ] ≤ γt 1 + (1 -γ)t 2 ,

which implies that γ(v 1 , t 1 ) + (1 -γ)(v 2 , t 2 ) ∈ A and thus A is convex. Also notice that by definition, A ∩ B = ∅. Using separating hyperplane theorem, there exists a point (q 1 , q 2 ) = (0, 0) and a value α such that for any (v, t) ∈ A, q 1 v + q 2 t ≥ α and for any (0, s) ∈ B, q 2 s ≤ α. Notice that we must have q 2 ≥ 0, otherwise, for sufficient s, we will have q 2 s > α. We thus have, for any f ∈ F [0,1] , we have

q 1 h[f ] + q 2 g[f ] ≥ α * ≥ q 2 α * .

If q 2 > 0, we have

max λ∈R min f ∈F [0,1] g[f ] + λh[f ] ≥ min f ∈F [0,1] g[f ] + q 1 q 2 h[f ] ≥ α * ,

which gives the strong duality. If q 2 = 0, we have for any f ∈ F [0,1] , q 1 h[f ] ≥ 0 and by the separating hyperplane theorem, q 1 = 0. However, this case is impossible:

If q 1 > 0, choosing f ≡ 1 gives q 1 h[f ] = q 1 f π0 (x 0 ) -1 < 0; If q 1 < 0, by choosing f ≡ 0, we have q 1 h[f ] = q 1 f π0 (x 0 ) -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 δ∈B min f ∈F [0,1] max λ∈R E π δ [f (x 0 + z)] + λ f π0 (x 0 ) -E π0 [f (x 0 + z)] ,

and the dual problem is

max λ∈R min δ∈B min f ∈F [0,1] E π δ [f (x 0 + z)] + λ f π0 (x 0 ) -E π0 [f (x 0 + z)] = max λ≥0 min δ∈B min f ∈F [0,1] E π δ [f (x 0 + z)] + λ f π0 (x 0 ) -E π0 [f (x 0 + z)] .

By the assumption that for any λ ≥ 0, we have

max λ≥0 min δ∈B min f ∈F [0,1] E π δ [f (x 0 + z)] + λ f π0 (x 0 ) -E π0 [f (x 0 + z)] = max λ≥0 min f ∈F [0,1] E π δ * [f (x 0 + z)] + λ f π0 (x 0 ) -E π0 [f (x 0 + z)] ,

for some δ * ∈ B. We have

max λ∈R min δ∈B min f ∈F [0,1] E π δ [f (x 0 + z)] + λ f π0 (x 0 ) -E π0 [f (x 0 + z)] = max λ≥0 min f ∈F [0,1] E π δ * [f (x 0 + z)] + λ f π0 (x 0 ) -E π0 [f (x 0 + z)] = max λ∈R min f ∈F [0,1] E π δ * [f (x 0 + z)] + λ f π0 (x 0 ) -E π0 [f (x 0 + z)] * = min f ∈F [0,1] max λ∈R E π δ * [f (x 0 + z)] + λ f π0 (x 0 ) -E π0 [f (x 0 + z)] ≥ min δ∈B min f ∈F [0,1] max λ∈R E π δ * [f (x 0 + z)] + λ f π0 (x 0 ) -E π0 [f (x 0 + z)] ,

where the second equality (*) is by Lemma 3.

A.2 PROOF FOR COROLLARY 1:

Proof. Given our confidence lower bound

min δ 2≤r max λ≥0 λp 0 -(λπ 0 (z) -π µ (z)) + dz , define C λ = {z : λπ 0 (z) ≥ π δ (z)} = {z : δ z ≤ δ 2

2 + σ 2 ln λ} and Φ(•) to be the cdf of standard gaussian distribution, then

(λπ 0 (z) -π δ (z)) + dz = C λ (λπ 0 (z) -π δ (z)) dz =λ • P N (z; 0, σ 2 I) ∈ C λ -P N (z; δ, σ 2 I) ∈ C λ =λ • Φ δ 2 2σ + σ ln λ δ 2 -Φ -δ 2 2σ + σ ln λ δ 2 . Define F (δ, λ) := λp 0 -(λπ 0 (z) -π δ (z)) + dz = λp 0 -λ•Φ δ 2 2σ + σ ln λ δ 2 +Φ -δ 2 2σ + σ ln λ δ 2 .

For ∀δ, F is a concave function w.r.t. λ, as F is actually a summation of many concave piece wise linear function. See Boyd & Vandenberghe (2004) for more discussions of properties of concave functions.

Define λδ = exp

2σ δ 2 Φ -1 (p0)-δ 2 2 2σ 2

, simple calculation can show ∂F (δ,λ) ∂λ

| λ= λδ = 0, which means min δ 2≤r max λ≥0 F (δ, λ) = min δ 2≤r F (δ, λ δ ) = min δ 2≤r 0 + Φ -δ 2 2σ + σ ln λδ δ 2 = min δ 2≤r Φ Φ -1 (p 0 ) - δ 2 σ = Φ Φ -1 (p 0 ) - r σ

This tells us min

δ 2≤r max λ≥0 F (δ, λ) > 1/2 ⇔ Φ Φ -1 (p 0 ) - r σ > 1/2 ⇔ r < σ • Φ -1 (p 0 )

, i.e. the certification radius is σ • Φ -1 (p 0 ). This is exactly the core theoretical contribution of Cohen et al. (2019) . This bound has a straight forward expansion for multi-class classification situations, we refer interesting readers to Appendix D.

A.3 PROOF FOR THEOREM 2 AND 5

In this subsection, we give the proof of theorem 2 and 5. Here we consider a more general smooth distribution π 0 (z) ∝ z

-k1 ∞ z -k2 2 exp - z 2 2

2σ 2 , for some k 1 , k 2 ≥ 0 and σ > 0. We first gives the following key theorem shows that D F [0,1] (λπ 0 π δ ) increases as |δ i | becomes larger for every dimension i. Theorem 6. Suppose π 0 (z) ∝ z

-k1 ∞ z -k2 2 exp - z 2 2

2σ 2 , for some k 1 , k 2 ≥ 0 and σ > 0, for any λ ≥ 0 we have

sgn(δ i ) ∂ ∂δ i D F [0,1] (λπ 0 π δ ) ≥ 0,

for any i ∈ {1, 2, ..., d}.

Theorem 2 and 5 directly follows the above theorem. Notice that in Theorem 2, as our distribution is spherical symmetry, it is equivalent to set B = δ : δ = [a, 0, ..., 0] , a ≤ r by rotating the axis.

Proof. Given λ, k 1 and k 2 , we define φ 1 (s) = s -k1 , φ 2 (s) = s -k2 e -s 2 σ 2 . Notice that φ 1 and φ 2 are monotone decreasing for non-negative s. By the symmetry, without loss of generality, we assume

δ = [δ 1 , ..., δ d ] for δ i ≥ 0, i ∈ [d]. Notice that ∂ ∂δ i x 0 -δ ∞ = I{ x 0 -δ ∞ = |x i -δ i |} ∂ ∂δ i (x i -δ i ) 2 = I{ x 0 -δ ∞ = |x i -δ i |} -(x i -δ i ) x 0 -δ ∞ .

And also

∂ ∂δ i x 0 -µ 2 = ∂ ∂δ i i (x i -µ i ) 2 = -(x i -µ i ) x 0 -µ 2 .

We thus have

∂ ∂δ 1 (λπ 0 (x 0 ) -π δ (x 0 )) + dx 0 = -I {λπ 0 (x 0 ) ≥ π δ (x 0 )} ∂ ∂δ 1 π δ (x 0 )dx 0 = I {λπ 0 (x 0 ) ≥ π δ (x 0 )} F 1 ( x 0 -δ ∞ , x 0 -δ 2 ) dx 0 = I {λπ 0 (x 0 ) ≥ π δ (x 0 ), x 1 > µ 1 } F 1 ( x 0 -δ ∞ , x 0 -δ 2 ) dx 0 + I {λπ 0 (x 0 ) ≥ π δ (x 0 ), x 1 < µ 1 } F 1 ( x 0 -δ ∞ , x 0 -δ 2 ) dx 0 ,

where we define

F 1 ( x 0 -δ ∞ , x 0 -δ 2 ) = φ 1 ( x 0 -δ ∞ ) φ 2 ( x 0 -δ 2 ) I{ x 0 -δ ∞ = |x 1 -δ 1 |} (x 1 -δ 1 ) x 0 -δ ∞ + φ 1 ( x 0 -µ ∞ ) φ 2 ( x 0 -µ 2 ) (x 1 -µ 1 ) x 0 -µ 2 .

Notice that as φ 1 ≤ 0 and φ 2 ≤ 0 and we have

I {λπ 0 (x 0 ) ≥ π δ (x 0 ), x 1 > δ 1 } F 1 ( x 0 -δ ∞ , x 0 -δ 2 ) dx 0 ≤ 0 I {λπ 0 (x 0 ) ≥ π δ (x 0 ), x 1 < δ 1 } F 1 ( x 0 -δ ∞ , x 0 -δ 2 ) dx 0 ≥ 0.

Our target is to prove that ∂ ∂δ1 (λπ 0 (x 0 ) -π δ (x 0 )) + dx 0 ≥ 0. Now define the set

H 1 = {x 0 : λπ 0 (x 0 ) ≥ π δ (x 0 ), x 1 > µ 1 } H 2 = [2δ 1 -x 1 , x 2 , ..., x d ] : x 0 = [x 1 , ..., x d ] ∈ H 1 . Here the set H 2 is defined as a image of a bijection proj(x 0 ) = [2δ 1 -x 1 , x 2 , ..., x d ] = x0

, that is constrained on the set H 1 . Notice that under our definition,

I {λπ 0 (x 0 ) ≥ π δ (x 0 ), x 1 > δ 1 } F 1 ( x 0 -δ ∞ , x 0 -δ 2 ) dx 0 = H1 F 1 ( x 0 -δ ∞ , x 0 -δ 2 ) dx 0 .

Now we prove that:

I {λπ 0 (x 0 ) ≥ π δ (x 0 ), x 1 < δ 1 } F 1 ( x 0 -δ ∞ , x 0 -δ 2 ) dx 0 (1) ≥ H2 F 1 ( x 0 -δ ∞ , x 0 -δ 2 ) dx 0 (2) = H1 F 1 ( x 0 -δ ∞ , x 0 -δ 2 ) dx 0 .

Property of the projection Before we prove the (1) and (2), we give the following property of the defined projection function. For any x0 = proj(x 0 ), x 0 ∈ H 1 , we have

x 0 -δ ∞ = x0 -δ ∞ x 0 -δ 2 = x0 -δ 2 x 0 2 ≥ x0 2 x 0 ∞ ≥ x0 ∞ . This is because xi = x i , i ∈ [d] -{1} x1 = 2δ 1 -x 1 , and by the fact that x 1 ≥ δ 1 ≥ 0, we have |x 1 | ≤ |x 1 | and |x 1 -δ 1 | ≤ |x 1 -δ 1 |.

Proof of Equality (2) By the fact that proj is bijective constrained on the set H 1 and the property of proj, we have

H2 F 1 ( x0 -δ ∞ , x0 -δ 2 ) d x0 = H2 φ 1 ( x0 -δ ∞ ) φ 2 ( x0 -δ 2 ) I{ x0 -δ ∞ = |x 1 -δ 1 |} (x 1 -δ 1 ) x0 -δ ∞ d x0 + H2 φ 1 ( x0 -δ ∞ ) φ 2 ( x0 -δ 2 ) (x 1 -δ 1 ) x0 -δ 2 d x0 ( * ) = H1 φ 1 ( x 0 -δ ∞ ) φ 2 ( x 0 -δ 2 ) I{ x 0 -δ ∞ = |x 1 -δ 1 |} (δ 1 -x 1 ) x 0 -δ ∞ |det (J )| dx 0 + H1 φ 1 ( x 0 -δ ∞ ) φ 2 ( x 0 -δ 2 ) (δ 1 -x 1 ) x 0 -δ 2 dx 0 = - H1 F 1 ( x 0 -δ ∞ , x 0 -δ 2 ) dx 0 ,

where ( * ) is by change of variable x0 = proj(x 0 ) and J is the Jacobian matrix

J =     -1 0 • • • 0 0 1 • • • 0 . . . . . . . . . . . . 0 0 • • • 1   

 and here we have the fact that x1 -δ 1 = (2δ 1 -x 1 ) -δ 1 = -(x 1 -δ 1 ).

Proof of Inequality (1) This can be done by verifying that H 2 ⊆ {x 0 : λπ 0 (x 0 ) ≥ π δ (x 0 ), x 1 < δ 1 }. By the property of the projection, for any x 0 ∈ H 1 , let x0 = proj(x 0 ), then λπ 0 ( x0 ) ≥ λπ 0 (x 0 ) ≥ π δ (x 0 ) = π δ ( x0 ) (by the fact that t φ 1 and φ 2 are monotone decreasing). It implies that for any x0 ∈ H 2 , we have λπ 0 ( x0 ) ≥ π δ ( x0 ) and thus

H 2 ⊆ {x 0 : π 0 (x 0 ) ≥ π δ (x 0 ), x 1 < δ 1 }.

Final statement By the above result, we have

∂ ∂δ 1 (λπ 0 (x 0 ) -π µ (x 0 )) + dx 0 ≥ 0,

and the same result holds for any ∂ ∂δ1

(λπ 0 (x 0 ) -π µ (x 0 )) + dx 0 , i ∈ [d],

which implies our result.

A.3.1 PROOF FOR THEOREM 4:

First notice that the distribution of z can be factorized by the following hierarchical scheme:

a ∼ π R (a) ∝ a d-1-k e -a 2 2σ 2 I{a ≥ 0} s ∼ Unif ⊗d (-1, 1) z ← s s ∞ a.

Without loss of generality, we assume δ * = [r, ..., r] . (see Theorem 6)

D F [0,1] (λπ 0 π δ * ) = E z∼π0 λ - π δ π 0 (z) + .

Notice that as the distribution is symmetry, i) is the i-th order statistics of |z j |, j = 1, ..., d conditioning on z ∞ = a. By the factorization above and some algebra, we have, for any ∈ (0, 1), P |z|

EQUATION

(d-1) |z| (d) > (1 -) | z ∞ = a ≥ 1 -(1 -) d-1 . And |z| (d-1) |z| (d) ⊥ |z| (d) . Now we estimate D F [0,1] (λπ 0 π δ * ). E z∼π0 λ - π δ π 0 (z) + =E a E z∼π0 λ - π δ π 0 (z) + | z ∞ = a = 1 2 E a E z∼π0 λ - π δ π 0 (z) + | z ∞ = a, z + δ * ∞ = a + r + 1 2 E a E z∼π0 λ - π δ π 0 (z) + | z ∞ = a, z + δ * ∞ = a + r . Conditioning on z ∞ = a, z + δ * ∞ = a + r, we have π δ π 0 (z) = 1 1 + r a k e -1 2σ 2 (2ra+r 2 ) = 1 1 + r a k e -d-1-k 2C 2 (2 a r +1) .

Here the second equality is because we choose mode( z ∞ ) = Cr, which implies that √ d -1 -kσ = Cr. And thus we have

E a E z∼π0 λ - π δ π 0 (z) + | z ∞ = a, z + δ * ∞ = a + r = λ - 1 1 + r a k e -d-1-k 2C 2 (2 a r +1) + π(a)da = λ -1 + r a -k e 2a/r+1 2C 2 -(d-1-k) + π(a)da =λ -O(t -d ),

for some t > 1. Here the last equality is by the assumption that z ∞ = O p (1).

Next we bound the second term And thus, for any ∈ [0, 1),

E a E z∼π0 λ -π δ π0 (z) + | z ∞ = a, z + δ * ∞ = a +

P z + δ * ∞ ≥ ((1 -)a + r) 2 | z ∞ = a, z + δ * ∞ = a + r ≥ 1 2 1 -(1 -) d-1 .

It implies that

E z∼π0 λ - π δ π 0 (z) + | z ∞ = a, z + δ * ∞ = a + r ≥ 1 2 1 -(1 -) d-1 λ -1 -+ r a -k

e -1 2σ 2 ( ( -2)a 2 +2r(1-)a+r 2 )

+ = 1 2 1 -(1 -) d-1 λ -1 -+ r a

-k e -d-1-k 2C 2 ( ( -2)a 2 /r 2 +2(1-)a/r+1) + .

For any ∈ (0, 1), by choosing = log(2/ ) d-1 , for large enough d, we have 

E z∼π0 λ - π δ π 0 (z) + | z ∞ = a, z + δ * ∞ = a + r ≥ 1 2 1 -(1 -) d-1 λ -1 -+ r a -k e -d-1-k 2C 2 (2(1-)a/r+1)

C ABALATION STUDY:

On CIFAR10, we also do ablation study to show the influence of different k for the 2 certification case as shown in Table 4 .

2 RADIUS (CIFAR-10) 0.25 0.5 0.75 1.0 1.25 1. 

D ILLUMINATION ABOUT BILATERAL CONDITION:

The results in the main context is obtained under binary classfication setting. Here we show it has a natural generalization to multi-class classification setting. Suppose the given classifier f classifies an input x 0 correctly to class A, i.e.,

EQUATION

where f B (x 0 ) denotes the prediction confidence of any class B different from ground truth label A. Notice that f A (x 0 ) + B =A f B (x 0 ) = 1, so the necessary and sufficient condition for correct binary classification f A (x 0 ) > 1/2 becomes a sufficient condition for multi-class prediction.

Similarly, the necessary and sufficient condition for correct classification of the smoothed classifier is 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 we do not use this bilateral formulation as reasons stated below.

When both π 0 and π δ are gaussian, which is Cohen et al. ( 2019)'s setting, this condition is equivalent to:

min δ∈B Φ Φ -1 (f π0 ,A (x 0 )) - δ 2 σ -max B =A Φ Φ -1 (f π0 ,B (x 0 )) + δ 2 σ > 0 ⇔ Φ -1 (f π0 ,A (x 0 )) - r σ > Φ -1 (f π0 ,B (x 0 )) + r σ , ∀B = A ⇔ r < σ 2

Φ -1 (f π0 ,A (x 0 )) -Φ -1 (f π0 ,B (x 0 )) , ∀B = A with a similar derivation process like Appendix A.2. This is exactly the same bound in the (restated) theorem 1 of Cohen et al. (2019) .

Cohen et al. ( 2019) use 1 -p A as a naive estimate of the upper bound of f π0 ,B (x 0 ), where p A is a lower bound of f π0 ,A (x 0 ). This leads the confidence bound decay to the bound one can get in binary case, i.e., r ≤ σΦ -1 (f π0 ,A (x 0 )).

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

:



Figures and Tables:

). With proper choices of F, B and π 0 , 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 a corollary of Theorem 1, we can exactly recover the bound derived byCohen et al. (2019). Corollary 1. With isotropic Gaussian noise π 0 = N (0, σ 2 I d×d ), 2 attack B = {δ : δ 2 ≤ r} and F = F [0,1] , the lower bound in Equation (5) equals the bound in Equation (2) by Cohen et al.

) See Appendix A.2 for more details. A key step of the proof is to show that max δ 2≤r D F [0,1] (λπ 0 π δ ) is achieved when δ is on the boundary of the 2 ball B = { δ 2 ≤ r}, which can be, for example, δ = [r, 0, . . . , 0] , due to symmetry of B (see figure on the right).

Figure 1: Starting from radius distribution in Equation (8) with d = 100 σ = 1 and k = 0 (black start), increasing k (green curve) allows us to move the mean towards zero without significantly reducing the variance. Decreasing σ (red curve) can also decrease the mean, but with a cost of decreasing the variance quadratically.

Figure 2: ∞ and 2 balls in high dimension.

Figure3: For ∞ attacking, the mixed norm distribution (right) yields smaller TV distances (larger overlap areas), and hence higher robustness.

) with Gaussian smoothing distribution. For fair comparisons, we use the same model architecture and pre-trained models provided by Cohen et al. (2019) and Salman et al. (2019), which are ResNet110 on CIFAR10 and ResNet50 on ImageNet.

> (1 -) | z ∞ = a, z + δ * ∞ = a + r =P |z| (d-1) |z| (d) > (1 -) | z ∞ = a ≥1 -(1 -) d-1 .

-d-1-k 2C 2 (2(1-)a/r+1) e a 2 log(2/ ) C 2 r 2 + ≥ 1 2 (1 -) λ -1 -+ r a -k e -d-1-k 2C 2 (2(1-)a/r+1) e a 2 log(2/ ) C 2 r 2 + .

z∼π0 [f A (x 0 + δ + z)] s.t. E π0 [f A (x 0 )] = f π0 ,A (x 0 ) > max f ∈F E z∼π0 [f B (x 0 + δ + z)] s.t. E π0 [f B (x 0 )] = f π0 ,B (x 0 )for ∀B = A and any perturbation δ ∈ B. Writing out their Langragian forms makes things clear:max λ λf π0 ,A (x 0 ) -D F [0,1] (λπ 0 π δ ) > min λ max B =A λf π0 ,B (x 0 ) + D F [0,1] (π δ λπ 0 )Thus the overall necessary and sufficient condition ismin δ∈B max λ λf π0 ,A (x 0 ) -D F [0,1] (λπ 0 π δ ) -max B =A min λ λf π0 ,B (x 0 ) + D F [0,1] (π δ λπ 0 ) > 0

Certified top-1 accuracy of the best classifiers with various 2 radius on CIFAR-10.

Table content: <table><tr><td>) (%)</td><td>60</td><td>43</td><td>34</td><td>23</td><td>17</td><td>14</td><td>12</td><td>10</td><td>8</td></tr><tr><td>OURS (%)</td><td>61</td><td>46</td><td>37</td><td>25</td><td>19</td><td>16</td><td>14</td><td>11</td><td>9</td></tr><tr><td colspan="9">2 RADIUS (ImageNet) 0.5 1.0 1.5 1.0 2.0 2.5 3.0</td><td/></tr><tr><td colspan="2">Cohen et al. (2019) (%)</td><td colspan="6">49 37 29 19 15 12</td><td>9</td><td/></tr><tr><td>OURS (%)</td><td/><td colspan="7">50 39 31 21 17 13 10</td><td/></tr></table>

Certified top-1 accuracy of the best classifiers with various 2 radius on ImageNet.

Table content: <table/>

Certified top-1 accuracy of the best classifiers with various l ∞ radius on CIFAR-10.

Table content: <table><tr><td colspan="7">l ∞ RADIUS (CIFAR-10) 2/255 4/255 6/255 8/255 10/255 12/255</td></tr><tr><td>Salman et al. (2019) (%)</td><td>58</td><td>42</td><td>31</td><td>25</td><td>18</td><td>13</td></tr><tr><td>OURS (%)</td><td>60</td><td>47</td><td>38</td><td>32</td><td>23</td><td>17</td></tr></table>

Certified top-1 accuracy of the best classifiers at various 2 radius. We use the same model as Cohen et al. (2019) and do not train any new models.

Table content: <table><tr><td>5 1.75 2.0 2.25</td></tr></table>

Peer review (iclr2020):
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. Overall 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. Key issues: 1. 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. 2. 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). 3. The justification for why the particular smoothing distributions are good ideas is sketchy. I elaborate on 1 and 3 below. Addressing 1-3 effectively will improve my score. #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. #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. I 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). Minor 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. Writing 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).