Training Provably Robust Models by Polyhedral Envelope Regularization
Authors: Chen Liu
Mathieu Salzmann
Sabine Süsstrunk
Venue:  (2020)
Keywords: deep learning
adversarial attack
robust certification

Abstract: Training certifiable neural networks enables one to obtain models with robustness guarantees against adversarial attacks. In this work, we use a linear approximation to bound model’s output given an input adversarial budget. This allows us to bound the adversary-free region in the data neighborhood by a polyhedral envelope and yields finer-grained certified robustness than existing methods. We further exploit this certifier to introduce a framework called polyhedral envelope regular- ization (PER), which encourages larger polyhedral envelopes and thus improves the provable robustness of the models. We demonstrate the flexibility and effectiveness of our framework on standard benchmarks; it applies to networks with general activation functions and obtains comparable or better robustness guarantees than state-of-the-art methods, with very little cost in clean accuracy, i.e., without over-regularizing the model.

Under review as a conference paper at ICLR 2020
TRAINING PROVABLY ROBUST MODELS BY POLYHEDRAL ENVELOPE REGULARIZATION
Anonymous authors Paper under double-blind review
ABSTRACT
Training certifiable neural networks enables one to obtain models with robustness guarantees against adversarial attacks. In this work, we use linear approximation to bound model's output given an input adversarial budget. This allows us to bound the adversary-free region in the data neighhorhood by a polyhedral envelope and yields finer-grained certified robustness than existing methods. We further exploit this certifier to introduce a framework called polyhedral envelope regular- ization (PER), which encourages larger polyhedral envelopes and thus improves the provable robustness of the models. We demonstrate the flexibility and effee- tiveness of our framework standard benchmarks; applies to networks with general activation functions and obtains comparable or better robustness guarantees than state-of-the-art methods, with very little cost in clean accuracy, i.e., without over-regularizing the model.
INTRODUCTION
Despite their great success in many applications, modern deep learning models are vulnerable to adversarial attacks: small but well-designed perturbations make the state-of-ther thrtt--ttttttttt models predict wrong labels with very high confidence (Goodfellow et al. 2014]] Moosavi-Dezfoolf et al. 2017]] Szegedy et al. 2013). The existence of such adversarial examples indicates unsatisfactory properties of the deep learning models' decision boundary (He et al. 2018), and poses threat to the reliability of modern machine learning systems.
As consequence. studying the robustness of deep learning has attracted growing attention, from the perspective of both attack and defense strategies. Popular attack algorithms, such as the fast gradient method (FGM) (Goodfellow et al., 2014). the CW attack (Carlini & Wagner] 2017) and the projected gradient descent (PGD) algorithm (Madry et al., 2017). typically exploit the gradient of the loss w.r.t. the input to generate adversarial examples. To counteract such attacks, many defense algorithms have been proposed (Buckman et al., 2018 Dhillon et al., 2018 Guo et al. 2017 Ma et al. 2018; Samangguui et al. 2018 Song et al. [217]] Xie et al. 2017). However, it shown in Athaayy et al. (2018) that most them depend on obfuscated gradients for perceived robustness. In other words, these methods train models fool gradient-basee attacks but do not achieve true robustness. As a consequence, they become ineffective when subjected to stronger attacks. The only exception is adversarial training (Madry et al., 2017), which augments the training data with adversarial examples. Nevertheless, while adversarial training yields good empirical performance, it still provides no guarantees of model's robustness.
In this work, we focus on constructing certifiers to find certified regions of the input neighborhood where the model is guaranteed give the correct prediction, and on using such certifiers to train a model to be provably robust against adversarial attacks. In this context, complete certifiers can either guarantee the absence of an adversary or construct an adversarial example given an adversarial budget. They are typically built on either Satisfiabllity Modulo Theories (SMT) (Katz et al. (017)) or mixed integer programming (MIP) (Tjeng et al. 2017, Xiao et al., 2018). The major disadvantages of complete certifiers are their puper-polynomial complexity and applicability to only piecewise linear activation functions, such as ReLU, By contrast, incomplete certifiers are faster, more widely applicable but more conservative in terms of certified regions because they rely approximations. Techniques such as linear approximation (Kolter & Wong 2017,; Wong et al.) 2018) Zhang et al. 2018 Weng al. 2018) symbolic interval analysis (Wang et al. 2018b), abstract transformers (Gehr
Xiao

---

Under review as a conference paper at ICLR 2020
et al. 2018 Singh et al. 2018 2019), semidefinite programming (SDP) Raghunathan et al. 2018a b)
and randomized smoothing (Cohen et al. 2019 Salman et al. 2019aa are exploited to offer better
certified robustness. Some of these methods enable training provably robust models (Raghunathan
(et al. 201 Sa Kolter & Wong 2017 Wong et al. 2018 Cohen et al. 2019 Salman et al. 2019a) by
optimizing the parameters as maximize the area of the certified regions.
While effective, all the above-mentioned methods, in their vanilla version, only provide binary results given a fixed adversarial budget. That is, if a data point is certified, it guaranteed to be robust in the entire given adversarial budget; otherwise no guaranteed adversary-free region is estimated. To overcome this and search for the optimal adversarial budget that can be certified, Kolter Wong (2017); Weng et al. (2018) 8); Zhang et al. (2018) use either Newton's 's method or binary search. By contrast, Croce et al. (2188) take advantage of the geometric property of ReL.U networks and gives finer-grained robustness guarantees. Given the piecewise linear ReI.U function, any input is located in a polytope where the ReLU network can be considered linear. Based on geometry, robustness guarantees can thus be calculated using the input distance to the polytope boundary and the decision boundary constraints. Unfortunately, in practice, the resulting certified bounds are trivial because such polytopes very small even for robust models. Nevertheless, Croce et al. (2018) introduce regularization scheme based on these bounds to effectively train provably robust models.
In this paper, construct stronger certifier, well regularization scheme to train provably robust models. To this end, building upon the geometry-inspired idea of Croce et al. (2018). we estimate linear bound of the model's output given predefined adversarial budget. Then, the condition to guarantee robustness inside this budget is also linear and forms a polyhedral envelope of the model's decision boundary. Similar coooe et al. (2018), the region contained in the polyhedral envelope and the adversarial budget is certified to be adversary-free We then further exploit this certifier design regularization framework to train provably robust neural network models.
In short, our contributions are twofold. First, we design a geometric-inspired certification method giving finer-grained one-shot bounds than its counterparts (Kolter & Wong] 2017 Weng et al., 2018 Zhang et al.] 2018) with little overhead and applies to general activation functions. More importantly, we propose a regularization scheme to train provably robust models. Compared with existing provable training methods, which have been found to over-regularize the model (Zhang et al. 2019), our training framework yields competitive robustness guarantees while maintaining good performance on clean inputs. In the remainder of the paper, we call our certification method Polyhedral Envelope Certifier (PEC) and regularization scheme Polyhedral Envelope Regularizer (PER).
PRELIMINARIES
2.1 NOTATION AND TERMINOLOGY
For simplicity, we discuss our approach using standard N-layer fully-connected network. Note, however, that it straightforwardly extends to any network topology that can be represented by directed acyclic graph (DAG) in the same way as in (Liu et al. 2019). A fully-connected network
parameterized by { (+))), (() N-1
Ti=1 can be expressed as
z (++1) ((0 + (1)
i= 1,2,, N 1 N....,N-.
2 (z)
2,3,,...,
where (1)) and (0) are the pre- & post-activations of the i-th layer, respectively, and (1) def the input of the network. An lp norm-based adversarial budget S (x) is defined as the set [x']]|x' - xIIp S c). x', z/(1) and z((+) represent the adversarial input and the corresponding pre- & nost-activations. For layer having n. neurons, we have ( E R xn. and (() E R
Throughout this paper, underlines and bars are used to present lower and upper bounds of adversarial
activations, respectively, i.e., z < z(() < z A "_" or subscript indicates the positive or negative part of a tensor. We use [K] as the abbreviation for the set {1, 2,., K).
2.2 MODEL LINEARIZATION
Given adversarial budget S(P) (x), we study the linear bound of the output logits z ((NN, given by
2

---

Under review as a conference paper at ICLR 2020
U +p(N)
(N) <z'M - v + (M))
(2)
The linear coefficients introduced above can be calculated by iteratively estimating the bounds of intermediate layers and linearizing the activation functions. Appendix [A.]] we discuss this for several activation functions, including ReLU, sigmoid, tanh and arctan. Note that our method differs from Zaang et al. (2018) because we need the analytical form of the linear coefficients for training, which removes numerical methods such binary search. The bounding algorithm trades off computational complexity and bound tightness. In this work, we study two such algorithms. One is based Fast-Lin CROWN (Weng al., 2018: Zhang al. 2018). It has tighter bounds but high computational complexity. Another is inspired by the interval bound propagation (IBP) (Gowal al. 2018), which is faster but leads to looser bounds. The details of both algorithms are provided in Appendices A.2 and A.3
We briefly discuss the complexity of both algorithms in Section 5
3 ALGORITHMS
3.1 ROBUSTNESS GUARANTEES BY POLYTIEDRAL ENVELOPE
For input point with label E [K], sufficient condition to guarantee robustness is that the lower bounds of 2, (N)
z, (N) are positive for all E [K]. Here, we use a trick called elision of the
((N) with the last linear layer last layer (Gowal et al., 2018 merge the subtraction of ((N) and z
and obtain the lower bound of z: ((N) z;
(N), (NN) - z (N) def U,x' + P Then, the sufficient Z
condition to ensure robustness within a budget s!P) (xx can be written as
(N) z, (NN) U,X' P 2 [
The constraint is trivial when i = c, so there are K - 1 such linear constraints, corresponding to K - hyperplanes in the input space. Within the adversarial budget, these hyperplanes provide polyhedral envelope of the true decision boundary. In the remainder of the paper, we use the term dic to represent the distance between the imput and the hyperplane defined in (3) and define de min die as the distance between the input and the polyhedral envelope boundary. The distance can be based on different ip norms, and djc- = when the input itself does not satisfy the inequality 3 Since
is sufficient condition for robustness given the adversarial budget s!P) (x), there is adversarial
examples in the intersection of s!P) (x) and the polytope defined in (3
The theorem below formalizes our robustness certification. We defer its proof to Appendix C.I
Theorem (PEC in Unconstrained Cases). Given a model f R" - [K] and an input point x with label let U and p in (3) be calculated using predefined adversarial budget S.P) (x). Then, there is no adversarial example inside an lp norm ball of radius d centered around x, with = min (c, ]
where dic = max 00
U.x+p 1ullle
}.
lg is the dual norm of the Lp norm, i.e., 1
1.
Based Theorem I when de, PEC has the same robustness guarantees KW (Kolter & Wong 2017). Fast-Lin (Weng et al., 2018 and CROWN (Zhang et al., 2018) we use the same model linearization method. When 0 < de < c, KW / Fast-Lin / CROWN N cannot certify the data point at all, while PEC still gives non-trivial robustness guarantees thanks to the geometric interpretability of the polyhedral envelope. Figure ((a] compares the certified bounds of KW / Fast-Lin and PEC randomly picked input for different values of e.
Figure I(b) shows a 2D sketch of the two cases mentioned above. If E is too small, as in the left portion of the figure, the linear bounds in (3) are tight but only valid in a small region s!') (x). Therefore, the certified robustness is most. If e is too large, the linear bounds are valid in larger region but more pessimistic because of linear approximation. [ This is depicted by the right portion of the figure, where the distances between the input and the hyperplanes are smaller and the certified robustness is then de. The hyperplane segments inside the adversarial budget (green lines) never exceed the decision boundary (dark blue lines). by definition of the polyhedral envelope.
'The value of dic monotonically decreases with the increase of e.
3

---

Under review as a conference paper at ICLR 2020
0.10
100
Corffed Boand
0.94
0.03
0110 1130
1635
0:30
(a) Certified Ls based bound of ran- domly picked input by PEC and KW Fast-Lin different values model is the 'FC1" on MNIST trained by "MM++at" in Croce ct al. 2018)
(b) 2D sketch of decision boundary (dark blue), hyperplane defined by (light blue), adversarial budget (red), polyhedral envelope (green) in PEC. The distance between the imput data and the hy- perplanes is depicted by yellow circle. The left and right portion correspond to de bigger and smaller than respectively.
The
Figure The two phases PEC algorithm.
To search for the optimal e, i.e. the peak in Figure ((a) Kolter & Wong (017) use Newton's 's method, which is an expensive second-order method. By contrast, Weng et (2018); Zhang et (2018) use binary search, and our PEC can accelerate their strategy. The acceleration comes from the partial credit when de < e, in which case we can rule out all values of below de and obtain better lower bound of the optimal e. A more detailed discussion is provided in Appendix B.]
Under many circumstances, the input is constrained a hypercube [r-(min), ,(mex)) For example, for images with normalized pixel values, attacker should not perturb the image out of the hypercube [0, 1| Because of this constraint for the attacker, the certified regions become larger.
To obtain robustness guarantees in this scenario, need recalculate dic, which now the distance between the input and the hyperplanes in (3) within the hypercube. The value of dic then is the minimum of the optimization problem
min ||
A
s.t. aA + bSO, A (min) A A (maz)
where, to simplify the notation, we define a U, b U,x + p. A (min)
(mii) and
the optimal A is an all-zero A (maz) p(max) -x x. When 0, the minimum is obviously
vector. In this case, either we cannot certify the input at all or even the clean input is misclassified. When b 0, by Hölder's ss inequality, aA + 2 - |ل + b, with equality reached when A and a are collinear. Based on this, the optimal A of minimum Ip norm to satisfy aA + b < 0 is
A
sign(a:) |a;
(5)
|
where sign(-) returns +1 for positive numbers and -1 for negative numbers.
To satisfy the constraint A (min) < A A (max), we use a greedy algorithm that approaches this goal progressively. That is, first calculate the optimal Â based on Equation (5) and check if the constraint A (minn) < A < A (maz) is satisfied. For the elements where it is not, we clip their values within [A (min). A [max)) and keep them fixed. We then optimize the remaining elements of A in the next iteration and repeat this process until the constraint satisfied for all elements. The pseudo-code is provided as Algorithm in Appendix B.2] The output of Algorithm i is the optimum of Problem (4). i.e., dic. We provide the proof in Appendix C.2 The certified bound this constrained case then min(e, d.) just as demonstrated by Theorem
3.2 GEOMETRY-INSPIREB REGULARIZATION
As in (Croce et al. 2018 we can incorporate our certification bounds in the training process so as to obtain more robust models. To this end, we design regularization term that encourages larger values of de- We first introduce the signed distance dua: when dic >> O, the clean input satisfies (3) and
4

---

Under review as a conference paper at ICLR 2020
dic dzes when die O, the clean imput does not satisfy (3) and there is no certified region; dic in this case is a negative number whose absolute value is the distance between the input and the hyperplane defined in 3/. If the input is unconstrained, we have dic = U Otherwise, following the notation 1
of dic sign(b)]lálln where A = arg min pl s.t. a + b = 0, A (min)) < A S (maz).
This problem can be solved by greedy algorithm similar to the one in Section 3.1
Now, we sort {d i0 as deoc I diie S ... S dix--e S de and then define the Polyhedral Envelope Regularization (PER) term, based on smallest T distances,
PER(X,
max
0,
(6)
1=0
Note that, following Croce et al. (0018). to accelcrate training, we take into account the smallest T distances. When dj.e 2 a, the distance is considered big enough, so the corresponding term will not contribute the gradient of the model parameters. This avoids over-regularizztion and allows to maintain accuracy on clean inputs. In practice, we do not activate PER in the early training stages, when the model is not well trained and the corresponding polyhedral envelope meaningless. Such "warm up" trick is commonly used in the deep learning practice (Gotmare et al. 2018).
Note that (2018). The only change w.r.t. the original PER consists of replacing die with d' the distance berween the polyhedral envelope and the adversarial example generated by PGD (Madry et al. 2017) instead of the clean input. We call the corresponding method aER+ar.
further incorporate PER with adversarial training in similar way to Croce et al.
Calculating the polyhedral envelope is expensive in terms of both computation and memory because of the need to obtain linear bounds of the output logits. To prevent prohibitive computational and memory overhead, we use the stochastic robust approximation of Wang et al. (2018a). For a mini-batch of size B, we only calculate the PER or PER+at regularization term for B < B instances sub-sampled from this mini-batch. Moosavi-Dezfooli et al. (2017) empirically points out the geometric correlation of high-dimensional decision boundaries near the data manifold. Thus, in practice, a B' much smaller than B provides good approximation of the full-batch regularization.
4 EXPERIMENTS
To validate the theory and algorithms above. we conducted several experiments on two popular image classification benchmarks: MNIST and CIFAR1O. 10. Each of these experiments can completed on a single GPU machine within hours. We will make the code and checkpoints publicly available.
4.1 TRAINING AND CERTIFYING RELU NETWORKS
As the main experiment, we first demonstrate the benefits of our approach over the fftte-of-thearre art training and certification methods. To this end,
the same model architectures as in Croce et al. (0018) Kolter& & Wong (2017): FC1, which is a fully-connected network with one hidden layer of 1024 neurons; and CNN, which has two convolutional layers followed by two fully-connected layers. For this set of experiments, all activation functions are ReLU.
We focus on training and certification method based model linearization and compare 7 different training schemes using 5 evaluation metrics under the same and fixed adversarial budgets. All the certification results here are one-shot results as the binary search for optimal e is not used. The training schemes are plain training (plain), adversarial training (at) (Madry et al.] 2017), KW (Kolter Wong 2017). MMR (Croce et al. 2018). MMR plus adversarial training (MMR+at) (Croce et al. 2018), and our PER and PER+at of Section 3.2 For certification, we compare Fast-Lin (Weng et al.
2018), KW (Kolter& & Wong 2017) and our PEC introduced in Section 3.1 KW algorithmically equivalent to Fast-Lin with elision of the last layer (Salman et al. 2019b). we consider them as one certification method. Based on the discussions in Section 3.1 all three methods have the same certified robust error, which is the proportion of the inputs whose certified regions smaller than the adversarial budget. Therefore, we report the clean test error (CTE), empirical robust error against PGD (PGD), the certified robust error (CRE I Lin), the average certified bound by Fast-Lin / KW (ACB
5

---

Under review as a conference paper at ICLR 2020
CTE (%)
PGD
CRE
ACB KW
ACH PEC
CTE (%)
PGID (%)
CRE
ACB
ACB
(%)
Lin
Lin
KW
PEC
(%)
(%)
MNIST FCI, ReLU,
U loos 6 =
0.1
MNIST FCI, ReLU,
12. = 0.3
plain
1.99
98.37
100.00
0.0000
0.0000
1.99
9.81
40.97
0.1771
0.2300
at
1.42
9.00
97.94
0.0021
0.0099
1.35
2.99
14.85
0.2555
0.2684
KW
2.26
8.59
12.91
0.0871
0.0928
1.23
2.70
4.91
0.2853
0.2892
MMR
2.11
17.82
33.75
0.0663
0.0832
2.40
5.88
7.76
0.2767
0.2845
MMR+at
2.04
10.39
17.64
0.0824
0.0905
1.77
3.76
5.68
0.2830
0,2880
PER
1.60
7.45
11.71
0.0883
0.0935
1.26
2.44
5.35
0.2840
0.2888
PER+at
1.81
7.73
12.90
0.0871
0.0925
0.67
1.40
4.84
0.2855
0.29
MNIST CNN, ReLU,
Jacy E
0.1
MNIST CNN, ReLU, 12, e
0.3
plain
1.28
85.75
100.00
0.0000
0.0000
1.28
4.93
100.00
0.0000
0,0000
at
1.02
4.75
91.91
0.0081
0.0189
1.12
2.50
100.00
0.0000
0.0000
KW
1.21
3.03
4.44
0.0956
0.0971
1.11
2.05
5.84
0.2825
0.2861
MMR
1.65
6.09
11.56
0.0884
0.0928
2.57
5.49
10.03
0.2699
0.2788
MMR+at
1.19
3.35
9.49
0.0905
0.0939
1.73
3.22
9.46
0,2716
0,2780
PER
1.44
3.44
5.13
0.0949
0.0965
1.02
1.87
5.04
0,2849
0,2882
PER+at
0.50
2.02
4.85
0.0952
0.0969
0.43
0.91
5.43
0.2837
0.2878
CIFARIO CNN, ReLU,
2/255
CIFARIO CNN, ReLU, 12, c
plain
24.62
86.29
100.00
0.0000
0.0000
23.29
47.39
100.00
0.0000
0,0000
at
27.04
48.53
85.36
0.0011
0.0015
25.84
35.81
99.96
0.0000
0,0000
KW
39.27
46.16
53.81
0.0036
0.0040
40.24
43.87
48.98
0.0510
0.0533
MMR
34.59
57.17
69.28
0.0024
0.0032
40.93
50.57
57.07
0.0429
0,0480
MMR+at 35.36
49.27
59.91
0.0031
0.0037
37.78
43.98
53.33
0.0467
0.0502
PER 39.21
50.98
57.45
0.0033
0.0038
34.10
52.54
63.42
0.0369
0.0465
PER+at 28.87
43.55
56.59
0.0034
0.0040
25.76
33.47
46.74
0.0533
0,0580
Table 1: Results for 7 training schemes and 5 evaluation schemes for ReLU networks. The best and second-bes results among robust training methods (plain and at excluded) are highlighted by dark gray and light gray.
KW) and by PEC (ACB PEC) on the test set. We do not report the certified bound by MMR CCroe al. 2018), because, in practice, it only gives trivial results. As matter of fact, Croce et (2018)
emphasize their training method and report certification results using KW and MIP (Tjeng et al.
2017). For methods that are not based on model linearization, such as IBP (Gowal et al. 200 8) and
CROWN-IBP (Zhang et al. 2019), we put more results and discussions in Table Appendix D
We downloaded the KW, MMR and MMR+at models from the checkpoints provided by [Croe et al.) (2018). To be fair, we use the same model linearization method for method. For CNN models, we use the warm up trick consisting of performing adversarial training before adding our PER or PER+at regularization term. The running time overhead of pre-training is negligible compared with computing the regularization term. We train all models for 100 epochs and provide the detailed hyper-parameter settings in Appendix D.I
We consider robustness in both the lac and la case, and the attackers are constrained to perturb the images within [0, 1jm1. Table 1 shows the results with the same adversarial budget used in Croce et al. (2018). Consistently with Section [.] our geometry-inspired PEC has better average certified bounds than Fast-Lin / KW given the same adversarial budget. For CIFARIO model against loc attack, there are 10% - 20% test points not certified by Fast-Lin / KW but have non-trivial bounds by PEC. Figure of Appendix s.2.]shows shows the distribution of these certified bounds. Among the training methods, PER PER+at give better performance in all cases than MMR MMR+at. When compared with KW, their certified robust error comparable, but PER+at has better clean test accuracy, particularly on CIFAR10. 10. In fact, PER+at maintains similar clean test error to adversarial training (at) while achicving competitive certified robust error. In other words, a model trained by PER+at is not over-regularized Appendix D.2. shows the parameter value distribution of models trained by KW/MMR+a//ER-an It is clear that parameters of PER+at models have the largest norms and thus better preserve the model capacity. The better performance of PER+at over PER, and of MMR+at over MMR, evidences the benefits of augmenting the training data with adversarial examples.
other training methods for provable robustness. Figure 6 of
Repository: htwp:///ww.........oooooooooooo.

---

Under review as a conference paper at ICLR 2020
To demonstrate the trade-off between clean test error and certified robust error, we evaluate our approach with differ- regularizer strength in (6). Figure 2 the results of PER+at in the l2 case for CIFARIO. When is small, PER+at becomes similar adversarial training (at) and has low clean test error but high certified robust error. As Y grows, the model increasingly regularized towards large polyhe- dral envelopes, which inevitably hurts the performance on the clean input. By contrast, the certified robust error first decreases and then increases. This is because training is nu- merically more difficult when 7 is too large and the model is over-regularized. The results of KW are shown horizontal dashed lines for comparison, which evidences that PER+at is less over-regularized in general than KW, with much lower clean test error for the same certified robust error.
70
Ener (N)
00-
10-1
IPP Value of
10'
Figure CTE and CRE for different val- ues of y in PER+at. The results of KW, for reference, are the horizontal dashed lines.
The experimental results of PER PER+at in Table I rely on the same model linearization methods as Fast-Lin KW. Since our framework is applicable to any linearization strategy, we present the results using IBP-inspired linearization in of Appendix [.2.2] Compared with Table II we find IBP- ins-inee linearization has competitive performance during training. although it leads to looser polyhedral envelope. addition, IBP-inspired linearization has less memory consumption and computational complexity, so it is suitable for machines of limited computational resources.
4.2 TRAINING AND CERTIFYING NON-RELU NETWORKS
To validate our method's s applicability to non-ReLU networks, we replace the ReLU function in FC1 with either sigmoid, or tanh, or arctan function. While WWog al. (2018) claim that their methods apply to non-ReLU networks, their main contribution is rather the extension of KW to broader set of network architectures, and their public code ( does not support non-ReL. U activations. Instead, we thus compare the average certified bound of CROWN (Zhang et al. 2018) (ACB CRO), which generalizes Fast-Lin to non-ReLU functions, with our PEC (ACB PEC). Since any linearization of
activation functions can be plugged in both methods f
we use the method in Appendix A.1
CTE (%)
PGD (%)
CRE Lin
ACB CRO
ACB PEC
CTE (%)
PGD (%)
CRE Lin
ACB CRO
ACB PFC
(%)
(%)
MNIST FCI, Sigmoid, loc,
0.1
MNIST FCI, Sigmoid, 12, c
0.3
plain
2.04
97.80
100.00
0.0000
0.0000
2.01
10.25
30.78
0.2077
0.2539
at
1.78
10.05
98.52
0.0015
0.0055
1.65
3.48
7.50
0.2775
0,2839
PER
2.29
8.44
15.75
0.0843
0.0908
1.19
2.36
7.08
0.2787
0,2849
PER+at
2.46
8.14
15.00
0.0850
0.0906
0.67
1.25
6.93
0.2792
0.2868
MNIST FCI, Tanh,
Loos
0.1
MNIST FC1, Tanh,
1a,
0.3
plain
2.00
99.57
100.00
0.0000
0.0000
1.94
16.46
61.66
0.1150
0.1789
at
1.28
8.89
99.98
0.0000
0.0001
1.36
3.02
12.35
0.2630
0.2735
PER
2.66
9.31
16.02
0.0840
0.0908
1.39
2.73
7.56
0.2773
0,2834
PER+at
2.73
8.45
14.99
0.0850
0.0907
0.81
1.76
11.80
0.2646
0.2745
MNIST FCI, Are
Tocs c
0.1
MNIST FCI, Are' Tan, 12,
0.3
plain
1.95
99.83
100.00
0.0000
0.0000
2.09
23.00
62.82
0.1115
0.1869
at
1.33
8.88
99.92
0.0001
0.0005
1.56
3.04
10.10
0.2697
0.2784
PER
2.78
9.55
16.75
0.0833
0.0904
1.42
2.66
7.81
0.2766
0.2828
PER+at
2.98
8.96
15.64
0.0844
0.0901
0.83
1.61
11.38
0.2659
0.2758
Table 2: Results of FC1 models with non-ReLU activation functions MNIST.
According Table 2 in contrast plain training and adversarial training, our PER / PER+at can train provably robust models, despite slightly lower performance on the clean test data. For certification, PEC has better average certified bounds than CROWN given the same adversarial budget.
Repossioor:: http:/gguuuhco/mouuulllhlaee
adversarial
Forr certification, there need require an analytical form of the linearization.
7

---

Under review as a conference paper at ICLR 2020
4.3 FINDING THE OPTIMAL BUDGET
To obtain the biggest certified bound, we need to search for the optimal value of 6, i.e., the peak in Figure [(a] While Kolter & Wong (2017) use Newton's 's method to solve a constrained optimization problem, which is expensive, Fast-Lin CROWN (Weng et al. 2018 Zhang et al. 2018) apply a binary search strategy to find the optimal e.
To validate the claim Section 3.1 that PEC can find the optimal faster than Fast-Lin CROWN, we compare the average number of iterations needed to find the optimal value given required precision cΛ. Using c and É to define the initial lower and upper estimates of the optimal value, then we need [log2 أ= steps of bound calculation to obtain the optimal value by binary search in Fast-Lin / CROWN. By contrast, the number iterations needed by PEC depends on the model to certify. The psdudo-code of the search algorithm is provided in Appendix [B.]]
We briefly discuss the experimental results here, and defer their details to Appendix D.2.3 Note that, because PEC has almost computational overhead compared with Fast-Lin and CROWN, the number iterations reflects the running time to obtain the optimal certified bounds. Altogether, our results show that PEC can save on average 25% of the running time for FC1 models with ReLU, 15% for FC1 models with non- ReLU activations and 10% for CNN models.
5 DISCUSSION
Let us consider an N-layer neural network model with k-dimensional output and m-dimensional input. For simplicity, let each hidden layer have neurons and n >> max,k: m]. ). In this context, the bounding algorithm based on Fast-Lin / CROWN need (NN2n FLOPs to obtain linear bounds of output logits. However, the complexity can be reduced ONN22 m)) at the cost of bound tightness when we use the -BP-inspired algorithm. In MMR (Croce et al. 2018). the complexity to calculate the expression of the input's linear region is also ONN"mm) On the training side, KW needs a back-propagan propagation to calculate the bound, which costs D(Nn)). MMR needs to calculate the distance between the input and (NN) hyper-planes, costing (NNm)) FLOPP,, while PER only calculates (kk) hyperplanes, thus requiring (kk)) FLOPs. Overall, can see that the estimation of the output logits or decision boundary dominates the complexity of all training algorithms and the main barrier towards scalable provably robust training. The complexity of PER is similar to Fast-Lin / CROWN if we use the same model linearization method as theirs. When we use an IBP-inspired algorithm instead, the complexity of PER is similar to MMR. Note that the FLOP complexity of PGD with h iterations is O(Nnh) and typically h & min(m, n),, so the overhead of the warm up phase is negligible for PER training.
No matter which linearization method we use, the bounds of the output logits inevitably become looser for deeper networks, which can be problem for large models. Purthermore, the linear approximation implicitly favors the Loc norm over other lp norms because the intermediate bounds are calculated in an elementwise manner (Liu et al. 2019). As result, our method performs better in loo cases than in la cases. Designing training algorithm with scalable and tight certified robustness highly non-trivial and worth further exploration.
CONCLUSION
In this paper, we have studied the robustness of neural networks from a geometric perspective. In our framework, linear bounds are estimated for the model's output under an adversarial budget. Then, the polyhedral envelope resulting from the linear bounds allows us to obtain quantitative robustness guarantees. Our certification method can give non-trivial robustness guarantees to more data points than existing methods. Furthermore, we have shown that our certified bounds can be turned into a geometry-inspired regularization scheme that enables training provably robust models. Compared with existing methods, our proposed framework can be applied to neural networks with general activation functions. Unlike many over-regularized methods, it can achieve provable robustness at very little loss in clean accuracy. Extending this framework to larger networks will be the focus of our future research.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples. arXiv preprint arXiv:1802.0042) 2018.
Jacob Buckman, Aurko Roy. Colin Raffel, and Ian Goodfellow. Thermometer encoding: One hot way to resist adversarial examples. 2018.
Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In 2017 IEEE Symposium on Security and Privacy (SP). pp. 39-57. IEEE, 2017.
Jeremy M Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. arXiv preprint arXiv: 1902.02918, 2019.
Francesco Croce, Maksym Andriushchenko, and Matthias Hein. Provable robustness of relu networks via maximization of linear regions. arXiv preprint arXiv:1810.07481, 2018.
Guneet S Dhillon, Kamyar Azizzadenesheli, Zachary C Lipton, Jeremy Bernstein, Jean Kossaifi, Aran Khanna, and Anima Anandkumar. Stochastic activation pruning for robust adversarial defense. arXiv preprint 1803v 01442, 2018.
Timon Gehr, Matthew Mirman, Dana Drachsler-Cohen. Petar Tsankov, Swarat Chaudhuri, and Martin Vechev. Ai2: Safety and robustness certification of neural networks with abstract interpretation. In 2018 IEEE Symposium on Security and Privacy (SP), pp. 3-18. IEEE, 2018.
Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. arXiv preprint vrXiv:1412.6577 2014.
Akhilesh Gotmare, Nitish Shirish Keskar, Caiming Xiong, and Richard Socher. A closer look at deep learning heuristics: Learning rate restarts, warmup and distillation. arXiv preprint
2018
Sven Gowal, Krishnamurthy Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Uesato, Timothy Mann, and Pushmeet Kohli. On the effectiveness of interval bound propagation for training verifiably robust models. arXiv preprint 1rXiv: 12715, 2018.
Chuan Guo, Mayank Rana, Moustapha Cisse, and Laurens van der Maaten. Countering adversarial images using input transformations. arXiv preprint arXiv:1711.00111 2017.
Warren He, Bo Li, and Dawn Song. Decision boundary analysis of adversarial examples. 2018.
Guy Katz, Clark Barrett, David L Dill, Kyle Julian, and Mykel J Kochenderfer. Reluplex: An efficient smt solver for verifying deep neural networks. In International Conference on Computer Aided Verification, pp. 97-117. Springer, 2017.
Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint 1rXiv:14/2.69880 2014.
J Zico Kolter and Eric Wong, Provable defenses against adversarial examples via the convex outer adversarial polytope. arXiv preprint arXiv:1711.0085: 1(2):3, 2017.
Chen Liu, Ryota Tomioka, and Volkan Cevher. On certifying non-uniform bound against adversarial attacks. arXiv preprint /9X3v 06603, 2019.
Xingjun Ma, Bo Li, Yisen Wang, Sarah M Erfani, Sudanthi Wijewickrema, Grant Schoenebeck, Dawn Song, Michael E Houle, and James Bailey. Characterizing adversarial subspaces using local intrinsic dimensionality, arXiv preprint arXiv:1801.02611 2018.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint arXiv:1706.00 06088, 2017.
Seyed-Mohsen Mlosavi-Dezzoool. Alhussein Fawzi, Omar Fawzi, and Pascal Frossard. Universal adversarial perturbations. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 1765-1773, 2017.

---

Under review as a conference paper at ICLR 2020
Aditi Raghunathan, Jacob Steinhardt, and Perey Liang. Certified defenses against adversarial examples. arXiv preprint arXiv:180100944. 2018a.
Aditi Raghunathan, Jacob Steinhardt, and Percy S Liang. Semidefinite relaxations for certifying robustness adversarial examples. In Advances in Neural Information Processing Systems, pp. 10877-10887, 2018b.
Hadi Salman, Greg Yang, Jerry Li, Pengchuan Zhang, Huan Zhang, Ilya Razenshteyn, and Sebastien Bubeck. Provably robust deep learning via adversarially trained smoothed classifiers. arXiv preprint urXiv:1996.04555 2019a.
Hadi Salman, Greg Yang. Huan Zhang. Cho-Jui Hsieh, and Pengchuan Zhang. A convex relaxation barrier to tight robust verification of neural networks. arXiv preprint arXiv: 2019b..
2019b.
Pouya Samangouei, Maya Kabkab, and Rama Chellappa. Defense-gan Protecting classifiers against adversarial attacks using generative models. arXiv preprint arXiv: 06055, 2018.
Gagandeep Singh, Timon Gehr, Matthew Mirman, Markus Püschel, and Martin Vechev. Fast and effective robustness certification. In Advances in Neural Information Processing Systems, pp. 10825-10836, 2018
Gagandeep Singh, Timon Gehr, Markus Püschel, and Martin Vechev. An abstract domain for certifying neural networks. Proceedings of the ACM Programming Languages, 3(P0PL):41, 2019.
Yang Song, Taesup Kim, Sebastian Nowozin, Stefano Ermon, and Nate Kushman. Pixeldefend: Leveraging generative models to understand and defend against adversarial examples. arXiv preprint arXiv: 10766, 2017.
Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties neural networks. arXiv preprint urXiv:1312.6199 2013.
Vincent Tjeng, Kai Xiao, and Russ Tedrake. Evaluating robustness of neural networks with mixed integer programming. arXiv preprint arXiv:/711.07336 2017.
Shiqi Wang, Yizheng Chen, Ahmed Abdou, and Suman Jana. Mixtrain: Scalable training of formally robust neural networks. arXiv preprint arXiv:1811.02622. 2018a.
Shiqi Wang, Kexin Pei, Justin Whitehouse, Junfeng Yang, and Suman Jana. Efficient formal safety analysis neural networks. In Advances in Neural Information Processing Systems, pp. 6367- 6377, 2018b.
Tsu Weng, Huan Zhang, Hongge Chen, Zhao Song, Cho-Jui Hsieh, Duane Boning, Inderjit S Dhillon, and Luca Daniel. Towards fast computation of certified robustness for relu networks. arXiv preprint arXiv: 1804.09699 2018
Eric Wong, Frank Schmidt, Jan Hendrik Metzen, and Zico Kolter. Scaling provable adversarial defenses. In Advances in Neural Information Processing Systems, pp. 14100-819, 2018.
Kai Y Xiao, Vincent Tjeng, Nur Muhammad Shafiullah, and Aleksander Madry. Training for faster adversarial robustness verification via inducing relu stability, arXiv preprint arXiv: Naw:1800.00000 03008, 2018.
Cihang Xie, Jianyu Wang, Zhishuai Zhang, Zhou Ren, and Alan Yuille. Mitigating adversarial effects through randomization. arXiv preprint arXiv: 1.09911, 2017.
Huan Zhang, Tsui- Tsui-Wei Weng, Pin- Yu Chen, Cho-Jui Hsieh, and Luca Daniel. Efficient neural network robustness certification with general activation functions. In Advances Neural Information Processing Systems, pp. 4944-4953, 2018.
Huan Zhang, Hongge Chen, Chaowei Xiao, Bo Li, Duane Boning, and Cho-Jui Hsich. Towards stable and efficient training of verifiably robust neural networks. arXiv preprint arXiv:1906.06316 2019.
10

---

Under review as a conference paper at ICLR 2020
A MODEL LINEARIZATION
A. LINEARIZATION OF ACTIVATION FUNCTIONS
In this section, we discuss the choice of / and in the linear approximation dr+ S. o < dx + for activation function a when I E [r, æj. Method used here is slightly different from Zhang et al. (2018). First, the slope of the linear upper and lower bound is the same for simplicity. Second, all coefficients need to have analytical form because we need to calculate the gradient based on them during training. Note that Zhang et al. (2018) use binary search for optimal d, I, h.
A.1.1 RELU
As Figure shows, the linear approximation for ReLU (Φ)) m0x x), which is convex, is:
I S & S 0
T
I オ< <<<
0,
I < 0 <
T
0 0srs#
< Ø 5 3
0
0-
-3
-3
-3
-3
(a) S r < 0
(b) x < 0
(c) 0 S
Figure The lincarization of RcLU function all scenarios.
A.1.2 SIGMOID, TANH, ARCTAN
Unlike ReLU function, Tanh function (xx) 2- Sigmoid function (xx = T4e-= and Arctan function (x) arclan(x) are not convex. However, these three functions are convex when a < 0 and concave when 0. (Left and right sub-figures of Figure 4) Therefore, when r S 0 or 0 S x S 3, we can easily obtain the tight linear approximation. When < 0 < F. we do not use the binary research to obtain the tight linear approximation like Zhang et al. (2018), because the results would not have analytical form in this way. Instead, we first calculate the slope between the two ends i.e. d a(E)-o(x) Then, bound the function by two tangent lines of the same slope d 8-2
(middle sub-figure of Figure
1.5
1.5
1.0
1.0
0.5
0.0
0.0
-0.5
-3
-0.5
-0.56
-3
0
3
-0.5
-6
-3
(a) 2
0
(b) 2 <
<
(c) 5
Figure 4: The lincarization of Sigmoid function in all scenarios.
11

---

Under review as a conference paper at ICLR 2020
For Tanh, Sigmoid and Arctan, we can calculate the coefficient of the linear approximation.
(a(1)) lid
H<0
To ( 2 - Ø
( o(x) d
(x(r) ro i
(8)
0s2sz
(122) 12d
0 < E
The coefficient 4 < <0< of 1 and i2 for different activation functions provided in Table
< l2 the position of tangent points both sides of origin. The definitions
Tanh
Sigmoid
Arctan
1 log id (d-2)-2v1-1
log
(2d
11+
2d
f2
1 log
(d 22-21
log
(2d 1)
v
2d
Table 3: Definition of ti and t2 for different activation functions.
A.2 BOUNDS BASED ON FAST-LIN / CROWN
Based on the linear approximation of activation functions above, we have D (1) + u where (+)) is diagonal matrix and 1((), ( are vectors. We can re-write this formulation as follows:
S {z <
3D 100 u Vz EZ 200,, 3m ( e ( s.t.z)))))))) (00000) + m (9)
We plug
9 into and the expression of z (+) can be rewritten as
0 = ()
b( b(.)...) (()))) + b (i-1)
WD 2) (...D ( (Wa)x + (0) + (2) + ((-2))
m (i-1)) + bb-l-))
[I ( w
wi D(N) 6
w (k) D() (())
w ()
(10)
This is linear function w.n. x' and (m Once given the perturbation budget ((P) (x) and the )=
bounds of [m])];=]
can calculate the bounds of z(()) and the bias term in (10). This process can
be repeated until we obtain the bound of output logits (2). The derivation here is the same as Weng
al. 2018) Liu al. (2019). encourage interested readers check these works for details.
A.3 BOUNDS INSPIRED INTERVAL BOUND PROPAGATION
Interval Bound Propagation (IBP) introduced in Gowal et al. (2088) is simple and scalable method to estimate the bounds of each layer neural networks. IBP much faster than algorithm introduced in Appendix A.2 because the bounds of any intermediate layer are calculated only based on the information its immediate previous layer. Therefore, the bounds are propagated just like the inference of network models, which cost only O(N) matrix-vector multiplications for N -llayer network defined in
In our work, need linear bounds of output logits in addition to general numeric bounds, so the linearization of activation functions defined in 99) is necessary. We define linear bounds U x
(i) < (i) U' (6), T (t) < (i) < ( + ( According to Section A.1
use the same slope to linearize activation functions, so the slopes of both bounds here are the same.
Plug (9) into this formulation, have:
O -D000 p0= - + 10, q()) - ( n
(11)
12

---

Under review as a conference paper at ICLR 2020
Here, we assume activation functions monotonic increasing, elements in D Similarity, compare the linear bounds of z and z((+1), we have:
are non-negative.
U(+ = p (011)
-
(1) P + w q() + bb q (++1)
-
w p
b
(12)
By definition, we have (()) = Land (()) = q()) = 0. Apply
11 and 12)
iteratively, we can obtain
the values of coefficients U(A), V(N), p (()) and q (M¹) in
B ALGORITHMS
B. ALGORITIMMS FOR SEARCH OPTIMAL
The pseudo code for finding optimal is demonstrated Algorithm M. x. EA, &, represent the classification model, the input point, precision requirement, predefined estimate of lower bound and upper bound respectively. Typically, ş set and é is set a large value which degree the image perturbation is perceptible. f is a function mapping model, an input point and a value of e to certified bound. a generalization form of algorithm Fast-Lin, CROWN, PEC etc.
During the search for optimal the lower bound is updated by current certified bound, while the upper bound is updated only when current certified bound is smaller than the choice of c. Fast-Lin and CROWN, we update either lower or upper bound in one iteration since the certified bound is either or current choice e. However, is possible for PEC to update both lower and upper bound in one iteration, which leads to faster convergence of e.
Algorithm 1: Search for optimal value of
Input: E, CA, f. M
Set the bounds c: Cup Clw =
while Eup Elow EA do
étry = ( Eup):
Ceert = [[M, x, ttry);
Update lower bound: fow max Clow Coert) then
if' Etry
Update upper bound: Etry'
end end
Output: (ELow + Eup)
B.2 GREEDY ALGORITHM IN CONSTRAINED CASES
We provide the pseudo code of greedy algorithm to solve problem as Algorithm 2 beloow.
To prevent prohibitive computational overhead, we set the maximum iteration number / (max) the while-loop. If this maximum number is met and the iteration is broken, then the output is lower bound of the solution problem (4) and thus still a valid but suboptimal robustness guarantee. In practice, set the maximum iteration number be 20, although the while-loop breaks within iterations in almost all cases.
C PROOFS
C.1 PROOF OF THEOREM 1
Proof. We let x' =x A be point break the condition
13

---

Under review as a conference paper at ICLR 2020
Algorithm 2: Greedy algorithm to solve Problem (
Input:
a, 6, A (min), A (maz) in and maximum iteration / (maz)
Set of fixed elements S(F)
Iteration number = O;
Calculate A according to
while A (min) Â S A (max) not satisfied and 7(maa) do
Set of violated elements S = { < A (min)
or Å > A (max)
};
Â clip( A min A (min) max A (maz)) s(D);
S(f) s(A) U
Update Á according to with elements in S(f) fixed;
Update i = + 1;
end
Output: | |pp
U,(x + A) + P
<0
U,A
< U,X Pi
|
< U - Pi
(13)
U +p:
|
|
The = comes from the Hölder's inequality.
13
indicates a perturbation of Lp norm over die
max fo, U is needed to break the sufficient condition of Zr: z (N) 2 0. Based on the IU.lle
(NN)
assumption of adversarial budget s! to produce an adversarial example is at least min {c, de).
(x) when linearizing the model, so the lp norm of perturbation
C.2 PROOF OF THE OPTIMALITY OF GEEDY ALGORITHM
Proof. We primal-dual method to solve the optimization problem 44. which is a convex opti- mization problem with linear constraints.
It is clear that there exists image inside the allowable pixel space which makes the model predict wrong label. That is to say, the constrained problem strictly feasible:
A s.l. aA + 0, A (min)
A A (maz)
(14)
Thus, this convex optimization problem satisfies Slater's Condition i.e. strong duality holds. We then rewrite the primal problem as:
min A (min)) <AC (max)
|
(15)
s.t. aA +
We minimize || instead of directly |||||p in order to decouple all elements in vector A. In addition, consider A (min) < A < A (maz) the domain of A instead of constraints for simplicity. We write the dual problem of (15) by introducing coefficient of relaxation À E R..
A (mms) A (mas) A(A,)) def |II I + A(aA + +B)
max X
min
(16)
14

---

Under review as a conference paper at ICLR 2020
To solve the inner minimization problem, we let the gradient do(A.)) be zero and obtain A; = -sign(a,, Aa.
ppln, + da to
0A;
Based on the convexity of function g X) w.r.t. A.
we can obtain the optimal A, in the domain.
Á clip -iig((())
da
p-
min
(min)))
A (maz)
(17)
Based on the strong duality, we can say the optimal Á is chosen by setting a proper value of X. Fortunately, |ا increases monotonically with X, so the smallest À corresponds to the optimum.
see, the expression of Â in is consistent with Á, in 7 if À is set properly. Greedy algorithm in Algorithm i the process to gradually increase À to find the smallest value satisfying constraint aA < O. With the increase of X, elements in vector Á remain unchanged when they reach either A (min) or A (marr) so keep such elements fixed and optimize the others.
As
D ADDITIONAL EXPERIMENTS
D.1 DETAILS OF EXPERIMENTS
D.1.1 MODEL ARCHITECTURE
FC1 and CNN network used in this paper is identical ones used Croce et al. (2018). FC1 network is a fully-connected network with one hidden layer of 1024 neurons. CNN network has two convolutional layers and one additional hidden layer before the output layer. Both convolutional layers have kernel size of 4, stride of 2 and padding of on both sides, so the height and width of feature maps are halved after each convolutional layer. The first convolutional layer has 32 channels while the second one has 16. The hidden layer following convolutional layers has 100 neurons.
1.1.2 HYPER- PARERRRR SETTINGS
In all experiments, we use Adam optimizer (Kingma & Ba 2014) with the initial learning rate 10-3 and train all models for 100 epochs with mini-batch of 100 instances. For CNN models, we decrease the learning rate to 10 for last 10 epochs. When we train CNN models on MNIST, we only calculate the polyhedral envelope of 20 instances subsampled from each mini-batch. When we train CNN models on CIFARIO, this subsampling number 10. For PER and PER+at, the value of T is always 4. We search in the logarithmic scale for the value of and in the linear scale for the value a. For the value e, we ensure its final values are close to the ones used
adversarial budget S(P) (x). We compare the constant values with exponential growth scheme for e but always constant values for and 7. The optimal value find for different settings are provided as below.
D.2 ADDITIONAL EXPERIMENTAL RESULTS
D.2.1 ADDITIONAL RESULTS OF THE MAIN EXPERIMENT
We show additional results including IBP (Gowal al. 2018) and CROWN-IBP (C-IBP) Zhang et al. (2019) in 5 We also report the certified robust error obtained by IBP (CRE IBP) and the corresponding average certified bound (ACB IBP). Consistent with Zhang et al. (201 we find IBP has non-trivial certification results only on models that are trained by IBP or CROWN-IBP For these models, IBP can have even better certification results than Fast- KW PEC, whose complexity are significantly higher. As mentioned in Liu et al. (2019), IBP and Fast-Lin are complementary. Our PER and PER+at algorithms still outperform IBP and CROWN-IBP.
'The power I when
15

---

Under review as a conference paper at ICLR 2020
a
initial value 0.0064 x2 every 20 epochs
MNIST - FC11, Loc
constant, 0.15
constant, 0.1
constant, 0.3 for PER constant, 0.03 for PER+at constant, 3 x 10-4 for PER constant, 1 x 10-3 for PER+at
MNIST - CNN, 3o
constant, 0.15
constant, 0.1
CIFARIO- CNNN 20
constant, 0.1
constant, 0.008
initial value 0.02
MNIST - FCI, l2
constant, 0.45
constant, 1.0
x2 every 20 epochs constant, 0.3
MNIST CNN, l/
constant, 0.45
constant, 1.0
constant, 0.3 for PER constant, 1.0 for PER+at
CIFARIO BE310-CNI CNN, l2
constant, 0.15
constant, 0.1
Table 4: Values of a, and y for different experiments.
CTE
CRE Lin
CRE
ACB KW
ACB IBP
ACB PEC
CTE (%)
FGD (%)
CRE
CRE
ACB
ACB
ACB
(%)
(%)
IBP
Lin
IBP
KW
IBP
PEC
(95
(%)
(18)
(%)
MINIST FCL, ReLU,
0,1
MNNST FCI, ReLU, la,
0.3
plain
1.99
98.37
100.00
100.00
0.0000
0,0000
0.0000
1.99
9.81
40.97
99.30
0.1771
0.0021
0.2300
1.42
97.94
0.0021
0.0000
0.0099
1.35
2.99
14.85
0.2555
0.0023
0.2684
KW
2.26
8.59
12.91
69.20
0.0871
0.0308
0.0928
1.23
2.70
4.91
41.55
0.2853
0.1754
0,2892
IBP
1.65
9.67
87.27
15.20
0.0127
0,0848
0.0705
1.36
2.90
6.87
9.01
0.2794
0.2730
0.2876
C-IBP
1.98
9.50
67.39
14.45
0.0326
0.0855
0.0800
1.26
2.80
6.36
8.73
0,2809
0.2738
0,2884
MMR
2.11
17.82
33.75
99.88
0.0663
0.0001
0.0832
2.40
5.88
7.76
99.55
0.2767
0.0013
0.2845
MMR+at
2.04
10.39
17.65
95.09
0.0624
0.0049
0,0905
1.77
3.76
5.68
99,86
0,2830
0.0004
0,2480
PER
1.60
7.45
11.71
92.89
0.0883
0.0071
0.0935
1.26
2.44
5.35
59.17
0.2840
0.1225
0.2888
PER
1.81
99.90
0.0871
0.0001
0.0925
4.84
64.79
0.2855
0.1056
1.2910
MNIST - CNN, ReLU,
Loc.
0.1
MNIST - CNN, ReT.U
la.
0.3
plain
1.28
85.75
100.00
100.00
0.0000
0,0000
0.0000
1.28
4.93
100.00
100.00
0.0000
0.0000)
0.000D
1.02
4.75
91.91
100.00
0.008
0.0000
0.0189
1.12
2.50
100.00
100.00
0.0000
0.0000
0.0000
KW
1.21
3.03
4.44
100.00
0.0956
0.0000
0.0971
1.11
2.05
5.84
100.00
0.2825
0.0000
0.2861
IBP
1.51
23.89
0.0761
0.0872
51.12
11.73
0.1534
0.2648
0.1669
C-IBP
1.85
4.28
10.72
6.91
0.0893
0.0931
0.0928
2.89
4.44
31.62
12.29
0.2051
0.2631
0.2178
MMR
1.65
100.00
0.0884
0.0000
0.0928
2.57
5.49
10.03
100.00
0.2699
0.0000
0.2788
MMR+aa
1.19
3.35
9.49
100.00
0.0905
0,0000
0.0939
1.73
3.22
9.46
100.00
0.2716
0.0000
0.2780
PER
1.44
3.44
5.13
100.00
0.0949
0.0000
0.0965
1.02
1.87
5.04
100.00
0.2849
0.0000
0.2882
PER
0.50
2.02
4.85
100.00
0.0952
0,0000
0.0969
0.43
0.91
5.43
100.00
0.2837
0.0000
0.2878
CIFARIO - CNN, ReI.U
2/255
CIFARIO - CNN, ReI.U
12,
0.1
plain
24.62
100.00
100.00
0.0000
0.0000
23.29
100.00
100.00
0.0000
0.0000
0.0000
at
27.04
48.53
85.36
100.00
0.001
0,0000
0.0015
25.84
35.81
99.96
100.00
0.0000
0.0000
0.0000
KW
39.27
48.16
53.81
99.98
0.0036
0.0000
0.0040
40.24
43.87
48.98
100.00
0.0510
0.0000
0.0533
IBP
46.74
56.38
61.81
67.58
0.0030
0.0025
0.0034
57.90
60.03
64.78
78.13
0.0352
0.0219
0.0366
C-TBP
58.32
63.56
66.28
69.11 10
0.0026
0.0024
0.0029
71.21
72.51
76.23
80.97
0.0238
0.0190
0.0256
MMR
34.59
57.17
69.28
0.0024
0.0032
40.93
$7.07
100.00
0.0429
0.0000
0.0480
MMR+at
35.36
49.27
59.91
100.00
0.0031
0.00000
0.00357
37.78
43.98
53.33
100.00
0.0467
0.0000
0.0502
PER
39.21
50.98
99.98
0.0033
0.0038
100.00
0.0369
0.0465
PEReat
28.87
43.55
56.59
100.00
0.0034
0,0000
0.0040
25.76
33.47
46:74
100.00
0.0533
0.0000
0.0580
Table 5: Full results of 9 training schemes and 7 evaluation schemes for ReLU networks.
The distribution of certified bounds of CIFAR10 model against t. attack are shown in Figure 6 We only consider the certified bounds strictly larger than 0 but smaller than c, which are nro-irivial bounds not obtained by one-shot Fast-Lin KW. For the CIFAR10 10 test set, there are 10% - 20% of such points, and their certified bounds are close to being uniformly distributed between 0 and e.
We show the histogram of parameter values for CIFARIO models trained by KW, MMR+at and PER+at. is clear that the parameter values of KW models are much more concentrated around 0 than those of +at models. For both 4 and l2 attacks, the PER+at model has the biggest norms, evidencing that it better uses the model capacity.
As can see in Equation 6 our proposed hinge-loss based PER is constant and does not contribute to the parameter update when de is greater than a. which is usually It means that when data point is robust enough against the adversarial attack, PER will not push the decision boundary further away from it. However, KW has cross-entropy based loss. It will always further push the output
16

---

Under review as a conference paper at ICLR 2020
Certried Sounds of CEAACU Model KM Attack
6-
Volio Centieer Boardh
Centried Sounds CIFACQU Model MMV Attadk
Camoiid Boands CIFARO Model Millt-ot Attace
Value Centhed Reamss
Witees Cort Board
Cartieed Bounds CIFABoo Modal by E'Eit Artaok
Certried Sounde of CEARRo Model Pill-at
Attack
11-
0061
Valuo
Centhee Beamds
Wilees
Figure Distributions certified bounds in (0, e) for CIFARIO models trained against loo attacks. The total numbers of such test points are 1045, 2162, 1396. 1122, 1489 for KW, MMR, MMR+at, PER, PER+at models, respectively.
Weight Ditritation CIARRO model apainst Artace
Weigh Dass bucio CIFARU2 mudd ageist Attack
MUR..u
PDR
0.5
0.
km
Viem
Figure Parameter value distributions CIFARIO models trained against loo and la attacks. The Euclidiean norm of parameter for KW, MMR+at, PER+at model against los attack is 18.08, 38,36 and 94,63 respectively. For models against l2 attack, the corresponding Euclidiean norm is 71.34, 62.97 and 141.77 respectively.
17

---

Under review as a conference paper at ICLR 2020
Optiral Born Datribution for CPARI Model agara: Attack
Optiral Scand Untrbetton for CIFARU Moed apandt to Aetsec
2.00
1.79
1.00
0.59
0.00
0.055
0.008
0X15
2005
0.08
0000
8.30
6.00
8.50
6.16
6.50
030
0.00
Figure 7: The distribution of optimal certified bounds of CIFAR1O models trained against loc and la attacks. The target bounds are marked as red vertical line. (2/255 for Loo cases and 0.1 for la cases.)
logits of the true label bigger and the others smaller. Figure 7 shows the distribution of optimal e found by Algorithm for CIFARIO models against lo and L2 attacks. Table Saale[shhee shows that KW and PER++a have similar certified robust error, which is the area on the right of the vertical red line in Figure 7 Because of the property of cross-entropy loss, KW pushes too many points far beyond the robustness target we set. This is unnecessary and causes the loss of clean accuracy.
D.2.2 TRAINING BY IBP-INSPIRED MODEL LINEARIZATION
We use ReLU networks to compare the performance of IBP IBP- inspired model linearization with the ones used Fast-Lin / CROWN. We observed that the hyper-parameter settings Table Jarle are ill-suited here. Specifically, since the estimation bounds of the output logits is looser, the gradient of the PER term based on IBP-inspired linearization is larger than the main experiments. As a result, we used value of 3 or 10 times smaller than those in Table 4 Furthermore, starting with a large might not work, because the bounds will be even looser under a big adversarial budget. So, we adopt a "warm up" scheme consisting of increasing the value of linearly until it reaches the desired value.
We provide the results in Table below. Note that we still use the tighter linearization method of Fast-Lin / CROWN when envelope during training, the IBP-inspired model lincarization achieves competitive performance with the ones in Fast-Lin CROWN. In some cases, has even better performance the test set. Because of the lower computational complexity and smaller memory consumption, the IBP-inspired method is suitable for machines with limited computational resources.
certification method (PEC). Despite the looser polyhedral
D.2.3 SEARCHING FOR THE OPTIMAL VALUE OF E
Tables 7 and g show the number of bound calculations in the binary search for the optimal in PEC and Fast- CROWN. In lox cases, the original interval ट] is [o, 0.4] for MNIST and [0, 0.1] for 10. In la cases, the original interval [c, ε is [0, 1.2) for MNIST and [0, 0.4] for CIFAR1O. The bound of the number calculation does not depend on the model in Fast-Lin / CROWN and is model-dependent in PEC as discussed in Section 4.3
18

---

Under review as a conference paper at ICLR 2020
CTE (%)
PGD (%)
Change (%)
CRE
Change (%)
ACB
Change
ACB
Change
(%)
KW
PEC
MNIST FCI, ReLU.
0.1
PER
1.60
6.28
-1.17
11.96
+0.25
0.0880
-0.0003
0.0934
-0.0001
PER+at
1.54
7.15
-0.58
13.19
+0.29
0.0868
-0.0003
0.0927
+0.0002
MINST CNN, ReLU,
loo. 6
0.1
PER
1.03
2.40
-1.04
4.64
-0.49
0.0954
+0.0005
0.0967
+0.0002
PER+at
0.48
1.29
-0.73
4.61
-0.24
0.0954
+0.0002
0.0971
+0.0001
CIEARTO CNN, ReLU,
lace 2/255
PER PER+at
29.34
51.54
+0.56
64.34
+7.11
0.0028
-0.0005
0.0036
-0.0002
26.66
43.35
-0.20
57.72
+1.13
0.0033
-0.0001
0.0040
0.0000
MNIST FC1, ReLU, 12, 0.3
PER PER+at
1.21
2.59
+0.15
5.34
-0.01
0.2840
0.0000
0.2888
0.0000
0.74
1.46
+0.06
7.81
+2.97
0.2766
-0.0089
0.2860
-0.0050
MNIST CNN, ReLU, 12,
0.3
PER PER+at
1.11
2.16
+0.29
6.37
+1.33
0.2809
-0.0040
0.2851
-0.0031
0.52
+0.21
7.89
+2.48
0.2763
-0.0074
0.2812
-0.0066
CIFARIÓ CNN, ReL.U, 12,
0.1
PER 33.94
43.06
-9.48
56,80
-6.62
0.0432
+0.0063
0.0484 0.0572
+0. +0.0019
PER+at 24.85
31.32
-2.15
47.28
+0.52
0.0528
-0.0005
-0.0008
Table 6: Results when using IBP-inspired model linearization. The color green, red and gray indicate better, worse and same results compared to those in Table
Tiin MNIST
TPCC
Tiin MNIST
TPEC
Tian CIFARIO CNN, ReL.U, 1oc
TP
Tyea:
FCI,
ReLU, 100
CNN, ReLUU,
plain KW
9.85
0.8207
10.56
0.8804
9.33
0.9331
10.77
0.8972
11.39
0.9489
9.12
0.9128
8.48
0.7066
11.61
0.9674
8.43
0.8432
MMR
8.04
0.6703
10.68
0.8897
8.05
0.8053
MMR+at
7.68
0.6402
11.22
0.9351
8.45
0.8450
PER
9.34
0.7780
11.17
0.9305
8.61
0.8606
PER+at
9.38
0.7816
11.74
0.9784
8.68
0.8681
MNIST FCI, ReLU, L2
MNIST CNN, ReLU,
CIFARIO CNN, ReLU,
plain
9.68
0.6914
13.64
0.9742
11.73
0.9775
10.44
0.7457
13.76
0.9829
11.67
0.9725
KW
7.72
0.5514
12.63
0.9021
10.23
0.8525
MMR
5,86
0.4186
8.52
0.6086
9.05
0.7542
MMR+at PER PER+at
5.91
0.4221
12.13
0.8664
10.33
0.8608
11.47
0.8194
13.75
0.9819
9.13
0.7609
11.34
0.8100
13.72
0.9796
10.71
0.8926
Table 7: Number of steps of bound calculation for the optimal in Fast- (Tii) and PEC (Trec) for ReLU networks. Note that Tian is constant for different models given the original interval Ee
Tcro MNIST
ТРЕС
Teec. Tero
TCrO
ТРЕС
Tee Teoo
ТPЕС MNIST FCI, AreTan, 7x0
TORO
IPeC
Tcro
FCI, Sigmoid, loo
MNIST
FC1, Tanh, los
plain PER
9.06
0.7547
9.69
0.8078
8,76
0.7304
10.92
0.9104
11.23
0.9356
11.19
0.9326
12
12
12
8.84
0.7369
9.02
0.7513
8.84
0.7369
PER+at
9.67
0.8060
9.64
0.8030
9.62
0,8020
MNIST
FCI, Sigmoid, l2
MNIST - FC1, Tanh, 12
MNIST
FC1, Are AreTan, 12
plain at
10.55
0.7534
10.96
0.7831
9.99
0.7134
11.83
0.8447
12.64
0.9032
12.30
0.8783
14
14
14
PER PER+at
12.09
0.8633
12.20
0.8717
12.08
0.8626
12.22
0.8728
12.50
0.8928
12.30
0.8786
Table 8: Number of steps of bound calculation for the optimal e in CROWN (TcRO) and PEC (Trec) for non-ReLU networks. Note that TeRo is a constant for different models given the original interval [e.
19


Reviews:
[{"review_id": "rklQ05jzqH", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes an approach for computing more refined estimates of robustness in comparison w/ existing linear approximation approaches that only give a yes or no answer with regard to robustness guarantees for a given lp-norm ball with radius epsilon. The nice thing is that as the linear-approximations get better, the contributions in this paper would continue to help. \n\nThe paper makes two key algorithmic/theoretical contributions:\n1. An approach to obtain a better estimate of the radius of the l-p ball where the NN is provably robust. This result is fairly straightforward, and relies on computing the distance of a point to the boundary of adversarial polytope.\n\n2. An approach to exploit the fact that the pixel values are restricted to specific bounds, which might allow us trim away some regions from the l-p norm balls around a given input image w.r.t which we want to be robust, while computing the robustness. This I think is a more interesting contribution. \n\n\nI am leaning towards a reject, however I am open to changing my score. I have several key concerns:\n\n1. Verified Training: Why is there no comparison with IBP and IBP+Crown (Zhang 2019) -- it seems like an appropriate comparison to make. Particularly, when the current paper refers and discusses both of the above works. \n\n2. I am not sure that comparison with CRO entirely suffices in my opinion. Would it be possible to compare with the tighter SDP based approaches (Raghunathan et al., NeurIPS'19 and Dvijotham et al., UAI'19)? Is there a specific reason to not compare (other than that the SDP based approach is not a linear approximation, and probably is much slower)? \n\nMy main concern here is the utility of pushing boundaries with the linear approximation, while there are potentially tighter relaxations?\n\n3. You claim no overhead compared to CROWN. Don't the greedy-optimization steps add some overhead, or am I missing something? How expensive are they? (It's possible I might have missed some discussion in this regard. If so, please point me in the right direction and that should suffice)\n\n4. Can you plot the distributions of the certified epsilon? Are there a few samples for which you can certify a much larger epsilon (than just saying not robust) or are there a lot of samples where you can only show a tiny bit of robustness (compared to CROWN saying not robust)? \n\nThe gains in the average robustness are somewhat small, and these gains alone are not convincing without being able to see how these gains were obtained. \n\nMinor Comment:\nMissing reference to MixTrain for B' < B helps. \n\nUpdate:\nThanks for the detailed response!\n\n1. This makes sense, the first bit seems obvious --> if you don't train with IBP, you won't get much out of IBP and this is reasonably well known. \n\nTable 5: When trained with IBP and verifying with IBP, it seems to do better or quite comparable to train/verify with PER --- in this sense, the gains seem quite marginal.\n\n2. Since a part of the contribution claimed in this paper is improved robustness guarantees for pre-trained networks, I do feel that comparisons with the UAI'19 paper or the NeurIPS'18 paper would be nice -- however, I do agree that the computational tractability of KW/FastLin/IBP are much more favorable.\n\n3. Thanks -- it is much more clear now.\n\n4. The distributions for MMR/PER seem quite similar and most of the gain seems to come at the lower end (small eps). \nThis still remains my biggest concern -- I was hoping that the distributions would diverge a bit more at larger eps, but this is difficult to confirm with the current set of plots.\n\nThese plots, as of the current version, are not very useful -- a CDF plot as opposed to a histogram would be much more illustrative in terms of comparing the different approaches. Overlaying them with different opacity might also be useful. \n\nI am still leaning towards a weak reject. I am not sure how the scoring system works, the scores are distributed unevenly -- I would judge this a 5 on the 1-10 scale. However, going by the wording, I will stay with a 3.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "Syx3S9paFr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\nThere exists several method (KW, Crown, zonotope transformers) which essentially propagate linear lower and upper bound through the network (bounds is a linear function of the input variables). So far, to check for robustness, these methods propagated the bounds until the last layer (+ margin computation) and then concretized them and compared the result to zero to see if the studied radius was safe or not. This paper highlights the fact that in the case where the studied radius is not safe, it is possible to extract a safe radius from the linear bound.\n\nThe authors then show that:\n-> this can be used to make binary search to find the larger verifiable epsilon faster (by providing a lower bound on epsilon even when failing to verify, rather than simply when succeeding verification)\n-> this can be employed during the training process to improve regularization, similarly to another previously proposed method (Croce et al.). While the methods are similar, the bounds are much less conservative than Croce's one and should therefore be more helpful\n\nThe presentation of the content is quite clear, and Figure 1.a is extremely useful in conveying the benefits of the method.\n\nExperimental validation is thorough:\n-> Comparing the ACB KW and ACB PEC columns in Table 1 and 2, for all type of activation functions, shows that this is as expected a strict improvement in the generated bound.\n-> Comparing the various rows in Table 1 shows the improvement with regards to other methods, both in terms of clean accuracy (this produces less over-regularization), while maintaining similar or better robust accuracy.\n-> Table 6 shows the benefit in the application to binary search.\n\nOpinion:\nThis paper is clearly written and I think that it's an interesting insight and that the authors do a good job at conveying its usefulness. I'm happy for this paper to be accepted.\n\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 carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "SJgClQwRKH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a certifiable NN training method, \"polyhedral envelope\nregularization\" (PER) for defending against adversarial examples.  The defense\nis based on the same linear relaxation based outer bounds of neural networks\n(KW/CROWN) used in many previous works.  The paper makes a few new (but small)\ntechnical contributions:\n\n1. this paper uses a different loss function (7), which is essentially Hinge\nloss on the lower bounds of distance to decision boundary. Previous works like\nKW used cross-entropy loss on the lower bound of prediction margin instead,\nwhich was based on minimax robust optimization theory. But I am not fully\nconvinced if the new loss function is better or not.\n\n2. in (5), the authors solve the bounded input case more carefully than\nprevious works.  (5) is trivial to solve in the L infinity case and has been\nused in previous works like (Wong & Kolter 2018, Gowal et al., 2018 and Zhang\net al., 2019); but solving it for other norms requires some efforts, and this\npaper proposes a good solution for it (Algorithm 2);\n\n3. In previous works like KW/CROWN, to find the largest certifiable radius, a\nbinary search is needed. The authors proposes a very small improvement to the\nbinary search process by setting the lower bound of search to the largest\nepsilon that is certifiable using the current linear relaxations obtained from\na larger epsilon.\n\nThe authors does not improve any bounds proposed in KW/CROWN, and they reuse\nthe same bounds. I see the main contribution as the new hinge-like loss\nfunction for training, and a more careful procedure to find the largest\ncertifiable radius in bounded input case.\n\nEmpirically, the improvement of the proposed algorithm is limited - based on\nTable 1 it is hard to say if PER is better than KW or not. PER+at outperforms\nKW sometimes, however it is not a completely fair comparison, as we can add a\nPGD based adversarial training loss to KW as well, as done in DiffAI (Mirman et\nal., https://github.com/eth-sri/diffai).\n\nQuestions:\n\n1. In my personal experience I usually found Hinge loss not as effective as\ncross-entropy loss in deep learning based tasks probably due to its\nnon-smoothness. The claim that (7) is better than cross-entropy loss is that it\ndoes not overregularize the network. The authors should provide more evidence\nto show if this argument holds, e.g., plotting the norm of weight matrices\nduring the training for the two losses to show that it can reduce\noverregularization.\n\n2. I think the metric ACB KW and ACB CRO (average certified radius of KW/CROWN)\nin Table 1 and 2 are confusing and not fair. In KW and CROWN's evaluation,\ngiving an epsilon, if an example cannot be certified due to epsilon to large\n(i.e., ||A|| \\epsilon + b > 0), certifiable radius will be count as 0 (flat\nline in Figure 1(a)). In this paper, the authors instead in this case use -b /\n||A|| as the certifiable radius. This is merely a different way of evaluation,\nand I don't see this as a contribution, as the \"improvement\" does not come from\na tighter bound.  In the same sense, I don't think Figure 1(a) and the\ndiscussions on page 3 are appropriate characterization of KW/CROWN. PEC uses\nexactly the same linear bounds as in KW/CROWN, and has the same certification\npower.\n\n3. For L2 based perturbations, in Table 1, the epsilon used for MNIST is too\nsmall. It is better to use an epsilon that is aligned with previous works. For\nexample in Wong et al., 2018 (https://arxiv.org/pdf/1805.12514.pdf), page 22,\nyou will find the epsilon used for MNIST and CIFAR.\n\n4. As discussed above, it is probably not fair to compare PER+at with KW. A new\nbaseline like KW+at should also be considered.\n\n5. For norms other than L infinity norms, solving (5) for getting $d$ can be\ntime consuming (Algorithm 2). How much additional time does it comparing\nto KW?\n\nOverall, I cannot recommend accepting this paper due to its limited theoretical\ncontribution as well as unconvincing empirical results comparing to previous\nmethods. I suggest rephrasing some parts of the paper and providing more\nexperimental results as discussed above.\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 carefully checked the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors develop a new technique for training neural networks to be provably robust to adversarial attacks. The technique relies on constructing a polyhedral envelope on the feasible set of activations and using this to derive a lower bound on the maximum certified radius. By training with this as a regularizer, the authors are able to train neural networks that achieve strong provable robustness to adversarial attacks.

The paper makes a number of interesting contributions that the reviewers appreciated. However, two of the reviewers had some concerns with the significance of the contributions made:
1) The contributions of the paper are not clearly defined relative to prior work on bound propagation (Fast-Lin/KW/CROWN). In particular, the authors simply use the linear approximation derived in these prior works to obtain a bound on the radius to be certified. The authors claim faster convergence based on this, but this does not seem like a very significant contribution.

2) The improvements on the state of the art are marginal.

These were discussed in detail during the rebuttal phase and the two reviewers with concerns about the paper decided to maintain their score after reading the rebuttals, as the fundamental issues above were not 

Given these concerns, I believe this paper is borderline - it has some interesting contributions, but the overall novelty on the technical side and strength of empirical results is not very high.
Decision: Reject