MACER: Attack-free and Scalable Robust Training via Maximizing Certified Radius
Authors: Runtian Zhai
Chen Dan
Di He
Huan Zhang
Boqing Gong
Pradeep Ravikumar
Cho-Jui Hsieh
Liwei Wang
Venue:  (2020)
Keywords: Adversarial Robustness
Provable Adversarial Defense
Randomized Smoothing
Robustness Certification

Abstract: Adversarial training is one of the most popular ways to learn robust models but is usually attack-dependent and time costly. In this paper, we propose the MACER algorithm, which learns robust models without using adversarial training but performs better than all existing provable l2-defenses. Recent work shows that randomized smoothing can be used to provide a certified l2 radius to smoothed classifiers, and our algorithm trains provably robust smoothed classifiers via MAximizing the CErtified Radius (MACER). The attack-free characteristic makes MACER faster to train and easier to optimize. In our experiments, we show that our method can be applied to modern deep neural networks on a wide range of datasets, including Cifar-10, ImageNet, MNIST, and SVHN. For all tasks, MACER spends less training time than state-of-the-art adversarial training algorithms, and the learned models achieve larger average certified radius.

Published as a conference paper at ICLR 2020
MACER: ATTACK-FREE AND SCALABLE ROBUST TRAINING VIA MAXIMIZING CERTIFIED RADIUS
Runtian Zhai' Chen Dan Di Hel HHuan Zhang? Boqing Gong', Pradeep Ravikumar", Cho-Jui Hsich & Liwei Wang'
!Peking University ²CMU UCLA 'Google "Equal Contribution
{shairuntian, di.he)epku. on, {odan, pradeepx Jace cmu, eddu
huanshangB.cla.ete boginggoEout lock. chohs 1 wehhce.ee...... www.eeee........eeeeeeeeee wanglwBeis pku.edu.cr.
ABSTRACT
Adversarial training is one of the most popular ways to learn robust models but is usually attack-dependent and time costly. In this paper, propose the MACER algorithm, which learns robust models without using adversarial training but per- forms better than all existing provable l2-defenses. Recent work (Cohen al.) 2019) shows that randomized smoothing can be used to provide a certified l2 ra- dius to smoothed classifiers, and our algorithm trains provably robust smoothed classifiers via MAximizing the CErtified Radius (MACER), The attack-free char- acteristic makes MACER faster train and easier optimize. In our experi- ments, we show that our method can be applied to modern deep neural networks on a wide range of datasets, including Cifar-10, ImageNet, MNIST, and SVHN. For all tasks, MACER spends less training time than ofte-of-the-art adversarial training algorithms, and the learned models achieve larger average certified radii. Our code is available at https: : //tgtt/ggtttt com/ Runt i anz macer
INTRODUCTION
Modern neural network classifiers are able to achieve very high accuracy on image classification tasks but are sensitive to small, adversarially chosen perturbations to the inputs (Szegedy et al. 2013] Biggio al. 2013). Given an image æ that is correctly classified by neural network, malicious attacker may find a small adversarial perturbation 8 such that the perturbed image x + 5, though visually indistinguishable from the original image, is assigned wrong class with high confidence by the network. Such vulnerability creates security concerns in many real-world applications.
Researchers have proposed variety of defense methods to improve the robustness of neural net- works. Most of the existing defenses are based on adversarial training (Szegedy et al. [2013] Madry al. 2017 Goodfellow al. 2015 Huang et al. 2015 Athalye et al.) 20188: Ding et al. 2020).
During training, these methods first learn on-the-lly adversarial examples of the inputs with multiple attack iterations and then update model parameters using these perturbed samples together with the original labels. However, such approaches depend on a particular (class of) attack method. It cannot be formally guaranteed whether the resulting model is also robust against other attacks. Moreover, attack iterations are usually quite expensive. As result, adversarial training runs very slowly.
Another line of algorithms trains robust models by maximizing the certified radius provided by ro- bust certification methods (Weng et al.] 2018 Wong & Kolter 2018 Zhang al. 20188; Mirman (et al. 2018: Wang et al., 2018 Gowal et al. 2018 Zhang et al., 2019c). Using linear or convex relaxations of fully connected ReLU networks, robust certification method computes "safe dius" r for a classifier at a given input such that at any point within the neighboring radius-r ball of the input, the classifier is guaranteed to have unchanged predictions. However, the certification methods are usually computationally expensive and can only handle shallow neural networks with ReLU activations, so these training algorithms have troubles in scaling modern networks.
In this work, we propose an attack-free and scalable method to train robust deep neural networks. We mainly leverage the recent randomized smoothing technique (Cohen al. 2019). A randomized smoothed classifier y for an arbitrary classifier f is defined as g(z) E + 7)), in which v) ~ NO o² o'I). While Cohen et al. (2019) derived how to analytically compute the certified radius of the randomly smoothed classifier g. they did not show how maximize that radius to make the classifier

---

Published as a conference paper at ICLR 2020
9 robust. Salman et al. 2019 proposed SmoothAdv improve the robustness of g. but it still relies on the expensive attack iterations. Instead of adversarial training, we propose to learn robust models by directly taking the certified radius into the objective. We outline few challenging desiderata any practical instantiation of this idea would however have to satisfy, and provide approaches to address each of these in turn. A discussion of these desiderata, as well as detailed implementation of our approach is provided in Section[] And as we show both theoretically and empirically, our method numerically stable and accounts for both classification accuracy and robustness.
Our contributions are summarized as follows:
We propose an attack-free and scalable robust training algorithm by MAximizing the CErti- fied Radius (MACER). MACER has the following advantages compared to previous works: Different from adversarial training. we train robust models by directly maximizing the certified radius without specifying any attack strategies, and the learned model can achieve provable robustness against any possible attack in the certified region. Additionally, by avoiding time-consuming attack iterations, our proposed algorithm runs much faster than adversarial training.
Different from other methods (Wong & Kolter 2018) that maximize the certified ra- dius but are not scalable to deep neural networks, our method can be applied to archi- tectures of any size. This makes our algorithm more practical in real scenarios.
We empirically evaluate our proposed method through extensive experiments on Cifar-10, 10, ImageNet, MČIST, and SVHN. On all tasks, MACER achieves better performance than state-of-the-art algorithmss, MACER is also exceptionally fast. For example, on ImageNet, MACER uses 39% less training time than adversarial training but still performs better.
2
RELATED WORK
Neural networks trained by standard SGD are not robust - a small and human imperceptible pertur- bation can easily change the prediction of network. In the white-box setting, methods have been proposed to construct adversarial examples with small for or Eg perturbations (Goodfellow et al.) 2015 Madry al., 2017 Carlini & Wagner 2016, Moosavi-Dezfooli et al. 2015). Furthermore, even in the black-bos box setting where the adversary does not have access to the model structure and parameters, adversarial examples can be found by either transfer attack (Papernot et al. 2016) or optimization-basee approaches (Chen et al. 2017 Rauber et al. 2017 Cheng et al. 2019)) It thus important to study how to improve the robustness of neural networks against adversarial examples.
Adversarial training So far, adversarial training has been the most successful robust training method according to many recent studies. Adversarial training was first proposed in SSzeedy et al. (013) and Goodfellow et al. (2015), where they showed that adding adversarial examples to the training set can improve the robustness against such attacks. More recently, Madry et al. (2017) for- mulated adversarial training as a min-mat optimization problem and demonstrated that adversarial training with PGD attack leads to empirical robust models. Zhhang et al. (2019b) further decomposed the robust error the sum of natural error and boundary error for better performance. Finally, Gao let al. (2019) proved the convergence of adversarial training. Although models obtained by adversar- ial training empirically achieve good performance, they do not have certified error guarantees.
Despite the popularity of PGD-based adversarial training, one major issue is that its speed is too slow. Some recent papers propose methods to accelerate adversarial training. For example, Free- m (Shafahi et al.) 2019) replays an adversarial example several times in one iteration, YOPO-m-n (Zhang et al. 20) restricts back propagation in PGD within the first layer, and Qin et al. (2019) estimates the adversary with local linearization.
Robustness certification and provable defense Many defense algorithms proposed in the past few years were claimed to be effective, but/Athalye et al. (2018) showed that most of them are based on "gradient masking" and can be bypassed by more carefully designed attacks. It is thus important to study how to measure the provable robustness of a network. A robustness certification algorithm takes a classifier f and an input point x as inputs, and outputs a "safe radius" r such that for any subject to ||ô]| < r. f(z) f(r + 5). Several algorithms have been proposed recently. including the convex polytope technique (Wong & Kolter 20188. abstract interpretation methods (Singh et al.
2018 Gehr al. 2018) and the recursive propagation algrithms (Weng al. 2018 /Zhang al.
2

---

Published as a conference paper at ICLR 2020
2018). These methods can provide attack-agnostic robust enror lower bounds. Moreover, to achieve networks with nontrivial certified robust error, one can train a network by minimizing the certified robust error computed by the above-mentioned methods, and several algorithms have been proposed in the past year (Wong& & Kolter] 2018: Wong et al., 2018) Wang et al., 2018 Gowal et al. 2018 Zhang et al. 2019c; Miirman al. 2018). Unfortunately. y, they can only be applied to shallow networks with limited activation and run very slowly.
More recently, researchers found a new class of certification methods called randomized smoothing. The idea of randomization has been used for defense in several previous works (Xie et al. [017]] Liu et al.] 2018) but without any certification. Later on, Lecuyer et al. (2018) first showed that if a Gaussian random noise is added to the input or any intermediate layer. A certified guarantee on small l2 perturbation can be computed via differential privacy. [i et al. (2018) and Cohen et al. (2019) then provided improved ways to compute the & certified robust error for Gaussian smoothed models. In this paper, we propose a new algorithm to train on these l certified error bounds to significantly reduce the certified error and achieve better provable adversarial robustness.
3 PRELIMINARIES
Problem setup Consider a standard classification task with an underlying data distribution Paata
over pairs of examples æ X C H and corresponding labels y E y 21. ... .K}, Usually Pdata is unknown and we can only access a training set S ((11,,1) ),.,..... (In, vn) } in which
(Ia,, M1) is i.i.d. drawn from Pdata- i = 1, 2, ..... , bution over S) is denoted by Pdata. Let f E F be the classifier of interest that maps any x E X' to V. Usually is parameterized by a set of parameters so we also write it as fo.
n.. The empirical data distribution (uniform distri-
We call x' = x + 8 an adversarial example of x to classifier fo if fo can correctly classify x but assigns different label x'. Following many previous works (Cohen et al. 2019 Salman et al,, 2019), we focus on the setting where 5 satisfies & norm constraint | S c. We say that the model To is-rbbust at (xr, y) if it correctly classifies æ as y and for any ||0]| S e, the model classifies x & as y. In the problem of robust classification, our ultimate goal is to find model that is 15-robust at (x, y) with high probability over (z. y) ~ Pdata for a given e > O.
Neural network In image classification we often use deep neural networks. Let up X - R be a neural network, whose output at input x is a vector (z), up (z)). The classifier induced by u1())) is fo(z) arg max,gy ug (x).
In order to train 0 by minimizing a loss function such as cross entropy, we always use a softmax layer on ug normalize it into a probability distribution. The resulting network is =0(:: ;): X + P(K) [
which is given by =0(;; () = (uū((e) Edeye G (u), Ve E ), 8 is the inverse temperature. For simplicity, we will use zz(x) to refer to <e (3 when the meaning is clear from context. The vector 20 =0(2) = (z) (x), ... 28 (x)) is commonly regarded as the "likelihood vector", and =g(x)) measures how likely input r belongs to class c.
Robust radius By definition, the lg-robustness of So at a data point (ar, y) depends on the radius of the largest 12 ball centered at a in which So does not change its prediction. This radius is called the robust radius, which formally defined as
inf || - =xl12, when fo(x) = R(fo; x. v) fo(=)))fu(=))
(1)
.wee fe(x) # y
Recall that our ultimate goal is to train a classifier which rs-robust at (z. y) with high probability over the sampling of (x. ~ Pdata. Mathematically the goal can be expressed as to minimize the expectation of the 0/1 robust classification error. The error is defined as
/01 - (Soz xr, v) == 1 (R((f=2
and the goal is to minimize its expectation over the population
0/1 I (fo) = E E(z,a))paann o (Fo v)-
2011
(3)
'The prohability simplex in R
3

---

Published as a conference paper at ICLR 2020
is thus quite natural to improve model robustness via maximizing the robust radius. Unfortunately, computing the robust radius ①T) of a classifier induced by a deep neural network is very difficult. Weng et al. (2018) showed that computing the I robust radius of deep neural network is NP-hard. Although there is no result for the l2 radius yet, it is very likely that computing the l2 robust radius is also NP-hard.
Certified radius Many previous works proposed certification methods that seek to derive a tight lower bound of R(fo;z, for neural networks (see Section 2 for related work). We call this lower bound certified radius and denote it by CRs x,y) The certified radius satisfies 0 o CR(fo: v) R(fo:x, x. y) for any z.
The certified radius leads to guaranteed upper bound of the 0/1 robust classification error, which called 0/1 certified robust error. The 0/1 certified robust error of classifier fo sample (z, y) is defined as
1/1 ccconiited (fo; x, y) := 1- (CR(fe:n))))))
(4)
i.. a sample is counted as correct only the certified radius reaches e. The expectation of certified robust error over (z, 3) Pdata serves performance metric of the provable robustness:
0/1 e- ce-eenifiedd (So) := "ppaas c centified (fo; x,,)
0/1
(5)
Recall that CR(fe; x. y) is lower bound of the true robust radius, which immediately implies that 1 Lee-cenitial (fo) 1 robaa (fo). Therefore, a small 0/1 certified robust error leads small 0/1 robust classification error.
Randomized smoothing In this work, we use the recent randomized smoothing technique (Cohen itt al. 2019), which is scalable to any architectures, to obtain the certified radius of smoothed deep neura networks. The key part of randomized smoothing to use the smoothed version of fo. which is denoted by go, to make predictions. The formulation of go is defined as follows.
Definition For an arbitrary classifier fe F and > O, the smoothed classifier go of fe is defined as
go(x) = arg max Pn + 7) cc)
(6)
cEY'
In short, the smoothed classifier go(x)) returns the label most likely to be returned by fo when its
input is sampled from Gaussian distribution (xx, o² I) centered at Cohen et al. (019) proves the following theorem, which provides an analytic form of certified radius:
Theorem 1. (Cohen al. 2019) Let fo E F, and 17 NN0 I²1). Let the smoothed classifier go be defined as in (6) Let the ground truth of an input x. be y. If go classifies x correctly, i.e.
Pa(fo(æ + 17) = v) Z max ma
17) =s)
v'4y
Then go is provably robust at x. with the certified radius given by
CR(go: x. y) = g
- (P,(fo( 7) = y)) - $b - (max Pry (f + n) = -/1i
2
1f #
(8)
o 1 ((o & -- (max 1 (((+tt)))))) y fリ
=
where &o is the c.d.f. of the standard Gaussian distribution.
4 ROBUST TRAINING VIA MAXIMIZING THE CERTIFIED RADIUS
As we can see from Theorem 1, the value of the certified radius can estimated by repeatedly sampling Gaussian noises. More importantly, it can be computed for any deep neural networks. This motivates us to design a training method to maximize the certified radius and learn robust models.
To minimize the 0/1 robust classification error in 3 or the 0/1 certified robust error in (). many previous works (Zhang et al. 2019b Zhai et al. 2019) proposed to first decompose the error. Note that a classifier go has a positive 0/I certified robust error on sample (z, y) if and only if exactly one of the following two cases happens:
4

---

Published as a conference paper at ICLR 2020
go(x)) y, i.. the classifier misclassifies
(o( y, but C' x. v) < c, i.e. the classifier is correct but not robust enough.
Thus, the 0/1 certified robust error can be decomposed as the sum of two error terms: a 0/1 classifi- cation error and 0/1 robustness error:
p/1 certtified (go: 2; y) =1 [CR(G002.))24)
1 (no(x))())
+1 C
(9)
011 Classification Error
0V1 Robustness Eror
4.1 DESIDERATA FOR OBJECTIVE FUNCTIONS
Minimizing the 0-1 еπтоr directly is intractable. A classic method is to minimize surrogate loss instead. The surrogate loss for the 0/1 classification error is called classification loss and denoted by lo(go; y). The surrogate loss for the 0/1 robustness error is called robusiness loss and denoted by In(go; x. y). Our final objective function
Mgo; v. y) (go; v) + In(go v.
(10)
We would like our loss functions (g(; x, y) and (n(go x, v) to satisfy some favorable conditions. These conditions are summarized below as (C1) (C3):
(C1) (Surrogate condition): Surrogate loss should an upper bound of the original er- ror function, i.c. (c(g;; 2, y) and (n(g0; should be upper bounds of (1)))t)) and
(Re(:)=y.CR(gov..)eee respectively.
(C2) (Differentiablityy): 1c(00; v) and In(oo;r,)) should be (sub-)diifereentiable with respect to
(C3) (Numerical stability): The computation of le (ge: ggradients with respect to 0 should be numerically stable.
(ge x, y) and (g x, 3) and their (sub-
The surrogate condition (C1) ensures that [ggo; y) itself meets the surrogate condition, i.e.
Vgg:; x, y) = (g(::; + Le [o: x; y) 2 0/1
C-couune x, y)
(11)
Conditions (C2) and (C3) ensure that TTP can be stably minimized with first order methods.
4.2 SURROGATE LOSSES (FOR CONDITION C1)
We next discuss choices of the surrogate losses that ensure satisfy condition (C1). The classifi- cation surrogate loss is relatively easy to design. There are many widely used loss functions from which we can choose, and in this work choose the cross-entropy loss the classification loss:
(go(z))v) S lg(g, v) = (c
(12)
For the robustness surrogate loss, we choose the hinge loss on the certified radius:
(13)
S X max (e + ē CR(go; v). [0o())==) == In(go; x, x.
where ē 0 and A > 1. We use the hinge loss because not only does it satisfy the surrogate condition, but also it is numerically stable, which will discuss in Section 4.4
4.3 DIFFERENTIABLE CERTIFIED RADIUS VIA SOFT RANDOMIZED SMOOTHING (FOR CONDITION C2)
The classification surrogate loss in 12)
is differentiable with respect to 6, but the differentiability
of the robustness surrogate loss in [1 requires differentiability of CRigo x. y). In this section
5

---

Published as a conference paper at ICLR 2020
will show that the randomized smoothing certified radius in (8) does not meet condition (C2), and accordingly, we will introduce soft randomized smoothing to solve this problem.
Whether the certified radius (8) is sub-differentiaabe with respect to & boils down to the differ- entiablity of ( Theoretically, the expectation indeed differentiable. However, from practical point of view, the expectation needs to be estimated by Monte Carlo sampling (f((()(())))))))) ~ R E (()( where πy i.idd Gaussian noise and is the number of samples. This estimation, which sum of indicator functions, is not differentiable. Hence, condition (C2) is still not met from the algorithmic perspective.
To tackle this problem, leverage soft randomized smoothing (Soft-RS). In contrast to the original version of randomized smoothing (Hard-RS), Soft-RS is applied to neural network 20(2)) whose last layer is softmax. The soft smoothed classifier ge is defined as follows.
Definition 2. For neural network zq X + P(K) whose last layer is softmax and a > 0, the soft smoothed classifier go of ze is defined as
(o( arg max B,-- ccY
(14)
Using Lemma 2 in Salman et al. 2201), we prove the following theorem in Appendix Theorem 2. Let the ground truth of input x be y. If go classifies z correctly, i.e.
E,yla (a n)l max maxx,1122 12y (x + 1))l
(15)
Then ğo is provably robust at with the certified radius given by CR v. y) = i (E, + m)) - + (max E,lly (x m))l
(16)
y'
where t is the c.d.f. of the standard Gaussian distribution.
We notice that in Salman et al. 2019) (see its Appendix B), a similar technique was introduced to overcome the non-differnntiabiliyy in creating adversarial examples to a smoothed classifier. Dif- ferent from their work, our method uses Soft-RS to obtain a certified radius that is differentiable in practice. The certified radius given by soft randomized smoothing meets condition (C2) in the algorithmic design. Even we use Monte Carlo sampling to estimate the expectation, (16) still sub-differentiable with respect to long 2g is sub-differentiable with respect to A.
Connection between Soft-RS and Hard-RS We highlight two main properties of Soft-RS. Firstly, it is differentiable approximation of the original Hard-RS. To see this, note that when + 0o, = (x; a.Si [ max, (x())), so ğe converges to ge almost everywhere. Conse- quently, the Soft-RS certified radius (T6) converges to the Hard-RS certified radius (8) almost every- where as 3 goes to infinity. Secondly, Soft-RS itself provides an alternative way to get a provable robustness guarantee. In Appendix [ will provide Soft-RS certification procedures that certify Ze with the Hoeffding bound or the empirical Bernstein bound.
4.4 NUMERICAL STABILITY (FOR CONDITION C3)
In this section, we will address the numerical stability condition (C3). While Soft-RS does provide us with a differentiable certified radius (T6) which we could maximize with first-order optimization methods, directly optimizing (16) suffers from exploding gradients. The problem stems from the inverse cumulative density function Φ- -z1(x,, whose derivative is huge when x: is close to 0 or 1.
Fortunately, by minimizing the robustness loss (3) instead, we can maximize the robust radius free from exploding gradients. The hinge loss restricts that samples with non-zero robustness loss must satisfy < CR(āe; x, v) < e + ē, which is equivalent to 0 Ee 2) < 7 where Eo y) = 4 (EE n))) 4 -- (max,' E, (z + r)]) and 7 2(cta) Under this restriction, the derivative of h- is always bounded as shown in the following proposition. The proof can be found in Appendix B
Proposition 1. Given any Pi. PK satisfies p1 2 P2 2 ... 2 PK 2 0 and p1 P2 + + = 1,
let 7 2(c+ē) the derivative of ofmin minn((--((m)) - (p-() 7) with respect to pr and p2 is bounded.

---

Published as a conference paper at ICLR 2020
4.5 COMPLETE IMPLEMENTATION
We are now ready to present the complete MACER algorithm. Expectations over Gaussian samples approximated with Monte Carlo sampling. Let ",, 7 be i.id samples from (0, o TT). The final objective function is
[@ee 2. v) = (o( y) + [go
= log 20 (x) + À m + ē C'Rioot v). [ (x)
(17)
= log (xr) + Ao
max(7 - Ea(o, v), 0} (g)(z)==)
2
where (x) 3: Eÿ=1 20 x + n1)) is the empirical expectation of 20(1 + 11) and (0 y)
(x)())) + -1 1 (max,/ By 2/ (z)). During training we minimize B(z,g))-paat [@o; xz y). De- tailed implementation is described in Algorithm | To simplify the implementation, we choose y to be a hyperparameter instead of ē. The inverse temperature of softmax also a hyperparameter.
Algorithm MACER: robust training via MAximizing CErtified Radius
1: Input: Training set Pasta noise level number of Gaussian samples k trade-off factor X, hinge factor y, inverse temperature 3, model parameters 0
2: for each iteration do
3: Sample a minibatch (x1, 1/1...... (In: yn) ~ Pdata
4: For each 2;, sample ls i.i.d. Gaussian samples Fs1," Fas o(z,021)
5: Compute the empirical expectations: (x(x)) + Ei=1 zo z0(zz)//k i....
6: Compute Go = { y4) Go (2,) = y (I.. Vi) E Go + yi arg max,ey (2;)
7: For each (1:4 E Gg. compute ju: ÿt arg ca =3(
8: For each (I; 3/) E Ga. compute (x): Eo(2; M1) + Φ (="' (x:)) (x:)) (2 (x:))
9:
Update with one step of any first-order optimization method to minimize
log aMh (xt)
Σ
maxf7 - Eo v.),
71
2n ECo
10: end for
Compare to adversarial training Adversarial training defines the problem as a mini-max game and solves it by optimizing the inner loop (attack generation) and the outer loop (model update) iteratively. In our method, we only have a single loop (model update). As a result, our proposed algorithm can much faster than adversarial training because it does not require additional back propagations to generate adversarial examples.
Compare previous work The overall objective function of our method, linear combination of a classification loss and a robustness loss, is similar to those of adversarial logit pairing (ALP) (Kannan et al., 2018) and TRADES (Zhang et al., 2019b). In MACER, the in the objective function (17) can also be viewed as trade-off factor between accuracy and robustness. However, the robustness term of MACER does not depend on a particular adversarial example x', which makes it substantially different from ALP and TRADES.
5 EXPERIMENTS
In this section, we empirically evaluate our proposed MACER algorithm on a wide range of tasks. We also study the influence of different hyperparameters in MACER the final model performance.
5.1
SETUP
To fairly compare with previous works, we follow Cohen et al. 2019) and Salman et al. (2019) to use LeNet for MNIST, ResNet-1 10 for Cifar-10 10 and SVHN, and ResNet-50 for ImageNet.

---

Published as a conference paper at ICLR 2020
MACER Training For Cifar-10, MNIST and SVHN, train the models for 440 epochs using our proposed algorithm. The learning rate is initialized to be 0.01, and is decayed by 0.1 at the 2400h epoch. For all the models, we use k 16, 7 8.0 and / 16.0. The value of À trades off the accuracy and robustness and we find that different À leads to different robust accuracy when the model is injected by different levels (o) of noise. We find setting À 12.0 for
0.25 and == 4.0 for о 0.50 works best. For ImageNet, we train the models for 120 epochs, The initial learning rate is set to be 0.1 and is decayed by 0.1 the 30"/600"/00" epoch. For all models on ImageNet, we use k 2, = 8.0 and 3 16.0. More details can be found in Appendix
Baselines We compare the performance of MACER with two previous works. The first work (Cohen et 2019) trains smoothed networks by simply minimizing cross-entrope loss. The second one (Salman et al. 2019) uses adversarial training on smoothed networks to improve the robustness. checkpoints provided by the authors and report their original numbers whenever available. In addition, we run Cohen et al. (2019)'s 's method on all tasks as it is a speical case of MACER by setting k- and X O.
For both baselines,
Certification Following previous works, we report the approximated certified test set accuracy, which the fraction of the test set that can be certified to be robust at radius r. However, the approximated certified test set accuracy is a function of the radius r. It is hard to compare two models unless one is uniformly better than the other for all r. Hence, we also use the average certified radius (ACR) as metric: for each test data (Ir, y) and model y. we can estimate the certified radius CRigg; x. y). The average certified radius defined [Scoes] (x,,)) CR(g; 2; y) where Stest is the test set. To estimate the certified radius for data points, we use the source code provided by Cohen et al. 2019).
1
5.2 RESULTS
We report the results on Cifar-10 and ImageNet in the main body of the paper. Results on MNIST and SVHN can be found in Appendix C.2
Table I: Approximated certified test accuracy and ACR on Cifar- 10: Each column an le radius.
Model
0.00
0.25
0.50
0.75
1.00
1.25
1.50
1.75
2.00
2.25
ACR
Cohen-0.22
0.75
0.60
0.43
0.26
0
0
0
0
0
0
0,416
0.25
Salman-0.25
0.74
0.67
0.57
0.47
0
0
0
0
0.538
MACER-0.25
0.81
0.71
0.59
0.43
0
0
0.556
Cohen-0.55
0.65
0.54
0.41
0.32
0.23
0.15
0.09
0.04
0
0
0.491
0.50
Salman-0.50
0.50
0.46
0.44
0.40
0.38
0.33
0.29
0.23
0
0.709
MACER-0.55 -0.50
0.66
0.60
0.53
0.46
0.38
0.29
0.19
0.12
0.726
Cohen-1 1.00
0.47
0.39
0.34
0.28
0.21
0.17
0.14
0.08
0.05
0.03
0.458
1.00
Salman-
0.45
0.41
0.38
0.35
0.32
0.28
0.25
0.22
0.19
0.17
0.787
MACER-1.00
0.45
0.41
0.38
0.35
0.32
0.29
0.25
0.22
0.18
0.16
0.792
MAGER 0.25
MAGER 0.50 Cahen-0.50
MACER 1.00
Carlilied sccuracy
Cohen-0.28
Cartilie socuracy
0.B
Cortified nogurapy
0.8
Cahen-1130
25.
Sa0men-0050
Salman-1.00
0.6
0.6
0.6
0.4
0.4
0.4
0.2
0.2
0
0.5 A radius
0.5
1/ redius
redius
(a) J = 0.25
(b)
0.50
(c)
1.00
Figure 1: Radius-accuracy curves of different Cifar- 10 models.
8

---

Published as a conference paper at ICLR 2020
Table 2: Approximated certified test accuracy and ACR on ImageNet: Each column an le radius.
Model
0.5
1.0
1.5
2.0
2.5
3.0
ACR
Cohen-0.25
0.67
0.49
0
0
0
0
0.470
0.25
Salman-0.25
0.65
0.56
0
0
0
0
0
0.528
MACER-0.25
0.68
0.57
0
0
0
0.544 0
Cohen-0.50
0.57
0.46
0.37
0.29
0
0.720
0.50
Salman-0.50
0.54
0.49
0.43
0.37
0
0
0.815
MACER-0.55
0.64
0.53
0.43
0.31
0
0
0.831
Cohen-I.00
0.44
0.38
0.33
0.26
0.19
0.15
0.12
0.863
1.00
Salman-1.00
0.40
0.37
0.34
0.30
0.27
0.25
0.20
1.003
MACER-1.00
0.48
0,43
0.36
0.30
0.25
0.18
0.14
1.008
MACER-0.25
MACER-0.50
MACER-1000
Certiied accurac
0.8
-Coeen 0.25
Certiiied acsuracy
0.8
-Cohon-0.58 0.50
Cerffied acquracy
0.8
-Cohon 1ahhon-1.00
0.6
0.6
0.4
0.4
0.2
0.2
0.2
0.5 l radius
0.5
1.5
o 0.25
(b)
0.50
(c) 1.00
Figure 2: Radius-accuracy curves of different ImageNet models.
Performance The performance of different models on Cifar- 10 are reported in Table 1 and in Figure [ we display the radius-accuracy curves. Note that the area under radius-accuracy curve is equal to the ACR of the model. First, the plots show that our proposed method consistently achieves significantly higher approximated certified test set accuracy than Cohen et al. (2019). This shows that robust training via maximizing the certified radius is more effective than simply minimizing the entropy classification loss. Second, the performance of model is different from that of Salman et al. (2019) for different r. For example, for a = 0.25, our model achieves higher accuracy Salman al. (2019)'s model when 0/0.25/0..0 0.5,, but the performance of ours worse when r 0.75. For the average certified radius, our models are better than Salman et al. (2019)'s model in all settings. For example, when o 0.25/0.50. the ACR our model is about 3% larger than that of Salman et al. (2019)'s. 's. The gain of our model is relatively smaller when o = 1.0. This is because 1.0 very large noise level (Cohen et al. 2019) and both models perform poorly. The ImageNet results are displayed in Table 2 and Figure and the observation is similar. All experimental results show that our proposed algorithm more effective than previous ones.
Training speed Since MACER does not require adversarial attack during training, it runs much faster to learn a robust model. Empirically, we compare MACER with Salman et al. (2019) on average training time per epoch and the total training hours, and list the statistics in Table 3 For fair comparison, we use the codesill provided by the original authors and run all algorithms on the same machine. For Cifar-10 10 we one NVIDIA P P100 GPU and for ImageNet P100 GPUs. According to our experiments, on ImageNet, MACER achieves ACR=0.544 117.90 hours. On the contrary, Contrary.SSllmnn clearly shows that our method is much more efficient.
use four NVIDIA
[Salman et al. (2019) only achieves ACR=0.528 but uses 193.10 hours, which
One might question whether the higher performance of MACER comes from the fact that train for more epochs than previous methods. In Section C.3 we also run MACER for 150 epochs and compare it with the models in Table The results show that when run for only 150 epochs, MACER still achieves performance comparable with SmoothAdv, and is 4 times faster at the same time.
Salman et al. 2019 releases hundreds of models, and select the model with the largest average certified baseline.
radius for each
ht / //t::////iii thub. com cow/ wwt.uusshsaamccccccaa.aa..a.a
https: thwb. Hadi man/ man/smoothing--dduee atw.

---

Published as a conference paper at ICLR 2020
Table 3: Training time and performance of 0.25 models.
Dataset
Model
sec/epoch
Epochs
Total hrs
ACR
Cohen-0.25 (Cohen al.
2019
31.4
150
1.31
0.416
Cifar-10
Salman-0.25 20225 5 Salman et al.
2019
1990.1
150
82.92
0.538
MACER-0.25 (ours)
504.0
440
61.60
0.556
Cohen-0.25
(Cohen al.
2019
2154.5
90
53.86
0.470
ImageNet
Salman-0.25 (Salman et al.
2019
7723.8
90
193.10
0.528
MACER-0.25 (ours)
3537.1
120
117.90
0.544
Cenibed RcceRa02
Oentie acqUA40
150
0.6
06
0.
16.3
0.6
6.4
(a) Effect of k
(b) Effect of X
(c) Efffect of
(d) Effect of B
Figure 3: Effect of hyperparameters on Cifar- 10 (a 0.25).
5.3 EFFECT OF HYPERPARAMETER
In this section, we carefully examine the effect of different hyperparameters in MACER, All exper- iments
Cifar-10 10 with 0.25 0.50. The results for 0.25 are shown in Figure All details can be found in Appendix C.4
Effect of k We sample & Gaussian samples for each input to estimate the expectation in (16). We can see from Figure ((a) example, the radius-accuracy curve of k 16 is uniformly above that of l: = 1.
tha)that that using more Gaussian samples usually leads to better performance. For
Effect of À The mudius-accuran curves Figure 3(b) demonstrate the trade-off effect of A. From the figure, large radii increases.
see that as increases, the clean accuracy drops while the certified accuracy
Effect of y defined as the hyperparameter in the hinge loss. From Figure 3(c) when y is small, the approximated certified test set accuracy at large radii is small since "truncates" the large radii. As y increases, the robust accuracy improves. It appears that also as trade-off' between accuracy and robustness, but the effect is not as significant as the effect of X.
that
Effect of 3 Similar to Salman al. (2019)'s finding (see its Appendix B), we also observe that using a larger / produces better results. While Salman et al. (2019) pointed out that a large 3 may make training unstable, we find that if we only apply large to the robustness loss, we can maintain training stability and achieve a larger average certified radius as well.
CONCLUSION AND FUTURE WORK
In this work we propose MACER, an attack-free and scalable robust training method via directly maximizing the certified radius of a smoothed classifier. We discuss the desiderata such an algo- rithm would have to satisfy, and provide approach to each of them. According to our extensive experiments, MACER performs better than previous provable ly-defenses and trains faster. Our strong empirical results suggest that adversarial training is not must for robust training, and de- fense based on certification is a promising direction for future research. Moreover, several recent papers (Carmon al.) 2019 Zhai et al. 2019: Stanforth et al.) 2019) suggest that using unlabeled data helps improve adversarially robust generalization. We will also extend MACER to the semi- supervised setting.
10

---

Published as a conference paper at ICLR 2020
ACKNOWLEDGMENTS
We thank Tianle Cai for helpful discussions and suggestions. This work was done when Runtian Zhai was visiting UCLA under the Top-Notch Undergraduate Program of Peking University school of EECS. Chen Dan and Pradeep Ravikumar acknowledge the support of Rakuten Inc., and NSF via IIS1909816. Huan Zhang and Cho-Jui Hsieh acknowledge the support of NSF via IIS1719097 Liwei Wang acknowledges the support of Beijing Academy of Artificial Intelligence.
REFERENCES
Anish Athalye, Nicholas Carlini, and David A. Wagner. Ohfuscated gradients give false sense of security: Circumventing defenses adversarial examples. CoRR, 0bb//1802.00420, 2018. URL
http::/arxivv.rr/ www.///gg/.//...ooo.... 1800200420000000
Battista Biggio, Igino Corona, Davide Maiorca, Blaine Nelson, Nedim Smndić, Pavel Laskov, Gior- gio Giacinto, and Fabio Roli. Evasion attacks against machine learning test time. In Joint European conference on machine learning and knowledge discovery in databases, pp. 387-402. Springer, 2013.
Nicholas Carlini and David A. Wagner. Towards evaluating the robustmess of neural networks. CoRR, hlss1608.04644 2016.
Yair Carmon, Aditi Raghunathan, Ludwig Schmidt, Percy Liang, and John C Duchi. Unlabeled data improves adversarial robustness. arXiv preprint 1905. 2019.
Pin-Yu Chen, Huan Zhang, Yash Sharma, Jinfeng Yi, and Cho-Jui Hsieh. Zoo: Zeroth order opti- mization based black-box attacks to deep neural networks without training substitute models. In Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security, pp. 15-26. ACM, 2017.
Minhao Cheng, Thong Le, Pin-Yu Chen, Jinfeng Yi, Huan Zhang, and Cho-Jui Hsieh. Query- efficient hard-label black-box attack: An optimization approach. 2019.
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 1310-1320, Long Beach, California, USA, 09-15 Jun 2019. PMLR.
Gavin Weiguang Ding, Yash Sharma, Kry Yik Chau Lui, and Ruitong Huang. Mma training: Direct input space margin maximization through adversarial training. In International Confer- Learning Representations, 2020. URL htttp:://opereete ikeryxBtPB
net fortm/irrmmidd
Ruiqi Gao, Tianle Cai, Haochuan Li, Cho-Jui Hsich, Liwei Wang, and Jason Lee. Convergence of adversarial training in overparametrized neural networks. In Advances in Neural Information Processing Systems 32. 2019.
Timon Gehr, Matthew Mirman, Dana Drachsler-Cohen, Petar Tsankov, Swarat Chaudhuri, and Mar- tin Vechev. Ai2: Safety and robustness certification of neural networks with abstract interpreta- tion. In 2018 IEEE Symposium on Security and Privacy (SP), pp. 3-18. IEEE, 2018.
Ian Goodfellow, Jonathon Shlens, and Christian Szegedy, Explaining and harnessing adversarial examples. In International Conference on Learning Representations, 2015. URL http:// arxiv. Dwxiv.org/abs/I4120 6572
Sven Gowal, Krishnamurthy Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Ue- sato, Timothy Mann, and Pushmeet Kohli. On the effectiveness of interval bound propagation for training verifiably robust models. arXiv preprint arXiv:1810.12711 2018.
Ruitong Huang, Bing Xu, Dale Schuurmans, and Csaba Szepesvári. Learning with a strong adver- sary. arXiv preprint arxiv: /51 1.03034, 2015.

---

Published as a conference paper at ICLR 2020
Harini Kannan, Alexey Kurakin, and lan J. Goodfellow. Adversarial logit pairing. CoRR, abs/1803.06373, 2018. URL httthhtpp//att /arxvv.iivv..////i/ org/ htap//bss.//1/ 0637733333333333
Mathias Lecuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified robustness to adversarial examples with differential privacy. arXiv preprint arXiv:1802.0344 2018.
Bai Li, Changyou Chen, Wenlin Wang, and Lawrence Carin. Second-order adversarial attack and certifiable robustness. CoRR, abs/1809.03115 2018. URL. htth::/tp/xxxii// wttpaiiw..oggoooo//ooooooooo
8099 03113
Xuanqing Liu, Minhao Cheng, Huan Zhang, and Cho-Jui Hsieh. 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. arXiv preprint 2017.
Andreas Maurer and Massimiliano Pontil. Empirical Bernstein Bounds and Sample Variance Penal- ization. arXiv e-prints, art. arXiv:0907.3740, Jul 2009.
Matthew Mirman, Timon Gehr, and Martin Vechev. Differentiable abstract interpretation for prov- ably robust neural networks. In International Conference on Machine Learning, pp. 3575-3583, 2018.
Seyed-Mohsen Moosavi-Dezfooli, Alhussein Fawzi, and Pascal Frossard. Deepfool: simple and accurate method to fool deep neural networks. CoRR, abs/1511.04599 2015. URL http: www.aii..orgabb////./. 15519999911
Nicolas Papernot, Patrick McDaniel, Arunesh Sinha, and Michael Wellman. Towards the science of security and privacy in machine learning. arXiv preprint (.0p:://1.08144 2016.
Chongli Qin, James Martens, Sven Gowal, Dilip Krishnan, Alhussein Fawzi, Soham De, Robert Stanforth, Pushmeet Kohli, et al. Adversarial robustness through local linearization. arXiv 2019.
preprint
Jonas Rauber, Wieland Brendel, and Matthias Bethge. Foolbox: A python toolbox to benchmark the robustness of machine learning models. arXiv preprint 1xXiv:1707.041333 2017. URL http:
7/ wawxiv.org/abb////.. 04131
Hadi Salman, Greg Yang, Jerry Li, Pengchuan Zhang, Huan Zhang, Ilya Razenshteyn, and Sébastien Bubeck. Provably robust deep learning via adversarially trained smoothed classifiers. CoRR, htts/1906.04884, 2019.
Ali Shafahi, Mahyar Najibi, Amin Ghiasi, Zheng Xu, John P. Dickerson, Christoph Studer, Larry S. Davis, Gavin Taylor, and Tom Goldstein. Adversarial training for free! CoRR, abs/1904. 2019. HTRL
als 1tt./1194..2....
Gagandeep Singh, Timon Gehr, Matthew Mirman, Markus Püschel, and Martin Vechev. Fast and effective robustness certification. In Advances in Neural Information Processing Systems, pp- 10802-10813, 2018.
Robert Stanforth, Alhussein Fawzi, Pushmeet Kohli, et al. Are labels required for improving adver- sarial robustness? arXiv preprint arXiv:1905. 2019.
Christian Szegedy, Wojciech Zaremba, llya Sutskever, Joan Bruna, Dumitru Erhan, Ian J. Goodfel- low, and Rob Fergus. Intriguing properties of neural networks. CoRR, 1bbs//3...699 2013. URL
http:://arxxi..rrg/bbb////
6199
Shiqi Wang, Yizheng Chen, Ahmed Abdou, and Suman Jana. Mixtrain: Scalable training of formally robust neural networks. arXiv preprint /afl:://11.06666 2018.
12

---

Published as a conference paper at ICLR 2020
Lily Weng, Huan Zhang, Hongge Chen, Zhao Song, Cho-Jui Hsieh, Luca Daniel, Duane Boning, and Inderjit Dhillon. Towards fast computation of certified robustness for ReLU networks. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 5276-5285, Stockholmsmssan, Stockholm Sweden, 10-15 Jul 2018. PMLR.
Eric Wong and Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th In- ternational Conference on Machine Learning, volume 80 Proceedings of Machine Learning Research, pp. 5286-5295, Stockholmsmssan, Stockholm Sweden, 10-15 Jul 2018. PMLR.
Eric Wong. Frank Schmidt. Jan Hendrik Metzen, and J. Zico Kolter. Scaling provable adversarial defenses. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Gamett (eds.), Advances in Neural Information Processing Systems 31, pp. 8400-8409. Curran Asso- ciates, Inc., 2018
Cihang Xie, Jianyu Wang. Zhishuai Zhang, Zhou Ren, and Alan Yuille. Mitigating adversarial effects through randomization. arXiv preprint arXiv:1711.0199) 2017.
Runtian Zhai, Tianle Cai, He, Chen Dan, Kun He, John E. Hoperoft, and Liwei Wang. Adversar- ially robust generalization just requires more unlabeled data. CoRR, abs/1906.00555, 2019. URL
atttp://axiv> wtwpg//bb/199..00e00 00555
Dinghuai Zhang, Tianyuan Zhang, Yiping Lu, Zhanxing Zhu, and Bin Dong. You only propagate once: Accelerating adversarial training via maximal principle. arXiv preprint arXiv: 1rXiv:1905.00877 2019a.
Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric Xing, Laurent El Ghaoui, and Michael Jordan. Theoretically principled trade-off between robustness and accuracy. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference Machine Learning, volume 97 Proceedings of Machine Leurning Reseurch, pp. 7472-7482, Long Beach, California, USA, 09-15 Jun 2019b. PMLR. URL http: httt:://proceeeiingg m p.esss/
2277/hhag199p html
Huan Zhang, Tsui- Weng. Pin- Yu Chen, Cho-Jui Hsieh, 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, Bo Li, Duane Boning, and Cho-Jui Hsieh. Towards sta- ble and efficient training of verifiably robust neural networks. arXiv preprint arXiv:/906.800 06311, 2019c.
13

---

Published as a conference paper at ICLR 2020
A SOFT RANDOMIZED SMOOTHING
In this section we provide theoretical analysis and certification procedures for Soft-RS.
A.1 PROOF OF THEOREM
Our proof is based on the following lemma:
Lemma 1. For any measurable function f X + [0, 1], define f(x) = n + n)) then
-+ (f(x)) is L/p-sipschitz.
This lemma is the generalized version of Lemma 2 in Salman et al. 2019).
Proof of Theorem
Let yy arg max, zy B, 1 (x + r)). For any c V, define 2g as:
2x(x)
+1]l
(18)
Because =8 : ; + [0, 1]. by Lemma we have x x- b-ve is 1/0-LLischiitzz Thus, Vy + y. for any 8 such that ||ól|2 S - (xr
m)]]]
+ (2 5)) + (2]()) - -00)) (z))
-
Φ 1 (x + 8)) v Φ (28 (z))
| - Φ - (z)))
(19)
$ < (x)) + 1 $ (=)(()))))
+ ( (+))
Therefore, Φ- (x, 8 5 (F, (x + 8 n))) Due to the monotonicity of Φ-1 we have En (x 2 En
(z 6++ which implies that go (x 8) y.
A.2 SOFT-RS CERTIFICATION PROCEDURE
Let Σл = E, + +)] and 2B maxy my Eyl-y (x: 7)]. If there exist 24, 2B [0, 1 such that P(2A 2 2A A 2B S BB 2 - a, then with probability at least 1 - a, CR((go: x, y) 2
(ZA) (2-)) Meanwhile, 2B S 1 - 2A, so we can take z = EA. and
P(CR(ğo: x, v) σ AA
-
(20)
It reduces to find a confidence lower bound of zA. Here we provide two bounds:
Hoeffding Bound
The random variable z (z + 11) has mean 24, and ...... , are its k observa- tions. Because 2i E [0, 1] for any j = -,... k. we can use Hoeffding's inequality to obtain lower confidence bound:
Lemma 2. (Hoeffding's 's Inequality) Let X1,.., X₁ be independent random variables bounded by the interval [0, 1). Ler X Ei=1 Xy. then for any t 2 0
P(X 2 t) < e 2k1
(21)
Denote Et = # 2/. By Hoeffding's 's inequality we have
log
P(:" ZA
S
(22)
2k
Hence, a a confidence lower bound ΣA of ZA is
log
2A4 2
(23)
14

---

Published as a conference paper at ICLR 2020
Empirical Bernstein Bound Maurer & Pontil 2009) provides us with tighter bound:
Theorem 3. (Theorem 4 in Maurey & Pontil ability at least -
(2009) Under the conditions of Lemma with prob-
252 log X- 1
7 1log2 +
(24)
k
3(k - 1)
where 52 the sample variance of X1. Xk. i.e.
(Σ)= x,)²
8 Σド= X²
k
(25)
k-1
Consequently, confidence lower bound AA of ZA is
25 log
7 a
(26)
3(k
The full certification procedure with the above two bounds is described in Algorithm 2
Algorithm 2 Soft randomized smoothing certification
# Certify the robustness of g around an input x with Hoeffding bound
2: function CERTIFYHOEFFDINGE o² x. noo ()) no, [1.
3: 20 + SAMPLEUNDERNNOSH(
4: ČA arg max, ~
5: ΣA f SAMPLEUNDERNOISS(... 11,
6:
+ A
log
2n
7: if then return prediction éΛ and radius o$ (2A)
8: else return ABSTAIN
9:
end function
10: # Certify with empirical Bernstein bound
function CERTIFY a², F. ng. n. ())
12:
20 < SAMPLEUNDERNOOSE((
no, o² [1, [1,
ČA < arg max, 40
14:
A < SAMPLEUNDER NOISE
0²)
15:
2A + A[1,čA]/n, Sa
A|2,2 A
n-1
16:
AA + AA -
2. log(2/a)
7log(2/a]
3(n-l)
17:
if &A > then return prediction čд and radius o (2A)
18:
else return ABSTAIN
19:
end function
20:
# Helper function: draw num samples from =(x + 11) and return the 1st and nnd sample moment function AMMPLEUDDERNOISESS.. x, num, g²)
21:
22:
Initialize 2 x K matrix A +- (0, ... ,, 0,......
for j to num do
24:
Sample noise 77 _N(00 021)
Compute: 2j = 2(x 71))
26:
Increment: A[I + A[1, :] zj. A[2,:] A[2,:] +
27:
end for
return
29:
end function
A.3
COMPARING SOFT-RS WITH HARD-RS
We use Soft-RS during training and use Hard-RS during certification. In this section, we empirically compare these certification methods. We certify the nine models in Table 4 For each model,
15

---

Published as a conference paper at ICLR 2020
Clopper-Pearson bound and for Soft-RS, we use the empirical Bernstein bound with different choices of B. The results are displayed in Figure 4 The results show that Hard-RS consistently gives larger lower bound of robust radius than Soft-RS. We also observe that there a gap between Soft-RS and Hard-RS when B + oc, which implies that the empirical Bernstein bound, though tighter than the Hoeffding bound, is still looser than the Clopper-Pearson bound.
certify with both Hard-RS and Soft-RS. For Hard-RS,
B PROOF OF PROPOSITION
Proof of Proposition / We only need to consider the case when ob (p1(p - Φ -- (p2) S 7 since the derivative is when क (p1)) T (p2) > y. Obviously, P2 0.5 and thus + (p2) I So
Φ- (p1( 7.
Define p" (0, 1) such that Φ- (--(p") 7. Since $- (p) is a strictly increasing function of p. p" (p2). Since is the - (p2) ]{ 7) = -p1(p1) --1(p2)
unique, and p1 S p". min minn((0111)) (pi) (pi)
largest value and P1 + P2 + +... PK in any closed interval of (0, 1). the derivative $ -p1) - Φ --1((p) with respect P1 bounded.
we have K S p1 S Since { [I) is continuous
Similarly, P2 is the largest among P2...PK and (K - 1)p2 2 P = 1 - P1 2 1 -p". Thus
1 pp'
P2 K- and the derivative of क h- T (p2( with respect p2 is bounded. L
C SUPPLEMENTARY MATERIAL FOR EXPERIMENTS
C.I COMPARED MODELS
In this section we list all compared models in the main body of this paper. Cifar-10 10 models are listed in Table and ImageNet models are listed in Table 5
Table 4: Models for comparison Cifar-10.
Model
Description
Cohen-
0.25,0.50,,
Cohen et al. (019))s models
Salman-0.25
8-sample 10-step SmoothAdv with c = 1.00
0.25
MACER-0.25
MACER with à: 16, À 12.0, 8 16.0 and 8.0
Salman-0.50
2-sample 10-step SmoothAdy with e = 2.00
0.50
MACER-0.50
MACER with 16, 4.0, 16.0 and y 8.0
Salman-1.00
2-sample 10-step SmoothAdy with 2.00
1.00
MACER-1.00
MACER with k = 16, dynamic 5
B 16.0 and 7 = 8.0
Table 5: Models for comparison on ImageNet.
Model
Description
Cohen-
(0.25,0.50, 1.00]
Cohen et al. 2019 's models 1-sample 2-step SmoothAdv with 1.0
Salman-0.22
0.25
MACER-0.22
MACER with = 2, = 6.0, 8 = 16.0 and 7 = 8.0
Salman-O.. 00.50
1-sample 1-step SmoothAdy with e 1.0
0.50
MACER-0.50
MACER with k 2, A = 3.0, 8 = 16.0 and
8.0
Salman- 1.00
I-sample 1-step SmoothAdy with e = 2.0
1.00
MACER-I.00
MACER with A 2, X 3.0, 8 16.0 and > 8.0
C.2 RESULTS ON MNIST AND SVHN
Here we present experimental results on MNIST and SVHN, For comparison we also report the results produced by Cohen et al. (219)'s 's method.
We first train with À 0.0, and then change to À 12.0 after learning rate decay.
16

---

Published as a conference paper at ICLR 2020
-0
Certifeed accuracy
0.8
0
0.8
Certified accuracy
0.8
4.0
16.0
16.0
16.0
0.8
0.6
0.6
0.4
Certifee
0.4
0.4
0.2
0.2
0.2
0.5
0.5
1.5
radius
radius
1 radius
(a) Cohen-0.25
(b) Cohen-0.50
(c) Cohen-1.00
Cartified acouradt
4.0
Certified aecurady
4.0
Cartified apcuracy
0.8
4.0
Hard-Rt
....: Hard-RS
.... Hard-R8
0.4
0.4
0.2
0.5
0.5
1.5
2
3
radius
cadios
(d) Salman-0.25
(c) Salman-0,50
( Salman- 1.00
3
1.0
+3
1.0
-3 1.0
Cerliiid accuracy SP
0.8
Certified acouragy
0.8
Certified acourscy
0.8
16.0
16.0
16.0
0.6
Hard-RS
0.6
Hard-RS
0.6
Hard-RS
0.4
0.4
0.4
0.2
1.5
1g radiua
1 redlus
1g radius
(g) MACER-0.25
(h) MACER-0.50
ii) MACER-1.00
Figure 4: Comparing Soft-RS with Hard-RS on Cifar-10. The three columns correspond to 0. 0.25, 0.50, 1.00 respectively.
17

---

Published as a conference paper at ICLR 2020
C.2.1 MNIST
The results reported in T
For all 0, we use k 16,
16.0, 7
8.0 and 16.0.
Table Approximated certified test accuracy and ACR on MNIST: Each column is an lg radius.
Method
0.00
0.25
0.50
0.75
1.00
1.25
1.50
1.75
2.00
2.25
ACR
Cohen
0.99
0.97
0.94
0.89
0
0
0
0
0.887
0.25
MACER
0.99
0.99
0.97
0.95
0
0.918
Cohen
0.99
0.97
0.94
0.91
0.84
0.75
0.57
0.33
0
1.453
0.50
MACER
0.99
0.98
0.96
0.94
0.90
0.83
0.73
0.50
0
1.583
Cohen MACER
0.95
0.92
0.87
0.81
0.72
0.61
0.50
0.34
0.20
0.10
1.417
1.00
0.89
0.85
0.79
0.75
0.69
0.61
0.54
0.45
0.36
0.28
1.520
C.2.2 SVHN
The results are reported in Table
7
We use
16,
12.0,
8.0 and 16.0.
Table 7: Approximated certified test accuracy and ACR on SVHN: Each column an l2 radius.
Method
0.00
0.25
0.50
0.75
1.00
1.25
1.50
1.75
2.00
2.25
ACR
Cohen
0.90
0.70
0.44
0.26
0
0
0)
0
0.469
0.25
MACER
0.86
0.72
0.56
0.39
0)
0)
0
0
0.540
Cohen
0.67
0.48
0.37
0.24
0.14
0.08
0.06
0.03
0
0.434
0.50
MACER
0.61
0.53
0.44
0.35
0.24
0.15
0.09
0.04
0
0
0.538
C.3 MACER TRAINING FOR 150 EPOCHS
In T we report the performance and training time of MACER on Cifar- 10 when it only run for 150 epochs, and compare with SmoothAdv (Salman et al. 2019) and MACER (440 epochs). The learning rate is decayed by 0.1 at epochs and 120. All other hyperparameters are kept the same as in Table 4
Table 8: Approximated certified test accuracy and ACR on Cifar- 10: Each column an la radius.
Method
0.00
0.25
0.50
0.75
1.00
1,25
1,50
1.75
ACR
Epochs
Total hrs
SmoothAdy
0.74
0.67
0.47
0.538
150
82.92
0.25
MACER
0.76
0.67
0.57
0.42
0
0
0
0.531
150
21.00
MACER
0.81
0.71
0,59
0.43
0
0
0
0.556
440
61.60
AmoothAdv
0.50
0.46
0.44
0.40
0.38
0.33
0.29
0.23
0.709
150
82,92
0.50
MACER
0.62
0.57
0.50
0.44
0.38
0.29
0.21
0.13
0.712
150
21.00
MACER
0.66
0.60
0.53
0.46
0.38
0.29
0.19
0.12
0.726
440
61 60
C.4 EFFECT OF HYPERPARAMETERS
All experiments Cifar- 10 with 0.25 0.50.
See Table for detailed experimental
settings. Results are reported in Tables 10 [3
18

---

Published as a conference paper at ICLR 2020
Table 9: Experimental setting for examining the effect of hyperparameters.
Experiment
k
Effect of &
1/24/8716
12.0
8.0
16.0
Effect of A
16
0.0/1.0/2.0/4 wtt.0/////88811.//////
8.0
16.0
Efflect 7
16
12.0
16.0
Effect
8.0
1.0/2.0/4.0/8 16.00.0002200
Table 10: Effect of k: Approximated certified test accuracy and ACR on Cifar-10.
k
0.00
0.25
0.50
0.75
1.00
1.25
1.50
1.75
2.00
2.25
ACR
0.77
0.65
0,45
0.27
0
0
0
0,448
2
0.81
0.69
0.53
0.38
0
0
0
0.519
0.25
4
0.79
0.69
0.55
0.38
0
0
0
0.517
8
0.78
0.69
0.57
0.41
0
0
0.538
16
0.81
0.71
0.59
0.43
0
0
0
0
0.556
0.36
0.31
0.26
0.19
0.12
0.09
0.05
0.02
0.306
2
0.60
0.53
0.47
0.37
0.28
0.19
0.13
0.08
0
0.589
0.50
4
0.60
0.55
0.50
0.42
0.34
0.26
0.18
0.11
0
0.665
8
0.61
0.56
0.50
0.43
0.37
0.28
0.22
0.14
0
0.699
16
0.60
0.56
0.50
0.46
0.38
0.29
0.23
0.14
0
0.712
Table 11: Effect of X: Approximated certified test accuracy and ACR on Cifar- 10.
0.00
0.25
0.50
0.75
1.00
1.25
1,50
1.75
2.00
2.25
ACR
0.0
0.82
0.67
0.51
0.32
0
0
0
0.488
1.0
0.81
0.68
0.54
0.35
0
0
0
0
0.516
2.0
0.81
0.71
0.54
0.36
0
0
0
0.523
0.25
4.0
0.82
0.71
0.56
0.41
0
0
0
0
0
0.540
8.0
0.80
0.70
0.59
0.43
0
0
0
0.550
16.0
0.78
0.69
0.57
0.46
0
0
0
0.550
0.0
0.69
0.56
0.44
0.31
0.21
0.13
0.06
0.02
0 0.515
1.0
0.68
0.59
0.52
0.43
0.33
0.23
0.15
0.07
0 0.662
2.0
0.70
0.61
0.53
0.43
0.36
0.27
0.18
0.09
0 0.709
0.50
4.0
0.66
0.60
0.53
0.46
0.37
0.29
0.19
0.12
0
0.726
8.0
0.62
0.56
0.50
0.45
0.37
0.29
0.21
0.13
0
0.700
16.0
0.60
0.56
0.51
0.45
0.36
0.30
0.21
0.14
0.711
19

---

Published as a conference paper at ICLR 2020
Table 12: Effect of y: Approximated certified test accuracy and ACR on Cifar- 10.
0.00
0.25
0.50
0.75
1.00
1.25
1.50
1.75
2.00
2.25
ACR
2.0
0.82
0.67
0.47
0.26
0
0
0.455
4.0
0.83
0.70
0.53
0.35
0
0
0
0
0.521
6.0
0.80
0.70
0.57
0.40
0
0
0
0.539
8.0
0.81
0.71
0.59
0.43
0
0
0
0
0
0
0.556
0.25
10.0
0.78
0.69
0.57
0.44
0
0
0
0.543
12.0
0.76
0.69
0.58
0.42
0
0
0
0
0.534
14.0
0.76
0.68
0.55
0.44
0
0
0
0.536
16.0
0.75
0.67
0.56
0.44
0
0
0
0.534
2.0
0.70
0.61
0.49
0.33
0.23
0.13
0.06
0.03
0 0.549
4.0
0.68
0.60
0.53
0.44
0.34
0.25
0.15
0.06
0.676
6.0
0.65
0.58
0.51
0.43
0.35
0.28
0.20
0.13
0 0.706
8.0
0.60
0.56
0.50
0.46
0.38
0.29
0.23
0.14
0
0.712
0.50
10.0
0.58
0.54
0.49
0.44
0.37
0.31
0.24
0.15
0
0.707
12.0
0.56
0.51
0.48
0.43
0.38
0.34
0.26
0.16
0
0.712
14.0
0.51
0.48
0.44
0.38
0.33
0.28
0.22
0.16
0
0.634
16.0
0.57
0.54
0.47
0.41
0.34
0.30
0.24
0.17
0
0.695
Table 13: Effect of 8: Approximated certified test accuracy and ACR on Cifar- 10.
0.00
0.25
0.50
0.75
1.00
1.25
1.50
1.75
2.00
2.25
ACR
1.0
0.79
0.67
0.54
0.37
0
0
0
0
0.513
2.0
0.81
0.69
0.56
0.41
0
0
0
0.534
4.0
0.79
0.70
0.59
0.43
0
0
0
0
0
0
0.549
0.25
8.0
0.79
0.71
0.57
0.43
0
0
0
0,541
16.0
0.81
0.71
0.59
0.43
0
0
0
0
0.556
32.0
0.79
0.70
0.58
0.43
0
0
0
0.549
64.0
0.74
0.65
0.54
0.42
0
0
0
0.517
1.0
0.67
0.59
0.52
0.43
0.35
0.26
0.19
0.10
0
0.696
2.0
0.63
0.57
0.52
0.45
0.37
0.31
0.22
0.13
0
0.719
4.0
0.60
0.55
0.50
0.45
0.36
0.30
0.22
0.14
0
0.703
0.50
8.0
0.60
0.56
0.52
0.43
0.38
0.30
0.24
0.14
0
0.713
16.0
0.60
0.56
0.50
0.46
0.38
0.29
0.23
0.14
0
0.712
32.0
0.59
0.55
0.49
0.44
0.36
0.30
0.23
0.14
0
0.705
64.0
0.45
0.41
0.38
0.35
0.32
0.26
0.21
0.16
0
0.579
20


Reviews:
[{"review_id": "ryg6D-wptS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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 a new approach to training models robust to perturbations (or 'attacks') within an l_2 radius, by maximizing a surrogate---a soft randomized smoothing loss---for the *certified radius* (a lower bound for the l_2 attack radius) of the classifier.  This approach has the advantage of not needing to explicitly train against specific attacks, and is thus much faster and easier to optimize.  The authors provide certain theoretical guarantees and also demonstrate strong empirical results relative to two baseline approaches.\n\nThis work builds on prior work where the goal of training a classifier that is robust to attacks is phrased as maximizing the *robust radius*, the largest l_2 ball within which a data point x can be perturbed without changing the (correct) classifications of trained classifier.  Since directly maximizing this robust radius is intractable, prior work seeks to derive a lower bound which the authors term the *certified radius*.  In order to directly maximize this, the authors use randomized smoothing- in which a randomly Gaussian-smoothed version of classifier f is used to make predictions- and then motivate and develop a \"soft randomized smoothing\" lower bound surrogate of the certified radius to maximize, which is differentiable and provably numerically stable.\n\nOverall, this paper is well explicated, starting with clearly written background on basic concepts and prior work, stating clear desiderata that the surrogate loss being developed should satisfy, and then providing theoretical proofs as to this.  The experiments are then thorough including core and ablation experiments to showcase the method.\n\nOne downside is that the paper does make fairly aggressive claims (e.g. \"performs better than all existing provable l_2-defenses\"), but then only compares to two prior / baseline approaches in the experiments.  Given the density of the field recently, this seems a bit sparse (although this reviewer is not an expert in this area)?", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "rJeCqcNIKr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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 paper presents a method for training a certified robust neural network, based on the certification method of cohen et al.\n\nI think this paper is quiet borderline, as it is a natural extension of cohen et al, but is incremental. The authors use a hinge surrogate loss with smoothing to make the certification differentiable and optimize it, getting results that are on par with Salmans et al.\n\nDetailed remarks:\n - From table 3 it seems like MACER was trained for more then the other models, up to almost x3 times more on cifar. This makes the comparison unfair and puts the results into question.\n- It was nice that the authors gave a theoretical guarantee for the soft-RS, but it is not clear if that is needed. You can train with soft-RS and apply the hard-RS at test time which has the standard guarantees\n- Fig. 3 needs labels on x&y axis\n-  The ablation study isn't really an ablation study, it is more testing the sensitivity of various parameters (which is good in itself). However the gamma results and claims are hard to see from the plot.\n\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "SkeTVpZxcH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "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 improves the robustness of smoothed classifiers by maximizing the certified radius, which is more efficient than adversarially train the smoothed classifier and achieves higher average robust radius and better certified robustness when the radius is not much larger than the training sigma. It proposes a novel objective which is derived by decomposing the 0/1 certified loss into the sum of 0/1 classification error and 0/1 robustness error. Three conditions are identified to make the optimization doable. Two surrogate losses (CE and hinge loss on the certified radius) for the two 0/1 errors are proposed as upper bounds of the 0/1 loss. Certified radius is derived as a function of the logits of Soft-RS to make the hinge loss differentiable. Numerical stability of the proposed objective is also analyzed by showing its gradient is bounded.\n\nIn general, the paper is well-written and the proposed objective is novel to my knowledge. I tend to accept the paper. Still, I am not sure about how much MACER improves upon the baselines, and would like to ask some questions.\n\n1. Cross entropy is used as a surrogate for the 0/1 classification error. This is true for all cases (including all experiments in this paper) except for binary classification, where the cross entropy is less than 1 when the score on the correct class is around 0.5. It is not important but would be better if you could mention this point.\n\n2. Have you ever tried using a tighter upper bound for the 0/1 classification error, e.g., using cross entropy loss only for the wrongly classified samples? How does it affect the results?\n\n3. Despite showing better results, MACER seems to be using much more epochs than the two baselines (but the total hrs is smaller than (Salman et al. 2019)). Also, MACER is using a much larger k than (Cohen et al., 2019). From Figure 3 (a) we can see a larger k improves the result a lot, and from Figure 3 (b) it seems that setting lambda to a non-zero value only improves the accuracy when the radius is large. For fair comparisons, could the authors give the ACR with different values of lambda while keeping other hyper parameters unchanged? Is Salman's method still not as good when using the same number of epochs?\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The submission proposes a robustness certification technique for smoothed classifiers for a given l_2 attack radius.

Strengths:
-The majority opinion is that this work is a non-trivial extension of prior work to provide radius certification.
-The work is more efficient that strong recent baselines and provides better performance.
-It successfully achieves this while avoiding adversarial training, which is another novel aspect.

Weaknesses:
-There were some initial concerns about missing experiments and unfair comparisons but these were sufficiently addressed in the discussion.

AC shares the majority opinion and recommends acceptance.
Decision: Accept (Poster)