Towards Stable and Efficient Training of Verifiably Robust Neural Networks
Authors: Huan Zhang
Hongge Chen
Chaowei Xiao
Sven Gowal
Robert Stanforth
Bo Li
Duane Boning
Cho-Jui Hsieh
Venue:  (2020)
Keywords: Robust Neural Networks
Verifiable Training
Certified Adversarial Defense

Abstract: Training neural networks with verifiable robustness guarantees is challenging. Several existing approaches utilize linear relaxation based neural network output bounds under perturbation, but they can slow down training by a factor of hundreds depending on the underlying network architectures. Meanwhile, interval bound propagation (IBP) based training is efficient and significantly outperforms linear relaxation based methods on many tasks, yet it may suffer from stability issues since the bounds are much looser especially at the beginning of training. In this paper, we propose a new certified adversarial training method, CROWN-IBP, by combining the fast IBP bounds in a forward bounding pass and a tight linear relaxation based bound, CROWN, in a backward bounding pass. CROWN-IBP is computationally efficient and consistently outperforms IBP baselines on training verifiably robust neural networks. We conduct large scale experiments on MNIST and CIFAR datasets, and outperform all previous linear relaxation and bound propagation based certified defenses in L_inf robustness.
Notably, we achieve 7.02% verified test error on MNIST at epsilon=0.3, and 66.94% on CIFAR-10 with epsilon=8/255.

Published as a conference paper at ICLR 2020
TOWARDS STABLE AND EFFICIENT TRAINING OF VERIFIABLY ROBUST NEURAL NETWORKS
Huan Zhang Hongge Chen Chaowei Xiao
Sven Gowal
Robert Stanforth
Bo Li Duane Boning² Cho-Jui Hsieh'
UCLA MIT University of Michigan DDepMiind UIUC
huan@huan-zhane zhang com, chenhg@mit edu, xiaocx@umich. edu sgowal@google. com, stanforth@google.com lbo@illincis edu, boningemtl ..miiimiiii mit. edu, chohsieh@cs. ucla.
ABSTRACT
Training neural networks with verifiable robustness guarantees is challenging. Several existing approaches utilize linear relaxation based neural network output bounds under perturbation, but they can slow down training by factor of hundreds depending on the underlying network architectures. Meanwhile, interval bound propagation (IBP) based training is efficient and significantly outperforms linear relaxation based methods on many tasks, yet it may suffer from stability issues since the bounds are much looser especially at the beginning of training. In this paper, propose new certified adversarial training method, CROWN-IBP, by combining the fast IBP bounds in a forward bounding pass and a tight linear relaxation based bound, CROWN, in backward bounding pass. CROWN-IBI is computationally efficient and consistently outperforms IBP baselines on training MNIST
verifiably robust neural networks. We conduct large scale experiments and CIFAR datasets, and outperform all previous linear relaxation and bound propagation based certified defenses in foo robustness. Notably, we achieve 7.02% verified test error on MNIST at 0.3, and 66.94% on CIFAR- 10 with = 8/255.
INTRODUCTION
The success of deep neural networks (DNNs) has motivated their deployment in some safety-critical environments, such as autonomous driving and facial recognition systems. Applications in these areas make understanding the robustness and security of deep neural networks urgently needed, especially their resilience under malicious, finely crafted inputs. Unfortunately. the performance of DNNs are often so brittle that even imperceptibly modified inputs, also known adversarial examples, are able to completely break the model (Goodfellow et 2015 Szegedy et al. (201)). The robustness of DNNs under adversarial examples is well-studied from both attack (crafting powerful adversarial examples) and defence (making the model more robust) perspectives (Athalye al.
2018: Carlini & Wagner 2017a b. Goodfellow et al. 2015 Madry et al. 2018 Papernot et al. 2016 Xiao et al. 2019b; 2018 Eykholt et al.) 2018 Chen et al. 2018 Xu et al. 2018: Zhang et al. 2019b). Recently, has been shown that defending against adversarial examples is a very difficult task, especially under strong and adaptive attacks. Early defenses such distillation (Papernot et al.
2016) have been broken by stronger attacks like C&W (Carlini & Wagner (017b). Many defense
methods have been proposed recently (Guo al. 2018 Song al. 2017: Buckman al. 2018 Ma
et al. 2018 Samangouei et al. 2018 Xiao et al. 201 8a 2019a), but their robustness improvement
cannot be certified no provable guarantees can be given to verify their robustness. In fact. most of
these uncertified defenses become vulnerable under stronger attacks (Athalye et al. 2018 He et al.
2017
Several recent works in the literature seeking to give provable guarantees on the robustness perfor- mance, such as linear relaxations (Wong& Kolter 2018 Mirman et al.) 2018 Wang et al.) [018a]] Dvijotham et al. 20181 2018b; Weng al. 2018 Zhang al. 2018), interval bound propagation (Mirman et al. 2018 Gowal et al. 2018), ReLU stability regularization (Xiao et al., 2019c), and distributionally
* Work partially done during an internship DeepMind.

---

Published as a conference paper at ICLR 2020
robust optimization (Sinha et al. 2018 and semidefinite relaxations (Raghunathan al. 2018a 8a Dvijotham et al.). Linear relaxations of neural networks, first proposed by Wong & Kolter (0118). 8). one of the most popular categories among these certified defences. They use the dual of linear programming or several similar approaches to provide a linear relaxation of the network (referred to as "convex adversarial polytope") and the resulting bounds are tractable for robust optimization. However, these methods are both computationally and memory intensive, and can increase model training time by a factor of hundreds. On the other hand, interval bound propagation (IBP) is simple and efficient method for training verifiable neural networks (Gowal et al. 2018), which achieved state-of- the art verified error on many datasets. However, since the IBP bounds are very loose during the initial phase of training, the training procedure can be unstable and sensitive to hyperparameters.
In this paper, we first discuss the strengths and weakness of existing linear relaxation based and interval bound propagation based certified robust training methods. Then we propose new certified robust training method, CROWN-IBP. which marries the efficiency of IBP and the tightness of a linear relaxation based verification bound, CROWN (Zhang et al. 2018) CROWN-IBP bound propagation involves a IBP based fast forward bounding pass, and a tight convex relaxation based backward bounding pass (CROWN) which scales linearly with the size of neural network output and is very efficient for problems with low output dimensions. Additional, CROWN-IBP provides flexibility for exploiting the strengths of both IBP and convex relaxation based verifiable training methods.
The efficiency, tightness and flexibility of CROWN-IBP allow it to outperform state-of-ther -orthef-- methods for training verifiable neural networks with for robustness under all settings MNIST and CIFAR- 10 datasets. In our experiment, on MNIST dataset we reach 7.02% and 22.06% IBP verified error under &oo distortions e 0.3 and e 0.4, respectively, outperforming the ofate-of-the-art baseline results by IBP (8. 55% and 15.01%) On CIFAR-IO, at 255 CROWN-IBP decreases the verified error from 55.88% (IBP) to 46.03% and matches convex relaxation based methods; a larger c, CROWN-IBP outperforms all other methods with a noticeable margin.
2
RELATED WORK AND BACKGROUND
2.1 ROBUSTNESS VERIFICATION AND RELAXATIONS OF NEURAL NETWORKS
Neural network robustness verification algorithms seek for upper and lower bounds of an output neuron for all possible inputs within a set S, typically a norm bounded perturbation. Most importantly, the margins between the ground-truth class and any other classes determine model robustness. However, it has already been shown that finding the exact output range is non-convex problem and NP-complete (Katz et al. 2017 Weng et al. 2018). Therefore, recent works resorted to giving relatively tight but computationally tractable bounds of the range range with necessary relaxations of the original problem. Many of these robustness verification approaches are based on linear relaxations of non-linear units in neural networks, including CROWN (Zhang al., 2018)), DeepPoly (Singh let al. (211). Fast-L.in (Weng et al. 2018). DeepZ. (Singh et al.] 2018) and Neurify (Wang et al. 2018b). We refer the readers (Salman et al. (019b) for a comprehensive survey on this topic. After linear relaxation, they bound the output of a neural network f((-) by linear upper/lower hyper-planes:
A..Ar by S f1(00 + Ax) S A,, + by
(1)
where row vector A... W ((--1)
( (()()) is the product of the network weight matrices ( and diagonal matrices ( reflecting the ReLU relaxations for output neuron é; by
a): Qin al. (2019) by; Dvijotham et al. propose semidefinite relaxations which are tighter compared to linear relaxation based methods, but computationally expensive. Bounds on neural network local Lipschitz constant can also be used for verification (Zhang al. [019c] Hein & Andriushchenko (017). Besides these deterministic verification approaches, randomized smoothing can be used to certify the robustness of any model in a probabilistic manner (Cohen et al. 2019. (Salman et al. 201 Lecuyer et al. 2018 Li et al. 2018).
and by are two bias terms unrelated Az. Additionally, Dvijotham et al. (2018c Audittonallyy DDijotaaaa
solve the Lagrangian dual of verification problem: RRahunathhn et al. (2018a
2.2 ROBUST OPTIMIZATION AND VERIFIABLE ADVERSARIAL DEFENSE
To improve the robustness of neural networks against adversarial perturbations, natural idea is to generate adversarial examples by attacking the network and then use them to augment the training set (Kurakin et al. 2017). More recently. Madry et al. (2018) showed that adversarial training can
2

---

Published as a conference paper at ICLR 2020
be formulated solving minimax robust optimization problem in 2.. Given model with parameter 8, loss function L, and training data distribution X, the training algorithm aims to minimize the robust loss, which is defined the maximum loss within neighborhood {z + 6|6 S} of each data point x, leading to the following robust optimization problem:
min
E (2.D)EX
max Lxx + 0; 0) ÓES
Madry et al. (0118) proposed to use projected gradient descent (PGD) to approximately solve the inner max and then use the loss on the perturbed example x + to update the model. Networks trained by this procedure achieve state-of-the-art test accuracy under strong attacks (Athalye et al. 2018: Wang et al.) 2018a Zheng et al. 2018). Despite being robust under strong attacks, models obtained by this PGD-based adversarial training do not have verified enror guarantees. Due to the nonconvexity of neural networks, PGD attack can only compute the lower bound of robust loss (the inner maximization problem). Minimizing lower bound of the inner max cannot guarantee (2) is minimized. In other words, even PGD-attace cannot find a perturbation with large loss, that does not mean there exists no such perturbation. This becomes problematic in safety-critical applications since those models need certified safery.
Verifiable adversarial training methods, the other hand, aim to obtain network with good robustness that can be verified efficiently. This can be done by combining adversarial training and robustness verification-instee adversarial training uses a verification method to find an upper bound of the inner max, and then update the parameters based on this upper bound of robust loss. Minimizing an upper bound of the inner max guarantees to minimize the robust loss. There are two certified robust training methods that are related to our work and we describe them in detail below.
of using PGD to find lower bound of inner max, certified
Linear Relaxation Based Verifiable Adversarial Training. One of the most popular verifiable adversarial training method was proposed in (Wong & Kolter (2018) using linear relaxations of neural networks to give upper bound of the inner max. Other similar approaches include Mirman it al. 2018): Waan et al. (2018a); Dvijotham et al. (2018b). Since the bound propagation process of a convex adversarial polytope too expensive, several methods were proposed to improve its efficiency, like Cauchy projection (Wong et al. 2018) and dynamic mixed training (Wang et al. 2018a). However, even with these speed-ups, the training process is still slow. Also, this method may significantly reduce model's standard accuracy (accuracy natural, unmodified test set). As we will demonstrate shortly, we find that this method tends to over-regularize the network during training. which is harmful for obtaining good accuracy.
include/Mirman
Interval Bound Propagation (IBP). Interval Bound Propagation (IBP) uses a very simple rule to compute the pre-activation outer bounds for each layer of the neural network. Unlike linear relaxation based methods, IBP does not relax ReLU neurons and does not consider the correlations between neurons of different layers, yielding much looser bounds. Mirman et al. (2018) proposed a variety of abstract domains to give sound vver-approximations for neural networks, including the "Box/Interval Domain" (referred to as IBP in Gowal et al. ( (2018) and showed that it could scale to much larger networks than other works (Raghunathan et al. 2018a 8a) could at the time. Gowal et al. (2018) demonstrated that IBP could outperform many saae-ol-the-ee more precise approximations for the last linear layer and better training schemes. However, IBP can be unstable to use and hard to tune in practice, since the bounds can be very loose especially during the initial phase of training, posing a challenge to the optimizer. To mitigate instability, Gowal et al. (2018) use mixture of regular and minimax robust cross-entropy loss as the model's training loss.
results by a large margin with
3 METHODOLOGG
Notation.
We define an L-layer feed-forward neural network recursively as:
f(x) ((4)
R (1) / (2()), Vi (1....,L.11,
201) (00
b0) (
((0) E R
where h( (x) = x. no represents input dimension and n,, is the number of classes, or is an element- wise activation function. We to represent pre-activation neuron values and h to represent
3

---

Published as a conference paper at ICLR 2020
Dataset
(foc norm)
CAP verified error
CROWN verified error
IBP verified error
0.1
8.90%
7.05%
5,83%
0.2
45.37%
24.17%
7.37%
MNIST
0.3
97.77%
65.26%
10.68%
0.4
99.98%
99.57%
16.76%
Fashion-MNIST
0.1
44.64%
36.85%
23.49%
2/255
62.94%
60.83%
58.75%
CIFAR-10
8/255
91.44%
82.68%
73.34%
IBP trained models have low IBP verified errors but when verified with a typically much tighter bound, including convex adversarial polytope (CAP) (Wong et al. 2018) and CROWN (Zhang) et al. 2018), the verified errors increase significantly. CROWN is generally tighter than convex adversarial polytope however the gap between CROWN and IBP is still large, especially large c.
Table 1:
We used a 4-layer CNN network for all datasets to compute these bounds."
post-activation neuron values. Consider an input example æy with ground-truth label yk., we define a set of S(æ e) { ||| æ æx S E} and we desire robust network to have the property yh = argmax,lffee (x))l for all æ E S. We define element-wise upper and lower bounds for 20) and h09) 2 200) s z(1) and ( (0)
Verification Specifications. Neural network verification literature typically defines specification vector c E R" that gives a linear combination for neural network output: c' f(z). In robustness verification, typically we C; = 1 where i is the ground truth class label, Cj -1 where j is the attack target label and other elements in are O. This represents the margin between class and class For ni class classifier and a given label y, define specification matrix C E Ro
1,
if j y, o y (output of ground truth class)
1, if = j. A y (output of other classes, negated)
(3)
0,
otherwise (note that the y-th row contains all 0)
Importantly, each element in vector m == Cf(()) E RT gives us margins between class y and all other classes. We define the lower bound of (z for all xs 5(xx, m( c). which is very important quantity: when all elements of m( <) > 0, 2t is verifiably robust for any perturbation with &oo norm less than e. m E) can be obtained by neural network verification algorithm, such as convex adversarial polytope, IBP, or CROWN. Additionally, Wong & Kolter (2018) showed that for cross-entropy (CE) loss:
max (E
L(f(x)); y: < L( L(-m m DR 0);
(4)
gives us the opportunity to solve the robust optimization problem via minimizing this tractable
upper bound of inner-max This guarantees that max ((m..)) L(f (z)
(z), v) is also minimized.
3.1 ANALYSIS OF IBP AND LINEAR RELAXATION BASED VERIFIABLE TRAINING METHODS
Interval Bound Propagation (IBP) Interval Bound Propagation (IBP) uses simple bound propa- S x S zu element-wise. For affine layers we have:
gation rule. For the input layer we set æ7
(1 (-1) 1)
+ (1-1)
(1-1)
h (1-1
z(1) = ((())
+
(
2 + 600
(5)
2
2 w()) 1
(1-1)
+ 4
(111)
(1-1)
11 (1-1)
(())
B())
(6)
2
where ((() takes element-wiss absolute value. Note that (0) = ay and (1
= x
And for
element-wise monotonic increasing activation functions
(2())
h 0
We implemented CROWN with efficient CNN support on GPUs: https//ggihub..om/uuunnlitn hwtp:///nnnng////RRR-///---
For inputs bounded with general norms, IBP can be applied as long as this norm can be converted to per-neuron intervals after the first afline layer. For example, for f norms (1 S p oc) Hölder's 's inequality can be applied the first affine layer obtain F. and (1), and IBP rule for later layers do not change.
4

---

Published as a conference paper at ICLR 2020
We found that IBP can be viewed as training simple augmented ReLU network which is friendly to optimizers (see Appendix for more discussions). We also found that a network trained using IBP
can obtain good verified errors when verified using IBP, but it can get much worse verified errors using linear relaxation based verification methods, including convex adversarial polytope (CAP) by Wong & Kolter (2018) (equivalently, Fast-Lin by WWnn al. (20T8)) and CROWN (Zhang et al. 2018). Table demonssrateeee that this gap can be very large on large
However, IBP is very loose bound during the initial phase of training, which makes training unstable and hard to tune; purely using IBP frequently leads to divergence. Gowal et al. (2018) proposed to
use a schedule where e is gradually increased during training. and a mixture of robust cross-entropy loss with natural cross-entropy loss as the objective to stabilize training:
kI 0) + (1 - R) (000--mmpaa,ee (2, e); 0)
min 8 (m.))EX
Issues with linear relaxation based training. Since IBP hugely outperforms linear relaxation based methods in the recent work (Gowal et al., 2018) in many settings, want to under- stand what is going wrong with linear relaxation based methods. We found that, empirically, the norm of the weights in the models produced by linear relaxation based methods such as (Wong) & Kolter 2018) and (Wong et al., (018)) does not change or even decreases during training. In Figure we train a small 4-layer MNIST model and we linearly increase from 0 to 0.3 in 60 epochs. We plot the l. induced norm of the 2nd CNN layer during the training process of CROWN-IBP and (Wong et al. 2018). The norm of weight matrix using (Wong et al. 2018)
2.0
45
Wong et al. verified arror CROWN-IBI verified error
40
Verrified Error
0.8
Wong weights
CROWN-IBP weights norm
35
Second layer wele weights
does not increase. When becomes larger (roughly at 0.2, epoch 40), the norm even starts to decrease slightly, indicating that the model is forced to learn smaller norm weights. Mcanwhile, the verified error also starts to ramp up possibly due to the lack of capacity. We conjecture that linear relaxation based training over-regularizes the model, especially at larger e. However, in CROWN-IBP, the norm of weight matrices keep increasing during the training process, and verifiable error does not significantly increase when c reaches 0.3.
0.6
Wong 20.
verified emr, 0,50
20
0.2
10
verilied 0.11
0.0
60
80
100
Epoch
Figure 1: Verified error and 2nd CNN layer's Eoo induced norm for a model trained using (Wong et al. 2018 and CROWN-IBP. is increased from 0 to 0.3 in 60 epochs.
Another issue with current linear relaxation based training or verification methods is their high computational and memory cost, and poor scalability. For the small network in Figure [ convex adversarial polytope (with 50 random Cauchy projections) is 8 times slower and takes times more memory than CROWN-IBP (without using random projections). Convex adversarial polytope scales even worse for larger networks; see Appendix J for a comparison.
3.2 THE PROPOSED ALGORITHM: CROWN-IBP
Overview. We have reviewed IBP and linear relaxation based methods above. As shown in Gowal al. (2018) IBP performs well at large with much smaller verified error, and also efficiently scales to large networks; however, it can be sensitive to hyperparameters due to its very imprecise bound at the beginning phase of training. On the other hand, linear relaxation based methods can give tighter lower bounds at the cost of high computational expenses, but it over-regularizes the network at large e and forbids us to achieve good standard and verified accuracy. We propose CROWN-IBP, a new certified defense where we optimize the following problem (0 represents the network parameters):
IBP bound
CROWN-IBP bound
min E N L(a; +(1 x)) L( (11 (m.))x
3 M (x, e) + (BmcRowx-Bgpaa e)); ys 0)
natural loss
robust loss
where our lower bound of margin m (x. c) is a combination of two bounds with different natures: IBP, and a CROWN-style bound (which will be detailed below); L is the cross-entropy loss. Note that the combination is inside the loss function and is thus still a valid lower bound; thus (4) still holds and are within the minimax robust optimization theoretical framework. Similar to IBP and
5

---

Published as a conference paper at ICLR 2020
TRADES Zhang et al. 2019a), we use mixture of natural and robust training loss with parameter R, allowing us to explicitly trade-off between clean accuracy and verified accuracy.
In high level, the computation of the lower bounds of CROWN-IBP (TeCROWN x e)) consists of IBP bound propagation in a forward bounding pass and CROWN-style bound propagation in a backward bounding pass. We discuss the details of CROWN-IBP algorithm below.
Forward Bound Propagation in CROWN-IBP. In CROWN-IBP, we first obtain z00) and 20) for all layers by applying ( (6) and (7) Then we will obtain Mise (2, e) = 2 2442 (assuming C' is merged into W(D).. The time complexity is comparable to two forward propagation passes of the network.
Linear Relaxation of ReLU neurons Given 20)) and z(1) computed in the previous step, we first check if some neurons always active (z 0) or always inactive (3 < 0), since they are effectively linear and no relaxations are needed. For the remaining unstable neurons, (Zhang et al.
(2018); Wong & Kolter (2018) give linear relaxation for ReLU activation function:
(1) 2k
(1) 0322 k I (26))) <
(1)
k
2k
(1)
!1) for all & E [mt] and 2
< 0
<
(10)
Z
where 0 S oz I 1: Zhang et al.
2018 propose to adaptively select ag when
2k 1 (1)
and 0 otherwise, which minimizes the relaxation error. Following (IO), for an input vector 20) we effectively replace the ReLU layer with linear layer, giving upper or lower bounds of the output:
D 20) < {z S D 20
(11)
where ( and D are two diagonal matrices representing the "weights" of the relaxed ReLU layer. Other general activation functions can be supported similarly, In the following we focus on conceptually presenting the algorithm, while more details of each term can be found in the Appendix.
Backward Bound Propagation in CROWN-IBP. Unlike IBP, CROWN-style bounds start bound- ing from the last layer, so we refer to it as backward bound propagation (not to be confused with the pack-propagation algorithm to obtain gradients). Suppose we want to obtain the lower bound (L) (we assume the specification matrix C' has been merged into W(4),. The input to layer ((() is 0(2(4-1)), which can be bounded linearly by Eq. (II). CROWN-style
[mcRowN-IBe (z, +) }} == 2i
bounds choose the lower bound of (= (() (LHS of (TT) when w:()) is positive, and choose the i,k
upper bound otherwise. We then merge ((1) and the linearized ReLU layer together and define:
(1-1) w Di(L-1)
where Dirk k,k
1.)--1)
D &,k
D
1-
(L-1) &.k
if
K if
(L) i
(L)
(12)
5,k
Now we have lower bound 2(4 A 21-1)) + b((-1)
(L) where
6(4-1)
S
2
Exwgg W + ((+) collects all terms not related to (1,-1), Note that the diagonal matrix
DilL--) implicitly depends on i. Then, we merge A.. (L-1) with the next linear layer, which is straight forward by plugging in 2 (L-11) = w(L-1)o(=(L-2)) b(L-1))
(L) - w((-1) (2 (L-()) + A ff- b(L-1) + b, (!T-1)
Then we continue to unfold the next ReLU layer o (1-22) using its linear relaxations, and compute
a new A (L-2) E x matrix, with (2-2) A. ! ((L-)) in a similar manner
as in 12). Along with the bound propagation process, we need to compute a series of matrices, A
(0), where (! A (1+1) (((DDD
Ro and A A w()))
D 1 D (L-)) (L-2)... ... (()), At this point, we merged all layers of the (L) (0)
network into linear layer: 2, A x + h, where collects all terms not related to A lower (L) bound for 2, with Φy < x S xy can then be easily given as
mplk = 2t = A (0) bb>b>> Σ
(L)
K. <D A ΦU.K + ERAO A +6 (13)

---

Published as a conference paper at ICLR 2020
For ReLU networks, convex adversarial polytope (Wong & Kolter 2018) uses very similar bound propagation procedure. CROWN-style bounds allow an adaptive selection of a, in (TO), thus often gives better bounds (e.g., see Table D. We give details on each term in Appendix
Computational Cost. Ordinary CROWN (Zhang et al. 2018) and convex adversarial poly-
tope (Wong& & Kolter 2018 use (33 compute all intermediate layer's 2!(T) and z((² (m E [4], by considering Wmm) as the final layer of the network. For each layer m, we need a different set of m A matrices, defined as A A..(1), E {m - 1, 0}. This causes three computational issues:
Unlike the last layer W(L), an intermediate layer W(m) typically has much larger output have large dimensions 12 Xn;
dimension nmm > R thus all AT,.()) E (Am.(m-1),.. Am.(())
Computation of all A,!(l) matrices expensive. Suppose the network has n neurons for all L 1 intermediate and input layers and n < n neurons for the output layer (assuming L 2 2), the time complexity of ordinary CROWN or convex adversarial polytope is O In3 + (I. - 1 1)mgn²) O((I-1) + (L. - 1)m = LnLn2 (In + n=))). A ordinary forward propagation only takes O[In²) time per example, thus ordinary CROWN does not scale up to large networks for training. due to its quadratic dependency in L and extra Ln times overhead.
When both w and ((11)) represent convolutional layers with small kernel tensors K00 and K(--)), there are no efficient GPU operations to form the matrix D() using K(l) and k('-)) Existing implementations either unfold at least one of the convolutional kernels to fully connected weights, or use sparse matrices to represent W and W(l-1), They suffer from poor hardware efficiency on GPUs.
In CROWN-IBP, we use IBP to obtain bounds of intermediate layers, which takes only twice the regular forward propagate time (OnLn)), thus we do not have the first and second issues. The time complexity of the backward bound propagation in CROWN-IBP is O((L 1)22?²) only ny times slower than forward propagation and significantly more scalable than ordinary CROWN (which Lm times slower than forward propagation, where typically > nt... The third convolution issue is also not a concern, since we start from the last specification layer ((L) which is small fully connected layer. Suppose we need to compute ((4)) with kernel K(L-1), we can efficiently compute (D(L-)))(((-))ww> transposed convolution operator with kernel K (4-1), without unfolding any convoluational layers. Conceptually, the backward pass of CROWN-IBP propagates a small specification matrix W(L) backwards, replacing affine layers with their transposed operators, and activation function layers with a diagonal matrix product. This allows efficient implementation and better scalability.
and ((--1) is a convolutional layer on GPUs using the
Benefits of CROWN-IBP. Tightness, efficiency and flexibility are unique benefits of CROWN-IBP:
CROWN-IBP is based on CROWN, a tight linear relaxation based lower bound which can greatly improve the quality of bounds obtained by IBP to guide verifiable training and improve stabability;
CROWN-IBP avoids the high computational cost of convex relaxation based methods the time complexity is reduced from O(Ln² + rT))) to OLLLnnz) well suited to problems where the output size nı, is much smaller than input and intermediate layers' sizes; also, there is no quadratic dependency on L. Thus, CROWN-IBP is efficient on relatively large networks;
9) is strictly more general than IBP and allows the flexibility to exploit the strength from both IBP (good for large c) and convex relaxation based methods (good for small c). We can slowly decrease /3 to 0 during training to avoid the over-regularization problem, yet keeping the initial training of IBP more stable by providing a much tighter bound; we can also keep B which helps to outperform convex relaxation based methods in small 6 regime (e.g.. e = 2/255 on CIF.R-10).
The objective
4 EXPERIMENTS
Models and training schedules. We evaluate CROWN-IBP on three models that are similar to the models used in (Gowal et al., 2018) MNIST and CIFAR- 10 datasets with different for perturbation norms. Here we denote the small. medium and large models in Gowal et al. (2018) as DM-small, DM-medium and DM-lee During training, first warm up (regular training without robust loss)
7

---

Published as a conference paper at ICLR 2020
for fixed number of epochs and then increase from 0 to Grain using ramp-up schedule of R epochs. Similar techniques are also used in many other works (Wong et al. 2018 Wang et al. 2018a Sa Gowal
et al. 2018). For both IBP and CROWN-IBP, natural cross-entropy (CE) loss with weight (as in
Eq ( may be added, and K is scheduled to linearly decrease from Aisan to Kend within R ramp-up epochs. Gowal al. (20T8) used Vistunt 1 and fiend = 0.5. To understand the trade-off between verified accuracy and standard (clean) accuracy, we explore two more settings: Kstart Kend 0 Kend = 0. For B, a linear schedule during the ramp-up period is used, but we always set Sstant = 1 and Bend 0, except that we set Ssturt Send = 1 for CIFAR-10 10 at 255 Detailed model structures and hyperparameters are in Appendix C
(without natural CE loss) and Kistart
Our training code for
IBP and CROWN-IBP, and pre-trained models are publicly available
Metries. Verified error is the percentage of test examples where at least one element in the lower bounds m m <) is < 0. It is an guaranteed upper bound of test enror under any Lx perturbations. We obtain m m e) using IBP or CROWN-IBP (Eq. 13). We also report standard (clean) errors and errors under 200-step PGD attack. PGD errors are lower bounds of test errors under &o perturbations.
Comparison to IBP. Table 2 represents the standard, verified and PGD errors under different for each dataset with different a settings. We test CROWN-IBP on the same model structures in Table of Gowal al. (2018). These three models' architectures are presented in Table A in the Appendix. Here we only report the DM-large model structure in as it performs best under all setttings: small and medium models are deferred to Table in the Appendix. When both Kstart Kend = no natural CE loss is added and the model focuses on minimizing verified error, but the lack of natural CE loss may lead to unstable training, especially for IBP: the Kutann = 1, Kend = 0.5 setting emphasizes on minimizing standard error, usually at the cost of slightly higher verified error rates. Katart 1, Aind = 0 typically achieves the best balance. We can observe that under the same K settings, CROWN-IBP outperforms IBP in both standard error and verified error. The benefits of CROWN-IBP is significant especially when model is large and E is large. We highlight that CROWN-IBP reduces the verified error rate obtained by IBP from 8.21 % to 7.02% on MNIST at 0.3 and from 55.88% to 46.03% on CIFAR- 10 at c = 2/255 (it is the first time that an IBP based method outperforms results from (Wong et al. 2018 and our model also has better standard error). We also note that are the first to obtain verifiable bound on CIFAR- at c = 16/255.
Trade-off' Between Standard Accuracy and Verified Ac- curacy. To show the trade-off between standard and ver- ified accuracy, we evaluate DM-large CIFAR-10 model with Gest = 8/255 under different к settings, while keeping all other hyperparameters unchanged. For each Kend {0.5, 0.25, 0}, we uniformly choose 11 Aistart E [1, Kend] while keeping all other typer-parameter larger Katart or Kend tends to produce better standard errors, and we can explicitly control the trade-off between standard accuracy and verified accuracy. In Figure 2 we plot the stan- dard and verified errors of IBP and CROWN-IBP trained models with different K settings. Each cluster on the figure has 11 points, representing II different Kstar values. Models with lower verified errors tend to have higher standard er- rors. However, CROWN-IBE clearly outperforms IBP with improvement on both standard and verified accuracy. and pushes the Pareto front towards the lower left corner, indicating overall better performance. To reach the same verified error of 70%, CROWN-IBP can reduce standard error from roughly 55% to 45%.
73
Verified Error (96)
72
71
better
unchanged. A
20
69
68-
Clclers AP 0.35
67
Coclara AP; Auy
45
50
33
60
65
Standard (Clean) Error (%)
Figure 2: Standard and verified errors
of IBP and CROWN-IBP with differ- ent Kuaa and Kend values.
Training Stability. To discourage hand-tuning on small set of models and demonstrate the stability of CROWN-IBP over a broader range of models, we evaluate IBP and CROWN-IBP on variety of small and medium sized model architectures (18 for MNIST and 17 for CIF, detailed in Appendix D To evaluate training stability, we compare verified errors under different e ramp-up schedule length (Rt (30, 60, 90, 120) on CIFAR-10 and R {10, 30, 60) on MNIST)
TensorFlow implementation and pre-trained models: http:://ghhuu..ccmmm//eppnnniii/ hounteeeeeeee-ee---oeeeee proponddtrppgattioon Py PoTch implementation and pre-trained models: http:///ghibbbcmm//mmmm/g///////
8

---

Published as a conference paper at ICLR 2020
Table 2: The verified, standard (clean) and PGD attack errors for models trained using IBP and CROWN-IBP on MNIST and CI..R-10. We only present performance model DM-large here due to limited space (see Table foor a full comparison). CROWN-IBP outperforms IBP under all
settings, and achieves state-of-the-ar performance on both MNIST and CIFAR datasets for all c.
Dotaset
< Clau norm)
Training Method
schechiles
Model errons (%b
Best errees reported in litentture (%)
Standanl
Verifled
PGD
Source
Stundard
Verilied
2.75
2.02
Deromnn
1.2
Yiur 0.1
1.14
2.81
2.11
Allrer
2019
1.45
4.4
0.2
1.17
2.36
1.91
Wrnng 2f 2015
1.08
3.67
CROWN-IRP
0.5
0395
2.38
1.77
1.0
3,4
1.06
6.58
IRP
0.5
2.12
4.75
4.24
Xlio of ID 20152
1.9
10.21
0.2
2.74
5.46
4.89
0.4
2.34
5.15
4.90
CROWN-IBP
4.13
3.45
9:76
8.42
Goeal et al. 2018
1.66
8:21"
MINIST
0.3
IBP
0.50
2.12
2.74
8.73
8.47
7.37
6.78
Wone ol
2019
2013
14.87
2.67
19.32
43.1
0.4
7.65
6.90
7.02
7.03
3:45
16.19
12.73
Gowal et al.
2018
1.66
15.01"
IHP
0.5
2.12
15.37
11.05
0.4
14.80
11.14
Saxa
12.74
10.39
CROWN-IB
12:59
9.58
2.17
12.06
9.47
38.54
55.21
49.72
Gooal et al.
2018
29. 84
55 88"88"
IBP
33.77
58.48
50.54
Vatrman
2010
38.0
47.8
Wonz Kf
2.2
46.03
4019c
CROWN- IBP
0.5
26.19
50.53
40.24
28.91
46.43
00.27
59.11
71.22
68.96
Goeal al.
2015
50.51
(68.44)1
Denolbam
54.02
66.94
65.42
Wolls 2t
2013
71.33
78.22
CROWN- IBP
0.5
45.117
69.55
65.74
Miriian 2010
59.8
76.8
55.27
67.26
65.71
16.97
best verilfedd and standand emerr (66.068) are hemer than Wong el 2018 at vin. despite our creing WWie langer.
205
68.88
78.91
76.95
Gma 17.89
67.17
77.27
75.76
CROWN IBP
0.5
56.23
78.20
74.87
66.06
76.80
75.23
Verifted errors reported Table af cicaall et 2018 are evallutted using mixed integes programming (MIP) and lincar programmiing (LPP, which strictly smaller than IBP verified erroes but computtaionlll expensive. For a comparison, we use the IBP verifedd errors repected in their Table 3. According direct communications with Gooal et 2018 achieving the 44% IBP verified
PGD adversarial training loss. Without adding PGD, the verified ernor 72.91% (LPVMP verifiedi or 73.52% (IBP verified). Our resalt should be compared to 73.52% Although explicitly mentioned, CIFAR-10 models
requires adding
2015) trinned using fuss 1.16,u-
their settings.
We Pan far for this setting. and thus CROWN-IBP bound (3 used evalunte the verified error.
and different i. settings. Instead of reporting just the best model, we compare the best, worst and median verified errors over all models. Our results are presented in Figure 3 (a) is for MNIST with e 0.3; (d) are for CIFAR with 8/255. We can observe that CROWN-IBP achieves better performance consistently under different schedule length. In addition, IBP with K O cannot stably converge on all models when schedule is short; under other и: settings, CROWN-IBP always performs better. We conduct additional training stability experiments on MNIST and CIFAR-10 dataset under other model and e settings and the observations are similar (see Appendix
5 CONCLUSIONS
We propose a new certified defense method, CROWN-IBP, by combining the fast interval bound propagation (IBP) bound and tight linear relaxation based bound, CROWN. Our method enjoys high computational efficiency provided by IBP while facilitating the tight CROWN bound to stabilize training under the robust optimization framework, and provides the flexibility to trade-off between the two. Our experiments show that CROWN IBP consistently outperforms other IBP baselines in both standard errors and verified emror and achieves state-of-the-art verified test errors for lo robustness.

---

Published as a conference paper at ICLR 2020
0,800
Verifled Error
0.20
C10WWwtt (1 ISP Home CR0WiS BP +
C- O)) ISP of
Verified Error
0.775
CROWN HP (Nan R)
IFF 2]
CROWN EP or (0)
Verified Error
0.65
CADWAN
ISF Xue #0
ISP 20
0.15
CROWN EP Maace 0.5
0.60
CRDWNs (aa0
15P Dow E.31
0.750
IPP 2eu 0..51
0.55
0.725
0.50
0.05
0.700
0.45
10
15
30
60
30
60
90
120
30
60
90
120
Schedule Length
Schedule Length
Schedule Length
(a) MNIST, = 0.3, best 7.46%
(b) CIFAR, 6 255 best 70.51% (c) CIFAR,
2 best 49.28%
265
Figure 3: Verified error vs. schedule length 8 medium MNIST models and 8 medium CIFAR-10 models. The solid bars show median values of verified errors. fistan = 1.0 except for the k- = 0 setting. The upper and lower ends of error bar are the worst and best verified error, respectively. For each schedule length, three color groups represent three different K settings.
REFERENCES
Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples. International Conference on Machine Learning (ICML), 2018.
Jacob Buckman, Aurko Roy, Colin Raffel, and Ian Goodfellow. Thermometer encoding: One hot way to resist adversarial examples. International Conference Learning Representations, 2018.
Nicholas Carlini and David Wagner. Adversarial examples are not easily detected: Bypassing ten detection methods. In Proceedings of the 10th ACM Workshop on Artificial Intelligence and Seccurtt, pp. 3-14. ACM, 2017a.
Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In 2017 38th IEEE Symposium on Security and Privacy (SP), pp. 39-57. IEEE, 2017b.
Hongge Chen, Huan Zhang, Pin- Yu Chen, Jinfeng Yi, and Cho-Jui Hsieh. Attacking visual language grounding with adversarial examples: A case study on neural image captioning. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). pp. 2587-2597, 2018
Jeremy M Cohen, Elan Rosenfeld, and J Zico Kolter. Certified adversarial robustness via randomized smoothing. arXiv preprint arXiv: 1902.02918, 2019.
Krishnamurthy Dvijotham, Marta Gamelo,, Alhussein Fawzi, and Pushmeet Kohli. Verification of deep probabilistic models. CoRR, abs/ 1stss/882202955 2018a. URL http:://aaxii.orr/aa//////B/
Krishnamurthy Dvijotham, Sven Gowal, Robert Stanforth, Relja Arandjelovic, Brendan O' D'onogguue Jonathan Uesato, and Pushmeet Kohli. Training verified learners with learned verifiers. arXiv preprint 1805 1025,,, 2018b.
Krishnamurthy Dvijotham, Robert Stanforth, Sven Gowal, Timothy Mann, and Pushmeet Kohli. dual approach to scalable verification of deep networks. UAI, 2018c.
Krishnamurthy Dj Dvijotham, Robert Stanforth, Sven Gowal, Chongli Qin, Soham De, and Pushmeet Kohli. Efficient neural network verification with exactness characterization.
Kevin Eykholt, Ivan Evtimov, Earlence Fernandes, Bo Li, Amir Rahmati, Chaowei Xiao, Atul Prakash, Tadayoshi Kohno, and Dawn Song. Robust whysical-worid attacks on deep learning visual classification. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 1634, 2018.
Ian J Goodffllow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. ICLR, 2015.
Sven Gowal, Krishnamurthy Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Uesato, Timothy Mann, and Pushmeet Kohli. On the effectiveness of interval bound propagation for training verifiably robust models. arXiv preprint 1810. 12715, 2018.
10

---

Published as a conference paper at ICLR 2020
Chuan Guo, Mayank Rana, Moustapha Cisse, and Laurens van der Maaten. Countering adversarial images using imput transformations. In ICLR, 2018.
Warren He, James Wei, Xinyun Chen, Nicholas Carlini, and Dawn Song. Adversarial example defenses: ensembles of weak defenses are not strong, In Proceedings of the 11th USENIX Conference on Offensive Technologies, pp. 15-15. USENIX Association, 2017.
Matthias Hein and Maksym Andriushchenko. Formal guarantees on the robustness of a classifier against adversarial manipulation. In Advances in Neural Information Processing Systems (NIPS), pp. 200222226666002 2276, 2017.
Guy Katz, Clark Barrett, David L Dill, Kyle Julian, and Mykel J Kochenderfer. Reluplex: An efficient SMT solver for verifying deep neural networks. In International Conference on Computer Aided Verification, pp. 97-117. Springer, 2017.
Alexey Kurakin, Ian Goodfellow, and Samy Bengio. Adversarial machine learning at scale. In International Conference on Learning Representations, 2017.
Mathias Lecuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified robustness adversarial examples with differential privacy. arXiv preprint arXhv:1802.0347/ 2018.
Bai Li, Changyou Chen, Wenlin Wang, and Lawrence Carin. Second-order adversarial attack and certifiable robustness. arXiv preprint Xiv:::89:0:03333 13, 2018
Xingjun Ma, Bo Li, Yisen Wang. Sarah M Erfani, Sudanthi Wijewickrema, Michael E Houle, Grant Schoenebeck, Dawn Song, and James Bailey. Characterizing adversarial subspaces using local intrinsic dimensionality. In International Conference on Learning Representations (ICLR), 2018.
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.
Matthew Mirman, Timon Gehr, and Martin Vechev. Differentiable abstract interpretation for provably robust neural networks. In International Conference on Machine Learning, pp. 3575-3583, 2018.
Matthew Mirman, Gagandeep Singh, and Martin Vechev. A provable defense for deep residual networks. arXiv preprint 1rXXiv:103.125//0 2019.
Nicolas Papernot, Patrick McDaniel, Xi Wu, Somesh Jha, and Ananthram Swami. Distillation defense to adversarial perturbations against deep neural networks. In 2016 IEEE Symposium on Security and Privacy (SP), pp. 582-597. IEEE, 2016.
Chongli Qin, Krishnamurthy Dj Dvijotham, Brendan O' D'nnoghue, Rudy Bunel, Robert Stanforth, Sven Gowal, Jonathan Uesato, Grzegorz Swirszez, and Pushmeet Kohli. Verification of non-linear specifications for neural networks. ICLR, 2019.
Aditi Raghunathan, Jacob Steinhardt, and Percy Liang. Certified defenses against adversar- ial examples. International Conference Learning Representations (ICLR), arXiv preprint arXiv:1801.09344 2018a
Aditi Raghunathan, Jacob Steinhardt, and Percy S Liang. Semidefinite relaxations for certifying robustness adversarial examples. In Advances in Neural Information Processing Systems, pp. 10900-10910, 2018b.
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 arXiv:1906.04584 2019a.
Hadi Salman, Greg Yang. Huan Zhang, Cho-Jui Hsich, and Pengchuan Zhang. A convex relaxation barrier to tight robust verification neural networks. arXiv preprint arXiv:1902.0877 08722, 2019b.
Pouya Samangouei, Maya Kabkab, and Rama Chellappa. Defense-GAN Protecting classifiers against adyersarial attacks using generative models. arXiv preprint a 1805.06605. 2018.
11

---

Published as a conference paper at ICLR 2020
Gagandeep Singh, Timon Gehr, Matthew Mirman, Markus Püschel, and Martin Vechev. Fast and effective robustness certification. In Advances in Neural Information Processing Systems, pp- 10825-10836, 2018.
Gagandeep Singh, Timon Gehr, Markus Püschel, and Martin Vechev. Robustness certification with refinement. ICLR, 2019.
Aman Sinha, Hongseok Namkoong, and John Duchi. Certifying some distributional robustness with principled adversarial training. In ICIR, 2018.
Yang Song. Taesup Kim, Sebastian Nowozin, Stefano Ermon, and Nate Kushman. Pixeldefend: Leveraging generative models to understand and defend against adversarial examples. arXiv preprint arXiv: 1770, 2017.
Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. arXiv preprint arXiv:1312.6199 2013.
Shiqi Wang, Yizheng Chen, Ahmed Abdou, and Suman Jana. Mixtrain: Scalable training of formally robust neural networks. arXiv preprint 1r1iv:1811. 1.02625, 2018a.
Shiqi Wang, Kexin Pei, Justin Whitehouse, Junfeng Yang, and Suman Jana. Efficient formal safety analysis of neural networks. In Advances in Neural Information Processing Systems, pp. 6369- 6379, 2018b.
Tsui-We Weng, Huan Zhang, Hongge Chen, Zhao Song, Cho-Jui Hsieh, Duane Boning, Inderjit Dhillon, and Luca Daniel. Towards fast computation of certified robustness for ReLU networks. In International Conference on Machine Learning, 2018.
Eric Wong and Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In International Conference Machine Learning, pp. 5283-52222 2018.
Eric Wong, Frank Schmidt, Jan Hendrik Metzen, and J Zico Kolter. Scaling provable adversarial defenses. Advances in Neural Information Processing Systems (NIPS), 2018.
Chaowei Xiao, Ruizhi Deng. Bo Li, Fisher Yu, Mingyan Liu, and Dawn Song. Characterizing adversarial examples based spatial consistency information for semantic segmentation. In Proceedings of the European Conference on Computer Vision (ECCV), pp. 217-234, 201 8a.
Chaowei Xiao, Bo Li, Jun-Yan Zhu, Warren He, Mingyan Liu, and Dawn Song. Generating adversarial examples with adversarial networks. IJCA/18, 2018b.
Chaowei Xiao, Jun- Yan Zhu, Bo Li, Warren He, Mingyan Liu, and Dawn Song. Spatially transformed adversarial examples. ICLRI8, 2018c.
Chaowei Xiao, Ruizhi Deng. Bo Li, Taesung Lee, Benjamin Edwards, Jinfeng Yi, Dawn Song, Mingyan Liu, and Ian Molloy. Advit: Adversarial frames identifier based on temporal consistency in videos. In Proceedings of the IEEE International Conference on Computer Vision, pp. 3968- 2019a.
Chaowei Xiao, Dawei Yang, Bo Li, Jia Deng, and Mingyan Liu. Meshady: Adversarial meshes for visual recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 6898-6907, 2019b.
Kai Y Xiao, Vincent Tjeng, Nur Muhammad Shafiullah, and Aleksander Madry. Training for faster adversarial robustness verification via inducing relu stability. ICLR, 2019c.
Kaidi Xu, Sijia Liu, Pu Zhao, Pin- Yu Chen, Huan Zhang, Quanfu Fan, Deniz Erdogmus. Yanzhi Wang, and Xue Lin. Structured adversarial attack: Towards general implementation and better interpretability. arXiv preprint arXiv: / 1808 01664, 2018.
Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric Xing, Laurent El Ghaoui, and Michael Jordan. Theoretically principled trade-off between robustness and accuracy. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference Machine Learning. volume 97 of Proceedings of Machine Learning Research, pp. 7472- 7482, Long Beach, California, USA, 09-15 Jun 2019a. PMLR. / http:///wooedding...mrsss//////p 19p.html
12

---

Published as a conference paper at ICLR 2020
Huan Zhang, Tsui- Wei Weng, Pin- Yu Chen, Cho-Jui Hsieh, and Luca Daniel. Efficient neural network robustness certification with general activation functions. In Advances in Neural Information Processing Systems (NIPS), 2018.
Huan Zhang, Hongge Chen, Zhao Song, Duane Boning, Inderjit S Dhillon, and Cho-Jui Hsich. The limitations of adversarial training and the blind-spot attack. ICLR, 2019b.
Huan Zhang, Pengchuan Zhang, and Cho-Jui Hsieh. Recurjac: An efficient recursive algorithm for bounding jacobian matrix of neural networks and its applications. AAAI Conference on Artificial Intelligence, 2019c.
Tianhang Zheng, Changyou Chen, and Kui Ren. Distributionally adversarial attack. arXiv preprint arxiv: 2018.
13

---

Published as a conference paper at ICLR 2020
A
IBP AS A SIMPLE AUGMENTED NETWORK
Despite achieving great success, it is still an open question why IBP based methods significantly outperform convex relaxation based methods, despite the fact that convex relaxations usually provide significantly tighter bounds. We conjecture that IBP performs better because the bound propagation process can be viewed as ReLU network with the same depth as the original network, and the IBP training process is effectively training this equivalent network for standard accuracy, as explained below.
Given a fixed neural network (NN) (ax), IBP gives very loose estimation of the output range of f()). However, during training, since the weights of this NN can be updated, we can equivalently view IBP as an augmented neural network, which we denote as an IBP-NN (Figure AA). Unlike usual network which takes an input Bg with label V/k, IBP-NN takes two points 3t, 3 e and TV 2 as inputs (where æ S EV, element-wiselyy. The bound propagation process can be equivalently seen as forward propagation Figure After the last specification layer C' (typically merged into W(L),, we can obtain m c)- Then, -m e) is sent to softmax layer for prediction. Importantly, since [m e)lup.
specially structured neural network, as shown in
(as the y row in is always 0), the top-1 prediction of the augmented IBP network is yv if and only all other elements of (2) c) positive, i.e., the original network will predict correctly for all 2 S æ I zy. When we train the augmented IBP network with ordinary cross-entropy loss and input Eg, are implicitly doing robust optimization (Eq.
desire it to predict correctly
W
W
W
C Hepecllisioon
5
RaLU
ReLU
I
C
softmax
XH-
Can Inggther (Last loyer elsiertiioooon
Figure A: Interval Bound Propagation viewed as training an augmented neural network (IBP-NN). The inputs of IBP-NN are two images Ig + and Ø; C. The output of IBP-NN is vector of lower bounds of margins (denoted as m between ground-truth class and all classes (including the ground-truth class itself) for all æy regular softmax function to get model prediction. The top-1 prediction of softmax is correct if and only if all margins between the ground-trus -tuuh class and other classes (except the ground truth class) are positive, i.e., the model is verifiably robust. Thus, an IBP-NN with low standard error guarantees low verified error on the original network.
S 2 + This vector m. is negated and sent into
The simplicity of IBP-NN may help a gradient based optimizer find better solutions. On the other hand, while the computation of convex relaxation based bounds can also be cast as an equivalent network (e.g., the "dual network" in WWng & Kolter (2018)). its construction is significantly more complex, and sometimes requires non-differentiable indicator functions (the sets I+, I and I in Wong Kolter (2018). As a consequence, can be challenging for the optimizer to find good solution, and the optimizer tends to making the bounds tighter naively by reducing the norm of weight matrices and over-regularizing the network, as demonstrated in Figure [
B TIGHTNESS COMPARISON BETWEEN IBP AND CROWN-IBP
Both IBP and CROWN-IBP produce lower bounds m( e), and a larger lower bound has better quality. To measure the relative tightness of the two bounds, we take the average of all bounds of training examples:
F T (
(#) MIBp(xC (x),)) )))
14

---

Published as a conference paper at ICLR 2020
A positive value indicates that CROWN-IBP is tighter than IBP. In Figure B we plot this averaged bound differences during e schedule for one MNIST model and one CIFAR-10 model. We can observe that during the early phase of training when the schedule just starts, CROWN-IBP produces significantly better bounds than IBP. A tighter lower bound m(æ. <) gives tighter upper bound for maxses TAxx: + y; 0), making the minimax optimization problem (2) more effective to solve. When the training schedule proceeds, the model gradually learns how to make IBP bounds tighter and eventually the difference between the two bounds become close to O.
MNIST
CIFAR
15.0
30
Bound Difference
12.5
10.0
20
7.5
10-
2.5
0-
0.0
10
20
40
60
80
320
800
1200 1600 2000 Epoch
Epoch
Figure B: Bound differences between IBP and CROWN-IBP for DM-large models during training. The bound difference is only computed during the e schedule (epoch 10 to 60 for MNIST, and 320 to 1920 for CIFAR-10), as we don't compute CROWN-IBS bounds in warmup period and after schedule.
Why CROWN-IBP stabilizes IBP training? When taking a randomly initialized network or a naturally trained network, IBP bounds very loose. But in Table I show that network trained using IBP can eventually obtain quite tight IBP bounds and high verified accuracy; the network can adapt IBP bounds and learn specific set of weights make IBP tight and also correctly classify examples. However, since the training has to start from weights that produce loose bounds for IBP, the beginning phase of IBP training can be challenging and vitally important.
We observe that IBP training can have a large performance variance across models and initializations. Also IBP is more sensitive to dyper-parameter like к or schedule length; Figure 3 many IBP models converge sub-optimally (large worst/median verified error). The reason for instability is that during the beginning phase of training. the loose bounds produced by IBP make the robust loss (9) ineffective, and it is challenging for the optimizer to reduce this loss and find set of good weights that produce tight IBP verified bounds the end.
Conversely, if our bounds are much tighter at the beginning, the robust loss 9 always remains in reasonable range during training, and the network can gradually learn to find good set of weights that make IBP bounds increasingly tighter (this is obvious in Figure B). Initially, tighter bounds can be provided by a convex relaxation based method like CROWN, and they are gradually replaced by IBP bounds (using 8yn 1, Beod 0), eventually leading to a model with learned tight IBP bounds in the end.
C MODELS AND HYPERPARAMETER FOR COMPARISON TO IBP
The goal of these experiments is to reproduce the performance reported in (Gowal al. 2018) and demonstrate the advantage of CROWN-IBP under the same experimental settings. Specifically, to reproduce the IBP results, for CIFAR-I0 we train using a large batch size and long training schedule on TPUs (we can also replicate these results multi-GPUs using a reasonable amount of training time; see Section F). Also, for this set of experiments we use the same code base as in Gowal et al. (2018). For model performance on a single GPU, please see Table D in Section Fl as well as the training stability experiments in Section 4 and Section H
comprehensive set of small and medium sized models trained
15

---

Published as a conference paper at ICLR 2020
The models structures (DM-small, DM-medium and DM-large) used in Table C and Table are listed in Table A These three model structures are the same as Gowal et al. (2018). Training hyperparameters are detailed below:
For MNIST IBP baseline results, we follow exact the same set of hyperparameters as in (Gowal et al., 2018). We train 100 epochs (60K steps) with batch size of 100, and use a warm-up up and ramp-up duration of 2K and 10K steps. Learning rate for Adam optimizer is set to x 10 and decayed by 10X at steps 15K and 25K. Our IBP results match their reported numbers. Note that we always use IBP verified errors rather than MIP verified emrors. We the same schedule for CROWN-IBP with Crain 0.2 (Gest 0.1) in Table C and Table 2 For Enain 0.4, this schedule can obtain verified error rates 4.22%, 7.01 % and 12.84% Erest {0.2, 0.3, 0.4] using the DM-Large model, respectively.
For MNIST CROWN-IBP IBP with Erain = 0.4 in Table and Table we train 200 epochs with batch size of 256. We use Adam optimizer and learning rate up with 10 epochs' regular training, and gradually ramp up from O to <tain in 50 epochs. We reduce the learning rate by 10X at epoch 130 and 190. Using this schedule, IBP's performance becomes worse (by about 1-2% in all settings), but this schedule improves verified error for CROWN-IBP at étest = 0.4 from 12.84% to to 12.06% and does do affect verified errors at other Eist levels.
10 4. We warm
For CIFAR-10, we follow the setting in Gowal et al. (2018) and train 3200 epochs on 32 TPU cores. We use batch size of 1024, and a learning rate of 5 10 4, We warm up for 320 epochs, and ramp-up e for 1600 epochs. Learning rate is reduced by 10X at epoch 2600 and 3040. We use random horizontal flips and random crops data augmentation, and normalize images according to per-channel statistics, Note that this schedule is slightly different from the schedule used in (Gowal et al., 2018); we use smaller batch size due to TPU memory constraints (we used TPUv2 which has half memory capacity as TPUv3 used in (Gowal et al.) (2018), and also we decay learning rates later. We found that this schedule improves both IBP baseline performance and CROWN-IBP performance by around 1%; for example, at 8/255, this improved schedule can reduce verified error from 73.52% to 72.68% for IBP baseline (Kistart 1.0, Ficnd = 0.5) using the DM-Large model.
Hyperparameter and B. We use a linear schedule for both hyperparameters, decreasing from Eatan to Kend while increasing 3 from Bumn to Bead- The schedule length set to the same length as the schedule.
In both IBP and CROWN-IBP, a hyperparameter & is used to trade-off between clean accuracy and verified accuracy. Figure 2 shows that Kinn can significantly affect the trade-off, while Ksan has minor impacts compared to Kend- In general, we recommend Aistan = and Kend = 0 as a safe starting point, and can adjust Kend larger value if a better standard accuracy is desired. The setting Katart Kend = 0 (pure minimax optimization) can be challenging for IBP as there is no natural loss stabilizer; under this setting CROWN-IBP usually produces model with good (sometimes best) verified accuracy but noticeably worse standard accuracy (on CIFAR-10 e be large as 10%). so this setting is only recommended when model with best verified accuracy is desired at cost of noticeably reduced standard accuracy.
8 the difference can 255
Compared IBP, CROWN-IBP adds one additional hyperparameter, 3. 3 has clear meaning: balancing between the convex relaxation based bounds and the IBP bounds. Buum is always set to I as we want to use CROWN-IBP to obtain tighter bounds to stabilize the early phase of training when IBP bounds are very loose; Bend determines if we want to use convex relaxation based bound (Band = 1) or IBP based bound (Bend = 0) after the schedule. Thus, we set Bend = for the case where convex relaxation based method (Wong et al.) 2018) can outperform IBP (e.g.. CIFAR-10 e = 2/255, and Bend = for the case where IBP outperforms convex relaxation based bounds. We do not tune or grid-search this hyperparameter.
16

---

Published as a conference paper at ICLR 2020
DM-Small
DM-Medium
DM-Large
CONY 16 4x4+2 CONV 32 1x141
CONY 32 3x3+1
CONV 64 3x3+1
CONV 32 1x142
CONV 64 3x3+1
FC 100
CONV 64 3x3+1
CONY 128 3x3+2
CONV 4x4+2
CONY 128 3x3+1
FC 512
CONY 128 3x3+1
FC 512
FC 512
Table A: Model structures from Gowal et al. (2018). "CONV wxh++s" represents a 2D convolutional layer with & filters of size wxh using a stride of in both dimensions. "FC n" fully connected layer with n outputs. Last fully connected layer is omitted. All networks use ReLU activation functions.
D HYPERPARAMETERS AND MODEL STRUCTURES FOR TRAINING STABILITY EXPERIMENTS
In all our training stability experiments, we use a large number of relatively small models and train them on a single GPU, These small models cannot achieve saae-off-hhe-al art performance but they can be trained quickly and cheaply, allowing us to explore training stability over a variety of settings, and report min, median and max statistics. We use the following hyperparameters:
For MNIST, we train 100 epochs with batch size 256. We use Adam optimizer and the learning rate is 5 x 10-4 The first epoch is standard training for warming up. We gradually increase linearly per batch in our training process with schedule length of 60. We reduce the learning rate by 50% every 10 epochs after schedule ends. No data augmentation technique used and the whole x 28 images are used (normalized to 0 range).
For CIFAR, we train 200 epoch with batch size 128. We use Adam optimizer and the learning rate is 0.0.1% 1.. The first 10 epochs are standard training for warming up. We gradually increase e linearly per batch in our training process with a e schedule length of 120. We reduce the learning rate by 50% every 10 epochs after schedule ends. We use random horizontal flips and random crops as data augmentation. The three channels are normalized with mean (0.4914, 0.4822, 0.4465) and standard deviation (0.2023, 0.1914, 0.2010). These numbers are per-channel statistics from the training set used in (Gowal et al. 2018).
All verified error numbers are evaluated on the test set using IBP, since the networks are trained using IBP (3 = 0 after reaches the target mmin), except for CIFAR compute the CROWN-IBP verified error.
255 where we set 8 = 1 to
Table B gives the 18 model structures used in our training stability experiments. These model structures are designed by us and are not used in Gowal al. (2018). Most CIFAR-10 models share the same structures as MNIST models (unless noted on the table) except that their input dimensions are different. Model is too small for CIFAR-I0 thus we remove it for CIFAR-10 experiments. Models A J are the "small models" reported in Figure 3 Models K T are the "medium models" reported in Figure For results in Table [ we use a small model (model structure B) for all three datasets. These MNIST, CIFAR-10 10 models can be trained on single NVIDIA RTX 2080 Ti GPU within a few hours each.
E OMITTED RESULTS ON DM-SMALL AND DM-MEDIUM MODELS
In Table 2 we report results from the best DM-Large model. Table Cerresents the verified, standard (clean) and PGD attack errors for all three model structures used in (Gowal et al. 2018) (DM-Small, DM-Medium and DM-Large) trained on MNIST and CIFAR-10 10 datasets. We evaluate IBP and CROWN-IBP under the same three settings in Table 2 We hyperparameters detailed in Section C to train these models. We can see that given any model structure and any x setting, CROWN-IBP BP consistently outperforms IBP.
17

---

Published as a conference paper at ICLR 2020
Name
Model Structure (all models have a last FC 10 layer, which are omitted)
A (MNIST Only)
Conv x 4+2, Conv 84 4+2, FC 128
B
Conv 8 x 4+2, Conv 16 x 4+2, FC 256
C
Conv 3 x 3+1, Conv 8.3 3+1, Conv 8 x 4+4, FC 64
D
Conv 8 x 3+ Conv 16 3 x 3+1, Cony 16 x 4+4, FC 128
E
Conv 4 x 5+1, Conv 8 5+1, Conv 8 5 5+4, FC 64
Conv 5 x 5+1, Conv 16 x 5+1, Cony 16.5 5 x 5+4, FC 128
G
Conv 4 x 3+ Conv 4 4 4+2, Conv 8 x 3+1, Conv 8.4 4+2, PC 256, FC 256
H
Conv 8.3 x 3+ Conv 8 4 4+2, Conv 16 3+1, Conv 1644 4+2. FC 256, FC 256
Conv 4 x 3+1, Conv 4 444 4+2, Conv 8 x 3+1, Conv 8 4+2, PC 512, FC
Conv 3 x 3+1, Conv 8 4+2, Conv 16.3 3+1, Conv 16 442. FC 512, FC 512
K
Conv 16 3 x 3+1, Conv 16 4 x 4+2, Conv 32 3 x 3+1, Conv 32 4+2, FC 256, FC 256
L
Conv 16 3 x 3+1, Conv 16 4 x 4+2, Conv 32 x 3+1, Conv 32 4+2, FC, FC
M
Conv 32 3 x 3+11.
Cony 32 4 x 4+2. Conv 64 3 x 3+1, Conv 64 4 4+2, FC 512. 512
N
Conv 64 3 x 3+1.
Cony 64 4 x 4+2, Conv 128
3+1, Conv 128 4 x 442, FC 512, FC
OIMNIST Only)
Conv 64 5 x 5+1.
Conv 128 5 5+1, Conv 128 4 x 4+4, FC 512
POMNIST Only)
Conv 32 5 X 5+1,
Conv 64 5 X 5+1, Conv 64 4 x 4+4, FC 512
Q
Conv 16 5 x 5+1.
Cony 32 5 x 5+1. Conv 32 5 x 5+4, FC 512
R S(CIFAR- 10 Only) T(CIFAR-10 Only)
Conv 32 3 x 3+1,
Cony 64 3 x 3+1, Conv 64 3 x 3+4, FC 512
Cony 32 4 x 4+2,
Conv 64 4 X 4+2, FC 128
Conv 64 4 x 4+2, Cony 128 4 4+2, FC 256
Table B: Model structures used in our training stability experiments. We use ReLU activations for all models. We omit the last fully connected layer its output dimension is always 10. In the table, "Conv & w x w + 8" represents to a 2D convolutional layer with & filters of size w x w and a stride of Model A J are referred to "small models" and model K to T are referred as "medium models".
F ADDITIONAL EXPERIMENTS ON SMALLER MODELS USING A SINGLE GPU
In this section we present additional experiments on a variety of smaller MNIST and CIFAR-I 10 models which be trained single GPU. The purpose of this experiment is compare model performance statistics (min, median and max) on a wide range of models, rather than few hand selected models. The model structures used in these experiments are detailed in Table B In Table D we present the best, median and worst verified and standard (clean) test errors for models trained on MNIST and CIFAR-10 using IBP and CROWN-IBP. Although these small models cannot achieve statc-of-the art performance, CROWN-IBP's best, median and worst verified errors among all model structures consistently outperform those of IBP. Especially, in many situations the worst case verified error improves significantly using CROWN-IBP because IBP training is not stable on some of the models.
It is worth noting that in this set of experiments we explore different setting: <rain <teat We found that both IBP and CROWN-IBP tend to overfit training dataset on MNIST with small e, thus verified errors using Erain > Gest (as used in Table and Table or using an explicit & regularization, which will be discussed in detail in Section |
not good presented in Table C This overfitting issue be alleviated by
18

---

Published as a conference paper at ICLR 2020
Table C: The verified, standard (clean) and PGD attack errors for 3 models (DM-small, DM-medium, DM-large) trained on MNIST and CIFAR test sets. We evaluate IBP and CROWN-IBP under different schedules. CROWN-IBP outperforms IBP under the same setting, and also achieves Mate-of-the-an results for lo robustness on both MNIST and CIFAR datasets for all e.
Datseet
(h,, nomn)
Training Method
schooliles Rigs
DM-small model's en (8)
DM-medium modal's or Verilied
DM-large model's
Rend
Standard
Verilied
PGD
Standard
PGD
Standard
Verilied
PGD
1.92
4.16
3.58
1.53
3.26
2.82
1.13
2.89
2.24
IDP
0.5
1.68
3,60
3.34
1.46
3.20
2.57
1.08
2.75
2.02
0.1
2.14
4.24
3.54
1.48
3.21
2.77
1.14
2.81
2.13
0.2
1.90
3.50
3.21
1.44
2.77
2.37
1.17
2.36
1.91
CROWN IBP
3.19
2.64
2.25
0.95
2.38
1.77
IBP
3.84
2.12
4.75
4.24
Foz 0.2
6.25
11:32
10.84
3.89
7.21
0.68
2.74
3,45
4,89
0.4
1.7%
6.61
5:40
1354
6.65
6.42
2.84
5.15
4.301
CROWN-IN IDP
0.5
2.96
6.11
5.74
2.37
5.35
4.90
1.82
4.13
3.81
MNIST
3.55
6.29
6:33
3.16
5.82
5.44
2.17
4,31
3.99
5,08
14,42
13:30
3.68
10:97
9.66
3.45
9.76
8.42
IHP
12:25
8.47
Tex
8.73
Teak
7.65
CROWN-IB
2.95
9.44
8:26
2.37
7.74
1.80
7.02
6.05
3.55
9,40
8.50
3.16
3.62
7.65
2.17
7.03
6.12
5.08
23.40
20:15
3.68
18.34
14.75
3.45
16.19
12.73
IBP
0.5
3.83
25.16
19.97
2.55
16.82
12.83
2.12
15.37
11.05
044
6.25
26.81
22.78
3,80
16.99
13.81
2.74
14.80
11.14
0.4
3.78
15.31
13:34
14.58
12.69
2.54
12.74
T0.39
CROWN-IBP
13.11
IDP
38.90
$7.94
53.64
34.19
56,24
19.63
33.77
58.48
50.54
151
44.00
56.32
54.16
39:30
53.68
49.74
39.22
55.19
30,40
39.43
$3.93
49 16
32.78
49.57
44.22
28. 48
46.03
40.28
CROWN IBP
0.5
34.08
$4.25
51.17
28.63
51.39
42.45
26.19
50.33
40.24
38.15
52.57
50.35
35.17
49.82
44.66
28.91
46.43
40.27
61.91
73.12
71.75
71.98
30.07
59.41
71.22
68.95
IDP
70.54
CIFAR-I0
66.94
Gras
CROWN IDP
53.12
73.51
70.61
18.51
71.55
67.67
45.47
69.55
65.74
600.84
72.47
71.18
58.19
68.94
67.72
55.27
67.76
63.71
0
70.02
78.36
77.67
67.55
78.65
76.92
68.97
75.12
76.65
16
IBP
0..5
67.73
63.43
81.58
78.71
77.53
78.81
70.38
60007
$1.01
79.26
77.45
77.32
68.88
59.46
78
30.85
76.95
76.977
77.27
75.70
CROWN-IBP
77.91
77.21
76.80
Verified errors reported Table of Gowal et al. 20188 are evaluated using mixed integer programming (MIP).
For a fair comparison, we use the IBP verified errors reported in Table of Gowal et al. (2088)
AAcordiing to direct communication with the authors of Gowal et al. (2018] achieving 68.44% IBP verified error requires adding extra PGD adversarial training loss. Without adding PGD, the achievable verified error is 72.91% (LP/MIP verified) 73.52% (IBP verified).
Although not explicitly mentioned, the CIFAR- models (Gowal et al. 2018) also use caain 1.
use Pean Send for this setting, the same as in Table and thus CROWN-IBP bound used to evaluate the verified error.
19

---

Published as a conference paper at ICLR 2020
Table D: Verified and standard (clean) test errors for large number of models trained on MNIST and CIFAR-10 datasets using IBP and CROWN-IBP. The purpose of this experiment is to compare model performance statistics (min, median and max) on wide range of models, rather than a few hand selected models. For each setting we report 3 representative models: the models with smallest, median, and largest verified error. We also report the standard error of these three selected models.
Note that in this table we set Etrain Eest and observe overfitting on small for MNIST. See Section [ for detailed discussions.
Model Family
Training Method
schedile
Verified
Eroe (8)
Standedd Test Exro((3) median
Fiee:
Find
worst
2.50
IBP
5.72
7:34
1.51
1.34
2.45
10 small models
0.5
4.21
5.24
5.18
5.95
6.80
7:36
1.41
1.41
1.88
1.85
2.55
1,57
CROWN-IBP
4.14
5.24
6.82
1.39
2.06
2.46
0.1 Il.1
0.5
4.60
5.94
6.88
1.26
1.88
1,97
5.9
0.25
7.82
1.14
1.12
1:23
IRP
5.77
6.30
7.50
1.21
1.13
1.34
mediom models
0.5
5.22
6.05
5.63
6.40
7.70
6.34
1.19
1.19
1.33
1,05
1.34
1,00
CROWN-IBR
1,115
1,00
1.00
2.76
4.14
12:92
2.56
small madels
0.5
7.31
7.29
8.71
11.97
13.54
1.62
1.93
2,36
2.3
3.86
3.20
CROWN IBP
6.27
7,66
12:11
2,01
2.92
4,00
0.2
0.5
6.53
8.14
12.56
1.61
1.61
3.27
0.2
7.56
5.60
9:50
1.96
2.19
1.39
IBP
8.26
8.72
9.54
1.45
1.75
1.31
mediam moddls
0.5
8.42
6.86
6.42
8.90
10.09
7.64
1.09
1.76
1.35
1.42
1.53
1.36
CROWN IDP
7.09
7.84
1.04
1.25
MNISTT
7.5L
7.96
1.08
1,25
1,19
6.07
23.0
3.4%
small models
11.29
12:78
23.99
16.83
3.44
3.62
5.19
7.35
CROWN-IDE IDP
9.59
11.33
15.23
2.78
3.41
5.90
Fexze 1.3 feu 11.5
0.5
9.30
11.9%
19.56
2.20
2:72
4.83
10.43
10.83
11.99
2.01
2.35
3.29
IRP
10.74
11.73
12.16
2.17
2.46
1,60
medium models
0.5
11.23
7.46
11.71
8.47
8.57
12.4
1.48
1.72
2.09
1,32
1,83
1.39
CROWN-JPP
7.96
8.53
5.59
1.45
1.56
1,85
0.5
8.19
9.20
9.51
1.27
1.46
1.62
18,89
5.4
9.63
TRP
18:75
55.3
11:32
small models
7.54
34.56
CROWN-IBP
5.15
8.54
Yrux 0.4 Ges 0.4
19.18
24. 76
3.97
6.64
15.17
15.54
18.98
2.85
3.79
4.91
ISP
15.63
16.06
17.11
2.93
3.4
3.75
mediam models
0.5
12.06
15.74
13.43
16.42
17.9%
14.25
7.76
2.35
2.31
2.85
3.15
3.36
CROWN IDP
12.90
13:47
14.06
2.42
2.86
3.11
0.5
15.00
13.69
14.52
1.89
2,40
2.35
$6.89
57.84
60.58
40.59
45.51
51.38
IHP
54.56
60.69
47.42
511.73
30.28
48.01
56.02
CROWN IDP
47.05
Gwi 2/2552 Giz - 2/255
57.49
60.11 12
03
35.76
43.40
55.47
56.41
58.54
41.39
45,23
46.34
IRP
55.51
56.74
57.55 85
42.41
43.71
44.74
mediomm models
0.5
57.05
49.57
59.70
50.83
$2.59
60.25
32.64
34,77
34,20
35,80
37.05
38.05
CROWN JBP
49.28
51.59
53.45
32.31
34,25
38.11
CIFAR-10
0.5
$2.00
53.56
55.25
27.80
20.49
32.42
72.07
73.34
73.88
61.11
61.01
66.0
TRP
72:57
73.49
62.26
60.98
63.5
small marelss
76.95
$2.53
53.79
CROWN IBP
72:24
73.10
61.56
Puuk: 8/255
76.11
$2,95
55.58
Prpe 8/255
72.75
75.23
73.82
03.35
IBP
72,
72.83
74.38
67.54
59.6
61.99
medium modets
0.5
70 70
74.84
71.61
75.59
97.95
72.20
$7.90
51.71
40.10
54,43
39.70
54.12
CROWN-IBP
70.51
71.56
72.82
57.87
50.95
50.
0.5
73.48
74.69
76.60 66
49.40
53.96
52.05
Verified errors reported in Table 4 of Gowal et al. (2018) evaluated using mixed integer pro- gramming (MIP) and linear programming (LP). which are strictly smaller than IBP verified errors use the IBP verified errors reported in
but computationally expensive. For fair comparison,
their Table
We use Burt = Send = for this setting, the same as in Table and thus CROWN-IBP bound used to evaluate the verified crror.
20

---

Published as a conference paper at ICLR 2020
0.800
CROWN-IBP Dj (X 0)
CROWN-IBP
Verified Error
0.65
Verified Error
IBP (K D)
CHOWN-IBP (Waez 01
0.775
CROWN-IBP (Kanz 0)
IBP (Navd OF CROWN-IBP (Mou 0.5) IPP (Sard 0.5]
IBP DKava O0
0.60
CROWN-IBP (Ran = 0.5)
0.750
IBP (Kere 0.5)
0.55
0.725
0.50
0.45
0.700
30
60
90
120
30
60
90
120
Schedule Length
Schedule Length
(a) small models, 2/255, best 48.87%
(b) small modcls, 8//25,, best 70.61%
Figure C: Verified error vs. schedule length (30, 60, 90, 120) on small models on CIFAR-10. The solid boxes show median values of verified errors. Ksturt 1.0 except for the 0 setting. The upper and lower bound of an error bar are worst and best verified error, respectively.
G REPRODUCIBILITY
To further test the training stability of CROWN-IBP, we run each MNIST experiment (using selected models in Table B 5 times to get the mean and standard deviation of the verified and standard errors on test set. Results are presented in Table D Standard deviations of verified errors are very small, giving us further evidence of good stability and reproduciblity.
entor
model A
model H
model C
model 13
model E
model F
model G
model H
model
model J
0.1
verifled enc (%)
std. em (%)
6,85 2 04
2.77 1 04
1.88 2
145 1 05
3.02 1 01
6.67
+ 1
1.77 1 .4
5.10
2:13 1 08
4.82 2.2222 .2
4,18 008
1.35 1 .06
2.03 1. 108
5,23 +
4,59 4: 08
1.32 1. 08
5,32
1.77
.0
119
5.40 + KM
1.45 :: .05
0.2
verifiedd
(%)
3.87 1 04
244
4.40 1 2
2,32 .4
3.45 .
6,05
1,90 0
2.67
7.50
2.00
6.45
2,23 104
7,50
1:05 1:
0.3
verified em (%)
std. or. (16)
4.4.4.00 08
10.6 m66
3.2020
16.1 3
0.78
11.3
3.102.1
11.7 2
9.96 =
X.10=
12.2 6
2.55
9.50 2
11.2 .19
2:36
9:21 4
0.4
verifled on. (16
std. emc (4)
6.45 1. 04
24.6
18.5 .2
1.851111
8.53 1
20.6 7
5,85 2
19:2 2
5.48
18.8 2 17.3
1.2
3.85 1 00
0. 004
6.80 6.80.1.2
20.4
0.28 1.1
16.3 12
18.3 .07
5,00 1.001.111
3.60 1.
15.2 d
Table E: Means and standard deviations verified and standard errors of MNIST models trained
using CROWN-IBP The architectures of these models are presented in Table We run each model 5 times to compute mean and standard deviation.
H TRAINING STABILITY EXPERIMENTS ON OTHER
Similar to our experiments in Section 4 we compare the verified errors obtained by CROWN-IBB and IBP under different schedule lengths (10, 15, 30, 60) MNIST and 60.,60.0,, 120) CIFAR-10. 10. We present the best, worst and median verified errors over all 18 models for MNIST in Figure D E at e E {0.1, 0.2, 0.3) and small models for CIFAR-10 in Figure C The upper and lower ends of an error bar are the worst and best verified error, respectively, and the solid boxes represent median values. CROWN-IBP can improve training stability, and consistently outperform IBP under different schedule length and K settings.
I OVERFITTING ISSUE WITH SMALL
E
We found that on MNIST for small 6, the verified error obtained by IBP based methods are not as good as linear relaxation based methods (Wong et al. [2018] Mirman et al., 2018). Gowal ct al. (2018) thus propose to train models using a larger and evaluate them under a smaller e, for example rrain 0.4 and feval 0.3. Instead, we investigated this issue further and found that many CROWN-IBP trained models achieve very small verified errors (close to and sometimes exactly 0) on training set (see Table This indicates possible overfitting during training. As we discussed in Section 3 linear relaxation based methods implicitly regularize the weight matrices so the network does not overfit when is small. Inspired by this finding, want to see if adding explicit E
21

---

Published as a conference paper at ICLR 2020
CROWINIIB (K O) Q] LACWIN-HH
CROWN-IBF (K
O) CROWN-IBP (F
Verified Error
Verified Error
0.08
IBP Uhind O)
BP
0.11
CROWIN-IB (W 0.5)
CROWN-IBP (hau 0.5)
IBP USana 0.5)
BP IKaea 0.5)
0.06
0.09
0.06
0.04
0.03
0.04
10
15
30
60
10
15
30
60
Schedule Length
Schedule Length
(a) 0.1, best 3.55%
(b) 0.2, best 4.98%
Figure D: Verified error vs. c schedule length (10, 15, 30, 60) on medium MNIST models. The upper and lower ends of vertical bar represent the worst and best verified error, respectively. The solid boxes represent the median values of the verified error. For a small using a shorter schedule length improves verified error due to early stopping, which prevents overfitting. All best verified errors are achieved by CROWN-IBP regardless of schedule length.
Verified Error
10P (x
Verified Error
CIOWNEE
EJ
Verified Error
CROWNATE Now O0) DO ChOWNISS
0.08
0.11
CADWN
0.15
0.09
0.20
0.04
0.00
0.03
0.04
0.05
30
60
Schedule Length
Schedule Length
Schedule Length
(a) = 0.1, best 3.84%
(b) 0.2, best 6.11%
(c) 0.3, best 8.87%
Figure E: Verified error vs. e schedule length (10, 15, 30, 60) on 10 small MNIST models. The upper and lower ends of vertical bar represent the worst and best verified error, respectively. All best verified errors are achieved by CROWN-IBI regardless of schedule length.
regularization term in CROWN- IBP training helps when Grain = 0.1 or 0.2. The verified and standard errors on the training and test sets with and without regularization can be found in Table We can see that with small & regularization added (A 5 x 10-5) we can reduce verified errors on test set significantly. This makes CROWN-IBP results comparable to the numbers reported in convex adversarial polytope (Wong et al. 20118: at c = 0.1, the best model using convex adversarial polytope training can achieve 3.67% verified error, while CROWN-IBP achieves 3.60% best certified error on the models presented in Table The overfitting is likely caused by IBP's strong learning power without over-regularization, which also explains why IBP based methods significantly outperform linear relaxation based methods at larger values. Using early stopping also improve verified error on test set; see Figure D
J TRAINING TIME
In Table G we present the training time of CROWN-IBP, IBP and convex adversarial polytope (Wong et al. 2018) on several representative models. All experiments are measured on a single RTX 2080 Ti GPU with 11 GB RAM except for 2 DM-Large models where we use 4 RTX 2080 Ti GPUs to speed up training. We can observe that CROWN-IBP is practically 1.5 to 3.5 times slower than IBP. Theoretically, CROWN-IBP is up ng 10 times slower" than IBP; however usually the total training time is less than 10 times since the CROWN-IBP bound is only computed during the ramp-up phase, and CROWN-IBP has higher GPU computation intensity and thus better GPU utilization than IBP. convex adversarial polytope (Wong et al.) 2018), as a representative linear relaxation based
More precisely, ny times slower as can omit the all-zero row in specification matrix Fq.
22

---

Published as a conference paper at ICLR 2020
Model Name (sec Appendix
À: regularization
Training
Test
standard error
verified emoor
standard error
verified error
0.01%
0.01%
1.05%
5.63%
10-6
0.32%
0.98%
1.30%
3.60%
0.1
0.02%
0.05%
0.82%
6.02%
O
x 10-5
0.38%
1.34%
1.43%
4.02%
0
0.35%
1.40%
1.09%
6.06%
P
x 10-5
1.02%
3.73%
1.48%
5,48%
0.2
O
0
0.31 %
1,54%
1.22%
6.64%
O
x 10-6
1.09%
4.08%
1.69%
5.72%
Table F: & regularized and unregularized models' standard and verified errors training and test set. At a small c, CROWN-IBP may overfit and adding regularization helps robust generalization, on the other hand, convex relaxation based methods (Wong et al. 2018) provides implicitly regularization which helps generalization under small but deteriorate model performance at larger
method, can be over hundreds times slower than IBP especially on deeper networks. Note that we use 50 random Cauchy projections for (Wong et al., 2018). Using random projections alone is not sufficient scale purely linear relaxation based methods to larger datasets, thus we advocate combination of IBP bounds with linear relaxation based methods as in CROWN-IBS which offers good scalability and stability. We also note that the random projection based acceleration also be applied to the backward bound propagation (CROWN-style bound) in CROWN-IBP to further speed up CROWN-IBP.
Table G: IBP and CROWN-IBBP training time on different models seconds. For IBP and CROWN- IBP, a batchsize of 256 for MNIST and 128 for CIFAR-10. For convex adversarial polytope, we use random Cauchy projections, and reduce batch size necessary to into GPU memory.
Data
CIFAR-10
Model Name
A
G
L
DM-large
0.4)
H
M
DM-large
IBP (s) (R
245
264
290
364
1032
3769'
734
908
1048
691
1407
40496
954
5584!
4137
91288'
CAP Wong et al. 2018 (6)
1708
9263
12649
35518
160794
2372
12688
18691
6961
51145
We use GPUs train this model.
Convex adversarial polytopes (CAP) are computed with 50 ramdom projections. Without random
projections will scale most models except for the smallest ones.
K REPRODUCING CIFAR-10 RESULTS ON MULTI-GPUS
The use 32 TPUs for our CIFAR-10 experiments is not necessary. We use TPUs mainly for obtaining completely fair comparison IBP (Gowal al. 2018), their implementation was TPU-based. Since TPUs are not widely available, we additionally implemented CROWN-IBP using multi-GPUs. We train the best models in Table on 4 RTX 2080Ti GPUs. As shown in Table H we can achieve comparable verified errоrs using GPUs, and the differences between GPU and TPU training are around +0.5%. Training time is reported in Table G
L EXACT FORMS OF THE CROWN-IBP BACKWARD BOUND
CROWN (Zhang et al. 2018) is general framework that replaces non-linear functions in a neural network with linear upper and lower hyperplanes with respect to pre-activation variables, such that the entire neural network function can be bounded by a linear upper hyperplane and linear lower hyperplane for all æ S (S is typically a norm bounded ball, box region):
Ar +
CROWN achieves such linear bounds by replacing non-linear functions with linear bounds, and utilizing the fact that the linear combinations of linear bounds are still linear, thus these linear bounds
23

---

Published as a conference paper at ICLR 2020
Table H: Comparison of verified and standard errors for CROWN-IBP models trained on TPUs and GPUs (CIFAR-10, DM-Large model).
Dataset
(oxo norm)
Training Device
schedules
Model errors (%) Standard
Ristart
Kend
Verified
Crest
2,
2
GPU
0
0
29.18
45.50
CIFAR-10
Cirain 255
TPU
0
28.48
46.03
GPU
0
54.60
67.11
Fiminn 263
8.8
TPU
54.02
66.94
1 We use Sstart gend 1 for this setting, the same as in Table 2 and thus CROWN-IBP
bound is used evaluate the verified error.
can propagate through layers. Suppose we have non-linear vector function a, applying to input (pre-activation) vector 2, CROWN requires the following bounds in a general form:
A z bb S 50(z) +b
Ag A by for different a needs to be given in a case-by-case In general the specific bounds A, b, basis, depending on the characteristics of a and the preactivation range S Z. In neural network common a can be ReLU, tanh, sigmoid, maxpool, etc. Convex adversarial polytope (Wong et al. 2018) is also a linear relaxation based techniques that closely related to CROWN, but only for ReLU layers. For ReLU such bounds are simple, where A, Ag are diagonal matrices, b,
D= {0(z)) Dz
(14)
where D and D are two diagonal matrices:
1, if 24 > O, i.e., this neuron is always active 2 < O, i.e., this neuron is always inactive a, otherwise, any 0 S a S
D &
(15)
1,
if 24 > 0, i... this neuron is always active E < 0, i.e. this neuron is always inactive otherwise
D k
(16)
Su 8u-8x
0,
if mか > 0, i.e. this neuron is always active if < 0, ie.. this neuron is always inactive otherwise
Ck
O,
(17)
Eu
Note that CROWN-style bounds require to know pre-activation bounds 20) and 2(), We assume these bounds are valid for E S. In CROWN-IBP, these bounds are obtained by interval bound propagation (IBP). With pre-activation bounds z ( and z(4) given (for E S), we rewrite the CROWN lower bound for the special case of ReLU neurons:
Theorem L.1 (CROWN Lower Bound). For a L-layer neural network function f(x) R2 + R"L Vj [nz], Væ S, we have (x) S fz(x), where
L
fz(x) = 100
A J.
(b + +b(00),
(18)
1=1
if = L;
A
A (11) (((1)(()))) Di(0)
A
ifl {0. ... 1-1..
24

---

Published as a conference paper at ICLR 2020
and Vi E [mg]], define diagonal matrices DJ:(), bias vector b b
D
b bz(())
V' A
W (11)
2 0, > 1 le [1, , 1};
D
if
+1)
2 2 < < 1 LE ... --1k
if A (6+1)
W (++1)
<0, le (1.',,-1)
ifA (1+1) W (41)
2 0: le .1-1
by
20
if if U+ W (11) <0 f1, ... II, 1}.
J.
W(+1
R
ej I is standard unit vector with j-th coordinate set 1.
Note that unlike the ordinary CROWN (Zhang et al., 2018), in CROWN-IBP we only need the lower bound to compute m and do not need compute the A matrices for the upper bound. This save half of the computation cost in ordinary CROWN. Also, W represents any affine layers in neural network, including convolutional layers CNNs. Section we discussed how to use transposed convolution operators to efficiently implement CROWN-IBP on GPUs.
Although in this paper we focus on the common case ReLU activation function, other general activation functions (sigmoid, max-pooling, etc) can be used in the network as CROWN is general framework to deal with non-linearity. For a more general derivation we refer the readers to (Zhang
al. 2018 and (Salman et al. 2019b).
25


Reviews:
[{"review_id": "SJeZNqlpqH", "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": "This work proposes CROWN-IBP - novel and efficient certified defense method against adversarial attacks, by combining linear relaxation methods which tend to have tighter bounds with the more efficient interval-based methods. With an attempt to augment the IBP method with its lower computation complexity with the tight CROWN bounds, to get the best of both worlds. One of the primary contributions here is that reduction of computation complexity by an order of \\Ln while maintaining similar or better bounds on error. The authors show compelling results with varied sized networks on both MNIST and CIFAR dataset, providing significant improvements over past baselines.\n\nThe paper itself is very well written, lucidly articulating the key contributions of the paper and highlighting the key results. The method and rationale behind it quite easy to follow.\n\n\nPros:\n> Show significant benefits over previous baseline with 7.02% verified test error on MNIST at  \\epsilon = 0.3, and 66.94% on CIFAR-10 with \\epsilon = 8/255\n> The proposed method is computationally viable, with up to 20X faster than linear relaxation methods with similar. better test errors and within 5-7X slower than the conventional IBP methods with worse errors\n\nCons:\n> Extensive experiments with more advanced networks/datasets would have been more convincing, esp. given the computation efficiency that enables such experiments\n> More elaborate insights into the choice of the training config/hyper-params esp. with the choice of \\K_start, \\K_end across the different datasets\n\n\nOther comments:\n> For the computational efficiency studies, it would be helpful to provide a breakdown of the costs between the different layers and operations, to better asses/confirm that benefits of CROWN-IBP method\n> Impact of other complementary techniques such a lower precision/quantization? One fo the references compared against is the Gowal et al. 2018 for the as a baseline, however, it seems to be those results were obtained on a different HW platform (TPUs - motioned in Appendix-B), with potentially different computational accuracies (BFLOAT16 ?). So, this bears to question of the impact of precision on these methods and also the computation complexity.\n> Since I'm not very well versed with the current baseline and state-of-art for variable robust training of DNN, it would be good to get an additional confirmation on the validity of the used baselines.", "extra_scores": {"experience_assessment": "I do not know much about 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 assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "HJgnxLMMcH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a new variation on certified adversarial training method that builds on two prior works IBP and CROWN. They showed the method outperformed all previous linear relaxation and bound propagation based certified defenses. \n\nPros:\n1. The empirical results are strong. The method achieved SOTA.\n\nCons:\n1. Novelty seems small. It is a straightforward combination of prior works, by adding two bounds together.\n2. Adds a new hyperparameter for tuning.\n3. Lack of any theoretical insights/motivation for the proposed method. Why would we want to combine the two lower bounds? The reason given in the paper is not very convincing:\n\n\"IBP has better learning power at larger epsilon and can achieve much smaller verified error.\nHowever, it can be hard to tune due to its very imprecise bound at the beginning of training; on the\nother hand, linear relaxation based methods give tighter lower bounds which stabilize training, but it\nover-regularizes the network and forbids us to achieve good accuracy.\"\n\nMy questions with regards to this:\n(i) Why does loose bound result in unstable training? Tighter bound stabilize training?\n(ii) If we're concerned with using a tighter bound could result in over-regularization, then why not just combine the natural loss with the tight bound, as natural loss can be seen as the loosest bound. Is IBP crucial? and why?\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "H1eplpk-5H", "reviewer": "AnonReviewer2", "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": "This paper proposes a new method for training certifiably robust models that achieves better results than the previous SOTA results by IBP, with a moderate increase in training time. It uses a CROWN-based bound in the warm up phase of IBP, which serves as a better initialization for the later phase of IBP and lead to improvements in both robust and standard accuracy. The CROWN-based bound uses IBP to compute bounds for intermediate pre-activations and applies CROWN only to computing the bounds of the margins, which has a complexity between IBP and CROWN. The experimental results are verify detailed to demonstrate the improvement.\n\nThe improvement is significant enough to me and I tend to accept the paper. The results on CIFAR10 with epsilon=8/255 is so far the state-of-the-art. However, it is far from being scalable enough to large networks and datasets, which has already been achieved by randomized smoothing based approaches. On CIFAR10, it takes 32 TPU cores to train a 4-conv-layer network. Still, such an approach has the advantage of making robust inferences much more efficiently than randomized smoothing, and thus still worth further explorations.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents a method that hybridizes the strategies of linear programming and interval bound propagation to improve adversarial robustness.  While some reviewers have concerns about the novelty of the underlying ideas presented, the method is an improvement to the SOTA in certifiable robustness, and has become a benchmark method within this class of defenses.
Decision: Accept (Poster)