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": "rgrPsCmjLGy", "reviewer": "Reviewer_iUZ4", "summary": "This paper investigates certified training with different linear relaxations.\nThe authors provide several theoretical and experimental results which can suggest that\nsome relaxations produce non-smooth loss landscape, and result in bad performance.\nBased on this, they also propose a new certified defense and evaluate it on several benchmarks.\n", "questions": "", "limitations": "", "rating": 4, "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": "In general, I think that investigating underlying reasons why some linear relaxations perform worse than others is important research direction. However, I feel this paper falls short of delivering satisfying explanation, while at the same time newly proposed certified defense achieves worse results than prior work. I list my three main concerns below.\n\nIf we view this paper as a new certified defense, then the problem is that results are still quite a bit below the SOTA numbers from prior work. For example, on CIFAR-10 with 8/255 CROWN-IBP achieves ~3% higher verified accuracy, and with 2/255 COLT achieves ~8% higher. Given that this paper focuses quite a bit on improving certified defense, I think the final results are disappointing as we see no improvement over prior work. \n\nI have some concerns with the results presented in Section 4.2. The main idea of Theorem 1 is to upper bound loss in the next step using difference in gradients, and then in Theorem 2 the gradient difference is bounded by assuming Lipschitz continuity.\nI am not sure whether considering upper bound is very informative here (e.g. all losses could be 0 and inequalities would hold).\nInstead, I think more interesting result would be to lower bound the loss of non-smooth relaxations, which would actually\nprove that they are not going to work well for training. Also, Equation 5 approximates Hessian vector product by the difference in gradients, and it is not clear how good is this approximation so we do not even get formal upper bound right now.  \n\nThere is also a concurrent work of Jovanovic et al. [1] which proposes different hypothesis that bad performance of linear\nrelaxations is due to the discontinuity and sensitivity of these relaxations. Could the authors discuss what is the relationship\nbetween the results presented in this submission and the work of Jovanovic et al.?\nIn particular, I am curious about Assumption 1 where authors assume that linear relaxation produces Lipschitz continuous loss (which implies continuity) while on the contrary Jovanovic et al. show that some relaxations are discontinuous (e.g CROWN-IBP) and they claim that this is the cause of bad performance. Because of these assumptions, it seems that theorems in this submission cannot be applied to discontinuous relaxations, so they cannot explain their bad performance. Could authors discuss the relationship between these two works?\n\nL120: seems there is a symbol missing after g^T *\n\nL164: increases -> increase\n\n[1] Jovanović, Nikola, et al. \"Certified Defenses: Why Tighter Relaxations May Hurt Training?.\" arXiv preprint arXiv:2102.06700 (2021).\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I could not find discussion of societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "iYQenQRthpx", "reviewer": "Reviewer_fogS", "summary": "The authors study the loss landscape of certifiably robust training methods such as IBP or CROWN. They show that the smoothness of the loss landscape impact the robustness obtained, independent of the tightness of the used bound. They propose a method based on CROWN-IBP to improve smoothness and show that this also leads to slightly better certified robustness.", "questions": "", "limitations": "", "rating": 4, "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": "Strengths:\n- Good related work section outlining early and previous work.\n- Separate section to introduce notation (which is complex in this paper).\n- Both empirical and theoretical analysis of the loss landscape.\n- Visually nice and easy-to-read plots.\n- Simple and well-motivated method to improve smoothness.\n- Comparison to multiple methods on several datasets in the experiments.\n- Empirical validation that the proposed method also improves smoothness.\n\nWeaknesses:\n- The authors start by referring to “more favorable loss landscape”. However, from the paper it mostly refers to being more smooth. This happens a couple of times throughout the paper and can be confusing – I would prefer being precise and using smoothness throughout the paper.\n- Generally, the paper is incredibly dense in terms of notation and math. Most equations/theorems/definitions are not explained “in words” and following the paper requires jumping back and forth a lot. Many aspects of notation are unclear (see below) and I am pretty sure that the paper is hard to understand without being familiar with previous work (i.e., IBP, CROWN, etc.). Even if this is the case, one has to go back to these papers to follow the submitted one.\n- Regarding the empirical smoothness measures: the authors refer to [29] for computing loss variation. This should be explained in the paper as it seems to be an important point of the paper.\n- I am also missing some discussion of why these measures correlate with loss landscape smoothness, i.e., what the intuition is.\n\n- Comments on structure and high-level content:\n– The examples in line 235 should come earlier. I essentially needed to read 5 pages before making the exact connection between the bounds a and the approximate gradient g.\n– It would make sense to discuss theorem 1 first, this clearly motivates why the authors empirically look at the difference of gradients.\n– After section 3, I had to read through a lot of notation, without really knowing why. The authors should try to give me a high-level impression (i.e., that they phrase CROWN-IBP in their notation and later try to improve upon it by changing the bounds).\n\n- Comments on notation:\n– Line 100: e^{(y)} is not clearly introduced, meaning the reader has to stop and try to understand how exactly C(y) is defined.\n– Line 120: g^T \\cdot is slightly unclear what the \\cdot refers to. Generally, in the discussion around Definition 1 it is unclear how exactly g is based on the function bounds. This becomes slightly clearer when discussing IBP, but not to an extent that the paper can be read on its own (without checking related papers).\n– Line 133ff: the introduction of IPB and CROWN-IBP requires the reader to be very familiar with these methods, otherwise it seems extremely hard to follow the discussion. I would prefer to introduce one of these methods (e.g, CROWn-IBP in more detail and save discussion at other points of the paper instead.\n– Line 202: I need to go back some pages to check how L^\\eps is defined again.\n– Line 209: in the assumptions, b(x; \\theta) is a notation not used before, same for p(x;\\theta) to some extent. Also, calling it the probability function is misleading as it may be associated with the data distribution and not the predicted softmax probabilities. The assumptions are also not put “in words” to help understand what they mean. The reader is left alone with thinking about how realistic these assumptions are.\n– Line 215: again a different notation for the bias b and the probability p.\n\n- Unstable ReLUs should be explained.\n- Equation (5) is also difficult to follow. It would be easier to have a sentence or an additional step to show that the proportionality holds.\n- No proof intuition is provided for both theorems. So as reader I only have the choice to spend hours to go through both proofs in detail or not understand where these come from.\n- The method is described very briefly and I would not be able to implement it. I think more space should be used to make an accurate description that allows to implement it easily when being familiar with CROWN-IBP.\n- In the experiments, the improvement seems small in some cases (e.g., in comparison with IBP for appropriate \\epsilon). This is not really discussed. Instead the authors discuss the differences of existing methods depending on \\epsilon and \\epsilon-scheduling. So from the text it is largely unclear whether the proposed method improves significantly or not.\n\nConclusion:\nRegarding writing, I think that the paper is not ready for NeurIPS. While I think that some insights and the approach can be valuable, the paper is too difficult to follow such that the benefit for the reader is very limited in its current form.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See above.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "LuN9b3WIGcc", "reviewer": "Reviewer_Bv3w", "summary": "This paper studies the problem of training certifiably robust models against adversarial examples. Besides the tightness of the upper bound, the paper identifies smoothness of the loss landscape as another key factor that influences the performance of certifiable training. Based on the theoretical analysis, the authors propose a new certifiable training method with the desired tightness and smoothness properties. Extensive experiments on MNIST, CIFAR-10, and SVHN show the effectiveness of the proposed method under certain range of perturbations.", "questions": "", "limitations": "", "rating": 5, "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": "Originality: The paper did a good job in answering the question \"What makes some loss landscapes more favorable than others?\" While prior works mostly focus on developing tighter upper bound for the loss function, the paper shows that both tightness and smoothness of the upper bound are important for linear relaxation based methods.\n\nQuality: The main results of Theorems 1 and 2 are interesting. I am glad to see the analysis also inspires an algorithm which improves SOTA by experiments. One of the major drawbacks of this paper is that, the authors fail to connect Theorems 1 and 2 to the certified robustness accuracy.\n\nClarity: The paper is well-written and easy to understand its main message.\n\nSignificance: The significance of this paper is on average. Though the paper achieves SOTA results in certain cases, the improvement is marginal (roughly 1%-2% improvement). So it seems that the extra smoothness consideration is not so important.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have addressed the limitations in Section 7.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "Azlx3i9awBo", "reviewer": "Reviewer_fj3F", "summary": "It has been empirically observed that using tighter relaxations of loss function (largely based on the linear relaxation techniques [1, \n2, 3]) do not result in improved performance for certifiably robust training compared to Interval bound propagation techniques which use a much looser relaxation [4, 5]. \n\n\n[1] E. Wong and Z. Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope.\n[2] E. Wong, F. Schmidt, J. H. Metzen, and J. Z. Kolter. Scaling provable adversarial defenses.\n[3] K. Dvijotham, S. Gowal, R. Stanforth, R. Arandjelovic, B. O’Donoghue, J. Uesato, and P. Kohli. Training verified learners with learned verifiers.\n[4] M. Mirman, T. Gehr, and M. Vechev. Differentiable abstract interpretation for provably robust neural networks.\n[5] S. Gowal, K. Dvijotham, R. Stanforth, R. Bunel, C. Qin, J. Uesato, T. Mann, and P. Kohli. On the effectiveness of interval bound propagation for training verifiably robust models.\n", "questions": "", "limitations": "", "rating": 3, "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": "The paper studies this problem through the lens of loss landscape. \n\nI believe the paper is not well written. There are some things which are not clearly defined or explained. It is not clear to me what the authors exactly mean by the loss landscape. It can be defined in many different ways: largest eigenvalues of the Hessian, largest principal curvatures of the manifold with loss = constant, or increase in the function value in the direction of the gradient. I have read Figure 1 where they use 3 different metrics as a heuristic for the loss landscape but in many different locations in the paper where the authors refer to loss landscape, what exactly do they mean by it? Which of these metrics are they using to describe loss landscape?  Moreover, it is never formally discussed anywhere whether the loss landscape is calculated with respect to the input or the weights of the neural network. Ideally, for robustness analysis, the loss landscape should be discussed with respect to the inputs (assuming weights of the neural network are constant). \n\nThe results are not very strong. For some epsilon values, their method works better but for others the previous methods significantly outperform. Moreover, in order to establish the generality of results comparison should also be performed for the l_{2} threat model.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I see no negative societal impact of this work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper is tackling an important question in certified robust training: why tighter bounds may not lead to better models. The authors point out that linear relaxation-based methods may lead to less smooth loss landscapes when upper and lower bounds are not properly chosen, and propose a method to improve linear relaxation-based methods by improving smoothness. 

Although the paper is interesting and could be valuable to the certified defense community, there are many presentation problems. Even for expert reviewers who have been publishing in the same area, the paper is very hard to follow. Furthermore, the proposed method only achieves marginal or even no improvement over state-of-the-arts, so whether smoothness is a critical factor in certified training remains shady. We thereby decide the reject the paper this time. We do think the paper contains some interesting ideas and would like to encourage the authors to improve the paper and resubmit to another top conference. 
Decision: Accept (Poster)