Adversarial Training and Provable Defenses: Bridging the Gap
Authors: Mislav Balunovic
Martin Vechev
Venue:  (2020)
Keywords: adversarial examples
adversarial training
provable defense
convex relaxations
deep learning

Abstract: We present COLT, a new method to train neural networks based on a novel combination of adversarial training and provable defenses. The key idea is to model neural network training as a procedure which includes both, the verifier and the adversary. In every iteration, the verifier aims to certify the network using convex relaxation while the adversary tries to find inputs inside that convex relaxation which cause verification to fail. We experimentally show that this training method, named convex layerwise adversarial training (COLT), is promising and achieves the best of both worlds -- it produces a state-of-the-art neural network with certified robustness of 60.5% and accuracy of 78.4% on the challenging CIFAR-10 dataset with a 2/255 L-infinity perturbation. This significantly improves over the best concurrent results of 54.0% certified robustness and 71.5% accuracy.
   


Published as a conference paper at ICLR 2020
ADVERSARIAL TRAINING AND PROVABLE DEFENSES: BRIDGING THE GAP
Mislav Balunović, Martin Vechev
Department of Computer Science ETH Zurich, Switzerland (mislav. ba bnovic,,,, martin. bartii..eeherJeeif..eti.
ABSTRACT
We present COLT, a new method to train neural networks based on a novel com- bination of adversarial training and provable defenses. The key idea is model neural network training as a procedure which includes both, the verifier and the adversary. In every iteration, the verifier aims to certify the network using con- vex relaxation while the adversary tries to find inputs inside that convex relaxation which cause verification to fail. We experimentally show that this training method, named convex layerwise adversarial training (COLT), is promising and achieves the best of both worlds it produces state-of-the-ar neural network with cer- tified robustness of 60.5% and accuracy of 78.4% on the challenging CIFAR-10 dataset with a 2/255 Loe perturbation. This significantly improves over the best concurrent results of 54.0% certified robustness and 71.5% accuracy.
INTRODUCTION
The discovery of adversarial examples in deep learning (Szegedy al., 2013; Biggio et al., 2013) has increased the importance of creating new training methods which produce accurate and robust neural networks with provable guarantees.
Existing work: adversarial and provable defenses Adversarial training (Goodfellow et al., 2015; Kurakin et al., 2017) provides a framework to augment the training procedure with adversarial inputs produced by adversarial attack. Madry et al. (2018) instantiated adversarial training using a strong iterative adversary and showed that their approach can train models which are highly ro- bust against the strongest known adversarial attacks such as Carlini & Wagner (2017). This method has also been able to train robust ImageNet models (Xie et al., 2019). While promising, the main drawback of the method is that when instantiated in practice, via an approximation of otherwise intractable optimization problem, it provides guarantees it does not produce certificate that there are no possible adversarial attacks which could potentially break the model. address this lack of guarantees, recent line of work provable defenses (Wong & Kolter, 2018; Raghunathan et al., 2018; Mirman et al., 2018) has proposed to train neural networks that are certifiably robust to specific attacker threat model. However, these guarantees come at the cost of significantly lower standard accuracy than models trained using adversarial training. This setting raises a natural question:
leverage ideas from both, adversarial training techniques and provable defense methods, so to obtain models with high accuracy and certified robustness?
This work: combining adversarial and provable defenses In this work, we take a step towards addressing this challenge. We show that it is possible to train more accurate and provably robust neu- ral networks using the same convex relaxations as those used in existing, state-of-the- defense methods, but with a new, different optimization procedure inspired by adversarial training. Our optimization works as follows: (i) to certify a property (e.g., robustness) of the network, the ver- ifier produces convex relaxation of all possible intermediate vector outputs in the neural network, then (ii) an adversary now searches over this (intermediate) convex region in order to find, what we refer to latent adversarial example that when propagated through the network causes a misclassification which prevents verification, and finally (iii) the resulting latent adversarial examples now incorporated into training scheme
provable
concrete intermediate input contained in the relaxation

---

Published as a conference paper at ICLR 2020
using adversarial training. Overall, training and provable defenses (it can conceptually be instantiated with any convex relaxation). We experimentally show that the method is promising and results in neural network with state-of-the- art 78.4% accuracy and 60.5% certified robustness on the challenging CIFAR-10 10 dataset with 2/255 To perturbation (the best known existing results are 71.5% accuracy and 54.0% certified robustness from concurrent work of Zhang et al. (2020)).
this method bridging the gap between adversarial
Main Contributions Our key contributions are:
A new method, which refer to as convex layerwise adversarial training (COLT), that can train provably robust neural networks and conceptually bridges the gap between adversarial training and existing provable defense methods.
Instantiation of convex layerwise adversarial training using linear convex relaxations used in prior work (accomplished by introducing a projection operator).
Experimental results showing convex layerwise adversarial training can train neural net- work models which achieve both, state-of-the-an accuracy and certified robustness on CIFAR-10 10 with 2/255 Tooo perturbation.
Complete implementation of our training and certification methods in system which release at https: htt///gitttt higthub.b....................... www/co////t../o eteetthhssee srr-rrr/eee coltt.
Overall, we believe the method presented in this work is promising step towards training models that enjoy both, higher accuracy and higher certification guarantees. An interesting item for future work would be to explore instantiations of the method with other convex relaxations than the one considered here.
2 RELATED WORK
We now discuss some of the closely related work on robustness of neural networks.
Heuristic adversarial defenses After the first introduction of adversarial examples (Szegedy et al., 2013; Biggio et al., 2013), defense mechanisms to train robust neural networks were built based the inclusion of adversarial examples to the training set (Kurakin et al., 2017: Goodfel- low et al., 2015). Models trained using adversarial training with projected gradient descent (PGD) (Madry et al., 2018) were shown to be robust against the strongest known attacks (Carlini & Wag- ner, 2017). This is in contrast to other defense mechanisms which have been broken by new attack techniques (Athalye al., 2018). While models trained using adversarial training achieve robust- ness against strong adversaries, there are no guarantees that model is robust against any kind of adversarial attack under the threat model considered.
Provable adversarial defenses There has also been considerable amount of work methods to train classifiers with robustness guarantees. These approaches are typically based on Lipschitz reg- ularization Hein & Andriushchenko (2017), linear (Wong & Kolter, 2018) or semidefinite (Raghu- nathan et al., 2018; Dvijotham et al., 2018a) relaxations, hybrid zonotope (Mirman et al., 2018) or interval bound propagation (Gowal al., 2018). While these approaches obtain robustness guaran- tees, accuracy of these networks is relatively small and limits practical use of these methods.
There has also been recent work on certification of general neural networks, not necessarily trained in special way. These methods are based on SMT solvers (Katz et al., 2017). abstract interpretation (Gehr et al., 2018), mixed-integer linear programs (Tjeng et al., 2019), linear relaxations (Weng al., 2018; Zhang al., 2018; Singh et al., 2019c) or combinations of those (Singh al., 2019b;a).
Another line work proposes to replace neural networks with a randomized classifier (Lecuyer et al., 2018; Cohen et al., 2019; Salman et al., 2019a) which comes with probabilistic guarantees on its robustness. While these approaches scale to larger datasets such as ImageNet (although with probabilistic instead of exact guarantees), their bounds come from the relationship between Lę bustness and Gaussian distribution. In this paper, we consider general verification problem where input is not necessarily limited to T.p ball, but arbitrary convex set, as explained in Section 3.
2

---

Published as a conference paper at ICLR 2020
3 BACKGROUND
In this work we consider a threat model where an adversary is allowed to transform an input a E IR into any point from a convex set (x) _ do The set Sp can capture wide range of specifications such as Lp perturbations (Wong & Kolter, 2018), geometric transformations (Balunović et al., 2019), semantic perturbations (Mohapatra et al., 2019) camera imaging (Yang & Rinard, 2019). In the case of a threat model based on L perturbations, which we experiment with later, the convex set will be defined (a())) = {æ' RRd, ||æ 2'1 < <e).
A neural network consisting of h layers and parameters is represented as a function ho where hg = hg о ng h h and h2 R441 - Rd denotes a transformation applied at hidden layer We also denote the function representing part of the neural network from layer to the final layer as hig ng hg
h h.g. hig.
Our goal will be to prove a property on the output of the neural network, encoded via a linear constraint:
c² (xx)) + d < 0, Yx' E So(x))
(1)
where and d are property specific vector and scalar values, respectively. This formulation is general enough to capture many interesting safety properties (Dvijotham et al., 2018b; Qin et al., 2019), including robustness to Lp perturbations. The standard approach to train model he to satisfy this constraint is to define surrogate loss L and solve the following min-mat optimization problem:
min E (ky)DD max ((ha(z'). x' (a)))
Because inner maximization is intractable, most existing approaches replace it with an approxima- tion. Depending on the used approximation, we distinguish two families of techniques.
adversarial training (Goodfellow et al., 2015; Kurakin et al., 2017), replaces the maximum loss with a lower bound which is ob- tained using an adversarial attack. Madry et al. (2018) maximized the inner loss using a projected gradient descent (PGD) attack and found that, perhaps surprisingly, this optimization procedure suc- ceeds in training deep architectures which are robust against the strongest known adversaries. While this provides strong empirical evidence that the resulting models are indeed robust, the approach offers no guarantees. Thus, it remains unclear whether there exist even stronger attacks that could break model trained in this manner.
Adversarial training One family of methods, referred
Provable defenses second family of methods to train certified neural networks is based on the computation of an upper bound to the inner loss, as opposed to a lower bound computed for adversar- ial training. These methods are typically referred to as provable defenses as they provide guarantees on the robustness of the resulting network, under any kind of attack inside the threat model. An upper bound is typically computed using linear relaxations (Wong & Kolter, 2018), interval propa- gation (Gowal et al., 2018) or methods combining interval bounds and linear relaxations (Mirman et al., 2018; Zhang et al., 2020). However, these methods suffer from two disadvantages.
First, due the convex relaxations, upper bound the loss is typically not tight and can be quite loose. However, we believe this is less of an issue due to the fact that interval relaxations were shown to experimentally be able train more provably robust models than methods based on linear relaxations (which usually produce tighter bounds than intervals). For example, Mirman et al. (2018); Zhang et al. (2020) report 28% robust accuracy using pure interval training on CIFAR-I0 with perturbation 8/255 while Wong et al. (2018) achieve 21% using linear relaxations.
Second, the way these methods construct the loss makes the relationship between the loss and the network parameters significantly more complex than in standard training. Given network with L layers and at most N neurons in each layer, to compute the loss we have to perform O(LN2) oper- ations for interval training and OLLN3) operations for linear relaxation based training. Intuitively, while there are exceptions, we can expect that a loss involving more mathematical operations is more difficult to minimize. We hypothesize that this complexity of loss computation (here quantified as number of operations) causes the resulting optimization problem for training the network to be more difficult, meaning these training methods often converge suboptimal solution. Our experimental results confirm this we substantially outperform existing methods both in terms of accuracy and certified robustness using the same linear relaxation, but different optimization procedure.
3

---

Published as a conference paper at ICLR 2020
Certification via convex relaxations We now formally describe how provable defenses perform certification. We denote the set of possible intermediate concrete vectors at layer i that can be obtained by propagating vector x' E (z) through the network as (zx)) hig (x)) S R As it is difficult to explicitly compute the set S,(x), a standard approach is to approximate it via convex relaxation (ar). As the input set is already convex, there is need to introduce relaxation, and thus we set Co (z) = (o( Given a neural network layer hi which transforms one set of vectors into another, we represent its corresponding convex relaxation transformer as gg. That is, 9g will transform one convex set into another convex set. More formally, for any set D C R (D) is convex and hi (ID) C (D). Then, we recursively define the effect of g on a convex relaxation as Cx = D (C--1 (x)) R4,, Finally, to certify robustness using the obtained convex relaxation, it is enough to check whether all output vectors in C& (zz) satisfy the linear constraint in Equation 1. If this is true, then all output vectors in (x)) satisfy the constraint as well due to the fact that (x) S (z))
4 PROVABLE DEFENSE VIA CONVEX LAYERWISE ADVERSARIAL TRAINING
We now describe our convex layerwise adversarial training approach which yields provable defense that bridges the gap between standard adversarial training and existing provable defenses.
Motivation: latent adversarial examples Consider an already trained neural network model ha which we would like to certify using convex relaxations. A fundamental issue here is that certifi- cation methods based on convex relaxations can struggle to prove the target property (c.g., robust- ness) due to the iterative loss of precision introduced by the relaxation. More precisely, assume the neural network actually satisfies the property from Equation 1 for an input æ, meaning that c. hhgh(a)) (x') + < 0, Va' E (ax).. Naturally, this also implies that the neural network behaves correctly in the latent space of its first hidden layer in the region S (z)). Formally, this means that cf hig (x1)+ +d < 0, Va' E S (ar). However, if one would use a certification method which replaces the region 81 (x) by its convex relaxation C₁ (xx) then it is possible that we would fail to certify our
desired property. This is due to the fact that there may exist an input x E (x)) \ S (x) such that c <2, + d 2 O. Of course, we could repeat the above thought experiment and possibly find more violating latent inputs in the set Cx(x) \ (ar) of any hidden layer i. The existence of points found in the difference between a convex relaxation and the true region is a fundamental reason for the failure of certification methods based on convex relaxations. For convenience, we refer to such points as latent adversarial examples. Next, we describe method which trains the neural network in way that aims to minimize the number of latent adversarial examples.
Layerwise provable optimization via convex relaxations Our key observation is that the two families of defense methods described earlier are in fact different ends of the same spectrum: meth- ods based adversarial training maximize the cross-entropy loss in the first convex region (x)) while provable defenses maximize the same loss, but in the last convex region C2 (z). Both methods then backpropagate the loss through the network and update the parameters using SGD. However, as explained previously, certification methods may fail even before the last layer due to the presence of latent adversarial examples in the difference of the regions (xr) and S (x). A natural question then is - can we leverage adversarial training so to eliminate latent adversarial examples from hidden layers and obtain a provable network?
To this end, we propose adversarial training in layerwise fashion. The initial phase of training is equivalent to adversarial training as used by Madry et al. (2018). In this phase in the inner loop we repeatedly find an input in Co(2:) which maximizes the cross-entropy loss and update the parameters of the neural network so to minimize this loss using SGD. Note that the outcome of this phase is model which is highly robust against strong multi-step adversaries. However, certification of this fact often fails due to the previously mentioned loss of precision in the particular convex relaxation being used, which then leads to the existence of latent adversarial examples in the hidden layers.
The next step of our training method is visually illustrated in Figure 1. Here, we propagate the initial convex region through the first layer of the network and obtain the convex region C1 (z)). We then solve the optimization problem to find a concrete point xn inside of C (w) which produces the maximum loss when this point is propagated further through the network (this forward pass
4

---

Published as a conference paper at ICLR 2020
Conv
Conv
Su-5 [(h (af).
Co(æ)
C (x))
C2(2)
Ca(x)
Figure I:
An iteration of convex layerwise adversarial training. Latent adversarial example æ/ is found in the convex region C (2) and propagated through the rest of the layers in a forward pass, shown with the blue line. During backward pass, gradients are propagated through the same layers, shown with the red line. Note that the first convolutional layer does not receive any gradients.
shown with the blue line). Finally, we backpropagate the final loss (red line) and update the parameters of the network to minimize the loss. Critically, do not backpropagate through the convex relaxation in the first layer as standard provable defenses do (Wong & Kolter, 2018; Mirman al., 2018; Gowal et al., 2018). We instead freeze the first layer and stop backpropagation after the update of the second layer. Because of this, our optimization problem significantly easier the neural network only has learn behave well on the concrete points that were found the convex region Cx))). This can be viewed as an extension of the robust optimization method that Madry al. (2018) found work well practice.
We then proceed with the above process for later layers. Formally, this training process amounts to (approximately) solving the following min-max optimization problem the I-th step:
min (xyy)= max BE
C(h 1 (zf), y, 0)
(3)
Note that for = this formulation is equivalent to the standard min-max formulation in Equation because Co(x) = Su (x). Our approach solve this min-max optimization problem for every layer I is shown in Algorithm 1. We initialize every batch by random sampling from the corresponding convex region. Then, every iteration we use projected gradient descent (PGD) to maximize inner loss in Equation 3. We first update æ;j in the direction of the gradient of the loss and then project it back to C,(æ,) using the projection operator II. Note that this approach assumes existence of an efficient projection method to the particular convex relaxation the method is instantiated with. In the next section, show how to instantiate the training algorithm described above particular convex relaxation which is generally tighter than a hyperrectangle and where we derive an efficient projection operation.
Algorithm 1: Convex layerwise adversarial training convex relaxations
Data: k-layer network fog training set V),, learning rate 17, step size inner steps Result: Certifiably robust neural network ha
for I < 1: do
2
for S Repoch. do
Sample mini-batch {(x1, y1), (x2, (22, y2),,.,, (Kh, yb)] (X,));
Compute convex relaxations (x1)) (x2)) ((()) Initialize æ (((21). C((22) ..., Ci(x));
5
for j < b do
Update in parallel times: 2' + II (a's a a
end
Update parameters 0 < - - Σ voL(h 1i (
end
Freeze parameters 0,+1 of layer function 1
end
5

---

Published as a conference paper at ICLR 2020
C((2)
II(e)
[T(r))
62
2
20
62
42
22
61
+ e2
Figure 2: Projection to a region based on linear relaxation using change of variables.
5 CONVEX LAYERWISE ADVERSARIAL TRAINING USING LINEAR RELAXATIONS
So far we described the general approach of convex layerwise adversarial training. Now we show how to instantiate it for a particular convex relaxation based on linear approximations. If instead one would use interval approximation (Mirman et al., 2018; Gowal et al., 2018) as the convex re- laxation, then all regions Ca())) would be hyperrectangles and projection to these sets is fast and simple. However, the interval relaxation provides coarse approximation which motivates the need to train with relaxations that provide tighter bounds. Thus, we consider linear relaxations which are generally tighter than those based on intervals.
In particular we leverage the same relaxation which was previously proposed in Wong & Kolter (2018); Weng et al. (2018); Singh et al. (2018) an effective way certify neural networks. Here, each convex region is represented as a set Cxxx) = {at + Aie e E [-1, 1, 1]"".. Vector a repre- sents the center of the set and the matrix A represents the affine transformation of the hypercube [-1,1] This representation is also known as zonotope abstraction (Ghorbal et al., 2009). The ini- tial convex region Co(x) is represented using ag x and Ao eIdo is diagonal matrix. Propaga- tion of these convex regions through the network is out of the scope of this paper full description can be found in Wong & Kolter (2018) Singh et al. (2018). At a high level, the convolutional and fully connected layers are handled by multiplying A, and by appropriate matrices. To handle the ReLU activation, we apply convex relaxation that amounts to multiplying A and a, by appropri- ately chosen diagonal matrices which depend on whether the ReLU is activated not. Using this relaxation of ReLU, we recursively obtain all convex regions Cx))). In practice, the term A,e can be computed without explicitly constructing matrix A, because A,e
TTA:-WWi-2 M.ee. Due to the associativity of matrix multiplication, we can compute Aie by performing a chain of matrix-vector multiplications from right to left (instead of more expensive chain of matrix-matia multiplications from left to right) and obtain vector Aie. We provide more detailed description of this computation in Appendix A.
Projection to linear convex regions To use our training method we now need to instantiate Algo- rithm I with suitable projection operator Ie), The key insight here is that the vector x' Ci(æ)) is uniquely determined by auxiliary vector E [-1, 1 where x' a; + Aje. Then instead of directly solving for x' which requires projecting to (z)x), we can solve for e instead which would uniquely determine x'. Crucially, the domain of e is a hyperrectangle [-1, 1] which is easy to project to. To visualize this further we provide an example in Figure 2. The goal is to project the red point ø' in the right picture to the convex region (x)). To project, we first perform change of variables to substitute x' with and then project to the square [-1, x [-1, to obtain the blue
point (I(e) on the left. Then, we again perform change of variables obtain the blue point [(x') on the right, which is the projection of x' we were looking for.
first update the coefficients ej using the following update rule: e, e + aA; va; C(x), vy), -1, 1). Here clip is function which thresholds its argument between -1 and 1, formally clip(t, -1, 1) = min(max(t,, -1), 1). This is followed by update at, via a/ +- a; + Aiej, completing the update step.
Based on these observations, we modify Line of Algorithm

---

Published as a conference paper at ICLR 2020
Efficient computation of convex regions While representation of convex regions with matrix A and vector aj has clean mathematical properties, in practice, a possible issue is that the matrix A, grow to be quite large. Because of this, propagating it through the network be mem- ory intensive and prohibit the use of larger batches. To overcome this difficulty, we propose two methods.
First method is based on the observation that A, is quite sparse. We start with a very sparse, diagonal matrix Ag the input. After each convolution, an element of matrix A4+1 non-zero only if there a non-zero element inside of its convolutional kernel in matrix A,. We can leverage this observation to precompute positions of all non-zero elements in matrix A++1 and compute their values using matrix multiplication.
Second method is based on the idea from Wong al. (2018). Their key insight is that convex regions (x)) can be computed approximately during training. They propose to use random projections from Li al. (2007) to estimate lower and upper bound for each neuron. While they operate in dual framework, we apply the same approach in our primal view. In our experiments, we use this method as it is more efficient than working with sparse representation. After training, during certification, we compute regions (x) exactly without the estimation.
This optimization critical to enabling training to take place altogether. An interesting item for future work is further optimizing the current relaxation (via specialized GPU implementation) or developing more memory friendly relaxations, so to scale the training to larger networks.
Regularization One issue with the method presented in Section 4 is that there is no explicit mech- anism that tries to make convex relaxation Cr(2)) as close as possible to the exact region (x)))) in order to avoid downstream loss of precision during later stages of the training, when layer 7 is already frozen. To address this, we also incorporate additional regularizers similar to Xiao et al. (2019): Lı regularization and ReLU stability regularization. The purpose of L1 regularization is to learn sparse weight matrices and the goal of ReLU stability regularization is to have fewer crossing ReLU units, both which are beneficial for precision. Our ReLU stability is different from Xiao et al. (2019) since directly minimize the area induced by linear convex relaxation. More details for these regularizers can be found in Appendix D.
6 CERTIFICATION OF NEURAL NETWORKS
After training neural network via convex layerwise adversarial training, our goal is to certify the target property (e.g., robustness). Here we leverage several recent advances in certification techniques which are not fast enough to be incorporated into the training procedure, but which can significantly speed up the certification or increase its precision.
Refinement of the linear approximation The linear relaxation of ReLU, which we are using, is parameterized by slopes À of the linear relaxation. Prior work which employed this relaxation (Wong Kolter, 2018: Weng et al., 2018; Singh al., 2018) has chosen these slopes greedily by minimizing the area of the relaxation. During training we also choose X in the same way. However, during certification, we can also optimize for the values of X that give rise to the convex region inside of which the maximum loss is minimized. This optimization problem can be written as:
min max XE
C(h l:k (z)).))
(x:A))
Solving this is computationally too expensive inside the training loop, but during certification is feasible to approximate the solution. We solve for À using the Adam optimizer and clipping the elements between 0 and I after each update. We remark that the idea of learning the slope is similar to Dvijotham al. (2018b) who propose optimize dual variables in dual formulation, however here we stay in the primal formulation.
Combining convex relaxations with exact bound propagation During convex layerwise adver- sarial training essentially train the network to be certified on all regions Co(x), ... Cx(x). While computing exact regions (x) C (x) is not feasible during training, we can afford it to some extent during certification. The idea is to first propagate the bounds using convex relaxations until

---

Published as a conference paper at ICLR 2020
one of the hidden layers I and obtain region Cx)). If training successful, there should not exist a concrete point zi E (x)) which, if propagated through the network, violates the correctness property in Equation 1. We can encode both, the property and the propagation of the exact bounds (a())) using a Mixed-Integer Linear Programming (MILP) solver. Note that we can achieve this because represent the region (a:) using set of linear constraints, which may not be possi- ble for general convex shapes. We perform the MILP encoding using the formulation from Tjeng al. (2019). It is usually possible to encode only the last two layers using MILP due the poor scalability of these solvers for realistic network sizes. One further improvement we also include is to tighten the convex regions (x))) using refinement via linear programming as described in Singh et al. (2019b). We remark that this combination of convex relaxation and exact bound propagation does not fall under the recently introduced convex barrier to certification Salman et (2019b).
7 EXPERIMENTAL EVALUATION
We now present evaluation of our training method on the challenging CIFAR-10 dataset. All of our code, datasets, trained models and scripts to reproduce the experiments can found at https: http://gttuu...m/ettt... srrrsriiiii colt.
Experimental setup We perform all experiments on desktop PC using single GeForce RTX 2080 Ti GPU and 16-core Intel(R) Core(TM) 19-9900K CPU @ 3.60GHz. We implemented training and certification in Py PyTorch (Paszke et al., 2017) and used Gurobi 9.0 as a MILP solver.
Neural network architecture We evaluate on architectures. First architecture is 4-layer convolutional network: first 3 layers are convolutional layers with filter sizes 32, 32, 128, kernel sizes 3, 4, 4 and strides 1, 2, respectively. Second architecture is 3-layer convolutional network: first 2 layers are convolutional layers with filter sizes 32 and 128, kernel sizes 5 and 4, strides 2 and 2, respectively. In both architectures, convolutional layers are followed by fully connected layer consisting of 250 hidden units. After each layer there is a ReLU activation. Final layer is fully connected layer with 10 output neurons.
Training During layerwise training we start with perturbation which higher than the one we certify, and then decrease it by certain factor when the training progresses to the next layer. In each stage of the training, we train for 200 epochs, starting from the same loss as in the previous stage and gradually annealing it to the loss of the current stage during first 60 epochs. We optimize using SGD with the initial learning rate 0.03 and after the initial 60 epochs we multiply the learning rate by 0.5 every 10 epochs. To find the best performing hyperparameters for training, we created a validation set consisting of random 5000 images from the training set and used it to tune the hyperparameters with SigOpt (Martinez-Caniie et al., 2018). We tuned batch size, initial c, factor to decrease after each layer, L, regularization and ReLU stability factors. All hyperparameter values used in our experiments are listed in Appendix C.I.
Certification After training completes, we perform certification as follows: for every image, we first try to certify it using only linear relaxations (with the improvement of learned slopes, Section 6). If this fails, encode the last layer as MILP and try again. Finally, if this fails encode the ReLU activation after the last convolution using additional up to 50 binary variables and the rest using the triangle formulation Ehlers (2017). We consider an image to be not certifiable if we fail certify using these methods. We always certify the full test set of 10 000 images.
Comparison to prior work We first train a robust network using our method for the Los per- turbation 2/255. this experiment, we used larger architecture with convolutional and fully connected layer. We perform convex layerwise adversarial training in 4 stages, for 200 epochs per stage, for a total of 800 epochs. The training takes 53, 164, 228, 250 seconds per epoch in the four respective stages of the training. It takes roughly 2 days to certify 10 000 images on a single GPU. Results are shown in Table 1. We always compare to the best reported and reproducible results in the literature et al., 2019), as these provide probabilistic instead of exact guarantees. Extensions to Cohen et al. (2019) such Salman et al. (2019a) also use additional existing techniques such pre-training
any architecture. We do not compare to smoothing based approaches (Cohen
8

---

Published as a conference paper at ICLR 2020
Table Evaluation on CIFAR-I0 dataset with Loe perturbation 2/255
Method
Accuracy(%)
Certified Robustness| %
Our work
78.4
60.5
Zhang et al. (2020)
71.5
54.0
Wong et (2018)
68.3
53.9
Gowal et al. (2018)
70.2
50.0
Xiao et al. (2019)
61.1
45,9
Mirman et al. (2019)
62.3
45.5
Table Evaluation on CIFAR-10 dataset with Loe perturbation 8/255
Method
Accuracy(%)
Certified Robustness( (
Our work
51.7
27.5
Zhang et al. (2020)
54.5
30.5
Mirman et al. (2019)
46.2
27.2
Wong et al. (2018)
28.7
21.8
Xiao et al. (2019)
40.5
20.3
on ImageNet and unlabeled data which orthogonal. We also do not compare to using cascades from Wong et al. (2018), as this improvement is also orthogonal to the method here. Thus, we only consider their best single network architecture (inline with prior work Zhang al. (2020) which compares to a single architecture). We believe all methods listed Table 1, including ours, would benefit from additional techniques such as cascades, pre-training and leveraging unlabeled data. Ex- perimentally, we find that the neural network trained using our method substantially outperforms all existing approaches, both in terms of standard accuracy and certified robustness for 2/255. Note that here we are using the same linear relaxation as Wong et al. (2018), but our optimization procedure is different and shows significant improvements over the one used in their work. We also remark that concurrent work Zhang et al. (2020) reports 59.7% robustness against PGD which implies that even empirical robustness of their best model is lower than certified robustness our network.
We also run the same experiment for Los perturbation 8/255 and present the results in Table 2. In this experiment, we used smaller architecture with 2 convolutional and I fully connected layer. Here we perform convex layerwise adversarial training in 3 stages, again for 200 epochs per stage, for total of 600 epochs. The training takes 20, 67, 87 seconds per epoch in the three respective stages of the training. Here we do not include comparison with Gowal et al. (2018) as their results were found to be not reproducible (Mirman et al., 2019; Xu, 2019; Zhang et al., 2019), and the best reproducible results for this method can be found in Zhang et al. (2020). Here existing approaches except for the concurrent work of Zhang et al. (2020) whose method is based on combination of interval and linear relaxation. We suspect that here the main issue is that our 3-layer network lacks capacity to solve this task, and capacity was found to be one of the key components necessary to obtain a robust classifier (Madry al., 2018). Due promising results for 2/255, we believe achieving state-of-the-ee art results for 8/255 is very likely an issue of instantiating our method with a convex relaxation that is more memory efficient, which we believe an interesting item for future work.
substantially outperform all
Analysis Next, we analyze the effect of our convex layerwise adversarial training, also on CIFAR- 10 with 2/255 and 8/255 T. perturbations. Recall that the first stage, our training is equivalent to PGD from Madry et al. (2018) and in each of the successive stages, we freeze the current layer and retrain the rest of the network. In this experiment, we are interested robustness of model against latent adversarial attacks during each stage of the training. To perform this experiment, after each stage of the training we stored the intermediate model and ran latent adversarial attack on these models, each of the layers. For latent adversarial attack, we perform PGD in the latent space, with 150 steps and step size of 0.01. Note that final models correspond to the models reported in Table 1 and Table 2.

---

Published as a conference paper at ICLR 2020
80
80
Latent robu robustness (%)
Latent robustness
40
Stage
20
Stage
20
Stage 1
Stage
Stage 2
Stage 4
Stage 3
Attacked layer
Attacked layer
(a) CIFAR- 10, 2/255
(b) CIFAR-IO, 8/255
Figure 3: Effect of proposed convex layerwise adversarial training, After each stage of the training, we attack the model with latent adversarial attack on each the layers. Note that layer 0 represents standard PGD attack (attack in the input space).
The results are shown in Figure 3a and Figure 3b, for 2/255 and 8/255 perturbations, respectively. Each dot represents success rate of latent adversarial attack on trained model, where each model is shown in different color. Red line shows the model trained after the first stage, which is equivalent to PGD training from Madry et al. (2018). As expected, this model is robust against the standard adversarial attack in the input space which denoted as attack on layer O. However, this Stage model lacks robustness in the deeper layers which prevents from certifying the robustness using convex relaxations. Using convex layerwise adversarial training, the model progressively becomes robust to perturbations in the deeper layers. For example, Figure 3a shows that final model, after Stage 4, has 41 %% robustness in layer 4 which is significant improvement over Stage 1 model which has only 18% robustness in layer 4. Note that this means can certify 41 % using only linear relaxation, and 60.5% when learning the slopes and encoding part of the network as MILP, which is explained in Section We observe similar results for 8/255 perturbation shown in Figure 3b.
Other datasets To further evaluate our method, we also experimented with other datasets: Street House View Numbers (SVHN) and MNIST Handwritten Digits. We report the full results in Ap- pendix C.2 and give a brief summary here. On SVHN with L perturbation 0.01 we also achieve state-of-the-arr accuracy and certified robustness. On MNIST, we evaluated with perturbations 0.1 and 0.3. With Los perturbation 0.1 we achieve results comparable with best results from prior work, while with perturbation 0.3 certified robustness is lower than the one achieved by approaches based on interval bound propagation (Zhang et al., 2020). We believe that, because of large pertur- bation of 0.3, random projections are imprecise and one would need use the exact bounds which introduces much higher cost at runtime. This is also reflected in the poor performance of Wong et al. (2018) on this benchmark, as we use the same random projections as their work. We believe that instantiating our method with convex relaxation that is more memory friendly than what we used would likely yield better results in this experiment.
CONCLUSION
We presented a new method to train certified neural networks. The key concept was to combine techniques from provable defenses using convex relaxations with those of adversarial training. Our method, named convex layerwise adversarial training (COLT), achieves state-of-the-art 78.4% ac- curacy and 60.5% certified robustness CIFAR-10 with 2/255 Lox perturbation, significantly outperforming prior work when considering a single network (it also achieves competitive results on 8/255 L.o). The method is general and can be instantiated with any convex relaxation. promis- ing future work item is scaling to larger networks: this will require tight convex relaxations with a low memory footprint that allow for efficient projection.
10

---

Published as a conference paper at ICLR 2020
REFERENCES
Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give a false sense of se- curity: Circumventing defenses to adversarial examples. In Proceedings of the 35th International Conference on Machine Learning, 2018.
Mislav Balunović, Maximilian Baader, Gagandeep Singh, Timon Gehr, and Martin Vechev. Certi- fying geometric robustness of neural networks. In Advances in Neural Information Processing Systems, 2019.
Battista Biggio, Igino Corona, Davide Maiorca, Blaine Nelson, Nedim Smdićć, Pavel Laskov, Gior- gio Giacinto, and Fabio Roli. Evasion attacks against machine learning at test time. Joint European conference machine learning and knowledge discovery in databases, 2013.
Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In 2017
IEEE Symposium Security and Privacy (S&P), 2017.
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. In Proceedings of the 36th International Conference on Machine Learning, 2019.
Krishnamurthy Dvijotham, Sven Gowal, Robert Stanforth, Relja Arandjelovic, Brendan O'Donoghue, Jonathan Uesato, and Pushmeet Kohli. Training verified learners with learned ver- ifiers. arXiv preprint /805. 10265, 2018a.
Krishnamurthy Dvijotham, Robert Stanforth, Sven Gowal, Timothy A Mann, and Pushmeet Kohli. A dual approach to scalable verification of deep networks. In UAI, 2018b.
Ruediger Ehlers. Formal verification of picce-wise linear forward neural networks. In Interna- fional Symposium on Automated Technology for Verification and Analysis, 2017.
Timon Gehr, Matthew Mirman, Dana Drachsler-Cohen Petar Tsankov, Swarat Chaudhuri, and Mar- tin Vechev. Ai2: Safety and robustness certification of neural networks with abstract interpreta- tion. In 2018 IEEE Symposium on Security and Privacy (S&P), 2018.
Khalil Ghorbal, Eric Goubault, and Sylvie Putot. The zonotope abstract domain taylorI+. In Inter- national Conference on Computer Aided Verification, 2009.
Ian Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In International Conference on Learning Representations, 2015.
Sven Gowal, Krishnamurthy Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Ue- sato, Timothy Mann, and Pushmeet Kohli. On the effectiveness of interval bound propagation for training verifiably robust models. arXiv preprint arXiv:1810.12715 2018.
Matthias Hein and Maksym Andriushchenko. Formal guarantees the robustness of classifier against adversarial manipulation. In Advances in Neural Information Processing Systems, 2017.
Guy Katz, Clark Barrett, David I. Dill, Kyle Julian, and Mykel Kochenderfer. Reluplex: An efficient smt solver for verifying deep neural networks. In International Conference on Computer Aided Verification, 2017.
Diederik Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint arXiv: 1412.6980, 2014.
Alexey Kurakin, lan Goodfellow, and Samy Bengio. Adversarial machine learning at scale. Inter- national Conference on Learning Representations, 2017.
Mathias Lecuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified robustness to adversarial examples with differential privacy. 2019 IEEE Symposium on Security and Privacy (S&P), 2018.
Ping Li, Trevor J Hastie, and Kenneth W Church. Nonlinear estimators and tail bounds for dimension reduction in 11 using cauchy random projections. Journal of Machine Learning Research, 2007.
11

---

Published as a conference paper at ICLR 2020
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations, 2018.
Ruben Martinez-Cantin, Cantin, Kevin Tee, and Michael McCourt. Practical bayesian optimization in the presence outliers. Proceedings of the Twenty-Firss International Conference on Artificial Intelligence and Statistics, 2018.
Matthew Mirman, Timon Gehr, and Martin Vechev. Differentiable abstract interpretation for prov- ably robust neural networks. In International Conference on Machine Learning, 2018.
Matthew Mirman, Gagandeep Singh, and Martin Vechev. A provable defense for deep residual networks. arXiv preprint arXiv: / /903. /2519, 2019.
Jeet Mohapatra, Pin- Yu Chen, Sijia Liu, Luca Daniel, et al. Towards verifying robustness of neural networks against semantic perturbations. arXiv preprint arXiv:1912.09533, 2019.
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. 2017.
Chongli Qin, Krishnamurthy (Dj) Dvijotham, Brendan O' O'Donoghue, Rudy Bunel, Robert Stanforth, Sven Gowal, Jonathan Uesato, Grzegorz Swirszez, and Pushmeet Kohli. Verification of non-linear specifications for neural networks. In International Conference on Learning Representations, 2019.
Aditi Raghunathan, Jacob Steinhardt, and Percy Liang. Certified defenses against adversarial exam- ples. In International Conference on Learning Representations, 2018.
Hadi Salman, Greg Yang. Jerry Li, Pengchuan Zhang, Huan Zhang, Ilya Razenshteyn, and Sebastien Bubeck. Provably robust deep learning via adversarially trained smoothed classifiers. arXiv preprint 190iv 04584, 2019a.
Hadi Salman, Greg Yang, Huan Zhang. Cho-Jui Hsieh, and Pengchuan Zhang. A convex relaxation barrier tight robust verification of neural networks. arXiv preprint 192.02190. 2019b.
Gagandeep Singh, Timon Gehr, Matthew Mirman, Markus Püichel, and Martin Vechev. Fast and effective robustness certification. In Advances in Neural Information Processing Systems, 2018.
Gagandeep Singh, Rupanshu Ganvir, Markus Püschel, and Martin Vechev. Beyond the single neuron convex barrier for neural network certification. In Advances Neural Information Processing Systems, 2019a.
Gagandeep Singh, Timon Gehr, Markus Puschel, and Martin Vechev. Boosting robustness certifica- tion of neural networks. In International Conference on Learning Representations, 2019b.
Gagandeep Singh, Timon Gehr, Markus Püschel, and Martin Vechev. An abstract domain for certi- fying neural networks. Proceedings of the ACM on Programming Languages, 2019c.
Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. arXiv preprint arXiv: 13/2.6/99, 2013.
Vincent Tjeng, Kai Y. Xiao, and Russ Tedrake. Evaluating robustness of neural networks with mixed integer programming. In International Conference on Learning Representations, 2019.
Lily Weng, Huan Zhang, Hongge Chen. Zhao Song, Cho-Jui Hsich, Luca Daniel, Duane Boning, and Inderjit Dhillon. Towards fast computation of certified robustness for ReLU networks. In Proceedings of the 35th International Conference on Machine Learning, 2018.
Eric Wong and Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In Proceedings of the 35th International Conference Machine Learning- PMLR, 2018.
Eric Wong, Frank Schmidt, Jan Hendrik Metzen, and J. Zico Kolter. Scaling provable adversarial defenses. In Advances in Neural Information Processing Systems 31. 2018.
12

---

Published as a conference paper at ICLR 2020
Kai Y. Xiao, Vincent Tjeng, Nur Muhammad (Mahi) Shafiullah, and Aleksander Madry. Training for faster adversarial robustness verification via inducing reLU stability. In International Conference Learning Representations, 2019.
Cihang Xie, Yuxin Wu, Laurens der Maaten, Alan Yuille, and Kaiming He. Feature denoising for improving adversarial robustness. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2019.
Weilin Xu. Reproducibility issue. 2019. URL http:s///ggttuub..cmm//emm...a interval-bount
Yichen Yang and Martin Rinard. Correctness verification of neural networks. arXiv preprint arXiv:1906.01030, 2019.
Huan Zhang, Tsui-Wei Weng, Pin- Yu Chen, Cho-Jui Hsich, and Luca Daniel. Efficient neural net- work robustness certification with general activation functions. In Advances in neural information processing systems, 2018.
Huan Zhang, Hongge Chen, Chaowei Xiao, Bo Li, Duane Boning, and Cho-Jui Hsieh. Towards sta- ble and efficient training of verifiably robust neural networks. arXiv preprint 2019.
06316,
Huan Zhang, Hongge Chen, Chaowei Xiao, Sven Gowal, Robert Stanforth, Bo Li, Duane Boning, and Cho-Jui Hsieh. Towards stable and efficient training of verifiably robust neural networks. In International Conference Learning Representations, 2020.
13

---

Published as a conference paper at ICLR 2020
Here provide additional details that were omitted in the main body of the paper.
A CONVEX RELAXATION USING LINEAR APPROXIMATIONS
In this section, we describe how to propagate convex relaxations of the form C((x)) = {ar + A E [-1,1]'²/ through the network, for a single input æ. As explained before, these relaxations were previously proposed in Wong & Kolter (2018); Weng al. (2018); Singh et al. (2018). For the sake of completeness we describe them here using our notation. Depending on the form function distinguish different cases. Here assume that
hi representing operation applied at layer have obtained region C,-1(x) and our goal is to compute the region (x) using convex relaxation gh of the function hig
Initial convex region Let e be Los radius which we are certifying. First, we compute minimum and maximum pixel values for each pixel as x. max(0, x e) and xt min(1, + c). Then, we define initial convex region as:
mg == do
1
ag 2 (x' x²
Ao = Td (x" - xx')
Convolutional and fully connected layers
For both convolutional and fully connected layers, the (a)) = W+11 + b Recall that x = a, + A,e where
concrete update given by x/41 = h/
[-1,1]m We can then compute:
h (x'))
W bi+1
Wi+i(a; A₁e) + bi+1
Wi+1a; bi+1 + W,i
Using this formula, we define convex region (,+1(x) {a:41 + A | 1 where:
m;+1 ==
a == W Wi11; b
A = W+114,
ReLU activation In this case h is ReLU activation function and क/ h ReLU(x()) = max(x,, 0) applied componentwise. We will explain the transformation a sin- gle element o'y = aij Aije. We first compute lower bound 4.j and upper bound uey of element of, in the set C,():):
mi
4
Gi.i
Ai.i
Ui.j
Di.j +
Aigh
If Way < O then ReLU(z),)) = 0 and if 4, > 0 then ReLU(x(.)) = = In the other case where is between ligj and Ui,j we define ReLU(x = Aigzl, + Pi.jem,+i where em,+j E [-1, is coefficient for a new error term. Formulas for At, and pi, are the following:
Uz
Ai. úi,j bisj
-Ui
M. 2(wis (i,))
14

---

Published as a conference paper at ICLR 2020
This computation also be written in the matrix form ReLU(x;) A M,-1 nne where A1+1 and M1+1 are diagonal matrices with elements computed as above. More formally, A4+1 and M1+1 are both d; x d, diagonal matrices with diagonal entries Ait1os M4+1js = Mijj
Aij and convex region (+) = (4:41 + A e [-11,1|mm+z is defined as:
We can rewrite 2/41 A441 M Cnew A;; A,e) Mi+1Cnew- Finally,
m4+1 m, + d₃
0,+1 A;+ia;
A++1 A M
where [] denotes concatenation of matrices along the column dimension.
B STATISTICAL ESTIMATION OF BOUNDS USING RANDOM PROJECTIONS
Here we describe how apply random projection approach from Wong et al. (2018) to estimate the bounds during training. While Wong et al. (2018) operate dual framework, their method to statistically estimate the bounds during training can also be applied in primal framework which we use in this paper. Recall that lower and upper bound for each neuron are computed as
4 = Di.j
A
(4)
k=1
Wig = Digi +
A
(5)
k=1
Thus, we need to compute |||:||ı which is L1 norm of each row in the matrix A, Wong et al. (2018) propose method, based the result from Li al. (2007), estimate ||A;|| using Cauchy random projections. Here A, is a matrix with d; rows and columns, where d; is dimensionality of the output vector in the i-th layer and m, is number of unit terms in the definition of region Ca The method of random projections samples standard Cauchy random matrix R of dimensions m. x k (k is number of projections) and then estimates ||Al| = modian[|A, R)). First, we expand A, as:
A [
W[[A;-1A M[-1]]
[WAA--A,--, W,M,-1]
-WA,,- 2 W.M
-W, -
A M.-s)..MM...
=
-,
W,M,-1]
= W W Mo.
W,M,-1
In the formula above. we Mo Ao. Now,
||A = W,
Moll: 11 +
+ [W ||
To calculate A,R we split R RRo Rr, R. 1) and compute:
= W, W MoR, A; W, W.2..
W,M,IRR--
Crucially, each summand can now be efficiently computed due to the associativity of matrix multi- plication by performing the multiplication from right left. Finally, compute the elementwise absolute value of A, R and take the median of each row, resulting in estimate of ||A:|] Using this approach, we obtain statistical estimate of bounds 4, 4g Equation
C ADDITIONAL EXPERIMENTAL RESULTS AND HYPERPARAMETERS
In this section we present additional results SVHN and MNIST datasets.
15

---

Published as a conference paper at ICLR 2020
C.I HYPERPARAMETERS
Here we list all hyperparameters used in our experiments.
Table 3: Hyperparameter values for CIFAR-10 with L perturbation 2/255
Hyperparameter
Value
L1 regularizer
le-5
éxtart
1.05
(2/255)
fine
1.1
batch size
100
ReLU stability regularizer
0.005
ReLU stability increase factor
1.5
Table 4: Hyperparameter values for CIFAR-10 with Lo perturbation 8/255
Hyperparameter
Value
L1 regularizer
5e-6
Esturt
1.05 (8/255)
Cine
1.2
batch size
150
ReLU stability regularizer
0.003
ReLU stability increase factor 1.5
For the experiments on CIFAR-10 dataset, we show hyperparameter values for Troc perturbation 2/255 in Table 3 and for 8/255 in Table 4. Across both experiments, we use 8 steps during the latent adversarial attack and each step size is 0.25 (where perturbations are normalized between -1 and 1). In both cases, use initial learning rate 0.03 and multiply learning rate by 0.5 every 10 epochs, after the initial 60 epochs. During the first 60 epochs, we mix the loss from the previous layer and the current layer (with current layer factor increasing linearily) and train each stage for total of 200 epochs. The rest of the hyperparameters are tuned on the validation set using Cantinez-Cantin al. (2018) for each experiment separately and shown in Table 3 and Table 4.
CIFAR-10
Table 5: Hyperparameter values for SVHN with L perturbation 0.01
Hyperparameter
Value
T regularizer
5e-5
start
0.01
Eine
1.2
batch size
200
ReLU stability regularizer
0.005
ReLU stability increase factor 1.5
SVHN For the experiments SVHN dataset, we use 40 steps for the latent adversarial attack with step size 0.035. We train using Adam (Kingma & Ba, 2014) with initial learning rate 0.0001 which is multiplied by 0.5 every 20 epochs, after the initial 60 epochs. Same for CIFAR-10, we mix the losses during the initial 60 epochs and train each stage for total of 200 epochs. We did not tune the hyperparameters for this experiment. The hyperparameters are shown in 5.
MNIST For the experiments on MNIST dataset, we use 40 steps for the latent adversarial attack with step size 0.035. We train using Adam (Kingma & Ba, 2014) with initial learning rate 0.0001 which multiplied by 0.5 every 10 epochs, after the initial mixing epochs. When training with perturbation 0.1 use 100 mixing and 300 total epochs, while for perturbation 0.3 use 60 mixing and 150 total epochs for each stage of the training. We did not tume the hyperparameters for this experiment. The hyperparameters are shown in Table 6 and Table 7.
16

---

Published as a conference paper at ICLR 2020
Table 6: Hyperparameter values for MNIST with Lee perturbation 0.1
Hyperparameter
Value
L regularizer
le-5
Start
1.5
Gine
1.0
batch size
100
ReLU stability regularizer
0.005
ReLU stability increase factor
1.5
Table 7: Hyperparameter values for MNIST with Lo perturbation 0.3
Hyperparameter
Value
Lı regularizer
le-5
Estart
0.3
Ginc
1.1
batch size
100
ReLU stability regularizer
0.0005
ReLU stability increase factor
1.0
C.2 EXPERIMENTAL EVALUATION ON SVHN AND MNIST
We also evaluated our method on SVHN and MNIST datasets.
SVHN
We evaluated our method on SVHN dataset. For this experiment, we used convolutional network with 2 convolutional layers of kernel size and stride with 32 and 64 filters respectively. These convolutional layers are followed by fully connected layer with 100 neurons. Each of the layers is followed by ReLU activation function. Results of this experiment We certified full SVHN test dataset consisting of 26 031 images. Our network has both, higher accuracy and higher certified robustness, than networks trained using prior approaches.
shown in Table 8.
In the next experiment, we evaluated on MNIST dataset. For this experiment, we used convolutional network with convolutional layers with kernel sizes and and strides followed by 1 fully connected layer. Each of the layers is followed by ReLU activation function. We certified the full test set, consisting of 10 000 images.
MNIST
For perturbation 0.1, convolutional layers have filter sizes 32 and 64, and fully connected layer has 100 neurons. Results are presented in Table Here, our numbers are comparable to those of state-of-the-art approaches.
For perturbation 0.3, convolutional layers have filter sizes and 128, and fully connected layer has 250 neurons. Results are presented in Table 10. Here, our certified robustness is lower than state-of-the-art. We believe this is due to the imprecise estimates of lower and upper bound random projections. This is also reflected in relatively poor performance of Wong al. (2018) who also rely on the same statistical estimates. Thus, for MNIST dataset and perturbation 0.3 is likely necessary to exact propagation instead of the estimates. However, this also induces large cost to the runtime, the most promising approach may be new convex relaxation which more memory efficient.
D REGULARIZATION
regularization mechanisms to make relaxation tighter, both previously proposed Xiao et al. (2019).
During training,
First, L1 norm regularization which is known induce sparsity in the weights of the net-
work. Xiao et al. (2019) has shown that weight sparsity helps to induce more stable ReLU units which in turn makes convex relaxation tighter (as for stable ReLU units it is already precise).
17

---

Published as a conference paper at ICLR 2020
Table Evaluation on SVHN dataset with Lee perturbation 0.01
Method
Accuracy (%)
Certified robustness (%)
Our work
88.5
70.2
Gowal et al. (2018)
85.2
62.4
Wong Kolter (2018) Dvijotham al. (2018a) 8a)
79.6
59.3
83.4
62.4
Table 9: Evaluation on MNIST dataset with Loo perturbation 0.1
Method
Accuracy (%)
Certified robustness (%)
Our work
99.2
97.1
Gowal et al. (2018)
98.9
97.7
Zhang et al. (2019)
99.0
94.4
Wong et al. (2018)
98.9
96.3
Dvijotham al. (201 8a)
98.8
95.6
Mirman et al. (2019)
98.7
95.8
Xiao et al. (2019)
99.0
95.6
Second, in the ë-th phase of training, we explicitly introduce loss based on the volume of convex region C++1. To make the relaxation tighter and minimize the volume, for each neuron in layer i i+ we add loss of the form max(O, (0,-1+1., max(0, ui+1.;). This loss corresponds to the area under ReLU relaxation, and derivation of this formula can be found in e.g. Singh et al. (2018) for derivation.
Table 10: Evaluation on MNIST dataset with Lox perturbation 0.3
Method
Accuracy (%)
Certified robustness (%)
Our work
97.3
85.7
Gowal al. (2018)
98.3
91.9
Zhang et al. (2020)
98.2
93.0
Wong al. (2018)
85.1
56.9
Mirman et al. (2019)
96.6
89.3
Xiao al. (2019)
97.3
80.7
18


Reviews:
[{"review_id": "ByxXM0cuKH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: the paper introduces a novel protocol for training neural networks that aims at leveraging the empirical benefits of adversarial training while allowing to certify the robustness of the network using the convex relation approach introduced by Wong & Kolter. The key ingredient is a novel algorithm for layer-wise adversarial (re-)training via convex relaxations. On CIFAR-10, the proposed protocol yields new state-of-the-art performance for certifying robustness against L_inf perturbations less than 2/255, and comparable performance over existing methods for perturbations less than 8/255 (where the comparison excludes randomized-smoothing based approaches as proposed by Cohen et al.).\n\nThe proposed methodology seems original and novel. The concept of latent adversarial examples, the layer-wise provable optimization techniques and the sparse representation trick are interesting in their own regard and could be valuable ingredients for future work in this direction. The improvement over the state-of-the-art on CIFAR-10 for perturbations less than 2/255 is significant (although I wouldn't call it substantial). For perturbations less than 8/255 the picture is less clear. The authors' explanation that they couldn't achieve state-of-the-art certified robustness because of smaller network capacity makes sense, however, it also highlights that their protocol doesn't scale as well as previous approaches.\n\nI am not concerned about the missing comparison with randomized smoothing-based approaches (I find the rationale provided in Section 2 convincing).\n\nThe discussion of the relatively weak performance of previous provable defenses on page 3 is a bit vague, e.g. the statement that \"the way these methods construct the loss makes the relationship between the loss and the network parameters significantly more complex than in standard training\", thus causing the \"resulting optimization problem to be more difficult\". To me, these are one and the same thing, and a bit more rigour in the argumentation would be advisable here, in my opinion.\n\n-------------\n\nI acknowledge I have read the authors' response and also the other reviews/comments which confirm my opinion that this paper is worthy to be published at ICLR.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "BJgNNQyF5r", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper was very clearly written and easy to follow. Kudos to the authors. In particular, the experimental evaluation section was exceptionally clear. Thanks to the authors for making the paper so easy to review. The “Main Contributions” section was excellent as well as it allows the reader to quickly understand what the paper is claiming.\n\nThe introduction & related work section was very clear, and seemed to quickly get the reader up to speed.\n\nMinor critiques:\n\n- It’s not clear to me that the network size is actually as impressive an improvement as is implied. Barring an extensive hyper-parameter search that demonstrated that this network architecture is the smallest possible that could achieve the presented results, I strongly suspect that applying techniques from papers like EfficientNet [1] or MobileNet would allow the authors of Mirman et. al (2018) to reduce the number of parameters required to achieve their results. I don’t think this takes away from the paper, though- the results are strong despite that. I would encourage the authors to weaken the claims that the only better network is 5 times larger. \n\n- In general, I would have liked to see more evaluation- e.g. I would have liked to see more results with a variety of perturbations (2 through 8, not just 2 & 8), and on a variety of datasets. \n\nQuestions to the authors:\n\n- How robust is the algorithm to architecture choice? \n- What happens if you change the test set? E.g. instead of evaluating on the first 1000 images, what if you evaluate on another random subset? Does that make a difference? I’m concerned that the subset of the test set the authors are using for evaluation isn’t representative of the entire test set. \n- Is the current architecture the largest network that can be run? I would be interested in seeing how network size affects the performance of your technique. \n- What hyper-parameter tuning did you do? What other network architectures did you try? \n- How do the comparison methods compare in terms of training time/machines used? E.g. do all the methods reported in Table 1 use similar amounts of computing power? \n\n\nOverall, this is a great paper, with some interesting results presented in a tight, clear manner. While I would like to see more experiments on larger datasets- e.g. ImageNet- the results seem solid and absolutely worthy of publication.\n\n[1]: https://arxiv.org/abs/1905.11946v2\n[2]: https://arxiv.org/abs/1704.04861", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "B1xSsNgtKS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\nSummary: \nThis paper provides a promising new general training methodology to obtain provably robust neural networks (towards adversarial input perturbations). The paper provides promising experimental results on CIFAR-10 by obtaining state-of-the-art certified accuracy while also simultaneously improving clean accuracy. The paper is overall well-written and the algorithm is clearly described. \n\nImportant questions to be answered: \nI find the need to clarify my understanding and request for more information in order to make a decision. \n\n--Methodology/motivation for the method: I am trying to understand abstractly what the proposed layerwise training is trying to optimize. To be concrete, let's compare to the relaxation of Wong and Kolter (which this paper uses in the instantiation of layerwise adversarial training). What's the exact difference?\n\nOne way to view this is the following: The same training objective, but a different way to optimize. The new proposal to train involves freezing weights until one layer iteratively starting from the input layer. It is possible that this kind of training provides some inductive bias in finding better solutions. Is this an appropriate understanding? \nHowever, the paper’s experimental results unfortunately change the certification procedure. In other words, they haven’t evaluated the same training objective as that of Wong and Kolter. Hence, it’s not clear if the gains are from the better networks, or better certification method, or network being better suited for certification by the method used. The phrase “same relaxation” is not appropriately used. Their certification procedure uses a different (and tighter) relaxation. \n\n\n--Effect on latent adversarial examples: I am unable to understand why this training procedure would reduce the number of latent adversarial examples. The definition of latent adversarial examples seems to suggest that it’s the gap between the actual set of activations corresponding to the input perturbations and the convex hull. However, the proposed layerwise adversarial training procedure involves replacing the actual set S_i with the convex hull C_i when freezing things till below i-1. I do not follow how the proposed method tries to make C_i = S_i. Implicitly the optimization objective does try to make C_i small because the bounds being optimized are tighter when C_i is small. But this is true even for normal certified training, and not sure what changes in the new training procedure.\n\n\nSpecific experimental results that would help: \n--Certified accuracy on using the same LP based certification procedure used in Wong and Kolter with the new layerwise trained networks\n--The paper’s own certification procedure (a combination of previous methods) on the network from Wong and Kolter or a note on why that doesn’t apply (if it doesn’t)\n--The paper currently provides only one data point to suggest this training method is superior. Would be good to try SVHN or MNIST. MNIST is perhaps “essentially” solved for small \\eps. But would be good to see if the training method offers gains at larger \\eps. In general, would be good to see more consistent gains. \n--The paper reports results on first 1000 examples of CIFAR10 test set. From my personal experience, there is a lot of variability in the robustness of test examples when evaluated on 1000 random test instances. Especially since the paper doesn't take a random subset, it might be good to make sure the gains are consistent on some other subset. The Wong et al. baseline is evaluated on the entire test set for example, and hence might not be a fair comparison? What's the Wong et al. accuracy on just the first 1000 test exampes\n\nOverall, I am leaning towards accept but need some conceptual and empirical clarification from the authors (detailed above). \n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers develop a novel technique for training neural networks that are provably robust to adversarial attacks, by combining provable defenses using convex relaxations with latent adversarial attacks that lie in the gap between the convex relaxation and the true realizable set of activations at a layer of the network. The authors show that the resulting procedure is computationally efficient and able to train neural networks to attain SOTA provable robustness to adversarial attacks.

The paper is well written and clearly explains an interesting idea, backed by thorough experiments. The reviewers were in consensus on acceptance and relatively minor concerns were clearly addressed in the rebuttal phase.

Hence, I strongly recommend acceptance.
Decision: Accept (Talk)