Towards Better Understanding of Training Certifiably Robust Models against Adversarial Examples
Authors: Sungyoon Lee
Woojin Lee
Jinseong Park
Jaewook Lee
Venue: NeurIPS 2021 Poster (2021)
Keywords: Adversarial Examples
Certified Robustness
Certified Defense
Certifiable Training
Loss Landscape
Deep Learning
Security

Abstract: We study the problem of training certifiably robust models against adversarial examples. Certifiable training minimizes an upper bound on the worst-case loss over the allowed perturbation, and thus the tightness of the upper bound is an important factor in building certifiably robust models. However, many studies have shown that Interval Bound Propagation (IBP) training uses much looser bounds but outperforms other models that use tighter bounds. We identify another key factor that influences the performance of certifiable training: \textit{smoothness of the loss landscape}. We find significant differences in the loss landscapes across many linear relaxation-based methods, and that the current state-of-the-arts method often has a landscape with favorable optimization properties. Moreover, to test the claim, we design a new certifiable training method with the desired properties. With the tightness and the smoothness, the proposed method achieves a decent performance under a wide range of perturbations, while others with only one of the two factors can perform well only for a specific range of perturbations. Our code is available at \url{https://github.com/sungyoon-lee/LossLandscapeMatters}.

Towards Better Understanding of Training Certifiably Robust Models against Adversarial Examples
Sungyoon Lee Korea Institute for Advanced Study (KIAS) sungyoonlee@kias.co re. kr
Woojin Lee Dongguk University-Seon xj9260dgu.ach ac.kr kr
Jinseong Park
Jaewook Lee Scoul National University jaewook@snu. ac kr
Scoul National Univeristy inseonggemu..a ac. kr
Abstract
We study the problem of training certifiably robust models against adversarial examples. Certifiable training minimizes an upper bound on the worst-case loss over the allowed perturbation, and thus the tightness of the upper bound an important factor in building certifiably robust models. However, many studies have shown that Interval Bound Propagation (IBP) training uses much looser bounds but outperforms other models that use tighter bounds. We identify another key factor that influences the performance of certifiable training: smoothness of the loss landscape. We find significant differences in the loss landscapes across many linear relaxation- based methods, and that the current state-of-the-arts method often has landscape with favorable optimization properties. Moreover, test the claim, we design new certifiable training method with the desired properties. With the tightness and the smoothness, the proposed method achieves decent performance under a wide range of perturbations, while others with only one of the two factors can perform well only for specific range of perturbations. Our code is available at /https://gttieei com/ weweoonnneeeeeseseeeeee hhengooooonn//sssssaaddeeeeeeee
Introduction
Despite the success of deep learning in many applications, the existence of adversarial example, an imperceptibly modified input that is designed to fool the neural network [34] 4. hinders the application of deep learning to safcty-critical domains. There has been increasing interest in building
model that is robust to adversarial attacks [4 26 23
43 T6 41 However, most defense
methods evaluate their robustness with adversarial accuracy against predefined attacks. Thus, these defenses be broken by new attacks
37
8
To this end, many training methods have been proposed build certifiably robust model that can be 15
guaranteed to be robust to adversarial perturbations [17 an upper bound on worst-case loss over valid adversarial perturbations and minimize to train certifiably robust model. These certifiable training methods can be mainly categorized into two methods and bound propagation methods. Linear relaxation based methods use relatively tighter bounds. but slow, hard to scale to large models, and memory- inefficient [39] 40 [ On the other hand, bound propagation methods, represented by Interval Bound Propagation (IBP), are fast and scalable due to the use of simple but much looser bounds 24 [5] One would expect that training with tighter bounds would lead to better performance, but IBP outperforms linear relaxation based methods, especially when the perturbation is large, despite using much looser bounds.
28 39
11
24
46 2 19]. They develop
types: linear relaxation-bass
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

These observations on the performance of certifiable training methods raise the following questions:
Why does certifiable training with tighter bounds not result in better performance? What other factors may influence the performance of certifiable training?
In this paper, we provide empirical and theoretical analysis to answer these questions. First, we demonstrate that IBP [15] has more favorable (smooth) loss landscape than other linear relaxation- based methods, and thus it often leads to better performance even with much looser bounds. To account for this difference, we present unified view of IBP and linear relaxation-based methods and find that the relaxed gradient approximation (which will be defined in Definition I of each method plays crucial role in its optimization behavior. Based on the analysis of the loss landscape and the optimization behavior, we propose a new certifiable training method that has a favorable loss landscape with tighter bounds. As result, the proposed method can achieve decent performance under a wide range of perturbations. We summarize the contributions of this study as follows:
We provide empirical and theoretical analysis of the loss landscape of certifiable training methods and find that smoothness of the loss landscape is important for building certifiably robust models, in addition the tightness of the upper bound.
We find that the relaxed gradient approximation of certifiable training method plays major role in shaping the loss landscape, determining its optimization behavior.
To verify our claims, we propose certifiable training method with tighter bounds and a favorable loss landscape. With the two key factors, the proposed method can achieve a decent performance under wide range of perturbations, while others with only one of the two can perform well only for specific range of the adversarial perturbations.
2 Related Work
Earlier studies on training certifiably robust models were limited to 2-layered networks 17 27 To scale to larger networks, a line of work has proposed the use of linear relaxation of nonlinear activation to formulate a robust optimization. Then, a dual problem is considered and a dual fcasible solution is used to simplify the computation further. By doing so. Wong and Kolter [39] built method that can scale to a 4-layered network, and later, Wong et al. [40] used Cauchy random projections to scale much larger networks. However, they still slow and memory-inefficien et al. 11 proposed a method called predictor-verifier training (PVT), which uses a verifier network to optimize the dual solution. This is similar our proposed method but we do not require any additional network. Similarly, a recent work called FROWN (2 used an optimizer to obtain tighter robustness certificates, but it focuses on efficient certification, not certifiable training. Xiao et al. [42 proposed to add regularization technique with adversarial training for inducing ReL.U stability, but it is less effective than other certified defenses.
Dvijotham
Mirman et al. 224] proposed the propagation of a geometric bound (called domain) through the network to yield an outer approximation in logit space. This can be done with efficient layerwise computation that exploits interval arithmetic. Over the outer domain, one can compute the worst- case loss to be minimized during training. Gowal et al. [15] used special case of the domain propagation called Interval Bound Propagation (IBP) using the simplest domain, the interval domain (or interval bound). They also introduced different objective function, heuristic scheduling on the hyperparameters, and elision of the last layer to stabilize the training and to improve the performance.
Both approaches, linear relaxation- based methods and bound propagation methods, use upper bound on the worst-case loss. Bound propagation methods exploit much looser upper bounds, but they enjoy an unexpected benefit in many cases: better robustness than linear relaxation-bais based methods. Balunovic and Vechev [2] hypothesized that the complexity of the loss computation makes the optimization more difficuut,, which could be reason why IBP outperforms linear relaxation-based methods. They proposed a new optimization procedure with the existing linear relaxation. In this paper, we further investigate the causes of the difficulties in the optimization. Recently, Zhang et al. proposed CROWN-IBI which uses linear relaxation in a verification method called CROWN in conjunction with IBP train a certifiably robust model.
46
45
Although beyond our focus here, there are other lines of work on certification with convex relaxation
38
31
33
32
45
5
29
22 35 10 48 and probabilistic certification called randomized smoothing

---

They focus solely on the tightness of the certified bounds. However, our work studies certifiable training from an optimization perspective.
20 18 7 44 25
Background
First, we provide brief overview of certifiable training methods. Then, we consider IBP 15] special case of linear relaxation-bass based methods. This unified view on certifiable training methods helps comprehensively analyze the differences between the approaches: bound propagation and linear relaxation. We present the details of IBP in Appendix B
3.1 Notations and Certifiable Training
We consider c-class classification problem with neural network [(;; 0) with the layerwise operations (*) (2(k-1) (k- .,... K) and the input 20))
X' The corresponding probability function is denoted by p = softmax o f X + [0, 1Je with subscript f. We denote subnetwork with k operations as h[k] = (2) o .... o h(1), For a linear operation (*),, we use W())
and (()) to denote the weight and the bias for the layer. We consider the robustness of the classifier against the corm-bounded perturbation set B(xx e) = (æ' E X | æ21 S E} with the perturbation level e. Here, we mainly focus on the -oo bounded set. To compute the margin between the
matrix Cyy) = I - 1e(w)" with (K) (mn 0, O.... c) 1). For the last linear layer, the weights (K) and the bias (k) are merged with C(y). that is, W(K) (C))W((K and b(K) = C(y)b(k), yielding the margin score function s(x, 0) C(y)f
true class y for the input and the other classes, define
(C)))=(K)) m = 2m Zy
f(=;0) fa 0)1 satisfying Pa Ps- Then we can define the worst-case margin score s" y, 0) = max (B(ccc s(x', y; 0) where max is element-wise maximization. With an upper bound 3 on the worst-case margin score, 2 s*, we can provide an upper bound on the worst-case loss over valid adversarial perturbations as follows:
L( e, 0),
max x'EB(n,))
((((x'))) 0)
for cross-entropy loss L [39]. We denote the empirical loss E(s,v) [C(3 0), y)] (0). Therefore, we can formulate certifiable training as minimization of the upper bound, ming L (0). instead of directly solving ming E(r,y) (max./ c(f(=';0) 0). y)] which is infeasible. Note that adversarial training [3] uses strong iterative gradient-based attack (PGD) to provide a lower bound on the worst-case loss to be minimized, but cannot provide a certifiably robust model. Whenever possible, we will simplify the notations by omitting variables such as y. e, and O.
3.2 Linear Relaxation- Methods
For a subnetwork I*], given with the pre-activation upper/lower bounds, u and for each nonlinear
activation function h in A((), linear relaxation-bais based methods [39 40 46) use a relaxation of the activation function by two elementwise linear function bounds, h and h, that is, h (z) < h(z) s h(x) for 1 < z < u. We denote the function bounds as π((z) O + b and h(z) a O z + b for some a. b, a. and b, where @ denotes the elementwise (Hadamard) product. Using all the function bounds h'' and h's for the nonlinear activations in conjunction with the linear operations in A 14), an äth (scalar) activation [x("]]
E: IR can be upper bounded by a linear function ni (.) g" +b over 45 This can be equivalently explained with the dual relaxation viewpoint
B (x, e) as in Zhang al.
in Wong and Kolter 33 Further details are provided in Appendix C Now we are ready to upper
bound the activation !/! over ((x,,)..
Definition (Linear Relaxation with Relaxed Gradient Approximation). For each neuron activation
(R) linear relaxation method computes an upper approximation of the activation over (B e) by using g E I and b R as follows:
max (2(2)))
h M
(2))
max g''x' + = g" + elglll + b. eBel))
(2)
We call g the relaxed gradient approximation of h [M]
over B(x,e).
3

---

Similarly. we can obtain the corresponding lower bound. Inductively using these upper/lower bounds on the output of the subnetwork, we can obtain the bounds for the next subnetwork h l and then for the whole network The final bound on the whole network can then be used in the objective (1). The tightness of the bounds and ((s. y) highly depend on how the linear bounds h and h are chosen in each layer.
Unified view of IBP and linear relaxation-based methods IBP can also be considered as linear relaxation-based method using zero-slope (a = a = 0) linear bounds, T(()) = ut and h+() = I+, where vF max(v, 0) and v min( v, 0). Thus, the bounds of nonlinear activation depend only on the pre-activation bounds u and & for the activation layer, substantially reducing the feed- bowaad/backproppgation computations. CROWN-IBP (46) applies different linear relaxation schemes to the subnetworks and the whole network. It uses the same linear bounds as IBP for the subnetworks h(a] for k- K except for the network
h( itself, and uses R())) ) u ut-
++
(z 1-) and
h(z)) = 1 Iut + t
> 0] @ z for the whole network 8. Moreover, CROWN-IBP uses interpolations
between two bounds with the mixing weight B, the IBP bound and the CROWN-IBP bound, with the following objective:
C
IBP (æ, E; 0) + B8 CROWN IBP (x, :; 0).
(3)
CAP 39 40 uses the linear bounds h(z) - + 1-) and h(z) -+- C z for all
subnetworks 144 and the entire network. As CAP utilizes the linear bounds for each neuron, is slow and nemmory-nefficient. It can be shown that tighter relaxations on nonlinear activations yield tighter bound on the worst-case margin score s". To specify the linear relaxation variable & = {a. o. 6, b} used in relaxation, we use the notation s(x, y, c; 0, Φ) with &. CROWN-IBI and CAP generally yield much tighter bound than IBP. These relaxation schemes are illustrated in Appendix D
4 What factors influence the performance of certifiable training?
One would expect that a tighter upper bound on the worst-case loss in (1 is beneficial in certifiable training. However, several previous works have shown that this is not the case: IBP performs better than linear relaxation-basel methods in many cases while utilizing a much looser bound. We investigate the loss landscape and the optimization behavior of IBP and other linear relaxation-base methods, and find that the non-smoothness of the relaxed gradient approximation of linear relaxations negatively affects their optimization, Detailed settings are presented in Appendix A
4.1 Loss Landscape of Certifiable Training
We empirically show that CROWN-IBE IBP [46 and CAP [39] tend to have non-smooth loss landscapes, which hinder optimization during training. We examine the learning curves of IBP and these methods. For simple analysis on the relation between their optimization and the lincar relaxation they used, we avoid considering the mixture of the two logits in (3), and use B = 1 to consider the CROWN-IBP logit only. Later, we will discuss how 8-scheduling affects the optimization. Figure ① shows the learning curves on CIFAR- 10 under Guain = $/255. We use q-schedulingg with the warm-up (regular training, 6, 0) for the first 10 epochs and the ramp-up (0 S 4 S Grain) during epochs 10-130 where we linearly increase the perturbation radius e, at iteration from O to the target perturbation Errin- Thus, the training loss may increase even during learning.
In the early phase of the ramp-up period, in which the models are trained with small et, CAP and CROWN- IBP have lower losses than IBP expected because they use much tighter relaxation bounds than IBP. This is consistent with the known results, that CAP tends to outperform the others at small perturbations, such Euain 2/255 on CIFAR- 10 (see Table I for details). However, at the end of the training, when the perturbation reaches its maximum target value (Grran = 8/255), the opposite result is observed where CAP and CROWN-IBP (3 1) perform worse than IBP.
To understand this inconsistency, we measure the variation in the loss value along the gradient direction (zeroth-order smoothness) as in Santurkar et al. (30, which is represented as the shaded region in Figure T We find that linear relaxation-based methods have large variations, while IBP maintains small variation throughout the entire training phase. It is known that smooth loss

---

DP
CROWN-IBP (3 =0=1)
CAP
LOURS
begiming
01. darkkecin
7519
73.01
Coline 950-8 6od Dfforesce
2,00
0.01
0.00
1.50
IBP
CROWN-IBP (8 [8=1]
CAP
0.50
10
20
40
50
50
70
10
90
120
110
120
330
10
100
150
200
Epoch
Epoch
CROWNIB (8
OURS
Figure 1: Left: The learning curves for the scheduled value of with the loss variation along the gradient descent direction. The vertical line indicates when the ramp-up ends. IBP starts with a higher loss but ends with a relatively lower loss (error), demonstrating smaller loss variations. Our method uses tight bounds like CROWN-IBP, while its landscape is as favorable as IBP, achieving the best performance among these four methods. We also provide train loss at the beginning and test error at the best checkpoint for the certifiable training methods in the top table. Right: Non-smoothness measures of the loss landscape between the certifiable training methods. Lower is better. (Top) Loss variations along the gradient descent direction, (Middle) di-distance between two consecutive loss gradients and (Bottom) the cosine distance between them during the ramp-up phase. Note that they are evaluated with the scheduled value c;.
landscape with small loss variation induces stable and fast optimization with well-behaved gradients 30), which will be discussed in detail in the following section. Therefore, even though CAP and CROWN-IBP (3 1) show better robustness in the early phase of training, the non-smooth loss landscape in the ramp-up up period hinders the optimization, yielding less robust models.
Non-smoothness
measures of loss landscape Next, we further investigate the smoothness of the loss landscape establish a relationship between the optimization behavior and linear relaxation. Figure [ (Right, middle and bottom) shows the difference between two successive loss gradient steps during training in terms of fz- and cosine distance, respectively. We observe that some linear relaxation methods have less smooth loss landscapes with unstable gradients, especially in the early stage of CAP and the middle stage CROWN-IBP (B = 1). Moreover, since the gradient directions are not well-aligned, they may not enjoy the advantages of momentum-based optimizers and be sensitive to the learning rate. As will be discussed the following section, we find that the loss landscape is highly related to the relaxed gradient approximation g used in linear relaxation.
4.2 Smoothness of Relaxed Gradient Approximation
In this section, investigate the optimization behavior further from theoretical perspective to answer the question: "What makes some loss landscapes more favorable than others?" We find that the relaxed gradient approximation of a linear relaxation affects the smoothness of the landscape. Before that, in the following theorem, we first look at the relation between the optimization and the smoothness of the loss landscape in terms the Hessian of the loss function with respect weight parameters. We defer the proof to Appendix F
Theorem 1. With gradient descent using step size within an interval Iç during the ramp-up period (0 S 4 < <), the loss L for the targel perturbation is reduced with
(9(0+1) 5L (0.)
μ cos? (be) ( HH
2
for u, = (OL)((0))
[o and H; satisfies L. ('041)) = (0.) (.. A and AT H; with A, 0.+1 O.. A
(0)11 where 0 < p < 1 cos(Oi) = VocSTVoLs
26
Here, a is modified Polyak-Lojjsiewicz (PI.) constant which is important for the optimization together with the Hessian term [H u,
B 21 In this paper, we mainly focus on the Hessian
5

---

term. Note that Hj = (0, is the Hessian of L at some O, between O and 0c+1- Thus, since A, T/e V C. (0.) with the learning rate T), we can approximate
|Hl & |HA
(o VoL
(5)
Therefore, it optimizes better with a smaller loss gradient difference (first-order smoothness).
To see what factors influence the loss gradient difference, first need some mild smoothness assumptions that are natural when the network parameters 01 and 02 are close to each other, especially they are two consecutive parameters from gradient descent update, i.c., O, and 0(+1.
Assumption 1. Given a linear relaxation method, make the following assumptions the bias b( 0) in the linear relaxation (2) and the probability function p(:; 0): (i) || Vab(w;; 02) V Vab(z: ax;
01)l L 02 01ll and
(ii) |p(a; 02) p(=; S L 1 0 ll. v0,, O2 and
With the above assumptions, we can provide an upper bound on the loss gradient difference for linear telaxation-based methods understand the optimization behavior follows:
Theorem 2. Suppose a E X' is bounded ||==|| S M with some M > O. For linear relaxation based
method with the upper bound 8m (a;; 0) maxx'eB(a.e) 9o (m)) (x) ) x' + 1(m)) (x:), if each ((m) and Ps satisfies Assumption 1, then
VVL (02) - (o.)(1))1
S (a max (2e V oog, (m) (m) (x)]l + M M/MMM/oooe
Voge, (m)) (m) (x))
Voge, (m) (a:) + I, T, 01ll)]
(6)
m
for any 0,, 02 where L (m) Lgg + 18 V ( 01,2) and 01,2 can be any of 01 and 02.
According to Theorem 2 the relaxed gradient approximations g ((m) in the linear relaxation play major role in shaping the loss landscape. The first two terms in the right hand side of (6) indicate the zeroth- and first-order smoothness of the relaxed gradient approximation with respect to weight parameters, respectively. The smoother the relaxed gradient approximations are, the smoother the loss landscape is. Especially for IBP, using the zero-slope relaxed gradient approximation g (
for all m, the loss gradient difference is upper bounded by only the last term, max (T)) [m0) 0, ll- and it is relatively small for a single gradient step. On the other hand, for other linear relaxation- methods using non-zero relaxed gradient approximation (mm) + O, the gradient updates used the training are more unstable than IBP. It is consistent with the empirical results shown in Figure I that
there are significant differences between the loss landscape of IBP and others.
5 Proposed Method
Our analyses so far suggest that not only tightness of the upper bound the worst-case loss but also smoothness of the loss landscape is important for building a certifiably robust model. Therefore, we aim design a new certifiable training method to improve the aforementioned factors (favorable landscape and tighter bound).
Favorable landscape with smooth g via sparse a To have smooth loss landscape, we aim to build a linear relaxation with a smooth relaxed gradient approximation by using sparse a. For example, in a simple 2-layered network case with sm (x) = w" h (W + b) + b, we have g (m) = W (a @
w + w and | (Vgg(m) = diad(aa(aa a ww < 0] 201 2 O) < | (|aa++
where diag(v) is the diagonal matrix whose entries are the elements of v. This simple example implies that a sparse a may help to smooth the relaxed gradient approximation.
To this end, we investigate variants of CROWN-IBP with different settings for unstable ReLUs to see their effects on the smoothness of the loss landscape. For each setting, we sample a E (0, 1} with for each neuron with pre- activation bounds and u. For example, CROWN-IBP uses (p, q) = (0, 1). We use a = 1 [ut +1= 0f for the other stable ReLUs. We consider the variants (p. q) = (0, 0), (0, 0.5), (0, 1), (0.5, 1), and (1, 1). in order of decreasing the sparsity. For the other elements of the linear relaxation variable
different (p, q) with P(a = 1 [|] > lul)
and P(a = 1 ||| S (u])
{(a, b. b)}. we fix -
=- and b 0 for each activation node, because w

---

1.00
0.75
10
0.55
Hio
OURS
1.00
0.89
0.00
20
43
60
30
60
160
210
120
130
Epo07
0.50
110 150
Epoch
Figure 2: Left: The non-smoothness measures of the models with different levels of sparsity of during the ramp-up period (same as in Figure (Right)). Notation (p. g) denotes the variant with sampling
(0, } with P(a ReL.Us. As a becomes sparse, the loss landscape is much smoother. Right: The configuration of a used for unstable ReLUs during the ramp-up period. It indicates that the proposed method reduces the number of nonzero a (purpletyellow).
> (ul) and P(a |/] S [u]) y for unstable
they are the optimal choices for tightening the bound (see Appendix C.2 for details). As expected, Figure (Leff) shows that tends to have a more smooth landscape as a becomes more sparse.
However, the sparsity only is not enough to achieve robustness unless the tightness is guaranteed. A variant of CROWN-IBB with (p, q) = (0, 0) achieves a favorable landscape, but they show looser upper bounds which lead to worse performance (details presented in Appendix E). Therefore, is required to search for appropriate a that can achieve both tightness and favorable landscape.
Tighter bound via optimization Now, we aim to make a sparse and to tighten the upper bound in ①. simultaneously. We can achieve both by minimizing the upper bound over the linear relaxation variable & follows: L(B(x)) 2 min ((3(x; Φ)) > m (((xx)). It can be equiva- lently understood as solving the dual optimization in CAP rather than using a dual feasible solution. However, solving the dual optimization is computationally prohibited for the linear relaxation of CAP. To resolve this problem, we use the same linear relaxation as IBP for the subnetworks except for itself, similar to CROWN-IBP Further, efficiently compute surrogate of the minimizer a arg minl, ((;(w;; Φ {(a, a, b, b)) using the one-step projected gradient update of the relaxation variable a for unstable ReLUs. Specifically, we have
à = [[ (ao rysign( V ((3(x:
with initial variable Φo { Cg. b, b)} where ag U10, 1|"d and 1, yielding the final objective [(s(x;; ()) where ob ((a, à b, b)).
The update (7) implicitly leads to a sparse à since the update direction tends to be negative for unstable ReLUs. We get the motivation from the relaxation of CROWN-IBP explained in Appendix
C.1
By tracking the sign of each element in computing the update direction, we can conclude yields sparse á. When computing the upper bound the lower slope
[0, 1]" is multiplied with non-positive w < 0, which yields w, 2 < O, and thus the preactivation value z; is likely to be (close to) the lower bound I, to maximize the value Ej W for the element j s.t. wy < O. Thus, 3m = wj 1 2 0. Thus, when projected onto [0, 1]", the update direction, -nssinn( V ((((;; Φo), v)) -nsiin( Pm V Va is likely to yield sparser á than CROWN-IBP (cf. Appendix F). Similar logic applies to the inner layers.
that
6 Experiments
In this section, we demonstrate the proposed method satisfies two key criteria required for building certifiably robust models: 1) tightness of the upper bound the worst-case loss, and 2) smoothness of the loss landscape. Subsequently, we evaluate the performance of the method by comparing with others certifiable training methods. Details on the experimental settings are in Appendix A
7

---

3.0
Tightrass
2.0
OUAS
CROWN-IB
CAP-IBP
RANDOM
DUNS
CROWNN-E
CAI-UP
RAN.DOM
Figure 3:
Violin plots of the test loss (Left) and of tightness (Right) for various linear relaxations. Lower is better. This shows that the proposed relaxation method has tighter bound than the others.
Table 1:
Test errors (Standard PGD/ Verified error) of IBP, CROWN-IBP (B 1), CAP, and OURS. Bold and underline numbers are the first and second lowest verified error. We use two different models (Shallow/Deep) for CIFAR-10 detailed in Appendix
Yuoa (
IBP
CROWN-IBP
CAP
OURS
1.18 3.52
1.07 (.69/ 2.10
9.0/1..333.1
1.79 2,336
0.2
2.00/ 3.29 6.31
2,99 5,50 77.97
3.22 6.72 11.06
1.70/3.44 /434
MNIST
0.3
5.85
10.45
5.73/ 10.76 16.28
19.19 35.84 47.85
/ 99.79
0.4
3.50/7.30/
17.96
5.73 14.63 23.80
3,49 6.77 15,42
3/255
37.98
55.39
32,48 42.77 50.15
28.80 / 38.95 / 48.50
31,49 42.73 49.42
4/255
4
62.80
45.56 58.24 64.47
40.78 52.62 61.88
42.53 55.55 61.52
CIFAR-10
6/255
$2.84 63.92/ 68.79
54.72 65.28 71.04
49.20 60.85 69.03
50.19 61,88 66.90
(Shallow)
$/258
55.71 66.1//6,7799 66.79/ 70.95
61.37
70.66 75.37
56.77 66.78 73.02
56.01 / 66.17 69.70
19/258
67.10/75.12 78.26
76.65 8190 84.42
75.11 80.67 82.07
65.93 / 75.39
CIFAR-I0
4/266
39.17 09.17/48.800 55.48
29.02 40.17 46.22
31.48 / 42.52 44.889
(Deep)
8/266
59.53 65.98 70,86
59.43 65.79 73.34
50.78 / 62.58 68.44
SVHN
0.01
19.91 / /3.12/ 43.83
17.25/30.5 39.88
16.88 /0. 37.09/
16.41 30.43 39.44
validate that the proposed method (OURS) has sufficiently tight bounds, we analyze various linear relaxation methods Figure 3 We define a tightness measure as Em= 8 (zx). Then, we evaluate multiple methods single fixed model pre-trained with the proposed training method. The compared methods are, from left to right, OURS, CROWN-IBP CAP-IBP, and RANDOM. All methods the same IBP relaxation for subnetworks, but different linear relaxation variables a for the whole network s. CROWN-IBP, CAP-IBP, and RANDOM use a = 1[u + > 0.
Tightness
- and 000 1]", respectively. We fix the other variables b. and b, as in Section 5 In both figures, our method shows the lowest value average, which indicates that a single gradient step sufficient to obtain tighter bounds. See Appendix M other models.
Smoothness Figure (Right) shows that method has successfully yielded more sparse than CROWN-IBP (3 = 1). This leads to the results shown in Figure [ (Right) that the proposed method has smooth loss landscape with IBP, whereas the others have less smooth ones.
Certified Robustness We evaluate the performance of the proposed method and compare it to
other certifiable training methods: IBP [15], CROWN-IBP (3 1) (46), and CAP (40) in Section
4.1] On MNIST, we follow Zhang et al. 44 and use étain 2 ftest' whereas for CAP, we use the same
Strain Ejss which yields better results. We used three evaluation metrics: standard (clean). 100-step PGD, and verified error. For the verified error, evaluated with the bound 3 of each method.
Table summarrizs the evaluation results under different Eest for each dataset. In general, when Ejest is low, methods with tighter linear relaxations show good performance, whereas IBP tends to perform better as Gest increases. In short, the current SOTA methods perform well for specific range of
Gest- For example, IBP shows relatively better performance in the case of = 0.3, 0.4 on MNIST and étea = 6/255, 8/255, 16/255 on CIFAR-10 10. On the other hand, CAP and CROWN-IBP (3 1) outperform IBP in the case of fest = 0.1 on MNIST, étest 2/255 on CIFAR-10 and étes = 0.001 on SVHN. This result is consistent with the analysis shown in Figure that CAP and CROWN-IBP (3 1) have lower loss than IBP at small but their loss landscape is less smooth than IBP, leading

---

Table Test errors (Standard / Verified error) compared to the best errors reported in the literature. Bold numbers are the lowest verified enror. The results in RS [42 and COLT 2 are evaluated with MILP based exact verifier 36
Data
MNIST
CIFAR-10
(/er(/o0)
0.1
0.3
2/255
8/255
RS
1.377487
2.77
38,887 54.07
59.55 / 79.72
DHfAA
1.3/4.2
3.4/ 10.7
/
53.8 / 72.8
COLT
0.8/2.
14,3
2166339.5
48.3 / 72.5
OURS
1.09/
2.42/784
31.48 /47.89
50.78 / 68.44
to worse performance at large Moreover, CAP cannot be trained on MNIST when Guain = 0.4. As the case also not specified in Wong et al. 40. seems that CAP is hard to be robust to Erain 2 0.4. On the other hand, the proposed method shows consistent performance in a wide range of freat values, achieving the best performance in most cases, since has tighter bounds and a favorable landscape, not overfitting on the hyperparameters in Appendix J
local minimum during the E-scchduu,nng We also conduct additional experiments and
We also compared our method with other prior work, ReLU Stability (RS) [42]. DiffAl [24] and COLT 2] Table 2 All experiments and results, except for Table 2 in this paper are based on our own reimplementation The proposed method shows the best verified error, except for the case Gest 2/255 on CIFAR-10, 10, in which COLT performs better. This is because COLT is based on the linear relaxation used in CAP.
Unlike standard training, certifiable training requires e--scheduling. It is implicitly assumed of weights that makes the network robust to a small e, is a good initial point to learn robustness to a large Erain- However, training methods with tighter bounds start with lower loss at a small er, but with an unfavorable loss landscape, they cannot explore a sufficiently large area of the parameter space. Hence, they overfit to be robust to a small perturbation, and cannot generalize to a large perturbation. CAP and CROWN-IBP (3 1) are typical examples that demonstrate the overfitting. This may overegularize the weight norm and decrease the model capacity 440 46). The tightness of the proposed method improves the performance for small Grain. while the smoothness helps the optimization process, which also leads to better performance for large érain conclude, the proposed method can achieve a decent performance under wide range of perturbations.
7 Discussion
proper 3-scheduling in (8) could help the model to obtain smoother landscape and improve the robustness performance. We use two different settings of B, CBP1-1 and CBP1-+0 where CBP stands for CROWN-IBP and the subscript S + Bend refers to the linear scheduling on 3 from Sstart to .end. Zhang et al. [46] found that the 8-scheduling of CBP1-0 can improve the robustness performance. And they argued that this is because training with a tighter bound of CROWN-IBI at the beginning can provide good initialization for later IBP training. On the other hand, we provide another explanation that CBP1- starts with a tighter bound (CROWN-IIP only) but not overfits to small perturbation by gradually introducing the IBP objective which has smoother landscape. In Appendix P we show that the success of CBP is due to the smoothness.
8/255, CBP obtains the improved Standard/PGD/verifee error of 54.02/65.4 011765.42/66.4 in the literature [46] while CBP,-11 shows 59.4 59.43//5.79/73 79/73.34. The result also implies that the smoothness is crucial factor in certifiable training, especially in large Erain The pro- posed method achieves 50.78/ 60.78/62.58/66 44. Although we couldn't 't achieve the same verification perfor- mance (A - 1.50), it has better standard/PGD accuracy by a larger margin (A +3.24/ + 2.84). worse than /0//40.1///46666 of CBP1-1- +- For small Cest the tightness affects the performance significantly. The proposed method shows 31. 011.4//4..5/4....0 the similar performance using a tighter bound (CBP,-.)).
In the case of frst
For Cest = 7/255, however, CBP1-0 shows
To summarize, emphasize two points in this section: (1) the f-scheduling in CB improves the smoothness by introducing the IBP objective, and (2) while the two CROWN-IBP methods perform well only for specific range of perturbations due to lack of either the tightness or the smoothness,

---

the proposed method has the two desired properties even without introducing the mixture parameter and shows a decent performance in wide range of adversarial perturbations.
Acknowledgement
Sungyoon Lee is supported by KIAS Individual Grant (AP083601) via the Center for Al and Natural Sciences Korea Institute for Advanced Study. This work was supported by the National Research Foundation of Korea (NRF) grant funded by the Korean government (MSIT) (NRF- O019RIA2C200233.
8 Conclusion
We have investigated the loss landscape of certifiable training and found that the smoothness of the loss landscape an important factor that influences in building certifiably robust models. To this end, proposed method that satisfies the two criteria: tightness of the upper bound on the worst-case loss and smoothness of the loss landscape. With the two factors, the proposed method can achieve decent performance for wide range of perturbations, while others with only one of the two factors can perform well only for a specific range of perturbations. We believe that with a better understanding of the loss landscape, better certifiably robust models can be built.
References
[1] A. Athalye, N. Carlini, and D. Wagner. Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples. In International Conference on Machine Learning, pages 274-283, 2018.
[2] M. Balunovic and M. Vechev. Adversarial training and provable defenses: Bridging the gap. In International Conference on Learning Representations, 2019.
[3] R. Bassily, M. Belkin, and S. Ma. On exponential convergence of sgd in non-convex over- parametrized learning. arXiv preprint arXiv:/811.00 122564, 2018.
[4] B. Biggio, I. Corona, D. Maiorca, B. Nelson, N. Šındić. P. Laskov, G. Giacinto, and F. Roli. Evasion attacks against machine learning at test time. In Joint European conference on machine learning and knowledge discovery in databases, pages 387-402. Springer, 2013.
[5] A. Boopathy, T.-W. Weng, P.-Y. work for certifying robustness of convolutional neural networks. In Proceedings of the AAAI Conference Artificial Intelligence, volume 33, pages 3240-3247, 2019.
Chen, S. Liu, and L. Daniel. Cnn-cert: An efficient frame-
[6] N. Carlini, A. Athalye, N. Papernot, W. Brendel, J. Rauber, D. Tsipras, I. Goodfellow. A. Madry, and A. Kurakin. On evaluating adversarial robustness. arXiv preprint arxiv: (eee::/020000000 2019.
[7] J. Cohen, E. Rosenfeld, and Z. Kolter. Certified adversarial robustness via randomized smooth- ing. In International Conference on Machine Learning, pages 1310-1320, 2019.
[8] F. Croce and M. Hein. Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-fre free attacks. In International conference on machine learning, pages 2206-2216. PMLR, 2020.
[9] F. Croce, M. Andriushchenko, V. Sehwag, N. Flammarion, M. Chiang, P. Mittal, and M. Hein. Robustbench: a standardized adversarial robustness benchmark. arXiv preprint arXiv:2010.096 2020.
[10] S. Dathathri, K. Dvijotham, A. Kurakin, A. Raghunathan, J. Uesato, R. Bunel, S. Shankar, Steinhardt, I. Goodfellow, Liang, et al. Enabling certification of verification-agnosiic networks via memory-efficiint semidefinite programming. arXiv preprint arXiv:2010.11645, 2020.
[11] K. Dvijotham, Gowal, R. Stanforth, R. Arandjelovic, O'Donoghue, Uesato, and Kohli. Training verified learners with leamned verifiers. arXiv preprint arXiv:1805. 2018.
10

---

[12] R. T. Farouki. The bernstein polynomial basis: A centennial retrospective. Computer Aided Geometric Design, 29(6):37--411 2012.
[13] T. Garipov, P. Izmailov, D. Podoprikhin, D. P. Vetrov, and A. G. Wilson. Loss surfaces, mode connectivity, and fast ensembling of dnns. In Advances in Neural Information Processing Systems, pages 8789-879999 8798, 2018.
[14] I. J. Goodfellow, J. Shlens, and C. Szegedy. Explaining and harnessing adversarial examples. arXiv preprint arXiv: 0214144226622 2014.
[15] S. Gowal, K. Dvijotham, R. Stanforth, R. Bunel, C. Qin, J. Uesato, Mann, and Kohli. On the effectiveness of interval bound propagation for training verifiably robust models. arXiv preprint arXiv:1810. 12715, 2018
[16] S. Gowal, C. Qin, J. Uesato, T. Mann, and P. Kohli. Uncovering the limits of adversarial training against norm-bounded adversarial examples. arXiv preprint arXiv:2010.0359:; 2020.
[17] M. Hein and M. Andriushchenko, Formal guarantees on the robustness of classifier against adversarial manipulation. In Advances in Neural Information Processing Systems, pages 2266- 2276, 2017.
[18] M. Lecuyer, V. Atlidakis, R. Geambasu, D. Hsu, and S. Jana. Certified robustness to adversarial examples with differential privacy. In 2019 IEEE Symposium on Security and Privacy (SP), pages 656-672. IEFE, 2019.
[19] S. Lee, J. Lee, and S. Park. cipschit training with tight outer bound. Advances in Neural Information Processing Systems, 33, 2020.
[20] B. Li, C. Chen, W. Wang, and L. Carin. Second-order adversarial attack and certifiable robustness. arXiv preprint 1rXiv:1809.0311 2018.
[21] C. Liu, L. Zhu, and M. Belkin. Toward theory of optimization for over-parameterrized systems of non-linear equations: the lessons of deep learning. arviv preprint arXiv:20033000307 2020.
[22] Z. Lyu, C.-Y. Ko, Z. Kong, N. Wong, D. Lin, and L. Daniel. Fastened crown: Tightened neural network robustness certificates. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 5037-5044, 2020.
[23] A. Madry, A. Makelov, L. Schmidt, D. Tsipras, and A. Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations, 2018.
[24] M. Mirman, T. Gehr, and M. Vechev. Differentiable abstract interpretation for provably robust neural networks. In International Conference on Machine Learning, pages 3575-3583 2018
[25] Mohapatra, C.-Y. Ko, T.-W. Weng, P.-Y. Chen, S. Liu, and L. Daniel. Higher-order certification for randomized smoothing. arXiv preprint urXiv:2010.06651, 2020.
[26] N. Papernot, P. McDaniel, X. Wu, S. Jha, and A. Swami. Distillation defense adversarial perturbations against deep neural networks. In 2016 IEEE Symposium on Security and Privacy (SP), pages 582-597. IEEE, 2016.
[27] A. Raghunathan, J. Steinhardt, and P. Liang. Certified defenses against adversarial examples. arXiv preprint arXiv: 1801.0940 2018
[28] A. Raghunathan, J. Steinhardt, and P. S. Liang. Semidefinite relaxations for certifying robustness to adversarial examples. In Advances in Neural Information Processing Systems, pages 10877- 10887, 2018
[29] H. Salman, G. Yang. H. Zhang, C.-J. Hsich, and P. Zhang. A convex relaxation barrier to tight robustness verification of neural networks. In Advances in Neural Information Processing Systems, pages 9835-9846, 2019.
[30] S. Santurkar, D. Tsipras, A. Ilyas, and A. Madry. How does batch normalization help optimiza- tion? In Advances in Neural Information Processing Systems, pages 2483-2493, 2018
11

---

[31] G. Singh, T. Gehr, M. Mirman, M. Püschel, and M. Vechev. Fast and effective robustness certification. In Advances Neural Information Processing Systems, pages 10802-10813, 2018.
[32] G. Singh, T. Gehr, M. Püschel, and M. Vechev. Boosting robustness certification of neural networks. International Conference on Learning Representations, 2018
[33] G. Singh, T. Gehr, M. Püschel, and M. Vechev. An abstract domain for certifying neural networks. Proceedings of the ACM on Programming Languages, 3(P, 2019.
[34] C. Szegedy, W. Zaremba, I. Sutskever, J. Bruna, D. Erhan, I. Goodfellow, and R. Fergus. Intriguing properties of neural networks. arXiv preprint arXiv:/312.600
2013.
[35] C. Tjandraatmadja, R. Anderson, J. Huchette, W. Ma, K. Patel, and J. P. Vielma. The convex relaxation barrier, revisited: Tightened single-neuron relaxations for neural network verification. arXiv preprint arXiv:2006. 14076, 2020.
[36] V. Tjeng, K. Xiao, and R. Tedrake. Evaluating robustness of neural networks with mixed integer programming. arXiv preprint urXiv:/711 1.00333,6, 2017.
[37] Tramer, N. Carlini, W. Brendel, and A. Madry. On adaptive attacks to adversarial example defenses. Advances in Neural Information Processing Systems, 33, 2020.
[38] T.W.. Weng, H. Zhang, H. Chen, Z. Song. C.-J. Hsieh, D. Boning, I. S. Dhillon, and
L. Daniel. Towards fast computation of certified robustness for relu networks. arXiv preprins 1804v
2018.
[39] E. Wong and Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In International Conference on Machine Learning, pages 5286-5295. PMLR, 2018
[40] E. Wong, F. Schmidt, H. Metzen, and J. Z. Kolter. Scaling provable adversarial defenses. In Advances in Neural Information Processing Systems, pages 8400-8409, 2018.
[41] D. Wu, S.-T. Xia, and Y. Wang. Adversarial weight perturbation helps robust generalization. Advances in Neurul Information Processing Systems, 33, 2020.
[42] K. Y. Xiao, V. Tjeng, N. M. Shatiullah, and A. Madry. Training for faster adversarial robustness verification via inducing relu stability. arXiv preprint wrXiv:1809.03000 2018.
[43] C. Xie, Y. WU, I.. d. Maaten, A. L. Yuille, and K. He. Feature denoising for improving adversarial robustness. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 501-509, 2019.
[44] G. Yang, T. Duan, E. Hu, H. Salman, I. Razenshteyn, and J. Li. Randomized smoothing of all shapes and sizes. arXiv preprint arXiv:2002.08111, 2020.
[45] H. Zhang, T.-W. Weng, P.-Y. Chen, C.-J. Hsieh, and L. Daniel. Efficient neural network robustness certification with general activation functions. In Advances neural information processing systems, pages 9939-4948. 2018
[46] H. Zhang, H. Chen, C. Xiao, S. Gowal, R. Stanforth, B. Li, D. Boning, and C.-J. Hsieh. Towards stable and efficient training of verifiably robust neural networks. In International Conference on Learning Representations, 2019.
[47] H. Zhang, Y. Yu, J. Jiao, E. Xing, L. El Ghaoui, and M. Jordan. Theoretically principled trade-off between robustness and accuracy. In International Conference on Machine Learning, pages 7472-7482, 2019.
[48] R. Zhang. On the tightness of semidefinite relaxations for certifying robustness adversarial examples. arXiv preprint arXiv:2006.06759, 2020.
[49] P. Zhao, P.Y. Chen, P. Das, K. N. Ramamurthy, and X. Lin. Bridging mode connectivity in loss landscapes and adversarial robustness. arXiv preprint arXiv:2005. 00060, 2020.
12


Reviews:
[{"review_id": "xYZ6dfVGFi1", "reviewer": "Reviewer_FkXz", "summary": "This paper observes that the smoothness of the loss landscape correlates with the certified performance for training certifiably robust models. The authors then design a trick to encourage the smoothness by finding sparser lower bounds parameter $\\underline{\\boldsymbol{a}}$.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "The perspective of exploring the smoothness of the loss landscape for training certifiably robust models is interesting. Experimental results support the claim that SOTA methods have favorable optimization properties. Theoretical analyses also reveal to some extent the connection between the loss gradient difference and the relaxed gradient approximations. However, I would like to give the following comments:\n\n1. The connection between the relaxed gradient approximation and the sparse $\\underline{\\boldsymbol{a}}$ is only established in a simple and small example. This hinders the utility of the connection for deeper networks, such as the models used in experiments.\n2. I can understand why the optimization trick in Eq. 7 may be helpful. However, the justification (line 263~271) for its implicit sparsity is not easy to follow. Could you explain this point more intuitively?\n3. Could one directly minimize $\\|\\nabla_{\\boldsymbol{w}} \\boldsymbol{g}^{(m)}\\|$ or $\\|\\boldsymbol{W}^{T}\\|$ in line 236 to encourage the smoothness?\n4. In the case of $\\epsilon=8/255$, the resulting performance is inferior to CROWN-IBP(1->0). This means that either smoothness itself is not the key factor, or the proposed sparsity trick is suboptimal for large $\\epsilon$. Either way, it undesirably affects the impact of the paper.\n5. In Figure 3, are the loss and tightness evaluated on the training set (as in Appendix B of [1]) or the test set? Could you provide more details?\n\nAt the moment, I’m on the border for this paper and would be happy to adjust my rating based on the discussion and revision.\n\n[1] Zhang et al. Towards Stable and Efficient Training of Verifiably Robust Neural Networks", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitations of the work are well discussed. Discussion about the potential negative societal impact is lacking.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "eYzUNZh3aUn", "reviewer": "Reviewer_Sz2Y", "summary": "The paper investigate the reason for why IBP training have better performance than the methods with tighter bounds. And it propose that the main reason for this difference is the loss landscape. The paper also designs a new certifiable training method based on their explanation.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "The topic of this paper is important in certified training and their conclusion is interesting, but I have some concerns about the theoretical and experimental results in this paper.\n\n1. In theorem 2, the paper proposed to bound the loss landscape by an upper bound and use this result to conclude that $g^{(m)}$ is major in shaping the loss landscape. However,  the influence of $g^{(m)}$ on the upper bound can not be extend to the difference off loss landscape without a discussion on the tightness of the inequality.\n2. The proposed method can bring about two influence. First, it may smooth $g$. Second it can tighter the bound. Both of these two difference can benefit the training, and is there any discussions available?\n3. For the experiment part, it seems that the result for IBP training is not satisfying compared to some new results from IBP[1], and this requires more comparison and discussions.\n[1] Fast Certified Robust Training with Short Warmup", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, the author has included the limitations.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "8L0GCfLXoCt", "reviewer": "Reviewer_ySnr", "summary": "This paper compare the two main stream methods of certifiable robust training: linear relaxation methods and bound propagation methods. By theoretical and empirical analysis, the author claim that, despite tight bounds of the output, linear relaxation methods suffer from worse loss landscape and thus obtain poorer performance. In the end, the authors propose a new methods with both tight bounds and benign loss landscape.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "Strength:\n\nAs far as what I know, this paper is the first compare linear relaxation methods with bound propagation method in the view of loss landscape. This is a very interesting aspect and extensive empirical findings support the authors' claim. The paper points out the pros and cons of both types of method, which is intrinsic and useful for researchers to design more powerful algorithms. The new method proposed by the authors achieve good performance as well. \n\nConcerns and Questions:\n\n1. [Line 84-85] There are indeed some methods training provably robust networks by randomized smoothing, such as https://arxiv.org/abs/1906.04584. So it is inappropriate to say \"They focus solely on the tightness of the certified bounds\". However, I would agree that the training methods based on randomized smoothing is not suitable to compare with the baselines here, because their guarentees are probabilistic. \n\n2. [Proof of Theorem 1] I think the author should assume the Hessian matrix is positive definite here, and by the context there is no implication about this ($\\theta_{t}$ is an arbitrary parameter instead of local minima). This assumption is necessary, because the first inequality in the formula between line 640 and 641 assumes $\\triangledown_{\\theta} \\mathcal{L}^{\\epsilon_t}(\\theta_t)^T H_t^{\\epsilon}\\triangledown_{\\theta} \\mathcal{L}^{\\epsilon_t}(\\theta_t)$ is a positive number.\n\n3. [Proof of Theorem 1] I don't understand why the authors assume $\\alpha = 2$ in line 643, it looks like $\\alpha = 1$ leads to a tight bound.\n\n4. [Equation (5)] I would not agree with the approximation here. $\\Delta_t$ is based on the gradient of $\\mathcal{L}^{\\epsilon_t}$, while $H^{\\epsilon}_t$ is the Hessian matrix of a point for $\\mathcal{L}^{\\epsilon}$, the adversarial budgets are different.\n\n5. [Theorem 2] There is not enough discussion about the third term of the inequality (6). It seems that the author assume that the constant $L^{(m)}$ does not depend on the linear approximation, however, this is not true. The authors should justify this to make the theoretical claim more rigorous.\n\nSummary:\n\nDespite the concerns above, I still believe this is a good paper, well written and easy to follow, with interesting obvervation and convincing claims. I think it will be useful for the whole community. My main complain is that the theoretical part needs improving to make it more rigorous. I strongly encourage the authors to address the concerns pointed above during the rebuttal period, after which I will do a re-evaluation.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors briefly discuss this in the Section 7. I would encourage the authors to highlight this more.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6 hours"}, "extra_text": {}}, {"review_id": "0bGJAzxslQ", "reviewer": "Reviewer_kMq3", "summary": "The paper studies why tighter convex relaxations for certifiably robust training do not always lead to better robustness guarantees. They hypothesize that this is due to optimization issues in the loss landscape, and back this up with empirical experiments and some theory. They use this knowledge to propose a modification to the certified training procedure to improve the training procedure and get improved robustness guarantees. ", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "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": "Overall I enjoyed reading this paper. It studies an open question which to my knowledge hasn't been resolved yet: why tighter relaxations don't lead to better robustness guarantees. Although this may not be the complete story (i.e. there may be other factors at play here), the authors provided what seemed to me to be a compelling argument as for how the optimization procedure can have a role in this behavior (backed up both theoretically and empirically). These findings seem to have real impact, with the improvements in robustness certification in their proposed variation of CROWN-IBP. I have two main critiques: \n\nFirst, I found that trying to decipher and parse the findings of this paper was perhaps unnecessarily difficult. Much of the work is muddled in dense, complex notation, and there are numerous long equations scattered in-line in the text. Consequent it took me quite a bit of effort to really figure out what was going on here, and this may deter other readers from picking up on this work. \n\nSecond, from the certification experiments, it would seem that although there are improvements across a range of epsilon, the proposed method seems to hurt for the smallest epsilon. Is there any intuition or explanation for why this is the case? It would be nice to include some discussion of this, i.e. as a potential limitation. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I would have liked a discussion on why the analysis does not seem to help in the case of smaller epsilon, as mentioned in the main review. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

Meta-review: I think this paper should be accepted. The paper looks at the area of certifiably robust training which is an important area. The paper poses a novel interesting question (why methods with a loose bound can perform better) and explains it using a new pespective (smoothness of the optimisation landscape). The explanation boilds down to a trade-off between smoothness and tightness. Furthermore, the authors propose a new certifiable training method that combines the smoothness and tightness and shows that it performs favorably in a wide range of perturbations. There is a concern related to the rigorousness of the proof but reading the discussion I believe the authors can address them in the final version.
Decision: Accept (Poster)