Improved Training of Certifiably Robust Models
Authors: Chen Zhu
Renkun Ni
Ping-yeh Chiang
Hengduo Li
Furong Huang
Tom Goldstein
Venue:  (2020)
Keywords: Convex Relaxation
Certified Robustness
Regularization

Abstract: Convex relaxations are effective for training and certifying neural networks against norm-bounded adversarial attacks, but they leave a large gap between certifiable and empirical (PGD) robustness. In principle, relaxation can provide tight bounds if the convex relaxation solution is feasible for the original non-relaxed problem. Therefore, we propose two regularizers that can be used to train neural networks that yield convex relaxations with tighter bounds. In all of our experiments, the proposed regularizations result in tighter certification bounds than non-regularized baselines. 

Under review as a conference paper at ICLR 2020
IMPROVED TRAINING OF CERTIFIABLY ROBUST MOD- ELS
Anonymous authors Paper under double-blind review
ABSTRACT
Convex relaxations are effective for training and certifying neural networks against norm-bounded adversarial attacks, but they leave large gap between certifiable and empirical robustness. In principle, convex relaxation can provide tight bounds if the solution to the relaxed problem is feasible for the original non-convex problem. Therefore, we propose two regularizers that can be used to train neural networks that yield tighter convex relaxation bounds for robustness. In all of our experiments, the proposed regularizers result in higher certified accuracy than non-regularized baselines.
INTRODUCTION
Neural networks have achieved excellent performances on many computer vision tasks, but they could be vulnerable to small, adversarially chosen perturbations that are barely perceptible humans while having a catastrophic impact on the network's 's performance (Szegedy et al. 2013 Goodfellow let al. 2014). Making classifiers robust to these adversarial perturbations is of great interest, especially when neural networks are applied to safety-critical applications. Several heuristic methods exist for obtaining robust classifiers, however powerful adversarial examples can be found against most of these defenses (Carlini & Wagner 2017 Uesato et al., 2018).
Recent studies focus on verifying or enforcing the certified accuracy of deep classifiers, especially for networks with ReLU activations. They provide guarantees of network's 's robustness to any perturba- tion 8 with norm bounded by |61|p S c (Wong & Kolter 2017 Wong et 2018 Raghunathan et al.) 2018 Dvijotham et al., (2018)) ZZhang et al.)
al.]]21111 [218]]
[018]]Salman (Salman et al. (2099). There are exact veriteess that
find the exact minimum adversarial distortions o or the robust error (Ehlers) 2017 Katz al.) 2017]
Tjeng et al. 2017). but due to the non-convex nature of the problem, exact verification is NP-hard. To make verification efficient and scalable, convex relaxations are adopted to expand the non-convex feasible set given by non- non-linear activations into convex sets, resulting in lower bound the norm of adversarial perturbations (Zhang et al.) [2018] Weng et al. (2018). or an upper bound on the robust error (Dvijotham et al. 201 Gehr al.] 2018]] (Singh al. 2018). With LP relaxations (Wong) et al. 2018), such a verifier can be efficient enough to estimate the lower bound of the margin in each iteration for training certifiably robust networks. However, due to the relaxation of the underlying problem, the lower bound of the margin is potentially loose, and thus a barrier remains between the optimal values from the original and relaxed problems (Salman et al. 2019).
In this paper, we focus on improving the certified robustness of neural networks trained with convex relaxation bounds. To achieve this, we first give a more interpretable explanation for the bounds achieved in (Weng et al. 2018 Wong et al. 2018). Namely, the constraints of the relaxed problem are defined by simple linear network with adversaries injecting bounded perturbations to both the input of the network and the pre-activations of intermediate layers. The optimal solution of the relaxed problem can be written as a forward pass of the clean image through the linear network, plus the cumulative adversarial effects of all the perturbations added to the linear transforms, which makes it easier to identify the optimality conditions and serves as a bridge between the relaxed problem and the original non-convex problem. We further identify conditions for the bound to be tight, and we propose two indicators for the gap between the original non-convex problem and the relaxed problem. Adding the proposed indicators into the loss function results in classifiers with better certified accuracy.

---

Under review as a conference paper at ICLR 2020
2 BACKGROUND AND RELATED WORK
heuristic defenses and verifiable defenses. The heuristic defenses either try to identify adversarial examples and remove adversarial perturbations from images, or make the network invariant to small perturbations through training (Papernot & McDaniel 2018; Shhan et al.) 2019; [Samangouei et al., 2018: Hwang et al.] 2219).. In addition, adversarial training uses adversarial examples as opposed to clean examples during training, so that the network can learn how to classify adversarial examples directly (Madry et al. [2077 Shafahi et al. 2019 Zhang et al. (019a)).
Adversarial defenses roughly fall into two categories:
In response, a line of works have proposed to verify the robustness of neural nets. Exact methods obtain the perturbation with minimum [|öí| such that f(x) + [(x + d). where f is a classifier and x is the data point. Nevertheless, the problem itself is NP-hard and the methods can hardly
scale (Cheng et al. [0117] Lomuscio & Magantii [017 Dutta et al.
2018 Fischetti & Jo 2017: Tjeng
ct al. 2017 Scheibler et al. 2015 Katz al. 2017] Carlini et al.
2017: Ehlers 2017).
body of work focuses on relaxing the non-linearitics in the original problem into linear inequality
constraints (Singh et al.] 2018; Gehr et al.) [2018] Zhang al. 20188] Mirman al. 2018), sometimes using the dual of the relaxed problem (Wong& & Kolter [2017 |olter|2011]
[/on et al. [2018] Dvijotham et al.)
2018b). Recently, /Salman et al. (2019) unified the primal and dual views into a common convex relaxation framework, and suggested there is an inherent gap between the actual and the lower bound of robustness given by verifiers based on LP relaxations, which they called convex relaxation barrier.
Some defense approaches integrate the verification methods into the training of a network minimize robust loss directly. Hein & Andriushchenko (2017) uses local lipschitz regularization to improve certified robustness. In addition, bound based on semi-definite programming (SDP) relaxation was developed and minimized as the objective (Raghunathan et al., 2018). [Wong& & Kolter (2017) presents an upper bound on the robust loss caused by norm -oonddddnded perturbation via LP relaxation, and minimizes this upper bound during training. [Wong et al. (2018) further extend this method to much more general network structures with skip connections and general non- non-lincarities, and provide memory- -rienddly training strategy using random projections. Since LP relaxation is adopted, the aforementioned convex relaxation barrier exists for their methods.
While another line of work (IBP) have shown that intuitively looser interval bound can be used to train much more robust networks than convex relaxation for large &oo perturbations (Gowal et al. 2018. [Zhan al. 2011b), it is still important to study convex relaxation bounds since it can provide better certificates against a broader class of adversaries that IBP struggles to certify in some cases, such as la adversaries for convolutional networks. We give brief discussion for the reason in Appendix B
We seek enforce the tightness of the convex relaxation certificate during training. It reduces the optimality gap between the original and the relaxed problem by adding the proposed indicators into the loss function as regularizers. Compared with previous approaches, we have the following contributions: First, based upon the same relaxation in (Weng et al.) 2018). we illustrate a more intuitive view for the bounds on intermediate ReLU activations achieved by (Wong et al. 2018) which can be viewed as a linear network facing adversaries adding bounded perturbations to both the input and the intermediate layers. Second, starting from this view, we identify conditions where the bound from the relaxed problem is tight for the original non-convex problem. Third, based on the conditions, we propose regularizers that encourage the bound to be tight for the obtained network, which improves the certificate both MNIST and CIFAR-10.
3 PROBLEM FORMULATION
In general, to train an adversarially robust network, we solve a constrained minimax problem where the adversary tries to maximize the loss given the norm constraint, and the parameters of the network are trained to minimize this maximal loss. Due to nonconvexity and the complexity of neural networks, it is expensive to solve the inner max problem exactly. To obtain certified robustness, like many related works (Wong et al.) 2018 Gowal et al.) 2018), we minimize an upper bound of the inner max problem, which is cross entropy loss the negation of the lower bounds of margins over each
2

---

Under review as a conference paper at ICLR 2020
other class, as shown in Eq. Without loss of generality, in this section we analyze the original and relaxed problems for minimizing the margin between the ground truth class y and some other class t under norm-bounde adversaries, which can be adapted directly to compute the loss in Eq.
The original nonconvex constrained optimization problem for finding the norm-bounded adversary that minimizes the margin can be formulated as
minimize of Fr,, subject to si+1 = (x;), fi(z.), for L,...,,, 21 p.)
(O)
where e = Ey Et, Ey and Er are one-hot vectors corresponding to the label y and some other class t, (-)) is the ReLU activation, and fi is one functional block of the neural network. This can be linear layer (z,) = W + bj), or even a residual block. We use (2 = fi(o to denote the ReLU network up to the i-th layer, and po to denote the optimal solution to O
(x))))
S
Kg
Xi
Eg
Bounded RcLU Constraiot
Optimal Layer-wisc Relaxation
Efficient Relaxation
Figure The feasible sets (blue regions/lines) given by the bounded ReLU constraints (Eq. convex hull (zom)T and the relaxation (Fast-Lin) discussed in this paper (specific choice for Eq. for E I. The red lines and dots are the intersections between the boundaries of the convex feasible sets and the ReLU constraints.
3.1 EFFICIENT CONVEX RELAXATIONS
Grouping of ReLU Activations
The nonconvexity of O stems from the nonconvex feasible set given by the ReLU activations. Since the network is continuous function, the pre-activations I, have lower and upper bounds yg and ã; when the input 2 E Bp (x). If certain pre-activation Tij has Byj < 0 Fajs its corresponding ReLU constraint 1 ( gives rise to non-convex feasible set as shown in the left of Figure]] |
making Eq. non-convex optimization problem. On the other hand, if øzj S 0 or Eij 2 0, the constraints degenerate into linear constraints 21+1,
and 2i+1.j Zij respectively, which do not affect convexity. Based on i and F; we divide the ReLU activations into three disjoint subsets
I = (j E.j S 0}, I = Gizy 2 0}. I, = وعاز < < T,yh.
(1)
j E Z,, call the corresponding ReLU activation unstable neuron.
Convex relaxation expands the non-convex feasible sets into convex ones and solves a convex optimization problem C. The feasible set Of a subset of the feasible set of C, the optimal value of C lower bounds the optimal value of Eq. O Moreover, we want problem C' to be solved efficiently, be integrated into the training process.
better with closed form solution, so that
Computational Challenge for the "optimal" Relaxation As pointed out by (Salman et al. 2019 the optimal layer-wise convex relaxation, i.e., the optimal convex relaxation for the nonlinear constraint 2;+1 = o (I;)) of single layer, can be obtained independently for each neuron. For each j E I; in a ReLU network, the optimal layer-wise convex relaxation the closed convex hull cont.; of Sij (Tigj =1+1, E I, Zi+ max(0, ziz); I Øaj < Tzj ). which is just Te L E,y)], corresponding to the triangle E.y-E,
cont. = [ 2++15) ma (0;)))) 21-15
region in the middle of Figure Despite being relatively tight, there is no closed-for foom solution to this relaxed problem. LP solvers are typically adopted to solve linear programming problem for each neuron. Therefore, such relaxation is hardly scalable to verify larger networks without any additional trick (like Xiao et al. (2018)). Weng al. (2018) find it to be 34 to 1523 times slower than Fast-Lin, and it has difficulty verifying MLPs with more than 3 layers on MNIST. In (Salman et al. 2019), it takes 10,000 CPU cores parallelize the LP solvers for bounding the activations of every neuron in a wwo-hidden-layer MLP with 100 neurons per layer. Since solving LP problems for all neurons usually impractical, is even more difficult to optimize the network maximize the
3

---

Under review as a conference paper at ICLR 2020
lower bounds of margin found by solving this relaxation problem, differentiating through the LP optimization process is even more expensive.
Computationally Efficient Relaxations In the layer-wise convex relaxation, instead of using boundary nonlinear in Tij. (Zhang et al. (018)) has shown that for any nonlinearity, when both the lower and upper boundaries are linear in Taj. there exist closed-form solutions to the relaxed problem. which avoids using LP solvers and improves efficiency. Specifically, the following relaxation of has closed-form solutions:
minimize
C. IL.
subject to
2. Hy + by S ž₁ S 5 a. ...... D2 + bi L. S x3 S Ti.
(C)
x W,4 + b,. for l..., L, E (x)(
where denotes element wise product, and for simplicity, we have only considered networks with no skip connections, and represent both Full Connected and Convolutional Layers as linear transform fi(2;) Wi2; + by-
Before we can solve to get the lower bound of margin, we need to know thee range [x. 7.] for the arevactivations z;- As in (Wong& & Kolter [0177] Weng et al. 20188 Zhang al.) 2018), we can solve the same optimization problem for each neuron Zij starting from layer I to L, by replacing e, with ej or -ej for Lij or Fij respectively TT
The most efficient approach in this category is Fast-Lin (Weng et al. 2018). which sets G.j- = a.j. as shown in the right of Figure [ A tighter choice is CROWN (Zhang et al. 2018), which chooses different Lij and 0.j such that the convex feasible set is minimized. However, CROWN has much higher complexity than Fast-Lin due to its varying slopes. We give detailed analysis of the closed- form solutions of both bounds and their complexities Appendix [ Recently, CROWN-IBP (Zhang et al. 2019b) has been proposed to provide better initialization to IBP, which uses IBP to estimate range Ey Fy for CROWN. In this case, both CROWN and Fast-Lin have the same complexity and CROWN is better choice.
4 TIGHTER BOUNDS VIA REGULARIZATION
Despite being relatively efficient to compute, Fi and CROWN are not even the tightest layer- wise convex relaxation. Using tighter bounds to train the networks could potentially lead to higher certified robustness by preventing such bounds from over-regularizing the networks. Nevertheless, there exist certain parameters and inputs such that the seemingly looser Fast-Lin is tight for i.e., the optimal value of Fast-Lin is the same as O The most trivial case is where unstable neuron exists. In practice, as shown in the illustrative example in Appendix A Fast-Lin can be tight even when unstable neurons exist. It therefore interesting check the conditions for Fast-Lin or CROWN to be tight for O and enforcing such conditions during training to improve the certified robustness.
4.1 CONDITIONS FOR TIGHTNESS
Here we look into conditions that make the optimal value Pe of the convex problem C be equal to P Let {2,, 24 //= be some feasible solution of C, from which the objective value of C can be L be some feasible solution of O computed by passing zi through the ReLU sub-networks ) defined in O and denote the resulting feasible objective value as P0 = c. a',
determined pc c. æt. Let {2/, x4
Generally, for a given network with the set of weights (W,, b 1 as long as the optimal solution {2 x; -;);= of C is equal to feasible solution {2/, x11/ of O we will have po Pc- since any feasible Po of O satisfies po 2 pb, and by the nature of relaxation pC - P
Therefore, for a given network and input to check the tightness of the convex relaxation, can check whether its optimal solution {2 H= is feasible for O. This can be achieved by passing = through the ReL.U network, and either directly check the resultant objective value p'- or compare {2, x;, L with the resultant feasible solution {2/, L Further, we can encourage such
For R.y, take negation on the solution.
4

---

Under review as a conference paper at ICLR 2020
conditions to happen during the training process to improve the tightness of the bound. Based on such mechanisms, we propose two regularizers to enforce the tightness. Notice such regularizers are different from the RS Loss (Xiao et al., 2018) introduced to reduce the number of unstable neurons, since we have shown with Appendix that C can be tight even when unstable neurons exist.
4.2
A INTUITIVE INDICATOR OF TIGHTNESS: Po Pe
The observation above motivates us consider the non- non-negative value
d(x, 5g. W,b) (2, Pč
(2)
as an indicator of the difference between , and { =(,=())== where (6 68) c, hz 6)) is the margin over class computed by passing the optimal perturbation og for through the original network. 6g can be computed efficiently from the optimality condition of Fast-Lin or CROWN, as demonstrated in Eq. 16 For example, when p = oc, the optimal input perturbation S of C is 6 -esign(c, WLa), which corresponds sending 2 2j esign(c, WL.) c Wi.. which corresponds to sending through the ReI.U network; when p 2, 56 = -1 ll. W2.12"
c. We.1 z1 = = x Tc Wzalla
The larger d(x;, 6/. W, b) is, the more relaxed is, and the higher pà - PC could be. Therefore, we can regularize the network to minimize dxx 6g. W, b) during training and maximize the lower-bound of the margin Pč: so that we can obtain a network where P is a better estimate of p and the robustness is better represented by PC- Such an indicator avoids comparing the intermediate variables, which gives more flexibility for adjustment. It bears some similarities to knowledge distillation (Hinton) al. 2015), in that encourages learning a network whose relaxed lower bound gives similar outputs of the corresponding ReLU network. It is worth noting that minimizing d(x, ög. W, 6) does not necessarily lead to decreasing (Ir dū) or increasing Pć- In fact, both p'e (2, 86) and pt can be increased or decreased at the same time with their difference decreasing.
The tightest indicator should give the minimum gap Pb Pe: where we need to find the optimal perturbation for + However, the minimum gap cannot be found in polynomial time, due to the non-convex nature O (Weng al., 2018) also proved that there is no polynomial time algorithm to find the minimum é moomr adversarial distortion with 0.99 In n approximation ratio unless NP=P, a problem equivalent to finding the minimum margin here.
4.3 A BETTER INDICATOR FOR REGULARIZATION DIFFERENCE IN SOLUTIONS
Despite being intuitive and is able achieve improvements, Eq. which enforces similarity between objective values does not work as good as enforcing similarity between the solutions {2, æt 1 and {2/, T in practice, an approach we will elaborate below. For both CROWN and Fast-Lin, unless d(xx, 87: W, b) O, {z x 1 may deviate a lot from x=),=() and does not correspond to any ReLU network, even if d(ær, dj. W, b) may seem small. For example, it is possible that zij < 0 for given of, but ReLU network will always have z/g 0.
We find an alternative regularizer more effective at improving verifiable accuracy. The regularizer encourages the feasible solution {2/, 2/) of O to exactly match the feasible optimal solution {z] x 1 of C. Since we are adopting the layer-wise convex relaxation, the optimal solutions of the unstable neurons can considered independently.
Here we derive sufficient condition for tightness for Fast-Lin, which also serves sufficient condition for CROWN. For linear programming, the optimal solution occurs on the boundaries the feasible set. Since Fast-Lin is layer-wise convex relaxation, the solution to each of its neurons in z; can be considered independently, and therefore for a specific layer and j E I,, the pair of optimal solutions 2f+1.) should occur the boundary in the right of Figure [ It follows that the only
3 optimal solutions ( 25+1.)) of C that are also feasible for O are (Eay- 0). (T.j. Fiy) and (0, 0). Notice they are also in the intersection between the boundary of CROWN and
In practice, out of efficiency concerns, both Fast-Lin and CROWN identify the boundaries that the optimal solution lies on and computes the optimal value by accumulating the contribution of each layer in a backward pass, without explicitly computing {=] xx J for each layer with forward
5

---

Under review as a conference paper at ICLR 2020
pass (see Appendix F for more details). It is therefore beneficial to link the feasible solutions of O to the parameters of the boundaries. Specifically, let o2 E (big. big be the intereept of the line that the optimal solution (21) 2(m1g) lies on. We want to find a rule based on { ) to determine whether the bound is tight from the values of (x/)(=1- For both Fast-Lin and CROWN,
FayKa bi 0, bij Fag Eay For Fast-Lin, when 8% = -bjj. only (z 2(+1,) = (Zig. 0) or (Zij. Zij) are fesible for when o = b.y only (T =(+1,) = (0,0) 0) is feasible for Meanwhile, 2(+1, = max ij. 0) is deterministic if æ/ is given. Therefore, when the bound is tight for Fast-Lin, if 8/ = b.y then iyy O. Otherwise, if o bi.. and z/j Σij or Eay- For CROWN, this condition also feasible, though it could be either æi, or z'y 2 0 when oū O, depending the optimal slope D.
Indeed, we achieve optimal tightness (0z pp)) for both Fast-Lin and CROWN if z/y satisfy these conditions at all unstable neurons. Specifically.
Proposition 1. Assume {24, xt 1- is obtained by the ReLU network by with input 2/1, and {6ī } 1==0 is the optimal solution of Fast-Lin CROWN. 2 x + 57. and v'g E S(8g)) for all 1. 1. 1 E Iú then {24, af is an optimal solution of O Fast-Lin and CROWN. Here
5(6))) = (Zng. Tzp
of
Tu 3. Bij 11--24
[0} o
We provide the proof of this simple proposition in the Appendix.
It remains be discussed how to best enforce the similarity between the optimal solutions of and Fast-Lin or CROWN. Like before, we choose to enforce the similarity between {</ and the closest
optimal solution of Fast-Lin, where {= is constructed by setting ø = . = W1(x + 65) + b1 and pass oi through the ReL.U network obtain x h,(x o%). By Proposition the distance
can be computed by considering the values of the intercepts {0 (--
r(x, 8g. W,
|o +
Σ
min(laly - Ezgh la4y xıs()) (3)
EEI
6 #0
where the first term corresponds 8/ and the condition oy (0), and the second term corresponds to ot ズıy= original ReLU network only needs to be optimized towards the nearest feasible optimal solution. It easy to see from Proposition that r(x, 5%. W.b) = O, then po pē, where could be both Fast-Lin CROWN.
7;,2;; and the condition x'y- (E.. To minimize the second term, the
Compared with d(x, ot, W, r(x, 85, W, 6) puts more constraints on the parameters W. b, since requires all unstable neurons of the ReLU network to match the optimal solutions of Fast-Lin, instead of only matching the objective values 1/o and pč. In this way, it provides stronger guidance towards network whose optimal solution for for[Oland and Fast-Lin CROWN agree. However, again, this is not equivalent to trying to kill all unstable neurons, since Fast- can be tight even when unstable neurons exist.

---

Under review as a conference paper at ICLR 2020
Algorithm I Computing the Fast-Lin Bounds and Regularizers for Lo Norm
Data: Clean images( J j= ReLU network with parameters W, b, and maximum perturbation
Result: Margin Lower Bound pč. Regularizer d(x, 6g. W, b) and r(ar, 6.. W.b).
Initialize W1.1 + W1. 91 (1) Wix + b1, 21 = (1( - e| T1 = 91 (a) +
el 1, Lrow for i=2...,,L+ L-1 do
Compute D with Eq. 13
Wil i; (3) +
I - (((x) - <l 1oo Ex= Ejet
2,4 min miin(().:+++)..))))
-
Ij - (x) + el/Wal 11. + == Ejely -,1-111
,,10,i min(-(Wess++))
end
Compute DL-1 with Eg.
13
WL.1 t WiDD-IWL-L,9100) -W +b
Compute Pe with Eq. 17
0g f-
c|lc. W2.1 1,row
w/ < ha; (x + ()) for
1 to T.
d(x, oū. W) 6 c, x't - pc
Compute r(z, 5, W, with Eq.
4.4 CERTIFIED ROBUST TRAINING IN PRACTICE
In practice, for classification problems with more than two classes, we will compute the lower bound of the margins w.r.t. multiple classes. Denote Pć and po as the concatenated vector of lower bounds of the relaxed problem and original problem for multiple classes, and de, r2 as the regularizers for the margins w.r.t. class t. Together with the regularizers, we optimize the following objective
minimize (ce(-Pé,u0 + Σ de W. + Σ re(x, og W,b), W.b
(4)
where LoE(- -Pe y) is the cross entropy loss with label y. as adopted by many related works (Wong al.) 2018 Gowal al.) 22018), and we have implicitly abbreviated the inner maximization problem w.r.t. (6. 1= into the optimal values Pč and solution 6%. More details for computing the intermediate and output bounds can found Algorithm where we have used || 1row to denote row-wise I norm, and (+), for taking the j-th column.
One major challenge of the convex relaxation approach is the high memory consumption. To compute the bounds Σ,, T4, we need to pass an identity matrix with the same number of diagonal entries the total dimensions of the input images, which can make the batch size thousands times larger than usual. To mitigate this, one can adopt the random projection from Wong et al. (2018), which projects identity matrices into lower dimensions as WA.1 R to estimate the norm of W. Such projections add noise/variance to Fi Ti and the regularizers are affected well.
EXPERIMENTS
Models, Datasets and Hyper- pappeeparameters:: We evaluate the proposed regularizer on two datasets (MNIST and CIFAR 10) with two different c each. We consider only fxx adversaries. We experiment with variety of different network structures, including MLP (2x100) with two 100-neuron hidden layers as (Salman et al.) 2019), two Conv Nets (Small and Large) that are the same as (Wong al. 2018), a familly of 10 small conv nets and a family of 8 larger conv nets, all the same as (Zhang et al. 2019b), and also the same 5-layer convolutional network (XLarge) as in the latest version of CROWN-IBP (Zhang et al. 2019b). For CROWN-IBP, we use the updated expensive training schedule as (Zhang et al. 2019b), which uses 200 epochs with batch size 256 for MNIST and 3200 epochs with batch size 1024 for CIFAR10. We use up to 4 GTX 1080Ti or 2080Ti for all our experiments.
Improved Training with Convex Relaxation Table Ishows comparisons with various approaches. All of our baseline implementations have improved compared with (Wong et al. 2018). When adding the proposed regularizers, the certified robust accuracy is further improved in all cases for both CP WWong al. 2018) and CROWN-IBP /Zhang al. 2019b). We also provide results against
7

---

Under review as a conference paper at ICLR 2020
Dataset
Model
Base Method
X
Rob. Err
PGD Err
Std. Err
MNIST
2x100, Exact
CP
0.1
0
0
14.85%
10.9%
3.65
MNIST
2x100, Exact
CP
0.1
2c-3
13.32%
10.9%
4.73%
MNIST
Small, Exact
CP
0.1
0
4.47%
2.4%
1.19%
MNIST
Small 11, Exact
CP
0.1
5e-3
Se-1
3.65%
2.2%
1.09%
MNIST
Best of PVl
0.1
4,44%
2.87%
1.20%
MNIST
Best of RS
0.1
4.40%
3.42%
1.05 %
MNIST
Small
CP
0.1
0
0
4,47%
3,3%
1.19%
MNIST
Small
CP
0.1
0
5e-1
4.32 %
3.4%
1.51%
MNIST
Targe
DAP
0.1
3.4%
2.4%
1.0%
MNIST
2x 100, Exact
CP
0.3
0
0
61 1.99%
49.4%
33. 16%
MNIST
2x100, Exact
CP
0.3
5c-3
5c-3
56.05% %
44.3%
26.10%
MNIST
Small. Exact
CP
0.3
0
0
31.25%
15.0%
7.88%
MNIST
Small Small, Exact
CP
0.3
5e-3
5e-1
29.65 %
13.7%
7.28 %
MNIST
Small
CP
0.3
0
0
42,7%
26.0%
15.93%
MNIST
Small
0.3
2c-3
2c-1
41.36 %
24.0%
14.29 %
MNIST
XLarge
IBP4
0.3*
8.05%
6.12%
1.66
MNIST
XLarge
CROWN-IBP
0.3"
7.01
5.88%
1.88%
MNIST
XLarge
CROWN-IBP
0.3
6.64%
1.76%
CIFARTO
Small
CP
2/255
53. 19%
48.0%
19%
CIFARIO
Small
CP
2/255
5o-3
5o-1
51.52%
47.0%
37.30% %
CIFARIO
Large
DAI
2/255
61.4%
55.6%
55.0%
CIFARIO
XTarge
IBP4
2/255*
49.98%
45.09%
29.84%
CIFARIO
XLazge
CROWN-IBP
2/255'
46.03%
40.28%
28.48%
CIFARIO
Large
CP
2/255
0
0
45.78%
38.5%
29.42%
CIFARIO
Large
CP
2/255
5e-3
5e-1
45.19%
38.8%
29.76%
CIFARIO IO
Srall
CP
8/255
0
0
75.45%
68.3%
62.79%
CIFARIO
Small
CP
8/255
lc-3
lc-1
74.70% %
67.9%
62.50 %
CIFARTO
Large
CP
8/255
0
0
74.04%
68, 8%
59.73%
CIFARIO
Large
CP
8/255
5e-3
5e-1
73.74% %
68.5%
59.82%
CIFARIO
XLarge
IBP
8/255*
67. 96%
65.23 %
50.51 %
CIFARIO
alarge
CROWN-IBP
8/255*
66.94%
65.42%
54.02%
CIFARIO
XLazge
CROWN-IBP
8/255*
0
5c-1
66.64% %
53.78%
Table 1: Results MNIST, and CIFARIO with small networks, large networks, and different coefficients of d(z, 86, W, b), r(x, 5, W 6). All entries with positive À or are using our regularizers. For all models not marked as "Exact", we have projected the imput dimension of Wi to 50, the same as Wong et al. (2018). For e val-
ues with larger is used for training. = 0.3. 2/255. 8/255 correspond to using 0.4, 2 2.2/255. 8.8 8.8/255
for training respectively. For the methods: DDijothha al. 2018at: 2, Xiao 2018); (Gowal et al. 2018).
2018
Mirman al.
100-step PGD adversary for CP models. We will add PGD error rates for CROWN-IBP models in our future version. Since both PGD errors and standard errors are reduced in most cases, the regularizer should have improved not only the certified upper bound, but also improved the actual robust error.
The relative improvement on 2x 100 with regularizer (10.3%/8.78 7%)) are comparable the im- provements (5.9% 55.9%/00.0% 10.0%) from (Salman et al. 2019), despite the fact that we start from a stronger baseline. This indicates that the improvement brought by using our regularizer is comparable with using the expensive and unstable optimal lase convex relaxation for relaxation.
Our results with Small are better than the best results of (Dvijotham al. 2018a Xiao al. 2018 on MNIST with e = 0.1, though not as good as the best of (Mirman et al. 2018). which uses larger model. When applying the same model on CIFAR10, we achieve better robust error than (Mirman et al. 2018).
The relative improvements in certified robust error for 0.1 and 0.3 are 18%/3.4% for the small exact model on MNIST, compared with 0.03% 133% for the random projection counterparts, In the exact models, we have better estimates of ng my. These consistent improvements validate that our proposed regularizers improve the performance.
In comparison with IBP-based methods, our regularizers is able to further improve CP on CIFARIO with e = 2/255, and demonstrate the best result among all approaches compared in this setting. To our knowledge, this the best result of models of the same size. By using our regularizers on CROWN- IBP provide better initialization for the later training stage of IBP, method also achieves the best certified accuracy on CIFAR1O under = 8/2 8/255. To provide more comprehensive evaluations, Table 4 shows the mean and variance of the results with smaller models, demonstrating consistent
8

---

Under review as a conference paper at ICLR 2020
Verified Test Error (%)
Standard Test Error (%)
Dataset
<((
Model Family
Method
best
median
worst
best
median
worst
Gowal
(2018)
8.05
1.66
CI Orig
7.46
8.47
8.57
1.48
1.52
1.99
MNIST 0.3
8 large models
CI Reimp
7.99
8.38
8.97
1.40
1.69
2.19
CT Reg
7.26
8.44
8.88
1.51
1.72
2.21
Table 2: Our results on the MNIST dataset, with CROWN-IBP. CI Orig are results copied from the paper, CI Relmp are results of our implementation of CROWN-IBP, and CT Reg with regularizer r.
improvements of our model, while Table 2 gives the best, median and worst case results with the large models on the MNIST dataset. Note all the networks are significantly smaller than (Gowal al. 2018), and our batch size and number of epochs (at most 256 and 140) are also much smaller than (Gowal et al. 2018 (1600 and 3200). Still, we are able to achieve better results.
CONCLUSIONS
We propose two regularizers that lead tighter LP relaxation bounds for certifiable robustness. Extensive experiments validate that the regularizers improve robust accuracy over non-regularized baselines. This work is step towards closing the gap between certified and empirical robustness. Future directions include methods to improve computational efficiency for LP relaxations (and certified methods in general), and better ways to leverage random projections for acceleration.
REFERENCES
Nicholas Carlini and David Wagner. Adversarial examples are not easily detected: Bypassing ten detection methods. In Proceedings of the 10th ACM Workshop on Artificial Inielligence and Security, pp. 3-14. ACM, 2017.
Nicholas Carlini, Guy Katz, Clark Barrett, and David Dill. Provably minimally-distortedd adversarial examples. arXiv preprint arXiv: I00./00770 2017.
Chih-Hong Cheng, Georg Nührenberg, and Harald Ruess. Maximum resilience of artificial neural networks. International Symposium on Automated Technology for Verification and Analysis, pp. 251-268. Springer, 2017.
Jeremy M Cohen, Elan Rosenfeld, and J Zico Kolter. Certified adversarial robustness via randomized smoothing. arXiv preprint 1902.00000.022 2019.
Souradeep Dutta, Susmit Jha, Sriram Sankaranarayanan, and Ashish Tiwari. Output range analysis for deep feedforward neural networks. In NASA Formal Methods Symposium, pp. 121-138. Springer, 2018.
Krishnamurthy Dvijotham, Sven Gowal, Robert Stanforth, Relja Arandjelovic, Brendan O' O'Dooghuue, Jonathan Uesato, and Pushmeet Kohli. Training verified learners with learned verifiers. arXiv preprint arXiv: 10265, 2018a.
Krishnamurthy Dvijotham, Robert Stanforth, Sven Gowal, Timothy Mann, and Pushmeet Kohli. A dual approach to scalable verification of deep networks. arXiv preprint 1rXiv:1803.06567, 104, 2018b.
Ruediger Ehlers.
Formal verification of piece-wise wisce linear feed-forward neural networks. In Interna- tional Symposium on Automated Technology for Verification and Analysis, pp. 269-2866660 286. Springer, 2017.
Mattco Fischetti and Jason Jo. Deep neural networks as 0-1 mixed integer linear programs: A feasibility study. arXiv preprint arXiv: 2017.
Timon Gehr, Matthew Mirman, Dana Drachsler-Cohen Petar Tsankov, Swarat Chaudhuri, and Martin Vechev. Ai2: Safety and robustness certification of neural networks with abstract interpretation. In 2018 IEEE Symposium Security and Privacy (SP), pp. 3-18. IEFE, 2018.

---

Under review as a conference paper at ICLR 2020
Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. arXiv preprint arXiv:1412.6572, 2014.
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 preprini arXiv: 1810. 12715, 2018.
Matthias Hein and Maksym Andriushchenko. Formal guarantees on the robustness of a classifier against adversarial manipulation. In Advances in Neural Information Processing Systems, pp. 2266-2276, 2017.
Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the knowledge in neural network. arXiv preprint wrX.vv1503.0253:1 2015.
Uiwon Hwang, Jaewoo Park, Hyemi Jang. Sungroh Yoon, and Nam Cho. Puvae: variational 2019.
autoencoder to purify adversarial examples. arXiv preprint
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.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
Alessio Lomuscio and Lalit Maganti. An approach to reachability analysis for feed-forward relu neural networks. arXiv preprint arXiv:1706.0735/1 2017.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint 2017.
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.
Nicolas Papernot and Patrick McDaniel. Deep k-nearest neighbors: Towards confident, interpretable and robust deep learning. arXiv preprint arXiv: 1803. 04065, 2018.
Aditi Raghunathan, Jacob Steinhardt, and Percy Liang. Certified defenses against adversarial examples. arXiv preprint #=Xiv:1801.09344 2018
Hadi Salman, Greg Yang, Huan Zhang, Cho-Jui Hsieh, and Pengchuan Zhang. A convex relaxation barrier tight robust verification of neural networks. NeurIPS, 2019.
Pouya Samangouei, Maya Kabkab, and Rama Chellappa. Defense-gan: Protecting classifiers against adversarial attacks using generative models. arXiv preprint 1805vv:805.00000 2018.
Karsten Scheibler, Leonore Winterer, Ralf Wimmer, and Bernd Becker. Towards verification of artificial neural networks. In MBMV, pp. 30 40, 2015.
Ali Shafahi, Mahyar Najibi, Amin Ghiasi, Zheng Xu, John Dickerson, Christoph Studer, Larry Davis, Gavin Taylor, and Tom Goldstein. Adversarial training for free! arXiv preprint arXiv: 12843, 2019.
Shawn Shan, Emily Willson, Bolun Wang, Bo Li, Haitao Zheng, and Ben Y. Zhao. Gotta eatch 'em all: Using concealed trapdoors to detect adversarial attacks on neural networks, 2019.
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. 10802-10813, 2018.
Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties neural networks. arXiv preprint arXiv: 2013.
Vincent Tjeng,
Kai Xiao, and Russ Tedrake. Evaluating robustness of neural networks with mixed integer programming. arXiv preprint 1711v:1711.073355 2017.
10

---

Under review as a conference paper at ICLR 2020
Jonathan Uesato, Brendan O' Donoghue, Aaron van den Oord, and Pushmeet Kohli. Adversarial risk and the dangers of evaluating against weak attacks. arXiv preprint arXiv:/802.05666. 2018.
Tsui- Wei Weng, Huan Zhang, Hongge Chen, Zhao Song, Cho-Jui Hsieh, Duane Boning, Inderjit S Dhillon, and Luca Daniel. Towards fast computation of certified robustness for relu networks. ICML, 2018.
Eric Wong and J Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. arXiv preprint urXiv:/71..000 2017.
Eric Wong, Frank Schmidt, Jan Hendrik Metzen, and Zico Kolter. Scaling provable adversarial defenses. In Advances in Neural Information Processing Systems, pp. 8400-8409, 2018.
Kai Y Xiao, Vincent Tjeng, Nur Muhammad Shafiullah, and Aleksander Madry. Training for faster adversarial robustness verification via inducing relu stability. arXiv preprint arXiv:1809.0300 2018.
Dinghuai Zhang, Tianyuan Zhang, Yiping Lu, Zhanxing Zhu, and Bin Dong. You only propagate once: Painless adversarial training using maximal principle. arXiv preprint arXiv: 1905.00877, 2019a.
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, pp. 4939-4948, 2018.
Huan Zhang, Hongge Chen, Chaowei Xiao, Bo Li, Duane Boning, and Cho-Jui Hsieh. Towards stable and efficient training of verifiably robust neural networks. arXiv preprint arXiv:1906.063/1 2019b.

---

Under review as a conference paper at ICLR 2020
A A TOY EXAMPLE FOR TIGHT RELAXATION
S1
(2(2,)= =
0
X0
X61
X6 6
50
-02
-0.6
-3.08
-0.75
-253
-0.25
0.00
0.25
350
0.75
1.00
Figure 2: Illustration of the data distribution and the decision boundary of the network. In this case,
b = 0.3, 6 = 0.2, zo = 0.4.2
We give illustrative example where the optimal solution to the relaxed problem is feasible solution to the original non-convex problem for certain input samples even when unstable neurons
exist. It is binary classification problem for samples xo [201. z02]" IR2 We assume xo is uniformly distributed in S, U U1, where S, {oo S |0 - b, || S 1}. S { 4o2 2 [ro1 + b, || S 1}. and 0 < b < The ground-truth label for 2o E Su and 2g E S are O, respectively. The maximal-mann mangin classifier for such data distribution is (#1g]|ara)); where 2 is the input to the classifier. The data distribution and the associated maximal-margin classifier is shown in Figure
This maaiimal-margin classifier can be represented by ReL.U network with single hidden layer as (22())))0)) where h2 (21) W (1 and
-1 0
W =
W2 [-1 -1 1 -1].
(5)
-1
Claim (Convex relaxation can be tight when unstable neurons exist). The solution to the relaxed problem is is feasible for the original non-convex problem of the aforementioned ReLU network
hz(10 + 0o) = (2 + 5g)) for any No E S1 under any perturbation 8g E [ S <.
<< b).
Proof. Both the network and S₁ are symmetric Øo1. therefore it sufficient to prove the result for Fo1 2 O.
(1) If Fo1 2 e, since 2o1 E St, Fo2 2 + e. The neurons in 21 Wi + 60) are either non-negative non-positive for any 80 [ c,0 b) and the convex relaxation is tight.
(2) If 201 c, for any input sample zo {x|x [ b b+ < c) C S₁, the optimal perturbation 5% E (ō]1|²)| < e, < < < < b) can be inferred from Figure 2 as [e, -e]". The corresponding ReLU activations and the optimal solution are
2/ = [a + 0,0, cf J = c- 2e.
(6)
Meanwhile, for the relaxed problem, the lower and upper bounds of the hidden neurons ø1 = W1
L 6, c -- of -, (a + e,, ae..ce -c -c
12

---

Under review as a conference paper at ICLR 2020
Therefore, the first hidden neurons are unstable neurons, and the convex relaxation using will relax the ReLU operation 22 = ( into 22 = Di + ò1, where D1 is a diagonal matrix, and ón are slack variables bounded by 0 S 81 s 8n. The diagonal entries of Dj and the upper bounds ōn are defined by Eq.
13 as
a E a +
(-a + c) + +) (aa + c) + +
"
diag( D1)
1.0
81
0,
2c
2c
2c
2c
i.e. 613 and 814 are always The relaxed linear network, as defined by the constraints in Eq. with our specific relaxation, is now determined as 22 = h2(21) = W2 + 50) + 61). It can be written into the same form as Eq. [4 as
2, = c212(21) = c. W2 W2 (r 00) + a 22 = es 22.1 12.1110 + W201,
where
a 1]. 4 12,1 =1-
Therefore, to minimize the term W2.11100 we should choose 80 [e, -cl", which is equal to 68 To minimize e, W201, we should let 0j (-a+e)aae)) (- (aat)(++e) 0.0 which gives rise to the optimal solution of the relaxed problem as
= D2Wi 6g) + + t,, 0, 2 c- a a-26. 2e.
the same as the optimal solution of the original non-convex problem given in Eq. 6 This shows both of the regularizers, in this case instantiated
d(z, 8 W1, W2) ca - r2), &. W1, W2) = (1211 -ii | 10/12 xī2));
are able to reach O for certain networks and samples when non-stable neurons exist.
It might seem that adding d(x, og. W, p/o (2,,))) 6() PC regularizer into the loss function will undesirably minimize the margin p6 (z. 66) for the ReLU network. Theoretically, however, is not the case, since min P'o P is different optimization problem from neither min Po nor max pč. In fact, the non-negative d(x, 0ū W. b) could be minimized to with both p/o and pč taking large values. In the illustrative example, is easy to see that for any xo E {xl x = [a, cl" <
< b+a S c).
d(x, 8, W, b) (1 x²) = O, but Po = Pč = c a - > 0 when e < 5
Moreover, since we are maximizing Pt via the robust cross entropy loss while minimizing the non-negative difference p'o pē- the overall objective tends converge state where both P' and pe are large.
B PROOF OF PROPOSITION ]
Proposition 1. Assume {2/, 2' is obtained by the ReLU network hy with input 2/,, and {5,) L-1 the optimal solution of Fast-Lin or CROWN. If 2 x + +8g and r'y S( for all
1. 1.... 1.j E I, then {24, 2M is an optimal solution of Fast-Lin and CROWN. Here
[ (xn Fzp}
8
S(1))
{10)
if if
0.
Proof. We only need to prove (z/, L is an optimal solution of both Fast-Lin and CROWN. After that, {z H both a lower bound and feasible solution of o and therefore is the optimal solution of O
Here we define क = W123 + by for i = 1, 1...., L, 2/+1 = D( 23 o7 for = 1,..., L - 1, and 2 = x + 5/- By definition, { [ is an optimal solution of Fast-Lin or CROWN. Also, since
"The cross entropy loss on top of the lower bounds of margins all non-ground-truth classes, see Eq.
13

---

Under review as a conference paper at ICLR 2020
2 x1. we have 2 = Wi - b2 2 Next, we will prove if the assumption holds, we will have
2/ 22 for both Fast-Lin and CROWN.
For j E Itt, by definition of Fast-Lin and CROWN, Diy = 1 and æi 2 Στ > 0. 0. 20 -ii 2 0.
2 Di ziş x m 0) z2z
For j E IT again, by definition, D(5 0, and iiş S Fij < 0, so وii = =ii < 0, 25/
DIf) vij =0 = m 0) z221
For j E IT:
If oi = 0 and o1 = 0 as assumed in the conditions, since =ं = 21, we know
i = Wi + b1 = W1,zi + tb = x = 0,
where W1y is the j-th row of W1. No matter what value DIG) is, 22.3 = -D1 æi₃ = 0. 2/21 max 0) = 0, the equality still holds.
If 8 = 21, for both Fast-Lin and CROWN, 25j = - Biy #15 _i, (z - 1. Further, if
21;
o²1y E {215 }1ا as assumed: if ii = x115 = Eig. then 21, < 0, so 2/2 = max (z1, 0) =
0, and 221 = Fyy-aa (51 -1,) = =zzj if if = 2iy 3ig. then ,.J > 0, 2/2 2113
R.
and 233 m. E,,
(51s [1²) = L1.- = zéz
Now we have proved 2/2 = 2ラ for both Fast-Lin and CROWN if the assumption is satisfied. Starting from this layer, using the same argument as above, we can prove 2/3 = 23.....²_-1 = for both Lant-Lin and CROWN. As result, z'2 = z and c, c/'², of at P8. where C can be both Fast-lin and CROWN. Therefore, {2/, x/H4 is an optimal solution of C.
C EXPERIMENTAL DETAILS
Experiments for Table The small convnet has two convolutional layers of 16, 32 output channels each and two FC layers with 100 hidden neurons. The large net has four Conv layers with 32, 32, 64 and 64 output channels each, plus three FC layers of 512 neurons. For all experiments, we are using Adam (Kingma& & Ba 2014) with learning rate of 1e 3. Like (Wong al., 2018), we train the models for 80 epochs, where in the first 20 epochs the learning rate is fixed but the e increases from 0.01/0.001 to its maximum value for MNIST/CIFARIO and in the following epochs, we reduce learning rate by half every 10 epochs. We do not use weight decay. We also adopt a warm-up schedule in all experiments, where X, y increases form 0 to the preset values in the first 20 epochs, due the noisy estimation from the random projections. Our implementation is based on the code released by (Wong et al. 2018), so when = 7 O, we obtain the same results as as (Wong et al. 2018
Experiments for Other Tables We use the same hyper- ssperpparametes as (Zhang al. 2019b), except for "Ir decay_step" and "epochs", which are set to 20 and 140 for lower variance.
D ABLATION STUDIES OF THE TWO REGULARIZERS
In this section, we give the detailed results with either À or 7 set to 0, i.e., we use only one regularizer in each experiment, in order to compare the effectiveness of the two regularizers. All the results are with the small model on CIFARIO 10 with e = 2/255. The best results are achieved with r(æ, 8j. W, b). We reasoned in 4.2 that d(z, 87. W, b) may not perform well when random projection is adopted. As shown in the supplementary, the best robust error achieved under the same setting when fixing y 0 is higher than when fixing À= O, which means r(z, 88, W, b) is more resistant to the noise introduced by random projection. Still, random projections offer a huge efficiency boost when they used. How to improve the bounds while maintaining efficiency is important future work.
14

---

Under review as a conference paper at ICLR 2020
7
Robust Err (%)
Std. Err (%)
?
Robust Err (%)
Std. Err (%)
le-5
52.90
37.61
0
le-3
52.56
37.45
5e-5
53.09
37.77
5e-3
53.38
38.19
le-4
52.48
37.37
0
le-2
52.60
37.73
5e-4
52.85
37.13
0
2.5e-2
52.70
37.78
le-3
52.61
37.96
5e-2
53.13
38.36
2.5e-3
53.10
38.24
0
le-1
52.72
38.22
Se-3
52.76
38.15
2.5e-1
52.90
38.04
le-2
53.14
38.58
0
5e-1
52.39
37.48
5e-2
52.82
39.89
52.27
38.07
le-1
53.94
41.59
0
2
53.10
38.64
Se-1
56.39
48.06
59.23
52.51
Table 3: Ablation results on CIFARIO with the small model, where 2/255.
E DIFFICULTIES IN ADAPTING IBP FOR l ADVERSARY
The Inverval Bound Propagation (IBP) method discussed here is defined in the same way as (Gowal al. 2018), where the bound of the margins are computed layer-wise from the input layer to the final layer, and the bound of each neuron is considered independently for both bounding that neuron and using its inverval to bound other neurons.
It is natural to apply IBP against for adversaries, since each neurons are allowed to change indepen- dently its interval, which is similar to the &o ball. One way generalize IBP other l, norms to modify the bound propagation in the first layer, such that any of its output neuron (i) is bounded by an interval centered at T1s = WI. _ + 61.4 with a radius of ep W..illp= where 21s the clean image r response, and W1, is the first layer's linear transform corresponding the neuron, and 11-112- is the dual norm of pp with 1. + 5- 1. We refer to this approach IBP((,, Ep). Here by the example y.
of & norm, show such adaptation may not be able obtain robust convolutional neural network compared with established results, such as reaching 61 % certified accuracy on CIFAR10 with 62 0.25 (Cohen et al. 2019).
Specifically, for adversaries within the 22- ball B2,02 (z), IBP(L2, 62) computes the upper and lower bounds
1 = Wi, + 62/ W + bi,i, zi: W1,x e2 c2IlWi,ille + bi,i- -ball Bo., (I), IBP(f Coo) computes the upper
(8)
By comparison, for some adversary within the -bll and lower bounds as
:h W1, coo W1,ll + b1. Φी = W1,12 - c W1. + b1.s.
660
Since the two approaches are identical in the following layers, to analyze the best-case results of IBP((2, 62) based on established results IBP( c,o), it suffices to compare the results of IBP( Ege) with 6oo set to some value such that the range žς zी of Eq. 9 majorized by the range J of of Eq. & In this way, we are assuming weaker adversary for IBP(E 66o) than the original certified accuracy is upper bound of IBP(22, 62). Therefore, it suffices let
(B, (2),
6x Willl S &2llW
=i= 1,2, ..., Bl.
(10)
For any Wi, Rd, we have ||W can set
v vallW, To make Eq. 10 hold for any Wi,5 E Rd.
6,c
Vd C2-
In general, d is equal to the data dimension, such as 3072 for the CIFARIC dataset. However, for convolutional neural networks, the first layer is usually convolutional layers and W1, 3072- dimensional sparse vector with at most & x & x 3 non-zero entries at fixed positions for convolution kernels with size is and input images with channels. In (Zhang et al., 2019b Gowal al. 2018 Wong et al. 2018). A 3 for their major results. In this case,
6oo 2
(II)
3/3
15

---

Under review as a conference paper at ICLR 2020
Under such assumptions, for E2 0.25, the certified accuracy of IBP( 0.25) on CIFARIO should be upper bounded by IB, 1.04811), unless changing the first layer bounds into & norm based bounds significantly harms the performance _ The best available results of certified accuracies are 33.06% for (B, 0.03137) and 23.20% for IB 0.06275) (Zhang et al. 2019b). Comparing with the established results from (Cohen al. 2019) (61 %), we conclude the certified accuracy of IB, 0.25) is at least 27.93% to 37.80% lower than the best available results, since we are assuming a weaker adversary.
IBP( e2) is also not as good as the results with convex relaxation from (Wong et al. 2018). where the best single-moder (with projection as approximation) certified accuracy with 62 36/255 is 51.09%. For IBP. this adversary is no weaker than Eoo = 6.9282 /255. The best available results for (B, 2/255) and (f 8/255) are 50.02% (Gowal et al. 2018 and 33.06% (Zhang et al. 2019b) respectively, which indicates the certified accuracy of IBP((2, 36/255) is at least 1.07% to 18.03% worse (much loser to 18.03% than the approximated version of convex relaxation under the same l2 adversary.
F SOLUTIONS TO THE RELAXED PROBLEMS
In this section, we give more details about the optimal solutions of Fast-Lin (Weng et al. 2018) and CROWN (Zhang al. 2018), to make this paper self-contained. Recall that for layer-wise convex relaxations, each neuron in the activation layer are independent. {ay. Ly: Gajy bij) are chosen to bound the activations assuming the lower bound Lnj and upper bound Tay of the preactivation zij is
known. For j E I. Taj + bi S max(0, Fai)) S T. B.y
(xij - Eiz) S BeySis + bi:: for j E Itt,
Bi J.g = a.j = bij = 1; for j I4 By = T.j buj big = 0.
Optimal Solutions of Fast-Linn In Fast-Lin (Weng et al. 2018), for j E I, G.j = Dij Fzj Eny"
Z.y shown as the blue region in the right of Figure To compute the lower by 0, b.j = EE,"
and upper bound 2i and Σ,, for Tij, we just need to replace the objective of Eq. with c[J2,, where Gj is one-hot vector with the same number of entries as 2y and the j-th entry being for Tay and -1 for Tij (an extra negation is applied to the minimum to get Tiy).
Such constraints allow each intermediate ReLU activation reach their upper lower bounds independently. As result, each intermediate unstable neuron can be seen as an adversary adding perturbation diy in the range [0,
m;j T:j Z4j - + dej. a linear transform, represented 2ij Fuy -;
Such point of view gives rise to a more interpretable explanation for Fast-Lin. If we construct network from the relaxed constraints, then the problem becomes how to choose the perturbations for both the input and intermediate unstable neurons minimize cf æ of multi-layer linear network. Such a linear network under the perturbations is defined as
1 = D.F; + 6;, x; = W: + b;, for = 1, L, 21 = x + 50
(12)
where D; is a diagonal matrix and 6, is vector. The input perturbation satisfies llōollo S The j-th diagonal entry Dij and the j-th entry dig for > Os defined
0,
if I if It 5zg E SS,, E
= -
Tr Eag F. 25-2.11
if E Iz
Di =
1,
-1(0
(13)
Fu
ifj
(1))
otherwise.
With such an observation, we can further unfold the objective in Eq. 12 into a more interpretable form as
4-1 1 Wr
oJ
Σ
II D&WLd,
(14)
T=0
k=++1
where the first term of RHS is a forward pass of the clean image x through a linear network interleaving between linear layer Wi b, and scaling layer D,z, and the second term
Which is unlikely, since 6 is now weaker adversary than 22 and the difference in gradient expression only appears in the first layer.
16

---

Under review as a conference paper at ICLR 2020
is the sum of the i-th perturbation passing through all the weight matrices W; of the linear operation layers and scaling layers D; after it.
Therefore, under such relaxation, only the second term affected by the variables {6, [-1 for opti- mizing Eq. C Denote the linear network up to the i-th layer as (i()), and Way = W; I W
Fe into the following We can transform Eq. with aij = Day 213-211 bij = 0. bis 21--11
constrained optimization problem
minimize of (1(x)) 6o.....6-11
of WLa+10, subject 11ōoll S &, Sa for 1,... L 1. (15)
Notice of WL is just a row vector. For > 0,j E I, to minimize co WW 18gj, we let dig be its Boy if (c] WL++1)s minimum value if (c. WLa+11j 2 or its maximum value dij m
where (c. W1a+1); is the j-th entry of e, WL For dg. when the infinity norm is used, we set 5.j = - if (c, Wis+ 1)s- 2 0, and otherwise dij t. For other norms, it also easy to see that
Wr.10 = -c max -c, Wr.1 = c|lc, Wralle.. S
min
(16)
116011
where |-I|- is the dual norm of the norm. In this way, the optimal value pe Pe of the relaxed problem (Eq. [5) can be found efficiently without any gradient step. The optimal value can be achieved by just treating the input perturbations and intermediate relaxed ReLU activations as adversaries against a linear network after them. The resulting expression for the lower-bound is
L-1
TijIig
po 2 Pè c. gz (z) <||c, WL.1 I1+
ΣΣ jEL
min((c) Wbs+1)5, (17)
Tij
Eij
Though starting from different points of view, can be easily proved that the objective derived from a dual view in (Wong et al. 2018 8) is the same as Fast-Lin.
Optimal Solution of CROWN The only difference between CROWN and Fast-Lin the choice of d.j for j E I, For ReLU activations, CROWN chooses Ø;j 1 if ž:y -Pay. O; 0 otherwise. This makes the relaxation tighter than Fast-Lin, but also introduces extra complexity due to the varying D,. In Fast-Lin, D; is constant once the upper and lower bounds 3; and I, are given. For CROWN, since 0 < d.j- < 1, Fij + 2.j- D; now changes with the optimality condition of 6, which depends on the layer and the index k of the neuron/logit of interest. Specifically, for too adversaries, the optimality condition of 6, is determined by ei Wha so now we have to apply
extra index to the slope as (,,)))) as well as the equivalent linear operator as (!(.)) As a result, the optimal solution is now
T-11
(z) - ellewwa (1.
ΣΣ
TijIs Tij
min ((Cn) (W
(((.)) ts+ ti+1) 0).
(18)
Fij
i=
JEL
This drastically increase the number of computations, especially when computing the intermediate bounds 2, and Ti, where we can no longer just compute single Wia1 to get the bound, but have to compute number-of-neuron copies of it for the different values of D(L. (1,8) in the intermediate layers.
Practical Implementations of the Bounds In practice, the final output bound (also the intermedi- ((.)) bounds) computed in backward pass, since we need to determine the value (cj, Mbs+1) 1); to choose the optimal 6. which is the multiplication of all linear operators after layer i. Computing
T (v..))) in a backward pass avoids repeated computation. It proceeds as
Cue 1s441
Cike (ilkk) = oT w((.)) 1a++1
D (l.b))
(19)
G DETAILED RESULTS ON THE FAMILY OF SMALL MODELS
17

---

Under review as a conference paper at ICLR 2020
erner
Copied
verifiie (5)
sd. (9)
15.4 08
10.6 1.6--:00 .06
3.20
16.1 -3
3,70 1.0:t.1
11.3 .1
3.85
11.7 2
9.96 .09
4,20
12.2 122-+.0
2.85
9.50 22
11.2 .08
9.21 3
Baseline
verified
sd.. (3)
14.70 +
5.85 D1
10.60
3,25 .5
1.70 -4
2.81
6.30 1
2,89 005
12.06
4.11 3
8,82
2.55 1.1
5.30 .4
2.56 1.1
With
verified (9)
(98)
14.54 +
6.0
10.46 =
13.37
3106
9.91
14.43 + 3
9.48
11.00
8.80 + 3
10.18
9.49 4
Table 4: Mean and standard deviation of the family of 10small models on MNIST CROWN-IBP with epoch=140 and Ir_decay Like in CROWN-IBP, we run each model times to compute the mean and standard deviation. "Copied" are results from (Zhang et al. 2019h).
0.3. Baseline
18


Reviews:
[{"review_id": "HyxG4FXV5B", "reviewer": "AnonReviewer4", "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": "Summary:\nThe aim of the paper is to improve verified training. One of the problem with verified training is the looseness of the bounds employed so the authors suggest incorporating a measure of that looseness into the training loss. It is based on a reformulation of the relaxation of Weng et al.\n\n\nComments:\nPage 2: \"it can certify a broader class of adversaries that IBP cannot certify, like the `2 adversaries.\". You can definitely use IBP to very properties against L2-adversaries. It is simply a matter of changing the way the bound is propagated through the first layer.\nPage 3: It's a bit pedantic, but the convex relation of Ehlers (middle of figure 1) is not the optimal convex relaxation. It is optimal only if you assume that all ReLU non linearities are relaxed independently. See the work by Anderson et al. for some examples \nPage 5, section 4: \"We investigate the gap between the optimal convex relaxationin Eq. O\" There is a bit of confusion in this section. Eq O is not the optimal convex relaxation, it's the hard non-convex problem.\nSection 4.1 bothers me. Equation C is the relaxed version of equation O, so they are only going to be equal if there is essentially no relaxation going on. Saying that it's possible to check whether the equivalence exists is a bit weird. The only case where this can happen is if all the terms in the sum over I_i are zero, which is essentially going to mean that no ReLU is ambiguous. (or if the c W are all positives, but that would be problematic during the optimization of the intermediate bounds given that c would make them both signs then)\nPage 5, section 4.2: The authors suggest minimizing d, the gap between the value of the bound obtained, and the value of forwarding the solution of the relaxation through the actual network. Essentially, this would amount to maximizing the lower bound (which all verified training already does), at the same time as minimizing the value of the margin (p_O) on a point of the neighborhood for which we want robustness (x + delta_0). Minimizing the value of the margin is the opposite of what we would want to do, so I'm not surprised by the observation of the author that this doesn't work well.\nThe conclusion of the section that d can not be optimized to 0 also seems quite obvious if you think about what the problem is.\n\nSection 4.3:\n\"the optimal solution of C can only be on the boundary of the feasible set.\" -> There is a subtlety here that I think the authors don't address. The three points they identify are the only feasible optimal solutions for solving a linear program over the feasible domain given by the relaxation of one ReLU but, when solving over the whole of C, the solution needs to be on the boundary of the feasible domain of C, which is larger than those three points.\n\nThe whole section is quite convoluted and makes very strong assumption. For Proposition 1, the condition x \\in S(\\delta) means that all the intermediate bound in the network must have been tight (so that the actual forwarding of an x can match the upper or lower bound used in the relaxation), and that the optimal solution of the relaxation requires all intermediate points to be at either at their maximum or their minimum. The only case I can visualise for this is essentially once again the case where there are no ambiguous ReLU and the full thing is linear.\n\nRegarding the experiments section, it would be benefical to include in table 1 the results of Gowal et al. (On the Effectiveness of Interval Bound propagation for Training Verifiably Robust Models) for better context. The paper is already cited so it should have been possible to include those numbers, which are often better than the ones reported here.\nThe comparison is included in table 2, when the baseline is beaten, but this is with using the training method of CROWN-IBP and it seems like most of the improvements is due to CROWN-IBP.\n\nTypos/minor details:\nPage 2: \" In addition, a bound based on semi-definite programming (SDP) relaxation was developed and minimized as the objective Raghunathan et al. (2018). (Wong & Kolter, 2017) presents an upper bound\" -> citation format\nPage 8: \"CORWN-IBP \"\n\nOpinion:\nI think that the analysis section is pretty confusing and needs to be re-thought. It provides a lot of complex discussion of when the relaxation will be exact, without really identifying that it will be when you have very few ambiguous ReLU. I think that there might be a few parallels to identify between the regularizer proposed and the ReLU stability one of Xiao et al. (ICLR2019) from that aspect. The experimental results are not entirely convicing due to the lack of certain baselines.", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "HyeOL_lGcB", "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": "Summary:\nThe paper proposes two new regularizers for adversarial robustness inspired by literature on verification of ReLU neural networks for resilience to epsilon perturbations using convex relaxations. The paper shows empirically that the proposed method leads to better robustness than previous works.\n\nStrengths:\n+ The paper seems to have an interesting perspective (with the proposed looser relaxation) of the convex relaxation of an adversary adding noise at every layer in the network\n\nWeaknesses:\n\n*Sec. 4.1: Eqn. (O) does not have a convex relaxation, it is the exact problem which is intractable. Why are we comparing the optimal values of p*(O) and p*(C)? The paper from Salman et.al. already shows that there is a convex relaxation barrier, which essentially corresponds to this difference. In general, in Sec. 4, it is often unclear whether when we talk about p(O) if we are referring to the unrelaxed original problem or the tightest convex relaxation. For example, at the start of Sec. 4.1, it seems like we are talking about the convex relaxation and then in Sec. 4.3 it seems like we are talking about the unrelaxed problem.\n\n*It is not clear how/ why the proposed method of relaxing (which by the way seems identical to Fast-Lin (Weng et.al.) is better than the optimal convex relaxation. Would this not lead to looser bounds? Is that the thing we are looking to investigate? Making that more clear would be useful. Perhaps it would be good to argue the proposed regularizer in this work cannot be constructed with the optimal convex relaxation. Is that true? A discussion on this would be helpful.\n\n* The crux of the contribution seems to rest on the premise that identifying the optimal perturbation in the input space with the relaxed model, and then computing the activations with respect to that and forcing the forward pass to saturate near the margins of the relu polytope (relaxation) is a good idea. In general, it seems very unclear why this should work based on the evidence presented in the paper. Specifically with the relaxation, it might not even be guaranteed (as far as I understand) that the value of \\delta_0^* that is found from problem C is even going to lie inside the L\\inf norm ball around the point x, for example. Thus it is not clear to me if this is an approach for verification or a regularizer based on verification.\n\n* Ultimately, the value of the approach in this context (as per my understanding) comes from the experiments and the results which show that there is increased robustness. It would be great to clarify a couple of details in the experiments:\n1. Is the method of Wong et.al. using the looser convex relaxation (used here) or the tight convex relaxation when reporting the numbers in Table. 1? \n2. If the optimal convex relaxation can be used to construct the same regularizer as the one proposed here, it would be good to evaluate how well that does.\n\nOverall, I am not an expert in the area but a lot of details from the writing (such as point 1 under weakness) and the theoretical justification of the regularizer are unclear to me. Thus given these (perceived) weaknesses I would lean towards weak rejection. Clarifications on these points would help me revise my score.", "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 did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "Hye3HcXoFB", "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": "Strengths:\nThis work proposed two regularizers that can be used to train neural networks that yield convex relaxations with tighter bounds.\nThe experiments display that the proposed regularizations result in tighter certification bounds than non-regularized baselines.\nThe problem is interesting, and this work seems to be useful for many NLP pair-wise works.\nweaknesses:\nSome presentation issues.\nThe dataset, MNIST, is not good enough for a serious research. \nMore datasets need to be added to the experiments in this paper.\n\n\nComments:\nThis paper proposes two regularizers to train neural networks that yield convex relaxations with tighter bounds. \n\nOverall, the paper solves an interesting problem. Though I did not check complete technical details, the extensive evaluation results seem promising. \n\n1. There are some presentation issues that can be addressed. For example, on page 8, the sentence of “the family of 10small” misses a blank space.\n\n2. In the experiments, the dataset is not a good one for evaluating the performance of the proposed idea.\n\nIn conclusion,  at this stage, my opinion on this paper is Weak Accept. ", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors develop regularization schemes that aim to promote tightness of convex relaxations used to provides certificates of robustness to adversarial examples in neural networks.

While the paper make some interesting contributions, the reviewers had several concerns on the paper:
1) The aim of the authors' work and the distinction with closely related prior work is not clear from the presentation. In particular, the relationship to the ReLU stability regularizer (Xiao et al ICLR 2019) and the FastLin/CROWN-IBP work (https://arxiv.org/abs/1906.06316) is not very well presented in the theoretical sections or the experiments.

2) The theoretical results (proposition 1) requires very strong conditions to apply, which are unlikely to be satisfied for real networks. This calls into question the effectiveness of the framework developed by the authors.

While the paper has some interesting ideas, it seems unfit for publication in its present form. 
Decision: Reject