Loss Landscape Matters: Training Certifiably Robust Models with Favorable Loss Landscape
Authors: Sungyoon Lee
Woojin Lee
Jinseong Park
Jaewook Lee
Venue:  (2021)
Keywords: Adversarial Examples
Certifiable Robustness
Certifiable Training
Loss Landscape
Deep Learning
Security

Abstract: In this paper, we study the problem of training certifiably robust models. 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 consider linear relaxation based methods and find significant differences in the loss landscape across these methods. Based on this analysis, we propose a certifiable training method that utilizes a tighter upper bound and has a landscape with favorable properties. The proposed method achieves performance comparable to state-of-the-art methods under a wide range of perturbations.

Under review as a conference paper at ICLR 2021
Loss LANDSCAPE MATTERS: TRAINING CERTIFIABLY ROBUST MODELS WITH FAVORABLE LOss LAND- SCAPE
Anonymous authors Paper under double-blind review
ABSTRACT
In this paper, we study the problem of training certifiably robust models. Certifi- able 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 Inter- val Bound Propagation (IBP) training uses much looser bounds but outperforms other models that use tighter bounds. identify another key factor that influ- ences the performance of certifiable training: smoothness of the loss landscape. We consider linear relaxation based methods and find significant differences the loss landscape across these methods. Based on this analysis, certifiable training method that utilizes tighter upper bound and has a landscape with favorable properties. The proposed method achieves performance compara- ble to state-of-the-art methods under a wide range of perturbations.
propose
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 (Szegedy et al. 2013
Biggio et al., 2013). hinders the application of deep learning to safety-critical domains. There has been increasing interest in building model that is robust to adversarial attacks (Goodfellow al.
2014 Papernot et al. 2016 Kurakin et al.) 2016 Madry et al. [2018] Tramèr et al. Z et al. 2019a Xie al.] 2019). However, most defense methods evaluate their robustness with adversarial accuracy against predefined attacks such as PGD attack (Madry et al. 2018 or C&W attack (Carlini
& Waggnr 2017). Thus, these defenses can be broken by new attacks (Athalye al. 2018).
To this end, many training methods have been proposed to build certifiably robust model that can be guaranteed to robust to adversarial perturbations (Hein & Andriushchenko 2017]] Raghunathan et al., al. 2018b] Wong & Kolter 2018 Dvijotham et al. 2018 Mirman et al.) 2018)] Gowal et al.) 2018
Zhang et al. 2019b). They develop an upper bound on the worst-case loss over valid adversarial
perturbations and minimize it to train certifiably robust model. These certifiable training methods can mainly categorized into two types: linear relaxation-based methods and bound propagation methods. Linear relaxation-basee methods relatively tighter bounds, but slow, hard to scale to large models, and -nneorr-inffficientt (Wong & Kolter] 20188) Wong et al.) 2018 Dvijotham et al., 2018). 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 (Mirman et al., 2018 Gowal et al.] 2018). One would expect that training with tighter bounds would lead to better per- formance, but IBP outperforms linear relaxation-based methods in many cases, despite using much looser bounds.
These observations on the performance of certifiable training methods raise the following questions:
Why does training with tighter bounds not result in better performance? What other factors may influence the performance of certifiable training? How can we improve the performance of certifiable training methods with tighter bounds?
In this paper, we provide empirical and thcoretical analysis to answer these questions. First, we demonstrate that IBP (Gowal al. 2018) has more favorable loss landscape than other linear

---

Under review as a conference paper at ICLR 2021
relaxation-based methods, and thus it often leads to better performance bounds. To account for this difference, we present a unified view of IBP and linear relaxation- methods and find that the relaxed gradient approximation (which will be defined in Definition [ of each method plays a crucial role in its optimization behavior. Based on the analysis of the loss landscape and the optimization behavior, we propose a certifiable training method that has favorable landscape with tighter bounds. The performance of the proposed method is comparable to that of state-of-the-ard methods under wide range of perturbations. We summarize the contributions of this study as follows:
with much looser
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.
We propose certifiable training method with tighter bounds and favorable loss landscape, obtaining comparable performance with state-of-ther --thh-rrt art methods under a wide range of perturbations.
RELATED WORK
Earlier studies on training certifiably robust models were limited to 2-layered networks (Hein & Andriushchenko 2017 Raghunathan et al. 2018a). To scale to larger networks, a line of work has proposed the use of linear relaxation of nonlinear activation to formulate robust optimization. Then, a dual problem is considered and a dual feasible solution is used to simplify the computation further. scale to 4-layered network, and later, Wong et al. (018)) used Cauchy random projections to scale to much larger networks. However, they still slow and eeemory-inefficientt Dvijotham et al. (018) proposed a method called predictor- verifier training (PVT), which uses verifier network to optimize the dual solution. This is similar to our proposed method but we do not require any additional network. Xiao et al. (2018) proposed to add regularization technique with adversarial training for inducing ReLU stability, but it is less effective than other certified defenses. We also encourage our model avoid unstable ReLUs, but we train the model with an upper bound of the worst-case loss and investigate ReLU stability from the loss landscape perspective.
By doing so, Wong & Kolter (2018) built method that
Mirman et al. (2018) proposed the propagation of geometric bound (called domain) through the network to yield an outer approximation in logit space. This can be done with an 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.] (2018) used a special case of the domain propagation called Interval Bound Propagation (IBP) using the simplest domain, the interval domain (or interval bound). In IBP, the authors introduced a different objective function, heuristic scheduling on the hyperparameters, and elision of the last layer 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-basee meth- ods. Balunovic & Vechev (2019) hypothesized that the complexity of the loss computation makes the optimization more difficult, which could be a 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. (2019b) proposed CROWN-IBP which uses linear relaxation in verification method called CROWN (Zhang et al.
2018 in conjunction with IBP to train a certifiably robust model.
Although beyond our focus here, there is another line of work randomized smoothing (Li et al. 2018 Lecuyer et al.) 2019; Cohen et al. 2019:; (almma et al.) 2019). which can probabilistically certify the robustness with arbitrarily high probability by using a smoothed classifier. However, requires a large number of samples for inference.
There many other works on certifiable verification (Weng et al. 2018 Singh et al. 2018 8a 2019
20186 Zhang et al. 2018 Boopathy et al. 2019 Lyu et al. 2020 However, our work focuses on "certifiable training".
2

---

Under review as a conference paper at ICLR 2021
3 BACKGROUND
First, we provide a brief overview of certifiable training methods. Then, we consider IBP (Gowal et al. 2018) special case of linear relaxation-based methods. This unified view certifable training methods helps us to comprehensively analyze the differences between the two approaches: bound propagation and linear relaxation. We present the details of the IBP in Appendix B
3.1 NOTATIONS AND CERTIFIABLE TRAINING
We consider a c-class classification problem with a neural network fæ; 0) with the layerwise oper- ations 28) = h 1a (2(k-1)) (k: = 1.... K) and the input x²)) = x in the input space X'. The cor- responding probability function is denoted by Py = softmax o f X - [0, 1 with subscript ʃ. We denote subnetwork with & operations as lk (k) ..... (() For a linear operation (x) we use ( and ((8) denote the weight and the bias for the layer. We consider the robustness of the clas- sifier against the norm-bounded perturbation set B(xx, e) (ær E X |x|| S } with the pertur- bation level e. Here, we mainly focus on the -nom bounded set. To compute the margin between the true class y for the input x and the other classes, we define a X c matrix C(y) = (
with (C())=(K)), mm =!x) Zy
(K)
(K) (m 0, c 1). For the last linear layer, the weights ((K) Ciyy (K) and ((K) C())6(k)
and the bias ((K) are merged with Cyy), that is. W(K) yielding the margin score function s( yi 0) = C(y) 0)
()=;0) (x satisfying Pa = Py. Then we can define the worst-case margin score s" (z. y, e; 0) = max s(x', y: 0)
where max is element-wise maximization. With an upper bound 3 on the worst-case margin score, 8", we can provide an upper bound on the worst-case loss over valid adversarial perturbations
as follows:
[(s(x, y, 0), 2 max
((f(=';0).)
x'Eb(2,))
for cross-entropy loss L (Wong & Kolter 2018). Therefore, can formulate certifiable train- ing as a minimization of the upper bound, ming L(3(a, (æ, e, 0);)), instead of directly solving ming max ((f ; 0), y) which is infeasible. Note that adversarial training (Madry et al. 2018) uses strong iterative gradient- loss be minimized, but it cannot provide a certifiably robust model. Whenever possible, we will simplify the notations by omitting variables such as æ, and O.
attack (PGD) to provide a lower bound on the worst-case
3.2 LINEAR RELAXATION-BASS METHODS
For a subnetwork 14] given with the pre-activation upper/lower bounds, u and for each nonlinear activation function in lk, linear relaxation- based methods (Wong & Kolter (2018); Wong et al. 2018); Zhang et al. (2019b)) use relaxation of the activation function by two elementwise linear function bounds, h and h. that is, h=z)) < h( h(2 < h(z) for 1 < z < u. We denote the function bounds as f1x) = a + + b and h(z) = O z + b for some a. b, and b, where @ denotes the elementwise (Hadamard) product. Using all the function bounds Ti's and h's for the nonlinear activations in conjunction with the linear operations in & Ak,,, an vth (scalar) activation h.
( E R can be upper bounded by linear function gd +b over B(xr,)) e) in Zhang et al. 2018 This can be equivalently explained with the dual relaxation viewpoint in Wong & Kolter (008). Further details
provided in Appendix C Now
ready upper bound the activation h over B(xxc).
Definition (Linear Relaxation with Relaxed Gradient Approximation). For each neuron activation h linear relaxation method computes upper approximation of the activation over BB c) by using g E IRd and b R as follows:
h (1)) max
g"xx' + b- g" d|gll= +
max xr e'E
x' d'EB(r,e)
We call g the relaxed gradient approximation of h over B(x,e).
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 [B[++] and then for the whole network The final bound the whole network can then be used in the objective
3

---

Under review as a conference paper at ICLR 2021
1b. The tightness of the bounds and ((s, highly depend how the linear bounds h and & in each layer are chosen.
Unified view of IBP and linear relaxation-based methods IBP can also be considered as a linear relaxation-baas based method using zero-slope (a a = 0) linear bounds, h(z) ut and h(z) 1 where vt = max o 0) and v = min(v: 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- forward/backpropaggat
computations. CROWN-IBP (Zhang et al. (019b) applies different linear relaxation schemes to the subnetworks and the whole network. uses the same linear bounds as IBP for the subnetworks [k] for k < K except for the network *
h(k] itself, and uses h(z)
u+- @ (z - 1-) and hiz) l + + > 0] ( for the whole network Moreover, CROWN-
IBP uses interpolations between two bounds with the mixing weight (3, IBP bound and CROWN-IBP bound, with the following objective:
C ((1 - 3) (a, y, 0) + 38 CROWN-IB (x, y, e; 0).
(3)
Convex Adversarial Polytope (CAP) (Wong & Kolter 2018 Wong et al. 2018) uses the linear bounds h(2) 2 a² (z- and h(z) 24 --
for all subnetworks h and the entire network. As CAP utilizes the linear bounds for each neuron, it is slow and memory inefficient. It can be easily shown that tighter relaxations on nonlinear activations yield tighter bound on the worst- case margin score 8*. To specify the linear relaxation variable &b = {a, a, b, b} used relaxation, we use the notation s(x, e; 0, Φ). CROWN-IBP and CAP generally yield a much tighter bound than IBP. These relaxation schemes are illustrated Figure [igure6oinn 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-bases methods in many cases while utilizing much looser bound. We in- vestigate the loss landscape and the optimization behavior of IBP and other linear relaxation-based methods, and find that the non-smoothness of the relaxed gradient approximation of linear relax- ations negatively affects their performance. Detailed settings of the following analyses are presented in Appendix A
4.1
LOSS LANDSCAPE OF CERTIFIABLE TRAINING
0.10
2.25
IBP
CROWN HBP (2 11
2,00
Loss Difference
0.05
OURS
1.75
0.00
1.50
IBP
1.25
CROWN-IBP (8 (6-1)
-0.05
CAP
DURS
0.75
-0.10
100
150
200
3
5
Epoch
(1 A)g(roo) + A0f
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), and (Right) the loss landscapes along the gradient descent direction at each training step the later phase of ramp-up period (epoch 50-130). The thin lines and thick lines in the figure on the right show some sample landscapes each step and the median values, respectively. Our method shows tight bounds like CROWN-IBP, while its landscape is as favorable as IBP, achieving the best performance among these four methods (see Table [].
4

---

Under review as a conference paper at ICLR 2021
We empirically show that models that have tighter bounds, CROWN-IBP (Zang et al., 2019b) and CAP (Wong& Kolter 2018), tend to have non-smooth loss landscapes, which hinder optimization during training. We examine the learning curves of IBP and these linear etaxatioo-basee methods. For a simple analysis, we avoid considering the mixture of the two logits in 3 and use / = consider CROWN-IBP logit only. Figure (lef))(((eett))) shows the learning curves on CIFAR-10 under Strain 5/235, We use e-scheduling with the warm-up (regular training) for the first 10 epochs and the ramp-up during epochs 10-130 where we linearly increases the perturbation radius from the target perturbation Crrain. 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 c, CAP and CROWN-IBP have lower losses than IBP as expected because they use much tighter relaxation bounds than IBP. particular, CAP has much tighter bounds than the others because CAP uses tighter relaxations for each subnetwork. This is consistent with the known results, that CAP tends to outperform the others at small perturbations, such as Ctrain = 2/255 on CIFAR-10 (see Table | for details). However, the end of the training, when the perturbation reaches its maximum target value (Etrain), ) the opposite result is observed where CAP and CROWN-IBP perform worse than IBP.
To understand this inconsistency, we measure the variation of the loss along the gradient direction as in Santurkar et al. (2018), which is represented as the shaded region in Figure | (left). We find that linear relaxation- based methods have large variations, while IBP maintains small variation throughout the entire training phase. It is known that a smooth loss landscape with a small loss variation induces stable and fast optimization with well-behaved gradients (Santurkar al.. 2018). Therefore, even though CAP and CROWN-IBP show robustness in the early phase of training, the non-smooth loss landscape in the ramp-up period might have hindered the optimization, yielding less robust models. As will be discussed in the following section, we find that the loss variation is highly related the relaxed gradient approximation g used in linear relaxation.
We further explore the loss landscape near the local region of the parameter space at the current parameter g(now) toward the next parameter (meezt) along the gradient in Figure [ (right). We plot the landscapes for the later phase of the ramp-up period (epochs 50-130) during which large per- turbations are used. IBP has flatter landscapes compared to the others, whereas CROWN-IBP has landscapes with large curvature along the gradient, and thus it tends to move towards sharp local minimum and it may remain stuck there. Therefore, it may overfit to be robust to small perturbations, but not robust to the target perturbation étrain.
Unstable ReeUU lonty
1.0
CROWN-IBP (6 1)
-0.5
CAP
0.03
0.02
0.01
0.00
10
20
30
40
50
60
80
90
100
110
120
130
Epech
Figure 2: (Top) Cosine similarities between two consecutive loss gradients and (Bottom) the ratio of the number of unstable ReLUs during the ramp-up period. A large number of unstable ReLUs, high nonlinearity, leads to unfavorable landscape that negatively affect the optimization process.
Next, we establish a relationship between the optimization procedure and linear relaxation. Figure (top) shows the directional deviation between two successive loss gradient steps in terms of co- sine similarity during training. Simultaneously, Figure (bottom) shows the ratio of the number of unstable ReLUs for which the pre-activation bounds and u span zero. We observe that the cosine similarity value is low when the number of unstable ReLUs is large for example, in the early stage of CAP and the middle stage of CROWN-IBB In particular, the middle of the ramp-up period, CROWN-IBP has a large number of unstable ReLUs and exhibits abrupt changes in gradient steps. often has deviation angles larger than 90º, leading to parameter updates in the opposite direction of the previous one, bouncing in the basin of local minimum. This is consistent with the results

---

Under review as a conference paper at ICLR 2021
shown in Figure I Moreover, since the gradient directions not well-aligned, it may not enjoy the advantages momentum based optimizers and be sensitive to the learning rate. To summarize, large number of unstable ReLUs, high nonlinearity, leads to an unfavorable landscape that can negatively affect the optimization process.
4.2 SMOOTHNESS OF RELAXED GRADIENT APPROXIMATION
In this section, we investigate the loss landscape further from theoretical perspective to answer the question: "What makes some landscapes more favorable than others?" We find that the relaxed gradient approximation of linear relaxation affects the smoothness of the landscape. First, we need some mild smoothness assumptions that are natural when the network parameters 02 and 02 are close to each other, especially they are two consecutive parameters from SGD update.
Given linear relaxation method, we make the following assumptions on the bias b(a:; 0) in the linear relaxation and the probability function p 0):
Assumption
(1) ||V [[llVab(z gbxx; x: 11) Vab(æ: æ; 02) S -
| 021 for all 0 02 and
(2) [p;; 0 - p(=; 0 - 1 0 for all 0, 02 and x.
With the above assumptions, we can provide an upper bound on the loss gradient difference for linear relaxation-based methods measure the non-smoothness of the loss landscape follows:
Theorem 1. Given input æ X and perturbation rudius let M be max ||~'|| For
linear relaxation- -aased method with the upper bound 3m (x;; 0) max 9 (m)) (ax: 0) T x'' +
Bfmm (o:; 0), if f(m) satisfies Assumption I for each m and ps satisfies Assumption (2), then
V ( 11) VoL(s(x;; 02))1
Vog (1m) (x; 02)1 + (m) 10 - 021 2e Veg (mL) (x: 0122)l + M| Vl (m)) (x: max
m
(4)
for any 01, O2 where L (m)
bbm) + L8 V (x; 01,2)ll and 01,2 can be any of 01 and 02.
According to Theorem 1, the relaxed gradient approximations (m)) in the linear relaxation play major role shaping the loss landscape. The smoother the relaxed gradient approximations are, the smoother the loss landscape is. Especially for IBP, using the zero-slope relaxed gradient ap- proximation (1T))) = 0 for all m. the loss difference is upper bounded by only the last term, max L 0 , O2l1. and it is relatively small for a single gradient step. On the other hand, for other linear relaxation-baal
methods using non-zero relaxed gradient approximation g (mm) o 0, the gradient updates used in the training more unstable than IBP. It is consistent with the empirical
results shown in Figure that there are significant differences between the loss variations of IBP and others.
PROPOSED METHOD
Our analyses so far suggest that tightness of the upper bound on the worst-case loss and smoothness of the loss landscape are important for building certifiably robust model. Therefore, we aim to design new certifiable training method improve the aforementioned factors (favorable landscape and tighter bound).
More favorable landscape via less a = We observe that CROWN-IBP (3 = 1) tends to have more unstable ReLU and less smooth landscape than the others. What, in the objective of CROWN- IBP, does lead to these results? To answer this question, we investigate variants of CROWN-IBP with different a settings for unstable ReLUs. For each setting, we sample a E {0, 1} with different for each neuron with pre- 1/u + 1 0] for the other stable ReLUs. For the other -
(p. with P(a = 1 [i| > /ul) = and P(a = [|] < |u])
activation bounds and u. We
elements of the linear relaxation variable Φb ((a, a, b, b)}, we fix a "
~"=, = - , and
for each activation node, because they are the optimal choices for tightening the bound (see Appendix C.2 for details). Figure shows that it tends have more unstable ReL.Us the number

---

Under review as a conference paper at ICLR 2021
Unstablc RalU
0:06
0/0.25
18 1
0.5/1
1/1
CAP-IPP
0.02
0:00
10
20
40 50
70
80
90 100 110
120
130
Epoch
Figure 3: The ratio of the number of unstable ReLUs for models with different a settings during the ramp-up period. Notation p/q denotes the variant with sampling a E {0, 1 with P(g [ul) = p and P(g = |4] I jul) = q for unstable ReLUs. As the number of a = increases, tends to have more unstable ReLUs, which leads to less smooth loss landscapes.
of a satisfying a = increases. This observation implies that it is required to have smaller portion of a with a = 1 to have a more favorable landscape.
However, reducing the portion of a with a 1 is not enough to achieve robustness unless the tight- ness is guaranteed. Through manually adjusting the a variants of CROWN-IBP achieve favorable landscapes, but they show looser upper bounds which lead to worse performance. Further inves- tigation variants of CROWN- is presented in Appendix E Therefore, it is required to search for appropriate values of that can achieve both tightness and favorable landscape.
Tighter bound via optimization Now, we aim to reduce the number of a satisfying - 1 and to tighten the upper bound in (T), simultaneously. We can achieve both by minimizing the upper bound over the linear relaxation variable & as follows:
((8(0, y, 0), > min L(8(x, v. 6)
C(f(x'; 0), (22,))))))
max
It can be equivalently understood as solving the dual optimization in CAP rather than using 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 subnet- works s except for s itself, similar to CROWN-IBP. Further, we efficiently compute a surrogate of the minimizer a" arg min, [(3(x, y, 0, Φ), y) using the one-step projected gradient update of the relaxation variable a Specifically, we have
à = [o (ao rsiign VaL(s( U. c;
v),)))
(6)
with an initial point ag where o- = ((ā. a b)b.
~ U0, 11"h and n 2 1, yielding the final objective L(3(x, y, 6,
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 on the worst-case loss, and 2) smoothness of the loss landscape. Subsequently, we evaluate the performance of the method by comparing it with others certifiable training methods. Details on the experimental settings are in Appendix A
Tightness To validate that the proposed method (OURS) has tighter bounds than other relaxations,
we analyze various linear relaxation methods in Figure 4 We define tightness measure sum over the worst-case margin for each class Em=o 5m (x, y, e; 0). obtained from (2) Then, evaluate multiple methods on a single fixed model pre-trained with the proposed training method. The compared methods are, from left to right, OURS, CROWN-IBP (Zhang et al.) 2019b). CAP- IBP, and RANDOM. All methods use the same IBP relaxation for subnetworks, but use different linear relaxation variables a for the whole network CROWN-IBP, CAP-IBP, and RANDOM use @ = 1|u + 1 > 0), a u - and a U(0, 1]". respectively. We fix the other variables a, and b, in Section 5 In both figures, indicates that a single gradient step in (6) is sufficient to obtain tighter bounds compared to other relaxation methods. See Appendix [P for the equivalent tightness violin plots of other models.
method shows the lowest value average, which
7

---

Under review as a conference paper at ICLR 2021
3.0
Tightness
Loss
76.37
73.59
2.0
-10
OURS CROWN-IBPCAP-IPP
CROWN-IBP
Figure 4: Violin plots of the test loss with the corresponding verified error (Left) and of tight- ness (Right) for various linear relaxations. Lower is better. This shows that the proposed relaxation method has a tighter bound than the others relaxation methods.
Figure 5: The ratio of number of a used for unstable ReLUs during the ramp-up period. Note that the blue region denotes the number of a 0 when [|| s lu]. It indicates that the proposed method reduces the number of satisfying = (purpletyellow).
Smoothness Figure shows that the proposed method has small loss variations along the gradi- with IBP, whereas CROWN-IBP (5 1) has wide range of loss values. This is because CROWN-IBE IBP (3 = 1) has more unstable ReLUs than our methods as shown Figure 2 As men- tioned above, number of is closely related the amount of unstable ReLUs, and Figure shows that our method has successfully reduced the number of = 1. Further, we conduct analysis on smoothness of the loss landscape with the loss gradient change (the left term in (4) in Appendix
Robustness We evaluate the performance of the proposed method and compare it to that of state- of-the-art certifiable training methods: IBP (Gowal et al.) 2018). CROWN-IBP (3
(Zhang
et al. 2019b), and CAP (Wong et al. 2018). in Section 4.1 On MNIST, follow Zhang et al. (2019b) and use Etrain 2 Eteat' whereas for CAP, we use the same étaain Eteat which yields better results. We used three evaluation metrics: standard (clean) error, 100-step PGD error, and verified error. For the verified error, we evaluated with the bound & of each method.
Test errors (Standard PGD Verified error) of IBP, CROWN-IBP (3 = 1), CAP, and OURS on MNIST, CIFAR-10, and SVHN. Bold and underline numbers are the first and second lowest verified error.
Table I:
Data
c(1x.)
IBP
CROWN-IBP (3 1)
CAP
OURS
0.1
1.18/2.16/..5
1.07/
0.80/ 1.73/993
1.09/ 1.77 /2336
0.2
2.00/3.29
6.31
5.50/ 7.97
3.22 / 6.72/ 11.06
1.70/3.44/ 4,34
MNIST
0.3
3,50 5.85 10.45
5.73 10.76 16.28
19.19 / 35.84 / /47.85
3.49/ 5.55 9.79
0.4
3.50/7.30/
17.96
5.73 14.63 23.80
3.49 6.77 15.42
2/208
37.98 / 49.40 55,39
32.48 / 42.77 / 50.15
28.8 / 38.95 / 48,50
/ /42.73 49.42
4/25G
46.42 / $7.42 62.80
45.56 / 58.24 64.47
40.78 / 52.62 / 61.88
42.53 / 55.55 61.52
CIFAR
6/255
52.84 / 63.92 68.79
54.72 65.28 7.1044
49.20 60.85 69.03
50.19 / 61.88 66.90
8/256
55.71 / 66.79 70.95
61.37 / 70.66 75.37
56.77 66.78 73.02
56.01 / 66.17/ 69.70
16/255
67.10 75.12 78.26
76.65 / 81.90/ 84.42
75.11 / 80.67 / 82.07
65.93 / 75.39 77.87
SVHN
0.01
19.91 34.12 43.83
17.25 30.84/ 39.88
16.88 36.16 37.09
16.41 / 30.43 39.44
8

---

Under review as a conference paper at ICLR 2021
Table summarizes the evaluation results under different Clest for each dataset. In general, when Etest is low, methods with tighter linear relaxations show good performance, whereas IBP tends to perform better Eest increases. In short, the state-of-the-an art methods perform well for specific range of Étest- For example, IBP show relatively better performance in the case of étst = 0.3, 0.4 on MNIST and étest 6/255, $/255, 16/255 on CIFAR-10. On the other hand, CAP and CROWN-IBP
(3 = 1) outperform IBP in the case of Eteat = 0.1 on MNIST, Éteat 2/255 on CIFAR-10 10 and Étest 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 to worse performance at large c. Moreover, CAP cannot be trained on MNIST when érrmin = 0.4. As the case is also not specified in Wong et al. (2018). it seems that CAP is hard to be robust to étrain 2 0.4. On the other hand, the proposed method shows consistent performance in a wide range of Etst values, achieving the best performance in most cases, since it has tighter bounds and a favorable landscape, not overfitting to a local minimum during the e-scheduling. We also compared our method with other prior work (Xiao et al. 2018 Mirman et al. 2018 Balunovic We also conduct additional experiments on the hyperparameters
& Vechev 2019) in Appendix
K
in Appendix
L M and N
Unlike standard training, certifiable training requires e-scheduling. is implicitly assumed that a set of weights that makes the network robust small is good initial point to learn robustness to a large étrain- However, linear relaxation-based methods with tighter bounds start with a lower loss a small e, but with an unfavorable loss landscape, they cannot explore a sufficiently large area of the parameter space. Hence, they overfit to be robust to small perturbation, and not generalize to 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 (Wong et al.) 2018 Zhang et al. 2019b). The tightness of the proposed method improves the performance for small while the smoothness of the proposed method helps the optimization process, which also leads to better performance for a large e. To conclude, the proposed method can achieve a decent performance under wide range of perturbations shown in Table !
Table 2:
Test errors (Standard/ / PGD/ / Verified error) of OURS and CROWN-IBP,.C 1--0 on CIFAR-1O. Bold numbers are the lower error.
((
9/265
4/20s
6/2to
8/350
10/203
OURS
31.49/42.73 / 49.42
42.53 55.555555///0
/
50.19/61.58
66.90
56.01 / 66.16/ 69.70
65.93/75.39/ 77.87
CROWN-IBP.... 1-10
36.30/47.13 552.70
45.92/57.58/ 62.07
53.54
64.14/
55.09/ 66.68 69.97 06.62/76.13777
Understanding 8-scheduling For CROWN-IBP. CROWN-IBP,-11 and CROWN-IBP,-N where the subscript Bxtars - Bend refers to the linear scheduling on /3 from Sstart to Bend- Zhhan et al. (2019b) found that the B-scheduling of CROWN- IBP1-00 could help to improve the robustness performance. And they argued that this is because training with tighter bound of CROWN-IBP the beginning can provide good initialization for later IBP training. On the other hand, we provide another explanation that CROWN-IBP)- starts with a tighter bound (CROWN-IBP only) but not overfits to small perturbation by gradually intro- ducing the IBP objective which has a smoother landscape. Despite using a single objective without the mixture parameter B, the proposed method can outperforms CROWN-IBP 1 on CIFAR-10 as shown in Table 2
two different settings of B in
7 CONCLUSION
In this work, we have investigated the loss landscape of certifiable training and found that the smoothness of the loss landscape is an important factor that influences in building certifiably ro- bust models. To this end, we proposed a method that satisfies the two criteria: tightness of the upper bound on the worst-case loss and smoothness of the loss landscape. Then, we empirically demon- strated that the proposed method achieves robustness comparable to state-of-the-an art methods under wide range of perturbations. We believe that with an improved understanding of the loss landscape, better certifiably robust models can be built.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give a false sense of se- curity: Circumventing defenses to adversarial examples. In International Conference on Machine Learning. pp. 274-283, 2018.
Mislav Balunovic and Martin Vechev. Adversarial training and provable defenses: Bridging the gap. In International Conference on Learning Representations, 2019.
Battista Biggio, Igino Corona, Davide Maiorea, Blaine Nelson, Nedim Šındić, Pavel Laskov, Giorgio Giacinto, and Fabio Roli. Evasion attacks against machine learning at test time. In Joint European conference on machine learning and knowledge discovery in databases, pp. 387-402. Springer, 2013.
Akhilan Boopathy, Tsu Weng, Pin-Yu Chen, Sijia Liu, and Luca Daniel. Can-cert: An efficient framework for certifying robustness of convolutional neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 3240-324 -2400-327,220 2019.
Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In 2017 IEEE Symposium on Security and Privacy (SP), pp. 39-57. IEEE, 2017.
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. In International Conference Machine Learning, pp. 1310-13222 1320, 2019.
Krishnamurthy Dvijotham, Sven Gowal, Robert Stanforth, Relja Arandjelovic, Brendan
O' O'Donoghue, Jonathan Uesato, and Pushmeet Kohli. Training verified learners with learned ver- ifiers. arXiv preprint arXiv:1805. 2018.
Rida T Farouki. The bernstein polynomial basis: A centennial retrospective. Computer Aided Geo- metric Design, 29(6))379-419, 2012.
Timur Garipov, Pavel Izmailov, Dmitrii Podoprikhin, Dmitry P Vetrov, and Andrew G Wilson. Loss surfaces, mode connectivity, and fast ensembling of dnns. In Advances in Neural Information Processing Systems, pp. 8789-8798, 2018.
Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. arXiv preprint 4rX65:1412.6577, 2014.
Sven Gowal, Krishnamurthy Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Ue- sato, Timothy Mann, and Pushmeet Kohli. On the effectiveness of interval bound propagation for training verifiably robust models. arXiv preprint arXiv: 12715, 2018
Matthias Hein and Maksym Andriushchenko. Formal guarantees the robustness of classifier against adversarial manipulation. In Advances in Neural Information Processing Systems, pp. 2266-2276, 2017.
Alexey Kurakin, Ian Goodfellow, and Samy Bengio. Adversarial examples in the physical world. arXiv preprint arXiv: 1607.02333.. 2016.
Mathias Lecuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified robustness to adversarial examples with differential privacy. In 2019 IEEE Symposium Security and Privacy (SP), pp. 656-672. IEEE, 2019.
Bai Li, Changyou Chen, Wenlin Wang, and Lawrence Carin. Second adversarial attack and certifiable robustness. arXiv preprint IrxXiv:800900. 2018
Zhaoyang Lyu, Ching-Yun Yun Ko, Zhifeng Kong, Ngai Wong, Dahua Lin, and Luca Daniel. Fastened crown: Tightened neural network robustness certificates. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 5037-5044, 2020.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations, 2018.
10

---

Under review as a conference paper at ICLR 2021
Matthew Mirman, Timon Gehr, and Martin Vechev. Differentiable abstract interpretation for prov- ably robust neural networks. In International Conference on Machine Learning, pp. 3575-3583, 2018.
Nicolas Papernot, Patrick McDaniel, Xi Wu, Somesh Jha, and Ananthram Swami. Distillation as a defense adversarial perturbations against deep neural networks. In 2016 IEEE Symposium Security and Privacy (SP), pp. 582-597. IEFF, 2016.
Aditi Raghunathan, Jacob Steinhardt, and Percy Liang. Certified defenses against adversarial exam- ples. arXiv preprint arXiv: 1801.9344, 2018a
Aditi Raghunathan, Jacob Steinhardt, and Perey S Liang- Semidefinite relaxations for certifying robustness to adversarial examples. In Advances in Neural Information Processing Systems, pp- 10877-10887, 2018b.
Hadi Salman, Jerry Li, Ilya Razenshteyn, Pengchuan Zhang, Huan Zhang, Sebastien Bubeck, and Greg Yang. Provably robust deep learning via adversarially trained smoothed classifiers. In Advances in Neural Information Processing Systems, pp. 11289-1 1300, 2019.
Shibani Santurkar, Dimitris Tsipras, Andrew Ilyas, and Aleksander Madry. How does batch nor- malization help optimization? In Advances in Neural Information Processing Systems, 2483- 2493, 2018
Gagandeep Singh, Timon Gehr, Matthew Mirman, Markus Püschel, and Martin Vechev. Fast and effecctive robustness certification. Advances in Neural Information Processing Systems, pp. 10802-10813, 2018a.
Gagandcep Singh, Timon Gchr, Markus Püschel, and Martin Vechev. Boosting robustness certifica- tion of neural networks. In International Conference on Learning Representations, 2018b.
Gagandeep Singh, Timon Gehr, Markus Püschel, and Martin Vechev. An abstract domain for cer- tifying neural networks. Proceedings of the ACM on Programming Languages, 3(POPL):1-30, 2019.
Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. arXiv preprint arXiv:1312.6199 2013.
Vincent Tjeng, Kai Xiao, and Russ Tedrake. Evaluating robustness of neural networks with mixed integer programming. arXiv preprint arXiv: 2017.
Florian Tramer, Alexey Kurakin, Nicolas Papernot, Ian Goodfellow, Dan Boneh, and Patrick Mc- Daniel. Ensemble adversarial training: Attacks and defenses. arXiv preprint S.KY:1705.072000 2017.
Tsui- Wei Weng, Huan Zhang, Hongge Chen, Zhao Song, Cho-Jui Hsieh, Duane Boning, Inderjit Dhillon, and Luca Daniel. Towards fast computation of certified robustness for relu networks. arXiv preprint arXiv: 1804.000000000 0804009699, 2018
Eric Wong and Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In International Conference on Machine Learning, pp. 5286-5295, PMLR, 2018.
Eric Wong, Frank Schmidt, Jan Hendrik Metzen, and Zico Kolter. Scaling provable adversarial defenses. In Advances in Neural Information Processing Systems, pp. 8400 140008809,000 2018.
Kai Y Xiao, Vincent Tjeng. Nur Muhammad Shafiullah, and Aleksander Madry. Training for faster adversarial robustness verification via inducing relu stability. arXiv preprint 1r09000809.03008, 2018.
Cihang Xie, Yuxin Wu, Laurens der Maaten, Alan L Yuille, and Kaiming He. Feature denoising for improving adversarial robustness. I Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 501-509, 2019.
11

---

Under review as a conference paper at ICLR 2021
Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric Xing, Laurent El Ghaoui, and Michael Jordan. Theoretically principled trade-off between robustness and accuracy. In International Conference Machine Learning, pp. 7472-7482, 2019a.
Huan Zhang, Tsui-Wei Weng, Pin-Yu Chen, Cho-Jui Hsieh, and Luca Daniel. Efficient neural net- work robustness certification with general activation functions. In Advances in neural information processing systems, pp. 4939-4948, 2018.
Huan Zhang, Hongge Chen, Chaowei Xiao, Sven Gowal, Robert Stanforth, Bo Li, Duane Boning, and Cho-Jui Hsieh. Towards stable and efficient training of verifiably robust neural networks. In International Conference on Learning Representations, 2019b.
Pu Zhao, Pin- Yu Chen, Payel Das, Karthikeyan Natesan Ramamurthy, and Xue Lin. Bridging mode connectivity in loss landscapes and adversarial robustness. arXiv preprint arXiv:2005.00060 2020.
12

---

Under review as a conference paper at ICLR 2021
A EXPERIMENTAL SETTINGS
Datasets and Architectures the experiments, we use three datasets: MNIST, CIFAR- 10 and SVHN and model architectures (Small, Medium, and Large) in Gowal et al. (2018) and their vari- ants (Small* and Large") as follows:
Small: Conv(;116,42)) Conv(16,32,441) Flatten - (C(,,100)-FC(1()))
Small": Conv(,,16,4,2) Conv(16,32,4422 Flatten FC(-,10)) -FC(100,c)
Medium:
Conv(32.32442)) Conn632.64.31)-Coonv666 -latten
FC(-,512) FC(512,512) -FC
Large: Conv(-664,3,1) Co3v(64,64,3,I)
C0nv(64,128,3,2)
Conv((28,128,3.)
Conv(128,128,3.1) Flatten FCC.5112) FCCS12,c)
Large": Conv((,643,11)) (40.43,.))--Coo6441122..333 (on,(64,128,3.2) Conv (288,11),1283331
128,3,1) Flat-
ten -
where Conv(c1, 02, 8) is a conv layer with input channel Cı, output channel 62. kerner size k, and stride and FC(d1, d2) is fully-connected layer with input dimension dj and output dimension d2- All layers are followed by ReLU activation except for the last layer and the flatten layer (Flatten).
Loss and training schedules For general training schedules, we refer Appendix C, D of Zhang et al. (2019b) with single GPU (Titan Xp). We use the following mixed cross cross-entropy loss as in Zhang al. (2019)):
x) ((1- BB x y, c; + MODEL (x. y. g).))).))) 9) kL (f(x; (1-
where 6 is the mixing weight between the natural loss and the robust loss, and B is the mixing weight between the two bounds obtained with IBP and given relaxation method (e.g. CROWN-IBP).
A.1 SETTINGS IN SECTION
We conduct the experiment in Figure [ CIFAR-10 dataset with Medium architecture over all four methods. We train the model with Ctran 8/255 for 200 epochs using c-scheduling with 10 warm-up epochs and 120 ramp-up epochs. We use Adam optimizer with learning rate 0.001. We reduce the learning rate by 50% every 10 epochs after e-scheduling ends.
Figure 1
To demonstrate the instability of each training, we describe the variation of the loss along the gra- dient direction as [annurrar al. (2018). We take steps of different lengths in the direction of the gradient and measure the loss values obtained each step. For the sake of consistency, Cauchy random matrix when evaluating CAP to obtain deterministic loss landscapes, not introduc- ing randomness. The loss variation is computed with
fix
(()()(t))
where ((3(0) = L(3 y, e; 0), and
(tt) = 0, tn vo for E 5].
(8)
where (= (0)) is the current model parameters and is the learning rate. For the step of length t, we sample ten points from a range of [0.5] on a log scale. In Figure (right), ((now) ((0) and 0 (next) (1).
Figure 2 (top) In Figure 2 with the model used in Figure 1 we plot cosine similarity be- tween two successive loss gradient steps during training as follows:
cos (VoL( Vol()))))))))(((())))))())))))))
where cos(v1, 122 is the cosine value of the angle between vectors en and v2
13

---

Under review as a conference paper at ICLR 2021
A.2 SETTINGS IN TABLE
For MNIST, we use the same syper-parameters as in Appendix C of Zhang et al. (2019b). We train for 200 epochs (10 warm-up epochs and 50 ramp-up epochs) on Large model with batch sizes of 100. we decay the learning rate, 0.0005, by 10% in (330190) epochs. As mentioned in Zhang et al.) (2019b), we also found the same issue when training with small e (see Appendix N for details). To alleviate the issue, we use Etrain mi.(0.4, Eteat + 0.1) for each Éteat as Table 2 of of'aan et al. (019b).
For CIFAR-10, 10, we train for 400 epochs (20 warm-up epochs and 240 ramp-up epochs) on Medium model with batch sizes of 128. We decay the learning rate, 0.003, by 2x every 10 epochs after the ramp-up period.
For SVHN, we train for 200 epochs (10 warm-up epochs and 120 ramp-up epochs) on Large model with batch sizes of 128 (OURS with batch sizes of 80 to avoid out of memory). We decay the learning rate, 0.0003, by 2x every 10 epochs after the ramp-up period. Only for SVHN, we apply normalization with mean (0.438, 0.444, 0.473) and standard deviation (0.198, 0.201, 0.197) for each channel.
In Table I to O, we refer the reader to Table 3
k-scheduling from 1 to O. For the corresponding results of k-scheduling from 0
We modify the source code for CAF match our settings. For example, introduce the warm- up period and linear e-scheduling. We avoid using the reported results the literature and aim to make fair comparison under the same settings with only minor differences for example, because CAP does not support the channel-wise normalization, we could not use the input normalization. Also, due the memory limit of CAP, we use smaller batch size of 32 and try other smaller architectures. We found that it often achieves better results with smaller architectures (similar to the results in Table of Wong al. (018)). ). Thus, we present the performance with Large*. Medium, and Small on MNIST, CIFAR- 0, and SVHN, respectively. Throughout the experiments, CAP uses the fixed
B INTERVAL BOUND PROPAGATION (IBP)
IBP Gowal et al. 2018) starts from the interval bound ( = (z : ( S 2 S u0)) = =B(x, c) in
the input space with the upper bound u (0) = æ + el and the lower bound ((0) = x - el where is
a column vector filled with I. Then we propagate the interval bound (kk {z 1 2 S
(1-1)) by using following equations iteratively:
u (k) (b) (k-))) and (k)) (1k-1))
(9)
for element-wise monotonic increasing nonlinear activation (00) with the pre-activation bounds r (1-1) and ((k-1), and
(k(k-1) + 1k=-1) + |W()) [u(h (1(h-1) 1(h-1)
(k) w(h)
(R) and
(10)
2
(kk-11) + ((x-1)
(k-11)
[(k-1)
(k) (kk)
[
+ (8)
(11)
2
for linear function (,0 (k = 1, K). Finally, IBP uses the worst-case margin = (() to formulate the objective in (1 for certifiable training.
hhtp:://gihuu...cm//oosssalllmme adversarial
14

---

Under review as a conference paper at ICLR 2021
C DETAILS ON LINEAR RELAXATION
C.I LINEAR RELAXATION EXPLAINED IN CROWN (ZAAGG ET AL. 2018
To make the paper self-contained, we provide details of linear relaxation given in the supplemen- tary material of CROWN (Zhang et al. 2018). We refer readers to the supplementary for more details. Given a network h 1 we want to upper bound the activation 1/[h We have [1(l(( (x') = W 1) (h (x')) + b(b) W!! (2 +b where 2 (R=22) h kk 1ll (x'). With
the linear function bounds of Thth (k-1) and h (k-1) on the activation function (k=-1), we have
h/ M4 (x') (x')
w (k)
(2- 1) (x-)) + b:aa)
S
Σ
w(k) (K-1) 11 1k 2) +
wr (k)))(k-11) (2))-2) + b/b²)
ijj
with
w 20
Σ
w (k) (1-1) (k-
w (b) (k-1) (k-2)'
5.
w
w
Σ
w
bfk
+ Σ
w W
bj
+ b
w <0
w 20
wilh) (x-2)) 2)/ + +b(())
w!! (2l')))(() + (((h)
w!!!) (w((-2)
2) (h kk3) (xx') + b + +b(h²)
()(k-2) n 33 (1-3)) + b((-2)
where W(( w 1) with the diagonal matrix D (k-1) ((()) and ((-ii
at-11) for satisfying
jjj aj
jj aj (1- for satisfying w((h)
iJ 2 0, b Ewiry w i.j Dj
(((1) +
( (k-1) 1) + (k) (k-2) 2) w (k-)), and 6.th (k-2) w/ (1(h) + (()) Ap-
Ewey
plying similar method iteratively, we can obtain and b in ( for the linear relaxation of h!!
C.2 DUAL OPTIMIZATION VIEW
We first modify some notations in the main paper and use the notations similar to Wong & Kolter 2018). We use the following hat notations: 2(A-1) = ((+11) + b(*+1) and (x) = (x where h (A) is the k-th nonlinear activation function. We can build a primal problem with cτ = C..: as follows:
max et g(K) ((K
(12)
such that
x el < (0)
2 (0) sx+el
* (k+1) 1) = - + (k+1) (k 0,... 0,, K - 1), and
z (4)) (2(()) (I: 1, 1,... K 1).
15

---

Under review as a conference paper at ICLR 2021
Note that our is negation of that of Wong & Kolter (018). Now derive the dual of the
primal (12 as follows:
min
sup
c² (k) + = cl 21)) E- + (z (0)
x xccl)
c 20 ((0))
200)
K-1
k K-1
+
Σ ukt1 (((++)) - (wr + b((ttt)) k=
+
Σ
Dj
(x(k)
h (((0)))))))))
k=1
K-1
= (c+ uk) Dx) ((( + 15----
- - Σ (t (k) (z( -v. (M))
Dk+1 + 1x)
k=1
K-1
(13)
v (1) - E"x x -clEEl1.
leads C+UKK = g + - (W V1 and (k+ P4+itig = -,... ,--)).
Alternatvell,, they are represented as follows:
VK- = c,
ig ((+ MK+1 (k = K - 1, 1), and
= 11.
Now we need relationship between i& and Vk, i.e., uk = g(ix). With the further relaxation va @ D2. we have relaxed problem as follows:
K-1
min sup ((k)
(o% (0 (2(0)) - 2()) - b
-xxxx -e||<(
(14)
such that
VK = -c,
8 W(+IIT Uk+1 (k: = K 1,,... ,,,,,,)). 1),
V = ar o i (k = K 1,,., 1), and
D1.
We decompose the first term in 14), and ignore the subscript & as follows 8 h²)(()) (a & D) Further, we decompose this for each element, Dh(E) aδλ (hh(2) o.)). If the pre-activation bounds for h are both positive (active ReLU), then a should be not to make the inner supremum Similarly, if the pre-activation bounds for h are both negative (dead ReLU), then should be O. In the case of unstable ReLU (1 < 0 < u), if < 0, then we need to solve max,, inf lu()) a.. The & 1, and is
inner infimum is for to solve min, sup; h(2) aå. The inner supremum is max (u au, -al},
otherwise. On the other hand, if i 2 0, then need r.l), and thus the optimal dual variable is a* --7 which yields the optimal value (multiplied by ()) as D(u ==
- ~
which is equivalent using linear relaxation with a Q z b bound h(z) -- (-) to include the case of active/dead ReLU. For the lower linear and b according to the dual relaxation with While CAP and CROWN-IBP use a dual feasible solution like - or a 1|u + 0j. our proposed method aims optimize over the dual variable equivalently optimize over 0 < 1 to further tighten the upper bound the loss.
J (z 1). We can represent
=+
u
@ 2
case of unstable ReLU, we can use any 0 <
16

---

Under review as a conference paper at ICLR 2021
D ILLUSTRATION OF LINEAR RELAXATIONS
Figure provides some illustrations of linear relaxations used in IBP, CAP, CROWN-IBP, and the proposed method. CROWN-IBP adaptively chooses the relaxation variable so that the area between h and h is minimized. However, the smaller area does not necessarily imply the tighter bound, and the proposed method achieves tighter bounds than CROWN-IBP relaxation as shown in Figure
(s)
Maas)
((+) (= -1)
b(2)
A(=)
((x))
(a) IBP
(b) (u,
(c) CAP
Ma) - (F
664) 1f2 6.8 domm
661) 1361 +1
Optimized over h(a) az
(d) CROWN-IBP
(e) CROWN-IBP
(u+ + 0)
(u+ +1 0)
(f) The proposed method
Figure 6: Illustrations of linear relaxation methods. Except for (b), they illustrate the relaxations when 1 I 0 S u (Unstable ReLUU. (b) Illustration of the relaxation of IBP when u, / > 0 (Active ReLU).
17

---

Under review as a conference paper at ICLR 2021
E LEARNING CURVES FOR VARIANTS OF CROWN-IBP
seems that a certifiable training with looser bound tends to favor stable ReLUs. For example, IBP starts with small number of unstable ReLUs while CAP starts with large number of ReLUs as shown in Figure 2 (bottom). However, a tighter bound does not directly lead to many unstable ReLUs. We find that 0.5/1 and 1/1 have looser bounds than CROWN-IBS (as shown Figure but they have more unstable ReLUs (as shown in Figure 3) where p/q denotes the variant with sampling with P(a
{0, [4] > lul) = p and P(a P(a=T T [i] S [u]) = q for unstable ReLUs. On the other hand, 0/0, 0/0.25, and 0/0.5 have looser bounds than CROWN-IBP and they have less unstable ReLUss, which leads small loss variations as in Figure Therefore, this observation implies that is more important to have less to have more smooth landscape.
Learning Curves
10"
0/0
0/0.25
0/0.5
Loss
x 10
0/1, CROWN-IBP (p=
0.5/1
1/1
CAP-IBP
OURS
10
50
100
150
200
Epoch
Figure 7: The learning curves for the scheduled value of with the loss variation along gradient descent direction (equivalent Figure T). As the ratio the number of with 1 increases, the loss variation increases.
Learning Curves
2.20
2.15
0/0.25
2.10
0/0.5
0/1, CROWN-IBP (8 1)
2.05
0.5/1
2.00
1/1
CAP-IBP
1.95
OURS
1.90
100
120
140
160
180
200
Epoch
Figure 8: A zoomed-in version of Figure for epochs 100-200.
Table Performance (in terms of errors) of the variants of CROWN-IBP (3 1). Note that 0/0.25, 0/0.5, and CAP-IBP start with looser bounds but they have more smooth landscape, which leads to a better performance than CROWN-IBP (3 1) (highlighted with underline).
0/1
Model 0/0
0/0.25
0/0.5
CROWN-IBP (8 1) 0.5/1
1/1
CAP-IBP
OURS
Standard
70.66
64.50
62.72
63.24
70.69
71.41
60.36
57.14
PGD
73.84
72.67
71.42
71.70
76.68
77.03
69.46
66.88
Verified
77.60
74.47
74.92
75.72
78.38
78.73
74.29
71.45
18

---

Under review as a conference paper at ICLR 2021
F PROOF
To prove Theorem [ first prove the following proposition. We note that 0 and g are vectorized and the matrix norm of Jacobian is naturally defined for example, || Vegll is induced by the vector norms defined in X' and e.
Proposition 1. Given input x E X and perturbation radius e, let M max[[|='I| x' B(x, e)}. Then, for the upper bound s(x; 0) maxx')3(a.e) g(:; 0) x' + b(::; 0) with b satisfying Assump- tion (1), we have
(os 01) (os(a;; 02)11
s 2e 01,2)ll M[[Vog(a; Vog(w; 02)1l T.al100. 10: 021l (15)
for any 0,, 02 where 01,2 can be any of 0 and 02.
Proof. Say J(x'; ; 0) g 0)T x'' + b(æ; 0) and the maximizer at arg rax (,) for each 0; 01, O2. Then, we have
Vo 01) - Va 02)1 = Vef(aji0)) Vef(a
- Vaf(<); 01) Vaf( V Vaf 02)]
< [o] 01) Vo](w); 01)1 + [/Vo] 01) Vo] 02)
(16)
The first term on the RHS can be upper bounded as follows:
[ (af 01)ll
Vo (gi T' क gi a;)l
[oV at - 91 x>))ll
VVogi (zj x5)1
S 2c| Vegill
where gi g( 0.). 6, = b(:; 0,), ) /." = 19 bb] and x"
|x" 1]. And the second term on the
RHS can be upper bounded as follows:
( (o](w;; 02)11 = |V T 222 -92 T #ل)ه
l g2 )
< o 1|)= I/Vo -22)l
$ Vo 92)ll | T 0 -2211,
Therefore, we obtain
| 01) Vo 02)1 < 2c Vel V - + L. 0= 0z1 2e Veg xx; 01)l + M Veg xz; 01) Veg [z: 02)1 + L 0 0211.
Note that 0, in the first term is arbitrarily chosen in (16). Therefore, this leads to the final inequality 15).
Theorem 1. Given input a X and perturbation radius e, let M be m ||'||| For linear relaxation-bass method with the upper bound 8m (x 0) = max g (m)) (x: 0) x'' + bom) (x; 0), if ((m) satisfess Assumption I for each and Ps satisfies Assumption (2), then
VoL(3(an 0 - VoL(3(a;02))
< max m
2e Veg (m) (x; 0122)1 + Mll (m) (z; 01) Vog (m²) (x; (x;02))1 + (mm) 100 - 021l
(4)
for any 0,, Oz where (.(m)
T.go
(.m(m)
T.P Vos(<;; 01,2)l| and 01,2 can be any of 0 and 0z.
19

---

Under review as a conference paper at ICLR 2021
Proof. We simplify the notation ps p. Then we have
(1)
Vo Vo8((: (2))1)
Σ (= 01) )m Vo (x: 02) Ppm
(pm (2; 02) - dymm)l
V (o (1)p((;;))) c Vos( 02) (2) 02) e(v1)]l
V Vos(w: 01)p(=;;1) - Vas( 02 (2:; 02)1
V a 5 az 01)p(2;0)) (a 01)p(
V (1
Vos(x: 02)p(x;;
V 88 <2: (:)(p(=;01) p(#; 02)) + (os 01 Vas(ar (2)) 02)
V Vos m: 0x)]llp((;;0 p(:: 02)
max
V 0 (m; 01) Vosn (cr; 02)1
m
Vas(<; ax; 01)1122110 02|l max
2 a 01)
v (x; 02)
< max 2e Veg (m)
(z: 112) + M| V eg (m))
(x: 01) - V Vog (m) (x; 02)1 + L 110 - 0all)
G LEARNING CURVE FOR Etrain
Figure shows the learning curves for the target perturbation Etroin during the ramp-up period, while Figure shows the corresponding curves for the scheduled value of The figures the same settings in Appendix A.1
Learning Curves
106
IBP
105
CROWN-IBP 11
104
CAP
OURS
Loss
103
10a
10a
100
20
40
80
100
120
Epoch
Figure 9: The learning curves for the target perturbation Ctrain during the ramp-up period.
20

---

Under review as a conference paper at ICLR 2021
H SMOOTHNESS
We empirically measure the non-smoothness of the loss landscape with the difference between the
Iwo consecutive loss gradients at 0, 0(0) and 02 ((1) in (8), says gradient difference (=
V (())) <z (I)) It is highly related to the ratio of the number of unstable ReLUs
(nonlinearity of the classifier) as shown in Figure 10
Simllsnty Grad Diference
CROWN-IBP
0.00
1.0
0.5
-0.5
Unstable RelU
30
120
Epoch
Figure 10: (Top) Gradient difference and (Middle) cosine similarities between two consecutive loss gradients, and (Bottom) the ratio of the number of unstable ReLUs during the ramp-up period.
21

---

Under review as a conference paper at ICLR 2021
1 MODE CONNECTIVITY
In this section, we check the mode connectivity (Garipov et al. 2018 between two models that are trained using certifiable training methods. Mode connectivity framework that investigates the connectedness between two models by finding a high accuracy curve between those models. It enables us to understand the loss surface of neural networks.
Let wy and wi be two sets of weight corresponding to two different well-trained neural networks. Moreover, let Φe_ (t) with
[0, 1] be a continuous piece-wise smooth parametric curve with pa- rameters O. such that Φo. (0) uno and dho (1) w1 To find a low-loss path between wo and w1, Garipov et al. (2018) suggested to find the parameter O₂ that minimizes the expectation of loss ((w) over a distribution qo, (t) on the curve,
L(O.) = Ei-go, (o)(((00
To optimize L(Os) for Oc. we use uniform distribution U10, 1J as qo, qo. and Bezier curve (Farouki 2012) as (t), which provides a convenient parameterization of smoothness on the paths connect- ing two end points (wo and w1) as follows:
Φ0. (t) (1 t)2wo + 2t(1 310++22
A path de, is said to have a barrier if 3t such that ((óo. (t)) > max(((wo)) [(w1)}. The existence of barrier suggests the modes of two well-trained models are not connected by the path in terms of the given loss function & (Zhao et al.) 2020).
We test the mode connectivity between the models trained with IBP, CROWN-IBP, and OURS. For example, to check the mode connectivity between two different models trained with CROWN- IBP and IBP, use the loss function used each model user-specified loss for training the parametric curve óe.-. Therefore, we can obtain two curves as depicted in Figure [1 12 and 13 for each pair of models. Here, we use the identical settings in Appendix A.I
Figure shows the mode-connectivity between CROWN-IBP and IBP. We use CROWN-IBP loss as user-specific loss in Figure [Ia and IBP loss in Figure [lb] this figure, we find that using CROWN-IBP loss (Tla). there exists a barrier between the two models. This suggests they are not connected by the path terms of CROWN-IBP loss. However, with IBP loss, there no loss barrier separating the two models. This indicates that using CROWN-IBP, it is hard to optimize the parameters from wi to wi, but IBP can.
Figure 12 shows the mode-connectivity results on IBP and OURS. We find that two models are not connected to each other using either TBP bound or OURS bound, since there exists barrier both curves. In this figure, of the loss function using OURS is lower than that of IBP.
also notify that OURS has tighter bounds than IBP because the value
Finally, Figure 1 illustrates the mode connectivity between CROWN-IBP and OURS. Using CROWN-IBP as a user-specified loss function, we can find that the robust loss on the curve is higher than that of the end points. However, when OURS is used as loss function, the robust loss generally decreases as the / increases. It shows that OURS has much favorable loss landscape com- pared to CROWN-IBP. In addition, since the value of the robust loss using OURS is lower than CROWN-IBP
find that OURS has tighter bound than CROWN-IBP,
22

---

Under review as a conference paper at ICLR 2021
CROWN-IBP (8- 1]
CROWN-IBP (B
3.25
3.25
IBP
Robuz Loze (CROWIN
3,00
Loss [10P
3.00
2.50
2.25
2.25
2.00
2.00
(a) CROWN-IB bound
(b) IBP bound
Figure 11: Mode connectivity between CROWN-IBP and IBP, where we and wh well-trained models using CROWN-IBP bound and IBP bound, respectively. 0g trained using CROWN-IBP
IIa and IBP (IIb respectively.
2.30
2.30
2.25
IBP
2.25
IBP
OURS
OURS
2.20
Rooust Loss
2.05
2.05
2.00
2.00
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
10
(a) IBP bound
(b) OURS bound
Figure 12: Mode connectivity between IBP and OURS, where wo and w are well-trained models using IBP bound and OURS bound, respectively. 0, is trained using IBP T2ab and OURS (Tbb). respectively.
CROWN-IBP (8=
CROWN-IP (8
1)
Babuzt Loz (CROYAN 18
2.20
OURS
2.20
OURS
2.15
2.15
2.00
2.00
1.95
1.95
1.90
1.90
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
(a) CROWN-IBB bound
(b) OURS bound
Figure 13: Mode connectivity between CROWN-IBP and OURS, where wo and w are well-trained models using CROWN-IBP bound and OURS bound, respectively. O, is trained using CROWN-IBP 13a) and OURS 13b), respectively.
23

---

Under review as a conference paper at ICLR 2021
J RELU
In this section, we investigate how pre-activation bounds u and for the activation layer change during training. For each activation node, it said be "active" when the pre-activation bounds both positive (0 < 1 S u), "unstable" when they span zero (1 S 0 S u), and "dead" when they are both negative S a < 0).
Figure 14 shows the ratios of the number of active and dead ReLUs during the ramp-up period. Notably, we find that CROWN-IBP has more active ReLUs during training compared the other three methods. Simultaneously. CROWN-IBP has the lowest ratio of dead Rel.Us.
Figure 15 shows the numbers of active, unstable, and dead ReLUs during the ramp-up period. We find that in CROWN-IBP, the number of unstable and active ReLUs increases as the number of dead ReLUs decreases. This indicates that a number of dead ReLUs change to unstable ReLUs as the training increases. However, in the other methods, the number of unstable ReLUs is consistently small, while the number of active ReLUs decreases as the number dead ReLUs increases.
Figure 16 depicts the histograms of the distribution of the slope -ーك the unstable ReLUs during ramp-up period. In the early stages of CAP training, slope distribution is concentrated around 0.4. However the training progresses with larger e, the histogram distribution moves left, which indicates unstable ReLUs change dead ReLUUs. It is consistent with the results in Figure 15c On the other hand, in the case of CROWN-IBP, the histogram distribution moves to right during training. the same with the results Figure 15b which shows that number of active ReLUs increases during training.
Active RetU
0.15
0.10
IBP
(8
1.00
Dead RueLU
OURS
0.70
30
60
110
120
130
Epoch
Figure 14: period.
The ratio the number of active (top) and dead (bottom) ReLUs during the ramp-up
24

---

Under review as a conference paper at ICLR 2021
IBP
CROWN IBP (6
30300
30000
20000
20000
10000
10000
Desd
Desd
100
epacc
epach
(a) IBP
(b) CROWN-IBP (B = 1)
CAP
OURS
00000
00.000
50000
50000
40300
40000
30000
30000
20000
Acliv
20000
Aciiuw
10000
10000
100
12c
n0
10c 120
(c) CAP
(d) OURS
Figure 15: Number of active (Green), unstable (Orange), and dead (Red) ReLUs.
Coach 18
Zoeth 40
Essch 73
Eases
Opech 338
IBP
Conch
toeth 40
Eaach 73
Epach
Coech
24
06
04
0.
24
03
24
20
(b) CROWN-IBP
(c) CAP
Spach
Spach
(d) OURS
Figure 16: Histograms of the distribution of the slope period.
when S S during the ramp-up
25

---

Under review as a conference paper at ICLR 2021
K COMPARISON WITH OTHER PRIOR WORK
All experiments and results (except for Table in this paper are based on our own reimplementation. For the unimplemented prior work, compare the best reported results in the literature in Table
We note that the results in Xiao et al. (2018) and Balunovic & Vechev (2019) are evaluated with
MILP based exact verifier TTeng al. 2017
Table Test errors (Standard Verified error) compared the best errors reported in the literature.
Bold numbers are the lowest verified error.
Data
c(Go)
Xiao et al. 2018
Mirman et al.
2018
Balunovic & Vechev 2019
OURS
0.1
1.32/ 4.87
1,3/4.2
0.8/29
1.09 2.28
MNIST
0.3
2.67 / 19.32
3 10.7
2.7 14.3
2,42 7.84
2/255
38.88 / 54.07
37.7 / 54.5
21.6 39.5
31.49 49.42
CIFAR-10
8/255
59.55 79.72
53.8 / 72.8
48.3 72.5
56.01 69.70
L AND X-SCHEDULINGS
Table 5 shows the evaluation results of the models as in Table 1 but trained with different i-- scheduling (from 0 0). Table 6 shows the evaluation results of the proposed models trained with different K- and 8-schedulings.
Table 5: Test errors (Standard PGD / Verified error) of IBP. CROWN-IBP (8 = 1), CAP, and OURS on MNIST, CIFAR-IO, and SVHN. See Appendix A for all the other settings, same in Table Bold and underline numbers are the first and second lowest verified error.
Data
e(lxx)
IBP
CROWN-IBP
CAP
OURS
0.1
1.25 /2.31 3310
1.23/2.19/277 2.75
0.80/ /.19
1.09 1.86 2,28
0.2
1.95 / 2.95 6.28
2.89 5.322
3,22 / 6.72 11.06
1.70/ 3.37 4.78
MNIST
3.67 / 5.55 99.74
6.11 11.33 17.51
19.19 /5.84//57745 /4788
3.39 / 4.85 9.12
0.4
3.67 6.55 16.55
6.11 15.34 26.72
3.39 / 5.88 15.04
3/255
43.60 52.62 56.58
32.15 42.67 49.36
28.80/ 38.95 48.50
32.04 / 43. 13 49.62
1/258
53.89 62.58 65.14
45.05 56.46/ / 63.04
40.78 52.62 61.88
43.15 54.85 61.31
CIEAR
6/255
61.37 68.64 70.82
53.87 65.03 71008
19.20/ 60.85 69.03
50.99 62.23 67.59
8/255
64.11 77066 72.99
60.96 70.52 75.68
56.77 66.77 78 733.02
56.35 67.06/ 70.56
16/255
69.74 / 76.66 79.86
79.14 / 83.64 84.36
75.11 80.67 82.07
66.96 75.63 78.08
SVHN
0.01
20.19/ / 34.57 /4..5
16.66 / 30.05 38.15
16.88/ 30.16/ 37.09
15.46 / 29.34/ 38.57
M ONE-STEP VS MULTI-STEP
To get a tighter bound, we propose multi-step version of 6 as follows:
0,+1 [o,1" (a, asign ()
(17)
We compare the original 1-step method (a > 1) to 7-step (t 7) method with 0.1. The results We found no significant difference between two methods even though multi-step takes multiple times with multi-step. Therefore, we decide to focus on one-step method.
are summarized in Table 7
26

---

Under review as a conference paper at ICLR 2021
Table 6: Test errors OURS with different 8- and s-scheduling on MNIST and CIFAR-10.
OURS
OURS -00
OURS
Duta
<(fx)
Standard
PGD
Vorfied
Standard
PGD
Verfled
Standard
PGD
Vertied
Standard
PGD
Verfied
0.1
1.09
1.77
2.36
1.29
2.29
3.58
1.09
1.86
2.28
1.15
2.03
3.53
0.2
1.70
3.44
4.34
1.61
3.09
5.71
1,70
3.37
4.78
1.64
2.57
5.43
MNIST
0.4
3.49
15.42
5.68
13.72
3.39
5.88
15:04
2.44
5.29
13.84
2/253
31.49
42.73
49.42
37.77
48.30
54,43
32,04
43.13
49.62
38.58
48.59
54.63
1/25a
56.01
66.17
69.70
58.87
67.76
71.50
56.35
67.06
70.56
58.90
67.81
70.99
16/255
65.39
75.39
77.87
66.24
74,69
78.66
66.96
75.63
78:08
66.76
75.17
77.99
Table 7: Test errors of OURS with different numbers of gradient update steps in 17 on CIFAR-10.
Here, we use k-scheduling from
OURS (1-step)
OURS (7-step)
Data
e(1xc)
Standard
PGD
Verfied
Standard
PGD
Verfied
2/235
32.04
43.11
49.62
31.40
42.30
49.20
CIFAR-10
8/235
56.35
67.03
70.56
54.44
66.29
71.53
27

---

Under review as a conference paper at ICLR 2021
N TRAIN WITH Etrain 2 Etest
N.1 Cirain 2 Otest ON MNIST
Zhang al. (2019)) and Gowal
20188 observed that IBP performs better when using Ctrain 2 Ctest than Ctrain Cesst Figure 8 shows the results with different Ctrain's 's for each Cest- The overfitting issue more prominent in the case of IBP and CROWN-IBP1-2 than the proposed method and CROWN-IBP 1-1- However, using larger perturbations compromises the standard ac- curacy, and thus it desirable to use smaller étrain-
Table 8: Comparison of the performance (Standard PGD Verified error) depending on various Strain Here, use x-scheduling from 0 to O.
Data
fteat
Etrain
IBP
CROWN-IBP,-.
OURS
CROWN-IBP
0.2
1.25 3.39 7.77
1,23 33448 7.64
1.09 /.177 6.29
1.13 5588
0.2
0.3
1.95 2.93 6.28
2.89 / 7.61
1.70 /4.7
L.8/2.73/4.
MNIST
0,4
3.67 /.777 6.36
/9.0/ 12.71
3,49 6.36
2.37 /3.26/ /4.64
1.95/3..1 12.90
7.35 14.97
1.70 /700/4.82 /9200
1.48 3.52 /9.40
0.3
0.4
3.67 5.55 9.74
6.11 11.33/ 17.51
3,49 / 5.59 19.79
2.37 3.63 7.222
N.2 ftrain 1.1etest ON CIFAR-10
As mentioned in Gowal et al. (2018), also train with Etrain 1.Letest 1IFAR-10. The results are shown in Table They attain slightly improved performances in 2/255, but not in 8/255 and larger
Table 9: Comparison of the performance (Standard PGD Verified error) the models trained with Strain and 1.1etrain. Here, x-scheduling from 0 to 0.
Data
Ezest
étrain
IBP
CROWN-IBP,..
OURS
CROWN-IBP 1-+0
7/255
52.71
56.58
32.15/ 42.67 /49.36
32.04 22.01/3.13//40
37.25 47.19/52.55
3/256
CIFAR
2.2/256
44.78 / 52.62
55.78
33.23 43.11 /49.18
33.04 / 43.70 48.60
38.42 / 47.80 52.53
10
8/253
64.11 / 70.68
72.99
60.96 70.52/ 75.68
56.35 6 67.06 70.56
56.95 / 67.89/ 70.43
#/256
8.8/258
64.54/ 70.30
72.40
61.48
75.17
50 70.52
59.37 68.51 70.71
O TRAINING TIME
All the training times are measured on a single TITAN X (Pascal) on Medium for CIFAR-10. We train with batch size of 128 for OURS, CROWN-IBP1-. and IBP, but with batch size of 32 for CAP due to its high memory cost. For CAP, we use random projection of 50 dimensions.
OURS: 115.9 sec epoch
CROWN-IBP 51.68 see epoch
IBP: 14.85 sec / epoch
CAP (batch size 32, GPU): 751.0 sec epoch
CAP (batch size 64, GPU): 724.6 sec epoch
CAP (batch size 128, 2 GPUs): 387.9 see /pooc
28

---

Under review as a conference paper at ICLR 2021
P LOSs AND TIGHTNESS VIOLIN PLOTS
We plot the equivalent tightness violin plots in Section 6 for models trained with other methods. The proposed method achieves the best results terms of loss and tightness followed by CROWN-IBP, CAP-IBP, and RANDOM. Figure (a)- (c)-(d), and (e)-(f) show the tightness evaluated on the model trained by CROWN-IBP, 1->0. CROWN-IBP; and IBP, respectively.
2.6
-25
2.4
Tightness
-7.
-10.0
-12.5
-15.0
OURS CROWN-IBP CAP-IB RANDOM
CROWN-BBCAP-IB RANDOM
(a) the loss of CROWN-IBP 1
(b) the tightness of CROWN-IBP
2.2
Tightness
Loss
-6
2.0
1.9
-8
OURS CROWN-IBP CAP-BP RANDOM
OURS CROWN-BBP CAP-IBP RANDOM
(c) the loss of CROWN-IBP;....
(d) the tightness of CROWN- CROW
15
10
Tightness
Lo5g
-5
-10
OURS CROWN-BBPCAP.II RANDOM
the loss IBP
the tightness IBP
Figure 17: Violin plots of the test loss (Left Column) and of tightness (Right Column) for various linear relaxations same as Section 6 Lower better.
29

---

Under review as a conference paper at ICLR 2021
Q
COMPARISON WITH CAP-IBP
As section we train a model with CAP-IBP and compare with the proposed method and CROWN-IBP (5 1). Figure 18 shows that CAP-IBP has gradient differences (defined in Sec- tion H larger than the proposed method and smaller than CROWN-IBP (3 1), which leads to performance between the proposed method and CROWN-IBP (3 1) (see Table B CAP-IBP has looser bounds than CROWN-IBE (8 1) as shown in Figure and Figure 17 but with a relatively
more smooth landscape, can achieve better performance than CROWN IBP (5 1).
Similanty Grad Difference
0.02
CROWN-IBP (B --]
CAP-BP
OURS
0.01
0.00
0.5
0.0
ReLU RetU
0.03
Unstable
0.02
0.01
0.00
10
20
30
90
60
90
100
110
120
130
Epoch
Figure 18: (Top) Gradient difference and (Middle) cosine similarities between two consecutive loss
gradients, and (Bottom) the ratio the number of unstable ReLUs during the ramp-up period.
30

---

Under review as a conference paper at ICLR 2021
R RELU STABILITY
To see the effect of unstable ReLUs on smoothness, we adopt the ReLU stability loss (RS loss) CRS(U, -1anh(1 + [) as a regularizer (Xiao al. 2018). We use L XCRS loss and run CROWN-IBP (3 = 1) with various À settings. We plot the smoothness and the tightness in Figure 19 and Figure 20 on 0, 0.01,
We found that small À suggested in Xiao et al. (2018) has effect on reducing the number of unstable ReLUs since certifiable methods have smaller unstable ReLUs as shown in Figure [5] and thus not on improving the smoothness. By increasing A, we observed that RS successfully reduces the number of unstable ReL.Us with 10. Figure T9 shows that large À leads better loss variation and gradient difference. This supports that unstable ReLUS are closely related to the smoothness of the loss landscape. However, as Xiao et al. (2018) mentioned "placing too much weight on RS Loss can decrease the model capacity, potentially lowering the provable adversarial accuracy", the models trained with large À 2 1 couldn't 't obtain a tightness of the upper bound and significant improvement robustness illustrated in Figure 20 The test errors (Standard / PGD / Verified) are 0.6278 0.7189 0.7634 on = 0.01 and 0.6090 0.7085 / 0.7600 on X 10.
0.02
OURS
Gred Diffennce
0.01
0.00
Simiarity
Unitate Ratu
0.08
0.00
0.01
0.00
10
20
90
10 60
90
1000
110
120
130
1.00
150
100
170
180
190
200
Epoch
Figure 19: (Top) Gradient difference and (Middle) cosine similarities between two consecutive loss- gradients, and (Bottom) the ratio of the number of unstable ReLUS on CROWN-IBP (3 1) with A = 0, = 0.01, A 10 and OURS.
2.2
==
==0.01
2.0
=
OURS
1.8
1.6
1.4
1.2
Figure 20: Robust loss of CROWN-IBP (3 1) with À 0.01, 10 and OURS during training.
31


Reviews:
[{"review_id": "og7cIHucq7O", "reviewer": "AnonReviewer1", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies why training with looser bounds (IBP) can outperform tighter linear relaxation based methods in certified defense. The authors argue that this is because IBP has a smoother loss landscape compared to linear relaxation based methods. Then the paper proposes to optimize the lower bound in the CROWN relaxation for unstable ReLU neurons during training, for tighter bounds and a smoother loss landscape.\n\nPros:\n* This paper studies an important problem in certified defense and tries to improve linear relaxation based certified defense methods, especially CROWN. \n* This paper novelly proposes to optimize the lower bound in the relaxation for unstable ReLU neurons to train tighter bounds in certified defense. \n* The paper showed some improvement on test verifier error, compared to CROWN-IBP(1->1), and it also showed improvement on tightness and loss smoothness.\n\nCons:\n* The link between the motivation and the proposed method is not well justified. Paragraph “Favorable Landscape” somewhat explains the connection between optimizing the lower bound in relaxation and improving loss landscape. But it states that the benefit comes from preferring dead ReLU neurons to unstable ones. If the proposed method is actually trying to make more unstable neurons dead, the paper does not discuss or compare with paper Xiao et al., 2018 (https://arxiv.org/pdf/1809.03008.pdf) which directly adds a regularization to induce ReLU stability. \n* It does not seem to make sense that the proposed method can prefer to have dead neurons via optimizing the relaxation for unstable neurons. With such an optimization, bounds of unstable neurons become tighter, so how can such tighter bounds make the model favor unstable neurons less than CROWN-IBP with relatively looser bounds?\n* As the paper mentions that CROWN-IBP does not penalize unstable ReLU neurons with (|u|<=|l|), but how about just make the lower bound equal to the upper bound as Fast-lin (Weng et al., 2018, https://arxiv.org/abs/1804.09699) does, so the lower bound is non-zero for unstable neurons? \n* An improvement over CROWN-IBP(1->1) is shown in the paper. However, the proposed method does not make enough improvement over CROWN-IBP(1->0). The improvement on CIFAR10 with eps=8/255 or 16/255 is very small (error 69.70 v.s. 69.97, 77.87 v.s. 77.88), while there is a large performance drop on MNIST with eps=0.3/0.4 (increased error 7.07->9.79 and 12.35->15.42). What will the performance of the proposed method look like if a changing $\\beta$ is used in training?\n* This paper missed some previous works, e.g., Xiao et al., 2018 and Weng et al., 2018 as mentioned above. More discussions or comparisons with them may be needed.\n\n==========================================================================================\n\nUpdate after rebuttal:\n\nThanks for the detailed author response. I think the paper is interesting in providing an analysis on how optimizing the linear relaxation in CROWN (although the verification method itself seems to be similar as the one in Fastened CROWN in AAAI 2020) can lead to better loss smoothness and tightness, which seems to improve the performance of certified training. The author replies have addressed some of my concerns in my initial review. However, there are still some outstanding concerns:\n\n1. After more consideration, I think the “More favorable landscape” paragraph is still insufficient to address the second point in my above cons. The author response argues that some “$(p/q)$” have looser or tighter bounds, but these are considered for relaxation *locally*, not the tightness on the final output, while the relaxation optimized in the paper is to tighten the final output. Thus it remains unclear why tighter final bounds with improvement from the unstable ReLU neurons makes the model favor unstable neurons less.\n\n2. AnonReviewer2 has reminded me that the “Fastened CROWN” work had a similar method about optimizing the lower bound of the linear relaxation in verification, which seems to be very similar to the method proposed in this paper, in terms of the verification part in certified training. Although this paper focuses on certified training and has some different analysis, the major modification on the method is still on the verification part, and thus I agree that a discussion on the comparison with Fastened CROWN should not be missed. The authors did not add it in the discussion period.\n\n3. It is promising that the proposed method outperformed the modified CROWN-IBP ($\\beta=1$) and IBP, and there seems to be a significant margin. But the proposed method fails to make a significant improvement compared to the original CROWN-IBP (the 1->0 one), e.g., the improvement on CIFAR-10 eps=8/255 or 16/255 is negligible. \n\nOverall, I am keeping my recommendation as rejection for the current version of the manuscript. \n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "ORKWHACJbp4", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors studied the role of loss landscape in training certifiable robust models. The authors reviewed linear relaxation based methods, and showed that Interval Bound Propagation (IBP) is a special case of linear relaxation based methods. Although linear relaxation based methods have a tighter bound on worst case loss with adversarial perturbations than IBP based method, the authors found in numerical studies that towards the end of training, IBP outperforms linear relaxation based methods. The authors hypothesized that this was because IBP loss landscape was more smooth, which helped optimization. The authors demonstrated in a theorem that IBP loss was indeed more smooth under certain assumptions. Based on this insight, the authors proposed a favorable landscape method. The authors showed in numerical studies that the sum over the worst-case margin for each class is lowest for their method. The loss of their method is also the most smooth among competing methods. Their method achieved a consistent performance in a range of perturbations, which is not achieved in competing methods.\n\nThe paper is clearly written. The insight is interesting, and could help future researchers.\n\nOn page 4, in Figure 1, what is the mathematical definition of \"variation\"? Why does the variation of CROWN-IBP first increase, and then decrease? A related question is why does the proportion of unstable ReLu first increase and then decrease in CROWN-IBP? Does it have something to do with the curvature shown in Figure 1 (right)?\n\nOne page 7, it would be great to also show the comparison of training time between these methods.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "2XK6OVV509P", "reviewer": "AnonReviewer2", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper claims to make three contributions:  (i) a theoretical and experimental demonstration that the driving force behind performance in certifiable training methods is loss landscape smoothness (ii) a new training method and domain designed to have a smooth loss landscape (iii) an evaluation showing their new training method performs comparably to the state of the art.\n\n\nPros:\n* The paper provides some experimental analysis support a hypothesis that has been conjectured since Mirman et al. (2018), that smooth loss landscapes produced by smoother transformers (zSmooth/hSmooth) would improve training.  \n* The paper does show experimentally that certain methods tend to have less smooth loss landscapes.  \n* The theoretical result connects the smoothness of the relaxed gradient approximations to the smoothness of the loss landscape, which may be useful for designing future certifiable training methods.\n\nCons:\n* In terms of accuracy and verified error, the proposed system performs comparably to some pre-existing systems.  The main claim that the authors have identified an important factor for improving certified training remains unsupported by the inability to improve noticeably upon results from prior work.\n* The authors do not compare it to the state of the art, COLT [1], which achieves for example 21.6/39.5 (standard, verified error) compared to this paper’s 31.49/49.42 results on CIFAR10 2/255.  This is a much more significant difference than for any of the comparisons made to other work in this paper.\n* It is unclear how fast the proposed method is.  No comparison appears to be made on training speed or memory usage compared with other systems.  Given comparable accuracy and verified error results, I would not see a reason to use this system if this one is slower.\n* I am not sure about the utility of the experiment on tightness and Figure 3.  Different methods could have different scales of loss while producing similarly verifiable networks (as this paper in fact demonstrates).  Further, even the worst case margin for a class could be fooled by a network with entirely  zero weights.  \n* Loss value is also compared between methods in Figure 1.\n* The paper claims that state of the art methods such as CROWN-IBP and CAP are held back by their non-smooth loss landscapes while failing to meaningfully outperform them.  5 out of 10 of the standard accuracies are worse than CROWN-IBP’s for example.\n* Section 4.1 claims that the experiments show that “the non-smoothness of the relaxed gradient approximation of linear relaxations negatively affects their performance” yet the evidence presented is circumstantial, and not capable of indicating causality.\n* Section 4.2 claims that the theoretical analysis states that some landscapes are more favourable  than others, whereas in fact it only demonstrates the smoothness of some landscapes not their “favourability.” \n* The paper leaves out additional related work.  In particular, I would like to see a discussion of the difference between the analysis used by Fastened Crown [2].\n\nWhile this paper does provide a new technique with some theoretical justification, unfortunately neither the theoretical justification or experimental results are significant enough to recommend acceptance.  Furthermore, because the paper’s central assumption, that a smooth loss landscape leads to better results, is unsupported by their own experimental results, I must rate the paper a rejection.\n\n[1] Mislav Balunovic and Martin Vechev. Adversarial training and provable defenses: Bridging the gap. In International Conference on Learning Representations, 2020.\n[2] Lyu, Z., Ko, C.-Y., Kong, Z., Wong, N., Lin, D., and Daniel, L. Fastened crown: Tightened neural network robustness certificates.  In AAAI, 2020.\n\n=========================================================================================\nUpdate:\n\nWhile some of my points have been addressed and the quality of the paper has been improved, my main concern, that the experiments do not support the central claim.  \n\nThe authors argue that because their method has a smoother loss landscape then similar methods, it performs better.  In the updated paper, the evidence that the method performs better than similar methods has been made clearer, but the improvement is is still marginal.  The more pressing matter however is that the conclusion that the cause of the improvement is from a change in the loss landscape smoothness is based only on a qualitative comparison of only five methods (as the benefit is not consistent between methods in any category).  This is enough to at best demonstrate a weak correlation, but not enough to demonstrate causation. \n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors argue that tighter relaxations for certified robustness suffer from a worse loss landscape and thus are outperformed by the much simpler and less tight IBP relaxation and come up with a new relaxation to overcome this problem. 

After the rebuttal there still remain doubts about the reasoning regarding the loss landscape (even though I acknowledge that the authors have invested significant amount of work to support their hypothesis). Moreover, the differences to existing certified training methods is small or the proposed method performs worse while being significantly more expensive (in particular if one takes into account the results which are reported on the IBP-Crown github page where the reported numbers are significantly lower than reported in the present paper) so that the benefit is unclear.

Thus the majority of the reviewers still suggests rejection and I agree with that even though I think that the paper has its merits and I encourage the authors to continue this line of work. For a next version, the authors should evaluate all the methods ideally with an exact verification method resp. use the best relaxation for all methods. Otherwise the differences can come just from the weaker relaxation but not from a difference in real robustness.


Decision: Reject