Year: 2019

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.

heading: 1 INTRODUCTION
text: 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 nonGaussian 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.

heading: 2 RELATED WORKS
text: 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 Ré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 `∞.

heading: 3 BLACK-BOX CERTIFICATION WITH VARIATIONAL OPTIMIZATION
text: 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 ∈ Rd for simplicity. The extension to multi-class cases is straightforward, and is discussed in Appendix D. Assume f ] : Rd → [0, 1] is a pre-trained binary classifier (] 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 robustness certification problem, a testing data point x0 ∈ Rd is given, and one is asked to verify if the classifier outputs the same prediction when we perturb the input x0 arbitrarily in B, a given neighborhood of x0. Specifically, let B be a set of possible perturbation vectors, e.g., B = {δ ∈ Rd : ‖δ‖p ≤ r} for `p norm with a radius r. If the classifier predicts y = 1 on x0, i.e. f ](x0) > 1/2, we want to verify if f ](x0 + δ) > 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(x0) := Ez∼π0 [ f ](x0 + z) ] ,
which returns the averaged probability of x0 + 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(x0) > 1/2, we want to verify that f ] π0(x0 + δ) > 1/2 for every δ ∈ B, that is, min δ∈B f ]π0(x0 + δ) = minδ∈B Ez∼π0 [f ](x0 + z + δ)] > 1/2. (1)
In this case, it is sufficient to obtain a guaranteed lower bound of minδ∈B f ]π0(x0 + δ) 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
min z∈B
Ez∼π0 [f ](x0 + z)] ≥ Φ(Φ−1(f ]π0(x0))− r/σ), (2)
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 NeymanPearson 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(x0) at the original image x0, instead of solving the difficult adversarial optimization over perturbation z in Equation (1). In practice, f ]π0(x0) is approximated by Monte Carlo approximation with a non-asymptotic confidence bound.

heading: 3.1 VARIATIONAL ADVERSARIAL CERTIFICATION
text: 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,
min δ∈B f ]π0(x0 + δ) ≥ minf∈Fminδ∈B
{ fπ0(x0 + δ) s.t. fπ0(x0) = f ] π0(x0) } , (3)
where we define fπ0(x0) = Ez∼π0 [f(x0 + z)] for any f , and search for the minimum value of fπ0(x0 + δ) for all classifiers in F and satisfies fπ0(x0) = f ]π0(x0). 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,
F[0,1] = { f : f(z) ∈ [0, 1],∀z ∈ Rd } , (4)
which guarantees to include f ] by definition. There are other F that also yields computationally tractable bounds, including the Lp 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(x0 + δ)− λ(fπ0(x0)− f ]π0(x0))
} ,
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:
Vπ0(F ,B) ≥ max λ≥0 min f∈F min δ∈B L(f, δ, λ) = max λ≥0 { λf ]π0(x0)−maxδ∈B DF (λπ0 ‖ πδ) } , (5)
where we define
DF (λπ0 ‖ πδ) = max f∈F {λEz∼π0 [f(x0 + z)]− Ez∼πδ [f(x0 + 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 ∈ Rd}, we have in particular
DF[0,1] (λπ0 ‖ πδ) = ∫ (λπ0(z)− πδ(z))+ dz, where (t)+ = max(0, t).
In addition, we have 0 ≤ DF[0,1] (λπ0 ‖ πδ) ≤ λ for any π0, πδ and λ > 0. Note that DF[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δ∈Bminf∈F[0,1] L (f, δ, λ) = minf∈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(x0) ≥ f ]π0(x0). Therefore, the Lagrangian multiplier can be restricted to be λ ≥ 0. We have
V (F ,B) = min δ∈B min f∈F max λ≥0
Eπδ [f(x0 + z)] + λ ( f ]π0(x0)− Eπ0 [f(x0 + z)] ) ≥max
λ≥0 min δ∈B min f∈F
Eπδ [f(x0 + z)] + λ ( f ]π0(x0)− Eπ0 [f(x0 + z)] ) //exchange min and max
= max λ≥0 min δ∈B { λf ]π0(x0) + minf∈F Eπδ [f(x0 + z)]− λEπ0 [f(x0 + z)]) }
= max λ≥0 min δ∈B
{ λf ]π0(x0) − DF (λπ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). 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 by Cohen et al. (2019). Corollary 1. With isotropic Gaussian noise π0 = N (0, σ2Id×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. (2019), that is,
max λ≥0 { λf ]π0(x0)− max‖δ‖2≤r DF[0,1] (λπ0‖πδ) } = Φ(Φ−1(f ]π0(x0))− r/σ). (6)
See Appendix A.2 for more details. A key step of the proof is to show that max‖δ‖2≤r DF[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).
Trade-off between Accuracy and Robustness The lower bound in Equation (5) reflects an intuitive trade-off between the robustness and accuracy,
max λ≥0 [ λf ]π0(x0)︸ ︷︷ ︸ Accuracy −max δ∈B DF (λπ0 ‖ πδ)︸ ︷︷ ︸ Robustness ] , (7)
where the first term reflects the accuracy of the smoothed classifier (assuming the true label is y = 1), while the second term maxδ∈B DF (λπ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 DF (λπ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(x0) 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 DF (λπ0 ‖ πδ) and large f ]π0(x0) simultaneously.

heading: 4 FILLING THE SOAP BUBBLES: NEW FAMILIES OF NON-GAUSSIAN SMOOTHING DISTRIBUTIONS
text: 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.

heading: 4.1 `2 REGION CERTIFICATION
text: 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, Id×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(‖x− x0‖2 ≤ √ d) for a constant < 1, where I is the indicator function. Then when the dimension d is large, we would have f ](x0) = 1 while f ]π0(x0) ≈ 0 when π0 = N (0, Id×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 Rd 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 rd−1 arises due to the integration on the sphere of radius r in Rd.
In particular, when z ∼ π0 = N (0, σ2Id×d), we have φ(r) = exp(−r2/(2σ2)) and hence p‖z‖2(r) ∝ r
d−1 exp(−r2/(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 rd−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 rd−1. This motivates the following family of smoothing distributions:
π0(z) ∝ ‖z‖−k2 exp ( − ‖z‖22 2σ2 ) , and hence p‖z‖2(r) ∝ r d−k−1 exp ( − r 2 2σ2 ) , (8)
where we introduce a ‖z‖−k2 term in π0, with k a positive parameter, to make the radius distribution less concentrated when k is large.
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 nonGaussian 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
DF[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‖−k2 exp ( −‖z‖ 2 2 2σ2 ) with k ≥ 0 and σ > 0. Define δ∗ = [r, 0, ..., 0]>, we have
DF[0,1] (λπ0 ‖ πδ∗) = max δ∈B DF[0,1] (λπ0 ‖ πδ) .
With Theorem 2, we can compute Equation (5) with δ = δ∗. We then calculate DF[0,1] (λπ0 ‖ πδ∗) using Monte Carlo approximation. Note that
DF[0,1] (λπ0 ‖ πδ∗) = ∫ (λπ0(z)− πδ∗(z))+ dz = Ez∼π0 [( λ− πδ ∗(z)
π0(z) ) + ] ,
which can be approximated with Monte Carlo method with Hoeffding concentration bound. Let {zi}ni=1 be an i.i.d. sample from π0, then we can approximate DF[0,1] (λπ0 ‖ πδ∗) with D̂ := n−1 ∑n i=1 (λ− πδ∗(zi)/π0(zi))+. Because 0 ≤ (λ− πδ∗(zi)/π0(zi))+ ≤ λ, we have
DF[0,1] (λπ0 ‖ πδ∗) ∈ [D̂ − λ √ log(2/δ)/(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.

heading: 4.2 `∞ REGION CERTIFICATION
text: 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, √ dr = {δ : ‖δ‖2 ≤ √ dr}, that is,
Vπ0(F[0,1], B`∞,r) = Vπ0(F[0,1], B`2, √ dr).
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 DF (λπ0 ‖ πδ) is achieved at one of these pointy points, making it equivalent to optimizing in the `2 ball with radius √ 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:
π0(z) ∝ ‖z‖−k∞ exp ( − ‖z‖22 2σ2 )
, (9)
in which we replace the ‖z‖−k2 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 DF (λπ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,
π0(z) ∝ ‖z‖−k∞ exp ( − ‖z‖2∞ 2σ2 ) . (10)
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.
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

heading: 1) ‖z‖∞ is stochastic bounded when z ∼ π0, in that for any > 0, there exists a finite M > 0 such
text: 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
{ DF[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 DF[0,1] (λπ0 ‖ πδ) (see Theorem 1). In particular, this implies that in high dimensional scenario, once f ]π0(x0) ≤ (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(x0) 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 DF[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
λ > 0, DF[0,1] (λπ0 ‖ πδ∗) = max
δ∈B DF[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.

heading: 5 EXPERIMENTS
text: 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) 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.
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, σ20), 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, σ20). 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, σ20). 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.

heading: 5.1 `2 CERTIFICATION
text: 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 CIFAR10 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.

heading: 5.2 `∞ CERTIFICATION
text: 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.

heading: 6 CONCLUSIONS
text: We propose a general variational optimization based framework of adversarial certification with non-Gaussian smoothing distributions. Based on the insights from our new framework and high dimensional geometry, we propose two new families of non-Gaussian smoothing distributions, which significantly outperform the Gaussian-based smoothing for `2 and `∞ 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.

heading: A PROOFS
text: 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(x0 + z)] + λ ( f ]π0(x0)− Eπ0 [f(x0 + z)] ) = max
λ∈R min f∈F[0,1] Eπδ∗ [f(x0 + z)] + λ
( f ]π0(x0)− Eπ0 [f(x0 + z)] ) .
The proof of Lemma 3 is standard. However, for completeness, we include it here.
Proof. Without loss of generality, we assume f ]π0(x0) ∈ (0, 1), otherwise the feasible set is trivial.
Let α∗ be the value of the optimal solution of the primal problem. We define f ]π0(x0) − Eπ0 [f(x0 + z)] = h[f ] and g[f ] = Eπδ∗ [f(x0 + 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 setsA and B are convex. This is obvious for B. For any (v1, t1) ∈ A and (v2, t2) ∈ A, we define f1 ∈ F[0,1] such that h[f1] = v1, g[f1] ≤ t1 (and similarly we define f2). Notice that for any γ ∈ [0, 1], we have
γf1 + (1− γ)f2 ∈ F[0,1] γh[f1] + (1− γ)h[f2] = γv1 + (1-γ)v2 γg[f1] + (1− γ)g[f2] ≤ γt1 + (1− γ)t2,
which implies that γ(v1, t1) + (1 − γ)(v2, t2) ∈ A and thus A is convex. Also notice that by definition, A ∩ B = ∅. Using separating hyperplane theorem, there exists a point (q1, q2) 6= (0, 0) and a value α such that for any (v, t) ∈ A, q1v + q2t ≥ α and for any (0, s) ∈ B, q2s ≤ α. Notice that we must have q2 ≥ 0, otherwise, for sufficient s, we will have q2s > α. We thus have, for any f ∈ F[0,1], we have q1h[f ] + q2g[f ] ≥ α∗ ≥ q2α∗. If q2 > 0, we have
max λ∈R min f∈F[0,1] g[f ] + λh[f ] ≥ min f∈F[0,1] g[f ] + q1 q2 h[f ] ≥ α∗,
which gives the strong duality. If q2 = 0, we have for any f ∈ F[0,1], q1h[f ] ≥ 0 and by the separating hyperplane theorem, q1 6= 0. However, this case is impossible: If q1 > 0, choosing f ≡ 1 gives q1h[f ] = q1 ( f ]π0(x0)− 1 ) < 0; If q1 < 0, by choosing f ≡ 0, we have q1h[f ] =
q1 ( f ]π0(x0)− 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(x0 + z)] + λ ( f ]π0(x0)− Eπ0 [f(x0 + z)] ) ,
and the dual problem is
max λ∈R min δ∈B min f∈F[0,1]
Eπδ [f(x0 + z)] + λ ( f ]π0(x0)− Eπ0 [f(x0 + z)] ) = max
λ≥0 min δ∈B min f∈F[0,1]
Eπδ [f(x0 + z)] + λ ( f ]π0(x0)− Eπ0 [f(x0 + z)] ) .
By the assumption that for any λ ≥ 0, we have
max λ≥0 min δ∈B min f∈F[0,1]
Eπδ [f(x0 + z)] + λ ( f ]π0(x0)− Eπ0 [f(x0 + z)] ) = max
λ≥0 min f∈F[0,1] Eπδ∗ [f(x0 + z)] + λ
( f ]π0(x0)− Eπ0 [f(x0 + z)] ) ,
for some δ∗ ∈ B. We have max λ∈R min δ∈B min f∈F[0,1] Eπδ [f(x0 + z)] + λ ( f ]π0(x0)− Eπ0 [f(x0 + z)] ) = max
λ≥0 min f∈F[0,1] Eπδ∗ [f(x0 + z)] + λ
( f ]π0(x0)− Eπ0 [f(x0 + z)] ) = max
λ∈R min f∈F[0,1] Eπδ∗ [f(x0 + z)] + λ
( f ]π0(x0)− Eπ0 [f(x0 + z)] ) ∗ = min f∈F[0,1] max λ∈R Eπδ∗ [f(x0 + z)] + λ ( f ]π0(x0)− Eπ0 [f(x0 + z)]
) ≥min δ∈B min f∈F[0,1] max λ∈R Eπδ∗ [f(x0 + z)] + λ ( f ]π0(x0)− Eπ0 [f(x0 + 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
{ λp0 − ∫ (λπ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, σ2I) ∈ Cλ ) − P ( N(z; δ, σ2I) ∈ Cλ ) =λ · Φ ( ‖δ‖2 2σ + σ lnλ ‖δ‖2 ) − Φ ( −‖δ‖2 2σ + σ lnλ ‖δ‖2 ) .
Define F (δ, λ) := λp0− ∫ (λπ0(z)− πδ(z))+ dz = λp0−λ·Φ ( ‖δ‖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)−‖δ‖22 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(p0)−
‖δ‖2 σ ) = Φ ( Φ−1(p0)− r
σ
)
This tells us min ‖δ‖2≤r max λ≥0
F (δ, λ) > 1/2⇔ Φ ( Φ−1(p0)− r
σ
) > 1/2⇔ r < σ · Φ−1(p0)
, i.e. the certification radius is σ ·Φ−1(p0). 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 k1, k2 ≥ 0 and σ > 0. We first gives the following key theorem shows that DF[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 k1, k2 ≥ 0 and σ > 0, for any λ ≥ 0 we have sgn(δi) ∂
∂δi DF[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 λ, k1 and k2, we define φ1(s) = s−k1 , φ2(s) = s−k2e − s2 σ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 ‖x0 − δ‖∞= I{‖x0 − δ‖∞ = |xi − δi|}
∂
∂δi
√ (xi − δi)2
= I{‖x0 − δ‖∞ = |xi − δi|} − (xi − δi) ‖x0 − δ‖∞ .
And also ∂
∂δi ‖x0 − µ‖2 =
∂
∂δi √∑ i (xi − µi)2
= − (xi − µi) ‖x0 − µ‖2 .
We thus have ∂
∂δ1
∫ (λπ0(x0)− πδ(x0))+ dx0
=− ∫ I {λπ0(x0) ≥ πδ(x0)} ∂
∂δ1 πδ(x0)dx0
= ∫ I {λπ0(x0) ≥ πδ(x0)}F1 (‖x0 − δ‖∞ , ‖x0 − δ‖2) dx0
= ∫ I {λπ0(x0) ≥ πδ(x0), x1 > µ1}F1 (‖x0 − δ‖∞ , ‖x0 − δ‖2) dx0
+ ∫ I {λπ0(x0) ≥ πδ(x0), x1 < µ1}F1 (‖x0 − δ‖∞ , ‖x0 − δ‖2) dx0,
where we define F1 (‖x0 − δ‖∞ , ‖x0 − δ‖2)
= φ′1 (‖x0 − δ‖∞)φ2 (‖x0 − δ‖2) I{‖x0 − δ‖∞ = |x1 − δ1|} (x1 − δ1) ‖x0 − δ‖∞
+ φ1 (‖x0 − µ‖∞)φ ′ 2 (‖x0 − µ‖2) (x1 − µ1) ‖x0 − µ‖2 .
Notice that as φ′1 ≤ 0 and φ′2 ≤ 0 and we have∫ I {λπ0(x0) ≥ πδ(x0), x1 > δ1}F1 (‖x0 − δ‖∞ , ‖x0 − δ‖2) dx0 ≤ 0∫ I {λπ0(x0) ≥ πδ(x0), x1 < δ1}F1 (‖x0 − δ‖∞ , ‖x0 − δ‖2) dx0 ≥ 0.
Our target is to prove that ∂∂δ1 ∫
(λπ0(x0)− πδ(x0))+ dx0 ≥ 0. Now define the set H1 = {x0 : λπ0(x0) ≥ πδ(x0), x1 > µ1} H2 = { [2δ1 − x1, x2, ..., xd]> : x0 = [x1, ..., xd]> ∈ H1 } .
Here the set H2 is defined as a image of a bijection proj(x0) = [2δ1 − x1, x2, ..., xd]> = x̃0, that is constrained on the set H1. Notice that under our definition,∫
I {λπ0(x0) ≥ πδ(x0), x1 > δ1}F1 (‖x0 − δ‖∞ , ‖x0 − δ‖2) dx0
= ∫ H1 F1 (‖x0 − δ‖∞ , ‖x0 − δ‖2) dx0.
Now we prove that∫ I {λπ0(x0) ≥ πδ(x0), x1 < δ1}F1 (‖x0 − δ‖∞ , ‖x0 − δ‖2) dx0
(1) ≥ ∫ H2 F1 (‖x0 − δ‖∞ , ‖x0 − δ‖2) dx0
(2) = ∣∣∣∣∫ H1 F1 (‖x0 − δ‖∞ , ‖x0 − δ‖2) dx0 ∣∣∣∣ .
Property of the projection Before we prove the (1) and (2), we give the following property of the defined projection function. For any x̃0 = proj(x0), x0 ∈ H1, we have
‖x0 − δ‖∞ = ‖x̃0 − δ‖∞ ‖x0 − δ‖2 = ‖x̃0 − δ‖2 ‖x0‖2 ≥ ‖x̃0‖2 ‖x0‖∞ ≥ ‖x̃0‖∞ .
This is because x̃i = xi, i ∈ [d]− {1} x̃1 = 2δ1 − x1,
and by the fact that x1 ≥ δ1 ≥ 0, we have |x̃1| ≤ |x1| and |x̃1 − δ1| ≤ |x1 − δ1|.
Proof of Equality (2) By the fact that proj is bijective constrained on the set H1 and the property of proj, we have∫
H2
F1 (‖x̃0 − δ‖∞ , ‖x̃0 − δ‖2) dx̃0
= ∫ H2 φ′1 (‖x̃0 − δ‖∞)φ2 (‖x̃0 − δ‖2) I{‖x̃0 − δ‖∞ = |x̃1 − δ1|} (x̃1 − δ1) ‖x̃0 − δ‖∞ dx̃0
+ ∫ H2 φ1 (‖x̃0 − δ‖∞)φ ′ 2 (‖x̃0 − δ‖2) (x̃1 − δ1) ‖x̃0 − δ‖2 dx̃0
(∗) = ∫ H1 φ′1 (‖x0 − δ‖∞)φ2 (‖x0 − δ‖2) I{‖x0 − δ‖∞ = |x1 − δ1|} (δ1 − x1) ‖x0 − δ‖∞ |det (J)| dx0
+ ∫ H1 φ1 (‖x0 − δ‖∞)φ ′ 2 (‖x0 − δ‖2) (δ1 − x1) ‖x0 − δ‖2 dx0
=− ∫ H1 F1 (‖x0 − δ‖∞ , ‖x0 − δ‖2) dx0,
where (∗) is by change of variable x̃0 = proj(x0) and J is the Jacobian matrix J = −1 0 · · · 0 0 1 · · · 0 ... ... . . .
... 0 0 · · · 1  and here we have the fact that x̃1 − δ1 = (2δ1 − x1)− δ1 = −(x1 − δ1). Proof of Inequality (1) This can be done by verifying that H2 ⊆ {x0 : λπ0(x0) ≥ πδ(x0), x1 < δ1}. By the property of the projection, for any x0 ∈ H1, let x̃0 = proj(x0), then λπ0(x̃0) ≥ λπ0(x0) ≥ πδ(x0) = πδ(x̃0) (by the fact that t φ1 and φ2 are monotone decreasing). It implies that for any x̃0 ∈ H2, we have λπ0(x̃0) ≥ πδ(x̃0) and thus H2 ⊆ {x0 : π0(x0) ≥ πδ(x0), x1 < δ1}.
Final statement By the above result, we have ∂
∂δ1
∫ (λπ0(x0)− πµ(x0))+ dx0 ≥ 0,
and the same result holds for any ∂∂δ1 ∫
(λπ0(x0)− πµ(x0))+ dx0, 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) ∝ ad−1−ke− a2
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)
DF[0,1] (λπ0 ‖ πδ∗) = Ez∼π0 ( λ− πδ
π0 (z) ) + .
Notice that as the distribution is symmetry,
Pπ0 (‖z + δ∗‖∞ = a+ r | ‖z‖∞ = a) = 1
2 .
Define |z|(i) is the i-th order statistics of |zj |, j = 1, ..., d conditioning on ‖z‖∞ = a. By the factorization above and some algebra, we have, for any ∈ (0, 1),
P
( |z|(d−1)
|z|(d) > (1− ) | ‖z‖∞ = a
) ≥ 1− (1− )d−1.
And |z| (d−1)
|z|(d) ⊥ |z| (d). Now we estimate DF[0,1] (λπ0 ‖ πδ∗).
Ez∼π0 ( λ− πδ
π0 (z) ) +
=EaEz∼π0
[( λ− πδ
π0 (z) ) + | ‖z‖∞ = a ]
= 1
2 EaEz∼π0
[( λ− πδ
π0 (z) ) + | ‖z‖∞ = a, ‖z + δ ∗‖∞ = a+ r ]
+ 1
2 EaEz∼π0
[( λ− πδ
π0 (z) ) + | ‖z‖∞ = a, ‖z + δ ∗‖∞ 6= a+ r ] .
Conditioning on ‖z‖∞ = a, ‖z + δ∗‖∞ = a+ r, we have
πδ π0 (z) =
( 1
1 + ra
)k e− 1 2σ2 (2ra+r2)
=
( 1
1 + ra
)k e− d−1−k 2C2 (2 ar+1).
Here the second equality is because we choose mode(‖z‖∞) = Cr, which implies that√ d− 1− kσ = Cr. And thus we have
EaEz∼π0
[( λ− πδ
π0 (z) ) + | ‖z‖∞ = a, ‖z + δ ∗‖∞ = a+ r ]
= ∫ ( λ− ( 1
1 + ra
)k e− d−1−k 2C2 (2 ar+1) ) + π(a)da
= ∫ ( λ− ( 1 + r
a
)−k ( e 2a/r+1 2C2 )−(d−1−k)) + π(a)da
=λ−O(t−d), for some t > 1. Here the last equality is by the assumption that ‖z‖∞ = Op(1).
Next we bound the second term EaEz∼π0 [( λ− πδπ0 (z) ) + | ‖z‖∞ = a, ‖z + δ∗‖∞ 6= a+ r ] . By the property of uniform distribution, we have
P
( |z|(d−1)
|z|(d) > (1− ) | ‖z‖∞ = a, ‖z + δ ∗‖∞ 6= a+ r
)
=P
( |z|(d−1)
|z|(d) > (1− ) | ‖z‖∞ = a ) ≥1− (1− )d−1.
And thus, for any ∈ [0, 1), P ( ‖z + δ∗‖∞ ≥ ((1− )a+ r) 2 | ‖z‖∞ = a, ‖z + δ ∗‖∞ 6= a+ r ) ≥ 1
2
( 1− (1− )d−1 ) .
It implies that
Ez∼π0
[( λ− πδ
π0 (z) ) + | ‖z‖∞ = a, ‖z + δ ∗‖∞ = a+ r ]
≥1 2
( 1− (1− )d−1 )( λ− ( 1− + r
a
)−k e− 1 2σ2 ( ( −2)a2+2r(1− )a+r2) )
+
= 1
2
( 1− (1− )d−1 )( λ− ( 1− + r
a
)−k e− d−1−k 2C2 ( ( −2)a2/r2+2(1− )a/r+1) )
+
.
For any ′ ∈ (0, 1), by choosing = log(2/ ′)
d−1 , for large enough d, we have
Ez∼π0
[( λ− πδ
π0 (z) ) + | ‖z‖∞ = a, ‖z + δ ∗‖∞ = a+ r ]
≥1 2
( 1− (1− )d−1 )( λ− ( 1− + r
a
)−k e− d−1−k 2C2 (2(1− )a/r+1)e a2 log(2/ ′) C2r2 ) +
= 1
2
( 1− (1− log(2/ ′)
d− 1 )d−1
)( λ− ( 1− log(2/ ′)
d− 1 + r a
)−k e− d−1−k 2C2 (2(1− )a/r+1)e a2 log(2/ ′) C2r2 ) +
≥1 2
(1− ′) ( λ− ( 1− + r
a
)−k e− d−1−k 2C2 (2(1− )a/r+1)e a2 log(2/ ′) C2r2 ) + .
Thus we have
1 2 EaEz∼π0
[( λ− πδ
π0 (z) ) + | ‖z‖∞ = a, ‖z + δ ∗‖∞ 6= a+ r ]
= 1
2 (1− ′)
( λ−O(t−d) ) .
Combine the bounds, for large d, we have DF[0,1] (λπ0 ‖ πδ∗) = (1− ′) ( λ−O(t−d) ) .

heading: B PRACTICAL ALGORITHM
text: In this section, we give our algorithm for certification. Our target is to give a high probability bound for the solution of
Vπ0(F[0,1], B`∞,r) = max λ≥0
{ λf ]π0 − DF[0,1] (λπ0 ‖ πδ) } given some classifier f ]. Following Cohen et al. (2019), the given classifier here has a binary output {0, 1}. Computing the above quantity requires us to evaluate both f ]π0 and DF[0,1] (λπ0 ‖ πδ). A lower bound p̂0 of the former term is obtained through binominal test as Cohen et al. (2019) do, while the second term can be estimated with arbitrary accuracy using Monte Carlo samples. We perform grid search to optimize λ and given λ, we draw N i.i.d. samples from the proposed smoothing distribution π0 to estimate λf ]π0 − DF[0,1] (λπ0 ‖ πδ). This can be achieved by the following importance sampling manner:
λf ]π0 − DF[0,1] (λπ0 ‖ πδ) ≥ λp̂0 − ∫ (
λ− πδ π0 (z) ) + π0(z)dz
≥ λp̂0 − 1
N N∑ i=1 ( λ− πδ π0 (zi) ) + − .
And we use reject sampling to obtain samples from π0. Notice that, we restrict the search space of λ to a finite compact set so the importance samples is bounded. Since the Monte Carlo estimation is not exact with an error , we give a high probability concentration lower bound of the estimator. Algorithm 1 summarized our algorithm.
Algorithm 1 Certification algorithm Input: input image x0; original classifier: f ]; smoothing distribution π0; radius r; search interval
[λstart, λend] of λ; search precision h for optimizing λ; number of samples N1 for testing p0; pre-defined error threshold ; significant level α;
compute search space for λ : Λ =range(λstart, λend, h) compute N2: number of Monte Carlo estimation given , α and Λ compute optimal disturb: δ depends on specific setting for λ in Λ do
sample z1, · · · , zN1 ∼ π0 compute n1 = 1N1 ∑N1 i=1 f ](x0 + zi)
compute p̂0 =LowerConfBound(n1, N1, 1− α) sample z1, · · · , zN2 ∼ π0 compute D̂F[0,1] (λπ0 ‖ πδ) = 1N2 ∑N2 i=1 ( λ− πδπ0 (zi) ) +
compute confidence lower bound bλ = λp̂0 − D̂F[0,1] (λπ0 ‖ πδ)− end if maxλ∈Λ bλ ≥ 1/2 then
x0 can be certified else
x0 cannot be certified end
The LowerConfBound function performs a binominal test as described in Cohen et al. (2019). The in Algorithm 1 is given by concentration inequality.
Theorem 7. Let h(z1, · · · , zN ) = 1N ∑N i=1 ( λ− πδ(zi)π0(zi) ) + , we yield
Pr{|h(z1, · · · , zN )− ∫ (λπ0(z)− πδ(z))+ dz| ≥ ε} ≤ exp ( −2Nε2
λ2
) .
Proof. Given McDiarmid’s Inequality, which says
sup x1,x2,...,xn,x̂i
|h (x1, x2, . . . , xn)− h (x1, x2, . . . , xi−1, x̂i, xi+1, . . . , xn)| ≤ ci for 1 ≤ i ≤ n,
we have ci = λN , and then obtain Pr{|h(z1, · · · , zN )− ∫ (λπ0(z)− πδ(z))+ dz| ≥ ε} ≤ exp ( −2Nε2
λ2
) .
The above theorem tells us that, once , λ,N is given, we can yield a bound with high-probability 1 − α. One can also get N when , λ, α is provided. Note that this is the same as the Hoeffding bound mentioned in Section 4.1 as Micdiarmid bound is a generalization of Hoeffding bound.
However, in practice we can use a small trick as below to certify with much less comupation:
Algorithm 2 Practical certification algorithm Input: input image x0; original classifier: f ]; smoothing distribution π0; radius r; search interval
for λ: [λstart, λend]; search precision h for optimizing λ; number of Monte Carlo for first estimation: N01 , N 0 2 ; number of samples N1 for a second test of p0; pre-defined error threshold ; significant level α; optimal perturbation δ (δ = [r, 0, . . . , 0]> for `2 attacking and δ = [r, . . . , r]> for `∞ attacking).
for λ in Λ do sample z1, · · · , zN01 ∼ π0
compute n01 = 1 N01
∑N01 i=1 f ](x0 + zi)
compute p̂0 =LowerConfBound(n01, N 0 1 , 1− α) sample z1, · · · , zN02 ∼ π0 compute D̂F[0,1] (λπ0 ‖ πδ) = 1N02 ∑N02 i=1 ( λ− πδπ0 (zi) ) +
compute confidence lower bound bλ = λp̂0 − D̂F[0,1] (λπ0 ‖ πδ) end
compute λ̂ = arg maxλ∈Λ bλ compute N2: number of Monte Carlo estimation given , α and λ̂ sample z1, · · · , zN1 ∼ π0 compute n1 = 1N1 ∑N1 i=1 f ](x0 + zi) compute p̂0 =LowerConfBound(n1, N1, 1− α) sample z1, · · · , zN2 ∼ π0 compute D̂F[0,1] (λπ0 ‖ πδ) = 1N2 ∑N2 i=1 ( λ− πδπ0 (zi) ) + compute b = λ̂p̂0 − D̂F[0,1] (λπ0 ‖ πδ)− if b ≥ 1/2 then x0 can be certified
else x0 cannot be certified end
Algorithm 2 allow one to begin with smallN01 , N 0 2 to obtain the first estimation and choose a λ̂. Then a rigorous lower bound can be achieved with λ̂ with enough (i.e. N1, N2) Monte Carlo samples.

heading: C ABALATION STUDY
text: On CIFAR10, we also do ablation study to show the influence of different k for the `2 certification case as shown in Table 4.
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 x0 correctly to class A, i.e.,
f ]A(x0) > max B 6=A f ]B(x0) (11)
where f ]B(x0) denotes the prediction confidence of any class B different from ground truth label A. Notice that f ]A(x0) + ∑ B 6=A f ] B(x0) = 1, so the necessary and sufficient condition for correct binary classification f ]A(x0) > 1/2 becomes a sufficient condition for multi-class prediction.
Similarly, the necessary and sufficient condition for correct classification of the smoothed classifier is
min f∈F
{ Ez∼π0 [fA(x0 + δ + z)] s.t. Eπ0 [fA(x0)] = f ]π0 ,A(x0) } >
max f∈F
{ Ez∼π0 [fB(x0 + δ + z)] s.t. Eπ0 [fB(x0)] = f ]π0 ,B(x0) } for ∀B 6= A and any perturbation δ ∈ B. Writing out their Langragian forms makes things clear:
max λ λf ]π0 ,A(x0)− DF[0,1] (λπ0 ‖ πδ) > minλ maxB 6=Aλf ] π0 ,B(x0) + DF[0,1] (πδ ‖ λπ0)
Thus the overall necessary and sufficient condition is
min δ∈B { max λ ( λf ]π0 ,A(x0)− DF[0,1] (λπ0 ‖ πδ) ) −max B 6=A min λ ( λf ]π0 ,B(x0) + DF[0,1] (πδ ‖ λπ0) )} > 0
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(x0))− ‖δ‖2 σ ) −max B 6=A Φ ( Φ−1(f ]π0 ,B(x0)) + ‖δ‖2 σ )} > 0
⇔ Φ−1(f ]π0 ,A(x0))− r σ > Φ−1(f ]π0 ,B(x0)) + r σ ,∀B 6= A ⇔ r < σ 2 ( Φ−1(f ]π0 ,A(x0))− Φ −1(f ]π0 ,B(x0)) ) ,∀B 6= 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 − pA as a naive estimate of the upper bound of f ]π0 ,B(x0), where pA is a lower bound of f ]π0 ,A(x0). This leads the confidence bound decay to the bound one can get in binary case, i.e., r ≤ σΦ−1(f ]π0 ,A(x0)). 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.

Review summaries:
This 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).

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.