Title: DOUBLEMARGIN: EFFICIENT TRAINING OF ROBUST AND VERIFIABLE NEURAL NETWORKS

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 0 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.

1. 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 human-imperceptible perturbations to 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 p norm for p ∈ {0, 1, 2, ∞} (Papernot et al., 2016; Carlini & Wagner, 2017; Athalye & Sutskever, 2017; Su et al., 2019; Xu et al., 2018; Chen et al., 2018) . 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 easily bypassed by stronger adversaries (Athalye et al., 2018) . The work Madry et al. (2018) proposed a stronger defense method, adversarial training, which minimizes the worst-case training loss under adversarial perturbations. However, it is restricted to a specific type of adversarial perturbations and not generalized to other types of perturbations (Tramèr & Boneh, 2019) .

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 arbitrary perturbation within a certain p ball region (Katz et al., 2017; Cheng et al., 2017; Carlini et al., 2017; Kolter & Wong, 2018; Raghunathan et al., 2018; Weng et al., 2018; Zhang et al., 2018; Boopathy et al., 2019; Dvijotham et al., 2018b; Wong et al., 2018; Xiao et al., 2019; Gowal et al., 2018; Mirman et al., 2018; Dvijotham et al., 2018a) . 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., 2018; Weng et al., 2018; Zhang et al., 2018; Boopathy et al., 2019; Dvijotham et al., 2018b; Wong et al., 2018) . Here the former 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 be accelerated by imposing weight sparsity and activation stability (so-called ReLU stability) on 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:

• We develop a 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 state-of-the-art certification based training methods. In particular, we demonstrate up to a 55% increase in certified accuracy at = 0.2 on MNIST, up to a 20.5% increase at = 2/255 on CIFAR, and up to a 24% increase at = 8/255 on 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 0 threat model and model ensembles. We demonstrate empirically that our 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 a norm-bounded threat model, finding the minimum adversarial distortion exactly is an NPcomplete 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-specific certification method, it is possible to find non-trivial bounds for fully connected ReLU networks (Kolter & Wong, 2018; Weng et al., 2018; Wang et al., 2018) , as well as networks with general activation functions (Zhang et al., 2018) and architectures (Singh et al., 2018 ). An "any-time" certifier has also been developed that allows for a trade-off between certification time and bound quality (Dvijotham et al., 2018b) .

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 et al., 2018) . However, adversarial training is not targeted towards verification or certification methods, and we therefore do not consider it a certified defense. One step towards certified defenses is natural regularization such as sparsity-inducing 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 are 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., 2018) and has surprisingly become the state-of-the-art 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 an efficient certified defense that has similar computation overhead as IBP-based defense (Gowal et al., 2018) while yielding better performance than existing methods.

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 (x) with input x where the first layer of the network z 0 is set to x. Given weights W i , biases b i and an activation function σ, for i = 0, . . . , n -1, subsequent layers are defined as:

EQUATION

) with f (x) = z n . 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 x nom is perturbed by perturbation δ to produce a perturbed input x = x nom + δ, where ||δ|| p ≤ and || • || p represents an p norm. Suppose the correct classification is given by c. Then the minimum distortion * is the minimal ∈ R + satisfying:

max j =c z n j -z n c > 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 et al., 2018) which bounds each layer in a network with a 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-wise bounds where l i ≤ z i ≤ u i , the next layer's bounds are found as:

EQUATION

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) .

Linear Bounding Framework Certified bounds can also be found using a linear bounding framework as first proposed in Fast-Lin (Weng et al., 2018) and later in the Neurify (Wang et al., 2018) and DeepZ (Singh et al., 2018) frameworks. This approach typically finds tighter bounds on minimum distortion than IBP. This framework bounds each activation layer σ(z i ) as follows:

α i z i + β i L ≤ σ(z i ) ≤ α i z i + β i U

, where α i represents the slopes of linear bounds on the activation and β i L ,β i U representing intercepts of linear bounds on the activation. When σ is ReLU activation, Fast-Lin sets the coefficients to be:

α i j = z i u,j z i u,j -z i l,j , β i L,j = 0, β i U,j = - z i u,j z i l,j z i u,j -z i l,j

, if the neuron j is uncertain, meaning z i l,j < 0, z i u,j > 0 and z i l,j ≤ z i j ≤ z i u,j . When both bounds are positive or negative, the bound on the activation is exactly the linear component on the corresponding side (i.e. when z i l,j > 0 for example, α i j =1, β i L,j = β i U,j = 0). Using these layer-wise bounds, Fast-Lin finds a pair of linear bounds on the network:

Ax + b L ≤ f (x) ≤ Ax + b U .

Then Fast-Lin bounds the network output over all possible adversarial distortion measured byp ball by:

Ax nom + b L -||A|| :,q ≤ f (x) ≤ Ax nom + b U + ||A|| :,q ,

where || • || :,q denotes a row-wise q 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 to analyze the output layer. Because Fast-Lin finds linear bounds on the network as an intermediate step to finding output bounds z u , z l , the bounds are tighter than the corresponding IBP bounds u, l. Fast-Lin is equivalent to using convex outer bounds to 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 α i in CROWN (Zhang et al., 2018) , and has been extended to general network architectures in CNN-Cert (Boopathy et al., 2019) .

3. UNIFIED FRAMEWORK OF CERTIFIED DEFENSE:

We propose a unified framework of certified defense under which many common certified defenses can be viewed as regularizations of a particular form. We first use our framework to provide analysis of (Xiao et al., 2019) E[i tanh(1 + u i l i )] ×1 Interval Bounds Propagation (Gowal et al., 2018 )

Training Method R(θ) Training cost 2 Regularization i ||W i || 2 F or i ||W i || F ×1 1 Regularization i ||W i || op,∞ or i ||W i || op,∞ ×1 ReLU Stability Loss

E[L + (u n ) + L -(l n ) -L(z n )] ×3 TRADES (Zhang et al., 2019) E[max δ:||δ||p≤ g(f (x nom + δ), f (x nom ))]

> 10 (empirically) Convex Outer Bounds (Kolter & Wong, 2018 )

E[L + (u n c ) + L -(l n c ) -L(z n )] > 100 (empirically)

MMR (Croce et al., 2019 ) general certified defenses. Under this framework, we 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, we consider it as our main baseline and highlight our method's advantages. Finally, we discuss extensions of our regularization.

E[max(0, 1 -dB γB ) + max(0, 1 -dD γD )] > 10000 (empirically) Double Margin E[L + (z n + s n + v n ) + L -(z n -s n -v n ) -L(z n )] ×3

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 a standard loss function. Given model parameters θ, a loss function L(θ) and a regularizer R(θ), the total regularized loss with a regularization parameter λ is given by: L(θ) + λR(θ)

Note that we denote a model's parameters in general as θ, and we use calligraphic symbols to denote functions of 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 i ||W i || l with l being some matrix norm. In fact, many certification-based robust training methods can also be viewed as different regularizations R(θ) as seen in Table 1 . Therefore, both standard regularizations and many robust training methods can be viewed under a unified framework. Training methods can be designed by selecting a particular regularizer according to the designer's objective.

Regularizer Construction Certified defenses such as IBP construct a regularizer by using bounds on the last layer of the network u n and l n to find an upper bound on the adversarial loss. Suppose a standard loss function L(θ) of model parameters θ is defined as a function of the last layer of the network

z n : L(θ) = E[L(z n )],

where the expectation is taken over the training set. For many loss functions L, including softmax cross-entropy loss and squared loss, it is possible to decompose the loss into an increasing and decreasing component:

EQUATION

where L + (z n ) increases element-wise with z n and L -(z n ) decreases element-wise with z n . For example in the case of softmax cross-entropy loss:

L(z n ) = -y T log (e z n /(1 T e z n )) = log 1 T e z n -y T z n ,

where e x is element-wise exponential function and y are one-hot encoded labels, the first term can be mapped to L + (z n ) while the second corresponds to L -(z n ) in (3). IBP then constructs the following regularizer: R(θ

) = E[L + (u n ) + L -(l n ) -L(z n nom )]

, where u n and l n are defined by (2) and z n nom is the value of layer z n with unperturbed input x nom . When this regularizer is added to the standard loss function L(θ) computed with unperturbed input x nom , the resulting quantity L(θ) + R(θ) is an upper bound on the adversarial loss since:

L(z n nom )+(L + (u n )+L -(l n )-L(z n nom )) ≥ L(z n )

, where z n is a function of perturbed input x, obtained by monotonicity of L + and L -and l n ≤ z n ≤ u n . Note that the adversarial loss L(z n ) is unknown, but the upper bound constructed here depends only on the IBP bounds u n and l n which are known. Typically, the model is trained with objective L(θ) + λR(θ) with λ < 1 instead of λ = 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 a particular robustness or generalization objective. As shown previously, adding a robust training regularizer such as IBP is equivalent to minimizing an upper bound on the adversarial loss: 1 m i max x:||x-xi||p≤ L(f (x)) ≤ L(θ) + λR(θ), for sufficiently large λ where there are m points x i in the training set. Similarly 1 and 2 regularization can be seen as minimizing a probabilistic upper bound on the test set loss: L test (θ) ≤ L(θ) + λR(θ). This is because many generalization error bounds (Bartlett & Mendelson, 2002; Neyshabur et al., 2015) are statements of the following form: with high probability, 4.

EQUATION

Proposition 1. Given a classifier with parameters θ and loss L(θ) with a local minimum θ, then for λ near 0, the local minimum of L(θ) + λR(θ) is approximately:

EQUATION

where H(L( θ)) is the Hessian of the loss at the original local minimum θ.

This statement provides a method of relating a regularizer to its effect on the classifier. Please refer to Appendix E for the proof and additional intuition.

Proposition 2. Given a classifier with parameters θ and loss L(θ) with a local minimum θ. For λ near 0, suppose θ * is the corresponding local minimum of a regularized loss L(θ) + λR 1 (θ). Then, for λ near 0, L(θ * ) + λR 2 (θ * ) < L( θ) + λR 2 ( θ) if and only if:

EQUATION

where

||a|| B = √ a T 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 R 2 (θ * ) 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:

Double Margin: Motivation and Rationale IBP is 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 in the network. Different from IBP that bounds the input of each layer z through u and l in (2), we introduce double margins s and v such that [z nom -sv, z nom + s + v] represents the approximate range of values each layer z can take, where z nom represents the value of the layer for unperturbed input x nom . In the similar spirit of IBP, we define the s 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 u and l.

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 to achieve tight bounds. However, using the s 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 margin has the property that when the network is locally linear in the sense that σ(z i j ) ≈ az i j + b for some a, b at all layers i, all margins v i ≈ 0. 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 C Figure 2 for a visual illustration). The inclusion of the v margin is the key qualitative difference between our approach and IBP. Because our approach explicitly penalizes non-linearity, it results in tighter certification and therefore more certifiable networks compared to IBP.

Double Margin: Formal Definition Assuming a known p perturbation size , our margins s i and v i at layer i have the same dimensionality as z i , whether they are vectors in fully connected layers or tensors in convolutional layers. Only the margins at the second layer depend on p.

These margins are initialized as: s 0 = 1, v 0 = 0. For i = 0, . . . , n -1, subsequent layer margins are defined as:

s i+1 = 1 2 |W i+1 | σ(z i nom + s i ) -σ(z i nom -s i ) (7) v i+1 = 1 2 |W i+1 | σ(z i nom + v i ) -σ(z i nom -v i ) (8) + 1 2 |W i+1 ||σ(z i nom + s i + v i ) + σ(z i nom -s i -v i ) -2σ(z i nom )|

For general p norms p = ∞, the second layer margins are modified so that s 1 is exactly half the range of values z 1 can take. To motivate the form of Equation ( 7), note that IBP can be reparameterized in terms of the half bound gap h = (u -l)/2 and bound average m = (u + l)/2. Then the half bound gap h is propagated as:

h i+1 = 1 2 |W i+1 |(σ(m i + h i ) -σ(m i -h i ))

The s margin is propagated similarly, with the difference being that IBP uses (u i + l i )/2 instead of z i 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 i . Specifically, note that given a 2nd order Taylor expansion of σ(•) at a specific scalar point x 0 , σ(x -x 0 ) ≈ 1 2 a(x -x 0 ) 2 + b(x -x 0 ) + c, then the second derivative of σ(•) at x 0 is given by: σ

(x 0 ) = a ≈ 1 γ 2 (σ(x 0 + γ) + σ(x 0 -γ) -2σ(x 0 ))

, where γ > 0 is small. Applying this approximation to the second term in Equation ( 8):

1 2 |W i+1 ||σ(z i nom + s i + v i ) + σ(z i nom -s i -v i ) -2σ(z i )| ≈ 1 2 |W i+1 ||σ (z i nom ) (s i + v i ) 2 |,

where all operators are applied element-wise. By approximating the second derivative of the activation, this term penalizes a level of non-linearity. To motivate our use of a 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. 1 in Moosavi-Dezfooli et al.

(2018) for a similar justification. Because we add two additional margins s and v in addition to the original network, we call our method double margin. Although the margins are defined for a fully connected network, the margins can be computed analogously for special cases or extensions such as convolutional neural networks or residual networks. Our regularizer is defined implicitly as a function of the model parameters θ:

EQUATION

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 1 for the full procedure. Note that using a value of λ = 0 corresponds to standard training while using λ = 1 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 a warm-up period where λ = 0 first, then linearly increases λ until it reaches λ = 0.5. Note that the value of λ is separate from the value of used during training which parameterizes the regularizer R(θ). A value of = 0 also corresponds to regular training, and higher values of correspond to defending against larger perturbation attacks. In addition to increasing λ during training, robust training methods also typically increase during training. IBP uses a piece-wise linear schedule for with warm-up and ramp-up periods coinciding with the schedule for λ. We use a similar piece-wise linear schedule as IBP.

3.3. EXTENSIONS:

We extend our method to an 0 threat model by modifying the double margin propagation at the second layer as done for general p perturbations. We also extend our method to ensembles of models trained with our regularizer. Additional details are provided in Appendix H.

4. EXPERIMENTS:

We Evaluation Although our regularizer applies to a general p threat model, we primarily conduct experiments assuming a ∞ threat model. The networks are evaluated on certified accuracy computed using CNN-Cert-ReLU, which efficiently finds a 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) (Tjeng & Tedrake, 2019) , even with using a optimization timeout as done by Gowal 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 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 I). 2 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. Table 2 provides a 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 = 0.01 and larger, and outperform IBP and Bounded for large perturbation sizes beyond = 0.07. We note that adding 1 weight regularization to our regularizer further enhances our certified accuracies. On CIFAR, our method outperforms ReLU stability based methods and adversarial training for = 1/255 and larger, and outperforms IBP and Bounded for perturbation sizes beyond = 0.5/255. On MNIST and CIFAR, we observe that due to 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 in Figure 1 . On GTSRB, our method outperforms IBP and MMR for = 3/255 and larger. Additional results on MNIST, CIFAR and GTSRB are shown in Appendix J, Tables 8, 9 and 6 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 s and v margins in Double Margin by running the following comparisons: training with only the s margin (Variation 1: 's only'), and training Double Margin with IBP bounds u, l replacing s (Variation 2: 'IBP+v'). Table 2 shows that Variation 1 performs comparably to or outperforms IBP while requiring only fewer propagation during training, supporting the intuition that the s 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 is primarily responsible for Double Margin'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 a different hyperparameter setting where λ is halved during training, reducing its final value from 1 2 to 1 4 . 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% on GTSRB) while achieving a higher clean accuracy (91.1% on MNIST and 75.6% on GTSRB). These results suggest that fine-tuning hyperparameters can improve clean accuracy to be more comparable to prior work while maintaining our better certified accuracy on large .

Extensions We find that our method's high certified accuracy extends to an 0 norm threat model. In addition, we find that using model ensembles with our method can be used to enhance certified accuracy. Results are shown in Appendix I.

5. CONCLUSION:

In this paper, we propose a unified framework of certified defense as regularization. We introduce a new efficient regularizer under this framework, and extend it to a 0 threat model and model ensembles. 

= 1 2 |W| (σ(z + s) -σ(z -s)). v is propagated as v = 1 2 |W| (σ(z + v) -σ(z -v)) + 1 2 |W||σ(z + s + v) + σ(z -s -v) -2σ(z)|.

D DOUBLE MARGIN ALGORITHM:

+ λR = λL + (z n + s n + v n ) + λL -(z n -s n -v n ) + (1 -λ)L(z n ) Compute gradients of L + λR w.r.t. W i , b i Update W i , b i via gradient descent end end

E PROOF OF PROPOSITION 1:

Proof. Suppose L(θ) + λR(θ) has local minimum θ * (λ). Note that at λ = 0, θ * = θ. Note that the derivative of the regularized loss is 0 at θ * :

∇ θ L(θ * ) + λ∇ θ R(θ * ) = 0

Differentiating both sides with respect to λ:

H(L(θ * )) d dλ θ * + ∇ θ R(θ * ) + λ d dλ ∇ θ R(θ * ) = 0 Solving for d dλ θ * : d dλ θ * = -H(L(θ * )) -1 (∇ θ R(θ * ) + λ d dλ ∇ θ R(θ * ))

Evaluating at λ = 0:

d dλ θ * | λ=0 = -H(L( θ)) -1 ∇ θ R( θ)

This implies that for small λ:

θ * ≈ θ -λH(L( θ)) -1 ∇ θ R( θ)

Intuitively, this statement indicates that for small amounts of regularization, the gradient of the regularizer is sufficient to determine the behavior of the regularizer: note that in Equation ( 5) the position of the new local minimizer only depends on 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, θ * = θ. Consider the difference between the performance of θ * and θ on regularized loss L(θ) + λR 2 (θ):

D(λ) = L( θ) + λR 2 ( θ) -L(θ * ) -λR 2 (θ * ) Taking the derivative with respect to λ: d dλ D(λ) = -∇ θ L(θ * ) T d dλ θ * -λ(∇ θ R 2 (θ * ) T d dλ θ * ) + (R 2 ( θ) -R 2 (θ * ))

Note that evaluated at λ = 0, this quantity is 0 since ∇ θ L( θ) = 0. Taking a second derivative with respect to λ:

d 2 dλ 2 D(λ) = - d dλ θ * T H(L(θ * )) d dλ θ * -∇ θ L(θ * ) T d 2 dλ 2 θ * -2∇ θ R 2 (θ * ) T d dλ θ * -λ d dλ (∇ θ R 2 (θ * ) T d dλ θ * )

Evaluating at λ = 0:

d 2 dλ 2 D(λ)| λ=0 = - d dλ θ * T | λ=0 H(L( θ)) d dλ θ * | λ=0 -2∇ θ R 2 ( θ) T d dλ θ * | λ=0 ,

since ∇ θ L( θ) = 0. Substituting the expression for d dλ θ * | λ=0 from Proposition 1:

d 2 dλ 2 D(λ)| λ=0 = -∇ θ R 1 ( θ) T H(L( θ)) -1 H(L( θ))H(L( θ)) -1 ∇ θ R 1 ( θ) + 2∇ θ R 2 ( θ) T H(L( θ)) -1 ∇ θ R 1 ( θ) Simplifying: d 2 dλ 2 D(λ)| λ=0 = -||∇ θ R 1 ( θ) -∇ θ R 2 ( θ)|| 2 H(L( θ)) -1 + ||∇ θ R 2 ( θ)|| 2 H(L( θ)) -1

Where ||a|| B = √ a T Ba. This implies that for small λ = 0, D(λ) > 0 is equivalent to the condition:

||∇ θ R 1 ( θ) -∇ θ R 2 ( θ)|| H(L( θ)) -1 < ||∇ θ R 2 ( θ)|| H(L( θ)) -1

This condition provides some guidelines on how to select a regularizer provided some "true" objective which is also a function of model parameters θ. The true objective J (θ) could, for example, be a robust generalization bound or the difference between robust validation set loss and clean training set loss. Given a standard loss function L(θ) and regularization parameter λ, the true objective can be expressed in the form of a regularization: J (θ) = L(θ) + λR J ( θ). Suppose L(θ) has minimum θ, and suppose there is a set of feasible regularizers that can be used during training of the network

{R 1 (θ), R 2 (θ), . . . , R k (θ)} with regularization coefficient λ. Then, Proposition 2 suggests selecting the regularizer R(θ) = arg min i ||∇ θ R i ( θ) -∇ θ R J ( θ)|| H(L( θ)) -1 .

Here R i ( θ) corresponds to the minimized regularizer R 1 ( θ) in Proposition 2 and R J ( θ) corresponds to the target regularizer R 2 ( θ). Intuitively, the regularizer that is closest to R J (θ) in gradient is selected. This selection of regularizer is optimal as λ approaches zero. For example, in the case of robust training, the robust training method with the closest gradient to R J (θ) is best.

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. 

H EXTENSIONS:

H.1 0 NORM THREAT MODEL

In addition to a p threat model, we can consider a 0 threat model where an input x nom is perturbed by perturbation δ to produce perturbed input x = x nom + δ where ||δ|| 0 ≤ k, where ||δ|| 0 is the number of non-zero elements in δ. This corresponds to perturbing at most k 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 as [0, 1].

In this case, our regularizer can be used directly without modification when using a large ∞ perturbation size . It is also possible to modify our regularizer at the first layer of margin propagation. At the first layer, the margin s 1 can be set exactly to one half the range of values each node can take:

s 1 j = 1 2 k l=1

rank(W 0 j,:

(1 -x nom ), l) -rank(W 0 j,: * x nom , l), assuming the input is restricted to range [0, 1], where rank(a, l) selects the lth largest element of a, and denotes element-wise multiplication. Doing so makes our regularizer more closely match the true range of values layers can take for 0 perturbations.

H.2 MODEL ENSEMBLE:

It is also possible to extend our regularizer to model ensembles. Suppose there are N models

f 1 (x), f 2 (x), ... f N (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 to yield an ensemble model:

f ensemble (x) = 1 N i f i (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 4 shows 0 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 and CIFAR respectively. We also show results for Double Margin modified for the 0 threat model trained with = 2. As illustrated, the Double Margin 0 regularizer yields certified accuracies that decay slowly with the number of perturbed dimensions . Surprisingly, we find that standard Double Margin performs better than the 0 modification for 0 certified accuracies, and moreover has consistent performance across perturbation sizes. This suggests that training methods that yield high ∞ certified performance on also transfer to yield high 0 certified performance. Intuitively, this may be because networks which are highly certifiable for low levels of ∞ perturbations have particular weight patterns such as sparsity that allow for high certification in general including for 0 perturbations. We hypothesize that this effect is particular to 0 due to the non-convexity of the 0 norm during training.

To support the reasoning that the transferability of Double Margin to a 0 threat model is unique to Similarly, for small perturbation sizes, Double Margin 2 achieves better certified accuracy than Double Margin 1 . This may be because certifiability on 2 and 1 norms incurs a stronger penalty on clean accuracy compared to the ∞ norm.

I.2 MODEL ENSEMBLE:

Table 5 shows certified accuracies for two ensemble models trained on MNIST and CIFAR, each composed of three models. The ensemble models are 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 a 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.

I.3 GTSRB:

Table 6 shows certified accuracies computed using CNN-Cert for a pureconv CNN model trained on GTSRB. Certified accuracies are 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 = 2/255, 8/255. Double Margin achieves higher certified accuracy than IBP over all tested perturbation sizes ≥ 2/255. In particular, we achieve a 24% improvement in certified accuracy for = 8/255. Double Margin also trains in less time than IBP.

I.4 MEDIUM CNN MODEL:

Tables 8 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 or outperforms IBP over most perturbation sizes, and particularly improves on IBP for large perturbation sizes ( = 0.1, 0.2, 0.3 for MNIST and = 2/255, 3/255, 5/255 for CIFAR). Table 11 : Certified accuracies for large and medium CNN models computed using IBP (Gowal et al., 2018) .

I.5 FULL TEST SET:

However, for models trained on IBP, IBP certified accuracies are much higher than those of CNN-Cert-ReLU and CNN-Cert-Ada, outperforming Double Margin. The high performance of IBP trained models under IBP certification is most likely because the they are specifically trained to enhance certified performance under interval bounds. This is in line with the observation that training with a loss function targeted towards a specific certifier yields especially high performance under that certifier (Kolter & Wong, 2018; Raghunathan et al., 2018; Dvijotham et al., 2018a) . Nevertheless, we find that the CNN-Cert-Zero certifier yields higher or equal accuracies to IBP certification over all networks. 

:



Figures and Tables:

Figure 1: 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 on MNIST and (b) on CIFAR. Refer to Table2for additional baselines including MMR and TRADES.

Double Margin Training Algorithm Data: Training data D, Randomly initialized weights and biases W i , b i , i = 1 : N , Number of epochs E, Perturbation size , Regularization weight λ Result: Trained weights and biases W i , b i for epoch = 1:E do for x nom in D do z 0 = x nom , s 0 = 1, v 0 = 0; for i = 1:N do Propagate z i+1 with Equation (1) Propagate s i+1 with Equation (7) Propagate v i+1 with Equation (8) end Construct regularized loss L

u i and l i are layer-wise bounds found using interval bounds propagation, and u i c and l i c are layer-wise bounds using convex outer bounds. denotes element-wise multiplication. || • || op,∞ denote the ∞ induced operator norm. g is a classification-calibrated loss function. d B and d D are quantities relating to lower bounds on the minimum adversarial distortion. Expectations are taken over training data. The training cost is compared to the standard training.

Table content: <table/>

where L test (θ) is the test set error, || • || is either a Frobenius or ∞ operator norm, m represents the number of training set points, and K and C are constants depending on the network architecture. It is possible to analyze the effect of general regularizations under the assumption that λ is close to zero. This corresponds to close to zero for robustness-based regularizers or m very large for generalization-based regularizers such as 1 or 2 weight regularization that can be interpreted as minimizing a generalization bound of the form in Equation

Table content: <table/>

Through comparative experiments on several model architectures, we demonstrate that our method outperforms state-of-the-art certification based training methods in terms of training time and certified accuracy.Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric P. Xing, Laurent El Ghaoui, and Michael I. Jordan.Theoretically Principled Trade-off between Robustness and Accuracy. In ICML, 2019.Huan Zhang, Tsui-Wei Weng, Pin-Yu Chen, Cho-Jui Hsieh, and Luca Daniel. Efficient neural network robustness certification with general activation functions. In NIPS, dec 2018.

Table content: <table><tr><td>Method (200 points)</td><td colspan="2">Training Time (sec)</td><td colspan="2">cert = 0</td><td>0.01</td><td>0.03</td><td>0.05</td><td>0.07</td><td>0.10</td><td>0.20</td><td>0.30</td><td>0.40</td></tr><tr><td/><td/><td/><td/><td colspan="3">Small CNN MNIST, 4 layer</td><td/><td/><td/><td/></tr><tr><td>Normal</td><td/><td>185.7</td><td/><td>98.5%</td><td>9.5%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td></tr><tr><td>Weight Regularization</td><td/><td>626.3</td><td/><td>99.5%</td><td>81.0%</td><td>1.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td></tr><tr><td>Adv. Training</td><td/><td>8760.5</td><td colspan="2">99.5%</td><td colspan="3">98.5% 91.5% 38.5%</td><td>1.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td></tr><tr><td>Bounded</td><td/><td>27966.8</td><td/><td>30.0%</td><td colspan="7">30.0% 30.0% 30.0% 30.0% 29.5% 28.5% 25.0%</td><td>0.0%</td></tr><tr><td>IBP</td><td/><td>611.2</td><td/><td>95.5%</td><td colspan="5">95.5% 95.5% 90.5% 76.5% 39.5%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td></tr><tr><td>ReLU Stabilty L1+RS+Pruning</td><td>= 0.3</td><td>595.8 686.5</td><td/><td>94.0% 95.0%</td><td colspan="3">90.0% 65.0% 23.0% 88.0% 53.5% 13.5%</td><td>5.0% 3.0%</td><td>0.5% 0.5%</td><td>0.0% 0.0%</td><td>0.0% 0.0%</td><td>0.0% 0.0%</td></tr><tr><td>Adv+RS+Pruning</td><td/><td>9657.1</td><td/><td>90.0%</td><td colspan="5">86.5% 70.5% 55.0% 30.5% 13.5%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td></tr><tr><td>Double Margin</td><td/><td>520.0</td><td/><td>90.0%</td><td colspan="7">89.0% 88.5% 88.0% 87.5% 86.5% 80.0% 66.5%</td><td>0.0%</td></tr><tr><td>Double Margin +L1</td><td/><td>547.1</td><td/><td>91.0%</td><td colspan="7">90.5% 90.0% 89.5% 89.0% 87.5% 83.5% 68.0%</td><td>0.0%</td></tr><tr><td>Method (200 points)</td><td colspan="2">Training Time (sec)</td><td colspan="9">cert = 0 0.5/255 1/255 2/255 3/255 5/255 7/255 8/255 9/255</td></tr><tr><td/><td/><td/><td/><td colspan="3">Small CNN CIFAR, 4 layer</td><td/><td/><td/><td/></tr><tr><td>Normal</td><td/><td>141.1</td><td/><td>61.5%</td><td>22.0%</td><td>1.5%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td></tr><tr><td>Weight Regularization</td><td/><td>1062.8</td><td/><td>58.0%</td><td>24.0%</td><td>2.5%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td></tr><tr><td>Adv. Training</td><td/><td>51893.6</td><td colspan="2">60.5%</td><td>25.0%</td><td>2.5%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td></tr><tr><td>Bounded</td><td/><td>21918.7</td><td/><td>4.0%</td><td>4.0%</td><td>4.0%</td><td>4.0%</td><td>4.0%</td><td>4.0%</td><td>3.5%</td><td>3.5%</td><td>3.5%</td></tr><tr><td>IBP ReLU Stabilty</td><td>= 8/255</td><td>410.0 396.1</td><td/><td>37.5% 12.0%</td><td colspan="7">35.0% 32.5% 20.0% 17.5% 12.0% 12.0% 12.0% 12.0% 12.0% 12.0% 12.0% 12.0% 2.5% 0.0% 0.0% 0.0%</td></tr><tr><td>Double Margin</td><td/><td>409.7</td><td/><td>45.5%</td><td colspan="7">45.0% 43.5% 40.5% 39.5% 28.0% 22.5% 19.5% 15.0%</td></tr><tr><td/><td/><td/><td/><td colspan="3">Pooling CNN CIFAR, 5 layer</td><td/><td/><td/><td/></tr><tr><td>Normal</td><td/><td>1164.9</td><td/><td>65.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td></tr><tr><td>Weight Regularization</td><td/><td>828.8</td><td/><td>59.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td></tr><tr><td>IBP</td><td/><td>4015.1</td><td/><td>43.0%</td><td>15.5%</td><td>8.5%</td><td>3.0%</td><td>3.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td></tr><tr><td>ReLU Stabilty Double Margin</td><td>= 8/255</td><td>1676.9 2899.5</td><td colspan="2">58.5% 40.0%</td><td colspan="4">8.5% 32.5% 30.5% 24.0% 23.5% 0.0% 0.0% 0.0%</td><td>0.0% 5.0%</td><td>0.0% 1.0%</td><td>0.0% 1.0%</td><td>0.0% 0.5%</td></tr><tr><td/><td/><td/><td colspan="4">Pureconv CNN GTSRB, 4 layer</td><td/><td/><td/><td/></tr><tr><td>Normal</td><td/><td>119.6</td><td/><td>92.0%</td><td colspan="4">77.5% 57.5% 37.0% 35.0%</td><td>6.5%</td><td>1.0%</td><td>0.0%</td><td>0.0%</td></tr><tr><td>IBP Double Margin</td><td>= 8/255</td><td>287.7 283.1</td><td colspan="2">64.0% 68.0%</td><td colspan="7">63.0% 62.0% 58.5% 57.0% 44.5% 31.5% 26.0% 22.0% 67.5% 67.0% 65.0% 64.5% 58.0% 52.5% 50.0% 45.5%</td></tr><tr><td>Method (1000 points)</td><td/><td colspan="2">Training Time (sec)</td><td colspan="2">cert = 0</td><td>0.05</td><td/><td>0.10</td><td/><td>0.20</td><td>0.30</td></tr><tr><td/><td/><td colspan="5">Small CNN MNIST, 4 layer</td><td/><td/><td/><td/></tr><tr><td>TRADES</td><td/><td colspan="4">8264.6 99.5 (0.7)%</td><td colspan="2">0.0 (0.0)%</td><td>0.0 (0.0)%</td><td colspan="2">0.0 (0.0)%</td><td>0.0 (0.0)%</td></tr><tr><td>IBP</td><td/><td colspan="7">611.2 96.3 (1.7)% 92.2 (2.5)% 46.5 (5.1)%</td><td colspan="2">0.0 (0.0)%</td><td>0.0 (0.0)%</td></tr><tr><td>IBP *</td><td/><td colspan="7">460.9 96.7 (1.4)% 90.3 (2.6)% 39.3 (4.6)%</td><td colspan="2">0.0 (0.0)%</td><td>0.0 (0.0)%</td></tr><tr><td>DM Variation 1</td><td>= 0.3</td><td colspan="7">273.3 94.0 (2.1)% 92.7 (2.5)% 90.1 (3.0)%</td><td colspan="3">78.0 (3.9)% 33.1 (4.7)%</td></tr><tr><td>DM Variation 2</td><td/><td colspan="10">589.6 90.1 (2.5)% 88.9 (3.1)% 86.5 (3.2)% 79.3 (3.7)% 59.0 (5.0)%</td></tr><tr><td>Double Margin</td><td/><td colspan="7">520.0 88.2 (2.6)% 86.7 (3.1)% 84.6 (3.4)%</td><td colspan="3">76.2 (3.9)% 61.9 (4.6)%</td></tr><tr><td>Double Margin *</td><td/><td colspan="7">415.3 91.1 (2.6)% 90.1 (2.9)% 87.6 (3.2)%</td><td colspan="3">78.4 (3.9)% 60.4 (4.7)%</td></tr><tr><td>Method (500 points)</td><td/><td colspan="2">Training Time (sec)</td><td colspan="2">cert = 0</td><td>1/255</td><td/><td>3/255</td><td/><td>5/255</td><td>8/255</td></tr><tr><td/><td/><td colspan="5">Small CNN CIFAR, 4 layer</td><td/><td/><td/><td/></tr><tr><td>TRADES</td><td/><td colspan="4">56391.6 62.2 (4.4)%</td><td colspan="2">7.2 (2.5)%</td><td>0.0 (0.0)%</td><td colspan="2">0.0 (0.0)%</td><td>0.0 (0.0)%</td></tr><tr><td>IBP</td><td/><td colspan="7">2446.6 38.0 (4.2)% 32.8 (4.0)% 14.6 (3.1)%</td><td colspan="2">6.0 (2.2)%</td><td>1.2 (0.8)%</td></tr><tr><td>DM Variation 1</td><td>= 8/255</td><td colspan="7">1475.8 45.0 (5.1)% 41.0 (3.8)% 33.8 (4.4)%</td><td colspan="3">22.8 (3.9)% 10.4 (2.6)%</td></tr><tr><td>DM Variation 2</td><td/><td colspan="7">3062.8 43.0 (4.6)% 40.6 (4.2)% 34.2 (4.0)%</td><td colspan="3">27.0 (4.1)% 18.2 (3.2)%</td></tr><tr><td>Double Margin</td><td/><td colspan="10">2198.7 43.2 (4.0)% 40.4 (4.6)% 32.8 (4.4)% 28.6 (4.4)% 19.8 (3.5)%</td></tr><tr><td/><td/><td colspan="5">Pureconv CNN GTSRB, 4 layer</td><td/><td/><td/><td/></tr><tr><td>MMR (4 epochs)</td><td/><td colspan="7">85377.2 88.2 (2.8)% 53.6 (4.0)% 18.2 (3.7)%</td><td colspan="2">4.2 (1.8)%</td><td>0.0 (0.0)%</td></tr><tr><td>IBP</td><td/><td colspan="7">287.7 71.8 (3.9)% 68.0 (4.3)% 60.8 (4.3)%</td><td colspan="3">47.6 (4.7)% 28.2 (3.5)%</td></tr><tr><td>IBP *</td><td>= 8/255</td><td colspan="7">266.6 78.0 (3.7)% 74.8 (3.7)% 62.2 (4.3)%</td><td colspan="3">45.6 (4.7)% 26.8 (3.5)%</td></tr><tr><td>Double Margin</td><td/><td colspan="7">283.1 67.8 (4.4)% 66.8 (4.3)% 61.4 (4.3)%</td><td colspan="3">56.4 (4.7)% 48.2 (4.5)%</td></tr><tr><td>Double Margin *</td><td/><td colspan="10">258.1 75.6 (3.9)% 73.8 (4.2)% 65.0 (4.5)% 57.2 (4.4)% 46.4 (4.4)%</td></tr></table>

Table of Notation

Table content: <table/>

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 ∈ {0.1, 0.2, 0.3} for MNIST and ∈ {2/255, 8/255} for CIFAR and GTSRB as the training target perturbation size train . We used fixed hyperparameters for a fair comparison among training methods (including ours without fine parameter tuning), which may cause different baseline clean accuracies from prior work.

Table content: <table/>

0 , we conduct experiments comparing different versions of Double Margin p with p = ∞, 2, 1 (see Section 3.2, Double Margin: Formal Definition for details). The three different versions of Double Margin are each certified on the three different p norms. Small CNN networks are trained on MNIST and CIFAR with = 0.3, 1, 4 and = 8/255, 0.2, 2 for ∞ , 2 , 1 norms respectively. All versions are trained with fixed hyperparameters for each dataset. We find that on the largest perturbation size evaluated, each version of Double Margin generally performs best on its respective norm (Double Margin ∞ has the highest ∞ certified accuracy etc.) This observation supports the hypothesis that the effectiveness of Double Margin ∞ on 0 is unique. Interestingly, for smaller perturbation sizes Double Margin ∞ achieves better certified accuracy on 2 perturbations than Double Margin 2 .

Table content: <table/>

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.

Table content: <table><tr><td colspan="2">J ADDITIONAL TABLES</td><td/><td/><td/><td/><td/><td/></tr><tr><td>Method</td><td/><td>Training Time (sec)</td><td>cert = 0</td><td>0.05</td><td>0.10</td><td>0.20</td><td>0.30</td></tr><tr><td/><td colspan="3">Small CNN MNIST, 4 layer, ∞</td><td/><td/><td/><td/></tr><tr><td>Double Margin ∞</td><td>= 0.3</td><td>609.7</td><td colspan="5">89.0% 89.0% 88.0% 81.0% 63.5%</td></tr><tr><td>Double Margin 1</td><td>= 4</td><td>593.7</td><td colspan="3">68.5% 59.5% 50.5%</td><td>9.0%</td><td>0.5%</td></tr><tr><td>Double Margin 0</td><td>= 2</td><td>593.3</td><td colspan="3">86.0% 76.0% 57.5%</td><td>4.0%</td><td>0.0%</td></tr><tr><td>Method</td><td/><td>Training Time (sec)</td><td>cert = 0</td><td>0.25</td><td>0.50</td><td>0.75</td><td>1.00</td></tr><tr><td/><td colspan="3">Small CNN MNIST, 4 layer, 1</td><td/><td/><td/><td/></tr><tr><td>Double Margin ∞</td><td>= 0.3</td><td>609.7</td><td>89.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td></tr><tr><td>Double Margin 1</td><td>= 4</td><td>593.7</td><td colspan="5">68.5% 62.5% 53.0% 35.5% 11.0%</td></tr><tr><td>Method</td><td/><td>Training Time (sec)</td><td>cert = 0</td><td>1.00</td><td>2.00</td><td>3.00</td><td>4.00</td></tr><tr><td/><td colspan="3">Small CNN MNIST, 4 layer, 0</td><td/><td/><td/><td/></tr><tr><td>Double Margin ∞</td><td>= 0.3</td><td>609.7</td><td colspan="5">89.0% 89.0% 89.0% 89.0% 89.0%</td></tr><tr><td>Double Margin 0</td><td>= 2</td><td>593.3</td><td colspan="5">86.0% 85.5% 84.0% 82.0% 60.5%</td></tr><tr><td>Method</td><td/><td>Training Time (sec)</td><td colspan="5">cert = 0 1/255 3/255 5/255 8/255</td></tr><tr><td/><td colspan="3">Small CNN CIFAR, 4 layer, ∞</td><td/><td/><td/><td/></tr><tr><td>Double Margin ∞</td><td>= 8/255</td><td>3058.8</td><td colspan="5">42.5% 40.0% 35.0% 31.0% 20.5%</td></tr><tr><td>Double Margin 1</td><td>= 2</td><td>2975.4</td><td colspan="5">30.0% 28.5% 24.5% 20.5% 19.5%</td></tr><tr><td>Double Margin 0</td><td>= 2</td><td>2991.7</td><td colspan="5">28.0% 27.0% 25.0% 22.5% 19.5%</td></tr><tr><td>Method</td><td/><td>Training Time (sec)</td><td>cert = 0</td><td>0.05</td><td>0.10</td><td>0.15</td><td>0.20</td></tr><tr><td/><td colspan="3">Small CNN CIFAR, 4 layer, 1</td><td/><td/><td/><td/></tr><tr><td>Double Margin ∞</td><td>= 8/255</td><td>3058.8</td><td>42.5%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td></tr><tr><td>Double Margin 1</td><td>= 2</td><td>2975.4</td><td colspan="5">30.0% 28.5% 27.0% 23.5% 22.5%</td></tr><tr><td>Method</td><td/><td>Training Time (sec)</td><td>cert = 0</td><td>1.00</td><td>2.00</td><td>3.00</td><td>4.00</td></tr><tr><td/><td colspan="3">Small CNN CIFAR, 4 layer, 0</td><td/><td/><td/><td/></tr><tr><td>Double Margin ∞</td><td>= 8/255</td><td>3058.8</td><td colspan="5">42.5% 42.5% 42.5% 42.5% 42.5%</td></tr><tr><td>Double Margin 0</td><td>= 2</td><td>2991.7</td><td colspan="5">28.0% 27.5% 27.5% 26.0% 24.0%</td></tr></table>

CNN-Cert certified accuracies for Effectiveness on other norms

Table content: <table><tr><td>Method</td><td/><td>Training Time (sec)</td><td>cert = 0</td><td>0.01</td><td>0.03</td><td>0.05</td><td>0.07</td><td>0.10</td><td>0.20</td><td>0.30</td><td>0.40</td></tr><tr><td/><td/><td/><td colspan="3">Small CNN MNIST, 4 layer</td><td/><td/><td/><td/><td/></tr><tr><td>Double Margin Double Margin Ensemble</td><td>= 0.2</td><td>521.1 1411.2</td><td>95.5% 95.5%</td><td colspan="6">95.5% 95.2% 94.2% 93.5% 91.7% 81.3% 95.5% 95.5% 95.5% 94.5% 93.5% 85.5%</td><td>0.0% 0.0%</td><td>0.0% 0.0%</td></tr><tr><td>Method</td><td/><td>Training Time (sec)</td><td colspan="9">cert = 0 0.5/255 1/255 2/255 3/255 5/255 7/255 8/255 9/255</td></tr><tr><td/><td/><td/><td colspan="3">Small CNN CIFAR, 4 layer</td><td/><td/><td/><td/><td/></tr><tr><td>Double Margin Double Margin Ensemble</td><td>= 8/255</td><td>2517.3 6566.2</td><td>42.8% 46.0%</td><td colspan="8">41.8% 39.8% 36.8% 36.3% 26.8% 18.8% 15.8% 13.8% 44.0% 43.5% 40.0% 38.0% 27.0% 22.0% 16.0% 11.0%</td></tr></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.

Table content: <table><tr><td>Method</td><td/><td>Training Time (sec)</td><td colspan="5">= 0 0.5/255 1/255 2/255 3/255 5/255 7/255 8/255 9/255</td></tr><tr><td/><td/><td/><td colspan="2">Pureconv CNN GTSRB, 4 layer</td><td/><td/></tr><tr><td>Normal</td><td/><td colspan="2">119.6 92.0%</td><td>77.5% 57.5% 37.0% 35.0%</td><td>6.5%</td><td>1.0%</td><td>0.0%</td><td>0.0%</td></tr><tr><td>IBP Double Margin</td><td>= 2/255</td><td colspan="2">289.3 84.0% 282.6 83.0%</td><td colspan="4">81.5% 78.0% 65.0% 63.5% 31.0% 14.5% 10.0% 80.0% 77.5% 68.5% 67.0% 43.5% 27.5% 22.0% 16.5% 5.5%</td></tr><tr><td>IBP Double Margin</td><td>= 8/255</td><td colspan="2">287.7 64.0% 283.1 68.0%</td><td colspan="4">63.0% 62.0% 58.5% 57.0% 44.5% 31.5% 26.0% 22.0% 67.5% 67.0% 65.0% 64.5% 58.0% 52.5% 50.0% 45.5%</td></tr></table>

CNN-Cert certified accuracies on GTSRB networks.

Table content: <table><tr><td>Method</td><td/><td>Training Time (sec)</td><td>cert = 0</td><td>0.05</td><td>0.10</td><td>0.20</td><td>0.30</td></tr><tr><td/><td colspan="3">Small CNN MNIST, 4 layer, ∞</td><td/><td/><td/><td/></tr><tr><td>Double Margin ∞</td><td>= 0.3</td><td>609.7</td><td colspan="5">89.0% 89.0% 88.0% 81.0% 63.5%</td></tr><tr><td>Double Margin 2</td><td>= 1</td><td>592.0</td><td colspan="4">68.5% 61.5% 50.0% 22.5%</td><td>1.5%</td></tr><tr><td>Double Margin 1</td><td>= 4</td><td>593.7</td><td colspan="3">68.5% 59.5% 50.5%</td><td>9.0%</td><td>0.5%</td></tr><tr><td>Double Margin 0</td><td>= 2</td><td>593.3</td><td colspan="3">86.0% 76.0% 57.5%</td><td>4.0%</td><td>0.0%</td></tr><tr><td>Method</td><td/><td>Training Time (sec)</td><td>cert = 0</td><td>0.25</td><td>0.50</td><td>0.75</td><td>1.00</td></tr><tr><td/><td colspan="3">Small CNN MNIST, 4 layer, 2</td><td/><td/><td/><td/></tr><tr><td>Double Margin ∞</td><td>= 0.3</td><td>609.7</td><td colspan="2">89.0% 84.5%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td></tr><tr><td>Double Margin 2</td><td>= 1</td><td>592.0</td><td colspan="5">68.5% 62.0% 52.0% 41.5% 24.0%</td></tr><tr><td>Double Margin 1</td><td>= 4</td><td>593.7</td><td colspan="4">68.5% 61.0% 51.5% 34.0%</td><td>9.0%</td></tr><tr><td>Double Margin 0</td><td>= 2</td><td>593.3</td><td colspan="4">86.0% 80.5% 69.0% 39.0%</td><td>7.5%</td></tr><tr><td>Method</td><td/><td>Training Time (sec)</td><td>cert = 0</td><td>1.00</td><td>2.00</td><td>3.00</td><td>4.00</td></tr><tr><td/><td colspan="3">Small CNN MNIST, 4 layer, 1</td><td/><td/><td/><td/></tr><tr><td>Double Margin ∞</td><td>= 0.3</td><td>609.7</td><td>89.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td></tr><tr><td>Double Margin 2</td><td>= 1</td><td>592.0</td><td colspan="3">68.5% 60.5% 39.0%</td><td>0.0%</td><td>0.0%</td></tr><tr><td>Double Margin 1</td><td>= 4</td><td>593.7</td><td colspan="5">68.5% 62.5% 53.0% 35.5% 11.0%</td></tr><tr><td>Double Margin 0</td><td>= 2</td><td>593.3</td><td colspan="4">86.0% 81.0% 69.0% 39.5%</td><td>6.5%</td></tr><tr><td>Method</td><td/><td>Training Time (sec)</td><td>cert = 0</td><td>1.00</td><td>2.00</td><td>3.00</td><td>4.00</td></tr><tr><td/><td colspan="3">Small CNN MNIST, 4 layer, 0</td><td/><td/><td/><td/></tr><tr><td>Double Margin ∞</td><td>= 0.3</td><td>609.7</td><td colspan="5">89.0% 89.0% 89.0% 89.0% 89.0%</td></tr><tr><td>Double Margin 2</td><td>= 1</td><td>592.0</td><td colspan="5">68.5% 68.5% 68.5% 68.5% 68.5%</td></tr><tr><td>Double Margin 1</td><td>= 4</td><td>593.7</td><td colspan="5">68.5% 68.5% 68.5% 68.5% 67.5%</td></tr><tr><td>Double Margin 0</td><td>= 2</td><td>593.3</td><td colspan="5">86.0% 85.5% 84.0% 82.0% 60.5%</td></tr><tr><td>Method</td><td/><td>Training Time (sec)</td><td colspan="5">cert = 0 1/255 3/255 5/255 8/255</td></tr><tr><td/><td colspan="3">Small CNN CIFAR, 4 layer, ∞</td><td/><td/><td/><td/></tr><tr><td>Double Margin ∞</td><td>= 8/255</td><td>3058.8</td><td colspan="5">42.5% 40.0% 35.0% 31.0% 20.5%</td></tr><tr><td>Double Margin 2</td><td>= 0.2</td><td>2969.9</td><td colspan="5">35.0% 32.5% 27.5% 25.5% 17.5%</td></tr><tr><td>Double Margin 1</td><td>= 2</td><td>2975.4</td><td colspan="5">30.0% 28.5% 24.5% 20.5% 19.5%</td></tr><tr><td>Double Margin 0</td><td>= 2</td><td>2991.7</td><td colspan="5">28.0% 27.0% 25.0% 22.5% 19.5%</td></tr><tr><td>Method</td><td/><td>Training Time (sec)</td><td>cert = 0</td><td>0.05</td><td>0.10</td><td>0.15</td><td>0.20</td></tr><tr><td/><td colspan="3">Small CNN CIFAR, 4 layer, 2</td><td/><td/><td/><td/></tr><tr><td>Double Margin ∞</td><td>= 8/255</td><td>3058.8</td><td colspan="3">42.5% 33.5% 18.5%</td><td>3.5%</td><td>0.0%</td></tr><tr><td>Double Margin 2</td><td>= 0.2</td><td>2969.9</td><td colspan="5">35.0% 33.0% 31.5% 28.0% 26.5%</td></tr><tr><td>Double Margin 1</td><td>= 2</td><td>2975.4</td><td colspan="5">30.0% 28.5% 27.0% 26.0% 23.5%</td></tr><tr><td>Double Margin 0</td><td>= 2</td><td>2991.7</td><td colspan="5">28.0% 27.0% 26.5% 25.0% 24.0%</td></tr><tr><td>Method</td><td/><td>Training Time (sec)</td><td>cert = 0</td><td>0.50</td><td>1.00</td><td>1.50</td><td>2.00</td></tr><tr><td/><td colspan="3">Small CNN CIFAR, 4 layer, 1</td><td/><td/><td/><td/></tr><tr><td>Double Margin ∞</td><td>= 8/255</td><td>3058.8</td><td>42.5%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td></tr><tr><td>Double Margin 2</td><td>= 0.2</td><td>2969.9</td><td colspan="5">35.0% 31.5% 28.0% 24.0% 20.0%</td></tr><tr><td>Double Margin 1</td><td>= 2</td><td>2975.4</td><td colspan="5">30.0% 28.5% 27.0% 23.5% 22.5%</td></tr><tr><td>Double Margin 0</td><td>= 2</td><td>2991.7</td><td colspan="5">28.0% 27.5% 26.0% 24.0% 23.5%</td></tr><tr><td>Method</td><td/><td>Training Time (sec)</td><td>cert = 0</td><td>1.00</td><td>2.00</td><td>3.00</td><td>4.00</td></tr><tr><td/><td colspan="3">Small CNN CIFAR, 4 layer, 0</td><td/><td/><td/><td/></tr><tr><td>Double Margin ∞</td><td>= 8/255</td><td>3058.8</td><td colspan="5">42.5% 42.5% 42.5% 42.5% 42.5%</td></tr><tr><td>Double Margin 2</td><td>= 0.2</td><td>2969.9</td><td colspan="5">35.0% 35.0% 35.0% 34.5% 34.0%</td></tr><tr><td>Double Margin 1</td><td>= 2</td><td>2975.4</td><td colspan="5">30.0% 30.0% 30.0% 29.0% 27.5%</td></tr><tr><td>Double Margin 0</td><td>= 2</td><td>2991.7</td><td colspan="5">28.0% 27.5% 27.5% 26.0% 24.0%</td></tr></table>

CNN-Cert certified accuracies for various p versions of Double Margin computed for different p perturbation sizes.

Table content: <table><tr><td>Method</td><td/><td>Training Time (sec)</td><td>cert = 0</td><td>0.01</td><td>0.03</td><td>0.05</td><td>0.07</td><td>0.10</td><td>0.20</td><td>0.30</td><td>0.40</td></tr><tr><td/><td/><td/><td colspan="3">Small CNN MNIST, 4 layer</td><td/><td/><td/><td/><td/></tr><tr><td>Normal</td><td/><td>185.7</td><td>98.5%</td><td>9.5%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td colspan="2">0.0% 0.0%</td></tr><tr><td>Weight Regularization</td><td/><td>626.3</td><td colspan="2">99.5% 81.0%</td><td>1.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td colspan="2">0.0% 0.0%</td></tr><tr><td>Adv. Training</td><td/><td>8873.6</td><td colspan="3">100.0% 97.0% 91.0%</td><td>0.5%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td colspan="2">0.0% 0.0%</td></tr><tr><td>Bounded</td><td/><td>27994.8</td><td colspan="6">48.5% 48.5% 48.5% 48.5% 48.0% 48.0%</td><td>0.0%</td><td colspan="2">0.0% 0.0%</td></tr><tr><td>IBP</td><td/><td>613.1</td><td colspan="6">99.5% 99.5% 99.0% 98.0% 96.5% 83.0%</td><td>0.0%</td><td colspan="2">0.0% 0.0%</td></tr><tr><td>ReLU Stabilty L1+RS+Pruning</td><td>= 0.1</td><td>602.3 686.7</td><td colspan="3">97.5% 89.5% 40.5% 98.0% 90.0% 34.5%</td><td>1.5% 1.5%</td><td>0.0% 0.0%</td><td>0.0% 0.0%</td><td>0.0% 0.0%</td><td colspan="2">0.0% 0.0% 0.0% 0.0%</td></tr><tr><td>Adv+RS+Pruning</td><td/><td>9710.9</td><td colspan="6">98.5% 96.5% 92.0% 84.5% 75.0% 54.0%</td><td>0.0%</td><td colspan="2">0.0% 0.0%</td></tr><tr><td>Double Margin</td><td/><td>520.0</td><td colspan="6">98.5% 98.5% 97.0% 96.5% 96.5% 95.0%</td><td>0.0%</td><td colspan="2">0.0% 0.0%</td></tr><tr><td>Double Margin +L1</td><td/><td>545.5</td><td colspan="6">98.5% 98.5% 97.5% 97.0% 96.5% 95.5%</td><td>0.0%</td><td colspan="2">0.0% 0.0%</td></tr><tr><td>Adv. Training</td><td/><td>8786.8</td><td colspan="4">99.0% 98.5% 91.0% 38.0%</td><td>0.5%</td><td>0.0%</td><td>0.0%</td><td colspan="2">0.0% 0.0%</td></tr><tr><td>Bounded</td><td/><td>27999.5</td><td colspan="7">77.5% 77.5% 77.5% 77.5% 77.5% 77.5% 75.0%</td><td colspan="2">0.0% 0.0%</td></tr><tr><td>IBP</td><td/><td>614.0</td><td colspan="6">97.5% 97.5% 97.0% 96.5% 96.0% 78.0%</td><td>0.0%</td><td colspan="2">0.0% 0.0%</td></tr><tr><td>ReLU Stabilty L1+RS+Pruning</td><td>= 0.2</td><td>592.6 684.8</td><td colspan="4">95.0% 90.0% 59.0% 12.5% 95.0% 89.5% 55.5% 10.5%</td><td>0.5% 1.0%</td><td>0.0% 0.0%</td><td>0.0% 0.0%</td><td colspan="2">0.0% 0.0% 0.0% 0.0%</td></tr><tr><td>Adv+RS+Pruning</td><td/><td>9669.4</td><td colspan="6">93.0% 92.0% 86.5% 80.0% 63.5% 46.0%</td><td>3.5%</td><td colspan="2">0.0% 0.0%</td></tr><tr><td>Double Margin</td><td/><td>518.8</td><td colspan="7">95.0% 94.5% 94.0% 93.0% 92.5% 92.5% 81.5%</td><td colspan="2">0.0% 0.0%</td></tr><tr><td>Double Margin +L1</td><td/><td>546.1</td><td colspan="7">95.5% 95.0% 95.0% 95.0% 95.0% 93.5% 82.0%</td><td colspan="2">0.0% 0.0%</td></tr><tr><td>Adv. Training</td><td/><td>8760.5</td><td colspan="4">99.5% 98.5% 91.5% 38.5%</td><td>1.0%</td><td>0.0%</td><td>0.0%</td><td colspan="2">0.0% 0.0%</td></tr><tr><td>Bounded</td><td/><td>27966.8</td><td colspan="9">30.0% 30.0% 30.0% 30.0% 30.0% 29.5% 28.5% 25.0% 0.0%</td></tr><tr><td>IBP</td><td/><td>611.2</td><td colspan="6">95.5% 95.5% 95.5% 90.5% 76.5% 39.5%</td><td>0.0%</td><td colspan="2">0.0% 0.0%</td></tr><tr><td>ReLU Stabilty L1+RS+Pruning</td><td>= 0.3</td><td>595.8 686.5</td><td colspan="4">94.0% 90.0% 65.0% 23.0% 95.0% 88.0% 53.5% 13.5%</td><td>5.0% 3.0%</td><td>0.5% 0.5%</td><td>0.0% 0.0%</td><td colspan="2">0.0% 0.0% 0.0% 0.0%</td></tr><tr><td>Adv+RS+Pruning</td><td/><td>9657.1</td><td colspan="6">90.0% 86.5% 70.5% 55.0% 30.5% 13.5%</td><td>0.0%</td><td colspan="2">0.0% 0.0%</td></tr><tr><td>Double Margin</td><td/><td>520.0</td><td colspan="9">90.0% 89.0% 88.5% 88.0% 87.5% 86.5% 80.0% 66.5% 0.0%</td></tr><tr><td>Double Margin +L1</td><td/><td>547.1</td><td colspan="9">91.0% 90.5% 90.0% 89.5% 89.0% 87.5% 83.5% 68.0% 0.0%</td></tr><tr><td/><td/><td/><td colspan="4">Medium CNN MNIST, 7 layer</td><td/><td/><td/><td/></tr><tr><td>Normal</td><td/><td>387.4</td><td>100%</td><td>0%</td><td>0%</td><td>0%</td><td>0%</td><td>0%</td><td>0%</td><td>0%</td><td>0%</td></tr><tr><td>IBP Double Margin</td><td>= 0.1</td><td>1553.6 1360.4</td><td colspan="6">100% 100% 100% 100% 100% 100% 100% 100% 100% 100% 90% 85%</td><td>0% 0%</td><td>0% 0%</td><td>0% 0%</td></tr><tr><td>IBP Double Margin</td><td>= 0.2</td><td>1553.2 1360.6</td><td colspan="6">100% 100% 100% 100% 100% 100% 100% 100% 100% 95% 80% 40%</td><td>0% 90%</td><td>0% 0%</td><td>0% 0%</td></tr><tr><td>IBP Double Margin</td><td>= 0.3</td><td>1550.6 1362.3</td><td colspan="4">100% 100% 100% 100% 90% 90% 90% 90%</td><td>90% 90%</td><td>50% 90%</td><td>0% 90%</td><td>0% 80%</td><td>0% 0%</td></tr><tr><td/><td/><td/><td colspan="4">Pooling CNN MNIST, 5 layer</td><td/><td/><td/><td/></tr><tr><td>Normal</td><td/><td>226.0</td><td>99.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td colspan="2">0.0% 0.0%</td></tr><tr><td>Weight Regularization</td><td/><td>145.1</td><td>99.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td colspan="2">0.0% 0.0%</td></tr><tr><td>Adv. Training</td><td/><td>7747.8</td><td colspan="2">99.5% 98.5%</td><td>4.5%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td colspan="2">0.0% 0.0%</td></tr><tr><td>IBP ReLU Stabilty</td><td>= 0.1</td><td>1075.6 337.3</td><td colspan="5">98.0% 92.0% 77.5% 64.5% 40.5% 98.5% 87.0% 0.0% 0.0% 0.0%</td><td>1.0% 0.0%</td><td>0.0% 0.0%</td><td colspan="2">0.0% 0.0% 0.0% 0.0%</td></tr><tr><td>Double Margin</td><td/><td>1070.3</td><td colspan="6">97.5% 95.0% 86.0% 80.0% 73.0% 55.5%</td><td>0.0%</td><td colspan="2">0.0% 0.0%</td></tr><tr><td>Adv. Training</td><td/><td>7573.4</td><td colspan="3">99.5% 98.5% 16.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td colspan="2">0.0% 0.0%</td></tr><tr><td>IBP ReLU Stabilty</td><td>= 0.2</td><td>1082.8 336.7</td><td colspan="6">96.0% 78.0% 63.5% 51.0% 39.0% 20.0% 97.0% 90.0% 4.0% 0.0% 0.0% 0.0%</td><td>0.0% 0.0%</td><td colspan="2">0.0% 0.0% 0.0% 0.0%</td></tr><tr><td>Double Margin</td><td/><td>680.5</td><td colspan="6">94.5% 94.0% 93.0% 91.5% 89.0% 82.5%</td><td>4.5%</td><td colspan="2">0.0% 0.0%</td></tr><tr><td>Adv. Training</td><td/><td>7518.9</td><td colspan="3">99.5% 97.5% 23.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td colspan="2">0.0% 0.0%</td></tr><tr><td>IBP ReLU Stabilty</td><td>= 0.3</td><td>395.4 337.5</td><td colspan="6">95.0% 76.5% 56.0% 44.0% 33.5% 13.5% 97.0% 88.5% 13.0% 0.0% 0.0% 0.0%</td><td>0.0% 0.0%</td><td colspan="2">0.0% 0.0% 0.0% 0.0%</td></tr><tr><td>Double Margin</td><td/><td>408.0</td><td colspan="7">88.0% 88.0% 87.5% 86.5% 85.0% 81.5% 43.0%</td><td colspan="2">0.5% 0.0%</td></tr><tr><td/><td/><td/><td colspan="4">1-Resnet CNN MNIST, 4 layer</td><td/><td/><td/><td/></tr><tr><td>Normal</td><td/><td>210.1</td><td>98.5%</td><td>2.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td colspan="2">0.0% 0.0%</td></tr><tr><td>Weight Regularization</td><td/><td>145.1</td><td colspan="2">99.0% 51.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td colspan="2">0.0% 0.0%</td></tr><tr><td>Adv. Training</td><td/><td>7705.8</td><td colspan="4">99.0% 97.5% 93.5% 22.5%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td colspan="2">0.0% 0.0%</td></tr><tr><td>IBP ReLU Stabilty</td><td>= 0.1</td><td>600.2 318.4</td><td colspan="6">99.0% 95.5% 94.5% 90.5% 87.5% 81.0% 93.0% 85.5% 58.5% 25.5% 9.0% 1.5%</td><td>3.0% 0.0%</td><td colspan="2">0.0% 0.0% 0.0% 0.0%</td></tr><tr><td>Double Margin</td><td/><td>629.3</td><td colspan="6">98.0% 80.5% 77.0% 74.5% 70.0% 65.5%</td><td>0.0%</td><td colspan="2">0.0% 0.0%</td></tr><tr><td>Adv. Training</td><td/><td>7554.4</td><td colspan="4">98.0% 98.0% 95.0% 69.0%</td><td>9.5%</td><td>0.0%</td><td>0.0%</td><td colspan="2">0.0% 0.0%</td></tr><tr><td>IBP ReLU Stabilty</td><td>= 0.2</td><td>593.3 317.8</td><td colspan="7">97.5% 62.0% 57.0% 52.0% 50.0% 45.0% 10.0% 93.0% 85.5% 67.0% 34.5% 17.0% 2.5% 0.0%</td><td colspan="2">0.0% 0.0% 0.0% 0.0%</td></tr><tr><td>Double Margin</td><td/><td>630.0</td><td colspan="7">95.0% 52.0% 51.5% 50.5% 50.0% 46.0% 28.5%</td><td colspan="2">0.0% 0.0%</td></tr><tr><td>Adv. Training</td><td/><td>7583.4</td><td colspan="5">99.0% 97.5% 94.5% 73.0% 17.0%</td><td>0.0%</td><td>0.0%</td><td colspan="2">0.0% 0.0%</td></tr><tr><td>IBP ReLU Stabilty</td><td>= 0.3</td><td>600.3 319.0</td><td colspan="7">96.5% 73.5% 69.0% 63.5% 57.5% 51.0% 13.0% 93.0% 86.0% 70.5% 40.0% 19.5% 4.5% 0.0%</td><td colspan="2">0.0% 0.0% 0.0% 0.0%</td></tr><tr><td>Double Margin</td><td/><td>630.4</td><td colspan="9">92.5% 77.0% 77.0% 75.5% 75.0% 74.5% 62.5% 46.0% 0.0%</td></tr></table>

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). For the medium CNN architecture, accuracies are found over 20 points.

Table content: <table><tr><td>Method</td><td/><td>Training Time (sec)</td><td colspan="9">= 0 0.5/255 1/255 2/255 3/255 5/255 7/255 8/255 9/255</td></tr><tr><td/><td/><td/><td colspan="3">Small CNN CIFAR, 4 layer</td><td/><td/><td/><td/><td/></tr><tr><td>Normal</td><td/><td colspan="2">141.1 61.5%</td><td>22.0%</td><td>1.5%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td></tr><tr><td>Weight Regularization</td><td/><td colspan="2">1062.8 58.0%</td><td>24.0%</td><td>2.5%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td></tr><tr><td>Adv. Training</td><td/><td colspan="2">51203.7 57.5%</td><td>24.5%</td><td>1.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td></tr><tr><td>Bounded</td><td/><td>22351.6</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td></tr><tr><td>IBP ReLU Stabilty</td><td>= 2/255</td><td colspan="2">394.8 47.0% 409.4 12.0%</td><td colspan="8">37.5% 22.0% 12.0% 12.0% 12.0% 12.0% 12.0% 12.0% 12.0% 12.0% 3.5% 3.5% 1.0% 0.0% 0.0% 0.0%</td></tr><tr><td>Double Margin</td><td/><td colspan="2">394.5 45.0%</td><td colspan="4">40.0% 34.0% 25.5% 24.0%</td><td>2.5%</td><td>0.5%</td><td>0.5%</td><td>0.5%</td></tr><tr><td>Adv. Training</td><td/><td colspan="2">51893.6 60.5%</td><td>25.0%</td><td>2.5%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td></tr><tr><td>Bounded</td><td/><td>21918.7</td><td>4.0%</td><td>4.0%</td><td>4.0%</td><td>4.0%</td><td>4.0%</td><td>4.0%</td><td>3.5%</td><td>3.5%</td><td>3.5%</td></tr><tr><td>IBP ReLU Stabilty</td><td>= 8/255</td><td colspan="2">410.0 37.5% 396.1 12.0%</td><td colspan="8">35.0% 32.5% 20.0% 17.5% 12.0% 12.0% 12.0% 12.0% 12.0% 12.0% 12.0% 12.0% 2.5% 0.0% 0.0% 0.0%</td></tr><tr><td>Double Margin</td><td/><td colspan="2">409.7 45.5%</td><td colspan="8">45.0% 43.5% 40.5% 39.5% 28.0% 22.5% 19.5% 15.0%</td></tr><tr><td/><td/><td/><td colspan="4">Medium CNN CIFAR, 7 layer</td><td/><td/><td/><td/></tr><tr><td>Normal</td><td/><td colspan="2">1778.3 50.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td></tr><tr><td>IBP Double Margin</td><td>= 2/255</td><td colspan="2">6613.4 50.0% 5770.2 35.0%</td><td colspan="2">35.0% 20.0% 25.0% 15.0%</td><td>0.0% 0.0%</td><td>0.0% 0.0%</td><td>0.0% 0.0%</td><td>0.0% 0.0%</td><td>0.0% 0.0%</td><td>0.0% 0.0%</td></tr><tr><td>IBP Double Margin</td><td>= 8/255</td><td colspan="2">6598.8 20.0% 5762.2 25.0%</td><td colspan="8">15.0% 15.0% 10.0% 10.0% 25.0% 25.0% 25.0% 25.0% 25.0% 20.0% 10.0% 10.0% 0.0% 0.0% 0.0% 0.0%</td></tr><tr><td/><td/><td/><td colspan="3">Pooling CNN CIFAR, 5 layer</td><td/><td/><td/><td/><td/></tr><tr><td>Normal</td><td/><td colspan="2">1164.9 65.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td></tr><tr><td>Weight Regularization</td><td/><td colspan="2">828.8 59.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td></tr><tr><td>IBP</td><td/><td colspan="2">4112.8 52.0%</td><td colspan="2">24.0% 16.0%</td><td>6.0%</td><td>4.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td></tr><tr><td>ReLU Stabilty Double Margin</td><td>= 2/255</td><td colspan="2">1682.6 60.5% 4091.4 50.5%</td><td colspan="3">1.0% 30.5% 23.5% 11.0% 0.0% 0.0%</td><td>0.0% 8.0%</td><td>0.0% 1.0%</td><td>0.0% 0.0%</td><td>0.0% 0.0%</td><td>0.0% 0.0%</td></tr><tr><td>IBP</td><td/><td colspan="2">4015.1 43.0%</td><td>15.5%</td><td>8.5%</td><td>3.0%</td><td>3.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td></tr><tr><td>ReLU Stabilty Double Margin</td><td>= 8/255</td><td colspan="2">1676.9 58.5% 2899.5 40.0%</td><td colspan="4">8.5% 32.5% 30.5% 24.0% 23.5% 0.0% 0.0% 0.0%</td><td>0.0% 5.0%</td><td>0.0% 1.0%</td><td>0.0% 1.0%</td><td>0.0% 0.5%</td></tr><tr><td/><td/><td/><td colspan="4">1-Resnet CNN CIFAR, 4 layer</td><td/><td/><td/><td/></tr><tr><td>Normal</td><td/><td colspan="2">1153.7 52.5%</td><td>4.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td></tr><tr><td>Weight Regularization</td><td/><td colspan="2">847.3 58.0%</td><td>3.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td></tr><tr><td>IBP</td><td/><td colspan="2">3700.3 48.5%</td><td>8.0%</td><td>6.0%</td><td>2.0%</td><td>2.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td></tr><tr><td>ReLU Stabilty Double Margin</td><td>= 2/255</td><td colspan="2">1592.6 37.5% 3393.9 48.5%</td><td>4.0% 9.0%</td><td>4.0% 8.0%</td><td>4.0% 4.0%</td><td>4.0% 4.0%</td><td>0.0% 1.5%</td><td>0.0% 0.5%</td><td>0.0% 0.5%</td><td>0.0% 0.5%</td></tr><tr><td>IBP</td><td/><td colspan="2">3421.6 42.5%</td><td>2.5%</td><td>2.0%</td><td>1.0%</td><td>1.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td></tr><tr><td>ReLU Stabilty Double Margin</td><td>= 8/255</td><td colspan="2">1594.4 40.0% 3531.5 35.0%</td><td>1.0% 4.0%</td><td>1.0% 4.0%</td><td>1.0% 4.0%</td><td>1.0% 4.0%</td><td>1.0% 4.0%</td><td>0.5% 3.5%</td><td>0.5% 3.5%</td><td>0.0% 3.5%</td></tr></table>

CNN-Cert certified accuracies on all CIFAR networks. Adv. Training(Madry et al., 2018), Bounded(Kolter & Wong, 2018), IBP(Gowal et al., 2018), ReLU Stability(Xiao et al., 2019). For the mediun CNN architecture, accuracies are found over 20 points.

Table content: <table><tr><td>Method</td><td/><td>Training Time (sec)</td><td>cert = 0</td><td>0.01</td><td>0.03</td><td>0.05</td><td>0.07</td><td>0.10</td><td>0.20</td><td>0.30</td><td>0.40</td></tr><tr><td/><td/><td/><td/><td colspan="3">Small CNN MNIST, 4 layer</td><td/><td/><td/><td/></tr><tr><td>Double Margin</td><td>= 0.2</td><td>518.8</td><td colspan="7">93.44% 93.15% 92.61% 92.06% 91.30% 89.63% 78.55%</td><td>0.00%</td><td>0.00%</td></tr><tr><td>Method</td><td/><td>Training Time (sec)</td><td>= 0</td><td colspan="2">0.5/255 1/255</td><td>2/255</td><td>3/255</td><td>5/255</td><td>7/255</td><td>8/255</td><td>9/255</td></tr><tr><td/><td/><td/><td/><td colspan="3">Small CNN CIFAR, 4 layer</td><td/><td/><td/><td/></tr><tr><td>Double Margin</td><td>= 8/255</td><td>409.7</td><td colspan="9">43.00% 41.71% 40.58% 37.72% 37.25% 28.44% 22.39% 19.06% 16.35%</td></tr></table>

CNN-Cert certified accuracies computed on the entire test set.

Table content: <table><tr><td>Method</td><td/><td>Training Time (sec)</td><td>cert = 0</td><td>0.01</td><td>0.03</td><td>0.05</td><td>0.07</td><td>0.10</td><td>0.20</td><td>0.30</td><td>0.40</td></tr><tr><td/><td/><td/><td colspan="4">Medium CNN MNIST, 7 layer</td><td/><td/><td/><td/></tr><tr><td>Normal</td><td/><td>387.4</td><td>99.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td></tr><tr><td>IBP Double Margin</td><td>= 0.1</td><td>1553.6 1360.4</td><td>98.5% 97.5%</td><td colspan="5">98.5% 98.5% 98.5% 97.5% 96.5% 97.5% 97.5% 97.0% 96.5% 96.5%</td><td>0.0% 0.0%</td><td>0.0% 0.0%</td><td>0.0% 0.0%</td></tr><tr><td>IBP Double Margin</td><td>= 0.2</td><td>1553.2 1360.6</td><td>98.5% 95.0%</td><td colspan="6">98.5% 98.5% 98.0% 98.0% 97.0% 94.0% 95.0% 94.5% 94.5% 94.0% 93.5% 89.5%</td><td>0.0% 0.0%</td><td>0.0% 0.0%</td></tr><tr><td>IBP Double Margin</td><td>= 0.3</td><td>1550.6 1362.3</td><td>97.5% 90.5%</td><td colspan="7">97.5% 97.5% 97.5% 96.5% 95.5% 94.0% 90.0% 90.5% 88.5% 87.5% 87.5% 87.0% 83.5% 79.5%</td><td>0.0% 0.0%</td></tr><tr><td/><td/><td/><td colspan="4">Large CNN MNIST, 7 layer</td><td/><td/><td/><td/></tr><tr><td>Normal</td><td/><td>930.6</td><td>99.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td></tr><tr><td>IBP Double Margin</td><td>= 0.1</td><td>4162.8 3742.5</td><td>98.0% 98.5%</td><td colspan="5">98.0% 98.0% 98.0% 97.0% 95.0% 98.5% 98.0% 98.0% 98.0% 97.0%</td><td>0.0% 0.0%</td><td>0.0% 0.0%</td><td>0.0% 0.0%</td></tr><tr><td>IBP Double Margin</td><td>= 0.2</td><td>4162.3 3740.2</td><td>98.5% 97.5%</td><td colspan="6">98.5% 98.5% 98.5% 97.5% 97.5% 93.5% 97.0% 96.5% 96.5% 96.5% 96.5% 95.5%</td><td>0.0% 0.0%</td><td>0.0% 0.0%</td></tr><tr><td>IBP Double Margin</td><td>= 0.3</td><td>4161.4 3739.2</td><td>98.5% 93.0%</td><td colspan="7">98.0% 97.5% 97.5% 97.5% 97.5% 94.5% 91.0% 93.0% 92.5% 92.5% 92.0% 91.0% 84.5% 0.0%</td><td>0.0% 0.0%</td></tr><tr><td>Method</td><td/><td>Training Time (sec)</td><td>= 0</td><td colspan="8">0.5/255 1/255 2/255 3/255 5/255 7/255 8/255 9/255</td></tr><tr><td/><td/><td/><td colspan="4">Medium CNN CIFAR, 7 layer</td><td/><td/><td/><td/></tr><tr><td>Normal</td><td/><td>1778.3</td><td>61.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td></tr><tr><td>IBP Double Margin</td><td>= 2/255</td><td>6613.4 5770.2</td><td>45.5% 45.0%</td><td colspan="3">36.5% 27.0% 11.0% 37.0% 24.5% 10.5%</td><td>9.5% 8.0%</td><td>0.0% 0.5%</td><td>0.0% 0.0%</td><td>0.0% 0.0%</td><td>0.0% 0.0%</td></tr><tr><td>IBP Double Margin</td><td>= 8/255</td><td>6598.8 5762.2</td><td>24.5% 33.5%</td><td colspan="8">24.5% 23.0% 21.5% 21.5% 18.5% 13.5% 12.0% 10.5% 33.0% 32.5% 31.5% 31.5% 25.0% 18.5% 16.0% 13.5%</td></tr><tr><td/><td/><td/><td colspan="3">Large CNN CIFAR, 7 layer</td><td/><td/><td/><td/><td/></tr><tr><td>Normal</td><td/><td>4020.6</td><td>65.5%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td></tr><tr><td>IBP Double Margin</td><td>= 2/255</td><td>17260.8 15141.5</td><td>45.5% 43.5%</td><td colspan="3">33.5% 23.5% 10.0% 33.0% 25.5% 9.5%</td><td>8.0% 9.0%</td><td>0.5% 2.0%</td><td>0.0% 1.0%</td><td>0.0% 0.5%</td><td>0.0% 0.0%</td></tr><tr><td>IBP Double Margin</td><td>= 8/255</td><td>17262.3 15131.7</td><td>27.0% 16.5%</td><td colspan="8">27.0% 26.5% 25.0% 25.0% 23.5% 23.0% 22.5% 21.0% 15.5% 15.0% 15.0% 15.0% 14.5% 14.5% 14.5% 14.5%</td></tr></table>

CNN-Cert-Ada certified accuracies for Comparing different certification methods.

Table content: <table><tr><td>Method (200 points)</td><td/><td colspan="2">cert = 0 0.01</td><td>0.03</td><td>0.05</td><td>0.07</td><td>0.10</td><td>0.20</td><td>0.30</td><td>0.40</td></tr><tr><td/><td/><td/><td colspan="3">Small CNN MNIST, 4 layer</td><td/><td/><td/><td/></tr><tr><td>Normal</td><td/><td>99.5%</td><td>5.5%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td></tr><tr><td>Weight Regularization</td><td/><td>99.5%</td><td>81.0%</td><td>1.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td></tr><tr><td>Adv. Training</td><td/><td>98.5%</td><td>95.5%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td></tr><tr><td>IBP</td><td/><td>95.5%</td><td colspan="5">95.5% 95.5% 93.5% 85.0% 45.5%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td></tr><tr><td>ReLU Stabilty L1+RS+Pruning</td><td>= 0.3</td><td>94.0% 95.0%</td><td colspan="3">90.0% 65.0% 23.0% 88.0% 53.5% 13.5%</td><td>5.0% 3.0%</td><td>0.5% 0.5%</td><td>0.0% 0.0%</td><td>0.0% 0.0%</td><td>0.0% 0.0%</td></tr><tr><td>Double Margin</td><td/><td>91.5%</td><td colspan="7">91.0% 90.5% 90.0% 88.0% 87.0% 77.5% 66.0%</td><td>0.0%</td></tr><tr><td>Method (200 points)</td><td/><td colspan="9">cert = 0 0.5/255 1/255 2/255 3/255 5/255 7/255 8/255 9/255</td></tr><tr><td/><td/><td/><td colspan="3">Small CNN CIFAR, 4 layer</td><td/><td/><td/><td/></tr><tr><td>Normal</td><td/><td>60.5%</td><td>23.5%</td><td>2.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td></tr><tr><td>Weight Regularization</td><td/><td>57.0%</td><td>24.0%</td><td>1.5%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td></tr><tr><td>Adv. Training</td><td/><td>53.5%</td><td>25.0%</td><td>4.5%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td></tr><tr><td>IBP Double Margin</td><td>= 8/255</td><td>47.5% 41.0%</td><td colspan="8">44.5% 41.5% 35.0% 34.0% 16.5% 40.0% 39.0% 36.0% 35.5% 29.5% 20.0% 17.5% 15.0% 4.5% 3.0% 1.5%</td></tr></table>

CNN-Cert-ReLU certified accuracies for Comparing different certification methods.

Table content: <table><tr><td>Method (200 points)</td><td/><td colspan="2">cert = 0 0.01</td><td>0.03</td><td>0.05</td><td>0.07</td><td>0.10</td><td>0.20</td><td>0.30</td><td>0.40</td></tr><tr><td/><td/><td/><td colspan="3">Small CNN MNIST, 4 layer</td><td/><td/><td/><td/></tr><tr><td>Normal</td><td/><td>99.5%</td><td>11.5%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td></tr><tr><td>Weight Regularization</td><td/><td>99.5%</td><td>85.0%</td><td>1.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td></tr><tr><td>Adv. Training</td><td/><td>98.5%</td><td>95.5%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td></tr><tr><td>IBP</td><td/><td>95.5%</td><td colspan="7">95.5% 95.5% 95.5% 95.5% 95.5% 93.5% 86.5%</td><td>0.0%</td></tr><tr><td>ReLU Stabilty L1+RS+Pruning</td><td>= 0.3</td><td>94.0% 95.0%</td><td colspan="3">90.0% 65.0% 23.0% 87.5% 53.5% 13.0%</td><td>5.0% 3.0%</td><td>0.5% 0.5%</td><td>0.0% 0.0%</td><td>0.0% 0.0%</td><td>0.0% 0.0%</td></tr><tr><td>Double Margin</td><td/><td>91.5%</td><td colspan="7">91.0% 90.5% 90.5% 88.5% 87.0% 82.0% 75.5%</td><td>0.0%</td></tr><tr><td>Method (200 points)</td><td/><td colspan="9">cert = 0 0.5/255 1/255 2/255 3/255 5/255 7/255 8/255 9/255</td></tr><tr><td/><td/><td/><td colspan="3">Small CNN CIFAR, 4 layer</td><td/><td/><td/><td/></tr><tr><td>Normal</td><td/><td>53.5%</td><td>23.0%</td><td>3.5%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td></tr><tr><td>Weight Regularization</td><td/><td>60.5%</td><td>15.5%</td><td>1.5%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td></tr><tr><td>Adv. Training</td><td/><td>57.0%</td><td>20.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td></tr><tr><td>IBP Double Margin</td><td>= 8/255</td><td>47.5% 41.0%</td><td colspan="8">44.5% 41.5% 36.5% 36.0% 26.0% 19.5% 17.5% 14.5% 40.0% 39.5% 36.5% 35.5% 30.5% 25.0% 21.0% 19.5%</td></tr></table>

CNN-Cert-Zero certified accuracies for Comparing different certification methods.

Table content: <table><tr><td>Method (200 points)</td><td/><td colspan="2">cert = 0 0.01</td><td>0.03</td><td>0.05</td><td>0.07</td><td>0.10</td><td>0.20</td><td>0.30</td><td>0.40</td></tr><tr><td/><td/><td/><td colspan="3">Small CNN MNIST, 4 layer</td><td/><td/><td/><td/><td/></tr><tr><td>Normal</td><td/><td>99.5%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td></tr><tr><td>Weight Regularization</td><td/><td>99.5%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td></tr><tr><td>Adv. Training</td><td/><td>98.5%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td></tr><tr><td>IBP</td><td/><td>95.5%</td><td colspan="7">95.5% 95.5% 95.5% 95.5% 95.5% 93.5% 86.5%</td><td>0.0%</td></tr><tr><td>ReLU Stabilty L1+RS+Pruning</td><td>= 0.3</td><td>94.0% 95.0%</td><td>33.0% 44.0%</td><td>0.0% 0.5%</td><td>0.0% 0.0%</td><td>0.0% 0.0%</td><td>0.0% 0.0%</td><td>0.0% 0.0%</td><td>0.0% 0.0%</td><td>0.0% 0.0%</td></tr><tr><td>Double Margin</td><td/><td>91.5%</td><td colspan="7">91.0% 90.5% 90.5% 88.5% 87.0% 81.0% 75.5%</td><td>0.0%</td></tr><tr><td>Method (200 points)</td><td/><td colspan="9">cert = 0 0.5/255 1/255 2/255 3/255 5/255 7/255 8/255 9/255</td></tr><tr><td/><td/><td/><td colspan="3">Small CNN CIFAR, 4 layer</td><td/><td/><td/><td/><td/></tr><tr><td>Normal</td><td/><td>53.5%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td></tr><tr><td>Weight Regularization</td><td/><td>60.5%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td></tr><tr><td>Adv. Training</td><td/><td>57.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td><td>0.0%</td></tr><tr><td>IBP Double Margin</td><td>= 8/255</td><td>47.5% 41.0%</td><td colspan="8">44.5% 41.5% 36.0% 36.0% 25.5% 18.5% 16.5% 14.0% 40.0% 39.0% 35.0% 35.0% 29.5% 20.5% 18.5% 16.5%</td></tr></table>

IBP certified accuracies for Comparing different certification methods.

Table content: <table/>

Peer review (iclr2020):
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. In 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. Besides 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. On 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. I 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. I 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: 1. 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. 2. 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. 3. 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. 4. 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. 5. 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. 6. 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. Now let*s discuss the issues in this paper in detail, and let*s focus on the empirical comparisons to IBP first. The 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. There 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. In 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%. Unfortunately, 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. The 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. Now let*s understand why the proposed method cannot improve IBP. The bounds themselves have a few issues: 1. 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. 2. 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*. 3. 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. I 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. The *theory* developed in section 3 is unconvincing and cannot support the *bounds*. There a few problems: 1. 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. 2. 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*. 3. 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. 4. 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. The 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. Sorry for the long comments and I hope they can be helpful for the authors. ****** Reply to general author response: The 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. Most 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. The 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. ****** Conclusions after author response After 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). The 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. This is quite disappointing.