Efficient Training of Robust and Verifiable Neural Networks
Authors: Akhilan Boopathy
Lily Weng
Sijia Liu
Pin-Yu Chen
Luca Daniel
Venue:  (2020)

Abstract: Recent works have developed several methods of defending neural networks against adversarial attacks with certified guarantees. We propose that many common certified defenses can be viewed under a unified framework of regularization. This unified framework provides a technique for comparing different certified defenses with respect to robust generalization. In addition, we develop a new regularizer that is both more efficient than existing certified defenses and can be used to train networks with higher certified accuracy. Our regularizer also extends to an L0 threat model and ensemble models. Through experiments on MNIST, CIFAR-10 and GTSRB, we demonstrate improvements in training speed and certified accuracy compared to state-of-the-art certified defenses.

Under review as a conference paper at ICLR 2020
DOUBLEMARGIN: EFFICIENT TRAINING OF ROBUST AND VERIFIABLE NEURAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
Recent works have developed several methods of defending neural networks against adversarial attacks with certified guarantees. We propose that many common certified defenses can be viewed under unified framework of regularization. This unified framework provides a technique for comparing different certified defenses with respect to robust generalization. that is both more efficient than existing certified defenses and can be used to train networks with higher certified accuracy. Our regularizer also extends to an to threat model and ensemble models. Through experiments on MNIST, CIFAR-IB 10 and GTSRB, we demonstrate improvements in training speed and certified accuracy compared to state-of-the-art certified defenses.
addition, we develop a new regularizer
INTRODUCTION
Although deep neural networks (DNNs) have achieved tremendous success in various applications, it becomes widely-known that they are vulnerable to adversarial examples (also known as adversarial attacks), namely, crafted examples with iippreeiippereptbbll perturbations cause misclassification (Goodfellow et al.] 2015 Szegedy et al. 2013). Many attack generation methods have been proposed in order to find the possible minimum adversarial perturbation, commonly evaluated by its L, norm (Papernot et al. 2016; Carlini & Wagner 2017 Atthalye & Sutskever 2017 Su al. 2019 Xu et al. 2018 Chen al. (018)). Meanwhile, various defense methods were proposed to enhance the robustness of DNNs against adversarial attacks. However, many of them are built on heuristic strategies. which are thus casily bypassed by stronger adversaries (Athalye et al. 2018). The Madry et al. (2018) proposed a stronger defense method, adversarial training, which minimizes the worst-case training loss under adversarial perturbations. However, is restricted a specific type of adversarial perturbations and not generalized to other types of perturbations (Tramer & Boneh 2019)
for perp E {0. 1, 2, oc)
Motivated by the limitation of heuristic defense, another line of research (known as verified/certified robustness) aims to provide provable robust guarantees of DNNs against an input with arbilrary
perturbation within a certain Ep ball region (Katz. et al. [017 Cheng al.] [ Carlini et al. [017]]
Kolter& & Wong 2018 1. Raghunathan et al., 2018] Weng et al., 2018 Zhang et [ Boopathy al. 2019 Dvijotha al.] [2018]] Wong et al. 2018 Xiao et al. 2019 Gowal et al. [0088] Mirman
et al. 2018 Dvijotham et al.) (018a). The recent progress on verification spans from the exact verification method (Katz et al. 2017 Cheng et al. 2017 Carlini et al. 2017) to the approximate (relaxed) verification method (Kolter & Wong 2018 Raghunathan et al. [0018] Weng et al., 2018 Zhang et al.) 2018 Boopathy al. Dvijotthm et al.] 20188] Wong et al.) 2018). Here the Tormer uses expensive computation methods, e.g., mixed-integer programming (MIP), to find the exact robustness bound, and the latter considers a relaxed verification problem by convexifying the adversarial polytope but significantly improves the computation efficiency compared to the exact method. Besides resorting to approximate verification method, the recent work Xiao et al. (2019) proposed the principle of co-design between training and verification, and showed that the exact verification method can accelerated by imposing weight sparsity and activation stability (so-called ReLU stability) trainable network models. On the other hand, it was shown in Kolter & Wong (2018); Raghunathan et al. (2018); Gowal et al. (2018); Mirman et al. (2018) Dvijotham et al. (2018a) that by incorporating the relaxed but computationally efficient verification methods into the training process, the learnt model yields strengthened robustness with certificate. Following this line of research, in this work:

---

Under review as a conference paper at ICLR 2020
We develop unified framework of certified defense and propose that many common certified defenses can be incorporated as different types of regularization. We theoretically analyze general regularizations and provide guidelines on how to select regularization.
We propose an efficient regularizer that better quantifies adversarial sensitivity during the training process to yield more certifiable models. Through experiments on six different architectures, we demonstrate our method's computational efficiency and higher certified accuracies on large perturbations compared to all current oftte-o-thhe-nn certification based training methods. In particular, we demonstrate up to a 55% increase in certified accuracy at e = 0.2 on MNIST, up to 20.5% % increase at 2/255 on CIFAR, and up 24% increase = 8/255 GTSRB. In addition, on all architectures and datasets we achieve faster training than any other certification based training methods.
We extend our regularizer to an Ey threat model and model ensembles. We demonstrate empirically that regularizer achieves high certified accuracy on this threat model. We also empirically show that model ensembling of models trained with our regularizer achieve higher certified accuracies.
2
BACKGROUND AND RELATED WORK
2.1 VERIFICATIONS
Assuming norm-bounded threat model, finding the minimum adversarial distortion exactly is an NP- complete problem, making it computationally infeasible (Katz et al. 2017). Fortunately, finding lower bounds on the minimum adversarial distortion is computationally tractable. Several techniques find these lower bounds only as a function of model weights (Szegedy et al. 2013 Peck et al. 2017; Hein & Andriushchenko 2017 Raghunathan et al.) 2018), but these methods typically provide very loose bounds for neural networks with more than 2 layers. Using an input- input-specific certification method, it is possible to find non-trivial bounds for fully connected ReL.U networks (Kolter & Wong 2018 Weng et al. 2018: Wang et al.) 2018), as well as networks with general activation functions (Zhang ct al. 2018) and architectures (Singh et al., 2018). An "any-time" certifier has also been developed that allows for trade-off between certification time and bound quality (Dvijotham et al. (018b).
2.2 CERTIFIED DEFENSES
Recent works have also developed methods of defending against adversarial attacks. One line of work uses adversarial training with adversarial attacks and empirically demonstrates high resistance to attacks (Madry et al. 2018 Sinha al.) 2018). However, adversarial training is not targeted towards verification certification methods, and we therefore do not consider it certified defense. One step towards certified defenses is natural regularization such as sparsity- induucin weight magnitude penalization. This method combined with adversarial training yields highly verifiable models (Xiao) et al. 2019). Using an additional ReLU stability regularizer to enhance ease-of-verification allows for even more verifiable models.
Other defenses specifically target certifiers or use certification methods as part of the training procedure. We note that these "certified" defenses not truly certified since they cannot ensure robustness to unseen points without using a certifier on these points. These defenses instead produce models that are empirically more certifiable on unseen test points. Using convex outer bounds to bound the adversarial loss function has been shown to be effective at producing certifiable models, although training is relatively slow (Kolter & Wong 2018: Wong et al. (2018). Using interval bounds propagation (IBP) to bound the adversarial loss is much cheaper to train (Gowal et al., (018)) and has surprisingly become the state-of-the-arr certifiably robust training method (Gowal et al. 2018)) Salman et al. 2019) despite IBP performing much more poorly than the convex outer bounds (Kolter & Wong 2018; Wong et al. 2018 in certifications. In this paper, we unify certified defenses under a unified framework of regularization. We also develop efficient certified defense that has similar computation overhead as IBP-based defense (Gowal et al. 2018) while yielding better performance than existing methods.
2

---

Under review as a conference paper at ICLR 2020
2.3 CERTIFICATION METHODS
Threat model In this paper, we will use the notation of fully-connected neural networks for exposition, but our method works for general convolutional neural networks including residual networks. Appendix B Table 3 includes descriptions of the main notations used in this paper. Consider an n layer neural network f f(x) with input x where the first layer of the network z is set to x. Given weights W biases b' and an activation function o, for i = O...., 1, subsequent layers are defined as:
= - (2)) bb+
(1)
with ((x) z". With this expression, the first layer of the network is defined by using the identity activation at the first layer. We assume the following threat model: a nominal input Xnom is perturbed by perturbation
produce a perturbed input x Xnom + 6, where ||0|pp pp S and -1 represents an lp norm. Suppose the correct classification is given by c. Then the minimum distortion e* is the minimal c e R satisfying: max 2 z 0.
Interval Bounds Propagation There exist several methods to efficiently find certified lower bounds on the minimum distortion necessary for misclassification. One such method is interval bounds propagation (IBP) (Gowal et al. (2018, Gehr al. 2018) which bounds each layer in a network with fixed upper and lower bound. These bounds are then propagated at each layer of the network using the previous layer's bounds. Specifically, given layer-wiss wise bounds where 1s S z I u², the next layer's bounds are found as: u o
(2) where W+ and W_ denote the positive and negative components of W respectively with other entries being zeros otherwise, Lower bounds are found similarly. Intuitively, IBP finds a box bounding each layer, which can result in very loose bounds for general network as demonstrated in (Kolter & Wong 2018 Gehr et al. 2018).
ou') + w ((')) + + 1+1
Linear Bounding Framework Certified bounds can also be found using a linear bounding frame- work as first proposed in Fast-Lin (Weng et al.) 2018) and later in the Neurify (Wang et al.) 2018) and DeepZ (Singh al. 2018) frameworks. This approach typically finds tighter bounds on minimum distortion than IBP. This framework bounds each activation layer (z") as follows: a xt + B I <z') S at @ x' + Py. where a² represents the slopes of linear bounds the activation and B1,B8 representing intercepts of linear bounds the activation. When is ReLU activation, Fast-Lin sets the coefficients to be:
zi.
Bh,5 -0, Big
2n.s 2/.
if the neuron j is uncertain, meaning zi, < 0, 2 > 0 and zi, Szz S 2 z When both bounds are positive or negative, the bound on the activation exactly the linear component on the corresponding side (i.e. when z > 0 for example, a1=1,, BL, = Big 0). Using these layer-wise bounds, Fast-Lin finds pair of linear bounds the network: by < f(x) < Ax by. Then Fast-Lin bounds the network output over all possible adversarial distortion measured by e-lp ball by:
Axnom + b - ||:a 2 S fxx) S Axnom + by [|:a]
where || Ills denotes row-wise 9 norm, dual to the norm p of the assumed attack threat model. is the assumed attack norm size. Intuitively, Fast-Lin finds linear upper and lower bounds on the entire network analyze the output layer. Because Fast-Lin finds linear bounds on the network as an intermediate step to finding output bounds Z,, 2/. the bounds are tighter than the corresponding IBP bounds u, 1. Fast-Lin is equivalent to using convex outer bounds bound the set of possible values at each layer of the network. Fast-Lin has been extended to general activation functions and asymmetric upper and lower bounds with different values of a² in CROWN (Zhang et 2018 and has been extended to general network architectures in CNN-Cert (Boopathy et al. 2019
3 UNIFIED FRAMEWORK OF CERTIFIED DEFENSE
We propose unified framework of certified defense under which many common certified defenses can be viewed regularizations of a particular form. We first our framework to provide analysis of
3

---

Under review as a conference paper at ICLR 2020
Training Method
R(0)
Training cost
Regularization
Σ. Ie |
6 Regularization
E. lon.s or II [W]] 1omes
x1
ReLU Stability Loss (iao al.
2019
B|- Σ, lanh(1 u о []]
Interval Bounds Propagation Gowal al.
2018
(1, + (_ L[x")] E [jmaas] si of + 8), f(Xnom))
TRADES Zhung al
2019
10 (empirically)
Convex Outer Bounds Kolter & Wong
2018
( + (-())) L(x")]
100 (empirically)
MMR (Croce al.
2019
Blmar[0, To mar B
10000 (empirically)
Double Margin
+ v") L- (2"
L(2"))
x3
Table I: u' and I' are layer-wise bounds found using interval bounds propagation, and u and I. are layer-wise bounds using convex outer bounds. @ denotes element-wise multiplication. || Ilop.oc denote the fo induced operator norm. g is classifictton-caliiratee loss function. dp and dp are quantities relating to lower bounds on the minimum adversarial distortion. Expectations are taken over training data. The training cost compared to the standard training.
general certified defenses. Under this framework, then propose our regularizer which outperforms other current certified defense methods as suggested by the experiments. Because IBP has been shown to be the current state-of-the-art in efficiently training certifiable models, consider it as our main baseline and highlight our method's advantages. Finally, we discuss extensions of our regularization.
3.1 ANALYSIS OF REGULARIZERS
A Unified Regularizer Framework for Certified Defense Many different training methods can often be formulated as different regularizations added to standard loss function. Given model param- eters 0, loss function ((0) and regularizer R(0), the total regularized loss with regularization parameter À is given by:
[( XR(())
Note that we denote model's parameters in general as 0, and we use calligraphic symbols to denote functions general parameters and standard symbols to denote functions varying at different data points. Standard regularizations chosen to enhance generalization include weight-based regularization where the regularizer is chosen to be Σ, |Wille with being some matrix norm. In fact, many certification- based robust training methods also be viewed as different regularizations R(0) as seen in Table [ Therefore, both standard regularizations and many robust training methods can be viewed under unified framework. Training methods be designed by selecting particular regularizer according to the designer's objective.
Regularizer Construction Certified defenses such as IBP construct regularizer by using bounds on the last layer of the network u" and l" to find an upper bound on the adversarial loss. Suppose standard loss function L(0) of model parameters is defined as a function of the last layer of the network z": L(0) = [2),2")),, where the expectation is taken over the training set. For many loss functions L. including softmax cross-entropy loss and squared loss, is possible to decompose the loss into increasing and decreasing component:
L(z") = L+(2)) (z"),
(3)
where T4 (z") increases feament-wise with x and T._ (z²) decreases element-wise with z". For example in the case of softmax cross- cross-entropy loss:
L(z") = -y
T log (e" /1T
log 1
-TT²"
where ex is element- exponential function and are one-hot encoded labels, the first term can be mapped to (z") while the second corresponds to L=(x)) in 3}. IBP then constructs the following regularizer: R(0)= = ELL+ (u") L- (I*) L(ziiom))l where u and 1 are defined by (2) and 2 the value of layer z" with unperturbed imput Xnom- When this regularizer is added to the standard
loss function L(0) computed with unperturbed input Xnom. the resulting quantity L(Ø) + R(0) is an
upper bound on the adversarial loss since: L(z)) +L (L+ +L")+__ (Ir) ((r)-L(("))) [(z))))) )) 2 L(z") " where
z" is function of perturbed input x, obtained by monotonicity of T.4 and I._ and 1 z < u².
4

---

Under review as a conference paper at ICLR 2020
Note that the adversarial loss L(z") is unknown, but the upper bound constructed here depends only on the IBP bounds u" and which are known. Typically, the model is trained with objective [(0) + XR(#) with À < instead of X 1 in order to ensure stable training.
Connecting regularization to robustness and generalization A regularized loss function often can be seen as an upper bound on particular robustness or generalization objective. As shown previously, adding robust training regularizer such as IBP is equivalent to minimizing an upper bound on the adversarial loss: m Σ, maxx: xx [x((x)) S C()) XR(0), for sufficiently large À where there are m points x; in the training set. Similarly l and Eg regularization can be seen as minimizing a probabilistic upper bound on the test set loss: Ctest (0) < C()) + AR(O). This is
because many generalization error bounds (Bartlett & Mendelson 2002
Neyshabur et al. 2015 are
statements of the following form: with high probabillty,
Crest (0) S L(0) III, ||
mm
where (te the test error, ||- is either a Frobenius or loo operator norm, m represents the number of training set points, and K and C' are constants depending on the network architecture. It possible analyze the effect of general regularizations under the assumption that À close to zero. This corresponds to close to zero for robustness-basse regularizers m very large for generalization-buie based regularizers such as l lg weight regularization that can be interpreted as minimizing generalization bound of the form in Equation 4
Proposition 1. Given a classifier with parameters and loss C(0) with a local minimum 0, then for À near 0, the local minimum of L(0) + XR(O) is approximately:
i (H(((())-VRR()))
(5)
where H(C(0)) is the Hessian of the loss at the original local minimum O.
This statement provides a method of relating a regularizer to its effect on the classifier. Please refer to Appendix for the proof and additional intuition.
Proposition 2. Given a classifier with parameters 0 and loss L()) with a local minimum Ô. For near O, suppose 4" is the corresponding local minimum of regularized loss L(0) + (R). Then, for X near L(0*) + XR2(0*) [(0) (R²(0) () if and only if:
- [ < [[ [17
(6)
where ||a||B VaTBa Ba.
This statement can be used to provide guidelines on regularization selection. Intuitively, the condition implies that selecting regularizers with close gradient to a particular "optimal" regularizer R2(0*) is
advantageous where distance is defined using the left hand side of the Equation 6 Please refer to Appendix F for the proof and additional intuition.
3.2 OUR REGULARIZER
Motivation and Rationale IBP one way to propagate the adversarial sensitivity at different layers of the neural network and construct a robust loss function, but there exist other methods of quantifying sensitivity the network. Different from IBP that bounds the input of each layer through and in 2). we introduce double margins and v such that [Znom s + v] represents the approximate range values each layer z can take, where Znom represents the value of the layer for unperturbed input Xnom- In the similar spirit of IBP, we define the term to approximate error margins at each layer of the network, but this margin s only requires propagation of one quantity while IBP requires two quantities and 1.
Double Margin:
V, 2nom
Existing certifiers such as Fast-Lin (Weng et al. 2018) and Reluplex (Katz et al., 2017) rely on activations to be locally linear in order achieve tight bounds. However, using the term by itself does not necessarily result in local linearity at activations. Thus, we also include the v term which penalizes a finite difference approximation of the second derivative of the activation function. This
5

---

Under review as a conference paper at ICLR 2020
margin has the property that when the network is locally linear in the sense that (zz) = azz + b for some a, b at all layers i, all margins v² x Intuitively, the s term can be seen as measuring a 1st order, linear level of adversarial sensitivity, while the v term measures 2nd order, nonlinear sensitivity (see Appendix Appendix(FFiuure 2 for visual illustration). The inclusion of the margin the key qualitative difference between our approach and IBP. Because our approach explicitly penalizes non-linearity, results in tighter certification and therefore more certifiable networks compared to IBP.
Double Margin: Formal Definition and v² at layer have the same dimensionality as z whether they are vectors in fully connected layers tensors in convolutional layers. Only the margins at the second layer depend on p.
Assuming a known lp perturbation size c, our margins s'
These margins are initialized as: S = el, v = O. For = O,..., n 1, subsequent layer margins are defined as:
s1+1
w (o + +s - o (z - -s))
2
++ w
(o + v') ozzioo v'))
(8)
2
+ 1
+s + v') + (zion -s'-
22 (z'mom)
For general Lp norms # oo, the second layer margins are modified so that s is exactly half the range of values z can take. To motivate the form of Equation 7 note that IBP can be reparameterized in terms of the half bound gap h (u - 1)/2 and bound average m = {u 1)/2. Then the half bound gap h is propagated as:
h H+1 W Wo + +h) - o (m' - h)))
2
The margin is propagated similarly, with the difference being that IBP uses (u' 12)/2 instead of z' as the centering point. This supports the intuition that the s margin by itself approximates the IBP bounds. The v margin is propagated the same way, with an additional term that uses a finite difference approximation of the second derivative of (-)) at z'. Specifically, note that given 2nd order Taylor expansion of (-) at specific scalar point Fo. a(x x0) 3 3a(z xo)2 b(x zu) + c, then the second derivative of (-) at xp is given by: o((xo) = a R 7 (a(2o + 77 + a (wo 7) (xx)),
where 7 > 0 small. Applying this approximation to the second term in Equation (
W (10
+ + +v*) + o (ziom s - - 2 w 10o""l
) (s' + v )
where all operators are applied element-wise. By approximating the second derivative of the activation, this term penalizes level of non-linearity. To motivate our use of finite difference instead of a second derivative directly, note that in the case of ReLU, using a second derivative would not work since ReLU has second derivative zero almost everywhere. A finite difference approximation also quantifies nonlinearity over a larger neighborhood; see Eq. I in Moosavi- et al. (2018) for a similar justification. Because we add two additional margins and addition the original network, we call our method double margin. Although the margins are defined for fully connected network, the margins can be computed analogously for special cases or extensions such convolutional neural networks residual networks. Our regularizer is defined implicitly function of the model parameters 0:
R(0)= E[L4 (z"i.m + + ++ L_ (z - - v²) L(z",o))
We note that our regularizer when added to the standard loss function is not a true upper bound on the adversarial loss since the margins do not provide exact bounds on each layer. However, as shown by Proposition 2 the gradient of a regularizer rather than its bound validity determines its certified test loss. Therefore, and as we also show experimentally, using an upper bound on the adversarial loss is not necessary to train certifiable models.
Training Procedure Training proceeds by using standard optimizers on the regularized loss. See Appendix D Algorithm T for the full procedure. Note that using value of X = corresponds to

---

Under review as a conference paper at ICLR 2020
standard training while using À = corresponds to using only the regularizer (i.e. robust loss). In practice, robust training methods such as IBP typically increase the value of À during training process. IBP specifically uses warm-up period where À = 0 first, then linearly increases À until it reaches X = 0.5. Note that the value of is separate from the value of e used during training which parameterizes the regularizer R(0)). A value of c = 0 also corresponds to regular training, and higher values of e correspond to defending against larger perturbation attacks. In addition to increasing during training, robust training methods also typically increase during training, IBP uses piece-wise linear schedule for c with warm-up and ramp-up periods coinciding with the schedule for A. We use a similar piece-wise linear schedule as IBP.
3.3 EXTENSIONS
We extend our method to an tn threat model by modifying the double margin propagation at the second layer done for general Ep perturbations. We also extend our method to ensembles of models trained with our regularizer. Additional details are provided in Appendix H
4 EXPERIMENTS
We conduct experiments comparing our regularizer to other robust training methods including & weight regularization, adversarial training, IBP, ReLU stability and convex outer bounds (Bounded).
4.1 SETUP, MODELS, DATASET
Implementation, Architectures, Training Parameters Training methods are implemented in Python with Tensorflow (Abadi al. 2016) and training is conducted on a NVIDIA Tesla P100 GPU. We evaluate the training methods on networks trained on the MNIST, CIFAR- 10 and GTSRB (Stal Ikamp et al. 2012) datasets. We consider 6 model architectures listed roughly in increasing model size: (i) Small CNN, (ii) Pureconv CNN, (iii) Resnet CNN, (iv) Pooling CNN, (v) Medium CNN, (vi) Large CNN. For fair comparison among training methods, we used fixed training parameters. Architecture and hyperparameter details are deferred to Appendix
We train networks with (i) normal training, (ii) & weight regularization, (iii) adversarial training, (iv) IBP, (v) ReLU stability, (vi) Bounded, (vii) MMR (Croce et al. 2019)). (viii) TRADES (Zhang et al. 2019) and (ix) our method (Double Margin). Due to the computational cost of running Bounded training, we train this method only on the small CNN architecture. For training Bounded models, we use the technique of random projections as proposed by (Wong et al.) 2018), using 50 random projections. For the small CNN architecture, we try additional robust training methods including (x) combining adversarial training with the ReLU stability loss and weight pruning Add+RRSPPruning and (xi) combining l weight regularization with ReLU stability and weight pruning (LI+RS+Pruning We also (xii) add & weight regularization to our regularizer (Double Margin LI).
Comparative Methods
Evaluation Although our regularizer applies general lp threat model, we primarily conduct experiments assuming a fo threat model. The networks are evaluated on certified accuracy computed using CNN-Cent-RLLU, which efficiently finds lower bound on the worst-case adversarial accuracy under norm bounded perturbations. We use CNN-Cert due to the high computational cost of using other methods such as Mixed Integer Optimization (MIO) Tieng & Tedrake (2019), even with using a optimization timcout as done by Goowal et al. (2018). In particular, we found that the initialization stage of the MIO verifier itself typically took longer than CNN-Cert. Baseline certified accuracies are generally higher in prior works because they are computed using slower certifiers. Certified accuracies are computed for 200 test set points (unless otherwise noted) over a range of perturbation sizes e in [0, 0.4] for MNIST and [0, 9/255] for CIFAR and GTSRB. In addition, for selected networks we compute certified accuracies using IBP. For all certified accuracy comparisons, we use the same randomly selected set of test points. For two selected networks, we also compute certified accuracies on the entire test set and verify that the certified accuracies are similar to ensure that our randomly chosen test points are representative (see Appendix [].
7

---

Under review as a conference paper at ICLR 2020
Craa 0.1
Emaa 02
X
03
200
beaa 2/255
8/255
Normal
Normal
Certified Accuracy (%)
Sounded
Certified Accuracy (%)
IBP
[8P
Double Margin
73
Double Margie
Stability
25.
0.00
0.22
Perturbation Size (a) MNIST
Perturbation Size
(b) CIFAR
Figure I: CNN-Cert certified accuracy against perturbation size for models trained normally and with several robust training methods including Bounded, IBP and our method, Double Margin. Results are shown for different values of Étrain. (a) shows results MNIST and (b) on CIFAR. Refer to Table for additional baselines including MMR and TRADES.
4.2 RESULTS
Baselines Comparison In all CNN-Cert comparison tables, the best methods in each column are highlighted, excluding normal training and standard weight regularization. provides summary of the comparative experiments. We first highlight that over all tested datasets, our training methods train in less time than IBP, Bounded, TRADES and MMR. On MNIST, our methods, in bold, outperform ReLU stability based methods and adversarial training for c = 0.01 and larger, and outperform IBP and Bounded for large perturbation sizes beyond 0.07. We note that adding &, weight regularization to our regularizer further enhances our certified accuracies. On CIFAR, our method outperforms ReLU stability based methods and adversarial training for e 1/255 and larger, and outperforms IBP and Bounded for perturbation sizes beyond e = 0.5/ On MNIST and CIFAR. we observe that due high hyperparameter sensitivity. Bounded and ReLU stability sometimes have low clean accuracy and TRADES achieves low certified accuracy. Certified accuracy results for selected small MNIST and CIFAR networks are also presented visually Figure [ On GTSRB, our method outperforms IBP and MMR for 3/ 3/255 and larger. Additional results on MNIST, CIFAR and GTSRB are shown in Appendix J Tables g 9 and respectively. In brief, all the experiments show that our method achieves higher CNN-Cert accuracy for large than any prior work.
Ablation Experiments and Hyperparameter Analysis In addition, we separately analyze the effect of and margins in Double Margin by rumning the following comparisons: training with only the s margin (Variation 1: "s only'), and training Double Margin with IBP bounds u, replacing (Variation 2: 'IBP+t"). sshows that Variation performs comparably to outperforms IBP while requiring only fewer propagation during training, supporting the intuition that the margin by itself approximates IBP. Variation 2 performs comparably to Double Margin but it requires one additional propagation during training (10-40% increased training time). These observations suggest that the "v' margin primarily responsible for Double Margin's 's improved certifiable robustness for large perturbations, but at the expense of lower clean accuracy compared to IBP. In order to improve the clean accuracy of networks trained with our method, we also train under different heprpaaraeeter setting where À is halved during training, reducing its final value from to 7. As seen in Table 2 Double Margin still outperforms IBP on the largest (60.4 vs 0.0% on MNIST and 46.4 vs 26.8% 8% GTSRB) while achieving a higher clean accuracy (91.1% % on MNIST and 75.6% on GTSRB). These results suggest that fine-tuning mee-unnng hyperparameters can improve clean accuracy to be more comparable to prior work while maintaining better certified accuracy large
Extensions We find that method's high certified accuracy extends to lo norm threat model. In addition, we find that using model ensembles with our method can used to enhance certified accuracy. Results shown in Appendix |
8

---

Under review as a conference paper at ICLR 2020
5 CONCLUSION
In this paper, we propose a unified framework of certified defense as regularization. We introduce new efficient regularizer under this framework, and extend it to threat model and model ensembles. Through comparative experiments on several model architectures, we demonstrate that our method outperforms state-of- oftte-of-the-att certification based training methods in terms of training time and certified accuracy.
Training
Method (200 points)
Time (scc)
0.01
0.03
0.05
0.07
0.10
0.20
0.30
0.40
Small CNN MNIST. 4aayer
Normal
185.7
98, 5%
9.5%%
0.9%
0.00%
0.05%
0.0%
0.05%
0.0%
0
Weight Regularization
Adv. Training
8760.5
99.5%
98.5%
91.5%
38.5%
1.0%
0.0%
0.0%
0.0%
0.0%
Hounded
27966 8
30.0%
30.09%
30.9%
30.05%
30.05%
29.5%
28.558
25.05
0.0%
IBP
95.5 35.5%
95.5%
95.5%
90.5%
76.5%
39.5%
0.0%
0.0%
0.0%
ReLU Stabilty
595.8
94.0%
90.055
65.0%
0%%
5.0%%
0.5%
0.0%
0.0%
LI-RS-Pruning
686.5
95.0%
88.0%
53.5%
13.5%
3.0%
0.5%
0.0%
0.0%
0.0%
Ad-+RS-Prrning
9657.1
90.0%
86.5%
70.5%
00%
30.5%
13.5%
0.0%
0.0%
0.0%
Margin
66.5%
Double Margin +1.1
$47.1
91.0%
90.59
90.0%
89.5%
89.0%
87.5%
83.5%
68.0%
0.0%
Training Time (scc)
Mothod (200 points)
0,5/255
1/255
2/255
3/255
5/ 225
7 7/266
8/ 8/256
9/255
Small CNN CIFAR, 4 layer
Normal
141.1
61.5%
22.0%
1.5%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
Weight Regulatization
1062.8
0.0%
Adv. Training
51893.6
60.5%
25.0%
2.5%
0.0%
0.0%
0.0%
0.0%
0,0%
0.0%
Bounded
21918.7
4.0%
4.0%
4.0%
4.0%
1.0%
4.0%
3.5%
3.5%
3.5%
IBP
8/206
410.0
37.5%
35.0%%
32.5%
20.0%
17.5%
2.5%
0.0%%
0.0%
0.0%
Rel.i Stabilty
12.0%
12.0%
12.0%
12.0%
12.0%
12.0%
12.0%
12.0%
12.0%
Double Margin
409.7
45.5%
45.0%
43.5%
40.5%
39.5%
28.0%
22.5%
19.5%
15.0%
Pooling CNN CIFAR, layer
0.0%
0.0%
Weight Regullarization
828.8
$9.0%
0.0%%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
IBP
4015.
43.0%
15.5%
8.5%
3.0%
3.0%
0.0%
0.0%
0.0%%
0.0%
ReLU Stabiity
8/ 255
1676.9
58.5%
Double Margin
2899.5
40.0%
32.5%
30.5%
24.0%
23.5%
5.0%
1.0%
1.0%
0.5%
Parecony CNN GTSRB, layer
Normal
IBP
287.7
64.0%
63.0%
62.0%
58.5%
57.00 57.0%
44.5%
31.5%
26.0%
22.00
Double Margin
8/
283.1
68.0%
67.5%
67.0%
65.0%
64.5%
58.0%
52.5%
50.0%
45.5%
Training Time (scc)
Method (1000 points)
Gerd
0.05
0.10
0.20
0.30
Small CNN MNIST, layer
TRADES
8264.6
99.5 (0.7)%
0.0 (0.00%
0.0 (0.0)%
0.0 (0.00%
0.0 (0.0)%
IBP
611.2
96.3 (1.7y%
92.2 (2.5y%
46.5 (5.1)%
0.0 (0.0%%
0.0 (0.0y%
IBP
460.9
96.7 (1 (1.4)%
90.3 (2.6)%
39.3 (4.6)%
0.0 (0.00%
0.0 (0.0y%
DM Variation
=
273.3
94.0 (2%
92.7 (2.5)%
90.1 (3.0)%
(3.99%
33.1 (4.7)%
DM Variation
$89.6
90.1 (2.5)%
88.9 (3.1)%
86.5 (3.2)%
(3.7)%
59.0 (5.0y%
Double Margin
520.0
88.2 (2.6)%
86.7 (3.1%)
(3.4%%
(3.9)%
61.9 (4.6) %
Double Margin
415.3
91.1 (2.6)%
90.1 (2.95%
(3.2)%
78.4 (3.9)%
60.4 (4.7)%
Training Time (sec)
Method (500 points)
Exert
1/255
3/255
5/255
8/255
Small CNN CIFAR, 4 layer
TRADES
56391.6
(4.4)%
(2.5y%
(0.0)%
(0.0)%
(0.0y%
IBP
2446.6
38.0 (4.2)%
32.8 (4.0y%
14,6 (3.1)%
6.0 (2.2g%
1.2 (0.89%
Variation
8/255
1475.8
45.0 (5.1)%
41.0 (3.8)
33.8 (4.4)%
22.8 (3.99%
10.4 (2.6%%
DM Variation
3062.8
43.0 (4.6)%
40.6 (4.2%%
34.2 (4.0)%
27.0 (4.1y%
(3.2)%
Double Margin
2198.7
43.2 (4.0)%
40.4 (4.61%
32.8 (4.4)%
28.6 (4.4)%
19,8 (3.5)%
Pureconv CNN GTSRB, layer
MMR (4 epachs)
853777.2
88.2 (2.8)%
53.6 (4.0y%
18.2
4.2 (1.8888)
(0.0%%
IBP
287.7
71.8 (3.9)%
68.0 (4.3)%
60.8 (4.3)%
47.6 (4.7%%
(3.5%%
IBP +
8/255
266.6
(3.7))
7488 (3.7) %
62.2 (4.3)%
45.6 (4.7)%
26.8 (3.55%
Double Margin
283.1
67.8 (4.4)%
66.8 (4.39%
61.4 (4.33%
56.4 (4.75%
48.2 (4.5)%
Double Margin
258.1
75.6 (3.9)%
73.8 (4.2)%
65.0 (4.5)%
57.2 (4.4)%
46.4 (4.4y%
Table 2: CNN-Cert certified accuracies and training times. std in (.). denotes a different setting of regularization parameter X, decreased from } to 4- MMR is trained for epochs due its long training time. Our methods or variants are in blue.

---

Under review as a conference paper at ICLR 2020
REFERENCES
Martín Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, et al. Tensorflow: system for large-scale machine learning. 2016.
Anish Athalye and Ilya Sutskever. Synthesizing robust adversarial examples. arXiv preprint arXiv:1707.07397, 2017.
Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give false sense of security: Circumventing defenses to adversarial examples. ICML, 2018.
Peter L.. Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. JMLR, 2002.
Akhilan Boopathy, Tsui-We Weng, Pin-Yu Chen, Sijia Liu, and Luca Daniel. Can-cert: An efficient framework for certifying robustness of convolutional neural networks. In AAAI, Jan 2019.
Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In IEEE Symposium on Security and Privacy (SP), pp. 39-57, 2017.
Nicholas Carlini, Guy Katz, Clark Barrett, and David L Dill. Provably minimally-distorted adversarial examples. arXiv preprint arXiv:1709.10200) 2017.
Pin-Yu Chen, Yash Sharma, Huan Zhang, Jinfeng Yi, and Cho-Jui Hsieh. Ead: elastic-net attacks to deep neural networks via adversarial examples, AAAI, 2018.
Chih-Hong Cheng, Georg Nührenberg, and Harald Ruess. Maximum resilience of artificial neural networks. In International Symposium on Automated Technology for Verification and Analysis, pp. 251-268. Springer, 2017.
Francesco Croce, Maksym Andriushchenko, and Matthias Hein. Provable robustness of relu networks via maximization of linear regions. In AISTATS, 2019.
Krishnamurthy Dvijotham, Sven Gowal, Robert Stanforth, Relja Arandjelovic, Brendan O'Donoguue, Jonathan Uesato, and Pushmeet Kohli. Training verified learners with learned verifiers. arXiv preprint arXiv: 10265, 2018a.
Krishnamurthy Dvijotham, Robert Stanforth, Sven Gowal, Timothy Mann, and Pushmeet Kohli. A dual approach to scalable verification of deep networks. UAI, 2018b.
T. Gehr, M. Mirman, D. Drachsler-Cohen. P. Tsankov, S. Chaudhuri, and M. Vechev. Ai2: Safety and robustness certification of neural networks with abstract interpretation. In JEEE Symposium on Security and Privacy (SP), volume 00, pp. 948 963, 2018.
Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. ICLR, 2015.
Sven Gowal, Krishnamurthy Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Uesato, Relja Arandjelovic, Timothy Mann, and Pushmeet Kohli. On the effectiveness of interval bound propagation for training verifiably robust models. arXiv preprint 15X1v:1810.12715. 2018.
Matthias Hein and Maksym Andriushchenko. Formal guarantees on the robustness of classifier against adversarial manipulation. In NIPS, 2017.
Guy Katz, Clark Barrett, David L Dill, Kyle Julian, and Mykel J Kochenderfer. Reluplex: An efficient smt solver for verifying deep neural networks. International Conference on Computer Aided Verification, pp. 97-117. Springer, 2017.
J Zico Kolter and Eric Wong. Provable defenses against adversarial examples via the convex outer adversarial polytope. /CML, 2018.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant adversarial attacks. ICLR, 2018.
10

---

Under review as a conference paper at ICLR 2020
Matthew Mirman, Timon Gehr, and Martin Vechev. Differentiable abstract interpretation for provably robust neural networks. In International Conference on Machine Learning, pp- 3575-3583, 2018.
Seyed-Mohsen Moosavi-Dezfooli, Alhussein Fawzi, Jonathan Uesato, and Pascal Frossard. Robust- ness via curvature regularization, and vice versa. In CVPR, 2018.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control in neural networks. JMLR, 2015.
Nicolas Papernot, Patrick McDaniel, Somesh Jha, Matt Fredrikson, Z Berkay Celik, and Ananthram Swami. The limitations of deep learning in adversarial settings. In IEEE European Symposium on Security and Privacy (EuroS&P), pp. 372-387, 2016.
Jonathan Peck, Joris Roels, Bart Goossens, and Yvan Saeys, Lower bounds the robustness to adversarial perturbations. In NIPS, 2017.
Aditi Raghunathan, Jacob Steinhardt, and Percy Liang. Certified defenses against adversarial examples. ICLR, 2018.
Hadi Salman, Greg Yang, Huan Zhang, Cho-Jui Hsieh, and Pengchuan Zhang. A Convex Relaxation Barrier to Tight Robustness Verification of Neural Networks. arXiv preprint MwXi:::902.0872. 2019.
Gagandeep Singh, Timon Gehr, Matthew Mirman, Markus Püschel, and Martin Vechev. Fast and effective robustness certification. In NewrlPS, 2018.
Gagandeep Singh, Timon Gehr, Matthew Mirman, Markus Püschel, and Martin Vechev, An abstract domain for certifying neural networks. In POPL, 2019.
Aman Sinha, Hongseok Namkoong, and John Duchi. Certifiable distributional robustness with principled adversarial training. ICLR, 2018.
Stallkamp. M. Schlipsing, J. Salmen, and C. Igel. Man vs. computer: Benchmarking machine learning algorithms for traffic sign recognition. Neural Networks, 2012.
Jiawei Su, Danilo Vasconcellos Vargas, and Kouichi Sakurai. One pixel attack for fooling deep neural networks. IEEE Transactions on Evolutionary Computation, 2019.
Christian Szegedy, Wojeiech Zaremba, llya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties neural networks. arXiv preprint 13 2013.
Vincent Tjeng and Russ Tedrake. Verifying neural networks with mixed integer programming. In ICLR, 2019.
Florian Tramèr and Dan Boneh. Adversarial training and robustness for multiple perturbations. arXiv preprint 190::1994.300000 2019.
Shiqi Wang, Kexin Pei, Justin Whitehouse, Junfeng Yang, and Suman Jana. Efficient formal safety analysis of neural networks. In NewrIPS, 2018.
Tsui- Wei Weng, Huan Zhang, Hongge Chen, Zhao Song, Cho-Jui Hsieh, Duane Boning, Inderjit S Dhillon, and Luca Daniel. Towards fast computation of certified robustness for relu networks. ICMI., 2018
Eric Wong, Frank Schmidt, Jan Hendrik Metzen, and J Zico Kolter. Scaling provable adversarial defenses, arXiv preprint arXiv:1805.12555 2018.
Kai Y. Xiao, Vincent Tjeng, Nur Muhammad Shafiullah, and Aleksander Madry. Training for faster adversarial robustness verification via inducing relu stability. In ICLR, 2019.
Kaidi Xu, Sijia Liu, Pu Zhao, Pin- Yu Chen, Huan Zhang, Deniz Erdogmus, Yanzhi Wang, and Xue Lin. Structured adversarial attack: Towards general implementation and better interpretability. arXiv preprint arXiv: 1808.0 066.0/664, 2018.
11

---

Under review as a conference paper at ICLR 2020
Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric P. Xing, Laurent El Ghaoui, and Michael I. Jordan. Theoretically Principled Trade-off between Robustness and Accuracy. ICML, 2019.
Huan Zhang, Tsui-Wei Weng, Pin-Yu Yu Chen, Cho-Jui Hsieh, and Luca Daniel. Efficient neural network robustness certification with general activation functions. In NIPS, dec 2018.
12

---

Under review as a conference paper at ICLR 2020
APPENDIX
A APPENDIX OUTLINE
A. Appendix Outline
B. Table of Notation
C. Double Margin Visual Illustration
D. Double Margin Algorithm
E. Proof of Proposition 1
F. Proof of Proposition 2
G. Architecture and Hyperparameter Details
H. Extensions
1. to Norm Threat Model
2. Model Ensemble
Additional Results
Comparing Different Certification Methods Effectiveness on Other Norms
3. Model Ensemble
4. GTSRB
5. Medium CNN Model
Full Test Set
J. Additional Tables
1. Comparing Different Certification Methods Effectiveness Other Norms
Model Ensemble Additional GTSRB Results
5. Double Margin Ep
6. Complete MNIST Results
7. Complete CIFAR Results
Full Test Set Additional IBP Certified Accuracy
B TABLE OF NOTATION
Notation
Definition
Notation
Definition
Xnom
unperturbed input input perturbation
W b
weights, biases of layer input of layer
8
z
maximum 4, perturbation size ||ő]| perturbed input
u'
pre-activation interval bounds double margins
st v
f
neural network classifier
a², St. Bi.
linear bounding parameters
neural network activation
A, bı, bu
linear network bounds
number of network layers number of training points point-wise loss function model parameters
C
training loss function
m
Ciess
loss function
L: 2t +
R +
regularizer
0
regularizer coefficient
Table Table of Notation
13

---

Under review as a conference paper at ICLR 2020
C
DOUBLE MARGIN VISUAL ILLUSTRATION
Margin s:
Margin v:
Tracks linear sensitivity
Tracks non-linear sensitivity
Less linear MY Less
1
nonlinear
sensitivity
sensitivity
Figure 2: A visual illustration of Double Margin's sensitivity quantification. is propagated as $ =
W (o + s) o(z s)). v is propagated W (a v) a(z -v))+ W lo
8 S+ v) - S v) (z)
D DOUBLE MARGIN ALGORITHM
Algorithm 1: Double Margin Training Algorithm
Data: Training data D, Randomly initialized weights and biases W b 1: N, Number of epochs E, Perturbation size e, Regularization weight
Result: Trained weights and biases W b'
for epoch = I:E do
for Xmom in D do
z Xnom. s
c1, v0 = 0;
for I:N do
Propagate z with Equation
Propagate s++1 with Equation
Propagate vi+ with Equation
end
Construct regularized loss
L + XR = AL (z" + + + v + XL_ (z" S" -v) + (1
-A)((z")
Compute gradients of C + XR w.r.t. W b.
Update W', b' via gradient descent
end
end
E PROOF OF PROPOSITION 1
Proof. Suppose L(0) + XR()) has local minimum (*)). Note that at X = 0, 6"
Note that the
derivative of the regularized loss is 0 at 0":
VoL(O") AVOR(0")=
Differentiating both sides with respect to A:
H(C(O')) d 0r + VoR(0") + X VoR(0") =
dx
dA
Solving for d 0":
dd 0" -H(C(()) + + d
VoR(o))
Evaluating A= 0:
dA - -
14

---

Under review as a conference paper at ICLR 2020
This implies that for small A: o" ~ -=O-AH(C())
Intuitively, this statement indicates that for small amounts of regularization, the gradient of the regularizer sufficient to determine the behavior of the regularizer: note that in Equation (5) the position of the new local minimizer only depends the regularizer via its gradient. This can be used to analyze which robust regularizer is optimal with respect to another known metric such as generalization error.
F PROOF OF PROPOSITION 2
Proof. Note that at À = 0, 0* Ó. Consider the difference between the performance of 0 and Ô on regularized loss L(0) + (f):
((A) [(0) (R2(()) L()*) (R2
Taking the derivative with respect to X: d
d D(A) = -- d
dA X
00) + (R2(0) - R2(0"))
YA
dd
Note that evaluated respect to A:
O, this quantity is since VoL(() 0. Taking second derivative with
d dxz
O ((((H((())) - -0- VoL(0')
de
D(A) D(A)
dx2 dx=00 - 2V 2V
-
dx
dx
x d
(o
dx
dd
Evaluating A 0:
d²
o HC(()) ((C()
D(A)l2=0 -
d 2V
00
dX2
d)
since VoL(0) O. Substituting the expression for -0 from Proposition
dc
dx2 1000 -
Simplifying:
&
(2) (v ((((())- ( +
(oR2 ( ((C())))
dx2
Where ||a||a = Va Ba. This implies that for small À + D(A) > equivalent to the condition:
[VoR, (0) V < ||V (
This condition provides some guidelines how to select regularizer provided some "true" objective which is also a function of model parameters A. The true objective J(0) could, for example, a robust generalization bound or the difference between robust validation set loss and clean training set loss. Given a standard loss function C()) and regularization parameter X, the true objective can be expressed in the form of regularization:
[(0) = L()) + (R) Suppose L(() has minimum 0, and suppose there is set of feasible regularizers that can be used during training of the network {R, (0), (0), (#)) with regularization coefficient X. Then, Proposition 2 suggests selecting the regularizer R(()) = arg min; (,) VoRg (f) ()c(()) (0) Here (0) corresponds to the minimized regularizer R, (0) in Proposition 2 and R (0) corresponds to the target regularizer (θ). Intuitively, the regularizer that is closest to R (8) in gradient is selected. This selection of regularizer optimal as À approaches zero. For example, in the case robust training, the robust training method with the closest gradient to Rg((1) (0) is best.
15

---

Under review as a conference paper at ICLR 2020
G ARCHITECTURE AND HYPERPARAMETER DETAILS
The small CNN architecture uses convolution layers of 16 and 32 filters followed by a 100 unit fully connected layer. The pureconv CNN architecture uses three convolution layers of 16 filters. The medium CNN architecture uses convolutional layers of 16, 16, 32 and 32 filters followed by two 512 unit fully connected layers. The large CNN architecture uses convolutional layers of 64, 64, 64, 128 and 128 filters followed by a 200 unit fully connected layer. The pooling CNN architecture uses two convolution layers of 16 filters each followed by a max-pooling layer of stride 2-by-2. The resnet CNN architecture uses a 16 filter convolution layer followed by a simple residual block with two 16 filter convolution layers. The MNIST and GTSRB networks are trained for 100 epochs each while the CIFAR networks are trained for 350 epochs each. For robust training methods, we use E (0.1, 0.33 for MNIST and c E (2/255, 8/ 8/255) for CIFAR and GTSRB as the training target perturbation size Étrain- We used fixed hyperparameters for fair comparison among training methods (including ours without fine parameter tuning), which may cause different baseline clean accuracies from prior work.
H EXTENSIONS
H.1 to NORM THREAT MODEL
In addition to a Ep threat model, we can consider a lg threat model where an input Xnom is perturbed by perturbation to produce perturbed input Xnom + 5 where ||ôllo S k, where |lollo is the number of non-zero elements in 8. This corresponds to perturbing at most dimensions of the input by any amount. In practice, in the case of image inputs for example, perturbations are limited by the range of values each dimension can take. For example, pixels are typically restricted to be in a limited range such [0, 1].
In this case, our regularizer can be used directly without modification when using a large foo perturbation size e. is also possible to modify our regularizer at the first layer of margin propagation. At the first layer, the margin s can be set exactly to one half the range of values each node can take:
5
rank(W)) @ (1 - xxom). rank W j.: Xxoms l),
assuming the input is restricted to range [0, 1]. where rank(a, 1) selects the Ith largest element of and @ denotes element- wise multiplication. Doing so makes our regularizer more closely match the true range of values layers can take for to perturbations.
H.2 MODEL ENSEMBLE
is also possible to extend our regularizer to model ensembles. Suppose there are N models fi (x),, (x)),... (x). Then the N models can be trained together using our regularizer. One method is to average together the output layers of the individual models yield an ensemble model:
fensembie (x)
Σ fi(x)
When using our regularizer, the regularization margins of the N models can also be averaged together. The ensemble loss is then constructed by substituting the averaged values into Equation (9). During inference, the final layers can be averaged together before classification. Alternatively, we can select the class with the most votes among the ensembled models.
I ADDITIONAL RESULTS
I.1 EFFECTIVENESS ON OTHER NORMS
Table 4illwsssswww & certified accuracies for a small CNN architecture trained on MNIST and CIFAR. We show results for both standard Double Margin trained with 0.3 and 8/255 for MNIST
16

---

Under review as a conference paper at ICLR 2020
and CIFAR respectively. We also show results for Double Margin modified for the to threat model trained with e = 2. As illustrated, the Double Margin Ey regularizer yields certified accuracies that decay slowly with the number of perturbed dimensions Surprisingly, Double Margin performs better than the to modification for fo certified accuracies, and moreover has consistent performance across perturbation sizes. This suggests that training methods that yield high Loo certified performance on also transfer to yield high lo certified performance. Intuitively, this may be because networks which are highly certifiable for low levels of Lo perturbations have particular weight patterns such as sparsity that allow for high certification in general including for to perturbations. We hypothesize that this effect is particular to Eo due to the non-convexity of the to norm during training.
find that standard
To support the reasoning that the transferability of Double Margin to a ln threat model is unique to lo. we conduct experiments comparing different versions of Double Margin Ep with p = co, 2, (see Section [32] Double Margin: Formal Definition for details). The three different versions of Double Margin are each certified on the three different Ep norms. Small CNN networks are trained on MNIST and CIFAR with 0.3, 1,4 4 and e = 8/255, 0.2, for loe &2 l norms respectively. All versions trained with fixed hyperparameters for each dataset. We find that the largest perturbation size evaluated, each version of Double Margin generally performs best on its respective norm (Double Margin for has the highest &o certified accuracy etc.) This observation supports the hypothesis that the effectiveness of Double Margin lor on to is unique. Interestingly, for smaller perturbation sizes Double Margin for achieves better certified accuracy on l2 perturbations than Double Margin l2- Similarly, for small perturbation sizes, Double Margin E2 achieves better certified accuracy than Double Margin ε, This may be because certifiability on lg and l norms incurs stronger penalty on clean accuracy compared to the &oo norm.
I.2 MODEL ENSEMBLE
Table shows certified accuracies for two ensemble models trained on MNIST and CIFAR, each composed of three models. The ensemble models compared with averaged certified accuracies for three individual models. Certified accuracies for the ensemble models are computed with CNN-Cert by considering the ensemble model as single model with multiple parallel sub-components. We find that the ensemble model achieves the same or higher certified accuracies for nearly all the perturbation sizes tested. This suggests that using ensembles may be a method of enhancing certified accuracies for smaller perturbation sizes without sacrificing performance on larger perturbation sizes.
1.3 GTSRB
shows certified accuracies computed using CNN-Cert for a pureconv CNN model trained on GTSRB. Certified accuracies computed over 200 random test set points. We compare Double Margin with IBP and normal training. For IBP and Double Margin, training is performed with perturbation sizes of e = 2/255, 8/255. Double Margin achieves higher certified accuracy than IBP over all tested perturbation sizes 2 2/255. In particular, we achieve a 24% improvement in certified accuracy for e 8/255. Double Margin also trains in less time than IBP.
Table shows
1.4 MEDIUM CNN MODEL
Tables g and 9 show complete certified accuracy results computed using CNN-Cert for including for Medium CNN models. Due to the cost of certifying on models of this size, we compute certified accuracies over 20 points. Double Margin matches outperforms IBP over most perturbation sizes, and particularly improves on IBP for large perturbation sizes (E 0.1, 0.2, 0.3 for MNIST and 2/25 255 3/255, 5/255 for CIFAR).
I.5 FULL TEST SET
Table T0
shows CNN-Cert certified accuracies computed on the full test set for two selected models trained on MNIST and CIFAR. The certified accuracies are similar to those computed on 200 randomly selected test set points, indicating that the random sample is fairly representative.
17

---

Under review as a conference paper at ICLR 2020
J ADDITIONAL TABLES
Training Time (sec)
Method
Ecort
0.05
0.10
0.20
0.30
Small CNN MNIST, layer, 8oo
Double Margin Eoo
E 0.3
609.7
89.0%
89.0%
88.0%
81.0%
63.5%
Double Margin &
593.7
68.5%
59.5%
50.5%
9.0%
0.5%
Double Margin to c
593.3
86.0%
76.0%
57.5%
4.0%
0.0%
Training Time (sec)
Method
Feert
0.25
0.50
0.75
1.00
Small CNN MNIST, 4 layer. E
Double Margin &oo
0.3
609.7 593.7
89.0% 68.5%
0.0%
0.0%
0.0%
0.0%
Double Margin
62.5%
53.0%
35.5%
11.0%
Training Time (sec)
Method
Coort
1.00
2.00
3.00
4.00
Small CNN MNIST; 4 layer,
Double Margin 8oc
6
0.3
609.7 593.3
89.0% 86.0%
89.0 %
89.0 %
89.0% %
89.0%
Double Margin kg 6
85.5%
84.0%
82.0%
60.5%
Training Time (sec)
Method
Ecort
1/255
3/255
5/255
8/255
Small CNN CIFAR, 4 layer, Loo
Double Margin 6o
8/255
3058.8
42.5%
40.0%
35.0%
31.0%
20.5%
Double Margin &
2975.4
30.0%
28.5%
24.5%
20.5%
19.5%
Double Margin to
2991.7
28.0%
27.0%
25.0%
22.5%
19.5%
Training Time (sec)
Method
Coert
0.05
0.10
0.15
Small CNN CIFAR, 4 layer, 6
Double Margin &go
8/255
3058.8 2975.4
42.5% 30.0%
0.0% 28.5%
0.0%
0.0%
0.0%
Double Margin
27.0%
23.5%
22.5%
Training Time (sec)
Method
Coort
1.00
2.00
3.00
4.00
Small CNN CIFAR, layer,
Double Margin 6o 6 8/255
3058.8 2991.7
42.5% 28.0%
42.5%
42.5% 27.5%
42.5% %
42.5 %
Double Margin &g 6
27.5%
26.0%
24.0%
Table 4: CNN-C certified accuracies for Effectiveness other norms
Training Time (sec)
Method
Coors
0.01
Small CNN MNIST,
Double Margin
521.1
95.5% 95.5%
95.5%
95.2%
94.2%
93.5%
91.7%
81.3%
0.0%
0.0%
Double Margin Ensemble
1411.2
95.5%
95.5%
95.5%
94.5%
93.5%
85.5%
0.0%
0.0%
Training
Method
Time (see)
Gevt
0.5/255
1/255
2/255
3/255
5/255
7/255
8 6/255
9/255
Small CNN CIFAR, layer
Margin
2517.3
42.8%
36,80 36.8%
26.8%
Double Margin Ensemble
5/255
6566.2
46.0%
44.0
43.5%
40.0%
38.0%
27.0% %
22.0%
16.0%
11.0%
Table CNN-Cert accuracies for Model ensemble. The ensemble uses three models with different random initialization and random training batches. For fair comparison with standard Double Margin, three models with the same random initializations and training batches are trained independently. The training times and certified accuracies for standard Double Margin are averaged over these three models.
18

---

Under review as a conference paper at ICLR 2020
Training Time (sec)
Method
0
0.5/255
1/255
2/255
3/255
5/255
7/255
8/255
9/255
Pureconv CNN GTSRB, 4 lnyer
Normal
119.6
92.0%
77.5%
57.5%
37.0%
35.0%
6.5%
1.0%
0.0%
0.0%
81.5%
65.0%
63.5%
10.0%
Double Margin
2/255
282.6
83.0%
80.0%
77.5%
68.5% %
67.0 %
43.5%
27.5%
22.0%
16.5%
IRP
287.7
64.0%
63.0%
62.0%
58.5%
57.0%
44.5%
31.5%
26.0%
22.0%
Double Margin
8/255
283.1
68.0%
67.5%
67.0%
65.0%
64.5%
58.0%
52.5%
50.0%
4
Table 6: CNN-Cert certified accuracies GTSRB networks.
19

---

Under review as a conference paper at ICLR 2020
Training Time (sec)
Method
Foors
Small CNN MNIST.
layer, &sc
Double Margin f..
0.3
609.7
89.0%
89.0%
88.0%
81.0%
63.5%
Double Margin Eg
$92.0
68.5%
61.5%
50.0%
22. 22.5%
1.5%
Double Margin &
593.7
68.5%
59.5%
50.5%
9.0%
0.5%
Double Margin
593.3
86.0%
76.0%
57.5%
4.0%
0.0%
Training Time (5ec)
Method
0.25
0.50
0.75
1.00
Small CNN MNIST, layer,
Double Margin &s
0.3
609.7
89.0%
84.5%
0.0%
0.0%
0.0%
Double Margin
592.0
68.5%
62.0%
52.0%
41.5%
24.0%
Double Margin E
593.7
68.5%
61 .00%
51.5%
34.0%
9.0%
Double Margin
593.3
86.0%
80.5%
69.0%
39.0%
7.5%
Training Time
Method
Goort
1.00
2.00
3.00
4.00
Small CNN MNIST, layer, Eg
Double Margin
609.7
0.0%
Double Margin fg
$92.0
68.5%
60.5%.
39.0%
0.0%%
0.0%
Double Margin
593.7
11.0%
Double Margiu &n
593.3
86.0%
81.0%
69.0%
39.5%
6.5%
Training Time (sec)
Method
Seart
1.00
3.00
4.00
Small MNIST, layer,
Double Margiu &x
0.3
609.7
89.0%
89.0%
89.0%
89.0%
89.0%
Double Margin fg
592.0
68.5%
68. 5%
68.5%
Double Margin fj
$93.7
68.5%
68.5%
68..5%
68.5%
67.5%
Margin
Training Time (sec)
Method
1/255
3/255
5/255
8/255
Small CNN CIFAR, 4 layor, fac
Double Margin &x
8/255
3058.8
42.5%
40.0%
35.0%
31.0%
20.5%
Double Margin
0:2
2969.9
35.0%
32.5%
27.5%
25.5%
17.5%
Double Margin 8
2975.4
30.0%%
28.5%
24.5%
20.5%
19.5%
Double Margin
2991.7
28.0%
27.0%
25.0%
22.5%
19.5%
Training Tane (sec)
Method
Keart
0.05
0.10
0.15
0.20
Small CNN CIFAR,
layer, fg
Double Margin 8/255
8
33.5%
Double Margiu &
0.2
2969.9 9
35.0%
33.0%
31.5% %
28.0%
26.5 %
Double Margin
2975.4
30.0%
28.5%
27.0%
26.0%
23.5%
Double Margin to
2991.7
28.05
27.0%
26.5%
25.0%
24.0%
Training
Method
Time (sec)
0.50
1.00
1.50
2.00
Small CIFAR,
layer, &
Double Margin f...
8/255
3058.8
42.5%
0.0%
0.0%
0.0%%
0.0%
Double Margin
2969.9
31.5%
Double Margin &
2
2975.4
30.0%
28.5%
27. 00
23.5%
22.5%
Double Margin
Training (sec)
Method
D)
1.000
2.00
33.00)
4,00
Small CNN CIFAR, layer, fo
Double Margin &=
8/255
3058.9 8
42.5%
42.5%
42.5%
42,5%
42.5%
Double Margin
0.2
2969. 9
35.0%
35.0%
35.0%
34.5%
34.0%
Double Margin
2975.4
30.0%
30.0%
27.5%
Double Margin
2991.7
28.0%
27.5%
27.5%
26.0%
24.0%
Table 7: CNN-Cert certified accuracies for various t versions of Double Margin computed for different l, perturbation sizes.
20

---

Under review as a conference paper at ICLR 2020
Tminnng (800)
Method
Coent 0
0.01
0.03
0.05
0.07
0.10
0.20
0.50
0.00
Small CNN MNIST, 4 layer
Nomal
185.7
5%
9.5%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
Weight Regularization
02263
99.51%
81.0%
1.0%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
Adv. Training
8873.6
100.0%
97.0%
91.0%
0.5%
0.0%
0.0%
0.0%
0.0%
0.0%
Bounded
2799448
48.51
48.5%
48.55
48,51%
48.0%
48.0%
0.0%
0.0%
0.0%
IBP
613.1
99.5%
99.5%
99.0%
98.0%
96.5%
83.0%
0.0%
0.0%
0.0%
RcLU Stabilty
660.3
97.55
40..5
0.0%
0.0%
0.0%
0.0%
L.IRS4Pruning
<=0.1 0.1
686.7
0.0%
0.0%
0.0%
9710.9
96.95
92.0%%
75.05
54
0.0%
Double Margin
$20.0
98.51%
98.5%
97.00%
96.55%
96.5%
95.0%
0.0%
0.0%
0.0%
Double Margin +1.1
545.5
98.51%
98.51%
97..5%
57.00%
96.5%
95.5%
0.0%
0.0%
0.0%
Adv. Training
8796.8
99.0%%
98.5%
91.0%%
38, 0%
0.55%
0.0%
0.0%
0.0%
0.0%
Bounded
27999.5
57.5%
77.5%
77.55 77.5%%
77.55 5%55%
77.5%
77.5%
75.0%
0.0%
0.0%
IBP
614.0
91.5%
97.51
97..0%
96.5%
96.0%
78.0%
0.0%
0.0%
ReL. Stabilty
592.6
90.0%%
59.00
12.5%
0.5%
0.0%
0.0%
0.2
684.8
EM6
89.5%
10.5%
1.0%
0.0%
0.0%
Artt-RSaPrunin
9669.4
92.05%
86,
63.59%
0.0%
0.0%
Double Margin
518.8
95.0%%
940.5%
94.00%
93.00%
92.5%
92.5%
81.3%%
0.0%
0.0%
Double Margin +L1
$16.1
51%
95.0%
95.0%%
95.00 0/%
95.0%%
93.5%
82.0%
0.0%
0.0%
Adv. Training
$7600.5
99.5%
98..5%
91.55%
38.5% 5%
1.0%
(1.0%
0.0%%
0.0%
0.0%
Bounled
27966.8
30.0%%
30.0%)
30.0%%
30.0%%
30.0%
29.5%
28.5%
25.0%
0.0%
1BP
611.2
95.3%
95.
50..5%
76.5%
39.55
0.0%
ReLU Stabiity
595.8
94.0%
90.0%
13.0%
5.00%
0.5%
0.0%
Plniig
0.3
68655
88.0%
3.0%
0.5%
0.0%
Adi--RSPrrming
9657.1
90.0%
86.58
70.5%
0%
30.5%
13.5%
0.0%
0.0%
0.0%
Double Margin
5300
90.0%%
89.096
88. 88.5%
87.39%
86 5.5
90.09
66.3%
0.0%
Double Margin +L1
$47.1
91.0%
90.5%
90.0%
89.5%
89.0%
87.5%
83.5%
68.0%
0.0%
Medium CNN MNIST, 7 Tayer
Nomaa
367.4
100%
0%
0%
0%
0%
0%
0%
IBP
100%
100%
100 %
100%
85%
0%
0%
Double Margin
0.1
100%
100%
100%
%
0%
TRP
100%
100%
100% 9
95%
809
40%
0%
Double Margin
0.2
1380.6
100%
100%
100 %6
100%
100%
100% %
90%
0%
TRP
1390
100%
100%
100% %
100%
90%
50%
08
0%
0%
Double Margin
1362.3
90%
90%
90S
90%
90%
90%
90%
80%
0%
Pooling CNNN MNIST, tayer
Normal
226.0
99.0%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
Weight Regularization
145.1
0.0%
Training
0.0%
0.0%
D%6
92.0%
64.5%
40.5%
1.0%
0.0%
ReI.U Staiity
c= 0.1
337.3
5%
87.0%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
Double Margin
1070.3
97.5%
95.05
86.099
50.0%
73.0%
55.55
0.0%
0.0%
0.0%
Adv. Training
7573.4
99.5%
98.5%
16.0%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
IBP
MIRZA
96. 0%
78.0%
63.5%
51.00 31.0%
39.0%
20.0%
0.0%
0.0%
0.0%
ReLU Stabilty
0.2
336.7
0%
90.0%
4.0%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
Double Margin
680.5
Training
97.3%
0.0%
0.0%
0.0%
TRP
305.4
0%
76.58
44.0%
33.58
0.0%
ReLU Stabilty
0.3
337.5
97.0%
88.5%
13.0%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
Double Margin
408.0
$8.0%%
88.0%
87.5%
$6.50 5/6
85.0%
81.5%
43.0%
0.5%
0.0%
1 ReRneet CNN MNIST, 4 layer
Namaa
210.1
5%
2.09%
0.0%%
0.0%%
0.0%
0.0%
0.0%
0.0%
0.0%
Weiglt Regularization
145.1
0.0%
0.0%
0.0%
0.0%
Training
7205.8
99.0%
93.5%
22.5%
0.0%
0.0%
0.0%
IBP
60012
95.5%
90.5%
87.5%
0.0%
Rel.1 Stabitty
0.1
318.4
0%
85.58
58
25.55
9.0%
1.5%
0.0%
0.0%
Double Margin
829.3
98.0%%
80.5%
77.0%
74.5%
70.0%
65.5%
0.0%
0.0%
0.0%
Adv. Training
7554.4
98. 0%
98.0%
95.0%
00.0%
9.5%
0.0%
0.0%
0.0%
0.0%
IBP
593.3
5%
62.00%
$7.0%%
52.0%
50.0%
45,00 15.0%
10.0%
0.0%
0.0%
ReLU Stabilty
0.2
317.8
93.04 0%
85.5%
67.0%%
34.5%
17.0%
2.5%
0.0%
0.0%
0.0%
Double Margin
63000
52.0%
50.5%
50.0%
0.0%
Training
7563.4
94.5%
17.0%
0.0%
0.0%
96.5%
13.5%
63.5%
57.5%
13.0%
0.0%
ReLU Stabilty
0.3
319.0
93.0%
86.0%
70.5%
40.0%
19.5%
4.5%
0.0%
0.0%
0.0%
Double Margin
6304
92.5%
77.0%
77.0%
75.5%
75.0%
74.5%
62.5%
46.0%
0.0%
Table 8: CNN-Cert certified accuracies on all MNIST networks. Adv. Training (Madry et al.
2018
Bounded (Kolter& & Wong 2018). IBP (Gowal et al. 2018), ReLU Stability (Xiao et al. 2019) (019..1. For the medium CNN architecture, accuracies are found over 20 points.
21

---

Under review as a conference paper at ICLR 2020
Training (sec)
Method
0
0.5/255
1/255
2/235
3/255
5/255
T/255
8/255
9/235
Small CNN CIFAR, layer
141.1
22.0%
1.5%
0.0%
0.0%
Weight Regularization
1062.8
58.0%
24.0%
2.5%
0.0%
0.0%
0.0%
0.0%
0.0%%
0.0%
Adv. Training
51203.7
57.5%
24.5%
1.0%
0.0%
0.0%
0.0%
0.0%
0.0%
Bounded
22351 6
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
IBP
2/255
ReLL Stubilty
409 .l
12.0%
12.0%
12.0%%
12.0%%
12.0%
12.0%
12.0%
12.0%
12.0%
Double Margin
394.5
2.5%
Adv. Training
51891.6
60.5%
25.0%
2.5%
0.0%%
0.0%
0.0%
0.0%
0.0%%
0.0%%
Bounded
21918.7
IBP
8/235
410.0
37.5%
35.0%
32.5%
20.0%
17.5%
2,5%
0.0%
0.0%
0.0%
ReLU Stabilty
396.1
12.0%
12.0%
12.0%
12.0%
12.0%
12.0%
12.0%
12.0%
12.0%
Double Margin
409.7
45.5%
45.0%
43.5%
40.5%
39.5%
28.0%
22.5%
19.5%
15.0%
Medium
CIFAR, layor
Normal
1778.3
50.0%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
Double Margin
2/255
5770.2
33.0%
25.0%
15.0%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
IBP
Double Margin
8/235
5762.2
25.0%
25.015
25.0%
25.0% %
25.0%
25.0%
20.0%
10.0%
10.0%
Pooling
CIFAR, layer
Normal
1164.9
65.0%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
Weight Regularization
828.8
0.0%
0.0%
0.0%
IBP
4112.8
52.0%
24.0%
16.0%
6.0%
4.0%
0.0%
0.0%
0.0%
0.0%
Stabiity Double Margin
2/255
1.0%
4091.4
50.5%
30.5%
23.5%
11.0%
8.0%
1.0%
0.0%
0.0%
0.0%
IBP
43.0%
15.5%
8.5%
3,0%
0.0%
0.0%
0.0%
RcE.U. Stabiiyy
8/255
1676.9
58.5%
8.5%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%%
0.0%
Margin
I-Resnet CNN CIFAR, 4 layer
4.0%
0.0%
Weight Regularization
847.3
58.0%
3.0%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
IBP
3700.3
48.5%
8.0%
6.0%
2.0%
0.0%
0.0%
0.0%
0.0%
ReLU Stabitty
2/255
1592.6
37.5%
4.0%
4.0%
4.0%
4.0%
0.0%
0.0%
0.0%
0.0%
Margin
IBP
3421.6 6
42.5%
2.5%
2.0%
1.0%
1.0%
0.0%
0.0%
0.0%
0.0%
ReI.I Suailty
8/255
1.0%
0.5%
Double Margin
3531.5
35.0%
4.0%
4.0%
4.0%
4.0%
4.0%
3,5%
3.5%
3.5%
Table 9: CNN-Cert certified accuracies on all CIFAR networks. Adv. Training (Madry et al. Bounded (Kotter& Wong 2018). IBP (Gowal al. 2018). ReLU Stability (Xiao et al. 2019) For the mediun CNN architecture, accuracies are found over 20 points.
2018
Training Time (sec)
Method
Ceart
0.01
0.03
0.05
0.07
0.10
0.20
0.30
0.40
Small CNN MNIST, layer
Double Murgin
0.2
518.8
93.44%
93.15%
92.61%
92.06%:
91.30%
89.63%
78.53%
0.00%
0.00%
Training Time (sec)
Method
0.5/255
1/255
2/255
3/255
5/255
7/255
8/255
9/255
Small CIFAR,
layer
Double Murgin
8/255
409.7
43.00%
41.71%
40.58%
37.72%:
37.25%
28 28.44%
22. 39%
19.06%
16.35%
Table 10: CNN-Cert certified accuracies computed on the entire test set.
22

---

Under review as a conference paper at ICLR 2020
Training Time (sec)
Method
Coort
0.01
0.03
0.05
0.07
0.10
0.20
0.30
0.40
Medium CNN MNIST, layer
Normal
387.4
99.0%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
IBP
1553.6
98.5%
98.5%
98.5%
98.5%
97.5%
96.5%
0.0%
0.0%
0.0%
Double Margin
0.1
1360.4
97.5%
97.5%
97.5%
97.0%
96.5%
96.5%
0.0%
0.0%
0.0%
1553.2
98.5%
Double Margin
0.2
1360.6
95.0%
95.0%
94.5%
94.5%
94.0%
93.5%
89.5%
0.0%
0.0%
IBP
1550.6
97.5%
97.5%
97.5%
97.5%
96.5%
95.5%
94.0%
90.0%
0.0%
Double Margin
1362.3
90.5%
90.5%
88.5%
87.5%
87.5%
87.0%
83.5%
79.55 79.5%
0.0%
Large CNN MNIST, 7 layer
Normal
930.6
99.09%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
IBP
4162.8
98.0%
00.0%
98.0%
98.0%
97.0%
95.0%
0.0%
0.0%
Double Margin
0.1
3742.5
98.5%
98.5%
98.0%
98.0%
98.0%
97.0%
0.0%
0.0%
0.0%
IBP
4162.33
98.3%
98.5%
98.5%
98.5%
91.5%
97.5%
93.5%
0.0%
0.0%
Double Margin
0.2
3740.2
97.0%%
IBP
4161.4
98.5%
98.0
97.5%
97.5%
97.5%
97.5%
94.5%
91.0%
0.0%
Double Margin
0.3
3739.2
93.0%
93.0%%
92.5%
92.5%
92.0%
91.0%
84.5%
0.0%
0.0%
Training Time (sec)
Method
0.5/255
1/255
2/255
3/255
5/255
7/255
8/255
9/255
Medium CNN CIFAR, 7 layer
Normal
1778.3
0.0%
0.0%
0.0%
0.0%
0.0%
IBP
2/255
6613.4
45.5%
36.5%
27.0%
11.0%
9.5%
0.0%
0.0%
0.0%
0.0%
Double Margin
5770.2
45.0%
37.0%
24.5%
10.5%
8.0%
0.5%
0.0%
0.0%
0.0%
24.5%
24.5%
23.0%
21.5%
21.5%
13.5%
12.0%
10.5%
8/255
Double Margin
5762.2
33.5%
33.0%%
32.5%
31.5%
31.5%
25.0%
18.5%
16.0%
13.5%
Large CNN CIFAR, 7 layer
Normal
4020.6
65.5%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
17260.8
33.5%
23.5%
10.0%
8.0%
0.5%
0.0%
0.0%
0.0%
Double Margin
2/255
15141.55
43.5%
33.0%%
25.5%
9,5%
9.0%
2.0%
1.0%
0.5%
0.0%
IBP
17262.3
27.0%
27.0%
26.5%
25.0%
25. 0%
23.5%
23.0%
22.5%
21.0%
Double Margin
8/255
15131.7
16.5%
15.5%
15.0%
15.0%
15.0%
14.5%
14.5%
14.5%
14.5%
Table II: Certified accuracies for large and medium CNN models computed using IBP (Gowal et al.
2018
23

---

Under review as a conference paper at ICLR 2020
K ADDITIONAL RESULTS IN REBUTTAL
K.1 COMPARING DIFFERENT CERTIFICATION METHODS
Here, we conduct experiments comparing different certification methods. Specifically, compare IBP with different variations of CNN-Cert including CNN-Cert-ReLU, CNN-Cert-Ada These bounds differ by how they bound the ReLU function for unstable ReLUs as illustrated in Figure 3 with CNN-Cert-Rel.U using parallel bounds and CNN-Cert-Ada using an adaptive lower bound. We also compare with variation of CNN-Cert using constant lower bound of zero, which we call CNN-Cert-Zero.
We note that this bound is strictly stronger than IBP as IBP uses a constant upper bound and lower bound to bound the activation function, whereas CNN-Cert-Zero uses a tighter linear upper bound and the same constant lower bound (y = 0), clearly shown in Figure 3 As result, for any fixed network, IBP yields weaker than CNN-Cert-Zero. Many certification methods in the literature are equivalent to one of these methods as illustrated in Table
output
ReLU activation
Case 1:
Case 1:
Case
Case 1: -I
-1 > u
-|> u
-1 >
u
input
Case 2:
Case 2: -I u
Case 2: I u
Case 2:
upper bound
-1 <<
u
Linear lower
bound
CNN-Cert-ReLU
CNN-Cert-Ada
CNN-Cert-Zero
IBP
Figure 3: Visualizing the bounds the ReLU function of different certification methods. Bounds illustrated for unstable ReLUs where the input bounds I, u satisfy I < 0 and u > O. Bounds for two cases are illustrated: -1 > and 2) -1 < u. The linear upper bounds of the ReLU function are shown in blue, and the lower bounds shown in orange.
Certification method
Equivalents
Convex Outer Bounds (Kolter & Wong
2018
CNN-Cert-Red
Fast-Lin
(Weng ct al.
2018
Zonotope
Singh al.
2018
Neurify
Wang et al.
2018
CROWN
Zhang al. 2018)
CNN-Cert-Ada
DeepPoly
Singh et al.
2019)
CNN-Cert-Zero
Box (Mirman et al.
2018
IBP
Naive Layer-wise Bounds (Koteer & Wong 2018
Table 12: Equivalent certification methods to different variants of CNN-Cert and IBP
Tables B
14 15 16 show certified accuracies using the different certification methods. We find
that CNN Cert-Ree Re and CNN-Cert-Ada generally yield the highest accuracies for most networks. Using these certifiers, Double Margin generally yields higher certified accuracies than other methods.
24

---

Under review as a conference paper at ICLR 2020
However, for models trained on IBP, IBP certified accuracies much higher than those of CNN- Cert-ReLU and CNN-Cert-Are Ada, outperforming Double Margin. The high performance of IBP trained models under IBP certification is most likely because the they specifically trained to enhance certified performance under interval bounds. This is line with the observation that training with loss function targeted towards specific certifier yields especially high performance under that certifier Kolter& & Wong 2018 Raghunathan et al. [0188] Dvijotham et al. [01 Sap. Nevertheless, we find that the CNN-Cert- certifier yields higher equal accuracies IBP certification over all networks.
Method (200 points)
Ceort
0.01
0.03
0.05
0.07
0.10
0.20
0.30
0.40
Small CNN MNIST. layer
Normal
99.5%
15.5%
0.0%
0.0%
Weight Regularization
99.5%
88.5%
2.0%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
Ady. Training
98.5%
96.5% %
0.00%
0.0%
0.0%
0.0%
0.0%
0.00%
0100%
95.5%
95.5%
95.0%
92.5%
87.0%
68 68.0%
9.5%
0.0%
0.0%
ReLU Stabilty
0.3
94.0%
90.0%
65.0%
23.0%
5.0%
0.5%
0.0%
0.0%
0.0%
Pruning
95.0%
88.0%
53.5%
13.5%
3.0%
0.5%
0.0%
0.0%
0.0%
Double Margin
91.5%
91.0%
90.5%
90.0%%
88.5%
87.0 %
77.0%
67.0%
0.0%
Method (200 points)
Seort
0.5/255
1/255
2/255
3/255
5/255
7/255
8/255
9/255
Small CNN CIFAR, layer
Normal
53.5%
28.5%
5.5%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
Weight Regularization
60.5%
26.5%
3,5%
0.0%%
0.0%
0.0%
0.0%
0.0%
0.00%
Adv. Training
57.0%
27.0%
3.0%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
8/255
%
41.5%
35.5%
18.55
5.5%
Double Margin
41.0%
40.0%
39.0%
36.0%
35.5%
29.0%
21.5%
19.0%
16.0%
Table 13: CNN-Cert-Ada certified accuracies for Comparing different certification methods.
Method (200 points)
Geort
0.01
0.03
0.05
0.07
0.10
0.20
0.30
0.40
Small CNN MNIST, layer
Normal
99.5%
5.5%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
Weight Regularization
99.5%
81.0%
1.0%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
Adv. Training
98.5
95.5%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
IBP
95.5%
95.5% %
95.5%
93.5%
85.0%
45.5%
0.0%
0.0%
0.0%
Stabilty
0.3
23.0%
5.0%
Pr+ning
95.09
88.0%
53.5%
13.5%
3.0%
0.5%
0.0%
0.0%
0.0%
Double Margin
91.5%
91.0%
90.5%
90.0%
88.0%
87.0%
77.5%
66.0%
0.0%
Method (200 points)
Scort
0.5/255
1/255
2/255
3/255
5/ 5/255
7/255
8/255
9/255
Small CNN CIFAR,
layer
Normal
60.5%
23.5%
2.0%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
Weight Regularization
57.0%
24.0%
1.5%
0.0%%
0.0%
0.0%
0.0%
0.0%
0.00%
Adv. Training
53.5%
25.0%
4.5%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
8/255
47.5 %
44.5%
41.5%
35.0%%
16.5%
4.5%
3.0%
Double Margin
41.0%
40.0%
39.0%
36.0%
35.5%
29.5%
20.0%
17.5%
15.0%
Table 14: CNN-Cert-ReLU certified accuracies for Comparing different certification methods.
25

---

Under review as a conference paper at ICLR 2020
Method (200 points)
0.01
0.03
0.05
0.07
0.10
0.20
0.30
0.40
Small CNN MNIST,
layer
Normal
99.5%
11.5%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
Weight Regularization
99.5%8
85.0%
1.0%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
Adv. Training
98.5%
95.5%
0.0%%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
IBP
95.5%
95.5%
95.5%
95.5%
95.5%
95.5%
93.5%
86.5%
0.0%
ReLU Stabilty
0.3
90.0%
23.0%
5.0%
0.0%
LI+RS+Pruning
95.0%
87.5%
53.5%
13.0%
3.0%
0.5%
0.0%
0.0%
0.0%
Double Margin
91.5%
91.0%
90.5%
90.5%
88.5%
97.0%
82.0%
75.5%
0.0%
Method (200 points)
Ceort
0.5/255
1/255
2/225
3/255
5/255
7/255
8/255
9/ 9/255
Small CNN CIFAR, 4 layer
Normal
53.5%
23.0%
3.5%
0.0%
0.0%
0.0%
0.0%
Weight Regularization
60.5%
15.5%
1.5%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
Ady. Training
57.0%
20.0%
0.0%%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
8/255
47.5
44.5%
41.5%
36.5%
36.0%
26.0 %
19.5%
17.5%
14.5%
Double Murgin
41.0%
40.0%
39.5%
36.5%
35.5%
30.5%
25.0%
21.0%
19.5%
Table 15: certified accuracies for Comparing different certification methods.
Method (200 points)
Coart
0.01
0.03
0.05
0.07
0.10
0.20
0.30
0.40
Small CNN MNIST,
layer
Normal
99.5%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
Weight Regularization
99.5%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
Adv. Training
98.5
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
IBP
95.5%
95.5%
95.5%
95.5%
95.5%
95.5%
93.5%
86.5%
0.0%
Stabilty
0.3
33.0%
0.0%
0.0%
0.0%
L1+RS+Pruning
95.0%
44.0%
0.5%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
Double Margin
91.5%
91.0%
90.5%
90.5%
88.5%
87.0%
81 1.0%
75.5%
0.0%
Method (200 points)
Scort
0.5/255
1/255
2/255
3/255
5/255
7/255
8/255
9/255
Small CNN CIFAR, 4 layer
Normal
53.5%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
Weight Regularization
60.5%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
Adv. Training
$7.0 %
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
0.0%
8/255
47.5%
44.5%
41.5%
36.0%
36.0%
25.5
18.5%
16.5%
14.0%
Double Margin
41.0%
40.0%
39.09:
35.0%
35.0%
29.5%
20.5%
18.5%
16.5%
Table 16: IBP certified accuracies for Comparing different certification methods.
26


Reviews:
[{"review_id": "rygwJPQ0FH", "reviewer": "AnonReviewer1", "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 authors first demonstrate that many existing approaches are special cases of regularized objectives, and then provide a theoretical analysis on the relationship between the local minima of the original loss and the corresponding regularized loss.  Afterwards, the authors propose a new regularizer inspired by the IBP regularizer by taking account of second order information. Through a large set of experiments the authors demonstrate that their approach achieves higher certified accuracy using CNN-Cert, compared to many previous approaches.\n\nI have some concerns on the writing and experiments of this paper. \n\n- The paper seems to have two parts that are isolated from each other. The first part of this paper discusses some theoretical analyses on the relationship of local minima for regularized and unregularized losses. The second part of this paper proposes the DoubleMargin regularizer. However, I can't see why the theoretical analysis motivates the DoubleMargin regularizer. The only statement that tries to relate theoretical analyses and the proposal is \"the gradient of a regularizer rather than its bound validity determines its certified test loss. Therefore ... using an upper bound on the adversarial loss is not necessary to train certifiable models\". This is a super general and vague motivation, and is not specialized to the DoubleMargin regularizer. The argument can actually be used for justifying arbitrary regularizers...\n\n- Since the advantage of DoubleMargin is not motivated theoretically, the empirical performance becomes critical. However, I don't think the experiments are rigorous and the comparisons are fair. In Table 2 only certified accuracies from CNN-Cert are reported. However, CNN-Cert does not work well for models trained by IBP. For fair comparison, the authors should report the best result from a group of certification methods. The certified results of IBP using CNN-Cert seem to be much worse than the results reported in the original IBP paper (Gowal et al., 2018) , which were verified using IBP. In fact, in both table 4 and table 12, the authors show results that the IBP method outperforms the DoubleMargin approach when results are verified by IBP. ", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "Hkx64BnJ5r", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 1, "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": "At a first glance, this paper proposed an interesting refinement of interval bound propagation (IBP). However, it has a major flaw in empirical evaluation, and the proposed \"theory\" and \"bounds\" are also questionable and have many issues.\n\nIn short, the main results of the paper in Figure 1 and Table 2 are problematic and not the right comparison, so they cannot justify the claim that the proposed method outperforms other state-of-the-art baselines like IBP.  Specifically, when comparing to IBP, the certified error should be computed by IBP; however the verification algorithm used in this paper performs extremely poor on IBP based models (giving vacuous bounds like 0%, and the authors are able to outperform this 0%).  Under fair comparison metrics (Table 12), the proposed method is worse than the IBP baseline in almost all settings. I will explain the reason the proposed method does not work in detail below.\n\nBesides the empirical results, the \"theory\" developed in this paper also has several fundamental weakness (will discuss in detail below) and are lack of solid connections to robustness and the proposed \"bounds\"; the proposed \"bounds\" are questionable and are not sound bounds, and they can hardly be justified theoretically; so it is not surprising that they cannot outperform IBP, which is based on rigorous minimax robust optimization and sound over-approximations of neural networks.\n\nOn the positive side, the authors considered the ensemble of multiple IBP trained models, as well as extending IBP to L0 norm setting. Both of them are valid (but small) contributions, but they are not sufficient. Also, overall the writing of the paper is great and easy to follow and understand.\n\nI really do not want to make the authors of this paper upset, especially, the main author might be the first time submitting a paper to ICLR or a undergraduate student new to this field. However I have to say this paper has significant flaws and should not be published. Especially, the wrong evaluation methodology used in this paper can be very misleading for new comers to this field, and misguide future research.\n\nI encourage the authors to read my detailed comments below and learn from the failure of the proposed method. If the authors can rephrase this paper significantly (especially, removing the entire section 3), and emphasize on the contributions of ensemble or L0 perturbation, it might become a good paper for a next venue. My suggestions for improvements are below:\n\n1. Be honest with your findings and do not try to hide the weakness of your method, and do not overclaim. Especially, the authors are aware of the problem that IBP based models are better if evaluated under IBP bounds (in Table 12), but still make strong and wrong claims that the proposed method outperforms other state-of-the-art methods in certified accuracy in Introduction.\n\n2. For the ensemble part, consider more \"smart\" ensembles rather than directly adding them together. For example, we can consider balancing the accuracy and certified error of each model and choose a blend of them. IBP is a strong method, and an ensemble of IBP can yield the best defense.\n\n3. For the L0 robustness with IBP, it is not a significant contribution alone since it only converts the L0 norm to interval bounds at the very first layer.  However the authors can consider more interesting settings, like adversarial patches or masks (https://arxiv.org/pdf/1712.09665.pdf), which can be dealt with similar techniques.\n\n4. When evaluating a certified defense method, it is also good to conduct PGD attacks to the networks, to see how tight the certified bounds are.  If the authors attack the models in Table 1, we can actually see that IBP based models can perform much better than the proposed method. From this, the authors should have realized that the verification method they used is not appropriate to evaluating IBP.\n\n5. Evaluation on only 200 test data points is not sufficient. Certified accuracy is computed on the entire test set (10,000 examples) in almost all previous certified defense papers (Wong et al., 2018; Mirman et al., 2018; Gowal et al., 2018; Wang et al., 2018). The authors should use a proper implementation of verification algorithm, like DiffAI (https://github.com/eth-sri/diffai), convex adversarial polytope (https://github.com/locuslab/convex_adversarial) or symbolic interval (https://github.com/tcwangshiqi-columbia/symbolic_interval). In my experience, on a single GPU they can verify small models over entire dataset (10,000 examples) within a few minutes; large models may take a few hours, but still quite reasonable. The verification method used in this paper is lesser-known and was probably implemented poorly and inefficiently. It is better to use a mature and well accepted library.\n\n6. A Minor issue: the first paper that proposed IBP training is Mirman et al., ICML 2018 (where the \"box\" domain was used for training), not Gowal et al. 2018. So some sentences in Introduction and Related works are not accurate.\n\n\nNow let's discuss the issues in this paper in detail, and let's focus on the empirical comparisons to IBP first.\n\nThe authors made the main claim based on Table 2 and Figure 1, where the \"certified accuracy\" (or most commonly referred to as \"verified accuracy\") for models trained using the proposed method seems to be higher than other methods, especially IBP. \"Certified accuracy\" is a lower bound of accuracy under any norm bounded perturbations (given a certain epsilon). Conversely, attack based methods like PGD give an upper bound, as there can be stronger attacks that further decrease accuracy.\n\nThere are many neural network verification methods to obtain certified accuracy; some of them can be particularly weak on certain models (giving vacuous lower bounds like 0%).  Generally, you choose the best possible (and computationally feasible) verification method to verify the robustness of a model. For example, if verification algorithm A gives a certified accuracy of 10%, but algorithm B gives 90% for the same model, we should use 90%. As an analogy in the adversarial attack setting, you pick the strongest possible attack to evaluate robustness: a model has high accuracy under weak FGSM attacks is not necessarily robust; conversely, a model has low certified accuracy (even 0%) does not necessarily mean it is vulnerable, as the verification method can be particularly weak on this model.\n\nIn the original IBP training paper (Gowal et al., 2018), the certified error is computed efficiently using IBP, and the error is about 8% for MNIST (epsilon=0.3), and 68% for CIFAR (epsilon=8/255).  My first hand experience on IBP can confirm that it is very easy (without too much tuning effort) to get 10% certified error for MNIST and 73-75% for CIFAR, even using small models.  These numbers translate to 90% certified accuracy on MNIST (eps=0.3) and 25-27% certified accuracy on CIFAR (eps=8/255). However, in Table 2 and Figure 1 of the paper the authors show 0% (!) certified accuracy for IBP trained models for both MNIST eps=0.3 and CIFAR eps=8/255, and their method outperforms this 0%.\n\nUnfortunately, the verification method (\"cnncert\") used in this paper performs extremely poor on IBP trained models (giving vacuous bounds like 0%); IBP trained models should be certified using IBP bounds to give non-vacuous results.  What Table 2 and Figure 1 really show is the weakness of their verification method used, rather than the true robustness of the model. What we really want to show here is how robust the models are, not how good a verification method is, so we need to use the best possible verification method; for IBP trained models, using IBP for verification is almost mandatory since it not only gives tight bounds but is also much more efficient.\n\nThe authors are aware of this problem - in appendix, Table 12 (a table never discussed anywhere), they listed IBP certified error for IBP trained models.  The MNIST numbers for IBP trained models are close to those on IBP paper (90% at eps=0.3), significantly better than their method in Table 2 (68%) or Table 12 (79%). The CIFAR numbers for IBP (22.5% certified accuracy at 8/255 in Table 12) are apparently de-tuned (in my experience IBP can easily do at least 25%, and Gowal et al. reported 32%), yet it is still better than the proposed method (less than 20% in Table 2 and 12).  So under the right metrics (IBP trained models certified using IBP), even if the IBP models are detuned, they can outperform the proposed method by a large margin. The proposed method only makes IBP worse under the right metrics.\n\n\n\nNow let's understand why the proposed method cannot improve IBP. The bounds themselves have a few issues:\n\n1. The \"s\" bound is not a sound bound for interval analysis anymore, because it uses the wrong center z_nom (the correct center is (l+u)/2 if you propagate the \"center\" and \"difference\" along the network, as an alternative implementation of IBP). The author claims that it is fine since we don't need sound bounds thanks to their \"theory\", however the \"theory\" itself is implausible, as will explained below. Although this tampered \"s\" bounds may empirically help to improve robustness, it is not theoretically sound; training a sound bound helps to obtain better certified accuracy.\n\n2. The \"v\" bound is claimed to capture second derivative of activation function. However, first of all, for ReLU the second order derivative does not exist at all. The author also argue that \"v\" is a finite difference based bound, however it is also not accurate since when the bounds propagate to later layers both \"s\" and \"v\" can become large, and this can be a very bad \"finite difference\".\n\n3. I do agree \"v\" somewhat regularizes linearity (assuming the \"finite difference\" is partially working). However, linearity does not guaranteed to produces good robustness, nor it is necessary. In fact, we should not impose unnecessary regularization to neural networks, since any regularization restricts its learning power. In some papers on empirical defense, linearity sometimes can help to reduce PGD error; however in the certified setting, a direct surrogate to certifiable robustness like IBP usually produces the best results. The addition of unnecessary regularizations mostly makes results worse, unless you have a very good reason and demonstrate strong empirical evidence that it can significantly outperform the baseline. See https://arxiv.org/pdf/1807.09705.pdf for a case study on the failure of over-regularization.\n\nI think the reason the authors still get a somewhat verifiable model is that the \"s\" bound sort of propagates a bound that is not sound but carries some similarity to IBP. IBP is a strong method so even tampering it a little bit, you can still get something.  The \"v\" bound implicitly regularizes the norm of weight matrices, which helps to gain better certified accuracy only under convex relaxation based verification methods.  I believe simply IBP+L1 regularization can achieve similar results as the proposed method, under the *wrong* evaluation metric in Table 2 and Figure 1. Under the correct evaluation metric, we shouldn't add this regularization term at all as it harms performance.\n\n\n\nThe \"theory\" developed in section 3 is unconvincing and cannot support the \"bounds\". There a few problems:\n\n1. The \"theory\" does not help us to find a good regularizer. When the authors argue that the gradient needs to be close to an \"optimal\" regularizer, we don't have the optimal regularizer at hand and have no idea how to approach it. Also the inverse Hessian used for distance metric in (6) is never known, so it is impossible to say which gradient is good and which is bad.\n\n2. The assumption that lambda is close to zero is almost never true, yet Proposition 1 and 2 strongly depends on it. In the paper the authors use lambda=0.5 (and other similar numbers) and never decay it to zero. So the proposed training method cannot be supported by the \"theory\".\n\n3. The \"theory\" makes weak or no connection to robustness guarantees; (4) is a classical results for the connection between test error and global Lipschitz constant, and the connection between this bound and our goal (robust classifier under adversaries) is too general and too weak. A more direct formulation, like minimax robust optimization will be a much better surrogate.\n\n4. The connection between the theory and the proposed bounds is vague; the authors claim \"the gradient of a regularizer rather than its bound validity determines certified test loss\", and under this sense, I can use any arbitrarily loss function and call it a \"regularizer\". For example, I can use a \"regularizer\" that encourages BAD robustness, and it still fits into the authors explanation. This is like someone publishes a proof showing that P=NP, yet you can use the same argument to show P != NP. This is embarrassing.\n\nThe bottom line: I am not saying the propositions in this paper are technically wrong (under the strong assumptions the authors proposed); at least their derivations are straightforward and simple enough to check within a few minutes. However, they are too weak to guide us to find a good training method, too far-fetched to our goal of obtaining good robustness guarantee, and too general that you can use them to prove both sides. So I don't think the \"theory\" is useful, and the proposed \"bounds\" guided by the theory has also failed to improve the baseline.\n\nSorry for the long comments and I hope they can be helpful for the authors.\n\n****** Reply to general author response:\n\nThe comparison in the \"certifier\" table is misleading. \"CNN-Cert-Zero\" seems to be a special case of CROWN, with a special setting of lower bounds for ReLU. CROWN allows any slope between 0 to 1 as the lower bound, and \"CNN-Cert-Zero\" is just a special case of that.\n\nMost importantly, the main issue with the paper is not the verifier used; the main issue is that the proposed method performs worse than baseline under correct evaluation, and the proposed \"theory\" is distracting or wrong.\n\nThe new empirical results still do not address any of my concerns - IBP still significantly outperforms the proposed method. For MNIST, Gowal et al. reported over 90% verified accuracy (the proposed method is 75%); the IBP results provided in author response has 0% verified accuracy at , which seems to be a problem or bug. For the CIFAR=8/255 case, the authors keep detuning IBP models and obtain an IBP baseline with less than 20% verified accuracy, yet the IBP model reported in literature (Gowal et al., 2018) can perform over 30%. The proposed method only performs around 20% and the performance gap is huge.\n\n\n****** Conclusions after author response\n\nAfter reading the author response, I am still keep my score of reject since the paper contains major technical errors. In a word, the theory is distracting or wrong, and the empirical results provided are intentionally misleading (the proposed method cannot outperform baseline under the right evaluation metrics).\n\nThe author response does not address any of my concerns raised, yet the authors insisted that their \"theory\" is useful (which is apparently not true according to all reviewers) and provided more confusing and misleading results. I have written a long review with detailed reasons and hope the authors can understand why the proposed method fails, but it seems they completely ignored it and did not learn anything from it.\n\nThis is quite disappointing.\n\n\n ", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "B1gnQjh5KH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 1, "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": "Summary: This paper studies the problem of certified robustness to adversarial examples and proposes a new training method to obtain better certified robustness. This new method is based on using a double margin regularizer. \n\nDecision: I vot for rejecting this paper. I think the paper studies an important problem. However, I find some serious flaws in the experiments and also do not find the motivation and proposed idea convincing, Detailed under: \n\nExperimental concerns:\n— Evaluating on 200 examples seems very small. Most papers consider at least 1000 examples. \n— The paper compares all models based on *one* certified procedure. This is an incorrect comparison. Some certification procedures work better on some networks over another, and this does not reflect onthe actual robustness of the network. For example, ReLU stability paper reports 80% certified accuracy at \\eps = 0.3, but this paper reports 0% (possibly due to weaker attack). While some certification methods are generally weak, it’s not necessary that they are uniformly weaker by the same amount on all networks. Hence this is an incorrect comparison. \n— Even if we use the results reported on the one certification method (ignoring the flaw above), the results only show in most settings that the double margin method ends up with a different point on the accuracy-robustness tradeoff. It’s not clear why this tradeoff is better.\n\n\nConcerns with the motivation and paper overall: \n— Paper seems to emphasize the “unified” perspective of certified training and regularization. I find this unification very natural and not particularly novel/insightful. It’s just a restatement of the objective. \n— I haven’t verified the correctness of the propositions inthe paper. However, just the statement confuses me. \\lambda -> 0 is the regime where we don’t care about robustness and only care about test accuracy. Why is this even interesting or relevant?\n— Finally, unfortunately while it looks interesting, I don’t understand the motivation behind the double margin method. This doesn’t seem to follow from rest of the paper. The authors mention below eq(9) that the gradient of the regularizer is the important term. Even if this is true, why does the double margin have a “better” gradient?\n\nIn light of the experimental concerns and generally weak motivation/description of the proposed regularizer, i vote for rejecting the current version. ", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies the problem of certified robustness to adversarial examples. It first demonstrates that many existing certified defenses can be viewed under a unified framework of regularization. Then, it proposes a new double margin-based regularizer to obtain better certified robustness.  Overall, it has major technical issues and the rebuttal is not satisfying.
Decision: Reject