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):
The authors first demonstrate that many existing approaches are special cases of regularized objectives, and then provide a theoretical analysis on the relationship between the local minima of the original loss and the corresponding regularized loss. Afterwards, the authors propose a new regularizer inspired by the IBP regularizer by taking account of second order information. Through a large set of experiments the authors demonstrate that their approach achieves higher certified accuracy using CNN-Cert, compared to many previous approaches. I have some concerns on the writing and experiments of this paper. - The paper seems to have two parts that are isolated from each other. The first part of this paper discusses some theoretical analyses on the relationship of local minima for regularized and unregularized losses. The second part of this paper proposes the DoubleMargin regularizer. However, I can*t see why the theoretical analysis motivates the DoubleMargin regularizer. The only statement that tries to relate theoretical analyses and the proposal is *the gradient of a regularizer rather than its bound validity determines its certified test loss. Therefore ... using an upper bound on the adversarial loss is not necessary to train certifiable models*. This is a super general and vague motivation, and is not specialized to the DoubleMargin regularizer. The argument can actually be used for justifying arbitrary regularizers... - Since the advantage of DoubleMargin is not motivated theoretically, the empirical performance becomes critical. However, I don*t think the experiments are rigorous and the comparisons are fair. In Table 2 only certified accuracies from CNN-Cert are reported. However, CNN-Cert does not work well for models trained by IBP. For fair comparison, the authors should report the best result from a group of certification methods. The certified results of IBP using CNN-Cert seem to be much worse than the results reported in the original IBP paper (Gowal et al., 2018) , which were verified using IBP. In fact, in both table 4 and table 12, the authors show results that the IBP method outperforms the DoubleMargin approach when results are verified by IBP.