Year: 2019

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.

heading: 1 INTRODUCTION
text: 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.

heading: 2 BACKGROUND AND RELATED WORK

heading: 2.1 VERIFICATIONS
text: 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).

heading: 2.2 CERTIFIED DEFENSES
text: 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.

heading: 2.3 CERTIFICATION METHODS
text: 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 z0 is set to x. Given weights Wi, biases bi and an activation function σ, for i = 0, . . . , n− 1, subsequent layers are defined as: zi+1 = Wi+1σ(zi) + bi+1, (1) with f(x) = zn. With this expression, the first layer of the network is defined by using the identity activation at the first layer. We assume the following threat model: a nominal input xnom is perturbed by perturbation δ to produce a perturbed input x = xnom + δ, 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: maxj 6=c znj − znc > 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 li ≤ zi ≤ ui, the next layer’s bounds are found as:
ui+1 = Wi+1+ σ(u i) +Wi+1− σ(l i) + bi+1, (2) where W+ and W− denote the positive and negative components of W respectively with other entries being zeros otherwise. Lower bounds are found similarly. Intuitively, IBP finds a box bounding each layer, which can result in very loose bounds for general network as demonstrated in (Kolter & Wong, 2018; Gehr et al., 2018).
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 σ(zi) as follows: αi zi + βiL ≤ σ(zi) ≤ αi zi + βiU , where αi represents the slopes of linear bounds on the activation and βiL,β i U representing intercepts of linear bounds on the activation. When σ is ReLU activation, Fast-Lin sets the coefficients to be:
αij = ziu,j
ziu,j − zil,j , βiL,j = 0, β i U,j = −
ziu,jz i l,j
ziu,j − zil,j ,
if the neuron j is uncertain, meaning zil,j < 0, z i u,j > 0 and z i l,j ≤ zij ≤ ziu,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 zil,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+bL ≤ f(x) ≤ Ax+bU . Then Fast-Lin bounds the network output over all possible adversarial distortion measured by -`p ball by:
Axnom + bL − ||A||:,q ≤ f(x) ≤ Axnom + bU + ||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 zu, zl, 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).

heading: 3 UNIFIED FRAMEWORK OF CERTIFIED DEFENSE
text: 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
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.

heading: 3.1 ANALYSIS OF REGULARIZERS
text: 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 regularizerR(θ), 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 ||Wi||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 un and ln 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 zn: L(θ) = E[L(zn)], 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:
L(zn) = L+(z n) + L−(z n), (3)
where L+(zn) increases element-wise with zn and L−(zn) decreases element-wise with zn. For example in the case of softmax cross-entropy loss:
L(zn) = −yT log (ez n /(1T ez n )) = log 1T ez n − yT zn,
where ex is element-wise exponential function and y are one-hot encoded labels, the first term can be mapped to L+(zn) while the second corresponds to L−(zn) in (3). IBP then constructs the following regularizer: R(θ) = E[L+(un)+L−(ln)−L(znnom)], where un and ln are defined by (2) and znnom is the value of layer zn with unperturbed input xnom. When this regularizer is added to the standard loss function L(θ) computed with unperturbed input xnom, the resulting quantity L(θ) +R(θ) is an upper bound on the adversarial loss since: L(znnom)+(L+(u n)+L−(l n)−L(znnom)) ≥ L(zn),where zn is a function of perturbed input x, obtained by monotonicity of L+ and L− and ln ≤ zn ≤ un.
Note that the adversarial loss L(zn) is unknown, but the upper bound constructed here depends only on the IBP bounds un and ln 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: 1m ∑ imaxx:||x−xi||p≤ L(f(x)) ≤ L(θ) + λR(θ), for sufficiently large λ where there are m points xi in the training set. Similarly `1 and `2 regularization can be seen as minimizing a probabilistic upper bound on the test set loss: Ltest(θ) ≤ 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,
Ltest(θ) ≤ L(θ) + K ∏ j ||Wj ||+ C√
m , (4)
where Ltest(θ) 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 4.
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:
θ̂ − λH(L(θ̂))−1∇θR(θ̂), (5)
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(θ) + λR1(θ). Then, for λ near 0, L(θ∗) + λR2(θ∗) < L(θ̂) + λR2(θ̂) if and only if:
||∇θR1(θ̂)−∇θR2(θ̂)||H(L(θ̂))−1 < ||∇θR2(θ̂)||H(L(θ̂))−1 , (6)
where ||a||B = √ aTBa.
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" regularizerR2(θ∗) 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.

heading: 3.2 OUR REGULARIZER
text: 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 [znom− s− v, znom+ s+ v] represents the approximate range of values each layer z can take, where znom represents the value of the layer for unperturbed input xnom. In the similar spirit of IBP, we define the 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 σ(zij) ≈ azij + b for some a, b at all layers i, all margins vi ≈ 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 si and vi at layer i have the same dimensionality as zi, 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: s0 = 1,v0 = 0. For i = 0, . . . , n− 1, subsequent layer margins are defined as:
si+1 = 1
2 |Wi+1|
( σ(zinom + s i)− σ(zinom − si) )
(7)
vi+1 = 1
2 |Wi+1|
( σ(zinom + v i)− σ(zinom − vi) )
(8)
+ 1
2 |Wi+1||σ(zinom + si + vi) + σ(zinom − si − vi)− 2σ(zinom)|
For general `p norms p 6=∞, the second layer margins are modified so that s1 is exactly half the range of values z1 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:
hi+1 = 1
2 |Wi+1|(σ(mi + hi)− σ(mi − hi))
The s margin is propagated similarly, with the difference being that IBP uses (ui + li)/2 instead of zi 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 zi. Specifically, note that given a 2nd order Taylor expansion of σ(·) at a specific scalar point x0, σ(x− x0) ≈ 12a(x− x0)
2 + b(x− x0) + c, then the second derivative of σ(·) at x0 is given by: σ′′(x0) = a ≈ 1γ2 (σ(x0 + γ) + σ(x0 − γ)− 2σ(x0)), where γ > 0 is small. Applying this approximation to the second term in Equation (8):
1 2 |Wi+1||σ(zinom+ si+vi)+ σ(zinom− si−vi)− 2σ(zi)| ≈ 1 2 |Wi+1||σ′′(zinom) (si+vi)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 θ:
R(θ) = E[L+(znnom + sn + vn) + L−(znnom − sn − vn)− L(znnom)] (9)
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 regularizerR(θ). 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.

heading: 3.3 EXTENSIONS
text: 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.

heading: 4 EXPERIMENTS
text: We conduct experiments comparing our regularizer to other robust training methods including `1 weight regularization, adversarial training, IBP, ReLU stability and convex outer bounds (Bounded).

heading: 4.1 SETUP, MODELS, DATASET
text: Implementation, Architectures, Training Parameters Training methods are implemented in Python with Tensorflow (Abadi et al., 2016) and training is conducted on a NVIDIA Tesla P100 GPU. We evaluate the training methods on networks trained on the MNIST, CIFAR-10 and GTSRB (Stallkamp et al., 2012) datasets. We consider 6 model architectures listed roughly in increasing model size: (i) Small CNN, (ii) Pureconv CNN, (iii) Resnet CNN, (iv) Pooling CNN, (v) Medium CNN, (vi) Large CNN. For a fair comparison among training methods, we used fixed training parameters. Architecture and hyperparameter details are deferred to Appendix G.
Comparative Methods We train networks with (i) normal training, (ii) `1 weight regularization, (iii) adversarial training, (iv) IBP, (v) ReLU stability, (vi) Bounded, (vii) MMR (Croce et al., 2019), (viii) TRADES (Zhang et al., 2019) and (ix) our method (Double Margin). Due to the computational cost of running Bounded training, we train this method only on the small CNN architecture. For training Bounded models, we use the technique of random projections as proposed by (Wong et al., 2018), using 50 random projections. For the small CNN architecture, we try additional robust training methods including (x) combining adversarial training with the ReLU stability loss and weight pruning (Adv+RS+Pruning), and (xi) combining `1 weight regularization with ReLU stability and weight pruning (L1+RS+Pruning). We also (xii) add `1 weight regularization to our regularizer (Double Margin + L1).
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).

heading: 4.2 RESULTS
text: 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 12 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.

heading: 5 CONCLUSION
text: 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. 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.

heading: A APPENDIX OUTLINE
text: A. Appendix Outline B. Table of Notation C. Double Margin Visual Illustration D. Double Margin Algorithm E. Proof of Proposition 1 F. Proof of Proposition 2 G. Architecture and Hyperparameter Details H. Extensions
1. `0 Norm Threat Model 2. Model Ensemble
I. Additional Results 1. Comparing Different Certification Methods 2. Effectiveness on Other Norms 3. Model Ensemble 4. GTSRB 5. Medium CNN Model 6. Full Test Set
J. Additional Tables 1. Comparing Different Certification Methods 2. Effectiveness on Other Norms 3. Model Ensemble 4. Additional GTSRB Results 5. Double Margin `p 6. Complete MNIST Results 7. Complete CIFAR Results 8. Full Test Set 9. Additional IBP Certified Accuracy

heading: B TABLE OF NOTATION
text: Notation Definition Notation Definition xnom unperturbed input Wi,bi weights, biases of layer i δ input perturbation zi input of layer i maximum `p perturbation size ||δ||p ui, li pre-activation interval bounds x perturbed input si,vi double margins f neural network classifier αi, βiU , β i L linear bounding parameters
σ neural network activation A,bL,bU linear network bounds n number of network layers L : θ → R training loss function m number of training points Ltest : θ → R test loss function L : zn → R point-wise loss function R : θ → R regularizer θ model parameters λ regularizer coefficient
Table 3: Table of Notation

heading: C DOUBLE MARGIN VISUAL ILLUSTRATION

heading: D DOUBLE MARGIN ALGORITHM
text: Algorithm 1: Double Margin Training Algorithm Data: Training data D, Randomly initialized weights and biases Wi,bi, i = 1 : N , Number of epochs E, Perturbation size , Regularization weight λ Result: Trained weights and biases Wi,bi for epoch = 1:E do
for xnom in D do z0 = xnom, s
0 = 1,v0 = 0; for i = 1:N do
Propagate zi+1 with Equation (1) Propagate si+1 with Equation (7) Propagate vi+1 with Equation (8)
end Construct regularized loss L+ λR = λL+(zn + sn + vn) + λL−(zn − sn − vn) + (1− λ)L(zn) Compute gradients of L+ λR w.r.t. Wi,bi Update Wi,bi via gradient descent
end end

heading: E PROOF OF PROPOSITION 1
text: 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 ddλθ ∗:
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.

heading: F PROOF OF PROPOSITION 2
text: Proof. Note that at λ = 0, θ∗ = θ̂. Consider the difference between the performance of θ∗ and θ̂ on regularized loss L(θ) + λR2(θ): D(λ) = L(θ̂) + λR2(θ̂)− L(θ∗)− λR2(θ∗) Taking the derivative with respect to λ:
d
dλ D(λ) = −∇θL(θ∗)T
d
dλ θ∗ − λ(∇θR2(θ∗)T
d
dλ θ∗) + (R2(θ̂)−R2(θ∗))
Note that evaluated at λ = 0, this quantity is 0 since ∇θL(θ̂) = 0. Taking a second derivative with respect to λ:
d2
dλ2 D(λ) = − d dλ θ∗TH(L(θ∗)) d dλ θ∗ −∇θL(θ∗)T
d2
dλ2 θ∗ − 2∇θR2(θ∗)T
d
dλ θ∗
− λ d dλ (∇θR2(θ∗)T d dλ θ∗)
Evaluating at λ = 0: d2
dλ2 D(λ)|λ=0 = −
d
dλ θ∗T |λ=0H(L(θ̂))
d
dλ θ∗|λ=0 − 2∇θR2(θ̂)T
d
dλ θ∗|λ=0,
since ∇θL(θ̂) = 0. Substituting the expression for ddλθ ∗|λ=0 from Proposition 1:
d2
dλ2 D(λ)|λ=0 = −∇θR1(θ̂)TH(L(θ̂))−1H(L(θ̂))H(L(θ̂))−1∇θR1(θ̂)
+ 2∇θR2(θ̂)TH(L(θ̂))−1∇θR1(θ̂) Simplifying:
d2
dλ2 D(λ)|λ=0 = −||∇θR1(θ̂)−∇θR2(θ̂)||2H(L(θ̂))−1 + ||∇θR2(θ̂)|| 2 H(L(θ̂))−1
Where ||a||B = √ aTBa. This implies that for small λ 6= 0, D(λ) > 0 is equivalent to the condition: ||∇θR1(θ̂)−∇θR2(θ̂)||H(L(θ̂))−1 < ||∇θR2(θ̂)||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(θ) + λRJ (θ̂). Suppose L(θ) has minimum θ̂, and suppose there is a set of feasible regularizers that can be used during training of the network {R1(θ),R2(θ), . . . ,Rk(θ)} with regularization coefficient λ. Then, Proposition 2 suggests selecting the regularizer R̃(θ) = argmini ||∇θRi(θ̂) − ∇θRJ (θ̂)||H(L(θ̂))−1 . Here Ri(θ̂) corresponds to the minimized regularizerR1(θ̂) in Proposition 2 andRJ (θ̂) corresponds to the target regularizer R2(θ̂). Intuitively, the regularizer that is closest toRJ (θ) 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 toRJ (θ) is best.

heading: G ARCHITECTURE AND HYPERPARAMETER DETAILS
text: The small CNN architecture uses convolution layers of 16 and 32 filters followed by a 100 unit fully connected layer. The pureconv CNN architecture uses three convolution layers of 16 filters. The medium CNN architecture uses convolutional layers of 16, 16, 32 and 32 filters followed by two 512 unit fully connected layers. The large CNN architecture uses convolutional layers of 64, 64, 64, 128 and 128 filters followed by a 200 unit fully connected layer. The pooling CNN architecture uses two convolution layers of 16 filters each followed by a max-pooling layer of stride 2-by-2. The resnet CNN architecture uses a 16 filter convolution layer followed by a simple residual block with two 16 filter convolution layers. The MNIST and GTSRB networks are trained for 100 epochs each while the CIFAR networks are trained for 350 epochs each. For robust training methods, we use ∈ {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.

heading: H EXTENSIONS
text: H.1 `0 NORM THREAT MODEL
In addition to a `p threat model, we can consider a `0 threat model where an input xnom is perturbed by perturbation δ to produce perturbed input x = xnom + δ 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 s1 can be set exactly to one half the range of values each node can take:
s1j = 1
2 k∑ l=1 rank(W0j,: (1− xnom), l)− rank(W0j,: ∗ xnom, 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 f1(x), f2(x), ... fN (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:
fensemble(x) = 1
N ∑ i fi(x)
When using our regularizer, the regularization margins of the N models can also be averaged together. The ensemble loss is then constructed by substituting the averaged values into Equation (9). During inference, the final layers can be averaged together before classification. Alternatively, we can select the class with the most votes among the ensembled models.

heading: I ADDITIONAL RESULTS
text: 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 `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. 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).
I.5 FULL TEST SET
Table 10 shows CNN-Cert certified accuracies computed on the full test set for two selected models trained on MNIST and CIFAR. The certified accuracies are similar to those computed on 200 randomly selected test set points, indicating that the random sample is fairly representative.

heading: J ADDITIONAL TABLES

heading: K ADDITIONAL RESULTS IN REBUTTAL
text: K.1 COMPARING DIFFERENT CERTIFICATION METHODS
Here, we conduct experiments comparing different certification methods. Specifically, we compare IBP with different variations of CNN-Cert including CNN-Cert-ReLU, CNN-Cert-Ada. These bounds differ by how they bound the ReLU function for unstable ReLUs as illustrated in Figure 3 with CNN-Cert-ReLU using parallel bounds and CNN-Cert-Ada using an adaptive lower bound. We also compare with a variation of CNN-Cert using a constant lower bound of zero, which we call CNN-Cert-Zero.
We note that this bound is strictly stronger than IBP as IBP uses a constant upper bound and lower bound to bound the activation function, whereas CNN-Cert-Zero uses a tighter linear upper bound and the same constant lower bound (y = 0), as clearly shown in Figure 3. As a result, for any fixed network, IBP yields weaker than CNN-Cert-Zero. Many certification methods in the literature are equivalent to one of these methods as illustrated in Table 12.
Tables 13, 14, 15, 16 show certified accuracies using the different certification methods. We find that CNN-Cert-ReLU and CNN-Cert-Ada generally yield the highest accuracies for most networks. Using these certifiers, Double Margin generally yields higher certified accuracies than other methods.
However, for models trained on IBP, IBP certified accuracies are much higher than those of CNNCert-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.

Review summaries:
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.