Certified Distributional Robustness via Smoothed Classifiers 
Authors: Jungang Yang
Liyao Xiang
Ruidong Chen
Yukun Wang
Wei Wang
Xinbing Wang
Venue:  (2021)

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.

A DISTRIBUTIONAL ROBUSTNESS CERTIFICATE BY RANDOMIZED SMOOTHING
Anonymous authors Paper under double-blind review
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 imputs as a robustness metric. Under this metric, we provide tractable upper bound serving robustness, we further propose a noisy adversarial learning procedure to minimize the upper bound following the robust optimization framework. The smoothness 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.
robustness certificate by exploiting the duality. To improve the
INTRODUCTION
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-criticll systems such 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 number of approaches have been proposed for certified robustness, it is vague how ro- bustness should be defined. For example, works including Cohen et al. (2019)][Pine) et al. (2019) 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 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 pertur- bation range, the modification of input instance cannot affect the prediction output. But 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 desired to evaluate the robustness of DNN over the input distribution.
We introduce the distributional risk as DNN robustness metric, and propose noisy adversarial learning (NAL) procedure based on distributional robust optimization, which provides provable guarantee. Assume base classifier trying to map instance Tip to corresponding label y. is found that when fed with the perturbed instance (within a la ball centered at ro), smoothed classifier g(x) = [z[((x (a + 2)] with Z ~ Z A (O, o2 can provably return the same label as g(xo) does. However, we think such robustness guarantee cannot ensure g(æo) 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 2g Po where Po is the distribution of the original input. By using E(-) as the loss function, evaluate DNNs by the worst-case distributional risk: supg Es[((0; s)]. The classifier is

---

parameterized by 8 E θ, and = Po. We prove such a loss is upper bounded by a data-dependent certificate, which can be optimized by the noisy adversarial training procedure:
S where S is distribution within a certain distance from
minimize sup Es Es({(0; s)]. 0E@
(1)
Compared to previous robustness certificates via smoothed classifiers, our method provides a prov- able guarantee w.r.t. the ground truth imput 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 that, for mild perturbations, we adopt a Lagrangian relaxation for the usual loss f(0; x as the robust surrogate, and the surrogate is strongly concave in and hence easy to optimize. Our approach enjoys convergence guarantee similar to the method in |iinaa et al. (2018), but different from (inha et al. (2018), our approach does not require L 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 defi- nition of robustness, and propose to evaluate robustness by the worst-case loss over the input dis- tribution. Second, we derive a data-dependent upper bound for the worst-case loss, constituting robustness certificate. Third, by minimizing the robustness certificate in the training loop, we pro- pose noisy adversarial learning for enhancing model robustness, in which the smoothness property entails the computational tractability of the certificate. Through both theoretical analysis and ex- perimental results, we verify that our certified DNNs enjoy better accuracies compared with the state-of-the-a defending adversarial example attacks.
RELATED WORK
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 adver- sarial examples. Stability training (Zheng et al. y) Zantedeschi et al. (2017); Liu et al. (2018)
improves model robustness by adding randomized noise to the input during training but shows lim-
ited performance enhancement, Adversarial training (Goodfellow al. (2015) y Kurakin et al. (2018)
Madry et al. (2017); : Kannan et al. 2018); Zhang et al. (2019); | He et al. (2019) y Wang et al. (0199)
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 fn-nrrm perturba- tion 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 2Slman Salman al. (2019))). 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 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 applicability than Sinha et al. (2018) with a tighter loss bound due to the smoothness property.
Lagrangian relaxation form of the worst-case loss, but has a broader
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. (0018). Zhang 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 statistically certified robustness guarantee. |Pino al. (2020) have demonstrated by game theory that no deterministic classifier can claim to be more robust than all others against any possible ad- versarial 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 specific neural network, or type of relaxation, but can be generally applied to arbitrary neural networks. The idea of udding randomized noise was first proposed by Lecuyer et al. (2019). given the inspiration of the differential privacy property, and then Li al. (2019) improve the certificate with Rényi divergence. [ohhnn et al.] (2019) obtain a larger certified robustness bound through the smoothed classifier based on Neyman- Pearssn theorem. Phan al. (2020) extend the noise addi- tion 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 ro- bustness adversarial attacks. Lee al. (2019) offer adversarial robustness guarantees for fn-norm attacks. Both [Salman et al. (2019)); Jia et al. (2019) employ adversarial training to improve the per- formance of randomized smoothing. Following a similar principle, 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.
3 PROPOSED APPROACH
We first define the closeness between distributions, based on which we constrain how far the input distribution perturbed. Then we introduce our definition of robustness on smoothed classifiers. Our main theorem gives 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.
3.1 A DISTRIBUTIONAL ROBUSTNESS CERTIFICATE
Definition 1 (Wasserstein distance). Wasserstein distances define a notion of closeness between distributions. Ler (X' C P) be probability space and the transportation cost c. X x X' + [0, d be nonnegative, lower semi-continuous, and c(xx = 0. P and Q are two probability measures supported on X. Let II(P,Q Q) denotes the collection of all measures on X X with factors and π (X, A) QA). VA A and π E II(P. Q). The Wasserstein distance between P and Q is
marginals P and Q on the first and second factors respectively, i.c., it holds that (AA X) P(A)
Qa(PQQ) = inf Ex [e (x,,)))
=EII(..Q)
For example, the 22-norm a0 || xo satisfies the aforementioned conditions.
Distributional robustness. Assume the original input Tn is drawn from the distribution Po. and the perturbed input is drawn from the distribution P. Each input is added randomized Gaussian noise ~ 2 = (0, o² before being fed to the classifier. Instead of regarding the noise as a part of the smoothed classifier, we treat s analysis. Since = E IRd, we need to set X' = Rd to admit E X' as Lecuyer et al. (2019); Cohen et al. 2211)][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: W. (P, Po) S P. E P(X)}, where > O. Within such a region, we evaluate the robustness as a worst-case population loss over noisy inputs: supsEr Es [e(E 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 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 y.
noisy input coming from the distribution S in the

---

As the main theorem of this work, provide upper bound for the worst-case population loss for any level of robustness p. We further show that for small enough p. the upper bound is tractable and easy to optimize.
Theorem 1. Let E O + Th and transportation cost function X X continuous. Let zo be an inpul drawn from the input distribution Po. 3: be the adversarial ex- ample which follows the distribution P and same shape as I. The sum of I and z is denoted as = I + 2 ~ S and we let dy (0; 20) = supzex Ez {E(O; + 2) yo (x + z, xo)} be the robust surrogate. For any T.P > 0 and o, we have
+ be
7 (0, a be the additive noise of the
sup S.W.(S.P))5
Es|e(0; S 70 Er (0:
The proof is given in Appendix A. It is notable that the right-hand side take the expectation over Po and respectively, and given particular input Zo and a noise sample 2, we seek an adversarial example which maximizes the surrogate loss. Typically, Po is impossible to obtain and thus use an empirical distribution, such as the training data distribution, to approximate Po in practice.
Since Thm. I provides upper bound for the worst-case population loss, it offers principled adversarial training approach which minimizes the upper bound instead of the actual loss, i.e.
minimize Ep.lo (0; xo)]] 0
(4)
In the following we show the above loss function a form which is tractable for arbitrary neural networks, due smoothed loss function. Hence Thm. provides a tractable robustness certificate depending on the data.
Properties of the smoothed classifier. We show the optimization objective of Eq. 4 has form which is tractable for any neural network, particular for the non-smooth ones with Re 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 l. : 0 X + [0, M) is bounded loss function. The loss function on the smoothed classifier can be expressed as ē(0;2)) :- -Ez Ez]e(0;; + =)], Z = (0,0021). Then have ê is 2M 0² smooth w.r.t E--norm, i.e., l satisfies
2M o² || x-xx'1 2'1l2-
-
(5)
The proof is in Appendix A.2 It mainly takes advantage of the randomized noise which has smoothing effect on the loss function. For DNNs with non-smooth layers, the smoothed classifier makes it up and turns the loss function to smoothed one, which contributes as an important property to the strong concavity of Ez [e(0; x + 2) - ye (æ + 2, xo)] and therefore ensures the tractability of the robustness certificate.
Corollary 1. For any X + - U (oo) 1-strongly convex in its first argument, and 2M
+ [z](((;x + 2)] being 7 -mooth, the function Ez [e(0; x + z) 7c (x + 2, is strongly concave in x for any y 2 2M
The proof is in Appendix A.3 Note that here specify the requirement the transportation cost to be I-strongly convex in its first argument. The 42-morm cost satisfies the condition. Before showing how the strong concavity plays part in the convergence, illustrate our algorithm first.
3.2 NOISY ADVERSARIAL LEARNING ALOGRITIIM
Problem 4 provides an explicit way to improve the robustness of smoothed classifier parameterized by 8. We correspondingly design 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 Po. and sample number of times to substitute the expectation with

---

the sample average. Assuming have total of training instances zb. Vi E [n]], and sample Zij (0, for the i-th instance for times, the objective is:
1 Y&P
minimize BEG
sup [e(0;2 + 21) 7a (x 2y. xb)]
(6)
==1 TEX
The detail of the algorithm is illustrated in Alg. In the inner maximization step (line 3-6), we adopt the projected gradient descent (PGD Madry et al. (2017): Kurakin et al. (2018) approximate the maximizer according to the convention. The hyperparameters include the number of iterations K and the learning rate 7/1 Within each iteration, sample the Gaussian noise times, given which compute an average perturbation direction for each update. The more noise samples, the closer the averaging result 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 and K is important in practice.
Algorithm Training Phase of NAL
Input: batch size n, number of noise samples r, noise STD o, learning rate m,, f/2 number of iterations K, penalty parameter y, training iterations T
Output: the classifier parameter
I: for fort E {I...., } do
2: for E [1....,]] m] do
3: for k E (0, .0.....A K 1] do
4:
Art = + V 2
E0; o + -6) - Vag. c( + 2zg, 2/), where 2n ~ N0 02)
5:
Fk411 k + m Ark
6: end for
7:
end for
1 Σ i=1 8: ge+1 8" - 112
0(0 De + 25)}3
Vo
9: end for
After training is done, we obtain the classifier parameter 0. In the inference phase, we sample number of (O, o²1) 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 O1//VT), similar to Sinha et al. (2018), but NAL does not need to replace the non-smooth layer ReLU with Sigmoid or ELU guarantee robustness.
4 A TIGHTER BOUND
We compare our work with the state-of siiie--ffthe-arrt robustness definitions and certificates in this section.
4.1 ADVERSARIAL TRAINING
Our approach improves the distributional robustness certificate proposed by Sinha al. (2018). In
Sinha et al. (2018). classifier f maps input instance Zy Po to corresponding label They perturb 2i to x' in the same robustness region as ours: P = {P W. (P, Po) s P E P(X)}
where p 0. But their worst-case population loss is defined on the base classifier without noise:
Ep. [p(0; x')). We show that, given the same classifier parameter 0, our worst-case loss is smaller than Sinha et al. (2018), suggesting better robustness certificate.
(PP
Theorem 3. Under the same denotations and conditions as Thm. 7
we have
sup Es Es(e((;s)) < inf {Yp + Er, (0;,ro)) SeP
720
inf 7p Ep, sup |6(0: x') no (2l, (o0, 720
sup (':W.(P,POSS
Ep [p(:)(()
x'EX

---

The proof is given in Appendix A.3 the tractable upper bound is smaller than the certificate of Sinha et al. (2018). If the outer minimiza- tion problem applies to both sides of the inequality, our approach would obtain smaller loss when both classifiers share the same neural architecture.
We demonstrate that not only the worst-case loss is smaller, but
4.2 SMOOTHED CLASSIFIERS
Works including Lecuyer et al. (211); 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 Ty E X' and its perturbation x within given range || zoll, S E. The smoothed classifier g(x) returns class e; with probability pr. For instance zo, robustness is defined by the largest perturbation radius R which does not alter the instance's prediction, i.e., g(x) classified into the same category g(2o). Such perturbation radius depends on the largest and second largest probabilities of p.. denoted by PB respectively. For example, the results in Cohen et al. (2019)
have shown that R CDF, PA is a lower bound of P. and pB is an upper bound of PB-
④ (PA) Φ (Pg) where & is the inverse of the standard Gaussian
The previous robustness definition only guarantees g(x) to be classi- fied to the same class as g(z)). but ignores the fact that gxx)) may be wrongly classified, which is not precise definition. To make up for it,[Li et al. (2019) propose stability training with noise (STN) and
Moist CNN(ReLU)
100
95
Accoracc
Cohen et al. 2019) adopt training with noise, both of which learn smoothed classifiers mapping noisy inputs to correct labels. How-
90
ever. there is no guarantee to ensure (Io) to be correctly labeled. Ac- tually we found the robustness mainly comes from the STN/training with noise, rather than the noise addition at the inference. In Fig. [ 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/raining with noise (diamond/circle). The result is an evidence that classi- fier 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.
80
Calecie gr11
1.00
12 attatk radius
Figure 1: Accuracies of mod- els trained on MNIST under different levels of & attacks. Undefend means naturally trained model. Solid lines rep- resent models tested with ad- ditive noise, and dotted lines mean that without. a 0.1 means adding Gaussian noise NO 0.1
We consider robustness refers to the ability of a DNN to classify ad- versarial examples into the correct classes, and such an ability should be evaluated on the population of adversarial examples, not a single instance.
5 EXPERIMENT
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 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. SmoothAdy combines adversar- ial 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 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, ResNet- 18, 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(2, mo) = || Fo [| is selected as the cost function.
Training hyperparameters. Table T gives the training hyperparameters in NAL and the batch size is chosen 128. The hyperparameters used in baselines are supplied in Appendix B.T Since NAL.

---

Dataset
V22
epochs
MNIST
0.5/y
1 1x 10
25
0.05
(0.25, 1,5,3
{0.84, 0.34, 0.21
CIFAR-IO(ReNNe-188)
0.5/y
1 10
100
0.1
1.5.5) {0.25,
{1.53, 0.92. 0.40
CIFAR-LO(VGG-BI
0.5/7
1 10 4
100
0.1
(0.25, 15
{1.23, 0.57, 0.28
Tiny ImageNet
0.5/7
2 10
100
0.1
1.5
0.93
Table Hyperparameters and perturbation ranges on different datasets.
Certificate: Ex kcl yp
cost without noise
NAL-40.25
WIRM-y0.25
NAL TRADES
SmoothAdy
Test worst-case: SuRgstale R1
noise
NAL-VL.5
WRM y0.5
-
STN
NAL $2.0
WRM y8.0
MNIST CNN(ELU)
CIFARIO L))
MNIST CNN(RLU)
MNIST CNN(ReLU)
1.2
1.0
Accurasye (a3
Accuracy
Accurngy 100
0.0
B 8
0.0
40
0.4
20
25 10
025
032
0.75
1.0
570
0:32
L75
170
0
12 attack radius
attack radius
1 attack radius
(a)
(b)
(c)
(d)
Figure 2: (a) gives the distance between the robustness certificate (yellow) and the worst-case performance testing data (pink) with example MNIST. The gap between the two lines indicates the tightness of our certificate (Eq. (b)(b)))) (b) compares the performance of two models trained with different c(-)s. The classifier trained with the noise included in the cost has better performance overall, (c) compares the performance of NAL with WRM on MNIST, CNN (ELJU) under different ys. NAL overall has hetter performance than WRM. (d) compares NAL with SmoothAdv, TRADES and STN on MNIST, CNN at y 0.25 and the corresponding NAL does not show significant improvement when y small.
and WRM bound the adversarial perturbations by the Wasserstein distance p which is different from the 2n-mrrm perturbation range in SmoothAdy and TRADES, we need to establish an equiva- lence between the perturbation ranges in different methods. Following the convention {f al. (2018), we choose different and for each we generate adversarial examples x by PGD with 15 iterations. We compute P as the expected transportation cost between the generated adversarial examples and the original inputs over the training set:
e² = p(0) = Erg Ez (x + 2, zo)]-
(8)
And can be computed accordingly. The corresponding values of y and e used in experiments are given in Table Tas 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) the adversarial attack following the convention Li et al. (2019); /inha et al. (2018); Zhang et al. (2019). etc. We set the number of iterations in PGD attack as K Kanack- = 20 and the learning rate 2 Kattnkk where aatck is &g attack radius.
5.1 RESULTS
Certificate. To better understand how close the upper bound is to the true distributional risk, we plot our certificate wp + Ep... [0, against any level of robustness p, and the out-of- sample (test) worst-case performance supsep Es [[( for NAL (Fig. 2 a)). Since the worst- case loss is hard to evaluate directly, we solve its Lagrangian relaxation for different values of Tadv- For each Tadur compute the average distance adversarial examples in the test set as Pust (8) : E Ez [c (2, + z,)0 where Prest is the test data distribution and x, arg max, Ez {E(0; x +2) Tadvo(x + 20))
} is the adversarial perturbation of Zo. The worst-case loss is given by (Prest (0), B_ Ez le (0; x. + =)]). As we observe, Prest (0) tends to increase with 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 18s by letting c(2, xg) = || xoll and inserting noise only to f. We set 7 1.5, mance of the model excluding noise from the cost is far inferior, which shows that the randomized noise is inherent part in the design.
0.1, K = 4, r 4. As Fig. bb) has shown, the accuracy perfor-
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) an example. The result in

---

NAL 10.25
WRM 10.25
NAL
SmosthAN
NAL
WRM V025
SmoothAdv
NAL-y1.
WRM
TRADES
STN
NAL-1.5
WAM.y15
TRADES
STN
NAL-Y6.0
WRM
NAley5.0
WAM-y55.
CIFARIO VGG-16(ELU)
CIFARIO VGG-I6(RcLL)
Tiny ImageNet ResNeLISELU)
Thn ImageNet ResNe(18(ReLL)
Accuracy
Accuracy
Accuracy%%)
Accurayy
8
05
05 radios
25 f2 attnekk radius
attack radios
12 altack
(d) Figure 3: NAL outperforms baselines on CIFAR-IO, VGG-16 and Tiny ImageNet, ResNet-11. (a),C) are trained on ELU models under different ys. For the same 7, NAL exceeds WRM. (b),d) are trained on ReLU models with 7 = 1.5 and the corresponding s. NAL yields the highest robustness under different levels of attack. STN has the highest clean accuracy.
(a)
(b)
(C)
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 combined consideration of computation overhead and accuracy, choose K 4, r by default in the experiments, which is likely to deliver sufficiently good performance. Due to space constraints, complete experimental results are in Appendix B.2
Penalty and noise level. We vary the value of y and a in the experiments to find out their impact. By the results in Fig. (d) and 3
we observe 7 = 0.25 yields the best performance for MNIST, and = 1.5 is best for CIFAR-IO and Tiny ImageNet, considering all levels of adversarial attacks. For a complete result on 7 one can refer to Appendix B.3 Likewise, the best value of a 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 la 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 large margin. For 1), we found STN mostly has far worse performance than other schemes when the attack radius > O, 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 bustness 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 perturba- tions (smaller 7). 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)
Eg attack radius
0.25
0.5
0.75
1.25
1.5
1.75
(K,r) = (4,1)
0.8647
0.7540
0.5950
0.4297
0.2814
0.1713
0.0983
0.0520
(K,r) = (4,4)
0.8546
0.7643
0.6520
0.5202
0.3922
0.2765
0.1811
0.1120
(K,r) = (4,8)
0.8537
0,7622
0.6482
0.5171
0.3846
0,2641
0.1702
0.0997
(K,r) = (8, 1)
0.8593
0.7555
0.6091
0.4630
0.3260
0.2205
0.1453
0.0929
(K,r) = (8,4)
0.8517
0.7663
0.6566
0.5289
0.3970
0.2769
0,1827
0.1129
(K,r) (8,8)
0.8493
0.7582
0.6520
0.5302
0.3978
0.2828
0.1895
0.1151
Table 2: Testing accuracies of NAL (CIFAR-10. ResNet-18) variety of and K. Under each setting, the model with the highest clean accuracy (l2 attack radius = 0) is chosen for testing. Numbers in bold represent the best performance in defending the attack.
CONCLUSION
Our work view the robustness of smoothed classifier from a different perspective, i.e., the worst- case population loss over the input distribution. We provide a tractable upper bound (certificate) for the loss and devise noisy adversarial learning approach to obtain tight certificate. Compared with previous works, our certificate is practically meaningful and offers superior empirical robustness performance.

---

REFERENCES
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. pp. 1310-1320, 2019.
Krishnamurthy Dvijotham, Robert Stanforth, Sven Gowal, Timothy A Mann, and Pushmeet Kohli. A dual approach to scalable verification of deep networks. In UAI, volume 1, pp. 2, 2018.
lan J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. 2015.
Sven Gowal, Krishnamurthy Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Ue- sato, Relja Arandjelovic, Timothy Mann, and Pushmeet Kohli. On the effectiveness of interval bound propagation for training verifiably robust models. arXiv preprint
2018.
Zhezhi He, Adnan Siraj Rakin, and Deliang Fan. Parametric noise injection: Trainable randomness to improve deep neural network robustness against adversarial attack. In Proceedings the IEEE Conference Computer Vision and Puttern Recognition, pp. 588-597, 2019.
Jinyuan Jia, Xiaoyu Cao, Binghui Wang, and Neil Zhenqiang Gong. Certified robustness for top-k predictions against adversarial perturbations via randomized smoothing. In International Confer- ence on Learning Representations, 2019.
Harini Kannan, Alexey Kurakin, and Ian Goodfellow. Adversarial logit pairing. arXiv:1803.06373, 2018.
arXiv preprint
Alexey Kurakin, Ian Goodfellow, and Samy Bengio. Adversarial machine learning at scale. 2018.
Mathias Lecuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified robustness to adversarial examples with differential privacy. In 2019 IEEE Symposium on Security and Privacy (SP), pp. 656-672. IEFE, 2019.
Guang-He Lee, Yang Yuan, Shiyu Chang, and Tommi Jaakkola. Tight certificates of adversarial robustness for randomly smoothed classifiers. In Advances in Neural Information Processing Systems, pp. 4910-4921, 2019.
Bai Li, Changyou Chen, Wenlin Wang, and Lawrence Carin. Certified adversarial robustness with additive noise. In Advances in Neural Information Processing Systems, pp. 9464-9474, 2019.
Xuanqing Liu, Minhao Cheng, Huan Zhang, and Cho-Jui Hsich. Towards robust neural networks via random self-ensemble. In Proceedings of the European Conference on Computer Vision (ECCV), pp. 369-385, 2018.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. 2017.
Matthew Mirman, Timon Gehr, and Martin Vechev. Differentiable abstract interpretation for prov- ably robust neural networks. In International Conference on Machine Learning, pp. 3578-3586, 2018.
Hongseok Namkoong and John C Duchi. Variance-based regularization with convex objectives. In Advances in neural information processing systems, pp. 2971-2980, 2017.
NhatHai Phan, My T Thai, Han Hu, Ruoming Jin, Tong Sun, and Dejing Dou. Scalable differential privacy with certified robustness adversarial learning. 2020.
Rafael Pinot, Laurent Meunier, Alexandre Araujo, Hisashi Kashima, Florian Yger, Cédric Gouy- Pailler, and Jamal Atif. Theoretical evidence for adversarial robustness through randomization. In Advances in Neural Information Processing Systems, pp. 1838-11849, 2019.
Rafael Pinot, Raphael Ettedgui, Geovani Rizk, Yann Chevaleyre, and Jamal Atif. Randomization matters. how to defend against strong adversarial attacks. 2020.

---

Aditi Raghunathan, Jacob Steinhardt, and Perey S Liang. Semidefinite relaxations for certifying robustness to adversarial examples. In Advances in Neural Information Processing Systems, pp. 10877-10887, 2018.
Hadi Salman, Jerry Li, Ilya Razenshteyn, Pengehuan Zhang, Huan Zhang, Sebastien Bubeck, and Greg Yang. Provably robust deep learning via adversarially trained smoothed classifiers. In Advances in Neural Information Processing Systems, pp. 11292-11332 1130, 2019a.
Hadi Salman, Greg Yang, Huan Zhang, Cho-Jui Hsieh, and Pengchuan Zhang. A convex relaxation barrier tight robustness verification of neural networks. In Advances in Neural Information Processing Systems, pp. 9835-9846, 2019b.
Gagandeep Singh, Timon Gehr, Matthew Mirman, Markus Püschel, and Martin Vechev. Fast and effective robustness certification. Advances in Neural Information Processing Systems, pp- (0802-10813, 2018.
Aman Sinha, Hongseok Namkoong, and John Duchi. Certifying some distributional robustness with principled adversarial training. 2018.
Vincent Tjeng, Kai Y Xiao, and Russ Tedrake. Evaluating robustness of neural networks with mixed integer programming. In International Conference on Learning Representations, 2018.
Yisen Wang, Difan Zou, Jinfeng Yi, James Bailey, Xingjun Ma, and Quanquan Gu. Improving adversarial robustness requires revisiting misclassified examples. International Conference on Learning Representations, 2019.
Tsui-Wes Wei Weng, Huan Zhang, Hongge Chen, Zhao Song, Cho-Jui Hsieh, Luca Daniel, and Inderjit Dhillon. Towards fast computation of certified robustness for relu networks. In International Conference on Machine Learning (ICML), 2018.
Eric Wong and Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In International Conference on Machine Learning, pp. 5286-595.. PMLR, 2018.
Valentina Zantedeschi, Maria-Irina Nicolae, and Ambrish Rawat. Efficient defenses against adver- sarial attacks. In Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security, pp. 19-49994922. 2017.
Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric Xing, Laurent El Ghaoui, and Michael Jordan. Theoretically principled trade-off between robustness and accuracy. 2019.
Huan Zhang, Tsui-We Wei Weng. Pin- Yun-Yu&o Chen, Cho-Jui Hsich, and Luca Daniel. Efficient neural net- work robustness certification with general activation functions. In Advances in neural information processing systems, pp. 4939-4948, 2018.
Huan Zhang, Hongge Chen, Chaowei Xiao, Sven Gowal, Robert Stanforth, Bo Li. Duane Boning, and Cho-Jui Hsieh. Towards stable and efficient training of verifiably robust neural networks. 2020.
Stephan Zheng, Yang Song, Thomas Leung, and Ian Goodfellow. Improving the robustness of deep neural networks via stability training. In Proceedings of the ieee conference on computer vision and pattern recognition, pp. 4480-4488, 2016.
A PROOFS
A. PROOF OF THEBREM II
Proof. We express the worst-case loss in its dual form with dual variable 7. By the weak dual property, we have
sup Es {E] SEP
S inf sup (Es[{(0;s)] - - xp) 720 seP
(9)

---

the left hand-side of which can be rewritten in integral form:
inf sup {Es[e(0; + =)] - - +
720 SEP
720 SEP { ( (0:0+++000000 (2)==+))d(())((3)) (W(( (( 70
(10)
inf sup
Note that for any E II(S, Po), we have f(s)dS = JJ (s))dT(s,20) And by the definition of Wasserstein distance, have
{ e(0; ((0:s))S(s) - -W, + 7P)
inf sup SEP
[ʃ]
rEll(S)6)) /f (o) + {p]
inf sup +20 SEP
E(O; ());(, x0) inf
(11)
// [((O:s) 7c(s. [s) + 770 tN0].
inf sup
sup =EIl(S
x20 SEP
By the independence between and 2, zo, one would obtain
/fLe(e: [[((0:)) yc(s, 2o(s,20))dT(s,20) 2o) /|] [100xx 2) 7e(x + 2, (2)) (12)
By taking the maximum over Z.
+ - (1 E2|e(0; + - (2)
(13)
$ /ʃ sup (Bz [<2 r + - 20)3 dr (x( 20).
Fixing x to be value that maximizes the expression to be integrated, x in the formula is fixed, so we only need to integrate dr dx< 20) X. So can get:
/f sup [Ez|<(0;< + 70(x + z, 20 dm( mo)
sup
70(x 2, dP (2r0)
(14)
E p. sup Ez [0 - +, 20)]]
Because the distribution of 2 is definite and 2 is independent of x, and supremum of replaced by the supremum of z. Therefore, Eq. II can be written
[fle(::s) - - top
inf sup 720 SEP
sup =EII(SS)))
< inf sup
sup xe x
Ep, sup Ez|e(0; 70(x x + z, 20)] + 7P
(15)
720 SEP
= inf 720
Ep, sup Ez(e(0; v0(x z, 20) + t
By plugging the above into Eq.
9 could get
sup Es [s[[(A s)] < inf Epg sup Ez [((0) + 2) - ve(a + 2, + 77
SEP
720
(16)
inf EE,, ( (0: mm) + }p} s Ep, 10 + +
220
for any given 7 2 which completes the proof.

---

A.2 PROOF OF THEOREM! 2
Proof. The proof of i being 2M -mooth is equivalent to vl being 2M Lippschiit. We apply the oF
Taylor expansion in vl at zo and set 20 2:
Vi(zo) = vê(x) + v2l(E + 86)6,
(17)
where 0 < 0 < 1. Hence we only need to prove
[2 06) is bounded since |/V + 6) v((x))12 [v - + 88)8|12. By taking the first and second-order derivatives of {(2), we have
vi(x) = (27)a/2 / e(t)( - x) exp (-
1
1 20 | e112 dt,
(18)
and
v2((s)= = (2r)4/20042 | e(t)
(- 1
20 11 1-- - t1|² 1-I+ 22 (t- - x) x) jdt.
(19)
We divide the right hand-side of Eq. 19 into two halves with the first half:
1 (mT) 2/2 d+2
(- 20 |2 - {1p) (-I)dtll2
E(t) exp
JR.
(20)
1 _
M
[1(()) (11)l S oz
I(((2))l2
0²
The second ialf
/ e(t) exp
1
20 || t||²)
((t - zt - x) x) )dtll22
(2 (2r)d/20
I (2x) (2x)4/20a44
exp
|| - t|l?) ||(t - xt x)) 112dt
(21)
20
3R
M
1
Σ (2x))
JAN cxp
|/ t1² ||( x)(t - x) 112dt.
20
Due to the rank of the matrix (t - (t= x) is 1, its lg norm is easy compute:
||(t z)(t x) T l|2 (t x²) T (t- z).
(22)
Hence
M
1 _ || e1(²) ||( =)(t - x) lladt
M
(2x))//2 gd44 d44
Jgd
exp
20
(23)
Finally, combining the two halves we get
2M
V + 00)112 <
(24)
π²
A.3 PROOF OF COROLLARY II
Proof. Since é is 2M af smooth and is 1-strongly convex in its first argument, we have
2M I, and vLl(0;)) 1 -
(25)
E2 (0 +2,20) = v2 [c(x, + do = V2c(2, 20) 2 I.
(26)
Therefore we have
2M
B2 {E(0; x + 2) 7o 2, 200} 3 1 - I.
(27)
Hence the strong concavity is proved for 7 3
2M

---

A.4 CONVERGENCE PROOF
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
VoL((; Vol(0'; x))l+ Loo 0 6111, [V_ - v_((0:
- Luw -a-l x'1l,
(28)
V V)((0;a)) Vol(0;='))]
Lgz||> =' Il, (0):0)))) V =(0' 1 Tu 1 0'|
Let ||- ll. be the dual norm to || -l: we abuse notation by using the same norm || on θ and X Here we have proved the second condition of Assumption holds true by Theorem with Lez 2M
d²
Therefore, if i satisfies the other three conditions, we could adopt similar proof procedure for Theorem 2 in Sinha et al. (2018) to prove the convergence of Algorithm
A.5 PROOF OF THEOREM 3
Proof. By Eq. we could get
sup [s({(0;8)] < inf {Tp + Eps (0: (0: SEP
(29)
720
where
Ep, (0,(0;)0)) = Ep
sup
Ez [e(0; x: + 2) - 7c (x + 2, mo)l
(30)
FEX
Since E(f;a: x + 2) yc (x + 2, .o) is strongly concave for + in Sinha et 2018 by Jensen Inequality we have for any fixed v,
Ez {E(0; x 2) 20
<f(0; 2)) 7c (Bz(2 + 20)
(31)
=((0;z) qa vo).
Hence, the following inequality holds
Ep. (0: < Ep, sup z
(x,,
(32)
By Proposition in Sinha et al. 2018), could get
inf
Ep, sup [f(0; 70 (x,, mo)l + PP
sup [e((0((;)))
(33)
720
Tex
P...((P (PP)Ps
Finally, we can get Eq. by concatenating the inequalities which completes the proof.
A.6 CONNECTIONS BETWEEN ROBUSTNESS CERTIFICATES
Proposition 1. Let PA.PB denote the largest and second largest probabilities returned by the smoothed classifier g(xo) and R ( (PA) x-1 (pT)). We choose i as the cross-entropy
loss the smoothed loss function ((xx = Ez [()) x + 2)], 2 ~~ Z = N(00022))
?(0:x) < log + (pn) + || -
(34)
holds, and the ground truth label y C.. then g(z) is robust against any such that 1 S R.
Proof. By Theorem Cohen et al. 2019), we just need to prove the condition Eq. 34 leads to the condition | roll2 < R. With being the cross-entropy loss
{xx) = Ez [(0 + 2)] = Ezl - log( (v) (I +))]
(35)
Then we use Jensen Inequality log(z)) obtain
(xx) Ez log( (x + =))] 2 -log[Ez (ar z)].
(36)

---

As y CA. we have Ezf = P(f(z + = ca). By Eq.
34
we have
1 --ooll2
P(g(p(( ca)l E + 2)) = log
+b + (PB)
+
o
(37)
And hence
x zol12
P( = + + (pp)
(38)
By the proof of Theorem
in Cohen al. (0119).
2x x0llz
P([( [ =Ca) =
$ (PA)
(39)
which leads to
| - -r-lollz ④- [p
| xolla
Φ (PA)
+
(40)
Therefore,
| zull2
(a-1 PA 2
R.
(41)
To sum up. if Eq. 34 holds and xy is correctly classified, g(x) is robust within a l ball with radius R. One can tell the loss on a single instance is weakly associated with the robustness of the model, and the condition g(x) being robust quite stringent. is not practical to sum up the single-instance loss to gauge the model robustness either.
B EXPERIMENTS
B. BASELINE SETTINGS
We provide the training settings for baselines in Table The learning rate 772 is adjusted according different ys and The noise level (a) is the same for all methods.
Dateset
mechanism
711
172
batch size
epochs
WRM
0.5/y
1 X 10
128
25
STN
X 10
128
25
MNIST
SmoothAdv
6/2
10-1
128
25
TRADES
c/2
1 X 10 10-4
128
25
WRM
0.5/Y
1 X 10
128
100
STN
X 10
128
100
CIFAR-10
SmoothAdv
6/2
1 X 10
128
100
TRADES
6/2
X 10
128
100
WRM
0.5/y
X 10
128
100
STN
X 10 10
128
100
Tiny ImageNet
SmoothAdy
c/2
x 10
128
100
TRADES
c/2
x 10
128
100
Table Baseline hyperparameter settings, 7 and is chosen from Table
B.2 RESULTS WITH VARYING a AND (K,r)
We compare NAL with SmoothAdy 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 a value is different. For example, NAL and STN obtain the best performance at 0.1, whereas SmoothAdy performs best at 0.05. For the same NAL has superior performance than the other two baselines except that, when o = 0.05, SmoothAdy is more robust than NAL for & attack radius 2 0.75. This is mainly because SmoothAdy achieves the best performance when a 0.05. However, the model accuracies degrade below 0.5 is not our main consideration.

---

& attack radius
0
0.25
0.5
0.75
1.25
1.5
1.75
NAL
0.05
0.8579
0.7809
0.6761
0.5549
0.4262
0.2916
0.1888
0.1329
NAL
a 0.1
0.8522
0.8155
0.7684
0.7140
0.6466
0.5684
0.4829
0.3909
NAL
σ 0.2
0.8307
0.7781
0.7213
0.6498
0.5644
0.4785
0.3837
0.2959
AmoothAdy
a 0.05
0.7643
0.7086
0.6378
0.5644
0.4841
0,4050
0.3297
0.2602
SmoothAdv
a 0.1
0.8066
0.7264
0.6281
0,5376
0,4399
0.3467
0.2700
0,2010
SmoothAdy
a 0.2
0.7411
0.6758
0.6079
0.5327
0,4689
0,4005
0.3350
0.2736
STN
σ 0.05
0.8988
0.7347
0,4834
0,2594
0.1167
0.0466
0.0155
0.0063
STN
0.1
0.8669
0.7609
0.6164
0.4416
0.2847
0.1678
0.0927
0.0443
STN
0.2
0.8000
0.7060
0.5867
0.4695
0.3523
0.2472
0.1708
0.1125
Table Different methods with different levels of noise on CIFAR-10, ResNet- 18, 7 1.5 and (K,r) (4, 4). The best performance at the same noise level is in bold.
In Table [] we show NAL's accuracy over a variety of a, K, values. We found that the result of 0.12 is generally better than larger value. Under the same o, we choose K {2, 4, 6, 8), {1.4), We found the model cannot converge with (K, r) (2, 1), and thus did not present the results. The Table show that larger K admits better robustness whereas does not have that impact.
Eg attack radius
0.25
0.5
0.75
T.25
1.5
1.75
K=2
r=4
0,8593
0.8414
0.8152
0.7891
0.7584
0.7177
0,6699
0,6103
K=4
r=1
0,8480
0.8142
0.7772
0.7306
0.6756
0.6185
0.5521
0.4748
K=
r=4 0,8462
0.8129
0.7728
0.7237
0.6692
0.6044
0.5339
0.4646
a a= 0.12
K=6
r=1 0.8528
0,8312
0.8105
0.7803
0.7473
0.7081
0.6585
0.5989
K=6
r=4 0.8424
0.7990
0.7584
0.7022
0.6372
0.5663
0.4853
0.3950
K=8
1=1 0.8526
0.8418
0.8329
0.8194
0.8049
0.7883
0.7670
0.7365
K=8
4
0.8443
0.8025
0.7494
0.6929
0.6250
0.5469
0.4578
0.3758
K=2
1= 0.7522
0.6885
0.6186
0,5403
0.4596
0,3739
0.2971
0.2195
K=2
F=4
0.7953
0.7421
0.6801
0.6069
0,5226
0,4332
0.3498
0.2691
K=4
0.7669
0.7077
0.6399
0.5717
0.4896
0.4103
0.3318
0.2594
K=4
0.8121
0.7679
0.7143
0.6540
0.5882
0.5153
0.4381
0.3622
0 0= 0.25
K=6
0.7632
0.7082
0.6501
0.5790
0.5095
0.4349
0.3569
0.2805
K=6
4
0.8098
0.7578
0.7059
0.6410
0.5677
0.4875
0.4133
0.3300
K=8
r=1 0.7808
0.7285
0.6720
0.6073
0,5273
0,4490
0.3694
0.2951
K=8
4
0,8150
0.7694
0.7132
0.6549
0.5896
0,5185
0.4391
0.3574
K=2
r=1 0.6434
0.5899
0.5335
0.4739
0.4155
0.3524
0.2958
0.2422
K=2
4
0.7122
0.6681
0.6201
0.5717
0.5212
0.4632
0.4090
0.3496
K=4
r=1 0.6744
0.6165
0.5631
0.5048
0.4450
0.3829
0.3226
0.2652
K=4
r=4
0.7186
0.6701
0.6217
0.5699
0.5135
0.4505
0.3966
0.3373
0.5
K=6
r=1 0.6860
0.6335
0.5799
0.5154
0.4566
0.3979
0.3362
0.2811
K=6
1=4 0.7185
0.6771
0.6243
0.5707
0.5174
0.4608
0.4019
0.3455
K=8
1=1
0.6943
0.6424
0,5911
0.5380
0.4758
0,4181
0.3548
0.2968
K=8
0.7239
0.6804
0.6320
0.5836
0.5345
0.4736
0.4250
0.3716
Table 5: NAL with different as and (K, r) on CIFAR-10, 10, ResNet- when ς = 1.16. The best performance under the same noise level is in bold.
E2 attack radius ELJU Model
0.25
0.5
0.75
1,25
1.5
1.75
0.8596
0.8046
0.7348
0.647
0.5465
0.4387
0.3315
0.2351
ReL.U Model
0.8522
0.8155
0.7684
0.714
0.6466
0.5684
0.4829
0.3909
Table 6: Testing accuracies the ReLU model and ELU model on CIFAR-10, ResNet-18.
B.3 RESULTS WITH VARYING 7
We show the impact of y MNIST and CIFAR-10. On MNIST, takes the value {0.25, (.5,5,1.5,33
and a is chosen as 0.05. On CIFAR-10, E {0.25, 1.5, 5) and o is set to 0.1. (K,r) r) = (4,4) for all experiments. Fig. 4a) and 5 a) compare NAL with WRM models with ELU, whereas the rest of Fig. 4 and [5] show the comparison with SmoothAdy, TRADES, and STN on regular models. NAL has superior performance than baselines in almost all cases.

---

NA2-
W5
NAL
SmoothAdv
NAI TRADES
Smoothsdy
NAI
SmoothhAdv
NAL-yL.5
WRM-v1.5
STN
NAL-y3.0
WRN-y3.0
MNIST CNN(ELU)
MNIST CNN(ReLU)
MNIST CNN(ReLU)
MNIST CNN(ReLU)
96-
Accuracy
Accuracy (%)
(corracy
Accuracy Sccuracy"% 52
94
92-
3
20
16:
88
0.
1.00
525
500
025
12 attack radius
1g attack
radius
12 attack radius
(a)
(b)
(c)
(d)
Figure 4: NAL versus baselines MNIST, CNN. (a) NAL WRM for different 7s. (b) 7 0.25. (c)
7 1.5. (d) 7 3. Equivalent are used in SmoothAdv and TRADES.
NA2- NAL-VL55
WRN-vO.25
NAL TRADES
SmoothAdv
SmootwWdv
NAL
SmoothMid
WRN-V1.5
STN
TRADES
TRADES
STN
WRM-V5,0
CIFARIO ReNNEL))()L.))
CIFARIO ResNett((ReLU)
CIFARIO Re(Net1)(ReeLt)
CIFARIO ResNat(((ReL.))
Accuracy9%)
Accuracy (%)
Accuracy
60-
Accuracy (%)
80
0.0
23
0.0
03
10 15
000
05
1.
100
23
10
12 attaack radius
f2 attack radius
f2 attack radius
12 attack radios
(a)
(b)
(c)
(d)
Figure 5: NAL versus baselines on CTEAR-10, ResNet- 18. (a) NAL versus WRM for different ys. (b) 0.25.
(c) y = 1.5. (d) y = 5. Equivalent Es are used in SmoothAdv and TRADES.
The results on MNIST are similar to those obtained in the experiment section. The gaps between NAL and baselines in Fig. c (d) grow larger than that in 4b). which could be explained different values of 7. On CIFAR-10, since we switch to ResNet- 18, the experimental results are slightly different from that VGG-16. The best robustness occurs at 0.25 (Fig. ())) 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 observe on Fig. (c), with an increase of the clean accuracy increases but at the sacrifice of adversarial accuracies. For example, NAL degrades to the performance of SmoothAdy and TRADES at y = 5.
B.4 COMPARISON BETWEEN RELU AND ELU
Here we show the difference between R with ReLU and ELU on CIFAR- for NAL. From Fig. o throughout the training process, the loss of the ReLU model is smaller than that of the ELU
CIFAR1O ResNet18
100
1.5
90
80
Trahing A0dN2
Traisin
70
60
ELU
50
ReLU
40
20
40
60
80
100
Epech
Figure 6: The comparison between the ReLU model (pink) and the ELU model (yellow) CIFAR-10, ResNet-
18 with > 1.5 and σ 0.1. The ReLU model converges faster than the ELU model.

---

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.


Reviews:
[{"review_id": "yK85iVt5xY", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 2, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors use some of the theory from optimal transport to certify the degree of robustness of an image classifier to adversarial perturbation. The theoretical contributions of the work, however, are largely already present, or easily deduced from results that are either already published or available online in a pre-published format. For theorem I have given a brief overview.  My score reflects a strong concern over the degree of originality of the results presented, particularly considering the authors cite some of the papers in which these results can already be found. I welcome the authors and other reviewers to draw my attention to any contributions in the paper I may have overlooked by mistake.\n\n### Theorem 1\nIn essence Theorem 1 corresponds to weak Kantorovich duality for the robust optimal transport problem. The best reference for strong Kantorovich duality in this setting is [Blanchet & Murthy (2019)](https://doi.org/10.1287/moor.2018.0936) and the result is easily deduced from Section 2.2.1. More closely the result can also be deduced from Proposition 1 of [Sinha et al. (2017)](https://arxiv.org/abs/1710.10571),  [Kuhn et al. (2019)](https://pubsonline.informs.org/doi/10.1287/educ.2019.0198) also have a variety of results on this topic. Theorem 1 of  [Cranko et al. (2020)](https://arxiv.org/pdf/2002.04197.pdf) additionally qualifies the tightness of the upper bound and relaxes a number of assumptions of some of the aforementioned papers. There are a number of other, related papers by some of the authors mentioned that I have left out. \n\n### Theorem 2\nTheorem 2 is not particularly surprising. In the proof the authors implicitly assume $\\ell(\\theta,\\cdot)$ is twice differentiable and bounded (for all $\\theta$). The addition of Gaussian noise is an additional complication, but it does not change things too much. The theorem is unsurprising because if it were not true it would lead to an absurd contradiction with the boundedness assumption.  The strong concavity result in the following corollary is also observed by [Sinha et al. (2017)](https://arxiv.org/abs/1710.10571) (at the bottom of page 2).\n\n### Theorem 3\nTheorem 3 was already proven in a significantly more general setting by [Blanchet & Murthy (2019)](https://doi.org/10.1287/moor.2018.0936)  (Theorem 1). Furthermore I am not convinced of the correctness of the proof since there appears to be an assumption that $\\gamma$ is sufficiently larger for $\\ell(\\theta; x) - \\gamma c(x,x_0)$ to be strongly concave. And I cannot even find an assumption that at this point $c(\\cdot, x_0)$  is assumed so much as convex for a choice of $x_0\\in\\mathcal{X}$. \n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "SuYEd0S-tdM", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "##########################################################################\n\nSummary: The authors propose to use the worst-case population loss (with bounded Wasserstein distance) over noisy inputs as a robustness metric. They provide a tractable upper\nbound serving as a robustness certificate by exploiting the duality. The smoothness\nof the loss function ensures the problem easy to optimize even for non-smooth\nneural networks (since these are smoothed by expectation over noisy inputs). They show experiments on a variety of datasets and models to verify that in terms of empirical accuracies, their approach exceeds the state-of-the-art certified/heuristic methods in defending adversarial examples.\n\n\n##########################################################################\n\nReasons for score: \n\nThough the problem setting is not very accurately motivated, I liked the fact that the authors showed distribution dependent guarantees on robustness. It is still unclear to me though why adversarial noise is expected to be within some bounded Wasserstein distance from the probability distribution of the data. Also, their method seems incremental over Sinha et. al's work. Computational experiments look promising. \n\n##########################################################################\n\nPros: \n\n- the authors show a concave upper bound on the loss function and minimize that, \n- they show that their method of \"noisy adversarial learning\" (NAL) has a convergence rate O(1/\\sqrt{T}), which is 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.\n- improved performance in experiments\n\n##########################################################################\n\nCons: \n\n1. The authors say that \"It is found that when fed with the perturbed instance x (within a L2 ball centered at x_0), a smoothed classifier g(x) = E_z[f(x + z)] with z \\sim N (0, \\sigma^2 I) can provably return the same label as $g(x_0)$ does.  However, we think such a robustness guarantee cannot ensure g(x0) to be correctly classified as y, resulting in unsatisfying performance in practice.\" I think there is a language error in this description, but if I understand correctly what the authors are trying to say, the smoothed classifiers are unsatisfying in performance -- however, aren't adversarial perturbations very specific, and therefore, smoothing should actually give more robustness to the model?  \n\n2. \"Instead, we evaluate robustness as the worst case loss over the distribution of noisy inputs\" - wouldn't the worst-case distribution simply place all the probability mass over the most adversarial example in the neighborhood? \n\n3. \"our approach does not require \\ell to be smooth, and thus can be applied to\narbitrary neural networks.\" -- isn't the smoothness simply coming from the expected loss over distributions \"close\" to the input distribution? (This is clear later, since they bound the \"possible probability distributions\" by Wasserstein distances, but very confusing in the introduction.)\n\n4. How loose/tight is the upper bound in Theorem 3? If \\gamma*p is large, then the guarantee is almost meaningless.\n \n##########################################################################\n\nQuestions during rebuttal period: \n\n \nPlease address and clarify the cons above \n\n \n#########################################################################\n\nTypos: \n\n\"The smoothness of the loss function ensures the problem easy to optimize even for non-smooth\nneural networks.\"  -- grammar\n\nThe authors use \"P\" in the introduction before defining it. \\mathcal{P} should be defined as the set of distributions at a bounded distance from P_0!! \n\nGrammatical error: \"But such a question remains open in the randomized regime, where randomized\nsmoothing can be considered as a contributing effort\"\n\n\"Our work view the robustness\" --> \"views\" \n\n\"right-hand side take the expectation\" --> \"takes\"", "extra_scores": {}, "extra_text": {}}, {"review_id": "4JZ9-Doot9A", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 2, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper 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.\n\nThe topic is definitely important and the authors did a good job of explaining their framework. Nevertheless, unfortunately, I think the proposed methodology seems rather straightforward and does not provide many new insights into this area. Besides, there are numerous careless flaws in the paper.\n\n1. Theorem 1 appears to be a standard result in distributional robust optimization and it is unfortunate that the authors did not recognize it. See, for example, Kuhn et al. (2019) (https://arxiv.org/abs/1908.08729).\n\n2. Theorem 2 and Corollary 1 appear to be a standard result in randomized smoothing. Besides, the proof is not rigorous -- it takes for granted that the $\\hat\\ell$ is twice differentiable.\n\n3. The statement of Theorem 3 contains an obvious typo. The left side and the right side are no different from each other -- the only difference is the integration variable: one is $\\hat{x}$ and the other is $x'$.\n\nThat is to say, all three major theoretical results are either straightforward corollary from existing results or contain flaws. \n\n4. The algorithm proposed in Section 3.2 is problematic. In particular, in equation (6) and Alg.1 line 3-6, when $\\cal X$ is a normed vector space, the value of the inner supremum does not depend on $z_{ij}$ simply via a change of variable from $x+z_{ij}$ to $x$. I think the correct version should be \n$$\n  \\frac{1}{n} \\sum_{i=1}^n \\sup_{x\\in\\cal X} [ \\frac{1}{s}\\sum_{j=1}^s \\ell(\\theta;x+z_{ij}) - \\gamma c(x,x_0^i) ].\n$$\n\n5. As for the numerical experiment, it is unclear to me how $\\gamma$ is chosen, and in particular, does such choice make the inner supremum of (6) a strongly concave problem?\n\nGiven these many issues that are not easy to fix, I would encourage the authors to carefully revise their manuscript and resubmit to another conference.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "0ri6Jv6GeRB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper 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.  \n\nTo see the main issue with the paper's problem formulation, note that Theorem 1 results in the adversarial loss function \\phi_{\\gamma}= E_Z[ max_x{...} ] which first maximizes over x\\in \\mathcal{X} (inner operation) and then takes expectation over Z (outer operation). This sequence is also the case in Equation (6) and is the basis of the theoretical and numerical analysis throughout the paper. However, one can see that this objective E_Z[ max_x{...} ] simply reduces to max_x{...} with no expectation over Z. This is because as long as the support set \\mathcal{X} is unconstrained, which is the case in Algorithm 1 applying no projections on X, the maximization solution for x+z will be the same given any outcome Z=z. This is a direct consequence of maximizing a strongly-concave objective in \\phi_{\\gamma} that has a unique maximizer. In fact, I think the opposite order max_x{ E_Z[...] } which hasn't been analyzed in the paper will lead to a properly smoothed optimization problem. I, therefore, suggest redoing the analysis for the properly-ordered max_x{ E_Z[...] }.\n\nFurthermore, Theorem 2 seems incorrect and the constant 2M in the theorem's upper-bound should be replaced with a function of both M and \\sigma. In the theorem's proof, Equation (17) implicitly assumes that \\sigma=1, whereas this assumption has not been mentioned in the theorem. Also, the step from Equation (22) to (23) mistakenly substitutes 1 with M and obtains a constant 2M instead of M+1, while there are no assumptions on M>1. The theorem needs to be revised since the current version is incorrect. Because of the above issues, I don't recommend this paper for acceptance in its current form. The paper should be revised to resolve these major issues. ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors present a framework for deriving distributional robustness certificates for smoothed classifiers under perturbations of the input distribution bounded under the Wasserstein metric. 

Several authors raised concerns regarding the correctness of results presented in the initial version of the paper. While these were addressed during the rebuttal, the reviewers remain concerned about the novelty of the work relative to prior work, in particular the following papers:
https://arxiv.org/abs/1908.08729
https://arxiv.org/pdf/2002.04197.pdf
https://doi.org/10.1287/moor.2018.0936
and the author responses during the rebuttal did not sufficiently address these concerns.

Hence, I recommend rejection.

Decision: Reject