Curvature-based Robustness Certificates against Adversarial Examples
Authors: Sahil Singla
Soheil Feizi
Venue:  (2020)
Keywords: Adversarial examples
Robustness certificates
Adversarial attacks
Machine Learning Security

Abstract: A robustness certificate against adversarial examples is the minimum distance of a given input to the decision boundary of the classifier (or its lower bound). For {\it any} perturbation of the input with a magnitude smaller than the certificate value, the classification output will provably remain unchanged. Computing exact robustness certificates for deep classifiers is difficult in general since it requires solving a non-convex optimization. In this paper, we provide computationally-efficient robustness certificates for deep classifiers with differentiable activation functions in two steps. First, we show that if the eigenvalues of the Hessian of the network (curvatures of the network) are bounded, we can compute a robustness certificate in the $l_2$ norm efficiently using convex optimization. Second, we derive a computationally-efficient differentiable upper bound on the curvature of a deep network. We also use the curvature bound as a regularization term during the training of the network to boost its certified robustness against adversarial examples. Putting these results together leads to our proposed {\bf C}urvature-based {\bf R}obustness {\bf C}ertificate (CRC) and {\bf C}urvature-based {\bf R}obust {\bf T}raining (CRT). Our numerical results show that CRC outperforms CROWN's certificate by an order of magnitude while CRT leads to higher certified accuracy compared to standard adversarial training and TRADES.


Under review as a conference paper at ICLR 2020
CURVATURE-BASED ROBUSTNESS AGAINST ADVERSARIAL EXAMPLES
CERTIFICATES
Anonymous authors Paper under double-blind review
ABSTRACT
A robustness certificate against adversarial examples is the minimum distance of a given imput the decision boundary of the classifier (or its lower bound). For any perturbation of the input with magnitude smaller than the certificate value, the classification output will provably remain unchanged. Computing exact robustness certificates for deep classifiers is difficult in general since it requires solving a non- convex optimization. In this paper, we provide computationally- -efffiiinnll robustness certificates for deep classifiers with differentiable activation functions in two steps. First, we show that if the eigenvalues the Hessian of the network (curvatures of the network) are bounded, we can compute robustness certificate in the 12 norm efficiently using convex optimization. Second, we derive a computationally- efficient differentiable upper bound on the curvature of deep network. We also use the curvature bound as regularization term during the training of the network boost its certified robustness against adversarial examples. Putting these results together leads to our proposed Curvature-based Robustness Certificate (CRC) and Curvature- based Robust Training (CRT). Our numerical results show that CRC outperforms CROWN's certificate when trained with our regularizer while CRT leads to higher certified accuracy compared to standard adversarial training.
INTRODUCTION
Modern neural networks achieve high accuracy on tasks such as image classification and speech recognition, but are known to be brittle to small, adversarially chosen perturbations of their inputs (Szegedy et al., 2014). A classifier which correctly classifies an image x, can be fooled by an adversary to misclassify an adversarial example + 8, such that x + 8 is indistinguishable from to human. Adversarial examples can also fool systems when they are printed out on a paper and photographed with smart phone (Kurakin et al. 2016a). Even in black box threat model, where the adversary has no access to the model parameters, attackers could target autonomous vehicles by using stickers or paint create adversarial stop sign that the vehicle would interpret a yield or another sign (Papernot et al., 2016). This trend is worrisome and suggests that these vulnerabilities need to be appropriately addressed before neural networks can be deployed in security critical applications.
In the last couple of years, several empirical defenses have been proposed for training classifiers to be robust against adversarial perturbations (Madry et al. 2018; Samangouei al., 2018 Zhang et al.)
Papernot et al. 20166 Kurakin et al. 20116b; MMyato et al. 2017: Zheng et al. 2016) Although
these defenses robustify classifiers to particular types of attacks, they can be still vulnerable against
stronger attacks (Athalye et al. 20188] Carlini & Wagner 2017: Uesato et al. 2018 Athalyy & Carlini 2018). For example, (Athalye et al., 2018) showed most of the empirical defenses proposed in ICLR 2018 can be broken by developing tailored attacks for each of them.
To end the cycle between defenses and attacks, a line of work on certified defenses has gained attention where the goal is to train classifiers whose predictions are provably robust within some given
region (Huang et al.) 2016 Katz et al. 2017|1 Ehlers 2017 Carlini et al. 2017 Cheng et al.) 2017 7
Lomuscio & Maganti| 2017 Dutta et 2011 Fischetti & Jo 2018 Bunel et al. 2017 7 Wang et al.
2018al Wong & Kolter 2017 Wang et al. 2018b; b Wong et al. 20188 Raghunathan et al. 2018)) a
Gehr Dvijotham et | 2018a by Croce et al. [2188] Singh al. [018]] Gowal et al. 2018 Gehr et al. 2018
Mirman et al. 2018] Zhang et al. 2018b) Weng et al.] [2018). These methods, however, do not seale
to large and practical networks used in solving modern machine learning problems. Another line of

---

Under review as a conference paper at ICLR 2020
defense work focuses on randomized smoothing where the prediction is robust within some region around the imput with a user-chosen probability (Liu et al, 2017; Cao & Gongl 2017 Lécuyer et al.
2018 Li et al. 2018 Cohen et al.] 2019 Salman et al. 2019]. Although these methods can scale to large networks, certifying robustness with probability close to 1 often requires generating a large number of noisy samples around the input which leads to high test-time computational complexity.
If the classifier f()) was linear, the distance of an input point x to its decision boundary (i.e. the robustness certificate) can be computed efficiently using a convex optimization. For example, the l2 robustness certificate in that case would be equal to J Vxx))/>Vv//x/// based on neural networks are not linear and and can have non-zero curvatures in different parts of the input domain. The deviation of the classifier from the linear model makes the robustness certification problem to be a non-convex optimization which is often difficult to solve exactly. However, if we could compute global bounds on the maximum curvature values of the classification network, one may be able to compute computationally--ffice non-linear deep classifiers. This is the key intuition of our results in this paper.
However, modern classifiers
lower bounds on the robustness certificate even for
In this work, we derive global bound on the Lipschitz constant of the gradient of deep neural networks with differentiable activation functions (such sigmoid, tanh, softplus, etc.). This provides an upper bound on the magnitude of the eigenvalues of the Hessian or the curvature values of the classification network. Using this global curvature bound and for the l2 metric, certification and attack problems. In the certification problem and for a given pre-trained classifier, provide camppuaationally-fffeeee decision boundary. In the related attack problem, for a given input and region around it, our goal is to find a perturbed input (an adversarial example) that maximizes the loss inside the given region. The outcome of the attack problem is then used in the adversarial training procedure (Madry et al. 2018) to further robustify the network. Furthermore, our global curvature bound is differentiable and we show that adding it to the loss function as a regularizer boosts certified robustness measures.
tackle both the
lower bound on the distance of a point to the classification
We note that other recent works (e.g. Moosavi Dezfooli et al (019)) Qin al. (2019) empirically show that using an estimate of curvature at inputs as a regularizer leads to empirical robustness on par with the adversarial training. In this work, however, we use a provable global upper bound on the curvature (and not estimate) as a regularizer and show that it results in high certified robustness. Moreover, previous works have tried to certify robustness by bounding the Lipschitz constant of the neural network (Szegedy et al. 2014 Peck al. 2017 Zhang et al. 2018c Anil et al. [018 Hein & Andriushchenkoo 2017). Our approach, however, is based on bounding the Lipschitz constant of the gradient of deep neural networks. We discuss existing works in more details in Appendix A
Below, we state the key theoretical results of this paper informally while detailed statements of these results are presented in Section 4
Theorem (informal) 1. Let z with differentiable activation functions. Then, the curvature of the neural network function is globally bounded as follows:
(L) denotes the tt logit of L layer fully-connected neural network
mI <V22 (1) & MI,
VxeRD
where m and M can be computed efficiently using parameters of the network.
This result along with the min-max theorem leads to the following curvature robustness certificate: Theorem (informal) 2. Consider a network whose curvature values are bounded. For a given input ()) with the true label y and the attack target (t # y). let p'urt denote the exact robustness certificate, iee. the distance of ( to the decision boundary. We can efficiently compute d' such that d'eet& Peert. Moreover, if the solution (crtt) for d' satisfies (1.) (1.) then d'ert Poert
zz
We have similar results for the attack problem. For simplicity, summarize definitions of Poerts d' Pattack d'ttack in T
In summary, in this paper, make the following contributions:
We provide global bounds on the eigenvalues of the Hessian of deep neural network with differentiable activation functions (Theorem and Theorem 4 In addition to the adversarial robustness problem, these bounds may be of an independent interest for readers.
2

---

Under review as a conference paper at ICLR 2020
Certificate problem (-) cent
Attack problem (-) attack
primal problem, P
mi)n 1/2/ xx(0)
|x |sp f(x)
dual function, (())
minx 1/2/x - 12 1xx
minx f(x) + +n/2(11x x- xx)
p²)
When is dual solvable?
-1/M s 1/5 -1m
-m 11
dual problem, d(-)
max- 1/X-1//Mns-1/m decrt(
max-msy dattack (1))
When primal dual?
f fxx(cert))= -0
|x(attuck) - xx(
Table summary of various primal and dual concepts used in the paper. denotes the function of the decision boundary, i.e. zy (L) 2 where is the true label and t is the attack target. m and M lower and upper bounds on the smallest and largest eigenvalues of the Hessian of respectively.
Method
Non-trivial bound
Multi- layer
Activation functions
Norm
Szegedy et al.
20144)
X
All
l2
Katz al. (0117)
/
ReLU
1
Hein Andriushchenko 2017
X
Differentiable
l/
Raghunathan et al.
(2018) 8a)
X
ReLU
100
Wong & Kolter
2017)
ReLU
100
Weng ct al. (2018)
V
ReLU
11, 1,,22,45 Low
Zhang al.
2018b
/
All
11,2, 1oo
Cohen al.
2019)
All
1/
Ours
Differentiable
ly
Table 2: Comparison of methods for providing provable robustness certification. Note that Cohen al. 2019) is probabilistic certificate.
Using the global curvature bounds, we develop computationally efficient methods for both the robustness certification well the adversarial attack problems (Theorems) T Tand
We show that using our proposed curvature bounds as regularizer during training leads to improved certified accuracy on 2,3 and 4 layer networks (on the MNIST dataset) compared to standard adversarial training with PGD (Madry et al.) 2018) as well as TRADES (Zhang et 2019). Moreover, our robustness certificate (CRC) outperforms CROWN's certificate (Zhang et al. 2018b) significantly while taking less time to compute.
2 NOTATION AND PROBLEM SETUP
Consider a fully connected neural network with L layers and N, neurons in the 1th layer (L 2 and / E [4] for multi-label classification problem with C' classes (N, C). The corresponding function of the neural network is z (4), RDD RC where D is the dimension of the input. For an input x, we use (1) (x) E R and a (²) (x) N to denote the input (before applying the activation function) and output (after applying the activation function) of neurons in the Ith hidden layer of the network, respectively. To simplify notation and when no confusion arises, we make the dependency of (1) and (1) to x implicit. We define (0) (x) x and No D.
With a fully connected architecture, each (1) and (4)) is computed using a transformation matrix (J) NNNNN-1 the bias vector ((4) NN and an activation function o(.) as follows:
z (x)) ( (x) (()
() = (z (x)).
We (z. (L)
2 (x) as shorthand for (1) (x) 29 (x).
3

---

Under review as a conference paper at ICLR 2020
.9. We use [p] to denote the set [l....,p} and [p.g], p. q to denote the set {p,p+ 1,...,9). We use small letters i, j. & etc to denote the index over a vector or rows of a matrix and capital letters I, J to denote the index over layers of network. The element in the 5th position of vector is given by vi, the vector in the 1th row of a matrix A is A; while the element in the 7th row and j column of A is Ai.j
-- We use ||v] and ||] to denote the 2-norm and the operator 2-norm of the vector and the matrix A, respectively. We use /v| and |A| to denote the vector and matrix constructed by taking the elementwise absolute values. We use Amaz (A) and Amin (A) to denote the largest and smallest eigenvalues of symmetric matrix A. We use diag(v) to denote the diagonal matrix constructed by placing each element of v along the diagonal. We use @ denote the Hadamard Product, I to denote the identity matrix. We use & and > to denote Linear Matrix Inequalities (LMIs) such that given two symmetric matrices A and B where A > B means A B Positive Semi-Definite (PSD).
USING DUALITY TO SOLVE THE ATTACK AND CERTIFICATE PROBLEMS
Consider an input x(0)
(0) with true label y and the attack target 4. In the certificate problem, our goal is to find a lower bound of the minimum 12 distance between (") and the decision boundary,
(L) (L) The problem for solving the exact distance (primal) can be written as:
Zy z
[01]
min max ( X x x01 1 (z 2 -2
Peert
min
(1)
2) (x)==,
However, solving the above problem can be hard in general. Using the minimax theorem (primal dual), we can write the dual of the above problem as follows:
Porrt& 2 max (1)r
deert (11) = min [ x (00
+1 (2(2)) 2 (x))
(2)
From the theory of duality, we know that deer:(1) for each value of 1) gives a lower bound on the exact certification value (the primal solution) Peere: However, since 2 -z(() is non-convex, solving
(L)
(1)r for every 7) can be difficult. In the next section, we will prove that the curvature of the
function (L) z (L) is bounded globally:
mI & V 2
(1( 2
(.))
$ MI
VxERD, m <0 M >>0 0
(3)
In this case, have the following theorem:
Theorem 1. Accr((1) is convex optimizution problem for -1/M S Sns -1/m. Moreover, If (cert)
the solution to d'ert such that way (x(er))) =2(2) "x (x(ert))) then Peert = d'ert-
Below, we briefly outline the proof while the full proof is presented in Appendix D.1 The Hessian of the objective function of the dual decrt(1) i.e the function inside the minx is given by:
v2 2 ||x xx-x(() 10 + (2 z. (1 (x) = I+ n/² (2)()) 2,55)
From equation (3.. we know that the eigenvalues of I 17 (z() -2 (0)) are bounded between
(1 + ym, + ny, M if 7 2 0, and in (1 + 1 + 17m) 17 S 0. In both cases, we can see that for -1/M s 5 -1/m, all eigenvalues will be non-negative, making the objective function convex.
When x (cert) satisfics 2
2 (I.) diers 1/2/x((crrt)_ (0) using the duality thcorem and
definition of Poert: we get Peert doert-
Next, we consider the attack problem. The goal here is to find an adversarial example inside an lz ball of radius P such that (L) (1) is minimized. Using similar arguments, we can get the following theorem for the attack problem (pattack) dattack and dattack are defined in Table I]:
Theorem 2. dattack (n) is a convex optimization problem for-m -m S n. Moreover, if (attock)) is the solution to d' such that ([attack)
x P. Pattack = d'ttackk
The proof is presented in Appendix D.2 Both Theorems I hold for any non-convex function with continuous gradients. They can also be of interest in problems such as optinization of neural nets.
Using Theorems
1 and 2
we have the following definitions for certification and attack optimizations:
4

---

Under review as a conference paper at ICLR 2020
Definition 1. (Curvature-based Certificate Optimization) Given input x (0) with true label y. the false target we define (n((ert), x((ert)) the solution of the following max-min optimization:
max min x x ( -1/Msnp--1/n 1/m
(T) -z( (.)) (x))
We refer to [x(cert) - || as the Curvature- Robustness Certificate (CRC).
Definition 2. (Curvature-basee Attack Optimization) Given input x (0) with label y, false target t, and the lg ball radius we define (spattacck) x(attack)) as the solution of the following optimization:
[1Ix-x (2!)
max min 12-111
When xlattack) is used for training in adversarial training framework, call the method the Curvature-based Robust Training (CRT).
Since both curvature- based certificate and attack optimizations are convex optimization problems, any convex optimization solver can be used to solve them. our implementation, we use majorization- minimization to solve the dual function for given 17 and bisection method maximize r7. More details are given in Appendix C.4 and C.5
CURVATURE BOUNDS FOR DEEP NETWORKS
In this section, provide computationally efficient approach compute the curvature bounds for neural networks with differentiable activation functions. To the best our knowledge, there is no prior work finding provable bounds the curvature values of deep neural networks. Our results rely on a closed form expression for the Hessian of the tt logit as a sum of matrix products (Section After establishing this result, we first derive curvature bounds for two-layer network in Section and then extend the bounds to deeper networks in Section
4.1 CLOSED FORM EXPRESSION FOR THE HESSTAN
Using the chain rule of second derivatives, we can derive V22 (1) sum matrix products: Lemma 1. Given an T. layer neural network, the Hessian of the tt hidden unit with respect the input x, i. V22 (L) is given by the following followingformuaar
I-1 (B") diag F (1.) oo (d B
V2Z (1)
where B(I) is the Jacobian of (1) with respect to x (dimensions N₃ x D), and F(L.I) is the Jacobian of (L) with respect to (!)) (dimensions N₁ x N1).
The proof presented in Appendix D.3 Using the chain rule of gradient, we can compute B(), F(L.)) matrices in Lemma recursively as follows:
( W(1)
B didg a (z B(T-1) I [2,
(4)
FL.L-1) (1))
(L.)) w(L diag (o' (z(b-1)) ((L-1.)) IE [
(5)
This leads to a fast back-propagation like method that can be used to compute the Hessian. Note that Lemma ] only assumes a matrix multiplication operation from a (I-1) to (!)) Since convolution operation can also be expressed matrix multiplication, we can directly extend this lemma deep convolutional networks. Furthermore, Lemma]] I can also be of independent interest in other related problems such as higher-order interpretation methods for deep learning (e.g. (inglaa et 2019
4.2 CURVATURE BOUNDS FOR Two LAYER NETWORKS
For a two-layer network and using Lemma
(2)
2(22) is given by:
2 (2) ((2)) = (W(1)) ding (W(?) w!!)) ((7))o oo (201 )was
5

---

Under review as a conference paper at ICLR 2020
Note that only o' (z) depends on x. We can maximize and minimize each element in the diag term, (w w()))
yo 4. )o (z)")) independently subject to the constraint that o (.) is bounded. Using
this procedure, we construct matrices and that satisfy properties given in the following theorem:
Theorem 3. Given nwo layer network whose activation function has bounded second derivative:
hy a (x) S he Vx e
(a) We have the following linear matrix inequalities (LMIs):
N (2)
Li & P
(2)
Vx RD
(b) If hy 0 and hr SO, P is PSD matrix, N is NSD matrix.
(c) This gives the following global bounds on the eigenvalues of the Hessian:
ml V Dyy 2 < MI, where M >maz (P), m Amin (N)
(2) (2)
P and N are independent of x and defined in equations
55) and
56
Appendix D.4
The proof is presented in Appendix D.4 Because power iteration finds the eigenvalue with largest magnitude, we can use it to find m and M only when PSD and N is NSD. We solve for hy and bt. for sigmoid, tanh, softplus activation functions in Appendix B and show that this is in fact the case for them. Note that this result does not hold for ReI.U networks since the ReLU function not differentiable. However, in Appendix [ we devise method to compute the certificate for two
layer ReLU network by finding quadratic lower bound for z x2)))
4.3 CURVATURE BOUNDS FOR DEEP NETWORKS
sum product of matrices B and (L.1) Thus, if we can find upper bounds for [ and || [ we can get upper bounds for |V (1) Using this intuition (details presented in Appendix D.5p, have the following result:
Using Lemma 1
we know that v
(L)
Theorem 4. Given an L layer neural network whose activation function satifies:
1o' (x)l S la
(x)1 sh
Vx R,
the absolute value of eigenvalues of vZz is globally bounded by the following quantity:
V
$ Σ
(r))
max max (s(L.)) R
T-1
where (1) and ((L,)) are independent of and defined recursively as:
(1) |
,()) > (| S(L.1) =g ((LL)) [
T [e(2,
(6)
S(L.L-1) w
(7)
The above expressions allows for an efficient computation of the curvature bounds for deep networks.
We consider simplification of this result for sigmoid, tanh, softplus activations in Appendix
Note that bounds for (L) ->((2) (L) can be computed by replacing (!( with ( -w(") in Theorem
4
The resulting bound is independent of x, and only depends on network weights W the true
label y, and the target t. We denote it with K(W. y. t). To simplify notation, when no confusion
arises we denote it with K. In our experiments, for two layer networks, we use M, m from Theorem
(since it provides tighter curvature bounds). For deeper networks (L 2 2),, we use M K, m K.
ADVERSARIAL TRAINING WITH CURVATURE REGULARIZATION
Using Theorem 2 (b), know that if solve the curvature-based attack optimization and obtain
(attack) x ())] x (attack) is provably the closest adversarial example ()), However, when

---

Under review as a conference paper at ICLR 2020
Figure I: Kut and K are upper and lower curvature bounds of the network with Sig- moid activations (averaged over (y. 1) pairs). When 7 (no curvature regularization), networks adversarially trained with CRT or PGD both have high curvatures. However, CRT even with a small y leads to a signifi- cant decrease in curvature bounds (note the log-scale of y-axis). Similar results hold for networks with Tanh activations (Appendix Figure 2
uppnr an wit
Lower bound Mit with CIT
Bound of wan
Figerusiitan bouumds the
061
6.0
642
6.3
0.
0.05
Edo
0.77
Curvature Regularization coefticient,
we performed adversarial training (with p 0.5), we found that the curvature bound is loose and almost none of training inputs lead to zero primal-dual gap with p |x (attack) - () || To fix this
issue, regularizer that penalizes the curvature bound, K. Using equations (6 and 7 we
can compute K using absolute value, matrix multiplications, and operator norm (|/w())
[L]).
Since the gradient of operator norm does not exist in standard libraries, we created a new layer where the gradient of |W()], ie V Vwnn [WD]
|| is given by:
V Wo W T (v())²
u ()) satisfy ()) |/
This approach compute the gradient of the largest singular value of a matrix has also been used in previous ICLR work (Miyato et al. 2018). Implementation details are in Appendix C.I
Thus, the per-sample loss for training with curvature regularization is:
cross erosseentopy (x (0)), v) <K(,, 3,,, ()
where y is the true label of the input ("), is the target label and y is the regularizer for penalizing large curvatures. Similar to the adversarial training, in CRT, we use x (attack) instead of (())
6 EXPERIMENTS
The empirical robust accuracy means the fraction of test samples that were correctly classified after running an l2 bounded PGD attack (Madry al. 2018), the certified robust accuracy means the fraction of correctly classified test samples whose robustness certificates are greater than a pre- specified radius p. Unless otherwise specified, we use the class with the second largest logit as the attack target (i.e. the class f) and p 0.5. All experiments were on the MNIST dataset. The notation (L x [1024], activation) denotes a neural network with L layers with the specified activation, (y c) denotes standard training with 7 set to c, while (CRT, e) denotes CRT training with y Certificates are computed over 150 randomly chosen correctly classified images.
Comparison with existing certificates: In Table 3 we compare CRC with CROWN-general (Zhang
al. 2018a). For 2-layer networks, CRC outperforms CROWN significantly. For deeper networks, CRC works better only when the network is trained with curvature regularization. However, even with small y = 0.005, we see a significant increase in CRC but a very small drop in the test accuracy (without any adversarial training). We can see that with 7 0.01, non-trivial certified accuracies of 83. 33.53% 88.33%, 89.61% 61% can be achieved on 2, 3.4 layer sigmoid networks, respectively, with- out any adversarial training. Adversarial training using CRT further boosts certified accuracy to 95.59%, 94.99% and 93.41%, respectively. We observe similar results with Tanh networks in Ap- pendix Section G.2 We show some results on CIFAR-10 10 dataset in Table We again observe improvements in the robustness certificate and certified robust accuracy using CRC and CRT.
In Figure [ we plot the effect of 7 on the curvature upper bound Kus and a lower bound Kis of a 4-layer network with Sigmoid activations. Kis is computed by taking the maximum of the largest eigenvalue of the Hessian across all test images with label y and the second largest logit t, then averaging across different (y.t). Similarly, Kab is the mean of K over all pairs (y.t) (details in Appendix[G.. We observe that without any curvature regularization (when y = 0), both standard adversarial training with PGD well as the CRT lead to networks with high curvatures. However,
7

---

Under review as a conference paper at ICLR 2020
CRT with even small y leads to significant decrease in curvature bounds. Similar trends can be observed for networks with Tanh activations (Appendix Figure 2). Curvature bounds are higher for the Tanh networks compared to the Sigmoid ones due to having larger g and h parameters for Tanh in Theorem 4 Moreover, we report curvature bounds for networks with different depth in Appendix
Table T2 We observe that increasing depth increases curvature bounds.
Comparison with existing adversarial training methods: We compare CRT with adversarial training methods namely PGD (Madry al., 2018) and TRADES (Zhang al. 2019) in Table
We observe that none of the other methods give higher certified accuracy or robustness certificates than our proposed methods. We observe similar results with Tanh networks (Appendix Table 9
Moreover, in Appendix Table I0 we observe that CRT outperforms Randomized Smoothing (Cohen al. 2019) for 2 and layer networks. Since TRADES and Randomized Smoothing were designed for untargeted attacks while CRT is for targeted attacks, to have fair comparison, we modify the multi-class version the cross entropy loss with binary version (details in Appendix Section G.3
However, we emphasize that there is fundamental difference between our certificate (and CROWN) with the smoothing based method since our certificate is deterministic while the smoothing-bai certificate is probabilistic (with high probability).
We also compare against robust training technique proposed in Wong et al. (2018) in Table with with lp radius - 1.58. We note that the activation functions used in this comparison are different because the method proposed in Wong et al. (2018) uses ReLU while our proposed CRT can only work with fully differentiable activation functions such softplus, sigmoid, tanh. For CRT, we with softplus activation function with curvature regularization. We observe that for two and three layer networks, CRT gives higher certified robust accuracy compared to that of Wong et al.) (2018) while the difference between certified accuracy of the two approaches for a layer network is small (around 0.) We emphasize that to get good certified accuracy using our method, we need to add curvature regularization during the training. Otherwise, the curvature bounds and therefore the robustness certificates are loose.
network
Certified Robust Accuracy
Certificate
Time per image (seconds)
Standard Accuracy
Network
Training
(mean)
CROWN
CRC
CROWN
CRC
standard
98.37%
54.17%
0.28395
0.48500
0.1818
0.1911
2x[ 2x[1024]. sigmoid
7 = 0.005
97.96%
82.68%
0.36125
0.83367
0.1599
0.2229
7 = 0.01
98.08%
83.53%
0.32548
0.84719
0.1732
0.2186
CRT, 0.01
98.57%
95.59 %
0.43061
1.54673
0.1823
0.1910
standard
98.37%
0.00%
0.24644
0.06874
1.6356
0.5012
3x[ [[[_]. sigmoid
7 0.005
97.98%
88.66%
0.38030
0.99044
1.6220
0.5319
= 0.01
97.71% %
88.33%
0.39799
1.07842
1.6342
0.5295
CRT, 0.01
97.23%
94.99% %
0.39603
1.24100
1.5625
0.5013
standard
98.39%
0.00%
0.19501
0.00454
4.7814
0.8107
4x 4x[1024]. 0.005
97.74%
88.95%
0.36863
0.91840
5.1667
0.8567
sigmoid
0.01
97.41% %
89.61%
0.40620
1.05323
4.6296
0.8328
CRT, 0.01
97.83%
93.41 %
0.40327
1.06208
4.1830
0.8088
Table 3: Comparison between CROWNN-gneraal (Zhang al. 2018a) and CRC. Note that both CROWN and CRC are computed on CPU. However, running time numbers are not directly comparable because our CRC implementation uses batch of images while the CROWN implementation uses single image at time.
EXTENSIONS AND DISCUSSION
7.1 USING LOCAL INSTRAD OF GLOBAL CURVATURE BOUNDS
From Theorems I and we can observe that if the curvature locally bounded within convex region around the input, then the corresponding dual problems (dz d' d'stack)) are convex optimization problems inside this region. This leads to the following result:
8

---

Under review as a conference paper at ICLR 2020
Empirical Robust
Certified Robust
Certificate
Standard Accuracy
Network
Training
(mean)
Accuracy
Accuracy
CROWN
CRC
PGD
98.80%
96.26%
93.37%
0.37595
0.82702
2x 2x[1024]
TRADES
98.87%
96.76%
95. 15.1
0.41358
0.92300
sigmoid
CRT, 0.01
98.57%
96.28%
95.59%
0.43061
1.54673
PGD
98.84%
96.14%
0.00%
0.29632
0.07290
3x [x[4]]
TRADES
98.95%
96.79%
0.00%
0.30576
0.09 108
sigmoid
CRT, 0.01
98.23%
95.70%
94.99% %
0.39603
1.24100
PGD
98.84%
96.26%
0.00%
0.25444
0.00658
4x [x[12,
TRADES
98.76%
96.67%
0.00%
0.26128
0.00625
sigmoid
CRT, 0.01
97.83%
94.65%
93.41 %
0.40327
1.06208
Table 4: Comparison between CRT, PGD
(Madry et al.
2018) and TRADES
Zhang al. 2019)
Certified Robust Accuracy
Standard Accuracy
Network
Training
Certified Robust
Standard Accuracy
Network
2x 2x[10) softplus
Accuracy
CRT, 0.01
98.68%
69.79%
2x[1024] relu
89.33%
44.29%
CRT, 0.01
98.26%
14.21%
3x 3x[1024], softplus
CRT, 0.03
97.82%
50.72%
3x[1024].
relu 89.12%
44.21%
CRT, 0.05
97.43%
57.78%
CRT, 0.01
97.80%
6.25%
4x[1024), relu 90.17%
4x [x[4]. softplus
44.66%
CRT, 0.03
97.09%
29.64%
CRT, 0.05
96.33%
44.44%
Table 5: Comparison between CRT (left table) and Convex Outer Adversarial Polytope (right table) Wong et 2018 with attack radius p 1.58.
Empirical Robust
Certified Robust
Certificate (mean)
Standard Accuracy
Network
Training
Accuracy
Accuracy
CROWN
CRC
standard
46.23%
37.82%
14.10% 10%
0.37219
0.38173
2
[1024], sigmoid
= 0.01
45.42%
38.17%
26.50%
0.40540
0.55010
standard
48.57%
34.80%
0.00%
0.19127
0.01404
x [1024], sigmoid
0.01
50.31%
39.87%
18.28%
0.24778
0.37895
standard
46.04%
34.38%
0.00%
0. 0.19340
0.00191
4x [1024], sigmoid
0.01
48.28
40. 10%
21 21.07%
0.29654
0.40005
Table 6: Results for CIFAR-10 dataset (only curvature regularization, no CRT training)
Both Curvature-basel Certificate and Attack Optimizations are convex optimization problems within an la ball of radius p around the input sample where curvature values are bounded.
Corollary 1.
To use local curvature bounds, we need ensure that the gradient descent trajectory does not escape the local region where curvature values are bounded. To do this, we reduce the step size by factor of two until the trajectory lies inside the l2 ball of radius around the input point.
It is straightforward to that local bounds on curvature values can be tighter than global ones which can lead to better robustness certifications. In Table we show significant improvements for the CRC certificate and some improvements
the certified accuracy for two-layer sigmoid and tanh networks on the MNIST dataset. In this case, to compute local curvature bounds, we need to have a bound on hr, and hy (Theorem 3 within the ball of radius p around the input sample. These bounds can be

---

Under review as a conference paper at ICLR 2020
significantly tighter than the global bounds. For example, if sigmoid neuron's output is bounded by -0.4 and 0.6 (those bounds can be obtained efficiently using CROWN), the second derivative of sigmoid is bounded between -0.048 and +0.048, much better than the worst bound -0.09623 and +0.09623 used in current global curvature bound.
Certified Accuracy (Global)
Certified Accuracy (Local)
CRC
CRC
Network
Training
Certificate (Global)
Certificate (Local)
CRT, 0.0
95.04%
95.31%
1.0011
1.3901
2x [1024]. sigmoid
CRT, 0.01
95.59%
95.59%
1,5705
1.7262
CRT, 0.02
95.21% %%
95.21%
1.6720
1.7397
CRT, 0.0
92.69%
94.39%
0.8028
1.0511
2x 1024]. tanh
CRT, 0.01
95.00%
95.00%
1.4832
1.6068
CRT, 0.02
94.77%
94.77%
1.5848
1.6592
Table 7: Comparison between Certified Robust accuracy and CRC for 2 layer sigmoid and tanh networks using global and local curvature bounds
For deeper networks, however, computing local curvature bounds is more challenging. We leave exploring this direction for the future work.
7.2 EXTENSION TO CONVOLUTIONAL NEURAL NETWORKS
The formula derived in Lemma is valid even for convolutional neural networks. However, to use our methods, we need to bound the singular values of the Jacobian of the convolution operation. In order to do this, one use spectral bounds for convolution layers derived in Sedghi al. (2018). Furthermore, other heuristic techniques such as the one proposed in Miyato et al. (2018) can be used for the curvature regularization as well. We present some prelimiary results using these techniques for 2 layer convolutional networks on MNIST and CIFAR-10 Appendix Section G.I
CONCLUSION
In this paper, we develop computationally-effiie convex relaxations for robustness certification and ad attack problems given the classifier has bounded curvature. We also show that this convex relaxation tight under some general conditions. To be able to use proposed certification and attack convex optimizations, we derive global curvature bounds for deep networks with differentiable activation functions. This result is a consequence the Hessian of deep network. Our empirical results indicate that proposed curvature-biis based robustness certificate outperforms the CROWN certificate by an order of magnitude while being faster compute well. Furthermore, adversarial training using our attack method coupled with curvature regularization results in a significantly higher certified robust accuracy than the existing adversarial training methods. Scaling up our proposed curvature-based robustness certification and training methods as well as further tightening the derived curvature bounds are among interesting directions for the future work.
closed-form expression that we derived for
ACKNOWLEDGMENT
We thank the reviewers for their feedback and comments specially extensions of our results to characterize local curvature bounds.
REFERENCES
Cem Anil. James Lucas, and Roger B. Grosse. Sorting out lipschitz function approximation. In ICML., 2018.
10

---

Under review as a conference paper at ICLR 2020
Anish Athalye and Nicholas Carlini. On the robustness of the evpr 2018 white-box adversarial example defenses. ArXiv, abs/1804.032880 00046, 2018.
Anish Athalye, Nicholas Carlini, and David A. Wagner. Obfuscated gradients give false sense of security: Circumventing defenses to adversarial examples. In ICML, 2018.
Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, New York, NY, USA, 2004. ISBN 0521833787.
Rudy Bunel, liker Turkaslan, Philip H. S. Torr, Pushmeet Kohli, and Pawan Kumar Mudigonda. A unified view of piecewise linear neural network verification. In NeurIPS, 2017.
Xiaoyu Cao and Neil Zhenqiang Gong. Mitigating evasion attacks to deep neural networks via region-baset based classification. ArXiv, abs/1709.05583, 2017.
Nicholas Carlini and David Wagner. Adversarial examples are not easily detected: Bypassing ten detection methods. In Proceedings of the 10th ACM Workshop Artificial Intelligence and Security, AISec 17, pp. 3-14, New York, NY, USA, 2017. ACM. ISBN 978- 1-4503-5202-4, doi: 10.11455312255723144444 URL hRLLttt:///00 acm. org 10. 11w1/ 21w..011111111122.25532 314044
Nicholas Carlini, Guy Katz, Clark E. Barrett, and David L. Dill. Provably aonimally-distoree adversarial examples. 2017.
Chih-Hong Cheng. Georg Nührenberg, and Harald Ruess. Maximum resilience of artificial neural
networks. In ATVA, 2017.
Jeremy M. Cohen, Elan Rosenfeld, and J. Zico Kolter. Certified adversarial robustness via randomized smoothing. In ICML, 2019.
Francesco Croce, Maksym Andriushchenkoo, and Matthias Hein. Provable robustness of relu networks via maximization of linear regions. ArXiv, abs/ 810.07481, 2018.
Souradeep Dutta, Susmit Jha, Sriram Sankaranarayanan, and Ashish Tiwari. Output range analysis for deep feedforward neural networks. NFM, 2018.
Krishnamurthy Dvijotham, Sven Gowal, Robert Stanforth, Relja Arandjelovic, Brendan O' D'Donoghue, Jonathan Uesato, and Pushmeet Kohli. Training verified learners with learned verifiers. ArXiv, Abs/1805.10 10265, 2018a.
Krishnamurthy Dvijotham, Robert Stanforth, Sven Gowal, Timothy A. Mann, and Pushmeet Kohli. A dual approach to scalable verification of deep networks. In UAI, 2018b.
Rüdiger Ehlers. Formal verification of piece-wise linear feed-forward neural networks. ArXiv, abs/1705.01320, 2017.
Matteo Fischetti and Jason Jo. Deep neural networks and mixed integer linear optimization. Con- straints, 23:296-309, 2018.
Timon Gehr, Matthew Mirman, Dana Drachsler-Cohen Petar Tsankov, Swarat Chaudhuri, and Martin T. Vechev. Ai2: Safety and robustness certification of neural networks with abstract interpretation. 2018 IEEE Symposium on Security and Privacy (SP), pp. 3-18, 2018.
Sven Gowal, Krishnamurthy Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Uesato, Relja Arandjelovic, Timothy A. Mann, and Pushmeet Kohli. On the effectiveness of interval bound propagation for training verifiably robust models. ArXiv, abs/1810.12715, 2018.
Matthias Hein and Maksym Andriushchenko. Formal guarantees on the robustness of a classifier against adversarial manipulation. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan. and R. Gamett (eds.), Advances in Neural Information Processing Systems 30, pp. 2266-226777 2017.
Xiaowei Huang, Marta Z. Kwiatkowska, Sen Wang, and Min Wu. Safety verification deep neural networks. ArXiv, abs/1 610.06940, 2016.
11

---

Under review as a conference paper at ICLR 2020
Guy Katz, Clark W. Barrett, David L. Dill, Kyle Julian, and Mykel J. Kochenderfer. Reluplex: An efficient smt solver for verifying deep neural networks. In CAV, 2017.
Alexey Kurakin, Ian J. Goodfellow, and Samy Bengio. Adversarial examples in the physical world. ArXiv, abs//660.00233, 201
Alexey Kurakin, Ian J. Goodfellow, and Samy Bengio. Adversarial machine learning at scale, ArXiv, abs/1611.01236 2016b.
Mathias Lécuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and S. K. K. Jana. Certified robustness to adversarial examples with differential privacy. In /EEE S&P 2019, 2018.
Bai Han Li. Changyou Chen, Wenlin Wang, and Lawrence Carin. Certified adversarial robustness with additive gaussian noise. 2018.
Xuanqing Liu, Minhao Cheng, Huan Zhang, and Cho-Jui Hsieh. Towards robust neural networks via random self-ensemble. ArXiv, abs/1712.00675. 2017.
Alessio Lomuscio and Lalit Maganti. An approach reachability analysis for feed-forward relu neural networks. ArXiv, abs/ 706.07351, 2017.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. To- wards deep learning models resistant adversarial attacks. In International Conference on Learn- ing Representations, 2018. URL
net/ forum 1d=rInIIIIIA
Matthew Mirman, Timon Gehr, and Martin T. Vechev. Differentiable abstract interpretation for provably robust neural networks. ICML, 2018.
Takeru Miyato, Shin ichi Maeda, Masanori Koyama, and Shin Ishii. Virtual adversarial training: A regularization method for supervised and semi-supervised learning. IEEE Transactions on Pattern Analysis and Machine Intelligence, 41:1979-1999, 2017.
Takeru Miyato, Toshiki Kataoka, Masanori Koyama, and Yuichi Yoshida. Spectral normalization for generative adversarial networks. International Conference on Learning Representations, 2018.
URL httptttss///peeeeeeeeeet/ net. forum? (ewoormmid-iBlgggeeeee
Seyed Mohsen Moosavi Dezfooli, Alhussein Fawzi, Jonathan Uesato, and Pascal Frossard. Robustness via curvature regularization, and vice versa. In The IEEE Conference on Computer Vision and Puttern Recognition (CVPR), 2019.
N. Papernot, P. McDaniel, X. Wu, S. Jha, and A. Swami. Distillation as a defense to adversarial perturbations against deep neural networks. In 2016 IEEE Symposium on Security and Privacy (SP), pp. 582-597, May 2016. doi: 10. 19.1...........1
Nicolas Papernot, Patrick D. McDaniel, Ian J. Goodfellow, Somesh Jha, Z. Berkay Celik, and Ananthram Swami. Practical black-box attacks against deep learning systems using adversarial examples. CoRR, abs/ abs/1602.00697, 2016. URL httpp:://axxii.oo//ab///////////
02697
Jonathan Peck, Joris Roels, Bart Goossens, and Yvan Saeys. Lower bounds on the robustness to adversarial perturbations. In NIPS, 2017.
Chongli Qin, James Martens, Sven Gowal, Dilip Krishnan, Alhussein Fawzi, Soham De, Robert Stanforth, and Pushmeet Kohli. Adversarial robustness through local linearization. arXiv preprint arXiv:1907.026100 2019.
Aditi Raghunathan, Jacob Steinhardt, and Percy Liang. Certified defenses against adversarial examples. ArXiv, abs/1801.09344, 2018a.
Aditi Raghunathan, Jacob Steinhardt, and Percy Liang. Semidefinite relaxations for certifying robustness to adversarial examples. In NeurIPS, 2018b.
Hadi Salman, Greg Yang, Jerry Li, Pengchuan Zhang, Huan Zhang, Ilya P. Razenshteyn, and Sébastien Bubeck. Provably robust deep learning via adversarially trained smoothed classifiers. ArXiv, abs/1 990640454, 2019.
12

---

Under review as a conference paper at ICLR 2020
Pouya Samangouei, Maya Kabkab, and Rama Chellappa. Erfense-GANi Protecting classifiers against adversarial attacks using generative models. In International Conference on Learning Representations, 2018.
Hanie Sedghi, Vineet Gupta, and Philip M Long. The singular values of convolutional layers. arXiv preprint arXiv: 10408, 2018.
Gagandeep Singh, Timon Gehr, Matthew Mirman, Markus Püichel, and Martin T. Vechev. Fast and effective robustness certification. NewrIPS, 2018.
Sahil Singla, Eric Wallace, Shi Feng, and Soheil Feizi. Understanding impacts of high-order loss approximations and features in deep learning interpretation. In ICML, 2019.
Christian Szegedy, Wojeiech Zaremba, llya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In International Conference on Learning Representations, 2014. URL (ttp::// / //rxivv org/ abs 1312. 6199
Jonathan Uesato, Brendan O' O'Donoguue, Pushmeet Kohli, and Aäron van den Oord. Adversarial risk and the dangers of evaluating against weak attacks. In ICMI. 2018.
Shiqi Wang, Yizheng Chen, Ahmed Abdou, and S. K. K. Jana. Mixtrain: Scalable training of verifiably robust neural networks. 2018a.
Shiqi Wang, Kexin Pei, Justin Whitehouse, Junfeng Yang, and S. K. K. Jana. Efficient formal safety analysis of neural networks. In NeurlPS, 2018b.
Tsui-Wei Weng. Huan Zhang, Hongge Chen, Zhao Song, Cho-Jui Hsieh, Duane Boning, Inderjit Dhillon, and Luca Daniel. Towards fast computation of certified robustness for relu networks. ArXiv, abs/1804.09699) 2018.
Eric Wong and Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. ArXiv, abs/1711 1.00851, 2017.
Eric Wong, Frank R. Schmidt, Jan Hendrik Metzen, and J. Zico Kolter. Scaling provable adversarial defenses. In NewrIPS, 2018
Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric P. Xing. Laurent El Ghaoui, and Michael I. Jordan. Theoretically principled trade-off between robustness and accuracy. In ICML, 2019.
Huan Zhang, Tei Weng, Pin-Ye Yu Chen, Cho-Jui Hsieh, and Luca Daniel. Efficient neural network robustness certification with general activation functions. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Biam Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems 31, pp. 4939 4948. Curran Associates, Inc., 2018a.
Huan Zhang, Tsui-Wet Weng, Pin-Yu Chen, Cho-Jui Hsieh, and Luca Daniel. Efficient neural network robustness certification with general activation functions. ArXiv, abs/ 181 1.00666, 2018b.
Huan Zhang, Pengchuan Zhang, and Cho-Jui Hsieh. Recurjac: An efficient recursive algorithm for bounding jacobian matrix of neural networks and its applications. AAAI, 2018c.
Stephan Zheng, Yang Song, Thomas Leung, and lan J. Goodfellow. Improving the robustness of deep neural networks via stability training. 2016 IEEE Conference Computer Vision and Pattern Recognition (CVPR), pp.
2016.
13

---

Under review as a conference paper at ICLR 2020
Appendix
A
RELATED WORK
Many defenses have been proposed to make neural networks robust against adversarial examples. These methods be classified into empirical defenses which empirically seem to be robust against known adversarial attacks, and certified defenses, which are provably robust against such attacks.
Empirical defenses The best known empirical defense is adversarial training (Kurakin et al.) [016b] Madry et al. 2018 Zhang et al., 2019). In this method, a neural network is trained to minimize the worst-case loss over region around the input. Although such defenses seem to work existing attacks, there is no guarantee that a more powerful attack would not break them. In fact, most such defenses proposed in the literature were later broken by stronger attacks (Athalye et al.) 2018 Carlini & Wagner 2017: Uesato et al. 2018 Athalye & Carlini 2018). To end this arms race between defenses and attacks, number of works have tried to focus on certified defenses that have formal robustness guarantees.
Certified defenses A classifier is said be certifiably robust one can easily obtain a guarantee that classifier's prediction remains constant within some region around the input. Such defenses typically rely on certification methods which are either exact or conservative. Exact methods report whether or not there exists adversarial perturbation inside some ip norm ball. In contrast, conservative methods either certify that no adversarial perturbation exists or decline to make a certification; they may decline even when such perturbation exists. Exact methods are usually based on Satisfiability
Modulo Theories (Huang et al.] 2016]] Katz et (017,211] (Eblers [017]] |Carlini et al.] (017)) and Mixed 2017|Carlini
Integer linear programming (Cheng et al. 2017 Lomuscio & Maganti 2017; Dutta et al. 2018
Fischetti & Jo 2018: [unell et al.] 2017). Unfortunately, they are computationally inefficient and
difficult scale up to even moderately sized neural networks. In contrast, conservative methods
more scalable and efficient which makes them useful for building certified defenses (Wang et al.
2018a /Wong& & Kolter 2017 [Wang et al., 20186; Wong et al.) 2018 Raghunathan
al.||20181) a Dvijotham et al. 2018a bj Croce et al. [2018] [Singh et al. 2018 Gowal et al. [20 Gehr et al. 2018 Mirman et al.j [0188] Zhang al.) 201 Weng et al. 2018). However, even these methods have not been shown to scale to practical networks that are large and expressive enough to perform well on ImageNet, for example. To scale to such large networks, randomized smoothing has been proposed as probubilistically certified defense.
Randomized smoothing Randomized smoothing was previously proposed by several works (Liu et al. 2017: Cao & Gong 2017) as a empirical defense without any formal guarantees. Lécuyer
ct al. (2018) first proved robustness guarantees for randomized smoothing classifier using inequalities from differential privacy. [Li et al. (2018) improved upon the same using tools from information theory. Recently, Cochnnly,CCohen et al. (201)) provided a even tighter robustness guarantee for randomized smoothing. [Salman et al. (2019) proposed method of adversarial training for the randomized smoothing classifier giving state of the art results in the la norm metric.
B THE ATTACK PROBLEM
For a given input x (0) with true label y and attack target I, consider the attack problem. We are given that the eigenvalues of the Hessian v2 (L)
{22 2.²² are bounded below i.e:
ml < 2 (2) 2
Vx e RD
(L) Here m < (since 2. x (L) is not convex in general).
The goal here is to find an adversarial example inside la ball of radius p such that (2 - (112) is minimized. That is, we want to solve the following optimization:
(2)0) 2t 2 (x))
(2.²) - 2 2 (x) + " (|x 1|x-x<01== 12 p²))
(2(0)22)
Pattack
min
= min max v20
|x-x(0) 150
2
14

---

Under review as a conference paper at ICLR 2020
This optimization can be hard in general. Using the max-min inequality (primal dual), have:
Pattack 2 max dattack (T),, dattack (1) min (()) (x)
! (1x [x-x(00) -00))=pp))
0²) (9)
We know that for every 1) O, dattack()) (1) gives lower bound to the primal solution Partack- But solving dattack-(1) (7) for any 7j 2 can be hard unless the objective convex. We prove that the eigenvalues of the Hessian bounded below i.e:
mI $ V2 2 (L) Zz (
Vx RD
In general O. since (z -z (m)) is non-convex.
dattack (1) is convex optimization problem for -m & 1,. Equivalently the objective function, i.e the function inside the minx:
( (2)0) (0) 11= -00))=)---p)))))
-
is convex function in for $ n
The Hessian of the above function is given by:
V 1 zi ( + +n1
(I) Since we know that eigenvalues ( y 2 (1) = mI, we know that eigenvalues of the above Hessian are v) m. For v -m, the eigenvalues positive implying that the objective function is convex.
Since dattack (1) gives a lower bound to Pattack for every 17 get the following result:
Pattuck 2 dottack where dattock- = max diastack(())
(10)
-msn
by the definition of Note that if x (attack) is the solution to dattack such that: (attack)) x0)
d' dattackk
d'sttckk (2/0)22, -2(-)( (.4)) (x (attack))
But then by the definition of Pattack: Pattack S d dattacko implying that the duality gap is zero, i.e
Pattack de dattack- This procedure leads the theorem
C IMPLEMENTATION DETAILS
C. COMPUTING THE DERIVATIVE OF LARGEST SINGULAR VALUE
Our objective is to compute derivative of the largest singular value, i.e |W(]] with respect to W(1)
u ( (!) are the singular vectors such that:
(1) (1) (w(')
v0) [2 can be computed by running power iteration (W(D) W()) ( can be computed using the identity:
(1) w()(()
7(1)
We 25 iterations of the power method to compute the above quantities.
C.2 UPDATE EQUATION FOR THE CERTIFICATE PROBLEM
Our goal to minimize |x - x such that (2 (x) = O. know that the Hessian satisfies the following LMIs:
mI v2 (2(()) z (1)) $ MI
(11)
15

---

Under review as a conference paper at ICLR 2020
K' is given by Theorem 4 for neural network of any depth (L 2 2). For 2 layer networks, M and m are given by Theorem 3 But for deeper networks (L 2 3), K, m = -K. either case,
K 2 max([m), [M]) Thus, we also have:
KI
V by
(111) KI
(12)
We will solve the dual (dhere) of the attack problem (Poert). The primal problem (Peert) is given by:
| x01
-
101
z (1)) x(0))(x))
Peert
min (1) (x))=x (2) (xx
min max "
2
Using inequality ITI and Theorem part (a), we know that the dual of the above problem convex when - < 1/mm
The corresponding dual problem (deert) is given by:
Aceri(1) min 1 2 x x01 (2 2, 20 (x)())) (x)
d'orrt max (1), -1/Mssps-1/m
For given 7, we have the following optimization:
dnerc(1) = min |x - + -x))
(x))) (x)
We will use majorization-miniiizzni At a point x (*)), we aim to solve for the point (k++1) that decreases the objective function. Using the Taylor's theorem at point (k), we have:
to solve this optimization.
(x(4)) 2 (x)
= =(2//) zi 21")) (x)
(x- (1)x (x-x")((xxx"""
1 (x x())
T ((9) (x (x)
+
where g (() is the gradient of connecting x and (k))
(zlg (L) 21 ( at (k) and ((9) is the Hessian at a point & on the line
Multiplying both sides by n, get the following equation:
" (L) 21 (.11) (x))) (x)
1) ( (111 (x())) (g( (x (+)) (x (()) H(5) (x-x(t))
(13)
Using incquality 12 we know that KI H(t) KI VE
S |n
(x )²) ( x (k)
|x - x (1)
(14)
Using equation (3) and inequality 14
7 (2 2 (x) 17 2 2
(L) (L) (x) + )² (x) + InK]
2 x xx-x(1)) (8)
Adding 1/2/ x0) to both sides, we get the following inequality:
1
|xx - 10 1² + (z( 21 (x) (x)
2
$ $ | - (0) + n (22
2. (x)()xxx) (x) +n (g( (x-x
|n|]
(+)]
LHS is the objective function of deere (n) and RHS is an upper bound. In conoiizatioomminiizatttei we minimize an upper bound the objective function. Thus we set the gradient of RHS with respect to x to zero and solve for x:
x- x- + + (2(2))) 21 = (x(())) (g( (x-x(() + |nK]
|x x (1)
|
x
=
2
16

---

Under review as a conference paper at ICLR 2020
x x-x x-x(") ng! +/nK] (x x x1)) =0
(1 + [ xx + 1788 (k) || x(()=
x= -1 ===(1</n)]>- (n)
|,7 k {)]|((()) -x(0))
This gives the following iterative equation:
( = =-11 (1+|)/]])+ (1g (k) [x) - -1 (0))
(15)
C.3 UPDATE EQUATION FOR THE ATTACK PROBLEM
Our goal is minimize (1) -z
(1) within an la ball of radius of p. We know that the Hessian satisfies
the following LMIs:
ml < VZ (2
-2 -z(4)-2,,
-2, (1)
$ MI
(16)
K is given by Theorem 4 for neural network of any depth (L 2 2). For 2 layer networks, M and m are given by Theorem 3 But for deeper networks (L 2 3), M = K, m K., In either case, K 2 max((m],||M) Thus, we also have:
KI VZ (
(4) KI
(17)
We solve the dual (dattock) of the attack problem (Pattack) for the given radius p.
The primal problem (Pattack) is given by:
2, min max 420
( 11)- 2, 21,0+ 1/ 11x
Pattack
min 2
[x-
Sp
Using inequality when -m n).
16 and Theorem
2 part (a), we know that the dual of the above problem is convex
The corresponding dual problem (d'ere) is given by:
max dattack (1)) dattack (11) min (2 21 (x) 7 2/5 x012 -1²) -1²)
dh dottack -m
For given 7, we have the following optimization:
dattack (1) min (z/.4) -0())=(()) (1) (x) (1x p²²)
We will use majorizaton-mmiiiiizaoon
minimization to solve this optimization.
At a point x( (k), we have solve for the point (k+1) that decreases the objective function. Using the Taylor's theorem at point (k), we have:
-x) zi (x(())))))))))))))))))))))))))
1 (x - (1))"" H(S) (x (()) (xx11) + (t)) (x-x(x)) +
(18)
where g (8)) is the gradient of (z. (11)) at (k) and (()) is the Hessian at a point & on the line
connecting x and (4).
Using inequality
17
we know that - KI (() KI VEERD,
1 1 (x - ( (()) (x x (b)
s 2 xx- xx)
K
(19)
Using equation (8) and inequality
(L) 2 (1)) (x) s (2 (1) (1) (x())) (g) (x - (x-x
K
x x
2
17

---

Under review as a conference paper at ICLR 2020
Adding n/2([1x 12 p²) to both sides, get the following inequality:
(z -2,0 (x) 2/2 100x
$ (z - (4) (x( + (B!())" (x (1))
K x (+ ?
(1x-x(00)
LHS is the objective function of dattack (17) and RHS is an upper bound. In pntiioriaatio-mmiimiiaalt we minimize an upper bound on the objective function. Thus we set the gradient of RHS with respect x to zero and solve for x:
Vx
(L) - zi ( (x(1) + (B( (x- xx))
K +
x x
(b))
+ 2
||x
x x001
-p²) =
]²)]=
2
(+)) K (x- x(())) + +1 (x xx--x09 =0
(K + 1)) x+ g (k) <x (0)
x = - (K+ [g (k) Kx (1) (1)
This gives the following iterative equation:
(k+1) - n) (g( (g Kx(() (0)
(20)
C.4 ALGORITHM TO COMPUTE THE CERTIFICATE
We start with the following initial values of x, 1/s Qmin, Mmax:
7mmn -1/M,
Tmaz = -1 -1/m
1 2 Mmin (max)) )
x x()
To solve the dual for given value of run 20 iterations of the following update (derived in Appendix C.2):
=-(+)=-(11(1]))) (ng(() 11///x -x))
To maximize the dual doer:()) over in the range [- 1-1/M, 11/m], we use a bisection method: If the
solution for given value of 77, (z.()) (2(())=2) -()-- (x) > 0, set Tmmi 77, else set Mmar 17. Set the new (1min + 2/2 and repeat. The maximum number of updates to are set to 30. The routine to
compute the certificate example given in Algorithm
C.5 ALGORITHM TO COMPUTE THE ATTACK
We start with the following initial values of x, 17, Amnnn Amax=
Umin -m, Umax 20(1-1))
n
(mmin + Mmaa))
x= x0)
To solve the dual for given value of 17, 20 iterations of the following update (derived in Appendix C.3
(k+1)= = -(K (k) (x (0)
To maximize the dual (Tere(T) over 7j in the range [-m, 20 - m. we use bisection method: If the solution x for given value of n7 xx x()] S p, set 7max 77, else set Mmin 1). Set new 77= (7min + 7/2 and repeat. The maximum number of updates to are set to 30. The routine to compute the attack example is given in Algorithm 2
18

---

Under review as a conference paper at ICLR 2020
Algorithm I Certificate optimization
Require: input x label y, target I
M, K + compute.boundds(e
(L) (Z)) (
Mmin + -1/M
mmax -1/m
1/2(7mmn + Tmnax)
X x())
for i in [].... 30] do
for j in [l.... 20] do
g comppteemgreeeeeeccce graniettgrdiinntt (1) 2,,,, x)
if ng (x (x-x(()) 10- then
break
end if
x +- -11 |n (1g 1 |/| (0)
end for
if (zy (1)
(1) (x) 0 then
Mmin +
else
Umaa + 11 end if
<- (Jmmn + "mmmx)) 1/2
end for return X
Algorithm 2 Attack optimization
Require: input ("), label y, target t. radius m, M, K hotputseebbuds(zz_ (1) z ())
Amin
Tmme 20(11 m)
1/2(Tmmn 7mma
(0)
for i [1,.... 30] do
for in [1...., 20] do
g + compute gradient(z)) by (1)) x)
if flg+mo + (x+n(x-x00 break
10 then
end if
x (K + n7) (g Kx ())
end for
if X
(0) < p then
Imax 17
else
7min 1)
end if
17 (Jmin Mpmaz) 1/2
end for return
19

---

Under review as a conference paper at ICLR 2020
D PROOFS
D.1 PROOF OF THROREM 1
1
x x x01 (x)) 2 (1(x)))
deere min
2
x x01
1/2 (x) 2 (x)()) =1+ v (2 )
We are given that the Hessian (2(2 4
(b) (L)
satisfies the following LMIs:
mI v2 2/ zi
(L)
MI
Vx R"
The eigenvalues of of (2) 21 (1)) are bounded between:
(1 n,M 7mm), if <
(1 + 1pm 1 + M), if O
We are given that satisfies the following inequalities where m < 0, M > 0 since (zy
z (4) is neither convex, concave as function of x:
-1
S 7
m < 0, 0
M
m
We have the following inequalities:
1+ M 2 0, 1 + 7mm 2 0
Thus, I (z 2 21()) is PSD matrix for all e RD when -1/M SnS -1/m.
Thus x/2/x- x 12 +n( (L) 24 ( (x) is convex function in x and deere (1) a convex
optimization problem.
(b) For every value of 11, deert (n) is lower bound for Poert- max_ 1/Ms s-1/m deert( is lower bound for Pierts i.::
Thus d'eert
d'err $ Poert
(21)
Let 1/ (nent) (ertt) the solution of the above dual optimization (dieri) such that
2 (x((or)))
(x
(22)
de is given by the following:
d'err
1
x0)) 1/ (cort) (x(cor)) (10 (x((con))) x (cert)
2
-0
Since we are given that z (0) (x(cce))) = (L) (xe(oort)), we get the following equation for
d'ertt
&eet 5 [ - (1
(23)
Since Foert is given by the following equation:
1 ||x - ||x-xx011
Peent
min
(24)
(1) (x)=a
(x)
Using equations 22 and
24 Poent is the minimum value of 1/2||x x20) Vx
(x): 2. (x) 2 (L)
Peert S 2 (
1 [11x(0or)) (12
(25)
From equation
23 we know that diert = 1/2(x(cerr) x0)
Thus, we get:
Pirrrt dhart
(26)
Using equation we have disrt $ Poers and using 26 Peert & diert
Voent doers
20

---

Under review as a conference paper at ICLR 2020
D.2
PROOF OF THEOREM 2
(a)
Battack (1)) = minn (2 2 20 (x) 7 (1x - s²)
2
V2 (1) -z (1)) (x) ! x x 22 (1) (2)))) 2 + n
Since the Hessian V (L) (2 -ht (L)) is bounded below:
mI < V2 (z()) -,,") Vx R
The eigenvalues of V (z)
(1)
z (T)) 1jI are bounded below:
(m + n)) < V (z) zi (1)) nI
Since 17 mm.
+ m2
Thus (z zy - 2, (1) 7 is PSD matrix for all x e RD when -m.
(T)
Thus (2g (L) 24 (x) + n//2[[x 102 p²²) a convex function x and dattack (11)
convex optimization problem.
(b) For every value of 7). dattack()) is lower bound for Pattack Thus dattackk
max-msn dottack (1)) is a lower bound for Pattuck'
L'ttack $ Pattock
(27)
Let (aattack) (attack) be the solution of the above dual optimization (d such that
x (attack)
-x(0)|=
(28)
dattack is given by the following:
dattack (z) (10)) (x(aatant)) fattacck)
( - xx00)²² -p²
2
Since we are given that ||x
[ (attack) x00 p. we get the following equation for d' dattackk
Fattack
22y 21 (xlataack)
(L)
(29)
Since Pattack is given by the following equation:
(2(0)-2)0 2-2 (x)
Pattack
min |x-x(0)|s sp
(30)
Using equations
28
and
30
Pattack is the minimum value of (z,))
(L)
x (x)
V
x
x (0)
S
pz
(2..)) 2 2(00) (x((ttack))
Pattack
(31)
From equation
29 know that d' d'sttack (2 2i
(L) (L) (x(attack)) Thus, we get:
Pattack S disttack
(32)
Using equation
27 have d attackk Pattack and using 32 Pattack d dattack
Pattack d= dattock
21

---

Under review as a conference paper at ICLR 2020
D.3 PROOF OF LEMMA
We have to prove that for an L layer neural network, the hessian of the 8th hidden unit in the th layer with respect to the input x, ie V22, (1) is given by the following formula:
(B())" diag F!L.D oo (2 )BC
(4) V 4
Σ
(33)
where B E [L] is matrix of size N, defined as follows:
B [Eze
(1) ..... VxaN (1) "
( Vxzl
IE [L]
(34)
and F(L.)) I [L- 1] is a matrix of size NL x N₁ defined as follows:
F(I.)) Vacnz(") (1) Va(nz (1)
(1)
I [E[L-1] 1]
(35)
No.
V22 (L) can be written in terms of the activations of the previous layer using the following formula:
NI-1
(L) Σ in
(36)
Using the chain rule of the Hessian and (1) (1) we can write (-1)
(L-1)
terms of Vxa
and V222(-11 (L-1) as the following:
(L-1) = o" (z)
(1111))
Vx22 (1-1))
(vxz
- + +o (2) (222) (-1)
(37)
Replacing (L-1)
using equation 337 into equation 36
we get:
N Σ
(1) =
( (1-1)) V (2
(z22f-111 +o (z) (F
i.j
NL.1
Vi2
(L)
w
(L)
(z) (2))-11) (x22(-111 (Txz
in
j-1
No
w(() o ( (
(38)
For each E [2, LJ, ie Nr. we define the matrix A as the following:
2 (1) = Σ wlO
N1-1
0 "
(2) (V=25(-1)
No
Σ woO (z) (222(111)
(2)--1)
(,
AnD
(39)
A
N1-1 "
Σ (!! o (z) (1)"")) (F=")(( (Zxz)(-11) (Vx
(40)
Substituting (4 using equation (40) into equation
38 we get:
v2 (2(0)) A
(2) (1) (v22(1))))11 (V2251-1)
(41)
We first simplify the expression for A (L), Note that A (L) is sum of symmetric rank one matrices
(vx2 (v)2 with the coefficient Wi (z) (2((-1) for each j. We create diagonal
22

---

Under review as a conference paper at ICLR 2020
matrix for the coefficients and another matrix B(L-1) such that each 9th row of B(L-1) is the vector Vx (L-1) This leads to the following equation:
NE-1 A E W (L) (2)--1) (x22((111) (Vx2((-1))
(B((-1))² diag (w( oo¹ (z(-))) B(L-1)
(42)
B() where I [ is a matrix of size Nj x D defined as follows:
(1) Vx22 (1) B()) = Vx21
Vx (1)
[
Thus B()) is the jacobian of 21 with respect the input x. Using the chain rule of the gradient, have the following properties of B();
((1) -(())
(43)
B w diag (o (
(44)
Similarly, F(I.)) where I [L], J [1 1] matrix of size N, N, defined as follows:
p(l,.) V Vacusza v (2.2)
(1) V
(
Nr
Thus ((...) is the jacobian of (d) with respect to the activations (!) Using the chain rule of the gradient, we have the following properties for F(L.));
((LLL1) W(L)
(45)
F(..)= (T.)) diag (o (z((1-))) p(
(46)
Recall that in our notation: For a matrix E, E, denotes the column vector constructed by taking the transpose of the ith row of the matrix E. Thus 7th row of W(L) is (w!")) 7 and F(L.)) is
(F(L.))" Equating the 4th rows in equation 446 we get:
(D!K
(w!") ding (o (2(1-1))) F(L-1.1)
Taking the transpose of both the sides and expressing the RHS as a summation, we get:
F(L.D = ((W!")" diag (o' (z(1-1)) p(b-I.1)
N wly' o' (z) (2((-11) ) F((-1.1)
Σ
(47)
Substituting (L)) using equation 45 into equation
get:
(4) = (B(--))² diag F (L,,L-1) oo" (2(4-1) B(L-1)
(48)
Substituting A A( using equation 48 into we get:
(L)
(4)
(B(1-))² diag 1 od" 00"(6'"""" (z)1))) B(1-1)
NE.1
Σ
iij o' (2) (V22(1111 (1-1)
(49)
Thus, equation 44 allows us to write the hessian of hth unit at layer I, i. (1 in terms of the
hessian of jth unit at layer L- 1, i. (1-). We will prove the following using induction:
L-1
V V22 (L)
Σ (B())" diag (F(L.)) oo" ((2(1) B())
(50)
23

---

Under review as a conference paper at ICLR 2020
Note that for L= 2, V22g 12221-1) 0, Vje Ni. Thus using (49) we have:
(1-1)
V 2) = (B())² diag (F(2.)) oo (2()) B())
Hence the induction hypothesis (50) is true for L = 22
Now we will assume (50) is true for L 1. Thus we have:
(BUT)* ding (D(L-111) oo (x47) B
VjeN
(51)
We will prove the same for L. Using equation (49). we have:
V22 (1)
(B(I))) T diag (F! o00 (z(1-1))) B((-))
No-1
Σ w! (z) (V22, (-11
j-1
In the next set of steps, we will be working with the second term of the above equation, i.c Eer iif o' (z) (V?2) (1-1))
Substituting V22g (L-1)
using equation we get:
T V22 (b) = (B(I-1))² diag (F!
(L,L))) ood (z B(t-1)
(z(-1)))B((T-))
NI-1 w
(1) o (z, 1)
(B()) diag (F) oo (=(7)) (B())))
Combining the two summations in the second term, we get:
32 (L)
(B(--))² ding (F((..-1) oo (2( B(b-1)
Σ w u a' (2) (B())² diag (F (((1-111)) oo" (z()))
Exchanging the summation over I and summation over j: T
V22 (4) = (BB"--)" diag (F((,)-1) oo" (z( B(l-1)
L- W (z)--1) (B")² ding ( oo" (x(")) B
Since (1) independent j. j. we take it out of the summation over j:
V&z (L) = (B((-1))) diag (((,L-1) oo" (2(411)) B(L-1)
L-2 T
(B")) Σ w (0) (11 diag (F
oo oo ())))) B )BO)
Using the property, a (d)ag(u)) 3 (diag(v) ding (au+ Bv) Va, E R, R"; we can move the summation inside the diagonal:
222 (L) =(B(L-1)"
o diag
(F(L ((LL-1))
oo (2( B((-))
N
oo why (z((-1)) (f(--1i)) " (2 JBU
Σ
(B diag
Σ
Since σ" ((221)) is independent of j. take it out of the summation over j:
222
(L) =(B(I-1)) T diag
FF (L,L-1) oa" " (z)) ((l-1)
Ni-1 wl (z) (2(--1)) x
F((-1.1)) o0 1 (2(2)) B
Σ (B())² diag
24

---

Under review as a conference paper at ICLR 2020
Using equation 47). we can replace Σn-1" w! o' (z) (2)()-11) ) p((-1.)) with F (!...:
V22 (1) (B(L-1)) )" diag FF (1.I--) oo (2(())))) B(L-1)
(BU))* x diag ((L.)) o (2(1) B
Vラ2!10 (4)
Σ (B())* T diag (((L.)) od " B())
1=1
D.4 PROOF OF THEOREM 3
Using Lemma we have the following formula for V2 (n.)) - r.²)):
V 2 (20) = (w-(W))) diag (W!?) (o?))-((3"))
w(")) oo (2 w() )
(w 3. w o" (2. w (w!!""
(52)
We are also given that the activation function o satisfies the following property:
hy S a (z) s he V
(53)
(a) We have to prove the following linear matrix inequalities (LMIs):
N v 2
(2)
22)
x PP
VXER
(54)
where P and N are given as following:
N
(w(2)-
t.3 W( (W!")?
P
=
Ps
(55)
Ni
(w(2)-
w!?) w( (w(")²" T
N
n2
(56)
(hu,
w(2)
w 20
n1 hh
w(2) w 0
P
W(3)
w
w 2.z
w
(57)
hL
o, $0
50
81
u.s
1,
We first prove: N < 22 (2) (2)
by =
Vx e RD:
We substitute
42
2/ - 2, and N from equations
(2)
(2)
52 and
56
respectively in
V2
(2)²)
2,
(2)
N:
2 2 z,
(2) N
N.
(w(2)- - ww 0- (2(10) (())-(W()) -ww!) 0.1
-w!?) ni w! ) (w!O)) w((2) t. ) (o" (24)) -n:) w!"" (w!")" 7
(w(2) y.i
Thus v (2) (2) N is a weighted sum of symmetric rank one matrices i.e,
23 2
w!!') (W(1)) T and it PSD if and only if coefficient of each rank one matrix i.e,
(wle) w(2)) (o" " (2 (2))) n: is positive. Using equations 53 and 57 we have
25

---

Under review as a conference paper at ICLR 2020
the following:
(w/ w(()) 4,2 20 = ni hr. =
0 2i 11 00
1
Vie [Ni], Vx RD
(w(3)-
(.())) 50- = n2 = hy = (o" " 2 73 00
(1)
vie [Ni]. Vx RR
8,1
t,e
(wll) w(!)) (o" " (z.
(1) ) n4 20 0
Vie [N1], V RD
(58)
Thus V2 (/4 z
(2)
N is a PSD matrix i.e:
V2 2/ =zz ) N
(2) (2)
N,
W ui w w
(0)) (2')
n4) w! (w!"))² T
00
Vx RD
always positive using 58
- N ( 2
VXER
(59)
Now we prove that V3 2 () =, &PP VXER":
We substitute
V2 Zz (2) and P from equations 52 and (56) respectively in P
= ): V2 by
(2)
P- V (2 =2
(2)
-
N₂
(w(e)- - -w!!)) p: (w -w(") o" (z. ww
N₂
(w(2) Mr w(o) (p: -o o" (2.")) w! (w!"))"
=
Thus
P- V2
2 z is a weighted sum of symmetric rank one matrices i.c.
w
(w())² and it is PSD if and only if coefficient of each rank one matrix i.e, (w(2)
o w(?)) p (pi-a" " (z
positive. Using equations 53 and 57 we have the
v.a
following:
(Wr?)
w(()) 20 = p== hy = p (4
(2()))2 20
VieN XER
4,1
(w)(2)
-w(!) 50 = pi = his = (pi-o" "
2 50
Vie X
(Wor) w ) ( (p: -0 o (z. (1) (())))2 20
"
vie [Ni], R
(60)
Thus P
v2 2 x is PSD matrix i.e:
P v (2(0) ((2))
-0 " (z. (p())()) w (w.')²>> 00 VXER
= Σ w vi
w (p:
always positive using eq. 600
P (2) y
(2)
Vx RDD
(61)
Thus by proving the LMIS 59 and 61
we prove 55
(b) We have to prove that if her 2 O and hr s 0, P is a PSD matrix, N is a NSD matrix. we have the following:
We are given by 2 0, dy s O. Using equation
(22
w((2
(2)
0
Pt ho 2 20 Ps (w(2) Vi
WV(2 (2)
0
(
w2(2)
= P4 = h 50 = Ps ((22)
(
5
2
f,
t,
P:
(w(2)
9.4
ww(2)
6,6
0
ViE [N1]
(62)
26

---

Under review as a conference paper at ICLR 2020
Thus iss weighted sum of symmetric rank one matrices i.e, w!!) (w!")² and each coefficient pi (w())
(2)
is positive.
f,a
P
Σ
Pi (
w
w!
(w('))² T 00
always positive using eq.
62
Using equation 57 we have the following:
(x(2)
w(?))
2 0
n4 50
ni (w(2) w 50
U.
1,1
v. 1,1
(w(2) (2)
w(2)
T4e = hu 20 = mi (w/2) (2) W w( (2)
1,3
50
=
1, 50
ni (w
w((2)
20
ViE [ia[
(63)
9.1
6,2
N; N
( ( y.a
w()) (w!"))" 00
The
always positive using eq. 03
Thus P a PSD and N a NSD matrix if by 0 and hy
(c) We have to prove the following global bounds on the cigenvalues of V2 (2) - =2(2))
mI < V / x12) x MI,
where M = max v v'V,, m= min N'
|v|-1
|v|11
Since V2 ( - (2)) &P P VX:RD:
y 2 (2) v
WVRR,, VXERD
(64)
Let v², x" be vectors such that:
(v') x- (2
21 ((0')] v" max max v T V (2 - 21 )
(2)))
(2)
lv|=1
Thus using inequality 664
(v (v') V (2
S max v 'Pv |v|=1 max max v 42 (2,2) (22) ) v
(2) - ) v- s pP
max v Pv
(65)
x |v|-1
|v|-1
Since N V2 ( 2 VXERD:
V'NVVV' (V (2 (2) - -z (2) ] VVERD, VXERD
(66)
Let v", x" be vectors such that:
(v') V2 ( 21 (2) ||
min min v
V22 [T[ (z,0) - -2 )/
x |
Thus using inequality (66)
(2)
2/ [2)) v² (v*) )² N'
min v Nv M
y
min min T v2 2 zz
(2)
v2
min T Nv |
(67)
|v|=1
Using the inequalities
65 and 67)
we get:
mI x 2
2 (2)
(2)
s MI,
where M = max Tv, m= min v TN
|v|=1 |v|=1
27

---

Under review as a conference paper at ICLR 2020
D.5 PROOF OF THEOREM 4
We are given that the activation function o is such that a', a are bounded, i.e:
|o (x)) s 9. 10 (x)) sh
e
(68)
We have to prove the following:
V
S h (1(1))
Σ 7-1
max (s!?) EXER
where 8(1.)) is matrix of size N x N, defined as follows:
|W01|
I= I.
(69)
[E|L-2)
and p(1) is scalar defined as follows:
|
I=1
(70)
1 [2 L-2
We will prove the same in 3 steps. In step (a), we will prove:
F (1.1)
s ((L.1)
(71)
In step (b), we will prove:
B [ s sr(1)
VXER
(72)
In step (c), we will use (a) and (b) to prove:
h
(x())²
max (S(L.1)
(73)
1=1
Note that (2) and F(L.)) are defined using
34 and 335 respectively.
(a) We have to prove that for L 2, I [L 1], is Nr, j Ny:
(L.1)
Rx
i.j
where S(4.1) is matrix of size N, x NN defined as follows:
[W())
=
S(L.D)
[ 2]
We first prove the case when
-= L 1
Using equation 445 F
(L,11)
w(L)
i.j
Since t.j
(L.L-1) (L
F(LL-1)) -(L.1-1)
F2 Hence for 22 I 1- we have equality in Hence proved. Now, we will use proof by induction.
To prove the base case T, = 2, note that / I, = the only possible value for Thus, using the result for / = T. - 1, the theorem holds for T. = 2. This proves the base case. Now we assume the induction hypothesis true for depth = T.- 1, / [T.-2]. and prove for depth L, I [- 1J. Since for = L 1, we have proven already, we prove for / s L-2. 2. Using equation
we have the following formula for F((..))
NL
(L.))
(L) o' (z) (21111 ((L-1.1) iik
28

---

Under review as a conference paper at ICLR 2020
Taking the jth element of the vectors on both sides:
N w(l
FLL
bik (2 (2) p(b-11))
(74)
By induction hypothesis, we know that:
F pp()1111 ((1-1.1)
$ kk
(75)
Using the absolute value properties for equation (74). we have:
N
w
(-111)
i.k
F
w o' c ( F 1 (1-1
$
k=1
NE-1 s
w o (z
Using Jo' (x())
Vx R (inequality (68
S g
w
(L) i,k
F
JJ
k-1
Using the induction hypothesis (inequality (75)):
Nx-1 S
(L.D) 1.
g
W i.k
kej
Using equation
66 for definition of s
((
F (L.1) {j $ (L.1) (L.I)
Hence we prove 71 for all L and 5 L 1 using induction.
(b) We have to prove that for 1 I M 1:
| s (1)
V RD
where (() scalar given as follows:
|
T=1
g g (11-1)
I [2 1]
Using equation 43 for I we have:
BBI 1| =(
(76)
Using equation for > 1, we have:
[B WWD (o' (2(1-1))) B((-D||
(((-1)))((--111
[ | l |diag( (z(1-1)))
Since [diag (o (2(1-1) = maxx oo' (2)(111) using equation (68)
| || g (())
( s wv (اا1) 122
(77)
Using inequalities 766 and (77). the proof follows using induction.
29

---

Under review as a conference paper at ICLR 2020
(c) We have to prove that:
1-1
|
(4)
Σ (v(0)² max (5!))
s
1 we have the following equation for VEzZ!! (m)
Using Lemma
V22
1-1
Σ (B))) diag E.(.. oo (z B
Using the properties of norm we have:
|2 1
B ( ding "p(".""'"" (2())) B
$
Σ
[ding (n! oo" (x(")) | ²
1=1
L-1
[F(l o" (157) / is
$
Σ 1=1
max
In the last inequality, we use the property that norm of a diagonal matrix is the maximum absolute value of the diagonal element. Using the product property of absolute value, we get:
V222
(1)
(4)
$ Σ
max
|E% "1(""(""))))) ||B
(2/)))
1=1
Since | and "o" " (2) |
are positive terms:
V222 (1)
$ Σ
L-1
max | |1(3)))
max 10" (2/7)) |
1=1
Since o is bounded by h::
L-1
V2 (1))
s h Σ
max
1.j |
1=1
Using inequality (71)
1-1
V22 (L)
S h
Σ
max () |
1-1
Using inequality 772
L-1
1222
sh
Σ
(1)7))² max (s
Vx e RD
E COMPUTING g, h, hy AND h2 FOR DIFFERENT ACTIVATION FUNCTIONS
E. SOFTPLUS ACTIVATION
For softplus activation, we have the following. We use S(x) to denote sigmoid:
(xx) log(1 (x)( a' d((x) = 5(x) o (xx (1- (1=)(
30

---

Under review as a conference paper at ICLR 2020
To bound S1x) (x))) let denote ((x). We know that a 1:
1 a(1 a) - 4
Thus, (1 5xx)) is maximum S(x) 1/2 and minimum at S(x) = 0 and S(x) 1. The
maximum value is 0.25 and minimum value is 0.
0
0.25 0 (x) S 0.25
Thus, by 0.25, hr. (for use in Theorem 3 and g 1, h 0.25 (for use in Theorem
E.2 SIGMOID ACTIVATION
For sigmoid activation, we have the following. We use S(x) to denote sigmoid:
5()) 1+exp(-x)
o' (z)= S(x)
o' (x) S1x) ((z)) 25(x))
The second derivative of sigmoid (o (x)) can be bounded using standard differentiation. Let denote S(x). We know that 0 a l:
h a (x) $ by
hy min a(1 a) (2) Usas1
by max a(1 - ())(1))111 2xx) 0sasl
To solve for both hy and hy, we first differentiate a - 2a. with respect to a:
Va (a(1-a)(f (1)) = Va (2a - 3a² + a)) = (6a² 6a 1)
Solving for 6a 6a 0, we get the solutions:
3 v3
v3
=
Since both (3 + (3- lie between and 1, we check for the second derivatives:
(a(1-a) 2x)) V. (6a² - 6a 1) 12a 6 6(2x- 1)
At = (3+ ())
0.
At (3 ///6. v 6(2n - -2/3<< 0.
Thus (3+ /3/6 is local minima, a= (3 /3)/6 is local maxima.
Substituting the two critical points into a(1 - a1) 20x, we get by -.6223 x 10-2, h4 -9.623 10-
Thus, hy 9. 623 10-2 2 h2 = 9.623 x 10-2 (for use in Theorem and g 0.25, = 0.09623
(for use in Theorem
E.3 TANH ACTIVATION
For tanh activation, we have the following:
(x) = tanh(x) exp(x) - exp(-x)
exp(x) exp(-2) (Ix)
(x) = (1 tanh())) tanh(*))
(x) -anhh(()) (1 tanh(x)) (1 tanh(x))
31

---

Under review as a conference paper at ICLR 2020
The second derivative of tanh, i. (o" (z)) be bounded using standard differentiation. Let denote tanh(z). We know that -1 S a S 1:
hg (z) s hu
hr = min
-0 az) + +x)
0ses1
by max
-2a cx) +a)
0cacl
To solve for both hy and hy, we first differentiate -2a(1 a) a) with respect to az
Va (-2a(1 - (1+ Va (2a² 2a) (6a² 2)
Solving for 6a 2 0, we get the solutions:
1
Since both -1/V3,1/V3 lie between and we check for the second derivatives:
Va (-2a(1-aa) a)) = Va (6a2 - 2) 12a
At = 12a 44/3<0. v
a 1/v3, v2 12a 12a 4/ 0. Thus 1/v3 is local minima, a -=-1/v3 is a local maxima. Substituting the two critical points into 2a - (1+1 a), we get hy = 0.76981, h4 -0.76981. Thus, by 0.76981, 4r -0.76981 (for use in Theorem and 1, h 0.76981 (for use in Theorem
F QUADRATIC BOUNDS FOR TWO-LAYER RELU NETWORKS
For layer network with ReLU activation, such that the input lies in the ball ||X p. can compute the bounds over (1)) directly:
w (1) (0) b,Sh
s sz w/
(1)
w( -b.0 + +p +||w!'||
Thus we can get lower bound and upper bound for each (1) We define de and u, as the following:
di ((()) x (0) + b (
(78)
4, (1) (0) b(t) + w("]
(79)
We can derive the following quadratic lower and upper bounds for each ag (1),
-d,
2
(1)) 2
ui
2 df
2
(1)
ufd,
|d. |uu]
(4: d
(u:
d,2
(4: - d;)²
a
<
u4
(2 (1)) 2
20
24
(1)
u.d
[d,] 2 |ud]
(4 - 2
(ui d
(u - d
2/d [u:]
(1)
z
|4,| 2 2/u,|
a
(1)
de (1)
2
otherwise
d;
U4 d
The above steps are exactly the same as the quadratic upper and lower bounds used in (Zhang et al. 2018a).
Using the above two incqualities and the identity:
(2)
(2(2)
-w(?)) a.)))
Z
B.3
32

---

Under review as a conference paper at ICLR 2020
can compute a quadratic lower bound for Zyy
(2) -z( in terms of (1)
2 by taking the lower bound
for a when (w(2) (2)
w(())
0 and upper bound when (w W
A, <= O. Furthermore since
(1) w(1)x x (1)
2
we can express the resulting quadratic in terms of Thus, we get the following
quadratic function:
1 Zi 2 2 Px+
2
The coefficients P, q and can be determined using the above procedure. Note that unlike in (Zhang et al. 2018a), RHS can be non-convex function.
Thus, it becomes an optimization problem where the goal is to minimize the distance 1/2 x x (
subject to RHS (which is quadratic in x) being zero. That is both our objective and constraint are quadratie functions. In the optimization literature, this is called the S-procedure and one of the few non-convex problems that can be solved efficiently (Boyd & Vandenberghe 20044).
We start with two initial values called Plow (initialized to 0) and Phigh (initialized to 5). We start with initial value of p. initialized 1/2 (Plow (high) to compute d; (eq. 788 and
us (eq. (79)). the final distance after solving the S-procedure is less than p. we set Plow = p. the final distance is greater than p. set Phigh p. Set new P 1/2 (piow Phigh) Repeat until convergence.
G ADDITIONAL EXPERIMENTS
Empirical accuracy means the fraction of test samples that were correctly classified after rumning PGD attack (Madry et al. 2018) with an l2 bound on the adversarial perturbations. Certified accuracy means the fraction of test samples that were classified correctly initially and had the robustness certificate greater than a pre-specified attack radius p. For both empirical and certified accuracy, we p 0.5. Unless otherwise specified, we use the class with the second largest logit the attack target for the given input (i.e. the class t). All experiments were run on the MNIST dataset while noting that results scalable for more complex datasets. The notation (L. x [1024], activation)
denotes a neural network with I. layers with the specified activation function, (7 e) denotes standard training with y set c, (CRT, c) denotes CRT training with y Certificates CROWN and CRC computed over 150 correctly classified images.
G. RESULTS ON CONVOLUTIONAL NEURAL NETWORKS
We 2 layer (1 hidden layer network). We use 64 filters in the convolution layer and softplus activation function and stride length This is followed by reshaping and fully connected layer.
MNIST
CIFAR-10 -0
Empirical Robust
Certified Robust
Empirical Robust
Certified Robust
Standard Accuracy
Standard Accuracy
Accuracy
Accuracy
Accuracy
Accuracy
0
98.68%
87.81% %
0.00%
56.22%
14.88%
0.00%
0.005
97.67%
93.71%
91.47%
56.18%
30.19%
9.37%
0.01
97.08%
92.92%
91.25%
53.52%
31.82%
17.39%
0.02
96.36%
90.98%
89.58%
49.55%
31.80%
25.93%
0.03
95.54%
89.99%
88.75%
46.56%
31.98%
29.26%
Table 8: Comparison between certified robust accuracy for different values of the regularization parameter y for a single hidden layer convolutional neural network with softplus activation function
33

---

Under review as a conference paper at ICLR 2020
G.2
RESULTS FOR TANH NETWORKS
Empirical Robust
Certified Robust
Certificate
Standard Accuracy
Network
Training
(mean)
Accuracy
Accuracy
CROWN
CRC
PGD
98.76%
95.79%
84.11 %
0.30833
0.61340
2x 2x[102] [1024].
TRADES
98.63%
96.20%
93.72%
0.40601
0.86287
tanh
CRT, 0.01
98.52%
95.90%
95.00%
0.37691
1.47016
PGD
98.78%
94.92%
0.00%
0.12706
0.03036
3x [024]. tanh
TRADES
98.16%
94.78%
0.00%
0.15875
0.02983
CRT, 0.01
98.15%
95.00%
94.16%
0.28004
1.14995
PGD
98.53%
94.53%
0.00%
0,07439
0.00140
4x [022]].
TRADES
97.08%
92.85%
0.00%
0.11889
0.00068
tanh
CRT, 0.01
97.24%
93.05%
91.37% %
0.33649
0.93890
Table 9: Comparison between CRT, PGD (Madry al. 2018 and TRADES (Zhang et al. 2019) for Tanh networks. CRC outperforms CROWN significantly for layer networks and when trained with regularizer for deeper networks. CRT outperforms TRADES and PGD giving higher certified accuracy.
G.3 COMPARING RANDOMIZED SMOOTHING AND TRADES WITH CRT
Randomized smoothing is designed to work in untargeted attack settings while CRT is for targeted attacks. Thus, to do fair comparison of CRT with randomized smoothing, we make the following changes in randomized smoothing.
First, we use ni = 100 initial samples to select the label class (l) and false target class (t). The samples for estimation were 100, 000 and failure probability was 0.001. Then we use the binary version of randomized smoothing for estimation, ie classify between y and t. To find the adversarial example for adversarial training,
the cross entropy loss for classes (y and t).
For TRADES, we select the class with second highest logit as the target class and use the class version of the cross entropy loss for finding the adversarial example.
Table 10: Comparison between CRT and Randomized Smoothing(Cohen al. standard deviation for smoothing. We use
2019 denotes the
0.5. For CRT, we use y 0.01
Randomized Smoothing
CRT
Network
= 0.25
0.50
1.0
2
1024], sigmoid
93.75%
93.09%
88.91 %
95.61 %
x
1024]. tanh
94.61%
93.08%
82.26%
95.00% %
1024). sigmoid
94.00%
93.03%
86.58%
94.99 %
3
1024]. tanh
93.69%
91.68%
80.55%
94.16% %
x
1024]. sigmoid 93.68 %
92.45%
84.99%
93.41 %
x
1024]. tanh 93.57 %
92. 19%
83.90%
91.37%
34

---

Under review as a conference paper at ICLR 2020
Table 11: Comparison between CRC and CROWN--gneraal (CROWN-Ada for relu) for different
targets. For CRT training, we use 7 0.01. We compare CRC with targets for 150 correctly classified images. Runner-up means class with second highest logit is considered adversarial class. Random means any random class other than the label is considered adversarial. Least means class with smallest logit adversarial. For 2-layer networks, CRC
for different
outperforms CROWN-general significantly even without adversarial training. For deeper networks (3
and layers), CRC works better on networks that are trained with curvature regularization.
Certificate (mean)
Time per Image (s)
Network
Training
Target
CROWN
CRC
CROWN
CRC
runner-up
0.50110
0.59166
0.1359
2.3492
2 x [1024], relu
standard
random
0.68506
0.83080
0.2213
3.5942
least
0.86386
1.04883
0.1904
3.0292
runner-up
0.28395
0.48500
0.1818
0.1911
standard
random
0.38501
0.69087
0.1870
0.1912
least
0.47639
0.85526
0.1857
0.1920
2 x [1024], sigmoid
runner-up
0.43061
1.54673
0.1823
0.1910
CRT, 0.01
random 0.52847
1.99918
0.
0.1911
least
0.62319
2.41047
0.1873
0.1911
runner-up
0.23928
0.40047
0.1672
0.1973
standard
random
0.31281
0.52025
0.1680
0.1986
least
0.38964
0.63081
0.1726
0.1993
2 x [1024], tanh
runner-up
0.37691
1.47016
0.1633
0.1963
CRT, 0.01
random 0.45896
1.87571
0.1657
0.1982
least
0.52800
2.21704
0.1697
0.1981
runner-up
0.24644
0.06874
1.6356
0.5012
standard
random
0.29496
0.08275
1.5871
0.5090
least
0.33436
0.09771
1.6415
0.5056
3 x [1024], sigmoid
runner-up
0.39603
1.24100
1.5625
0.5013
CRT, 0.01
random 0.46808
1.54622
1.6142
0.4974
least
0.51906
1.75916
1.6054
0.4967
runner-up
0.08174
0.01169
1.4818
0.4908
standard
random
0.10012
0.01432
1.5906
0.4963
least
0.12132
0.01757
1.5888
0.5076
3 x [1024], tanh
runner-up
0.28004
1.14995
1.4832
0.4926
CRT, 0.01
random 0.32942
1.41032
1.5637
0.4957
least
0.38023
1.65692
1.5626
0.4930
runner-up
0.19501
0.00454
4.7814
0.8107
standard
random
0.21417
0.00542
4.6313
0.8377
least
0.22706
0.00609
4.7973
0.8313
4 x [1024], sigmoid
runner-up
0.40327
1.06208
4.1830
0.8088
CRT, 0.01
random
0.47038
1.29095
4.3922
0.7333
least
0.52249
1.49521
4.4676
0.7879
runner-up
0.03554
0.00028
5.7016
0.8836
standard
random
0.04247
0.00036
5.8379
0.8602
least
0.04895
0.00044
5,8298
0.9045
4 x [1024], tanh
runner-up
0.33649
0.93890
3,8815
0.8182
CRT, 0.01
random 0.41617
1.18956
4.0013
0.8215
least
0.47778
1.41429
4.3856
0.8311
35

---

Under review as a conference paper at ICLR 2020
G.4 MEASURING THE IMPACT OF CURVATURE REGULARIZATION
In Table 12 we measure how the standard accuracy, empirical aceuracy, certified accuracy, up- per bound the curvature Kub, lower bound the curvature Ki. changes increase the regularization parameter and the network is trained with CRT.
In Table 13 measure how the standard accuracy, empirical accuracy, certified accuracy, CROWN and CRC changes as we increase the regularization parameter ? and the network is trained without any adversarial training.
G.5 COMPUTING Kis AND Kud
First, note that K does not depend on the input, but on network weights W(), label and target t. Different images may still have different K because label y and target t may be different.
To compute Ki in the table, first for each pair and t, we find the largest eigenvalue the Hessian of all test images that have label y and second largest logit of class t. Then take the max of the largest eigenvalue across all test images. This gives a rough estimate of the largest curvature in the vicinity of test images with label y and target 6. We can directly take the mean across all such pairs compute K₁.- However, we find that some pairs y and / were infrequent (with barely 1,2 test images in them). Thus, for all such pairs we cannot get good estimate of the largest curvature vicinity. We select all pairs y and that have at least 100 images in them and compute Kis by taking the mean across all such pairs.
To compute Kus in the table, we compute K for all pairs y and that have at least 100 images, i.e at least 100 images should have label y and target f. And then we compute the mean across all K that satisfy this condition. This was done to do fair comparison with Kis-
Figure shows plot of the Kub and Kis with increasing 7 for a tanh network.
Figure Kus and Kis are upper and lower curvature bounds of the network with Tanh activations (averaged over (y. t) pairs). When 7 (no curvature regularization), networks adversarially trained with CRT or PGD both have high curvatures. However, CRT with even small y leads to significant decrease in curvature bounds. Also, curva- ture bounds higher with Tanh than with Sigmoid. Results are similar to Sigmoid in Figure T
Egenvaliue bounds for the Hessian
Upper bound CEgl with CITT
Lawer bound tual with ox
wihiie
301-
6d1.
002
643
806
C.0
Curvature Regulatization confficient,
36

---

Under review as a conference paper at ICLR 2020
this table, we measure the effect of increasing 7, when the network is trained with CRT on standard, empirical, certified robust accuracy, Ky, and Kub (defined in subsection G.5 for different depths (2, 3, layer) and activations (sigmoid, tanh). We find that for all networks y 0.01 works best. We find that the lower bound, Kn, increases (for y 0) for deeper networks suggesting that deep networks have higher curvature. Furthermore, for given 7 (say 0.005), we find that gap between K and Kis increases as we increase the depth suggesting that K is not a tight bound for deeper networks.
Table 12:
Empirical Robust Accuracy
Certified Robust
Curvature bound (mean)
Standard Accuracy
Network
KBb
Kub
Accuracy
0.0
98. 78.77%
96.17%
95.04%
7.2031
72.0835
0.005
98.82%
96.33%
95.61 %
3.8411
8,2656
2x 2x[14,
0.01
98.57%
96.28%
95.59%
2.8196
5,4873
sigmoid
0.02
98.59%
95.97%
95.22%
2.2114
3,7228
0.03
98.30%
95.73%
94.94%
1.8501
2.9219
0.0
98.65%
95.48%
92.69%
12.8434
107.5689
0.005
98.71 08.71%
95.88%
94.76%
4.8116
10.1860
2x[1024].
0.01
98.52%
95.90%
95.00%
3.4269
6,3529
tanh
0.02
98.35%
95.71%
94.77%
2.3943
4.1513
0.03
98.29%
95.39%
94.54%
1.9860
3.933
0.
98.52%
90.26%
0.00%
19.2131
3294.9070
0.005
98.41 %
95.81 %
94.91% %
2.6249
13.4985
0.01
98. 98.23%
95.70%
94.99 %
1.9902
8.6654
3x[1024],
0.02
97. 97.99%
95.33%
94.64%
1.4903
5,4380
sigmoid
0.03
97. 97.86%
94.98%
94.15%
1.2396
4.1409
0.04
97.73%
94.60%
93.88%
1.0886
3.3354
0.05
97.60%
94.45%
93.65%
0.9677
2.7839
0.
99.19%
86.38%
0.00%
133.7992
17767.5918
0,005
98.13%
94.56%
93.01 %
3.2461
17.5500
0.01
98. 15.1%
95.00%
94.16%
2.2347
10.8635
3x [1024).
0.02
97. 87.84%
94.79%
94.05%
1.6556
6.7072
tanh
0.03
97.70%
94. 19%
93.42%
1.3546
5,0533
0.04
97.57%
94.04%
92.95%
1.1621
4.0071
0.05
97.31%
93.66%
92.65%
1.0354
3.3439
0.
98.22%
83.04%
0.00%
86.9974
343582.
0.005
98.18%
95.02%
93.20%
2.1760
15.3358
0.01
97.83%
94.65%
93.41 %
1.6823
10.2289
0.02
97.33%
94.02%
92.94%
1.2089
6,5573
4x 4x[1024],
0.03
97.07%
93.52%
92.65%
1.0144
4.9576
sigmoid
0.04
96.70%
92.78%
91.95%
0.8840
3.9967
0.05
96.38%
92.29%
91.33%
0.7890
3.4183
0.06
96.29%
92.17%
91.11%
0.7128
3,0050
0.07
96.08%
91.83%
90.67%
0.6614
2.6905
0.
97. 97.45%
75.18%
0.00%
913.6984
37148156
0.005
97.48%
93.29%
89.98%
2.8690
18.8079
0.01
97. 97.24%
93.05%
91.37 %
1.9114
12.2148
0.02
96.82%
92.65%
91.35%
1,3882
7.1771
4x[1024]
0.03
96.27%
91.43%
90.09%
1.1643
5.1671
tanh
0.04
95.62%
90.69%
89.41%
0.9620
3,9061
0.05
95.77%
90.69%
89.40%
0,9160
3,2909
0.06
95.52%
90.00%
88.38%
0.8234
2,8808
0.07
95.24%
89.51%
87.91%
0.7540
2.5635
37

---

Under review as a conference paper at ICLR 2020
Table 13: In this table, measure the impact of increasing curvature regularization (7) on accuracy, empirical robust accuracy, certified robust accuracy, CROWN CROWN-genent -egneral and CRC when the network trained without any adversarial training. We find that adding very small amount of curvature regularization has minimal impact the accuracy but significantly increases CRC. Increase in CROWN certificate is not of similar magnitude. Somewhat surprisingly, we observe that even without any adversarial training, we can get nontrivial certified accuracies of 84.73% 88.66% 89.61 % on 2,3,4 layer sigmoid networks respectively.
Empirical Robust Accuracy
Certified Robust
Certificate (mean)
Standard Accuracy
Network
CROWN
CRC
Accuracy
0.
98.37%
76.28%
54.17%
0.28395
0.48500
0.005
97.96%
88.65%
82.68%
0.36125
0.83367
2 [1024], sigmoid
0.01
98.08%
88.82%
83.53%
0.32548
0.84719
0.02
97.88%
88.90%
83.68%
0.34744
0.86632
0.03
97.73%
89.28%
84.73%
0.35387
0.90490
0.
98.34%
79.10%
14.42%
0.23938
0.40047
0.005
98.01%
89.95%
85.70%
0.27262
0.89672
2 x [1024], tanh
0.01
97.99%
90.17%
86. 18%
0.28647
0.93819 19
0.02
97.64%
90.13%
86.40 %
0.30075
0.99166
0.03
97.52%
89.96%
86.22%
0.30614
0.98771
0.
98.37%
85.19%
0.00%
0.24644
0.06874
0.005
97.98%
91.93%
88.66 %
0.38030
0.99044
0.01
97.71%
91.49%
88.33%
0.39799
1.07842
3 [1024], sigmoid
0.02
97.50%
91.34%
88.38%
0.38091
1.08396
0.03
97.16%
91.10%
88.63%
0,41015
1.15505
0.04
97.03%
90.96%
88.48%
0,42704
1.18073
0.05
96.76%
90.65%
88.30%
0,43884
1.19296
0.
97.91%
77.40%
0.00%
0.08174
0.01169
0.005
97.45%
91.32%
88.57 %
0,28196
0.95367
0.01
97.29%
90.98%
88.31% %
0.31237
1.05915
3 x [1024], tanh
0.02
97.04%
90.21%
87.77%
0.30901
1.08607
0.03
96.88%
90.02%
87.52%
0.34148
1.11717
0.04
96.53%
89.61%
86.87%
0.36583
1.11307
0.05
96.31%
89.25%
86.26%
0.38519
1.1 1.19689
0.
98.39%
83.27%
0.00%
0.1950
0.00454
0.005
97.74%
91.67%
88.95%
0.36863
0.91840
0.01
97.41%
91.71%
89.61 %
0,40620
1.05323
0.02
96.47%
90.03%
87.77%
0.45074
1.14219
4 x [1024], sigmoid
0.03
96.24%
90.40%
88. 14%
0.47961
1.30671
0.04
95.65%
89.61%
87.54%
0,49987
1.35129
0.05
95.36%
89.10%
87.09%
0.51187
1.36064
0.06
95.29%
88.96%
87.01%
0.52629
1.38666
0.07
95.23%
88.03%
85.93%
0.54754
1.27948
0.
97.65%
69.20%
0.00%
0.03554
0,00028
0.005
97.02%
89.77%
85.98%
0.29410
0.82364
0.01
96.52%
89.38%
86.40%
0.34778
0.97365
0.02
96.09%
88.79%
86.09%
0,41662
1.10860
4 [1024], tanh
0.03
95.74%
88.36%
85.65%
0.44981
1.17400
0.04
95.10%
87.50%
84.74%
0.48356
1.21957
0.05
95.14%
87.72%
84.77%
0,49113
1.25076
0.06
94.66%
86.96%
84.28%
0.51104
1,28653
0.07
94.34%
86.67%
83.90%
0.49750
1.24198
38

---

Under review as a conference paper at ICLR 2020
G.6 COMPARING OUR ATTACK AGAINST 12 BOUNDED PGD
In this section, we empirically compare our Curvature-based attack optimization to the PGD method of Madry et al. 2018) (200 steps of size 0.01). We should note that the objectives of attack and PGD are different. The PGD attack (with sufficiently large number of steps) will always find solution (attacck) such that (x - -x(0) [|2 p. However, if our curvature bound is loose (or even if the curvature bound is tight but the network itself has large curvature), our method may converge to point inside the ball where (x(attack) x || p. The primary benefit of our method is that if converges to point on the surface of the ball (i.e. |xx (a x0) |2 p), then (attackk) provably the worst case perturbation in the la ball of radius p around the input (0) (since primal=dual using Theorem 2
Thus, have the same perturbation magnitude between our attack optimization and PGD, we consider a subset of samples where our attack method converges to point on the surface of the ball. Table 14 we show a comparison between average values of Zy 24 computed using PGD and our method where is the correct label and t is the attack target. In this table, Mean CBA (Curvature- Based Attack) is computed by taking the average of n, z, for all test samples satisfying (atttackk x l (with curvature based attack optimization). The relative gain is computed as (Mean PGD Mean CBA)/(Mean PGD).
Table 14: Comparison between mean values of n Z, for l2 bounded PGD and Curvature-Based Attack (CBA) optimization. See the experimental details Section G.6
Network
Mean PGD
Mean CBA
Relative Gain
2x
1024
sigmoid 5.1526
4.9296
4.33%
3 x
[1024].
sigmoid 3.7748
3.6342
3.72%
4 x
1024
sigmoid
3.2024
3.0846
3.68%
Table 15: Table showing attack success rates for different values of 7. Attack success rate denotes the fraction of points (x) satisfying (xttllinngg/((ttttttei (xattack)) x x0))
|| = implying primal = dual in Theorem
Network
Attack success rate
0.
5.05%
2 [1024], sigmoid
0.01
100%
0.02
100%
0.
0.%
0.01
44.86%
3 [1024], sigmoid
0.03
100%
0.05
100%
0.
0.%
0.01
24.42%
4 x [1024], sigmoid
0.03
88.82%
0.05
99.97%
39


Reviews:
[{"review_id": "SyeeMBpX5r", "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 develops computationally-efficient convex relaxations for robustness certification and adversarial attack problems given the classifier has a bounded curvature. The authors showed that the convex relaxation is tight under some general conditions. To be able to use proposed certification and attack convex optimizations, the authors derive global curvature bounds for deep networks with differentiable activation functions. The result is a consequence of a closed-form expression that the paper derived for the Hessian of a deep network. \n\nThe empirical results indicate that the proposed curvature-based robustness certificate outperforms the CROWN certificate by an order of magnitude while being faster to compute as well. Furthermore, adversarial training using the attack method coupled with curvature regularization results in a significantly higher certified robust accuracy than the existing adversarial training methods. \n\n1.  I am not at all familiar with the robustness certification, therefore little knowledge of relevant related works. \n\n2. I hope the authors can provide a more thorough survey of related works. \n\n3. There exist good amount of theoretical analysis in the paper. However all empirical results are only from MNIST. This certainly weakens the method's contribution. \n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "H1xPn2zPYr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary\n========\nThis paper proposes the Curvature-based Robustness Certificate (CRC) and Curvature-based Robust Training (CRT) for robustness certificate against adversarial examples. The proposed techniques are theoretically formulated and empirically justified. The authors showed that, when the curvature (Hessian) of the network is bounded, improved certificate can be achieved by convex optimization. Explicit curvature regularization via CRT seems further improve both the certified robustness accuracy and the certificate, at a cost of 2% decrease in empirical robust accuracy. \n\nWhile the proposed approaches are theoretically sound, I have several concerns, mostly on the experiments.\n=================\n1. Existing certification methods should be compared in more details, in terms of different assumptions, activation functions, etc. A summary table can help.\n\n2. Comprehensive comparisons to more existing works such as \"Certified adversarial robustness via randomized smoothing\" (more formal comparison than in the appendix). \n\n3. Experiments on CIFAR-10 and different activation functions in the main text.\n\n4. Not sure why compare to uncertified defenses PGD and TRADES, though it doesn't seem to hurt the conclusions.\n\n===============\nAfter rebuttal:\n\nThanks for the response, my concerns have been addressed, rating upgraded to 6: weak accept.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "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_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BJxB8Y3gqS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper gives a global curvature bound for general neural networks, and used this bound for certifying robustness of neural networks. The basic techniques include writing the neural network verification problem as a constrained optimization problem (similar to [1]), and construct a Lagrangian dual for it, and discuss the situation where the dual problem is convex and can be solved efficiently. The global curvature bound is the crucial step to determine the condition that the optimization problem is convex.\n\nThe benefits of the proposed methods include efficiency (bounds m and M only need to be solved for each target label pair, and the optimization process to get the certificate is fast), and tight certified accuracy for shallow networks. Also, it can be used during training to improve the tightness of CRC bounds.  There are also a few weakness: the certificate unfortunately only works for non-ReLU networks, and only for L2 norm; for networks beyond 2 layers, CRC cannot outperform CROWN unless it is specially trained using the CRC loss.\n\nQuestions and concerns:\n\n1. For the curvature regularization training, some comparisons against other certified defenses are needed - PGD and TRADES are not good examples since they are not certified defense methods, and 0% certified accuracy are obtained. I understand many existing works like Wong et al., 2018 only work on ReLU networks, but I believe interval bound propagation (IBP) based methods [2] should be easily applicable to any monotonic activation functions. At least, the authors should compare verified accuracy at the same epsilon settings (\\pho=1.58) as in Wong et al., 2018.  In page 22 (last page of appendix in arxiv version) of [3], you can find their L2 robustness training results.  How does the certified accuracy of CRC compare to these results?\n\n2. The paper mentions the Attack problem and proposes an attack algorithm (Algorithm 2), however I am not able to find any experiments on the attack. If the authors want to claim the contribution of curvature based attacks, some empirical results should be given, and at least compare it to a 200-step PGD baseline and see which one finds smaller adversarial examples.\n\n3. The claim (in introduction and conclusions) that CRC is much faster than CROWN probably won't hold under a fair comparison. I believe the gradient decent based certification algorithm (Algorithm 1) was computed efficiently on GPU, where the NN is defined. For a fair comparison, it should be also compared to a GPU implementation of CROWN ([4] provides such an implementation).  In my experience, CROWN is an efficient algorithm that can be even used iteratively during training (as a certified defense [4]), so for the small networks used in this paper, it should compute bounds almost instantly on GPUs. I think it is better to revoke this claim, and in experiments the authors should clearly state that CROWN was computed on CPU so time is not comparable. \n\n4. Also the claim \"CRC outperforms CROWN's certificate significantly\" should be made clearer that it only holds for CRC trained models. According to Table 3, CRC is significantly worse than CROWN if the model is not CRC trained.  Additionally, it should be made clear that the proposed method currently only applies to L2 norm setting.\n\n5. (Minor) There are several duplicated references, e.g., on page 9, Cohen et al., (randomized smoothing) was cited twice as two different papers; the same is with Madry et al., on page 10, and Zhang et al. (CROWN) on page 11. These causes some confusions, e.g., on page 2, when talking about the bounded Lipschitz constant, I believe the correct citation for (Zhang et al., 2018b) should be another paper [5] from the same first author which is on bounding Lipschitz constant.\n\nImprovements and extensions:\n\nI think the proposed method can be greatly improved by using \"local curvature\", where the curvature bounds m and M are computed within a local region near an input point. This is sufficient as long as our optimization does not escape this safe region, and the safe region can be naturally defined as the perturbation radius to be certified. The local curvature can be obtained by giving a tighter bounds on the second derivative of activation function, rather than considering just the worst case. Using CROWN, we can obtain pre-activation upper and lower bounds. These bounds can be used to bound the second derivative. For example, if a tanh neuron's input is bounded by -0.1 and 0.1 (those bounds can be obtained efficiently by CROWN), the second derivative of tanh is bounded between -0.197356 and +0.197356, much better than the worst case bound -0.76981 and +0.76981 used in current global curvature bound. A similar technique to bound Jacobian matrix was used in [5]. Including some results for local curvature certificates will greatly increase the contribution of this paper, and make it a complete work. I strongly encourage the authors to do so, and feel free to discuss with me on any questions.\n\n\nDespite some concerns, the main contribution of giving global curvature bounds of neural networks is valid. Thus I vote for accepting this paper, however the authors should make sure to address all the concerns.\n\n[1] Salman, Hadi, et al. \"A convex relaxation barrier to tight robust verification of neural networks.\" arXiv preprint arXiv:1902.08722 (2019).\n[2] Gowal, Sven, et al. \"On the effectiveness of interval bound propagation for training verifiably robust models.\" arXiv preprint arXiv:1810.12715 (2018).\n[3] Wong, Eric, et al. \"Scaling provable adversarial defenses.\" Advances in Neural Information Processing Systems. 2018. https://arxiv.org/pdf/1805.12514.pdf\n[4] Zhang, Huan, et al. \"Towards Stable and Efficient Training of Verifiably Robust Neural Networks.\" arXiv preprint arXiv:1906.06316 (2019).\n[5] Zhang, H., Zhang, P., & Hsieh, C. J. Recurjac: An efficient recursive algorithm for bounding jacobian matrix of neural networks and its applications. arXiv preprint arXiv:1810.11783 (2018).\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 paper presents a upper bound on the curvature of a deep network. After the discussion, the author has addressed some concerns of reviwers, but the results are not very strong, there is some limitation on the applications. There is no strong support for this paper. Due to the high standard of ICLR, the acceptance of the paper need strong results in terms of theory or experiments.
Decision: Reject