A DISTRIBUTIONAL ROBUSTNESS CERTIFICATE BY RANDOMIZED SMOOTHING
Year: 2020

Abstract:
The robustness of deep neural networks against adversarial example attacks has received much attention recently. We focus on certified robustness of smoothed classifiers in this work, and propose to use the worst-case population loss over noisy inputs as a robustness metric. Under this metric, we provide a tractable upper bound serving as a robustness certificate by exploiting the duality. To improve the robustness, we further propose a noisy adversarial learning procedure to minimize the upper bound following the robust optimization framework. The smoothness of the loss function ensures the problem easy to optimize even for non-smooth neural networks. We show how our robustness certificate compares with others and the improvement over previous works. Experiments on a variety of datasets and models verify that in terms of empirical accuracies, our approach exceeds the state-of-the-art certified/heuristic methods in defending adversarial examples.

heading: 1 INTRODUCTION
text: Deep neural networks (DNNs) have been known to be vulnerable to adversarial example attacks: by feeding the DNN with slightly perturbed inputs, the attack alters the prediction output. The attack can be fatal in performance-critical systems such as autonomous vehicles or automated tumor diagnosis. A DNN is robust when it can resist such an attack that, as long as the range of the perturbation is not too large (usually invisible by human), the model produces an expected output despite of the specific perturbation. Various approaches have been proposed for improving the robustness of DNNs, with or without a performance guarantee.
Although a number of approaches have been proposed for certified robustness, it is vague how robustness should be defined. For example, works including Cohen et al. (2019); Pinot et al. (2019); Li et al. (2019); Lecuyer et al. (2019) propose smoothed classifiers to ensure the inputs with adversarial perturbation to be classified into the same class as the inputs without. However, since both inputs are inserted randomized noise, it cannot be guaranteed that the inputs are classified into the correct class. It is possible that the adversarially perturbed input has the same label as the original one which is wrongly classified by the DNN. In this case, the robustness guarantee does not make sense any more. Further, the robustness guarantee is provided at the instance level, i.e., within a certain perturbation range, the modification of an input instance cannot affect the prediction output. But a DNN is a statistical model to be evaluated on the input distribution, rather than a single instance. Instead of counting the number of input instances meeting the robustness definition, it is desired to evaluate the robustness of a DNN over the input distribution.
We introduce the distributional risk as a DNN robustness metric, and propose a noisy adversarial learning (NAL) procedure based on distributional robust optimization, which provides a provable guarantee. Assume a base classifier f trying to map instance x0 to corresponding label y. It is found that when fed with the perturbed instance x (within a l2 ball centered at x0), a smoothed classifier g(x) = EZ [f(x + z)] with z ∼ Z = N (0, σ2I) can provably return the same label as g(x0) does. However, we think such a robustness guarantee cannot ensure g(x0) to be correctly classified as y, resulting in unsatisfying performance in practice. Instead, we evaluate robustness as the worst-case loss over the distribution of noisy inputs. For simplicity, we jointly express the input instance and the label as x0 ∼ P0 where P0 is the distribution of the original input. By using `(·) as the loss function, we evaluate DNNs by the worst-case distributional risk: supS ES [`(θ; s)]. The classifier is
parameterized by θ ∈ Θ, and s = x+ z ∼ S where S is a distribution within a certain distance from P0. We prove such a loss is upper bounded by a data-dependent certificate, which can be optimized by the noisy adversarial training procedure:
minimize θ∈Θ sup S ES [`(θ; s)]. (1)
Compared to previous robustness certificates via smoothed classifiers, our method provides a provable guarantee w.r.t. the ground truth input distribution. Letting the optimized θ be the parameter of g(·) and f(·) respectively, we further show that the smoothed classifier g(·) provides an improved robustness certificate than that of f(·), due to a tighter bound on the worst-case loss. The key is that, for mild perturbations, we adopt a Lagrangian relaxation for the usual loss `(θ;x+z) as the robust surrogate, and the surrogate is strongly concave in x and hence easy to optimize. Our approach enjoys convergence guarantee similar to the method in Sinha et al. (2018), but different from Sinha et al. (2018), our approach does not require ` to be smooth, and thus can be applied to arbitrary neural networks. The advantage of the smoothed classifier also lies in a tighter robustness certificate than the base classifier. The intuition is that, in the inner maximization step, instead of seeking one direction which maximizes the loss, our approach performs gradient ascent along the direction which maximizes the total loss of examples sampled from the neighborhood of the original input. The noisy adversarial training procedure produces smoothed classifiers robust against the neighborhood of the worst-case adversarial examples with a certified bound.
Highlights of our contribution are as follows. First, we review the drawbacks in the previous definition of robustness, and propose to evaluate robustness by the worst-case loss over the input distribution. Second, we derive a data-dependent upper bound for the worst-case loss, constituting a robustness certificate. Third, by minimizing the robustness certificate in the training loop, we propose noisy adversarial learning for enhancing model robustness, in which the smoothness property entails the computational tractability of the certificate. Through both theoretical analysis and experimental results, we verify that our certified DNNs enjoy better accuracies compared with the state-of-the-art defending adversarial example attacks.

heading: 2 RELATED WORK
text: Works proposed to defend against adversarial example attacks can be categorized into the following categories.
In empirical defences, there is no guarantee how the DNN model would perform against the adversarial examples. Stability training (Zheng et al. (2016); Zantedeschi et al. (2017); Liu et al. (2018)) improves model robustness by adding randomized noise to the input during training but shows limited performance enhancement. Adversarial training (Goodfellow et al. (2015); Kurakin et al. (2018); Madry et al. (2017); Kannan et al. (2018); Zhang et al. (2019); He et al. (2019); Wang et al. (2019)) trains over adversarial examples found at each training step but unfortunately does not guarantee the performance over unseen adversarial inputs. Although without a guarantee, adversarial training has excellent performance in empirical defences against adversarial attacks.
Certified defences are certifiably robust against any adversarial input within an `p-norm perturbation range from the original input. A line of works construct a computationally tractable relaxation for computing an upper bound on the worst-case loss over all valid attacks. The relaxations include linear programming (Wong & Kolter (2018)), mixed integer programming (Tjeng et al. (2018)), semidefinite programming (Raghunathan et al. (2018)), and convex relaxation (Namkoong & Duchi (2017); Salman et al. (2019b)). But those deterministic methods are not scalable. Some works such as Dvijotham et al. (2018) formulate the search for the largest perturbation range as an optimization problem and solve its dual problem. Sinha et al. (2018) also propose a robustness certificate based on a Lagrangian relaxation of the loss function, and it is provably robust against adversarial input distributions within a Wasserstein ball centered around the original input distribution. The certificate of our work is constructed on a Lagrangian relaxation form of the worst-case loss, but has a broader applicability than Sinha et al. (2018) with a tighter loss bound due to the smoothness property.
An alternative line of works propose to select appropriate surrogates for each neuron activation layer by layer (Weng et al. (2018); Zhang et al. (2018)) to facilitate the search for a certified lower bound. By integrating with interval bound propagation (Gowal et al. (2018)), Zhang et al. (2020)
make the search computationally efficient and scalable. Other works (Mirman et al. (2018); Singh et al. (2018)) apply the abstract interpretation to train provably robust neural networks. Our work is orthogonal to these works.
Randomized smoothing introduces randomized noise to the neural network, and tries to provide a statistically certified robustness guarantee. Pinot et al. (2020) have demonstrated by game theory that no deterministic classifier can claim to be more robust than all others against any possible adversarial attack. But such a question remains open in the randomized regime, where randomized smoothing can be considered as a contributing effort. The smoothing method does not depend on a specific neural network, or a type of relaxation, but can be generally applied to arbitrary neural networks. The idea of adding randomized noise was first proposed by Lecuyer et al. (2019), given the inspiration of the differential privacy property, and then Li et al. (2019) improve the certificate with Rényi divergence. Cohen et al. (2019) obtain a larger certified robustness bound through the smoothed classifier based on Neyman-Pearson theorem. Phan et al. (2020) extend the noise addition mechanism to large-scale parallel algorithms. By extending the randomized noise to the general family of exponential distributions, Pinot et al. (2019) unify previous approaches to preserve robustness to adversarial attacks. Lee et al. (2019) offer adversarial robustness guarantees for `0-norm attacks. Both Salman et al. (2019a); Jia et al. (2019) employ adversarial training to improve the performance of randomized smoothing. Following a similar principle, our work trains over adversarial data with randomized noise. But we provide a more practical robustness certificate and a training method achieving higher empirical accuracy than theirs.

heading: 3 PROPOSED APPROACH
text: We first define the closeness between distributions, based on which we constrain how far the input distribution is perturbed. Then we introduce our definition of robustness on smoothed classifiers. Our main theorem gives a tractable robustness certificate which is easy to optimize. Our algorithm for improving the robustness of the smoothed classifiers is provided. All proofs are collected in the appendices for conciseness.

heading: 3.1 A DISTRIBUTIONAL ROBUSTNESS CERTIFICATE
text: Definition 1 (Wasserstein distance). Wasserstein distances define a notion of closeness between distributions. Let ( X ⊂ Rd,A, P ) be a probability space and the transportation cost c : X × X → [0,∞) be nonnegative, lower semi-continuous, and c(x, x) = 0. P and Q are two probability measures supported on X . Let Π(P,Q) denotes the collection of all measures on X × X with marginals P and Q on the first and second factors respectively, i.e., it holds that π(A,X ) = P (A) and π(X , A) = Q(A), ∀A ∈ A and π ∈ Π(P,Q). The Wasserstein distance between P and Q is
Wc(P,Q) := inf π∈Π(P,Q)
Eπ [c (x, y)] . (2)
For example, the `2-norm c(x, x0) = ‖x− x0‖22 satisfies the aforementioned conditions. Distributional robustness. Assume the original input x0 is drawn from the distribution P0, and the perturbed input x is drawn from the distribution P . Each input is added randomized Gaussian noise z ∼ Z = N (0, σ2I) before being fed to the classifier. Instead of regarding the noise as a part of the smoothed classifier, we treat s = x + z as a noisy input coming from the distribution S in the analysis. Since z ∈ Rd, we need to set X = Rd to admit s ∈ X as Lecuyer et al. (2019); Cohen et al. (2019); Salman et al. (2019a) do. Since the perturbed input should be visually indistinguishable from the original one, we define the robustness region as P = {P : Wc (P, P0) ≤ ρ, P ∈ P (X )} , where ρ > 0. Within such a region, we evaluate the robustness as a worst-case population loss over noisy inputs: supS∈P ES [`(θ; s)]. Essentially, we evaluate the robustness of a smoothed classifer based on its performance on the worst-case adversarial example distribution. A smaller loss indicates a higher level of robustness. We will compare the definition against others in the next section. However, such a robustness metric is impossible to measure in practice as we have no idea about P . Even if P can be acquired, it can be a non-convex region which renders the constrained optimization objective intractable. Hence we resort to the Lagrangian relaxation of the problem by assuming a dual variable γ.
As the main theorem of this work, we provide an upper bound for the worst-case population loss for any level of robustness ρ. We further show that for small enough ρ, the upper bound is tractable and easy to optimize.
Theorem 1. Let ` : Θ × X → R and transportation cost function c : X × X → R+ be continuous. Let x0 be an input drawn from the input distribution P0, x be the adversarial example which follows the distribution P and z ∼ Z = N (0, σ2I) be the additive noise of the same shape as x. The sum of x and z is denoted as s = x + z ∼ S and we let φγ (θ;x0) = supx∈X EZ {`(θ;x+ z)− γc (x+ z, x0)} be the robust surrogate. For any γ, ρ > 0 and σ, we have
sup S:Wc(S,P0)≤ρ ES [`(θ; s)] ≤ γρ+ EP0 [φγ(θ;x0)] . (3)
The proof is given in Appendix A.1. It is notable that the right-hand side take the expectation over P0 and Z respectively, and given a particular input x0 and a noise sample z, we seek an adversarial example which maximizes the surrogate loss. Typically, P0 is impossible to obtain and thus we use an empirical distribution, such as the training data distribution, to approximate P0 in practice.
Since Thm. 1 provides an upper bound for the worst-case population loss, it offers a principled adversarial training approach which minimizes the upper bound instead of the actual loss, i.e.,
minimize θ∈Θ EP0 [φγ(θ;x0)]. (4)
In the following we show the above loss function has a form which is tractable for arbitrary neural networks, due to a smoothed loss function. Hence Thm. 1 provides a tractable robustness certificate depending on the data.
Properties of the smoothed classifier. We show the optimization objective of Eq. 4 has a form which is tractable for any neural network, particular for the non-smooth ones with ReLU activation layers. More importantly, the smoothness of the classifier enables the adversarial training procedure to converge as we want by using the common optimization techniques such as stochastic gradient descent. The smoothness of the loss function comes from the smoothed classifier with randomized noise. Specifically,
Theorem 2. Assume ` : Θ × X → [0,M ] is a bounded loss function. The loss function on the smoothed classifier can be expressed as ˆ̀(θ;x) := EZ [`(θ;x+ z)], z ∼ Z = N (0, σ2I). Then we have ˆ̀ is 2Mσ2 -smooth w.r.t. `2-norm, i.e.,
ˆ̀satisfies∥∥∥∇x ˆ̀(θ;x)−∇x ˆ̀(θ;x′)∥∥∥ 2 ≤ 2M σ2 ‖x− x′‖2 . (5)
The proof is in Appendix A.2. It mainly takes advantage of the randomized noise which has a smoothing effect on the loss function. For DNNs with non-smooth layers, the smoothed classifier makes it up and turns the loss function to a smoothed one, which contributes as an important property to the strong concavity of EZ [`(θ;x+ z)− γc (x+ z, x0)] and therefore ensures the tractability of the robustness certificate.
Corollary 1. For any c : X × X → R+ ∪ {∞} 1-strongly convex in its first argument, and ˆ̀ : x 7→ EZ [`(θ;x+ z)] being 2Mσ2 -smooth, the function EZ {`(θ;x+ z)− γc (x+ z, x0)} is strongly concave in x for any γ ≥ 2Mσ2 .
The proof is in Appendix A.3. Note that here we specify the requirement on the transportation cost c to be 1-strongly convex in its first argument. The `2-norm cost satisfies the condition. Before showing how the strong concavity plays a part in the convergence, we illustrate our algorithm first.

heading: 3.2 NOISY ADVERSARIAL LEARNING ALOGRITHM
text: Problem 4 provides an explicit way to improve the robustness of a smoothed classifier parameterized by θ. We correspondingly design a noisy adversarial learning algorithm to obtain the classifier of which its robustness can be guaranteed. In the algorithm, we use the empirical distribution to replace the ideal input distribution P0, and sample z a number of times to substitute the expectation with
the sample average. Assuming we have a total of n training instances xi0,∀i ∈ [n], and sample zij ∼ N (0, σ2I) for the i-th instance for r times, the objective is:
minimize θ∈Θ
1
nr n∑ i=1 r∑ j=1 sup x∈X [ `(θ;x+ zij)− γc ( x+ zij , x i 0 )] . (6)
The detail of the algorithm is illustrated in Alg. 1. In the inner maximization step (line 3-6), we adopt the projected gradient descent (PGD Madry et al. (2017); Kurakin et al. (2018)) to approximate the maximizer according to the convention. The hyperparameters include the number of iterationsK and the learning rate η1. Within each iteration, we sample the Gaussian noise r times, given which we compute an average perturbation direction for each update. The more noise samples, the closer the averaging result is to the expectation value, which is definitely at the sacrifice of higher computation expense. Similarly, a larger number of K indicates stronger adversarial attacks and higher model robustness, but also incurs higher computation complexity. Hence choosing appropriate values of r and K is important in practice.
Algorithm 1 Training Phase of NAL Input: batch size n, number of noise samples r, noise STD σ, learning rate η1, η2, number of
iterations K, penalty parameter γ, training iterations T Output: the classifier parameter θ
1: for t ∈ {1, . . . , T} do 2: for i ∈ {1, . . . , n} do 3: for k ∈ {0, . . . ,K − 1} do 4: ∆xik = 1 r ∑r j=15xik`(θ;x i k + zij)− γ 5xik c(x i k + zij , x i 0), where zij ∼ N (0, σ2I) 5: xik+1 = x i k + η1∆x i k 6: end for 7: end for 8: θt+1 = θt − η2 { 1 nr ∑n i=1 [ 5θ ∑r j=1 `(θ t;xiK + zij) ]} 9: end for
After training is done, we obtain the classifier parameter θ. In the inference phase, we sample a number of z ∼ N (0, σ2I) to add to the testing instance. The noisy testing examples are fed to the classifier to get the prediction outputs.
Convergence. An important property associated with the smoothed classifier is the strong concavity of the robust surrogate loss, which is the key to the convergence proof. The detail of the proof can be found in Appendix A.4. As long as the loss ˆ̀ is smooth on the parameter space Θ, NAL has a convergence rate O(1/ √ T ), similar to Sinha et al. (2018), but NAL does not need to replace the non-smooth layer ReLU with Sigmoid or ELU to guarantee robustness.

heading: 4 A TIGHTER BOUND
text: We compare our work with the state-of-the-art robustness definitions and certificates in this section.

heading: 4.1 ADVERSARIAL TRAINING
text: Our approach improves the distributional robustness certificate proposed by Sinha et al. (2018). In Sinha et al. (2018), a classifier f maps input instance x0 ∼ P0 to corresponding label y. They perturb x0 to x′ in the same robustness region as ours: P = {P : Wc (P, P0) ≤ ρ, P ∈ P (X )} , where ρ > 0. But their worst-case population loss is defined on the base classifier without noise: supP ′:Wc(P ′,P0)≤ρ EP ′ [`(θ;x
′)]. We show that, given the same classifier parameter θ, our worst-case loss is smaller than Sinha et al. (2018), suggesting a better robustness certificate. Theorem 3. Under the same denotations and conditions as Thm. 1, we have
sup S∈P ES [`(θ; s)] ≤ inf γ≥0 {γρ+ EP0 [φγ(θ;x0)]}
≤ inf γ≥0
{ γρ+ EP0 sup
x′∈X [`(θ;x′)− γc (x′, x0)] } = sup P ′:Wc(P ′,P0)≤ρ EP ′ [`(θ;x′)]. (7)
The proof is given in Appendix A.5. We demonstrate that not only the worst-case loss is smaller, but the tractable upper bound is smaller than the certificate of Sinha et al. (2018). If the outer minimization problem applies to both sides of the inequality, our approach would obtain a smaller loss when both classifiers share the same neural architecture.

heading: 4.2 SMOOTHED CLASSIFIERS
text: Works including Lecuyer et al. (2019); Cohen et al. (2019); Pinot et al. (2019); Li et al. (2019) and others guarantee the robustness of a DNN classifier by inserting randomized noise to the input at the inference phase. Most of them do not concern about the training phase, but merely provide a deterministic relationship between the robustness certificate and the additive noise. Specifically, we have the original input x0 ∈ X and its perturbation x within a given range ‖x− x0‖2 ≤ ε. The smoothed classifier g(x) returns class ci with probability pi. For instance x0, robustness is defined by the largest perturbation radiusR which does not alter the instance’s prediction, i.e., g(x) is classified into the same category as g(x0). Such perturbation radius depends on the largest and second largest probabilities of pi, denoted by pA, pB respectively. For example, the results in Cohen et al. (2019) have shown thatR = σ2 ( Φ−1 ( pA ) − Φ−1 (pB) ) where Φ−1 is the inverse of the standard Gaussian CDF, pA is a lower bound of pA, and pB is an upper bound of pB .
The previous robustness definition only guarantees g(x) to be classified to the same class as g(x0), but ignores the fact that g(x0) may be wrongly classified, which is not a precise definition. To make up for it, Li et al. (2019) propose stability training with noise (STN) and Cohen et al. (2019) adopt training with noise, both of which learn smoothed classifiers mapping noisy inputs to correct labels. However, there is no guarantee to ensure g(x0) to be correctly labeled. Actually we found the robustness mainly comes from the STN/training with noise, rather than the noise addition at the inference. In Fig. 1, we could observe that the model performance indeed improves when tested with noise. However, the classifier trained without additive noise (triangle) degrades significantly compared with STN/training with noise (diamond/circle). The result is an evidence that a classifier almost cannot defend adversarial attacks when trained without but tested with additive noise. Therefore, we conclude the smoothed classifier can only improve robustness only if the base classifier is robust.
We consider robustness refers to the ability of a DNN to classify adversarial examples into the correct classes, and such an ability should be evaluated on the population of adversarial examples, not a single instance.

heading: 5 EXPERIMENT
text: Baselines, datasets and models. Testing accuracies under different levels of adversarial attacks are chosen as the metric. We compare the empirical performance of NAL with representative baselines including: WRM (Sinha et al. (2018)), SmoothAdv (Salman et al. (2019a)), STN (Li et al. (2019)) and TRADES (Zhang et al. (2019)). Since WRM requires the loss function to be smooth, we follow the convention to adapt the ReLU activation layer to the ELU layer. SmoothAdv combines adversarial training with the smoothed classifier and claims to be superior than Cohen et al. (2019). Hence we omit Cohen et al. (2019) in comparison. TRADES is an adversarial training algorithm which won 1st place in the NeurIPS 2018 Adversarial Vision Challenge. Experiments are conducted on datasets MNIST, CIFAR-10, and Tiny ImageNet, and models including a three-layer CNN, ResNet18, VGG-16, and their corresponding variants with ReLu replaced by ELU for fair comparison with WRM. The cross-entropy loss is chosen for ` and c(x, x0) = ‖x − x0‖22 is selected as the cost function.
Training hyperparameters. Table 1 gives the training hyperparameters in NAL and the batch size is chosen as 128. The hyperparameters used in baselines are supplied in Appendix B.1. Since NAL
and WRM bound the adversarial perturbations by the Wasserstein distance ρ which is different from the `2-norm perturbation range ε in SmoothAdv and TRADES, we need to establish an equivalence between the perturbation ranges in different methods. Following the convention of Sinha et al. (2018), we choose different γs and for each γ we generate adversarial examples x by PGD with 15 iterations. We compute ρ as the expected transportation cost between the generated adversarial examples and the original inputs over the training set:
ε2 = ρ(θ) = EP0EZ [c (x+ z, x0)] . (8) And ε can be computed accordingly. The corresponding values of γ and ε used in experiments are given in Table 1 as well.
Attack parameters. To evaluate the empirical accuracies for different methods, we adopt the PGD attack Kurakin et al. (2018); Madry et al. (2017) as the adversarial attack following the convention of Li et al. (2019); Sinha et al. (2018); Zhang et al. (2019), etc. We set the number of iterations in PGD attack asKattack = 20 and the learning rate η = 2εattack/Kattack where εattack is `2 attack radius.

heading: 5.1 RESULTS
text: Certificate. To better understand how close the upper bound is to the true distributional risk, we plot our certificate γρ + EP̂test [φγ(θ;x0)] against any level of robustness ρ, and the out-ofsample (test) worst-case performance supS∈P ES [`(θ; s)] for NAL (Fig. 2(a)). Since the worstcase loss is hard to evaluate directly, we solve its Lagrangian relaxation for different values of γadv . For each γadv , we compute the average distance to adversarial examples in the test set as ρ̂test (θ) := EP̂test EZ [c (x? + z, x0)] where P̂test is the test data distribution and x? = arg maxx EZ {`(θ;x+ z)− γadvc(x+ z, x0)} is the adversarial perturbation of x0. The worst-case loss is given by (ρ̂test (θ) ,EP̂test EZ [` (θ;x? + z)]). As we observe, ρ̂test (θ) tends to increase with a higher noise level. Hence we need to keep the noise at an appropriate level to make our certificate tractable.
Cost without noise. To find out if NAL works when noise is removed from the cost, we designed a verification experiment on CIFAR-10 (ResNet-18) by letting c(x, x0) = ‖x − x0‖22 and inserting noise only to `. We set γ = 1.5, σ = 0.1,K = 4, r = 4. As Fig. 2(b) has shown, the accuracy performance of the model excluding noise from the cost is far inferior, which shows that the randomized noise is an inherent part in the design.
Sample number and PGD iterations. We also study the impact of the noise sample number s and PGD iteration K to the model robustness with CIFAR-10 (ResNet-18) as an example. The result in
Table 2 shows that while the model performance enhances with K, it does not necessarily increase with a larger noise samples. We did not test with greater noise samples due to high complexity. For a combined consideration of computation overhead and accuracy, we choose K = 4, r = 4 by default in the experiments, which is likely to deliver a sufficiently good performance. Due to space constraints, complete experimental results are in Appendix B.2.
Penalty and noise level. We vary the value of γ and σ in the experiments to find out their impact. By the results in Fig. 2 (c),(d) and 3, we observe γ = 0.25 yields the best performance for MNIST, and γ = 1.5 is best for CIFAR-10 and Tiny ImageNet, considering all levels of adversarial attacks. For a complete result on γ, one can refer to Appendix B.3. Likewise, the best value of σ also depends on the dataset, shown by the experimental results in Appendix B.2.
Comparison with baselines. Finally, we compare the empirical accuracies with the baselines and the results are presented in Fig. 2 (c),(d) and 3. For WRM, the experiments are conducted on the modified structure of DNNs to ensure smoothness. NAL has superior performance in almost all cases except that: 1) the clean accuracies (denoted by `2 attack radius = 0) on CIFAR-10 and Tiny ImageNet of NAL are inferior to STN; 2) on MNIST, the performance of NAL is no worse but does not exceed baselines by a large margin. For 1), we found STN mostly has far worse performance than other schemes when the attack radius> 0, which echos the proposition in Salman et al. (2019a) that adversarial training brings higher robustness than stability training. Hence it can be explained by the inherent tradeoff between clean accuracy and robustness (Zhang et al. (2019)) that STN has higher clean accuracies than others. Actually, NAL shows better tradeoff between accuracy and robustness than baselines, indicated by the relatively flat accuracy lines. For 2), we think MNIST has a relatively simple decision boundary than the other two datasets and hence allows larger perturbations (smaller γ). Thus the performance boost by NAL is not significant. Actually, when γ is larger, the performance of NAL exceeds baselines by a large margin (Appendix B.3).

heading: 6 CONCLUSION
text: Our work view the robustness of a smoothed classifier from a different perspective, i.e., the worstcase population loss over the input distribution. We provide a tractable upper bound (certificate) for the loss and devise a noisy adversarial learning approach to obtain a tight certificate. Compared with previous works, our certificate is practically meaningful and offers superior empirical robustness performance.

heading: A PROOFS

heading: A.1 PROOF OF THEOREM 1
text: Proof. We express the worst-case loss in its dual form with dual variable γ. By the weak dual property, we have
sup S∈P ES [`(θ; s)] ≤ inf γ≥0 sup S∈P {ES [`(θ; s)]− γWc(S, P0) + γρ} , (9)
the left hand-side of which can be rewritten in integral form:
inf γ≥0 sup S∈P {ES [`(θ;x+ z)]− γWc(S, P0) + γρ}
= inf γ≥0 sup S∈P
{∫ `(θ;x+ z)dZ(z)P (x)− γWc(S, P0) + γρ } .
(10)
Note that for any π ∈ Π(S, P0), we have ∫ f(s)dS = ∫∫ f(s)dπ(s, x0). And by the definition of Wasserstein distance, we have
inf γ≥0 sup S∈P
{∫ `(θ; s)dS(s)− γWc(S, P0) + γρ } = inf γ≥0 sup S∈P {∫∫ `(θ; s)dπ(s, x0)− γ inf π∈Π(S,P0) ∫∫ c(s, x0)dπ(s, x0) + γρ
} = inf γ≥0 sup S∈P { sup
π∈Π(S,P0)
∫∫ [`(θ; s)− γc(s, x0)]dπ(s, x0) + γρ } .
(11)
By the independence between z and x, x0, one would obtain∫∫ [`(θ; s)− γc(s, x0)]dπ(s, x0) = ∫∫∫ [`(θ;x+ z)− γc(x+ z, x0)]dZ(z)dπ(x, x0) (12)
By taking the maximum over x,∫∫∫ [`(θ;x+ z)− γc(x+ z, x0)]dZ(z)dπ(x, x0)
= ∫∫ EZ [`(θ;x+ z)− γc(x+ z, x0)]dπ(x, x0)
≤ ∫∫
sup x {EZ [`(θ;x+ z)− γc(x+ z, x0)]} dπ(x, x0).
(13)
Fixing x to be value that maximizes the expression to be integrated, x in the formula is fixed, so we only need to integrate dπ(x, x0) on X . So we can get:∫∫
sup x {EZ [`(θ;x+ z)− γc(x+ z, x0)]} dπ(x, x0)
= ∫ x0 sup x {EZ [`(θ;x+ z)− γc(x+ z, x0)]} dP0(x0) =EP0 sup x EZ [`(θ;x+ z)− γc(x+ z, x0)].
(14)
Because the distribution of z is definite and z is independent of x, and supremum of S is replaced by the supremum of x. Therefore, Eq. 11 can be written as
inf γ≥0 sup S∈P
{ sup
π∈Π(S,P0)
∫∫ [`(θ; s)− γc(s, x0)]dπ(s, x0) + γρ }
≤ inf γ≥0 sup S∈P
{ sup
π∈Π(S,P0) EP0 sup x EZ [`(θ;x+ z)− γc(x+ z, x0)] + γρ
}
= inf γ≥0
{ EP0 sup
x EZ [`(θ;x+ z)− γc(x+ z, x0)] + γρ
} .
(15)
By plugging the above into Eq. 9, we could get
sup S∈P ES [`(θ; s)] ≤ inf γ≥0
{ EP0 sup
x EZ [`(θ;x+ z)− γc(x+ z, x0)] + γρ } = inf γ≥0 {EP0 [φγ(θ;x0)] + γρ} ≤ EP0 [φγ(θ;x0)] + γρ.
(16)
for any given γ ≥ 0, which completes the proof.

heading: A.2 PROOF OF THEOREM 2
text: Proof. The proof of ˆ̀ being 2Mσ2 -smooth is equivalent to ∇ˆ̀ being 2M σ2 -Lipschitz. We apply the Taylor expansion in ∇ˆ̀at x0 and set δ = x0 − x:
∇ˆ̀(x0) = ∇ˆ̀(x) +∇2 ˆ̀(x+ θδ)δ, (17)
where 0 < θ < 1. Hence we only need to prove ‖∇2 ˆ̀(x + θδ)‖2 is bounded since ‖∇ˆ̀(x + δ) − ∇ˆ̀(x)‖2 = ‖∇2 ˆ̀(x+ θδ)δ‖2. By taking the first and second-order derivatives of ˆ̀(x), we have
∇ˆ̀(x) = 1 (2π)d/2σd+2 ∫ Rd `(t)(t− x) exp ( − 1 2σ2 ‖x− t‖2 ) dt, (18)
and
∇2 ˆ̀(x) = 1 (2π)d/2σd+2 ∫ Rd `(t) exp ( − 1 2σ2 ‖x− t‖2 ) [−I + 1 σ2 (t− x)(t− x)>]dt. (19)
We divide the right hand-side of Eq. 19 into two halves with the first half:
‖ 1 (2π)d/2σd+2 ∫ Rd `(t) exp ( − 1 2σ2 ‖x− t‖2 ) (−I)dt‖2
= 1
σ2 ‖ˆ̀(x)(−I)‖2 ≤
1
σ2 ‖ˆ̀(x)‖2 ≤
M σ2 .
(20)
The second half is
‖ 1 (2π)d/2σd+4 ∫ Rd `(t) exp ( − 1 2σ2 ‖x− t‖2 ) ((t− x)(t− x)>)dt‖2
≤ 1 (2π)d/2σd+4 ∫ Rd |`(t)| exp ( − 1 2σ2 ‖x− t‖2 ) ‖(t− x)(t− x)>‖2dt
≤ M (2π)d/2σd+4 ∫ Rd exp ( − 1 2σ2 ‖x− t‖2 ) ‖(t− x)(t− x)>‖2dt.
(21)
Due to the rank of the matrix (t− x)(t− x)> is 1, its `2 norm is easy to compute:
‖(t− x)(t− x)>‖2 = (t− x)>(t− x). (22)
Hence M
(2π)d/2σd+4 ∫ Rd exp ( − 1 2σ2 ‖x− t‖2 ) ‖(t− x)(t− x)>‖2dt = M σ2 . (23)
Finally, combining the two halves we get
‖∇2 ˆ̀(x+ θδ)‖2 ≤ 2M
σ2 . (24)

heading: A.3 PROOF OF COROLLARY 1
text: Proof. Since ˆ̀ is 2Mσ2 -smooth and c is 1-strongly convex in its first argument, we have
∇2x ˆ̀(θ;x) 2M
σ2 I, and (25)
∇2xEZc(x+ z, z0) = ∇2x [ c(x, x0) + dσ 2 ]
= ∇2xc(x, x0) I. (26) Therefore we have
∇2xEZ {`(θ;x+ z)− γc (x+ z, x0)} ( 2M
σ2 − γ)I. (27)
Hence the strong concavity is proved for γ ≥ 2Mσ2 .

heading: A.4 CONVERGENCE PROOF
text: We start with the required assumptions, which roughly quantify the robustness we provide.
Assumption 1. The loss ˆ̀ : Θ×X → [0,M ] satisfies the Lipschitzian smoothness conditions
‖∇θ ˆ̀(θ;x)−∇θ ˆ̀(θ′;x)‖∗ ≤ Lθθ‖θ − θ′‖, ‖∇x ˆ̀(θ;x)−∇x ˆ̀(θ;x′)‖∗ ≤ Lxx‖x− x′‖, ‖∇θ ˆ̀(θ;x)−∇θ ˆ̀(θ;x′)‖∗ ≤ Lθx‖x− x′‖, ‖∇x ˆ̀(θ;x)−∇x ˆ̀(θ′;x)‖∗ ≤ Lxθ‖θ − θ′‖. (28)
Let ‖ ·‖∗ be the dual norm to ‖ ·‖; we abuse notation by using the same norm ‖ ·‖ on Θ and X . Here we have proved the second condition of Assumption 1 holds true by Theorem 2, with Lxx = 2Mσ2 . Therefore, if ˆ̀ satisfies the other three conditions, we could adopt a similar proof procedure for Theorem 2 in Sinha et al. (2018) to prove the convergence of Algorithm 1.

heading: A.5 PROOF OF THEOREM 3
text: Proof. By Eq. 16 we could get
sup S∈P ES [`(θ; s)] ≤ inf γ≥0 {γρ+ EP0 [φγ(θ;x0)]} , (29)
where
EP0 [φγ(θ;x0)] = EP0 {
sup x∈X
EZ [`(θ;x+ z)− γc (x+ z, x0)] } . (30)
Since `(θ;x + z) − γc (x+ z, x0) is strongly concave for x + z in Sinha et al. (2018), by Jensen Inequality we have for any fixed x,
EZ {`(θ;x+ z)− γc (x+ z, x0)} ≤`(θ;EZ(x+ z))− γc (EZ(x+ z), x0) =`(θ;x)− γc (x, x0) .
(31)
Hence, the following inequality holds
EP0 [φγ(θ;x0)] ≤ EP0 sup x∈X [`(θ;x)− γc (x, x0)] . (32)
By Proposition 1 in Sinha et al. (2018), we could get
inf γ≥0
{ EP0 sup
x∈X [`(θ;x)− γc (x, x0)] + γρ } = sup P ′:Wc(P ′,P0)≤ρ EP ′ [`(θ;x)]. (33)
Finally, we can get Eq. 7 by concatenating the inequalities which completes the proof.

heading: A.6 CONNECTIONS BETWEEN ROBUSTNESS CERTIFICATES
text: Proposition 1. Let pA, pB denote the largest and second largest probabilities returned by the smoothed classifier g(x0) and R = σ2 ( Φ−1 ( pA ) − Φ−1 (pB) ) . We choose ` as the cross-entropy loss in the smoothed loss function ˆ̀(x) = EZ [`(θ;x+ z)], z ∼ Z = N (0, σ2I). If
ˆ̀(θ;x) ≤ − log ( Φ [ Φ−1(pB) +
‖x− x0‖2 σ
]) (34)
holds, and the ground truth label y = cA, then g(x) is robust against any x such that ‖x−x0‖2 ≤ R.
Proof. By Theorem 1 of Cohen et al. (2019), we just need to prove the condition Eq. 34 leads to the condition ‖x− x0‖2 ≤ R. With ` being the cross-entropy loss,
ˆ̀(x) = EZ [`(θ;x+ z)] = EZ [− log(f (y)(x+ z))]. (35) Then we use Jensen Inequality on − log(x) to obtain
ˆ̀(x) = EZ [− log(f (y)(x+ z))] ≥ − log[EZf (y)(x+ z)]. (36)
As y = cA, we have EZf (y)(x+ z) = P (f(x+ z) = cA). By Eq. 34, we have − log[P (f(x+ z) = cA)] ≤ EZ [− log(f (y)(x+ z))] ≤ − log ( Φ [ Φ−1(pB) +
‖x− x0‖2 σ
]) .
(37) And hence P (f(x+ z) = cA) ≥ Φ [ Φ−1(pB) +
‖x− x0‖2 σ
] . (38)
By the proof of Theorem 1 in Cohen et al. (2019),
P (f(x+ z) = cA) = Φ
( Φ−1 ( pA ) − ‖x− x0‖2
σ
) , (39)
which leads to
Φ−1 ( pA ) − ‖x− x0‖2
σ ≥ Φ−1(pB) + ‖x− x0‖2 σ . (40)
Therefore, ‖x− x0‖2 ≤ σ
2
( Φ−1 ( pA ) − Φ−1 (pB) ) = R. (41)
To sum up, if Eq. 34 holds and x0 is correctly classified, g(x) is robust within a `2 ball with radiusR. One can tell the loss on a single instance is weakly associated with the robustness of the model, and the condition of g(x) being robust is quite stringent. It is not practical to sum up the single-instance loss to gauge the model robustness either.

heading: B EXPERIMENTS

heading: B.1 BASELINE SETTINGS
text: We provide the training settings for baselines in Table 3. The learning rate η1 is adjusted according to different γs and εs. The noise level (σ) is the same for all methods.
B.2 RESULTS WITH VARYING σ AND (K, r)
We compare NAL with SmoothAdv and STN under the same experimental setting but different σs. In Table 4, NAL achieves the best performance at σ = 0.1 above all. We believe in different experimental settings, the best σ value is different. For example, NAL and STN obtain the best performance at σ = 0.1, whereas SmoothAdv performs best at σ = 0.05. For the same σ, NAL has superior performance than the other two baselines except that, when σ = 0.05, SmoothAdv is more robust than NAL for `2 attack radius ≥ 0.75. This is mainly because SmoothAdv achieves the best performance when σ = 0.05. However, the model accuracies degrade below 0.5 is not our main consideration.
In Table 5, we show NAL’s accuracy over a variety of σ,K, r values. We found that the result of σ = 0.12 is generally better than a larger value. Under the same σ, we choose K ∈ {2, 4, 6, 8}, r ∈ {1, 4},. We found the model cannot converge with (K, r) = (2, 1), and thus did not present the results. The Table show that a largerK admits better robustness whereas r does not have that impact.
B.3 RESULTS WITH VARYING γ
We show the impact of γ on MNIST and CIFAR-10. On MNIST, γ takes the value {0.25, 1.5, 3} and σ is chosen as 0.05. On CIFAR-10, γ ∈ {0.25, 1.5, 5} and σ is set to 0.1. (K, r) = (4, 4) for all experiments. Fig. 4(a) and 5(a) compare NAL with WRM on models with ELU, whereas the rest of Fig. 4 and 5 show the comparison with SmoothAdv, TRADES, and STN on regular models. NAL has superior performance than baselines in almost all cases.
The results on MNIST are similar to those obtained in the experiment section. The gaps between NAL and baselines in Fig. 4(c)(d) grow larger than that in 4(b), which could be explained different values of γ. On CIFAR-10, since we switch to ResNet-18, the experimental results are slightly different from that on VGG-16. The best robustness occurs at γ = 0.25 (Fig. 5(b)). The performance of STN is consistent with that in the experiment section: it enjoys the highest clean accuracies but much worse performance over adversarial examples. As we observe on Fig. 5(b),(c),(d), with an increase of γ, the clean accuracy increases but at the sacrifice of adversarial accuracies. For example, NAL degrades to the performance of SmoothAdv and TRADES at γ = 5.

heading: B.4 COMPARISON BETWEEN RELU AND ELU
text: Here we show the difference between ResNet-18 with ReLU and ELU on CIFAR-10 for NAL. From Fig. 6, throughout the training process, the loss of the ReLU model is smaller than that of the ELU
model, and ReLU model presents faster convergence. The robustness performance of both models is presented in Table 6. It is clear that in the testing phase, the ReLU model also obtains a better performance. Hence NAL generally yields better performance on ReLU models than ELU models.

Review summaries:
This paper studies the problem of certified robustness in adversarial learning. In a nutshell, they apply the randomized smoothing technique to the distributional robustness certificate proposed by Sinha et al. (2018), thereby relaxing the smoothness assumption required therein so that the ReLU network can be applied. Based on this new formulation, they derive the upper bound on the worst-case population loss and develop an algorithm with convergence guarantees. The results on tested on MNIST, CIFAR-10 and Tiny ImageNet.

This paper proposes smoothing the classifier in the distributional robust learning framework by adding random noise to the input. The smoothed distributional robust framework is used to gain robustness against adversarial perturbations in settings where the classifier is originally non-smooth and then smoothed via the additive noise. While the proposed idea can be potentially useful for training adversarially-robust classifiers over non-smooth function spaces, the paper's theoretical formulation seems to reduce to original non-smoothed distributional robust optimization. Theorem 2 also seems incorrect and its proof suffers from several mistakes.