Year: 2019

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

heading: 1 INTRODUCTION
text: have done a series of nice works in practical sights or theoretical sights (Zheng et al., 2016; Gouk et al., 2018). Among them, certifiably robustness is valuable, since it can withstand all attacks within a norm ball and has a nice theoretical and practical outcome. However, most work cannot deal with the case for general neural networks.
Deep networks are flexible models that are widely adopted in various applications. However, it has been shown that such models are vulnerable against adversary (Szegedy et al., 2014). Concretely, an unnoticeable small perturbation on the input can cause a typical deep model to change predictions arbitrarily. The phenomenon raises the concerns of the security of deep models, and hinders its deployment in decision-critical applications. Indeed, the certification of robustness is a pre-requisite when AI-generated decisions may have important consequences.
Certifying the robustness of a machine learning model is challenging, especially for modern deep learning models that are over-parameterized and effectively black-box. Hence, the existing approaches mainly rely on empirical demonstration against specific adversarial attack algorithms (Goodfellow et al., 2015; Madry et al., 2018; Finlay et al., 2019). However, this line of works can give a false sense of security. Indeed, successful defense against the existing attack algorithms does not guarantee actual robustness against any adversaries that may appear in the future.
Recently, the adversarial robustness community has shifted the focus towards establishing certificates that prove the robustness of deep learning models. The certificate can be either exact or conservative, so long as the certified region cannot exhibit any adversarial examples. Given the over-parameterized deep models and modern high-dimensional datasets, scalability becomes a key property for the certification algorithms, as many methods are computationally intractable.
Our work is based on the novel modeling scheme that generates ensembles of a fixed black-box classifier based on input randomization (Cohen et al., 2019). Under this framework, tight robustness certificates can be obtained with only the ensemble prediction values and randomization parameters. Given appropriate choices of distributions, the robustness guarantee can be derived for `2 or `0 norms (Cohen et al., 2019; Lee et al., 2019). The tightness simply implies that any point outside the certified region is an adversarial example in the worst case. However, the derivations of the previous results heavily relies on the fact that the target norm (`2 or `0) is symmetric, therefore analyzing any perturbation direction for attacking the model gives the same certification guarantee.
In contrast, `1 norm is asymmetric. That is, for a given `1 ball centered at the origin, if we move another `1 ball also from the origin by a distance δ, where ‖δ‖1 is fixed, then the overlapped region
between the two `1 balls may have different shapes and sizes (See Figure 1). The characterization of this overlapped region is the key step for proving tight certificates, hence the existing techniques do not apply for `1 norm.
In this work, we derive a tight `1 robustness guarantee under isotropic Laplace distributions. The Laplace distribution can be interpreted as an infinite mixture of uniform distributions over `1-norm balls, which is a natural “conjugate” distribution for `1 norm. Due to asymmetry, we first identified the tight robustness certificate for attacking the model in one particular direction, δ = (‖δ‖1, 0, · · · , 0). To show that other perturbation directions cannot lead to worse results, we convert the d dimensional likelihood function into an one dimensional function, where we apply relaxation for various δ and show that the worst case result is bounded by the specific direction (‖δ‖1, 0, · · · , 0). Theoretically, our certificate is tight in the binary classification setting. In the multi-class classification setting, our certificate is always tighter than the previous certificate proposed by Lecuyer et al. (2019). The theoretical improvement always leads to superior empirical results on certifying the same model, where we demonstrate the result on CIFAR-10 and ImageNet with ResNet models. Moreover, the proposed robustness certificate on models smoothed by Laplace distributions also outperforms the same models trained and certified using Gaussian distributions (Cohen et al., 2019) in `1 certified robustness, where the Gaussian-based robustness certificate is adapted from `2 norm.

heading: 2 RELATED WORK
text: Robustness of a model can be defined in various aspects. For example, Feynman-Kac Formalism can be used to improve robustness (Wang et al., 2018). In this paper, we focus on the classification setting, where the goal is to provide guarantee of a constant prediction among a small region specified via some metric. The robustness certificate can be either exact or conservative, so long as a constant prediction is guaranteed in the certified region. Note that the certification of a completely black-box model requires checking the prediction values at every point around the point of interest, which is clearly infeasible. A practical certification algorithm inevitably has to specify and leverage the functional structure of the classifier in use to reduce the required computation.
Exact certificates. The exact certificate of deep networks is typically derived for the networks with a piecewise linear activation function such as ReLU. Such networks have an equivalent mixed integer linear representation (Cheng et al., 2017; Lomuscio & Maganti, 2017; Dutta et al., 2017; Bunel et al., 2018). Hence, one may apply mixed integer linear programming to find the worst case adversary within any convex polyhedron such as an `1-ball or `∞-ball. Despite the elegant solution, the complexity is, in general, NP-hard and the algorithms are not scalable to large problems(Tjeng et al., 2017).
Conservative certificates. A conservative certificate can be more scalable than the exact methods, since one can trade-off the accuracy of certification with efficiency (Gouk et al., 2018; Tsuzuku et al., 2018; Cisse et al., 2017; Anil et al., 2018; Hein & Andriushchenko, 2017). For example, one can relax the search of the worst case adversary as a simpler optimization problem that only bounds the effect of such adversary. Alternatively, people also consider the robustness problem in a modular way, where the robustness guarantee can be derived iteratively for each layer in the deep networks by considering the feasible values for each hidden layer (Gowal et al., 2018; Weng et al., 2018; Zhang et al., 2018; Mirman et al., 2018; Singh et al., 2018). However, this line of works have not yet been demonstrated to be feasible to realistic networks in high dimensional problems like ImageNet.
Randomized smoothing. Randomized smoothing has been proved to be closely related to robustness. Although similar techniques have been tried by (Liu et al., 2018; Cao & Gong, 2017), no corresponding proofs have been given; Li et al. (2018) and Cohen et al. (2019) have proved certified robustness of `2 norm under isotropic Gaussian noise, and Lee et al. (2019) proved robustness for `0 form. Lecuyer et al. (2019) use techniques from differential privacy to prove `1 robustness under Gaussian and Laplace noise respectively, but the bounds are not tight. Li et al. (2018); Pinot et al. (2019) use Rényi divergence framework without tightness proof. Our results synthesize the ideas in (Cohen et al., 2019; Lee et al., 2019; Lecuyer et al., 2019; Li et al., 2018; Pinot et al., 2019) and prove the tight robustness radius under the binary classification setting.

heading: 3 PRELIMINARIES
text: Definition 1 (Laplace distribution) Given λ ∈ R+, d ∈ Z+, we use L(λ) to denote the Laplace distribution in dimension d with parameter λ. The p.d.f. of L(λ) is denoted as L(x;λ) ,
1 (2λ)d exp(−‖x‖1λ ).
As we will see in Lemma 3.1, in smoothing analysis, we are interested in the likelihood ratio of two random variables X = and Y = δ + (here ∼ L(λ) and δ ∈ Rd is a fixed vector). Specifically,
µY (x) µX(x) = exp ( − 1 λ (‖x− δ‖1 − ‖x‖1) )
Therefore, the likelihood ratio between two d dimensional random variables is controlled by a one dimensional random variable T (x) , ‖x − δ‖1 − ‖x‖1, where x ∼ L(λ). This transformation is crucial in our analysis, and it is easy to see that T (x) is a mixed random variable, since Px(T (x) = ‖δ‖1) > 0. In our analysis, we need to calculate the inverse of c.d.f. of T (x). However, since T (x) is a mixed random variable, sometimes the inverse may not exist. See Figure 3 for illustration, where the inverse of the probability 0.85 does not exist. To deal with this case, we have the following modified version of Neyman-Pearson Lemma, with the proof in Appendix A.
Lemma 3.1 (Neyman-Pearson Lemma for mixed random variables). Let X ∼ L (λ) and Y ∼ L (λ) + δ. Let h : Rd → {0, 1} be any deterministic or random function. Given any β ∈ R, and S′ ⊆ { z ∈ Rd : ‖z − δ‖1 − ‖z‖1 = β } :
1. If S = { z ∈ Rd : ‖z − δ‖1 − ‖z‖1 > β } ∪ S′, and P(h(X) = 1) ≥ P(X ∈ S) then P(h(Y ) = 1) ≥ P(Y ∈ S)
2. If S = { z ∈ Rd : ‖z − δ‖1 − ‖z‖1 < β } ∪S′, and P(h(X) = 1) ≤ P(X ∈ S), then P(h(Y ) = 1) ≤ P(Y ∈ S)

heading: 4 MAIN RESULTS
text: In this paper, we apply the randomized smoothing technique (Cohen et al., 2019) for getting robustness certificates, which works as follows. Given an input x, we perturb it with , s.t. ∼ L(λ). Then instead of evaluating the robustness of the original function f(x), we evaluate g(x) , arg maxc P (f(x+ ) = c), which is effectively the smoothed version of f(x).

heading: 4.1 ROBUSTNESS CERTIFICATES FOR GENERAL CASES
text: Our first theorem proves that for the smoothed classifier g, and a given input x, there always exists a robust radius R, such that any perturbation δ s.t. ‖δ‖1 ≤ R, does not alter the prediction of g(x).
Theorem 1 Let f : Rd → Y be deterministic or random function, and let ∼ L(λ). Let g(x) = arg maxc P (f(x+ ) = c). Suppose PA, PB ∈ [0, 1] are such that
P (f(x+ ) = cA) ≥ PA ≥ PB ≥ max c 6=cA P(f(x+ ) = c)
Then g(x+ δ) = g(x),∀‖δ‖1 ≤ R, where
R = max
{ λ
2 log(PA/PB),−λ log(1− PA + PB)
} (1)
Some Remarks:
1. When PA → 1 or PB → 0, we can get R → ∞. It is reasonable since the Laplace distribution is supported over Rd, PA → 1 is equivalent to f = cA almost everywhere.
2. Compared with (Lecuyer et al., 2019) where they have R = λ2 log(PA/PB), our bound
is better if 1−2PA(1−PA)−
√ 1−4PA(1−PA)
2PA ≤ PB ≤
1−2PA(1−PA)+ √
1−4PA(1−PA) 2PA . See
Figure 4 for illustration, where we use baseline to denote the bound R = λ2 log(PA/PB).
Proof sketch: (The full proof is in Appendix B) For arbitrarily classifier f , we can transform it into a random smoothing classifier g using random smoothing technique, where g returns class cA with probability no less than PA, and class cB with probability no more than PB . Below we list the three main ideas we used in our proof:
1. How to deal with an arbitrary f with PA and PB?
Following Cohen et al. (2019), we use Neyman-Pearson Lemma to transform the relation between P(f(X) = cA) and P(f(Y ) = cA) into the relation between P(X ∈ A) and P(Y ∈ A). From Lemma 3.1, Neyman-Pearson Lemma still holds for mixed random variables.

heading: 2. How to deal with the relation between X = and Y = + δ?
text: Inspired by Lecuyer et al. (2019), we use the DP-form inequality (P (Y ∈ A) ≤ e P (X ∈ A)) to deal with the relation between P (X ∈ A) and P (Y ∈ A). In Laplace distribution, = ‖δ‖1λ .

heading: 3. Take complements to get tighter bound.
text: When PA or B < 1/2, the above DP-form inequality gets tighter. Therefore, we analyze Ac when PA ≥ 1/2 to get a new bound, and compare it with the baseline expression. We derive this bound by Neyman-Pearson Lemma in this work, but an alternative approach is using Rényi Divergence (Li et al., 2018).

heading: 4.2 TIGHT ROBUSTNESS CERTIFICATES FOR BINARY CASE
text: Although we get improved result over Lecuyer et al. (2019), the bound in Theorem 1 is not tight since it considers the general case with multiple categories. In this section, we first present our result for binary classification (Theorem 2), which further improves over Theorem 1.
Theorem 2 (binary case) Let f : Rd → Y be deterministic or random function, and let ∼ L(λ). Let g(x) = arg maxc P (f(x + ) = c). Suppose there are only two classes cA and cB , and PA ∈ [ 12 , 1] s.t. P (f(x+ ) = cA) ≥ PA Then g(x+ δ) = g(x),∀‖δ‖1 ≤ R, for
R = −λ log[2(1− PA)] (2)
Scretch of the proof: (The full proof is in Appendix C) Theorem 2 is a special binary case of Theorem 1. We can use a method similar to Theorem 1 to get the results. However, it is worth noting that in binary cases, our new improved bound in Theorem 1 always dominates the bound by Lecuyer et al. (2019). Moreover, our bound in Eqn. (2) is tight, as shown below.
Theorem 3 (tight bound in binary case) In the same setting as Theorem 2, assume PA + PB ≤ 1 and PA ≥ 12 . ∀R
′ > −λ log[2(1 − PA)], ∃ base classifier f∗ and perturbation δ∗ with g∗(x) = arg maxc P (f ∗(x+ ) = c) and ‖δ‖1 = R′, s.t. g∗(x) 6= g∗(x+ δ∗).
Scretch of the proof:(The full proof is in Appendix C) For Theorem 3, we prove that the bound in Theorem 2 is tight by calculating the results in one-dimensional case, where δ = (‖δ‖1, 0, . . . , 0). By calculating, we show that when δ = (‖δ‖1, 0, . . . , 0)
P(Y ∈ B) = ∫ ‖δ‖1+λ log[2PB ] −∞ 1 2λ exp (−|x| λ )dx
= { exp(‖δ‖1λ )PB when ‖δ‖1 ≤ −λ log[2PB ] 1− 1
4PB exp(−‖δ‖1λ ) o.w.
Therefore, when ‖δ‖1 ≤ −λ log[2PB ], the DP-inequality is tight. The worst-case δ appears in the one-dimension case.
Figure 5 shows the reason why the inequality is tight. When δ is small, for P(X ∈ B), the set B we selected satisfies ∀x ∈ B, T (x) = −‖δ‖1 (red part). When P(Y ∈ B) is considered, it moves set S towards left by step δ. However, due to the small δ, S after moving still satisfies the requirement of ∀x ∈ S, T (x) = −‖δ‖1 (blue part). Therefore, the inequality is tight.

heading: 4.3 METHOD COMPARISON
text: We compared our method with Cohen et al.’s and Lecuyer et al.’s in binary case, see Table 1. We plot the curves in Figure 6. As we can see, under the same variance of each noise, our method can reach better robustness radius. Below we show simple derivations of the bounds in Table 1.
Robustness radius of Lecuyer et al. (2019)
Using the basic inequality from differential privacy, we have:
P (f(X) = cA) ≤ exp(β)P (f(Y ) = cA) P (f(Y ) = cB) ≤ exp(β)P (f(X) = cB)
where β = ‖δ‖1/λ. The above two inequalities show that to guarantee P (f(Y ) = cA) > P (f(Y ) = cB), it suffices to show that:
P (f(X) = cA) > exp(2β)P (f(X) = cB)
So plug in β = ‖δ‖1/λ, we have ‖δ‖1 ≤ λ2 log(PA/PB). Furthermore, in binary case, we can plug in PB = 1− PA, and get the robustness radius: R = λ2 log(PA/1− PA). Robustness radius of Cohen et al. (2019)
Denote Bp,r(c) = {x : ‖x − c‖p ≤ r}. Since we know that B1,r(c) ⊂ B2,r(c), so the radius in (Cohen et al., 2019) can be directly used in `1 form, which is σΦ−1(PA).
Besides, since B1,r+ (c) 6⊂ B2,r(c) whatever > 0 is. And (Cohen et al., 2019) is an exact robustness guarantee, so we have that the best `1 form that isotropic Gaussian noise random smoothing can get is σΦ−1(PA).
Finally we will prove that −λ log[2(1 − PA)] ≥ λ2 log(PA/1− PA). For simple denotion, we just set PA = p ≥ 0.5. So it is sufficient to show that−λ log[2(1−p)] ≥ λ2 log(p/(1−p)). By applying exponential operation, it suffices to show that 12(1−p) ≥ √ p 1−p , which is simply p(1− p) ≤ 1 4 .

heading: 5 EXPERIMENTS

heading: 5.1 IMPLEMENTATION DETAILS
text: Monte Carlo. Since we cannot get the exact value of PA, we have to use Monte Carlo method to get the approximate value of PA. More specifically, we take multiple random samples from the Laplace distribution to estimate PA. One way to do it is grouping the samples and get PA using non-parametric estimation.
In our experiments, we applied two different types of training, as described below.
Type1-Training: The first method is intuitive, and was applied in (Cohen et al., 2019). In the training process, we add into inputs:
inputs = inputs + noise
where the noise is sampled from isotropic Laplace distribution.
Type2-Training: The second method was recently proposed by Salman et al. (2019). The idea is to use adversarial noise samples instead of the raw noise samples in a neighborhood to train the base classifier. Each training sample can be decomposed to
inputs = inputs + noise + perturbation
where the noise comes from an isotropic Laplace distribution, and the perturbation is found approximately by the gradient of loss with respect to the input. Concretely, if we denote the loss as L and the input as x, the perturbation ∆ can be calculated by ∆ = a ∗ sign(∇xL(θ, x, y)), where a is a constant.
Evaluation Index. In this paper, we choose certified accuracy as our evaluation index. Robustness certified accuracy at radius r refers to the proportion of correctly classified samples with at least robustness radius r. Specifically, if a group of samples with capacity n is {xi}, i = 1, 2, . . . , n, its corresponding certified robustness radius is Ri. An index xi represent if the sample is classified correctly. If the sample is correctly classified, xi = 1, otherwise xi = 0. For a given r, the corresponding robustness certified accuracy is defined as α = ∑n i=1 xi1(Ri ≥ r)/n, where 1(·) is an indicator function.
However, from Section 5.1 we know that we cannot calculate the exact robustness radius R, so we use its R̂ to approximate R, which leads to a “approximate robustness certified accuracy”(α̂), which is calculated by
α̂ = n∑ i=1 xiI(R̂i ≥ r)/n (3)
Cohen et al. (2019) demonstrates that when significance level of R̂ is small, the difference between these two quantities is negligible. In practice, we plot approximate certified accuracy α̂ as a function of radius r. From Eqn. (3), we know that α̂ is non-increasing w.r.t. r. And when r →∞, α̂→ 0. Hyperparameters. In our paper, we set all our hyperparameters following Cohen et al. (2019). Specifically, we set significance level to 0.001. n0 = 100 in Monte Carlo simulation (used to get bound for α̂) and n = 100, 000 in estimation part (used to estimate α̂). Moreover, we test three parameters in CIFAR-10 dataset and ImageNet dataset (σ = 0.25, 0.50, 1.00). Since (Cohen et al., 2019) use Gaussian noise and we use Laplace noise, they should have the same standard deviation during comparison. This requires that σ = √ 2λ.

heading: 5.2 EXPERIMENTAL RESULTS
text: Results on ImageNet and CIFAR-10. We applied random smoothing on CIFAR-10 (Krizhevsky (2009)) and ImageNet (Deng et al. (2009)) respectively. On each data set, we trained several random smoothing models with differential standard deviation σ for Laplace noise. In order to keep in line with Cohen et al.’s method and make a comparison, we select σ = 0.25, 0.50, 1.00 on CIFAR-10, and ImageNet, corresponding parameter λ = σ/ √ 2.
Figure 6 draws the certified accuracy achieved by smoothing with each sigma. For the ImageNet dataset, we only use the most basic training method (Type1 Training). For the CIFAR-10 data set, we use two training methods (Type 1 and Type 2 Training). We can see that the smaller sigma performs better when the radius is smaller. As the noise gets bigger, the accuracy becomes lower, but the robustness guarantee becomes higher. The dashed black line shows the empirical robust accuracy of an undefended classifier from Cohen et al. (2019).
Comparison with baseline.
We will show our comparison results in the following. Based on Table. 1, we will test our method on CIFAR-10 with the ResNet110 architecture as well as Type1 and Type2 training, and ImageNet with ResNet50 architecture as well as Type1 training. We will compare our results with (Cohen et al., 2019) and (Lecuyer et al., 2019) under the same standard deviation σ. For base classifiers, ours and Lecuyer et al.’s share the same base classifier with Laplace training noise, and Cohen et al.’s uses the base classifier with Gaussian training noise.

heading: 6 CONCLUSION
text: In this paper, we combine the inequality from differential privacy and the classic Neyman-Pearson Lemma to resolve the challenging asymmetry of `1 metric and the mixed discrete-continuous property of the likelihood ratios under isotropic Laplace distributions. In addition, by comparing the high-dimensional case with a special edge case, we prove the tight `1 robustness guarantee for binary classification problems, and obtain the state-of-the-art certified accuracy in large scale experiments.
The establishment of `1 certificate via Laplace distributions and the prior result of `2 certificate via Gaussian distributions may be extended to a generic theorem for a general `p norm robustness certificate via the associated realization of the generalized Gaussian distribution, where the aforementioned results are special cases of the general scheme. The introduction of the mixed random variable analysis and `p geometry analysis may serve as a valuable extension of existing works towards such general goal.

heading: A PROOF OF LEMMA 1
text: In this section, we will prove that Neyman-Pearson Lemma holds with mixed random variable.
WLOG, x = 0, X ∼ L (λ) and Y ∼ L (λ) +δ. We will firstly introduce Neyman-Pearson Lemma, which plays an important role in our proof.
Lemma 3.1 (restated).LetX ∼ L (λ) and Y ∼ L (λ)+δ. Let h : Rd → {0, 1} be any deterministic or random function. Given any β ∈ R, and S′ ⊆ { z ∈ Rd : ‖z − δ‖1 − ‖z‖1 = β } :
1. If S = { z ∈ Rd : ‖z − δ‖1 − ‖z‖1 > β } ∪ S′, and P(h(X) = 1) ≥ P(X ∈ S) then P(h(Y ) = 1) ≥ P(Y ∈ S)
2. If S = { z ∈ Rd : ‖z − δ‖1 − ‖z‖1 < β } ∪S′, and P(h(X) = 1) ≤ P(X ∈ S), then P(h(Y ) = 1) ≤ P(Y ∈ S) Proof of Lemma 3.1 First, notice that P(X ∈ S) can be regarded as a mixed random variable. We want to prove that as long as we can choose a S′ that satisfies P(X ∈ S) ≤ P(h(X) = 1), Neyman-Pearson Lemma can always hold.
Let’s first see what happens in the proof of Neyman-Pearson Lemma. Notice that X and Y are continuous variables, but X ∈ S and Y ∈ S can be regarded as mixed continuous-discrete event. Then we can choose a reasonable S′ for X and Y . We will prove case 1 and the other one can be proved with similar method.
P(h(Y ) = 1)− P(Y ∈ S)
= ∫ Rd h(1|z)µY (z)dz− ∫ S µY(z)dz
=[ ∫ Sc h(1|z)µY (z)dz + ∫ S h(1|z)µY(z)dz]− [ ∫ S h(1|z)µY(z)dz + ∫ S h(0|z)µY(z)dz]
= ∫ Sc h(1|z)µY (z)dz− ∫ S h(0|z)µY(z)dz
≥t( ∫ Sc h(1|z)µX(z)dz− ∫ S h(0|z)µX(z)dz)
=t([ ∫ Sc h(1|z)µX(z)dz + ∫ S h(1|z)µX(z)dz]− [ ∫ S h(0|z)µX(z)dz + ∫ Sc h(1|z)µX(z)dz]) =t(P(h(X) = 1)− P(X ∈ S)) ≥0
(4)
The first inequality holds due to the construction of mixed definition S. If z ∈ S, µY (z)µX(z) ≥ t. If z ∈ Sc, µY (z)µX(z) ≤ t. Compared with continuous set, the only difference appears in the equal sign.
It should be noted that P(X ∈ S) and P(Y ∈ S) should keep consistent, which means that they should have the same S′. In this derivation, we can find that P (X ∈ S) and P (Y ∈ S) use the same set S′ in Eqn. (4).
Next, we will plug in the condition that X and Y are isotropic Laplaces.
Then we just need to prove that{ z ∈ Rd : µY (z) µX(z) ≤ t } ⇐⇒ { z ∈ Rd : ‖z − δ‖1 − ‖z‖1 ≥ β } When X and Y are isotropic Laplaces, the likelihood ratio turns out to be:
µY (z) µX(z) = exp(− 1λ‖z − δ‖1) exp(− 1λ‖z‖1)
= exp(− 1 λ (‖z − δ‖1 − ‖z‖1))
By choosing β = −λ log(t), we can derive that
‖z − δ‖1 − ‖z‖1 ≥ β ⇐⇒ µY (z)
µX(z) ≤ t
‖z − δ‖1 − ‖z‖1 ≤ β ⇐⇒ µY (z)
µX(z) ≥ t

heading: B PROOF OF THEOREM 1
text: Theorem 1(restated) Let f : Rd → Y be deterministic or random function, and let ∼ L(λ). Let g(x) = arg maxc P (f(x+ ) = c). Suppose PA, PB ∈ [0, 1] are such that
P (f(x+ ) = cA) ≥ PA ≥ PB ≥ max c 6=cA P(f(x+ ) = c)
Then g(x+ δ) = g(x),∀‖δ‖1 ≤ R, where
R = max
{ λ
2 log(PA/PB),−λ log(1− PA + PB)
} (5)
Proof of Theorem 1 Denote T (x) = ‖x − δ‖1 − ‖x‖1. Use Triangle Inequality we can derive a bound for T (x):
− ‖δ‖1 ≤ T (x) ≤ ‖δ‖1 (6)
Pick β1, β2 such that there exists A′ ⊆ {z : T (z) = β1}, B′ ⊆ {z : T (z) = β2}, and P(X ∈ {z : T (z) > β1} ∪A′) = PA ≤ P(f(X) = cA)) P(X ∈ {z : T (z) < β2} ∪B′) = PB ≥ P(f(X) = cB) Define A := {z : T (z) > β1} ∪A′
B := {z : T (z) < β2} ∪B′
Thus, apply Lemma 3.1, we have P(Y ∈ A) ≤ P(f(Y ) = cA) P(Y ∈ B) ≥ P(f(Y ) = cB)
(7)
Then consider P(Y ∈ A) and P(Y ∈ B) P(Y ∈ A) = ∫ A [2λ] −d exp(−‖x− δ‖1 λ )dx
= ∫ A [2λ] −d exp(−‖x‖1 λ ) exp(−T (x) λ )dx ≥ exp(−‖δ‖1 λ ) ∫ A [2λ] −d exp(−‖x‖1 λ )dx = exp(−‖δ‖1 λ )PA
(8)
The inequality is derived by Eqn.( 6). Similarly, we can get
P(Y ∈ B) = ∫ B [2λ] −d exp(−‖x− δ‖1 λ )dx
= ∫ B [2λ] −d exp(−‖x‖1 λ ) exp(−T (x) λ )dx ≤ exp(‖δ‖1 λ ) ∫ B [2λ] −d exp(−‖x‖1 λ )dx = exp( ‖δ‖1 λ )PB
(9)
First, we would like to show that robustness can be guaranteed when R ≤ λ2 log(PA/PB).
If ‖δ‖1 ≤ λ2 log(PA/PB), by Eqn. (7, 8, 9), we have P(f(Y ) = cA) ≥ P(Y ∈ A) ≥ P(Y ∈ B) ≥ P(f(Y ) = cB)
Then, we would like to show that robustness can be guaranteed whenR ≤ −λ log(1−PA+PB).
From Eqn. (9), we know that P(Y ∈ B) ≤ exp(‖δ‖1λ )PB . Besides, by applying Eqn. (9) in set Ac, we can get that P(Y ∈ A) ≥ 1 − exp(‖δ‖1λ )(1 − PA). So we can calculate that if ‖δ‖1 ≤ −λ log(1− PA + PB), we have
P(f(Y ) = cA) ≥ P(Y ∈ A) ≥ P(Y ∈ B) ≥ P(f(Y ) = cB)
Moreover, by simple algebraic operation, we can derive that−λ log(1−PA+PB) ≥ λ2 log(PA/PB) requires 1−2PA(1−PA)− √ 1−4PA(1−PA)
2PA ≤ PB ≤
1−2PA(1−PA)+ √
1−4PA(1−PA) 2PA .
The proof for Theorem 1 is finished.

heading: C PROOF OF THEOREM 2 AND THEOREM 3
text: Theorem 2(restated) (binary case) Let f : Rd → Y be deterministic or random function, and let ∼ L(λ). Let g(x) = arg maxc P (f(x+ ) = c). Suppose there are only two classes cA and cB , and PA ∈ [ 12 , 1] s.t. P (f(x+ ) = cA) ≥ PA Then g(x+ δ) = g(x),∀‖δ‖1 ≤ R, for
R = −λ log[2(1− PA)] (10)
Proof of Theorem 2:
It is similar to the proof of Theorem 1. Pick β3 such that there exists B′ ⊆ {z : T (z) = β3}, and
P(X ∈ {z : T (z) < β3} ∪B′) = PB = P(f(X) = cB) Define
S := {z : T (z) < β3} ∪B′
So we also have P(X 6∈ S) = PA = P(f(X) = cA). Plug into Lemma 3.1, we can get P(Y 6∈ S) ≤ P(f(Y ) = cA) P(Y ∈ S) ≥ P(f(Y ) = cB)
Using a similar method as Eqn. (9), we can get that
P(Y ∈ S) ≤ exp(‖δ‖1 λ )PB
Since we have PB = P(f(X) = cB) = 1− PA ≤ 1− PA
Thus, if ‖δ‖1 ≤ R = −λ log[2(1− PA)], it holds that
P(Y ∈ S) ≤ exp(‖δ‖1 λ )PB
≤ exp(−λ log[2(1− PA)] λ )(1− PA) = 1
2
That is to say, P(f(Y ) = cA) ≥ P(Y 6∈ S) ≥ 12 ≥ P(Y ∈ S) ≥ P(f(Y ) = cB). The proof for Theorem 2 is finished.
Theorem 3(restated) (tight bound in binary case) In the same setting as Theorem 2, assume PA + PB ≤ 1 and PA ≥ 12 . ∀R
′ > −λ log[2(1 − PA)], ∃ base classifier f∗ and perturbation δ∗ with g∗(x) = arg maxc P (f ∗(x+ ) = c) and ‖δ‖1 = R′, s.t. g∗(x) 6= g∗(x+ δ∗).
Proof of Theorem 3: Here, we first set δ = (‖δ‖1, 0, . . . , 0). For simplification, we denote δ = ‖δ‖1.And define
A := { z : |z − δ| − |z| ≥ max{δ + 2λ log [ 2 ( 1− PA )] ,−δ} } Then, we can calculate that
P(X ∈ A) = Px(|x− δ| − |x| ≥ max{δ + 2λ log[2(1− PA)],−δ})
= ∫ −λ log[2(1−PA)] −∞ 1 2λ exp (−|x| λ )dx
= 1− ∫ ∞ −λ log[2(1−PA)] 1 2λ exp ( x λ )dx
= PA
(11)
where x ∼ 12λ exp (− |x| λ ), δ = ‖δ‖1 . Notice that if δ + 2λ log[2(1 − PA)] ≤ −δ, we will get the integral equation by choosing S′. With Eqn. (11), we have
P(X ∈ A) = PA ≤ P(f(X) = cA) (12)
Thus, plug Eqn. (12) into the results of Lem. 3.1, we have
P(Y ∈ A) ≤ P(f(Y ) = cA) (13)
Also, since Y = X + δ, it can be derived that P(Y ∈ A) = ∫ −λ log[2(1−PA)]−δ −∞ 1 2λ exp (−|x| λ )dx (14)
Here we use the consistency of X ∈ A and Y ∈ A. Since Y can be regarded as an offset of X , the integral limit should be translated into the same length. So, if ‖δ‖1 = δ ≤ −λ log[2(1 − PA)], by Eqn. (7) and Eqn. (14), we have
P(f(Y ) = cA) ≥ P(Y ∈ A) ≥ 1
2
This means that the results we get in binary case is a tight bound, and the worst-case δ appears when δ = (δ, 0, . . . , 0). Furthermore, if we slightly enlarge δ, there would be a case that the robustness is destroyed.
The proof for Theorem 3 is finished.

heading: D WHY LAPLACE NOISE INSTEAD OF GAUSSIAN
text: In this section, we theoretically analyze the certification capabilities of Gaussian and Laplace noises. We will show that, given the same base classifier f the parameter of Laplace distributions λ is less sensitive than the parameter of Gaussian distributions σ. Given a base classifier f , where
f(x) = { cA |x| ≤ 1 cB o.w.
and two random smoothing functions
g1(x) = arg max c
P(f(x+ ) = c), ∼ L(0, λ),
g2(x) = arg max c
P(f(x+ ) = c), ∼ N (0, σ2),
we aim to prove that Laplace noises will better protect the original prediction than Gaussian noises. Formally, we compare their Rectified Optional Parameter Space (ROPS), defined as Λ = { √ 2λ : g1(x;λ) = f(x)} and Σ = {σ : g2(x;σ) = f(x)}. Note that the rectified term √
2 is due to the fact that σ = √ 2λ yield the same variance. Essentially, ROPS indicates the feasible region where the smoothing distribution does not negatively impact the base classifier, thus measuring the sensitivity of the smoothing distribution (the larger the better).
First, we would like to compare its prediction on a given point (x, f(x)) = (0, cA). We have
g1(0) = cA ⇐⇒ P(f(0 + ) = cA) ≥ 1 2 ⇐⇒ P(| | ≤ 1) = 1− exp(− 1 λ ) ≥ 1 2 ⇐⇒ λ ≤ 1 log 2 ,
g2(0) = cA ⇐⇒ P(f(0 + ) = cA) ≥ 1 2 ⇐⇒ P(| | ≤ 1) = 2Φ( 1 σ )− 1 ≥ 1 2 ⇐⇒ σ ≤ 1 Φ−1(3/4) .
Since √
2 log 2 > 1 Φ−1(3/4) , Laplace noises have a larger ROPS than Gaussian noises at the point x = 0.
The analysis can be further extended in two cases.
First, if we have x 6= 0, what is the corresponding ROPS that leads to the desired result (g(x) = f(x))? We show in Fig. 10 that we will have a larger ROPS under Laplace noises.
Second, if we have a fixed x but fixed a desired certified radius, what is the corresponding ROPS? We show in Fig. 11 that Laplace noises again have a larger ROPS.
We empirically validate this finding with ResNet110 on CIFAR-10. The resulting smoothed model has 24.8% clean accuracy under a Laplace noise, and 23.7% clean accuracy under a Gaussian noise (with the same variance as the Laplace noise). Here the accuracy is computed with respect to predictions of the base classifier instead of the labels (to illustrate how the smoothing impacts the predictions).

Review summaries:
The authors propose a new certified classifier in \ell_1 norm that is tight. That is to say, upon smoothing a given classifier f with Laplacian noise, a smoothed version of that classifier (probabilistic maximum majority vote) is certified with a radius measured in \ell_1 norm. The authors show that this bound is tight for binary classifiers. These results are complementary to Cohen et al. results.