Efficient Bi-Directional Verification of ReLU Networks via Quadratic Programming
Authors: Aleksei Kuvshinov
Stephan Guennemann
Venue:  (2020)

Abstract: Neural networks are known to be sensitive to adversarial perturbations. To investigate this undesired behavior we consider the problem of computing the distance to the decision boundary (DtDB) from a given sample for a deep NN classifier. In this work we present an iterative procedure where in each step we solve a convex quadratic programming (QP) task. Solving the single initial QP already results in a lower bound on the DtDB and can be used as a robustness certificate of the classifier around a given sample. In contrast to currently known approaches our method also provides upper bounds used as a measure of quality for the certificate. We show that our approach provides better or competitive results in comparison with a wide range of existing techniques.

Under review as a conference paper at ICLR 2020
EFFICIENT BI-DIRECTIONAL VERIFICATION OF RELU NETWORKS VIA QUADRATIC PROGRAMMING
Anonymous authors Paper under double-blind review
ABSTRACT
Neural networks are known to he sensitive to adversarial perturbations. To investi- gate this undesired behavior we consider the problem of computing the distance the decision boundary (DiDB) from a given sample for deep neural net classifier. In this work we present an iterative procedure where in each step we solve convex quadratic programming (QP) task. Solving the single initial QP already results a lower bound on the DiDB and can used as a robustness certificate of the classifier around given sample. In contrast to currently known approaches our method also provides upper bounds used as a measure of quality for the certificate. We show that our approach provides better competitive results in comparison with a wide range of existing techniques.
INTRODUTION
The high predictive power of neural network classifiers makes them the method of choice to tackle challenging classification problems in many areas. However, questions regarding the robustness of their performance under slight input perturbations still remain open, severely limiting the applicability of deep neural net classifiers to sensitive tasks that require certification of the obtained results.
In recent years this issue gained a lot of attention, resulting in a large variety of methods tackling tasks ranging from adversarial attacks and defenses against these robustness verification and robust training. In this work we focus on robustness verification of deep classifiers. That is, computing the distance from a given anchor point x0 in the input space to closest adversarial, i.e. a point that is assigned a different class label by the network. This problem plays a fundamental role in understanding the behavior of deep classifiers and essentially provides the only reliable way to assess classifier robustness. Unfortunately, its complexity class does not allow a polynomial time algorithm. For deep classifiers with ReLU activation the verification problem can equivalently be reformulated as a mixed integer programming (MIP) task and was shown to be NP-complete by Katz et al.) (2017). Even worse, |Weng et al. (2018) showed that an approximation of the minimum adversarial perturbation of a certain (high) quality cannot be found within polynomial time.
Related work There exist three streams of related work on robustness verification of deep ReLU classifiers. This categorization is based on whether they are solving the verification problem exactly or verifying a bound on the distance to the decision boundary (DtDB).
The first group of methods are exact verification approaches. As mentioned above, the verification task can be modeled using MIP techniques. Katz et al. (2017) present modification of the simplex algorithm that can be used to solve the verification task exactly for smaller ReLU networks based on satisfiable modulo theory (SMT). Other approaches (see Ehlers (2017)) rely on SMT solvers when solving the described task. Bunel al. (2018) provide an overview and comparison of those. Other exact methods (Dutta et al. (2018); Lomuscio and Maganti (2017) Tieng et al. (2017) deploy MIP solvers together with presolving to find a tight formulation of the MIP problem or (Jordan et al.) (2018) use algorithm to find the largest ball around the anchor point that touches the decision boundary.
The second popular class of methods for verifying classifier robustness deals with verification of an e-neighborhood: given an anchor point xd and an e >> 0, the task is to verify whether an adversarial point exists within the neighborhood of d which is defined with respect a certain norm in the

---

Under review as a conference paper at ICLR 2020
imput space. All existing methods relax the initial problem and require bounds activation imputs in
each layer. These bounds should be as tight as possible to ensure good final results. [Rahhnathaa
et al. (2018a Dvijotham et al. (2018 2019) consider semidefinite (SDP) and linear (LP) problems
as relaxations of the e-verification problem. Wong and Kolter (2018) replace ReI.U constraints by
linear constraints and consider the dual formulation of the obtained L.P relaxation. |Weng al. (20T8)
present an approach that also uses linear functions (later extended to quadratic functions by Zhang
al. 2018) to deal with nonlinear activation functions and propagate the layer-wise output bounds until the final layer. Finally Hein and Andriushchenko (2017); T'suzuu et al. (2018) use the Lipschitz constant of the transformations within classifier's 's architecture.
Our approach belongs to the third group of approaches dealing with constructing lower bounds on DIDB without restricting admissible adversarial points to a given neighborhood. The e-verification task is closely related to the problem of constructing lower bounds on DIDB: each e-neighborhood that can be certified as adversarial-fre perturbation magnitude. It is also common strategy for the methods from the previous group to use a binary search or a Newton method on top of their algorithm to find the largest such that the e-neighborhood around z can still be verified robust. Croce et al. (2019) leverage the piecewise affine nature of the outputs of a ReLU classifier and compute lower bounds on DtDB by assuming that the classifier behaves globally the same way it does in the linear region around the given anchor point.
immediately provides lower bound on the minimal adversarial
Adversarial attacks Constructing misclassified examples that are close to the anchor point can be considered as complementary research direction to robustness verification since each adversarial example by definition provides an upper bound on the DIDB, Many methods were proposed to construct such points (Szegedy et al. (2014); Goodfellow et al. (2015), Kurakin et al. (2016) Papernot
ct al. (016);; Madry et al. (2017) 7 Carlini and Wagner (2017)
Robust training The question of how to actually train a robust classifier is closely related to robustness verification since the latter might allow us to construct some type of robust loss based on the insights from the verification procedure (see Hein and Andriushchenko (2017): Madry et al.
(2017): Wong and Kolter (2018); 8); |Raghunathan et al. (2015 Sab; Tsuuzuu et al. (2018): Wang et al.
(2018) Croce et al. (2019) We leave this direction for future work.
Contributions
We propose a novel relaxation of the DIDB problem in form of a QP task allowing efficient computation of high quality lower bounds on the DIDB in 12-norm with extension to -norm. For networks with up to two hidden layers we reach state-of-the-ee performance with an improvement of over 50% when compared to the bounds obtained from methods based on LP relaxations (CROWN by IZhang et al.] (2018) and ConvAdy by WWng and Kolter (2018)). Furthermore, our method performs much faster than methods based on SDP relaxations (Raghunathan et al., (018b), while providing smaller lower bounds. This is a fundamental property due to the difference in computational complexity between SDP and QP tasks.
2. Unlike e-verification techniques, we provide a lower bound on DIDB without an initial guess and without computing bounds for the neuron activation values in each layer. Such bounds have to be tight enough to verify non-trivial neighborhoods and play an important role in other relaxation techniques such as the SDP based approaches by |Raghunathan et al. (0188): Dvijotham et al. (2019).
3. In addition to computing the lower bounds after solving single QP, our approach allows to construct adversarial examples by repeatedly choosing a new anchor on the boundary of the verified region and solving its associated QP. One of the main limitations of competing inexact approaches is the fact that the situation around the given anchor point outside of the certified radius remains unclear. Since these approaches rely on relaxations of the initial problem, failed certification does not indicate the presence of an adversarial example. Instead, when using these methods, one must rely externally constructed adversarial examples to obtain an upper bound. We present a di-directional robustness verification technique that uses the verification mechanism itself to construct upper bounds and assess the quality of the lower bounds.
2

---

Under review as a conference paper at ICLR 2020
2 NOTATION AND IDEA
We consider neural network consisting of T. linear transformations representing dense, convolutional, skip or average pooling layers and I, ReLU activations (no activation after the last hidden layer). The number of neurons in layer / is denoted as nu for ( 0.... L, meaning that the data has no features and n, classes. Furthermore, we present our analysis for the 22-norm as perturbation magnitude measure since only few available methods are applicable to this setting. To make our method comparable with Raghunathan et al. (2018b) a generalization to loc -peruurbations is addressed in Appendix
Given sample x E R weight matrices W E R= and bias vectors E RR!,, we define the output of the i-th neuron in the 1-th layer after the ReLU activation as
/ = [ + b/] and bf
f((x²) at
where [x] is the positive part of z and f(z0) = denotes the output of the complete forward pass through the network. We start with the observation that the ReLU activation function acts as one of two linear functions depending on its input's s sign. That allows us reformulate it (see Section 3.1 and obtain an optimization problem with so called linear complementarity constraints (also used by Raghunathan et al. (2018b); Dvijotham et al. (2019) for e-verification). Note that for each pair of scalars a and the following holds.
x²
b b= [a]+
620, b- a 2222200 0, b(b - a) = 0
(2)
3 OPTIMIZATION PROBLEM
3.1 FORMULATION OF DTDB
For given sample z0 pre-trained neural net f. predicted label and target label y aim to find the closest point to 30 Rho that has a larger or equal probability of being classified as y compared to the initial label. This can be done by solving the following optimization problem.
min
| - =011, s.t. (eg - f(x))((x)) SO
(DiDB)
2 PRRM
where e; is the i-th unit vector in R and ||.||| denotes the Euclidean norm of æ.. Note that explore the boundary between classes y and ÿ around &o_ To compute the distance from j to the (full)
decision boundary, one needs compute the solution for all target labels 1,...; ny except ÿ.
We can "unfold" the above optimization problem using variables _ ,..., x..
|I where x denotes a container with all
min ||00 - 2012, s.t. (eg eyy Fu S 0, =²= -W4gb-1 b² =ER*
x' = ReLU - + b²) for 1 = I,...,L-- L L-1
We apply 2 to reformulate the problem and eliminate L such that from now on x. contains only and n Ro + + n1
the remaining variables z....., .....
min | 2012, s.t. (eg e,)) T ( 1- + bb) 50 #Ekn
(DtDB)
(x') (a' - (w 1 + +b') = 0 for = 1,.... L -
(3)
/ - (W + 6¹) > 0, x > 0 for == I,...,
(4)
3

---

Under review as a conference paper at ICLR 2020
3.2 QP RELAXATION
Next we consider Lagrangian relaxation DiDB without constraints (
We will refer to the resulting problem QPRel A) when the explicit dependency the multipliers is required.
L-1
min 1x00 - 10112 RER
Σ
A (x!)
(x' (W'x'- + +b)) s.t.
(QPRel)
1=1
(eg (ey-ey) ey) (W bb²) S 0
(5)
-' (W' + +b) 00
x¹ > 0 for
L
(6)
The obtained problem is indeed QP with linear constraints. We need to clarify two questions. How does the problem QPRel us with solving DIB and how can this problem itself be solved efficiently?
QPRel vs. DIDB
First, we describe properties of the solution of QPRel providing information To do so, we define for arbitrary vectors x E 12
about DIDB
R and X E R4
dx, A) Σ de (x)) (a' (w' + +b))
as the corresponding propagation gap. It follows directly from the definition that for arbitrary non-negative À holds that:
if x is feasible for DIDB we have c(x, A) = 0, meaning that x equals the vector obtained by propagating _ through the neural net as defined in
if is feasible for QPRel we have e(zz, A) 2 O, meaning that there might be slack between the true output layer when getting x as an input and the value x' obtained by QPRel
In general the following holds for the relation between the solution of OPRel and DIDB (see also Figure D every point in the hatched area is certified to be classified as belonging to the class 77) Lemma 1. Denote the solution of OPRel by gg and the square root of its optimal objective value by dup. let d be the square root of the optimal objective value DDDB The following holds:
1. dyp S. d and when cp A) 0 we have dup = dl and Zep is optimal for DrDB
2. For two non-negative X2, 2, X2 with X < elementwise holds that dap (Aa) S dap (A2).
The first result from Lemma ensures that dap provides radius of a certified neighborhood around the anchor point. Whereas the second part indicates that we should choose À as large as possible to get our lower bound closer to DtDB Unfortunately,
0
adv
show below, the problem QPRel becomes non-convex for large values of X. While one could try to tackle non-convex QP with proper optimization methods, will address necessary conditions such that QQPeelis is guaranteed to be convex and can be solved efficiently next.
dap
c(xapp A)
7
917
Convexity of QPRel To look into the problem QPRel in more detail we introduce the Hessian M (which is constant matrix) of its objective function.
Figure I: Setting of the optimal solu- tions for DDBB Tadv and QPRel
Tap
Definition 1. Let E, ==* be the identity matrix of the corresponding dimension. We define M E B as the following symmetric block tridiagonal matrix
Do
MF
Mi
D1
Mī
M
with Mi -===->oW" D. XxEr and Ao = 1.
M2
D1-1
4

---

Under review as a conference paper at ICLR 2020
Using this matrix rewrite the objective function from [Pme| AiRelas (see Appendix min x. M"M b(x, + c(7"), ) s.t. =ER"
C
Lemma
where and č influence only the linear and constant terms and are therefore not relevant in this section. clearly see that the matrix M* determines the (non- Jconvexity of the objective function. The following theorem provides sufficient and necessary conditions on depending the weights Wi assuring that M is positive semi-definite. This allows off-the-shelf QP-solvers with excellent convergence properties.
From this reformulation
Theorem 1. Let W ..... W be the weights of an arbitrary pre-trained neural net and [[ the spectral norm of an arbitrary matrix. Then the following two conditions for À provide correspondingly sufficient and necessary criterion for the matrix M* be positive semi-defnile.
2)o
A1-1
(suf. condition)
A1 E
and X 1
for = ...... .....,,L
(8)
||i|P
4
(nec. condition)
A |
for
Furthermore, we define X and that correspondingly satisfy conditions
and 9 with equality:
2
X 4'
II
|
In case with a single hidden layer choosing definite.
= À from guarantees M to positive-semi
We use
and our previous results as guidelines for the choice of A. Since QPRel A) is monotonous in the sense of Lemma we perform a binary search between À and À from Theorem ] to find the point closest to Ā such that the QP remains convex. This preprocessing step does not considerably affect the runtime since checking whether matrix is positive semi-definite is done efficiently by Cholesky decomposition. However, it improves the final bounds by up to a factor two compared to the bounds obtained when using À À without binary search.
Note that this procedure has to be done once for given classifier. The obtained can subsequently be used solve QPRel for all anchor points and target labels. This is significant computational advantage compared to SDP based e-verification procedures. For example, the method by Dvijotham et al. (2099) includes the dual multipliers variables in the SDP problem that has to be solved for each combination of the anchor point, target label and verified epsilon.
UPPER BOUNDS
Now describe iterative procedure generating sequence of points in Th that converges point on the decision boundary. This procedure provides an upper bound on the distance to DIDB and thus allows for bi-directional verification of classifier.
Algorithm 1: Algorithm to construct an adversarial example by iteratively solving QPRel
Data: T0 trained neural net and À such that M is positive semi-definite, Got,
Result: dub. .00 begin
2
+00
while >> Ceots pred(5") pred (a:) do
Solve QPReel A) from the anchor point o
Tap. dup optimal solution and square root of the objective function value
c(Siup-
Choose the next anchor point on the boundary of the current certified region:
if Goo then
-- 1
+ dap
stp
else r <- x0 d (1 8)
||lb
|| 2
end
addy + 00; dui < |,.00 5.0
end
5

---

Under review as a conference paper at ICLR 2020
Idea In each step we verify certain neighborhood around the current anchor point x: and then expand the verified region further. For that we choose the next anchor point as follows. 1) Choice go from x towards the solution of @PRee since, if the QP relaxation is tight, its solution should be close to an optimal solution of DtDB which is the closest adversarial point to x 2) Choice of step size: we know that there are adversarial points within the ball of the verified radius d around the anchor, so every step size smaller than d would be unnecessary small. On the other hand, if we proceed with a new anchor point that is strictly farther away than d, we might miss an adversarial point lying close to the boundary of the d-ball around zº. Therefore, we choose the next anchor point to be on the boundary of the currently verified region, so that every e-ball that we manage to verify around the new point would add to the overall robust set. Algorithm 1 provides a pseudo-code for this procedure.
of direction:
The algorithm terminates as soon as the propagation gap c(x; A) (see (7 becomes small enough or the anchor point gets misclassified. Note that c(2, A) means that the solution x provides the optimal objective function value of the DiDB problem (see Lemma I and. thus, an adversarial example. However, the termination condition e S Col from Algorithm T line cannot ensure that the optimal point zip from the last iteration belongs to different class. Therefore, if we stop with e I God and the second termination condition not satisfied, we take an additional step on the boundary of the ball of radius dpp(1 + 5), where dup is the verified radius and 5 is tiny offset.
Termination
Additionally, we check in each step whether the next anchor point is already misclassified before the condition S Gial is reached (this can happen in multi-class setting; and is indeed observed frequently). We empirically verified that all points obtained this way are indeed true adversarials. This means that the sequence of anchor points converges towards the boundary and then, if no adversarial point was found yet, makes a step across the boundary using a positive, small ô. Note, while the most powerful attacks proposed by Carlini and Wagner (2017) were empirically shown to succeed for every considered sample, their success in not guaranteed and might require tuning of hyper-parameters. In contrast, we provide a formal proof of our method's convergence below.
Figure 2 illustrates how the constructed sequence of anchor points and solutions QPRel mightt look like for the setting of Figure Here only the first three steps are shown assuming that we would reach either a small value for the propagation gap or an adversarial point in the last step. Blue arrows show how we proceed from the solution of of the next anchor point in each iteration (compare to the update formula from Algorithm line g)
0
adv
dubb
Convergence The following result holds for the conver- gence rate of Algorithm [ under the assumption that the propagation gap c(x, A) is not too large with respect to the op- timal objective function value for the QPRel problem solved in each step.
x.
advv
Figure 2: Three steps of Algorithm] 1
Theorem 2. For k = 0, 0,1,... let be the propagation gap as defined in 7 and ok the optimal
objective fanction value we obtain after solving [PRel] in the k k'th iteration of Algorithm | Assume that there exists [0, 1] such that for all k the following holds.
||
Ck 1- equivalently d
ap
(10)
di
where I. is the anchor point and Tap is the optimal solution of QPRel in iteration k. (we omit the iteration index k on x' ss. Then for all
24 2 a)d Ck (2 11211=))))
+1 db
(11)
Furthermore, if a 1/2 then the number of iterations is such that Algorithm 7 terminates with eg S Ciol is bounded by
log Ciol -2log do log 2(1 a)) 1.
(12)

---

Under review as a conference paper at ICLR 2020
First of all, this result ensures that Algorithm Iterminates after final number of steps if (O)) holds for some & E (2. 1]. Moreover, provides a hint about how many iterations we would have to do decreased the threshold Gat by factor of 10. In this case the upper bound 12) on the number of iterations would increase by A = - (log 2(1 - a)) with Aka - oo when ( + and Ak, - 0 when a 1. Note that being almost means that eą is close to O. In this regime the relaxation is exact, as discussed in Lemma ! part 1. Therefore, considering a as a measure of tightness of the relaxation QPRel we can conclude that, when the relaxation is tight (i.e. a 1), decreasing Ctol by an order of magnitude will not be as costly as when is smaller.
Related work In relation to the methodology proposed in this section consider the work exact DIDB computation by Pordan et al. (2018). The proposed algorithm GeoCert iteratively computes the radius of the largest bp-ball that stays within certain polyhedral complex. The latter is incrementally updated in each step until the decision boundary is reached. This way one get a sequence of lower bounds on DIDB until the true distance is found. GeoCert significantly different to our method: 1.) It does not employ relaxation of (DiB). 2.) It does not change the anchor point, but rather expands the considered polyhedral complices by analyzing the linear regions of ReLU classifier. 3.) While it can use an upper bound to speed up the algorithm, the complexity of computing its own exact distance comparable MIP-based approaches as shown Dordan et al. (2018).
5
EXPERIMENTS
5.1 SETUP
The values of the parameters used well as the runtime of the compared algorithms is shown in Appendix B.1 and B.2 To solve the QP tasks we use Gurobi Optimization 2018).
Datasets and classifiers The experiments are performed using the MNIST and Fashion-MNIST datasets scaled such that the feature values lie in [0. 1] interval. For each of the datasets we use the correctly classified samples from 1200 train points (label distribution preserved) to evaluate the verification approaches. The exact number of used samples is reported for each experiment in Appendix D
For classification we take ReLU networks consisting of dense linear layers. The architectures we used are named by the number of hidden layers and the number of neurons per hidden layer: L1N50, L2N50, L3N50, L4N50, L5N50 and L1N300 with the same number of neurons in each hidden layer. normally trained classifiers well robustly trained ones (indicated
For each architecture by suffix R, e.g. LIN5OR) using the method by Wong and Kolter (2018) with 1.58 in l2-setting. The weights will be available in the project repository.
Competitors We compare our approach QPRel with the following c-verification methods: ConvAdy bynn and Kolter (2018) based on the LP relaxation of ReLU constraints (we use its implementation supporting the /2-norm by Croce et al. (2019), CROWN by Zhang et al. (2018) which is a layerwise bound propagation technique including performance boosting quadratic approximations and warm start (for each setting we report only the best result from these two competitors), and SDPRel by Raghunathan et al. (2018b) based on SDP relaxation solved by MOSEK. Finally, we take the iterative PGD attack with 200 steps and a step size of 2.5c/ /200 (in accordance with Madry et al. (2017) as competitor for QPReI-UB. We use the notation QPReI-LB QPReI-UB, when want to emphasize what bounds are meant.
5.2 RESULTS
Results on MNIST in l2-setting are shown in Table T We include the complete results in Appendix D We run all methods for each of the considered samples and report the following metrics.
AvgBound: The average value of the bounds obtained from QPRel and the corresponding competitor. Both lower and upper bounds are reported separately.
7

---

Under review as a conference paper at ICLR 2020
MedRelDiff to QPRel: The median of the relative difference between the bounds (e.g. QPReI-LB minus CROWN and then divided by CROWN). Positive values for the lower bounds mean our bounds better in average over the samples; negative values are better for the upper bounds.
to hit 50% LB-verified: The number of samples with an adversarial ffree radius e monotonically decreasing in Therefore, assess the performance of verification procedure like QPReI-LB or CROWN we report the smallest such that exactly 50% of the samples can be verified. The larger this value, the better.
VerRatio worst:
While the previous metric only considers the lower bound, we can consider both bounds (LB, UB) jointly by evaluation the verification ratio: For given e, it corresponds to the fraction of samples for which we can either prove that the e-neighborhood is adversarial-frn or contains misclassified point in In short: either the lower bound larger then or the upper bound is smaller then c.
Note, that for very small values almost all samples will be verified as c-robust by any algorithm providing non-trivial lower bounds. On the other side, when is large, attacks will be able to find an adversarial that even closer to the anchor and verify almost every sample as e-non-robust. Between these two extremes, the verification ratio drops to its minimum for certain value of ég. In this setting, fmaltesttraction
the considered algorithm is able to verify the smallest fraction of samples - that is, it corresponds to the worst case performance of the bi-directional verification method. We report this smallest fraction in the table, denoted with VerRatio worst. The larger, the better.
MedfelDiff UB-LB: Lastly, we report the median of the relative difference between the different bounds for each approach (QPRel-UB vs. QPReI-LB or PGD vs. CROW N/ConvAddy It shows the tightness of the certificates when compared to the upper bounds. The smaller, the better.
Table 1: Better bounds and verification ratio for the compact networks (2-perturbbations)
MNIST. l2
AvgBound
MedRelDiff
hit 50%
VerRatio worst (%)
MedRelDiff UB-LB (%)
QPRel (%)
LB-verified
L//R
Method
LB
UB
LB
UB
1/50
QPReI
0.42
0.49
0.398 0.239
87.5
13.7
1/50
CROWN+PGD
0.25
0.72
+63.0
-30.8
31.4
168.7
1/50/R
QPRel
1.69
1.84
1.698
90.3
5.3
1/50/R
CROWN+PGD
1.52
2.68
+12.8
-30.8
1.567
49.8
72.0
2/50
QPRel
1.20
1.21
1.174
99.3
<0.01
2/50
ConvAdv+PGD
0.89
1.80
+30.1
-2.00
0.891
51.2
89.8
2/50/R
QPRel
1.39
1.11
1.388
74,8
25.3
2/50/R
ConvAdv+PGD
1.47
2.62
2.9
-30.8
1.527
52.4
76.3
3/50
QPRel
0.18
0.55
0.181
26.0
200.2
3/50
ConvAdv+PGD
0.19
0.71
-9.3
-18.2
0.199
19.9
246.4
3/50/R
QPRel
1.10
1.78
1.091
59.5
57.7
3/50/R
ConvAdv+PGD
1.43
2.55
-21.9
-3.88
1.488
51.1
74.3
4/50
QPRel
0.09
0.58
0.106
9.1
484.6
4/50
ConVAdv+PGD
0.19
0.70
-50.4
-18.2
0.191
19.5
255,4
4/50/R
QPRel
0.69
1.76
0.698
35.7
142.5
4/50/R
ConVAdv+PGD
1.41
2,51
-9.88
25.0
1.497
51.2
71.6
5/50
QPRel
0.02
0.42
0.037
9.5
1370.6
5/50
ConvAdv+PGD
0.16
0.63
-84.4
-35.7
0.167
19.5
274.2
5/50/R
QPReI
0.37
1.76
0.391
20.0
357.0
5/50/R
ConvAdv+PGD
1.41
2.58
-73.1
-30.8
1.466
49.3
79.9
1/300
QPRel
0.26
0.28
0.243
94.0
1/300
CROWN+PGD
0.10
0.53
+149.1
-3.88
0.101
17.2
385.2
1/300/R
QPRel
0.78
1.81
0.782
42.8
120.4
1/300/R
CROWN+PGD
1.43
2.76
-44.1
-30.8
1.418
46.6
83.5
8

---

Under review as a conference paper at ICLR 2020
State-of-the-are bounds For the normally trained networks with smaller number of hidden layers the lower bounds computed by QPRel are tighter in comparison to the competitors in average and for most individual images (see Table [ AvgBound and MedRelDiff). ). This results in larger values of to hit 50% VerRatio as well. It seems that the competitors tend to underestimate robustness of these networks. For example, for 50% of the MNIST images classified with L1N300 we have improved the lower bound from CROWN by over 149%. This discrepancy in the quality of the lower bounds decreases with network's 's depth and if it was trained using the robust training approach by Wong and Kolter (2018) so that the competitors outperform QPRel's lower bound for robustly trained deep networks.
Noteworthy, the upper bounds derived via QPRel always outperform the one computed by the competing methods independent of the neural network architecture and the training procedure. That is, the 200-step PGI) attack was not able to construct adversarial examples that are closer to the anchor point then those found by QPReI-UB as described in Section 4 in all settings (see Table [ columns AvgBound/UB and MedRelDiff to QPRel/UB). Therefore, in the settings where the bounds from QPReI-LB are also tighter as the competitors' we get much higher VerRatio worst value and smaller MeffelDiff UB-LB that ensure the good quality of QPReI-LB bounds without computing the DIDB exactly. For example, for L2N50 the gap between QPReI-LB and QPReI-UB vanishes resulting in VerRatio worst of over 99%. That means the computed lower bound is almost the exact DtDB for the majority of the samples. Note that no exact method computing DtDB via MIP techniques is used to achieve that. For larger networks we observe decay of VerRatio worst and looser MedRelDiff UB-LB.
Comparison with SDP-relaxations in 460 -ettinn In order to compare our method with Raghu- nathan et al. (0018)) we generalize QPRel to the Lov -ee-ttnn as described in Appendix A Note, that the resulting relaxation is looser then the initial QPRel for the 12-setting since we introduce an additional penalty term to make the problem convex. That leads to worse results shown in Tables 9 and TO To compute the largest e such that the SDP verification succeeds we perform a binary search between the lower bounds dap computed by QPReI-LB and dmma = 1.0 which is the maximal perturbation for the lso norm on images. Since this approach takes longer to run we test it only on the L1N50R net trained with 0.1 (MNIST test data). Further, we speed up this approach by modifying MOSEK parameters (see Table 6 for details) such that the optimization procedure terminates earlier (approximately after a half of the usual number of iterations). We can still rely on the obtained results since we are not interested in the exact value of the SDP objective, but only whether it is positive or negative which was observed to be determined far sooner during the solution process then when the solver would reach a true optimum.
While QPReI-L.B in this setting is able provide tighter bounds then the I.P-baeed approaches for larger computational cost, our bounds are about 1.54 times larger then the ones of SDPRel (see Table 10 though computed three orders of magnitude faster (see Appendix B.2). This shows that the QP relaxation is less suited then SDPRel for obtaining tight bounds in -etting as already indicated by the arguments above and in Appendix A but trades this off by much better efficiency.
CONCLUSION
In this work we present a novel approach to solve the problem of approximating the minimal adversarial perturbations for ReLU networks based in a convex QP relaxation of DiD We show that the lower bounds computed with QPRel improve the results of the available LP based methods and allow certification of larger neighborhoods. Since convexity of the underlying QP determines computational efficiency of our approach we derive the necessary and sufficient conditions on the Lagrangian multipliers for it. Additionally, method that constructs a sequence of points converging to the point on the decision boundary provides upper bounds on DIDB. Quality of the obtained bounds in the le-setting is shown to be good enough to verify consistently over 80% of the considered samples for MNIST and FashionMNIST data and simple networks for all values of the perturbation magnitude, while competitors verification ratio might drop below 20%.
With contribution make step towards robustness verification of deep ReLU-based classifiers. To be able to apply the approach on a wider class of networks it should be generalized to popular architectures beyond ReLU activations and linear layers. Moreover, for deeper networks the proposed

---

Under review as a conference paper at ICLR 2020
relaxation was shown to provide looser bounds than the other methods indicating an important direction the future work. Furthermore, there are several points about Theorem that will be addressed in our future work. It is an open question how to verify (IO) priori. Experiments show that for the current choice of À (see the discussion after Theorem this condition does hold for small networks, but not for the larger ones.
10

---

Under review as a conference paper at ICLR 2020
REFERENCES
Rudy R Bunel, liker Turkaslan, Philip Torr, Pushmeet Kohli, and Pawan K Mudigonda. A unified view of piecewise linear neural network verification. Advances Neural Information Processing Systems 31, pages 4790-4799. Curran Associates, Inc., 2018.
Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In 2017 IEEE Symposium Security and Privacy (SP), pages 39-57. IEEE, 2017.
Francesco Croce, Maksym Andriushchenko, and Matthias Hein. Provable robustness of relu networks via maximization of linear regions. AISTATS, 2019.
Souradeep Dutta, Susmit Jha, Sriram Sankaranarayanan, and Ashish Tiwari. Output range analysis for deep feedforward neural networks. In NASA Formal Methods, pages 121-138. Springer International Publishing, 2018.
Krishnamurthy Dvijotham, Robert Stanforth, Sven Gowal, Timothy A. Mann, and Pushmeet Kohli. A dual approach to scalable verification of deep networks. Proceedings of the Conference on Uncer- tainty in Artificial Intelligence, 2018. http://///aun wttpe/////ooaaaa0////////1 http:///ei...///oeerede....enae
papers/ 204. pdf
Krishnamurthy Dvijotham, Robert Stanforth, Sven Gowal, Chongli Qin, Soham De, and Pushmeet Kohli. Efficient neural network verification with exactness characterization. Proceedings of the Conference on Uncertainty in Artificial Intelligence, 2019. URL sttp://auai. org/
201 9/ http://rceiinns////pepaeae http:/pppprrr.....pppo pd.
Rüdiger Ehlers. Formal verification of piece-wist wise linear feed-forward neural networks. Automated Technology for Verification and Analysis, pages 269-286. Springer International Publishing, 2017.
Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial
examples. In International Conference on Learning Representations, 2015. URL http://
arxiv.
LLC Gurobi Optimization. Gurobi optimizerr reference manual, 2018. URL gurobi con
Matthias Hein and Maksym Andriushchenko. Formal guarantees the robustness of a classifier against adversarial manipulation. In Advances in Neural Information Processing Systems 30, pages 2266-2276 Curran Associates, Inc., 2017.
Matt Jordan, Justin Lewis, and Alexandros G. Dimakis. Provable certificates for adversarial examples: Fitting ball in the union of polytopes. In Advances in Neural Information Processing Systems 33, 2018.
Guy Katz, Clark Barrett, David L. Dill, Kyle Julian, and Mykel Kochenderfer. Reluplex: An efficient smt solver for verifying deep neural networks. In Computer Aided Verification, pages 97-117. Springer International Publishing, 2017.
Alexey Kurakin, Ian J. Goodfellow, and Samy Bengio. Adversarial examples in the physical world. In International Conference on Learning Representations, 2016. URL httttt:p//axxiv.org/
abs/1607. 02533
Alessio Lomuscio and Lalit Maganti. An approach to reachability analysis for feed-forward ReLU neural networks. arXiv e-prints, art.
2017.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint 2017.
Nicolas Papernot, Patrick McDaniel, Somesh Jha, Matt Fredrikson, Z Berkay Celik, and Ananthram Swami. The limitations of deep learning in adversarial settings. In 2016 IEÉE European Symposium Security and Privacy & P), pages 372-387. IERE, 2016.

---

Under review as a conference paper at ICLR 2020
Aditi Raghunathan, Jacob Steinhardt, and Percy Liang. Certified defenses against adversarial examples. In International Conference on Learning Representations, 2018a.
Aditi Raghunathan, Jacob Steinhardt, and Percy S Liang. Semidefinite relaxations for certifying robustness adversarial examples. In Advances in Neural Information Processing Systems 31, pages 10877-10887. Curran Associates, Inc., 2018b.
Christian Szegedy, Wojciech Zaremba, llya Sutskever, Joan Bruna, Dumitru Erhan, lan Goodfellow, and Rob Fergus. Intriguing properties of neural networks. International Conference on Learning Representations, 2014.
6199
Vincent Tjeng, Kai Xiao, and Russ Tedrake. Evaluating robustness of neural networks with mixed integer programming. arXiv preprint 1rXiv:/711.07356,, 2017. URL htLlhtt://aaxxv.or
abs/1711. 07356
Yusuke Tsuzuku, Issei Sato, and Masashi Sugiyama. Lipschitzz-maginn training: Scalable certification of perturbation invariance for deep neural networks. In Advances in Neural Information Processing Systems 3/, pages 6541-6550 Curran Associates, Inc., 2018.
Shiqi Wang, Yizheng Chen, Ahmed Abdou, and Suman Jana. Mixtrain: Scalable training of verifiably robust neural networks. arXiv preprint arXiv:1811.0262. 2018.
Lily Weng, Huan Zhang. Hongge Chen. Zhao Song, Cho-Jui Hsich, Luca Daniel, Duane Boning, and Inderjit Dhillon. Towards fast computation of certified robustness for ReI.U networks. In Proceedings of the 35th International Conference Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 5276-5285. PMLR, 2018.
Eric Wong and Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 5295. PMLR, 2018
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 31, pages 4939 4948. Curran Associates, Inc., 2018.
12

---

Under review as a conference paper at ICLR 2020
A GENERALIZATION TO 10
For comparison with Raghunathan et al. (2018b) we show how our method can be applied to compute bounds on the distance to the closest adversarial measured using the lc norm. straight forward way would be to modify the objective function accordingly. By introducing a new variable m representing max, -a 2012 and ng new quadratic constraints we get the following versions of QPRel. Note that the quadratic constraints do not harm the complexity since they describe a convex cone and can handled by the QP-solvers including gurobi.
||. -0 -
min m + c(x, A), s.t. 2ER" MER
(a) 2 < m, -,.... no
(eg ey) (W I.
x/ 1. + +b4) 50
x' - (W'x' 11 + bb) 2 0. x 20
While this formulation of a similar structure as the QPRel (quadratic objective and linear plus quadratic constraints), the Hessian of the objective function is not positive semi-definite for any value of x. Since c(x, A) is the only source of quadratic terms now (squared distance to the anchor point is now replaced by m), the new M is of the same form as Lemma 2 but with Åg O. To see that we cannot affect the convexity of the objective function by the parameter À anymore consider vector 1 and at for / > Then
with an arbitrary xº Ro, x² =W''2" 20 with
T MM-x (1="))2-("" W x0 (1-)
(x
\1 - < w'
meaning that M cannot be positive semi-definite.
To overcome this issue we utilize the new quadratic constraints. We return back to a convex QP by considering the following problem with a positive Ja.
min #ER" MER
m + cx, A) + 1
((x) - -2y)² m). with
1=1
(a) = 2 < m, = 1....,
(cg yT Lw 1111 + +bb) 0
x' ( + b*) 2 0, x 2
Clearly, for 0 < μ < "g the solution of this problem is finite lower bound on DtDB with the loe norm. On the other side we are back in the setting of Theorem with À fu allowing us to use the same framework before. Results in the -etting were obtained by solving this problem with (2no)-1.
B EXPERIMENTS SETUP AND RUNTIME
B. SETUP
is chosen for each classifier according to Theorem and the discussion afterwards such that an accuracy level of 10-4 is achieved during the binary search in each λ For the values of other parameters in Algorithm we choose for all tests Cwt = 10 and = 10-4, Other methods are tested with the default settings provided in the corresponding repositories.
B.2 RUNTIME AND NUMBER OF ITERATIONS
Tables 2 3 and 5 show the average runtime and its standard deviation for networks LIN5OR, LIN100. LIN and L2N100 as well as the number of iterations Algorithm needs to terminate. During the binary search procedure we apply with SDPRel we always make 10 bisection steps. All tasks necessary for the computation of bounds on DIDB for one sample are run on single CPU (including the solution of QPs and SDPs with Gurobi Optimization (208)) and MOSEK respectively).
13

---

Under review as a conference paper at ICLR 2020
Here, do not consider ConvAdv CROWN performs always faster. From the comparison of the time for the computation our lower bounds (column Runtime-LB (s)) and the overall runtime (column Runtime (s)) conclude that obtaining the upper bounds takes n 1 times longer than solving the initial QP where n is approximately the overall number of the iterations in A Algorithm While in almost all considered settings n remains smaller than 4 it might become limiting factor when applying QPReI-UB on larger networks. That means further investigation of the convergence properties Algorithm D is necessary for generalizing the described method. From the comparison of QPReI-LB and CROWN we see the clear ad advantage of the latter since it doesn't 't involve any optimization task. However, this advantage comes in cost of the verification properties as discussed above. On the other hand, SDPRel with binary search provides better bounds, but is about 2000 times slower then QPReI-LB (see the last line in the MNIST section in Table
Table Runtime comparison, train data, l2-setting
Setting
Runtime-Lee -BB (s)
Runtime- Full (s)
Nr. iterations( (-UB)
Data
L/N
NrPts
Method
mean
std
mean
std
mean
std
1/100
1086
QPRel
1.467
0.142
4.200
2.091
2.845
1.416
1/100
1086
CROWN
0.021
0.002
MNIST
2/100
965
QPRel
0.280
0.017
0.472
0.140
1.679
0.484
2/100
965
CROWN
0.034
0.013
1/300
1142
QPRel
5,421
0.309
12.631
3.414
2.317
0.629
1/300
1142
CROWN
0.064
0,016
1/50
1180
QPRel
0.253
0.018
0.805
0.257
3.176
1.002
1/50
1180
CROWN
0.017
0.006
I/100
1083
QPRel
1.441
0.156
4.534
4.124
3.142
2.687
1/100
1083
CROWN
0.025
0.009
F-MNIST
2/100
924
QPRel
0.289
0.019
0.992
0.469
3.431
1.600
2/100
924
CROWN
0.031
0.012
1/300
1094
QPRel CROWN
5.385
0.317
18.782
12.443
3.503
2.313
1/300
1094
0.063
0.018
Table 3: Runtime comparison, test data, 12-setting
Setting
Runtime LB (s)
Runtime-Fuu (s)
Nr. iterations(-UB
Data
L/N
NrPts
Method
mean
std
mean
std
mean
std
1/100
1137
QPRel
1,451
0.142
4.225
1.994
2.898
1.342
1/100
1137
CROWN
0.024
0.009
MNIST
2/100
1028
QPRel
0.280
0.018
0.473
0.141
1.683
0.486
2/100
1028
CROWN
0.033
0.012
1/300
1166
QPRel
5.353
0.328
12.954
3.386
2.398
0.619
1/300
1 1166
CROWN
0.059
0.017
1/50
1212
QPRel
0.257
0.018
0.817
0.256
3.183
0.993
1/50
1212
CROWN
0.016
0.006
1/100
1061
QPRel
1.456
0.148
4.635
4.186
3.161
2.676
1/100
1061
CROWN
0.024
0.008
F-MNIST
2/100
949
QPRel
0.276
0.022
0.985
0.455
3.557
1.613
2/100
949
CROWN
0.031
0.012
1/300
1069
QPRel CROWN
5.406
0.301
19,585
12.080
3.638
2.251
1/300
1069
0.058
0.016
14

---

Under review as a conference paper at ICLR 2020
Table 4: Runtime comparison, train data, loc setting
Setting
Runtime-Ie LB (s)
Runtime- Full (s)
Nr. iterations
Data
L/N
NrPts
Method
mean
std
mean
std
mean
std
1/100
1086
QPRel
6,202
1.283
19.104
63.168
2.752
8.231
1/100
1086
CROWN
0.019
0.005
MNIST
2/100
965
QPRel
1.392
0.143
4.110
1.738
2.988
1.293
2/100
965
CROWN
0.029
0.011
1/300
1142
QPRel
10.470
0.854
14.567
7.457
1,400
0.732
1/300
1142
CROWN
0.054
0.017
1/50
1180
QPRel
2.634
0.916
16.813
19.141
5.818
3.660
1/50
1180
CROWN
0.016
0.006
1/100
1083
QPRel
5.750
1.314
18.447
66.807
2.651
7.627
1/100
1083
CROWN
0.018
0.004
F-MNIST
2/100
924
QPRel
1.500
0.179
3.496
2.978
2.348
1.954
2/100
924
CROWN
0.026
0.010
1/300
1094
QPRel
10.636
0.882
11.541
4.031
1.085
0.379
1/300
1094
CROWN
0.053
0.017
Table 5: Runtime comparison, test data, -etting
Setting
Runtime-LA LB (s)
Runtime- Full (s)
Nr. iterations(-U
Data
I/N
NrPts
Method
mean
std
mean
std
mean
std
1/100
1137
QPRel
6.208
1.250
22.898
75.986
3.145
8.924
1/100
1137
CROWN
0.020
0.007
MNIST
2/100
1028
QPRel
1.321
0.145
3.912
1.619
3.002
1,266
2/100
1028
CROWN
0.029
0.011
1/300
1166
QPRel
10.512
0.844
15.852
8,343
1,515
0.808
1/300
1166
CROWN
0,048
0.014
1/50
1054
QPRel
2.683
1.041
17.439
16.539
6.102
3.307
1/50
1054
CROWN
0.016
0.006
1/50
1054
SDPRel
4338.017
949.572
10
0.000
I/100
1061
QPRel
5,805
1.193
21.649
73.836
3.107
8.900
1/100
1061
CROWN
0.020
0.007
F-MNIST
2/100
949
QPRel
1.454
0.164
3.407
2.689
2.352
1.827
2/100
949
CROWN
0.025
0.009
1/300
1069
QPRel
10.686
0.927
11.829
5.051
1.107
0.466
1/300
1069
CROWN
0.048
0.014
15

---

Under review as a conference paper at ICLR 2020
C PROOFS
Lemma 1. Denote the solution of [QReel by aap and the square root its optimal objective value by dep, let d be the square root of the optimal objective value DrDB The following holds:
1. dup S d and when c(x, A) = O we have dup = and x is optimal for DIDB
2. For two non-negative X2, with A S elementwise holds that dap (A+) S dap( (A2).
Proof. Assume Indv is the optimal solution of DIDB Then it is an admissible point of QPRel as well and c(Tadr A) 0 since sr W' for | 1, 1,..., L 1. Since Sip is optimal for QPRel and Jady is just its admissible point we get that
de = | 10 = || =011 + c(Eadv. A) 2 - 11 + c(Tap. A)
d
proving the first claim. The second one follows from the fact that c(ar, A) for a given x a linear function of A:
cx
c(z, A) = X7
(II
where each c(r,, (xt) (x' (Wiz'-1 + +)) is non-negative for admissible because of the
non-negativity constraints (4 Therefore the claim follows immediately from the assumption that \t < Af for /
clz,1 x = Σ
Mo(a, S Σ xi((z, c(x,)2).
1=1
Lemma 2. Objective function of QPRel can be reformulated as
dup (A,x) x" M + x b(A, a(5")
where terms and don't 't depend on
Proof. The proof done by sorting the quadratic, linear and constant terms in the objective function of the initial formulation.
dep (A, ||ا0" - =0112 ( (xl
+b))
1--1
(20)Txx x0 2 (20)² 20 + ||
Σ \ (x') (x')T=² x' - W (ad)
1=1
( + Σ ( w (x0) 20 ( 8' 12012
quadratic term
lineur and constant lerms
From the quadratic term identify now the blocks of A
diagonal: MA Er
1 = --1,
sub-diagonal: MA = (MBr)1)) --- W
= 0, I,...,
16

---

Under review as a conference paper at ICLR 2020
Theorem 1.
Let W ...... W be the weights of an arbitrary pre-trained neural net and [[]]| the spectral norm of an arbitrary matrix. Then the following two conditions for À provide correspondingly sufficient and necessary criterion for the matrix M* be positive semi-defnite.
2Ao
A1-1 |
(suf. condition)
A1 S
and X S
for = =2, --1
[
-
(nec. condition)
A S
for =
L
1
Further, we define and X that correspondingly satisfy conditions 8 and 9 with equality:
d 2 II |
X = 4'
|
In case with single hidden layer Md with À from is guaranteed be positive-semi definite.
Proof. Let the assumptions hold and be an arbitrary vector from R². First we prove the sufficient condition by deriving lower bound on xf M that non-negative if holds.
L-1 Σ vu
x
M
r
>1I 12
(xd)
W'z'11
1=0
1=1
Ao
||=0|| 11
+
A6-1 1|00 1112
2
2
+
At
||
- A (xt) T w
+
d 1
2
2
1=1
Ao
|1
+
AL-1 1|o2--113
2
2
A1
+
|1=
1 Au (xt)
W
11
2
1-1 1
+
Σ
Ar-1
||
11
A
|
2
2
1=1
Aa
11
+
AL-1
1
11
Σ
\v
||
w'
2
2
2
1=1
+
L-1
A1-1
||0""
1|
A
W
W 112
2
2
1-1
AL-1
A 2
100
1-
1112
+
||
W
1'
2
1=1
A1
|
Σ
1--
1
1
+
2
2
4-1
AL-1
|
1-11pp
+
Σ
||ا
w' 11+
2
1=1
1
+ 2 (2X0 - 13 12
|
2
where we applied the aub-mulipllicativity property of the spectral norm, i.e. | W < |||aa|1 'II. to obtain the last inequality. We see that under the assumption
À and W's
holds that
X >=||W²1 12 2 and > 1/ < A for I 2,...,
17

---

Under review as a conference paper at ICLR 2020
and the lower bound x a in the last line is sum of non-negative terms meaning that x M 2 for all x E R
To prove the necessary condition consider for each / = I.... ...... - 1 special vector 2 (we don't 't explicitly label it as dependent on / to avoid overloaded notation) which is everywhere zero except
|
and L' = W'
arg max ZER"I1
||||||
For M in order to be positive semi remi-definite it has to satisfy
(1-1)
A Ei-1 Ae (W!)² T
M
z
Wi
Fr
x
A || 1 1|2 112- de (x') T W 2e115/112
= - - 1 Null
(A--1
||ا
which results in the necessary condition 19 stated above. remains to prove the sufficiency of (9) the considered network contains one hidden layer. For that we can reuse the last computation and obtain now for arbitrary R. that
x² M²x >o|1==1 - d1 (x')² 10200 + >111==112
=>01|>01 - 2112 Xill W 10 - x x'11
z Ao - - 1100112 + X1ll W2 2011
We see that the last term remains non-negative in case of λ
42g TW for all x.
Theorem 2. For k = 0, 0,1.... let be the propagation gap as defined in 7 and df the optimal objective function value we obtain after solving OPRel in the k 4'th iteration of Algorithm Assume that there exists [0, 1] such that for all k the following holds.
||x00
Ck < 1 aa equivalently dz
qp
10P
dg
where x is the anchor point and Tap the optimal solution of @PPee in k's iteration (we omit the iteration index k on s). Then for all k
&h S 2(1-
S (2(1 (2(1 db-
Furthermore, a 2 then the number of iterations ko such that Algorithm Terminates with eg S bounded by
log Csol 2oog do log 2(1 -a) a) 1.
12
Proof. First, we prove that given (00) it holds that de + < 2(1 a)) We denote the anchor point in
iteration k as d and the optimal solution for QPRel with that anchor point Zyp- The corresponding objects in the next iteration A + 1 are denoted by yd and Map- Then according to the choice of the next anchor point (see Algorithm line 8
0
y 2 + de
1110
spll = d4 -1100 - spll (compare to Figure
(13)
|1
l1
and it follows that
11y00 20112 + c(x, A) S -1000100
= + c(Fup A)
||000
= 11)
(1 - (1-a)2 2d + (1 a²) 2(1 a)d.
ck m0
18

---

Under review as a conference paper at ICLR 2020
Now, applying this relation every two subsequent iterations up to the k's obtain (here 1 a (1 + a) (1 - a) < 2(1 a) to get the last inequality)
Ck [1 (1-a - (1-02)21 a)) di - - (2(1-a))++1d)
remains prove the last inequality [2). Note that for 2 a > the derived upper bound on ck
is monotonically decreasing and converges to 0 as k find the first l such that the upper bound on e becomes smaller or equal Caol we have solve the equation Cool (2(1 a)))+Idd di for & resulting in the upper bound on & as claimed in 12
since 0 < 2(1 a)) 1. Therefore, to
D TABLES
Table MOSEK parameters we use to run SDPRel and their default values
Parameter
New value
Default value
MSK IPAR NUM THREADS
0
MSK DPAR INTPNT CO TOL MU RED
10 10-4 4
10 10-8
MSK _RKR OPPARINNPPNTAAI COOPNTCCOTTOLLL REL GAP
10-4
10-8
MSK_ DPAR LITTNTT_C_TTOT
10-6
10-12
MSK DPAR INTPNT CITPNT_CO_TIIE TOL DFEAS
DFEAS
10-4
10-8
_SS_DDAR_INTPNT.CC
10-1
10-8
hhttps://doee mosek com/9. h/ppythhnapipppaaaeeeer.. html contains the full list of pa- rameters including their description.
19

---

Under review as a conference paper at ICLR 2020
Table 7: Results for train data, /2-perturbations
Setting
MedRelDiff
hit 50%
VerRatio
MedRelDiff
Data
L/N
NrPts
Method
to QPRel (%)
LB-verified
worst (%)
UB-LB (%)
1/100
1086
QPReI-LB
0.246
82.8
13.4
1/100
1086
CROWN+FGSM
+82.4
0.129
8.1
1033.7
MNIST
2/100
965
QPReI-LB
1.174
99.3
<0.01
2/100
965
COnVAd++FGSM +30.1
0.891
23.3
277.9
1/300
1142
QPReI-LB
0.243
94.0
5,5
1/300
1142
CROWN+FGSM
+149.1
0.101
10.9
627.8
1/50
1180
QPReI-LB
0.872
82.4
14.3
1/50
1180
CROWN+FGSM
+67.0
0.506
8.8
419.4
1/100
1083
QPReI-LB
0.252
81.9
17.2
F-MNIST
1/100
1083
CROWN+FGSM +49.1
0.159
15.9
678.8
2/100
924
QPReI-LB
0.332
83.0
20.3
2/100
924
COMVAd++FGSM
+68.0
0.205
22.2
375.1
1/300
1094
QPReI-LB
0.183
78.8
23.1
1/300
1094
CROWN+FGSM +56.6
0.122
12.8
902.2
Table 8: Results for test data, 12- perttuuurbttions
Setting
MedRelDiff
to hit 50%
VerRatio
MedRelDiff
Data
I/N
NrPts
Method
to QPRel (%)
IB-verified
worst (%)
UB-LB (%)
1/100
1137
QPReI-LB
0.268
81.9
14.6
1/100
1137
CROWN+FGSM
+84.6
0.146
6.7
1097.2
MNIST
2/100
1028
QPReI-LB
1,251
99.4
0.0
2/100
1028
COnVAdv+FGSM +30.2
0.959
23.6
281.8
1/300
1166
QPReI-LB CROWN+FGSM +154.6
0.267
93.9
5.9
1/300
1166
0.111
7.0
658.5
1/50
1212
QPReI-LB CROWN+FGSM +68.5
0.937
80.0
15.2
1/50
1212
0.562
7.4
421.8
1/100
1061
QPReI-LB
0.258
79.8
19.2
F-MNIST
1/100
1061
CROWN+FGSM
+50.3
0.164
13.7
703.0
2/100
949
QPReI-LB
0.355
79.9
21.3
2/100
949
FGSM
+71.6
0.213
19.3
375.2
1/300
1069
QPReI-LB
0.194
77.0
24.7
1/300
1069
CROWN+FGSM
+59.3
0.122
10.6
890.9
20

---

Under review as a conference paper at ICLR 2020
Table Results for train data, Lo perturbations
Setting
MedRelDiff
hit 50%
VerRatio
MedRelDiff
Data
L/N
NrPts
Method
to QPRel (%)
LB-verified
worst (%)
UB-LB (%)
1/100
1086
QPReI-LB
0.010
5.8
1478.1
1/100
1086
CROWN+FGSM
+33.4
0.010
13.6
882.5
MNIST
2/100
965
QPReI-LB
0.057
5.3
2484.0
2/100
965
CONVAd++FGSM +16.8
0.057
32.4
220.4
1/300
1142
QPReI-LB
0.011
3.6
1691.4
1/300
1142
CROWN+FGSM
+104.3
0.011
13.0
575.1
1/50
1180
QPReI-LB CROWN+FGSM
0.033
1.6
3344.0
1/50
1180
+2.2
0.033
16.0
286.8
1/100
1083
QPReI-LB
0.010
6.9
1520.8
F-MNIST
1/100
1083
CROWN+FGSM
+5.5
0.010
17.8
599.5
2/100
924
QPReI-LB
0.013
3.6
1855.8
2/100
924
COMVAd++FGSM
+17.1
0.013
33.1
341.6
1/300
1094
QPReI-LB
0.007
3.0
1579.8
1/300
1094
CROWN+FGSM
+11.0
0.007
14.2
741.8
Table 10: Results for test data, Lo perturbations
Setting
MedRelDiff
to hit 50%
VerRatio
MedRelDiff
Data
I/N
NrPts
Method
to QPRel (%)
IB-verified
worst (%)
UB-LB (%)
1/100
1137
QPReI-LB
0.011
7.2
1439.0
1/100
1137
CROWN+FGSM
+33.6
0.011
10.5
946.5
MNIST
2/100
1028
QPReI-LB
0.115
5.2
2480.9
2/100
1028
CONVAdv+FGSM +16.5
0.058
28.7
218.6
1/300
1166
QPReI-LB
0.011
2.4
1704.3
1/300
1166
CROWN+FGSM
+105.7
0.011
8.1
610.7
1/50
1054
QPReI-LB
0.037
1.8
3462.1
1/50
1054
CROWN+FGSM
+2.3
0.037
15.5
280.8
1/50
1054
SDPReI+FGSM
-54.5
0.074
51.1
68.1
1/100
1061
QPReI-LB
0.011
6.8
1520.9
F-MNIST
1/100
1061
CROWN+FGSM
+5.5
0.011
19.3
605.4
2/100
949
QPReI-LB
0.012
2.5
1938.1
2/100
949
FOS
+18.2
0.012
28.6
344.7
1/300
1069
QPReI-LB
0.007
3,9
1543.1
1/300
1069
CROWN+FGSM
+12.6
0.007
12.9
736.9
21


Reviews:
[{"review_id": "SyeGBpm3tH", "reviewer": "AnonReviewer2", "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:\nThis paper introduces an encoding of the bounds on Neural Networks based on a (non-convex) quadratic program. The method covers both L_inf and L_2 perturbations, and the optimization problem posed are solved using Gurobi.\n\nThe authors formulate the ReLU as a quadratic constraint , and then relax the problem by taking it's Lagrangian dual. This results in the standard properties from taking a lagrangian dual: any choice of dual variables will produce a lower bound.\nFor an appropriate choice of dual variables, the lagrangian problem is convex and the authors give a way of choosing dual variables that guarantees this convexity such that the bound can be computed.\n\nA method is proposed to find upper bound on the verified region (which can also be understood as just finding an incorrectly classified sample, that should ideally be the closest to the original point), based on iterating the solving of the QP.\n\nComments:\n- Encoding of the ReLU as a quadratic constraint as done in (2) is not novel, as it was done before by Dvijotham et al. (UAI 2019) or Raghunathan et al. (NeurIPS 2018). The Lagrangian relaxation that is then done is to the best of my knowledge different than any one introduced before. \n\n- The problem solved is also different to most of the literature: rather than verifying robustness for a certain radius, this attempts to find the maximum radius being robust, which provide more information.\n\n- I'm confused at the upper bound finding method. The solution of the QP will not necessarily respect the constraints of forward propagation of the network so if you just consider the variables corresponding to the input, the resulting output may not necessarily a violation. Also, I don't understand the motivation for why repeatedly solving the QP will lead to a good violation on the decision boundary. I know that the paper says that \"analytic investigation of this algorithm including a convergence proof remains future work.\" but at the moment there is not even an intuition for why it might be a good idea. By the second iteration, there is no notion of the reference point around which safety is computed so it's not sure how the closest violation would be found.\n\n- The network tested are extremely small, even by formal verification of neural network standards, which makes it hard to appreciate the impact of the method and makes me question the applicability of the method. Is it because QP are more complex to solve than LPs?\n- It is also a little bit problematic to give results as ratio of improvements over the lower bound on radius, when most of the network used are non robust, given that those networks have extremely low verified radius, so the relative difference will look inflated. \n\n- The reporting of the verification ratio as a function of the perturbation radius is an interesting measure that I think is very benificial to making the point but I think it should be better explained as it took me a long time to get the point. The experiment section in general is quite confuse and hard to parse, having to jump around quite a lot to get what the author meant.\n\n- FGSM is a very very weak baseline for the use that is employed here. By construction, it doesn't look for the smallest violation, is not iterative, and produce perturbations at the limit of the attacked budget.\n\n- The paper takes the opportunity to say that their method is 2000x faster than SDP based method but not that they are 10x to 100x slower than CROWN (outside from the appendix). It's better to report results clearly than only trying to show the good points of the algorithm. The bounds obtained are tighter than those resulting from Crown so it might be a worthwile tradeoff to make.\n\n* Probably worth discussing / comparing to:\nProvable Certificates for Adversarial Examples: Fitting a Ball in the Union of Polytopes, Jordan et al. (ICML 2019)\n\n* Typos and minor comments:\n- Adjust the label for Figure 2\n- \"Guarantied\" on page 4\n- top of page 8 \"VerRation\"\n\n\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "HyxxRpXCYB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a method to compute the distance to the decision boundary for a given network, where the network is composed of linear layers followed by a RELU activation. The authors provide a lower bound and an upper bound for the distance of a sample from the decision boundary. The lower bound is obtained as the solution to a quadratic program, which in turn is obtained by relaxing the original optimization problem. The relaxation is obtained by decomposing the RELU condition to a set of 3 constraints (eqn 2). The authors also provide conditions under which the quadratic program stays convex.\n\nThe paper is clearly written. The method is useful to verify robustness of neural networks. The experiments show the improvement of the proposed method over existing certificates.\n\nWhile the lower bound is theoretically justified, I did not see any guarantees for the upper bound. I am not referring to a convergence proof here, but simply a guarantee that the value returned by Algorithm 1 is indeed an upper bound. Algorithm 1 does not verify whether the point returned belongs to a different class. It would also be helpful to provide intuition for the iterative procedure to compute the upper bound.\n\nMinor comments:\n1) Line 9 is Algorithm 1: x^qp0 should be x^qp (no 0)\n2) What is L/N in Table 1? ", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "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": {}}, {"review_id": "BklGRAFe9B", "reviewer": "AnonReviewer1", "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 proposed to use a convex QP relaxed formulation to solve the neural network verification problem, and demonstrated its effectiveness on a few small networks (1-2 hidden layers) on MNIST and Fashion-MNIST datasets.\n\nThere are several benefits the proposed methods: they are technically tighter relaxations of ReLU neurons and empirically the authors show they perform well in L2 norm (but not L infinity norm, unfortunately); solving this formulation does not require to know pre-activation bounds of hidden neurons; also the convexity of the QP problem needs to be determined only once for a model, rather than once per example. Although the QP relaxation of ReLU neuron is not new and has been used in Raghunathan et al., 2018b, they solve the problem as a SDP rather than convex QP. SDP is tighter than the convex QP formulation used in this paper, however is much slower.\n\nIssues and Questions:\n\n1. The concept of \"bi-direction verification\" is not new, since finding an upper bound is basically finding adversarial examples. Many previous papers have been using PGD based attacks to obtain the upper bound. Convex relaxation based verification methods like CROWN can also be used for generating adversarial examples, and it is called \"Interval attack\", which is demonstrated in [1][2]. Claiming this is the first \"bi-direction robustness verification technique\" is not accurate.\n\n2. The use of FGSM as an upper bound is inappropriate, as FGSM is known to be a very weak attack. Replacing it with a multi-step PGD attack is necessary. Using a stronger attack will also close the gap between upper and lower bound. Also, compare the upper bound found by PGD with QPRel-LB and update Figure 3(a). If a stronger attack like PGD is used, I think for larger norms CROWN+PGD in Figure 3(c) should be able to verify almost all examples.\n\n3. The models used in Table 1 is trained using a L2 perturbation of epsilon=0.1. This epsilon value is too small for L2 norm. In page 22 (last page of appendix in arxiv version) of [3], you can find the they conduct L2 robustness training but at a much larger epsilon value (eps=1.58). Sine the authors did not use these standard epsilon setting, my concern is that does the proposed method works at larger L2 epsilon?\n\n4. Some experiments on larger and deeper networks are necessary; especially, it is interesting to see how CROWN and the proposed method scale to deeper networks. The presented experiments only include networks with 1 and 2 hidden layers, which is insufficient. A new experiment with number of hidden neurons per layer kept (say 50) and increase the depth from 2 to 10 will be very helpful.\n\n5. The main claim of the paper in Introduction needs to be made clearer, especially the primary strength of the proposed algorithm is in L2 norm, and it does not seem to outperform CROWN in L infinity norm setting.\n\nFurther improvements and potential directions:\n\n1. In the proposed method, the authors relaxed ReLU neurons using quadratic programming. This relaxation does not require to computing bounds for the neuron activation values. However, I think it is possible to include neuron activation upper and lower bounds as constraints of the QP problem (adding them as constraints like l <= x <= u in Eq. QPRel). This will make the bounds tighter. The per-neuron lower and upper bounds can be obtained using CROWN efficiently, so there is no too much computation cost.\n\n2. Improving the scalability of QP relaxation is another challenge. CROWN can be implemented efficiently on GPUs [4]. For QP relaxations, this can possibly be done by transforming QP solving into a computation graph that can be executed efficiently on GPUs (this is a potential future work directions and I do not expect the authors to address them during the discussion period).\n\nOverall I am positive with this paper, however before accepting it I think the authors should at least make their claims clearer (the relaxation performs well mainly in L2 norm, and the concept of \"bi-directional verification\" is also not entirely new), replacing FGSM by a 200-step PGD and compare the upper bound found by PGD with QPRel, and test the proposed algorithm in models trained with a larger epsilon (eps=1.58 to align with previous works, if possible) and deeper models.\n\n[1] Wang, S., Chen, Y., Abdou, A., & Jana, S. (2019). Enhancing Gradient-based Attacks with Symbolic Intervals. arXiv preprint arXiv:1906.02282.\n[2] Wang, S., Chen, Y., Abdou, A., & Jana, S. (1811). MixTrain: Scalable Training of Verifiably Robust Neural Networks.\n[3] Wong, E., Schmidt, F., Metzen, J. H., & Kolter, J. Z. (2018). Scaling provable adversarial defenses. In Advances in Neural Information Processing Systems (pp. 8400-8409).\n[4] https://github.com/huanzhang12/RecurJac-and-CROWN\n", "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 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 article is concerned with sensitivity to adversarial perturbations. It studies the computation of the distance to the decision boundary from a given sample in order to obtain robustness certificates, and presents an iterative procedure to this end. This is a very relevant line of investigation. The reviewers found that the approach is different from previous ones (even if related quadratic constraints had been formulated in previous works). However, they expressed concerns with the presentation, missing details or intuition for the upper bounds, and the small size of the networks that are tested. The reviewers also mentioned that the paper could be clearer about the strengths and weaknesses of the proposed algorithm. The responses clarified a number of points from the initial reviews. However, some reviewers found that important aspects were still not addressed satisfactorily, specifically in relation to the justification of the approach to obtain upper bounds (although they acknowledge that the strategy seems at least empirically validated), and reiterated concerns about the scalability of the approach. Overall, this article ranks good, but not good enough. 

Decision: Reject