LOSS LANDSCAPE MATTERS: TRAINING CERTIFIABLY ROBUST MODELS WITH FAVORABLE LOSS LAND-
Year: 2020

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: 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.

heading: 1 INTRODUCTION
text: 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 a model that is robust to adversarial attacks (Goodfellow et al., 2014; Papernot et al., 2016; Kurakin et al., 2016; Madry et al., 2018; Tramèr et al., 2017; Zhang et al., 2019a; Xie et 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 & Wagner, 2017). Thus, these defenses can be broken by new attacks (Athalye et al., 2018).
To this end, many training methods have been proposed to build a certifiably robust model that can be guaranteed to be robust to adversarial perturbations (Hein & Andriushchenko, 2017; Raghunathan et 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 a certifiably robust model. These certifiable training methods can be mainly categorized into two types: linear relaxation-based methods and bound propagation methods. Linear relaxation-based methods use relatively tighter bounds, but are slow, hard to scale to large models, and memory-inefficient (Wong & Kolter, 2018; 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 performance, 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 a 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 theoretical analysis to answer these questions. First, we demonstrate that IBP (Gowal et al., 2018) has a more favorable 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 a unified view of IBP and linear relaxation-based methods and find that the relaxed gradient approximation (which will be defined in Definition 1) 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 new certifiable training method that has a favorable landscape with tighter bounds. The performance of the proposed method is comparable to that of state-of-the-art methods 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.
• We propose a certifiable training method with tighter bounds and a favorable loss landscape, obtaining comparable performance with state-of-the-art methods under a wide range of perturbations.

heading: 2 RELATED WORK
text: 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 a robust optimization. Then, a dual problem is considered and a dual feasible solution is used to simplify the computation further. By doing so, Wong & Kolter (2018) built a method that can scale to a 4-layered network, and later, Wong et al. (2018) used Cauchy random projections to scale to much larger networks. However, they are still slow and memory-inefficient. Dvijotham et al. (2018) proposed a method called predictorverifier training (PVT), which uses a 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 to 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.
Mirman et al. (2018) 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 an efficient layerwise computation that exploits interval arithmetic. Over the outer domain, one can compute the worstcase 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 to stabilize the training and to improve the performance.
Both approaches, linear relaxation-based methods and bound propagation methods, use an 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-based methods. 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 relaxationbased 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 a 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 on randomized smoothing (Li et al., 2018; Lecuyer et al., 2019; Cohen et al., 2019; Salman et al., 2019), which can probabilistically certify the robustness with arbitrarily high probability by using a smoothed classifier. However, it requires a large number of samples for inference.
There are many other works on certifiable verification (Weng et al., 2018; Singh et al., 2018a; 2019; 2018b; Zhang et al., 2018; Boopathy et al., 2019; Lyu et al., 2020). However, our work focuses on ”certifiable training”.

heading: 3 BACKGROUND
text: First, we provide a brief overview of certifiable training methods. Then, we consider IBP (Gowal et al., 2018) as a special case of linear relaxation-based methods. This unified view on certifiable 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.

heading: 3.1 NOTATIONS AND CERTIFIABLE TRAINING
text: We consider a c-class classification problem with a neural network f(x;θ) with the layerwise operations z(k) = h(k)(z(k−1)) (k = 1, · · · ,K) and the input z(0) = x in the input space X . The corresponding probability function is denoted by pf = softmax ◦ f : X → [0, 1]c with subscript f . We denote a subnetwork with k operations as h[k] = h(k) ◦ · · · ◦h(1). For a linear operation h(k), we use W (k) and b(k) to denote the weight and the bias for the layer. We consider the robustness of the classifier against the norm-bounded perturbation set B(x, ) = {x′ ∈ X : ||x′−x|| ≤ }with the perturbation level . Here, we mainly focus on the `∞-norm bounded set. To compute the margin between the true class y for the input x and the other classes, we define a c × c matrix C(y) = I − 1e(y)T with (C(y)z(K))m = z (K) m −z(K)y (m = 0, · · · , c− 1). For the last linear layer, the weightsW (K) and the bias b(K) are merged with C(y), that is, W (K) ≡ C(y)W (K) and b(K) ≡ C(y)b(K), yielding the margin score function s(x, y; θ) = C(y)f(x; θ) = f(x; θ) − fy(x; θ)1 satisfying ps = pf . Then we can define the worst-case margin score s∗(x, y, ; θ) = maxx′∈B(x, ) s(x′, y; θ) where max is element-wise maximization. With an upper bound s on the worst-case margin score, s ≥ s∗, we can provide an upper bound on the worst-case loss over valid adversarial perturbations as follows:
L(s(x, y, ;θ), y) ≥ max x′∈B(x, ) L(f(x′;θ), y) (1)
for cross-entropy loss L (Wong & Kolter, 2018). Therefore, we can formulate certifiable training as a minimization of the upper bound, minθ L(s(x, y, ; θ), y), instead of directly solving minθ maxx′∈B(x, ) L(f(x′; θ), y) which is infeasible. Note that adversarial training (Madry et al., 2018) uses a strong iterative gradient-based attack (PGD) to provide a lower bound on the worst-case loss to be minimized, but it cannot provide a certifiably robust model. Whenever possible, we will simplify the notations by omitting variables such as x, y, , and θ.

heading: 3.2 LINEAR RELAXATION-BASED METHODS
text: For a subnetwork h[k], given with the pre-activation upper/lower bounds, u and l, for each nonlinear activation function h in h[k], linear relaxation-based methods (Wong & Kolter (2018); Wong et al. (2018); Zhang et al. (2019b)) use a relaxation of the activation function by two elementwise linear function bounds, h and h, that is, h(z) ≤ h(z) ≤ h(z) for l ≤ z ≤ u. We denote the function bounds as h(z) = a z + b and h(z) = a z + b for some a, b,a, and b, where denotes the elementwise (Hadamard) product. Using all the function bounds h’s and h’s for the nonlinear activations in conjunction with the linear operations in h[k], an ith (scalar) activation h[k]i (·) ∈ R can be upper bounded by a linear function gT · +b over B(x, ) as in Zhang et al. (2018). This can be equivalently explained with the dual relaxation viewpoint in Wong & Kolter (2018). Further details are provided in Appendix C. Now we are ready to upper bound the activation h[k]i over B(x, ). Definition 1 (Linear Relaxation with Relaxed Gradient Approximation). For each neuron activation h [k] i , a linear relaxation method computes an upper approximation of the activation over B(x, ) by using g ∈ Rd and b ∈ R as follows:
max x′∈B(x, )
h [k] i (x ′) ≤ max x′∈B(x, ) gTx′ + b = gTx+ ||g||∗ + b. (2)
We call g the relaxed gradient approximation of h[k]i over B(x, ).
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[k+1] and then for the whole network s. The final bound s on the whole network s can then be used in the objective
(1). The tightness of the bounds s and L(s, y) highly depend on how the linear bounds h and h in each layer are chosen.
Unified view of IBP and linear relaxation-based methods IBP can also be considered as a linear relaxation-based method using zero-slope (a = a = 0) linear bounds, h(z) = u+ and h(z) = l+, where v+ = max(v,0) and v− = min(v,0). Thus, the bounds of a nonlinear activation depend only on the pre-activation bounds u and l for the activation layer, substantially reducing the feedforward/backpropagation computations. CROWN-IBP (Zhang et al., 2019b) applies different linear relaxation schemes to the subnetworks and the whole network. It uses the same linear bounds as IBP for the subnetworks h[k] for k < K except for the network s = h[K] itself, and uses h(z) = u+
u+−l− (z − l−) and h(z) = 1[u+ + l− > 0] z for the whole network s. Moreover, CROWNIBP uses interpolations between two bounds with the mixing weight β, IBP bound and CROWN-IBP bound, with the following objective:
L ( (1− β)sIBP(x, y, ;θ) + βsCROWN-IBP(x, y, ;θ), y ) . (3)
Convex Adversarial Polytope (CAP) (Wong & Kolter, 2018; Wong et al., 2018) uses the linear bounds h(z) = u +
u+−l− (z − l−) and h(z) = u + u+−l− z for all subnetworks h[k] 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 a tighter bound on the worstcase margin score s∗. To specify the linear relaxation variable φ ≡ {a,a, b, b} used in relaxation, we use the notation s(x, y, ;θ,φ). CROWN-IBP and CAP generally yield a much tighter bound than IBP. These relaxation schemes are illustrated in Figure 6 in Appendix D.

heading: 4 WHAT FACTORS INFLUENCE THE PERFORMANCE OF CERTIFIABLE TRAINING?
text: 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-based 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-based methods, and find that the non-smoothness of the relaxed gradient approximation of linear relaxations negatively affects their performance. Detailed settings of the following analyses are presented in Appendix A.

heading: 4.1 LOSS LANDSCAPE OF CERTIFIABLE TRAINING
text: We empirically show that models that have tighter bounds, CROWN-IBP (Zhang 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 relaxation-based methods. For a simple analysis, we avoid considering the mixture of the two logits in (3), and use β = 1 to consider CROWN-IBP logit only. Figure 1 (left) shows the learning curves on CIFAR-10 under train = 8/255. We use -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 0 to the target perturbation train. 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 , CAP and CROWN-IBP have lower losses than IBP as expected because they use much tighter relaxation bounds than IBP. In 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 train = 2/255 on CIFAR-10 (see Table 1 for details). However, at the end of the training, when the perturbation reaches its maximum target value ( train), 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 1 (left). We find that linear relaxation-based methods have large variations, while IBP maintains a 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 et 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 to 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 θ(now) toward the next parameter θ(next) along the gradient in Figure 1 (right). We plot the landscapes for the later phase of the ramp-up period (epochs 50-130) during which large perturbations 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 a sharp local minimum and it may remain stuck there. Therefore, it may overfit to be robust to small perturbations, but is not robust to the target perturbation train.
Next, we establish a relationship between the optimization procedure and linear relaxation. Figure 2 (top) shows the directional deviation between two successive loss gradient steps in terms of cosine similarity during training. Simultaneously, Figure 2 (bottom) shows the ratio of the number of unstable ReLUs for which the pre-activation bounds l 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-IBP. In particular, in the middle of the ramp-up period, CROWN-IBP has a large number of unstable ReLUs and exhibits abrupt changes in gradient steps. It often has deviation angles larger than 90◦, leading to parameter updates in the opposite direction of the previous one, bouncing in the basin of a local minimum. This is consistent with the results
shown in Figure 1. Moreover, since the gradient directions are not well-aligned, it may not enjoy the advantages of momentum-based optimizers and be sensitive to the learning rate. To summarize, a large number of unstable ReLUs, high nonlinearity, leads to an unfavorable landscape that can negatively affect the optimization process.

heading: 4.2 SMOOTHNESS OF RELAXED GRADIENT APPROXIMATION
text: In this section, we investigate the loss landscape further from a theoretical perspective to answer the question: ”What makes some landscapes more favorable than others?” We find that the relaxed gradient approximation of a linear relaxation affects the smoothness of the landscape. First, we need some mild smoothness assumptions that are natural when the network parameters θ1 and θ2 are close to each other, especially they are two consecutive parameters from SGD update. Assumption 1. Given linear relaxation method, we make the following assumptions on the bias b(x;θ) in the linear relaxation and the probability function p(x;θ): (1) ||∇θb(x;θ1)−∇θb(x;θ2)|| ≤ Lbθθ||θ1 − θ2|| for all θ1,θ2 and x. (2) ||p(x;θ1)− p(x;θ1)|| ≤ Lpθ ||θ1 − θ2|| for all θ1,θ2 and x.
With the above assumptions, we can provide an upper bound on the loss gradient difference for linear relaxation-based methods to measure the non-smoothness of the loss landscape as follows: Theorem 1. Given input x ∈ X and perturbation radius , let M be maxx′∈B(x, ) ||x′||. For a linear relaxation-based method with the upper bound sm(x;θ) = maxx′∈B(x, ) g(m)(x;θ)Tx′ + b(m)(x;θ), if b(m) satisfies Assumption 1 (1) for each m and ps satisfies Assumption 1 (2), then
||∇θL(s(x;θ1))−∇θL(s(x;θ2))|| ≤ max
m
( 2 ||∇θg(m)(x;θ1,2)||+M ||∇θg(m)(x;θ1)−∇θg(m)(x;θ2)||+ L(m)||θ1 − θ2|| ) (4)
for any θ1,θ2, where L(m) = Lb (m) θθ + L ps θ ||∇θs(x;θ1,2)|| and θ1,2 can be any of θ1 and θ2.
According to Theorem 1, the relaxed gradient approximations g(m) in the linear relaxation play a major role in 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 approximation g(m) ≡ 0 for all m, the loss difference is upper bounded by only the last term, maxL(m)||θ1 − θ2||, and it is relatively small for a single gradient step. On the other hand, for other linear relaxation-based methods using non-zero relaxed gradient approximation g(m) 6= 0, the gradient updates used in the training are more unstable than IBP. It is consistent with the empirical results shown in Figure 1 that there are significant differences between the loss variations of IBP and others.

heading: 5 PROPOSED METHOD
text: 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 a certifiably robust model. Therefore, we aim to design a new certifiable training method to improve the aforementioned factors (favorable landscape and tighter bound).
More favorable landscape via less a = 1 We observe that CROWN-IBP (β = 1) tends to have more unstable ReLU and less smooth landscape than the others. What, in the objective of CROWNIBP, 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 ∈ {0, 1} with different (p, q) with P (a = 1 | |l| > |u|) = p and P (a = 1 | |l| ≤ |u|) = q for each neuron with preactivation bounds l and u. We use a = 1[u+ + l− > 0] for the other stable ReLUs. For the other elements of the linear relaxation variable φ = {(a,a, b, b)}, we fix a = u+u+−l− , b = − u +l−
u+−l− , and b = 0 for each activation node, because they are the optimal choices for tightening the bound (see Appendix C.2 for details). Figure 3 shows that it tends to have more unstable ReLUs as the number
of a satisfying a = 1 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 tightness is guaranteed. Through manually adjusting the a, variants of CROWN-IBP achieve favorable landscapes, but they show looser upper bounds which lead to a worse performance. Further investigation of variants of CROWN-IBP is presented in Appendix E. Therefore, it is required to search for appropriate values of a that can achieve both tightness and favorable landscape.
Tighter bound via optimization Now, we aim to reduce the number of a satisfying a = 1 and to tighten the upper bound in (1), simultaneously. We can achieve both by minimizing the upper bound over the linear relaxation variable φ as follows:
L(s(x, y, ;θ), y) ≥ min φ L(s(x, y, ;θ,φ), y) ≥ max x′∈B(x, ) L(f(x′;θ), y). (5)
It can be equivalently 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 of s except for s itself, similar to CROWN-IBP. Further, we efficiently compute a surrogate â of the minimizer a∗ = arg mina L(s(x, y, ;θ,φ), y) using the one-step projected gradient update of the relaxation variable a. Specifically, we have
â = Π[0,1]n ( a0 − ηsign(∇aL(s(x, y, ;θ,φ), y)) ) (6)
with an initial point a0 ∼ U [0, 1]n and η ≥ 1, yielding the final objective L(s(x, y, ;θ, φ̂), y) where φ̂ = {(a, â, b, b)}.

heading: 6 EXPERIMENTS
text: 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 a tightness measure as a sum over the worst-case margin for each class m, ∑c−1 m=0 sm(x, y, ;θ), obtained from (2). Then, we 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), CAPIBP, and RANDOM. All methods use the same IBP relaxation for subnetworks, but use different linear relaxation variables a for the whole network s. CROWN-IBP, CAP-IBP, and RANDOM use a = 1[u+ + l− > 0], a = u +
u+−l− and a ∼ U [0, 1]n, respectively. We fix the other variables a, b, and b, as in Section 5. In both figures, our method shows the lowest value on average, which 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.
Smoothness Figure 1 shows that the proposed method has small loss variations along the gradient as with IBP, whereas CROWN-IBP (β = 1) has a wide range of loss values. This is because CROWN-IBP (β = 1) has more unstable ReLUs than our methods as shown in Figure 2. As mentioned above, number of a is closely related to the amount of unstable ReLUs, and Figure 5 shows that our method has successfully reduced the number of a = 1. Further, we conduct analysis on smoothness of the loss landscape with the loss gradient change (the left term in (4)) in Appendix H.
Robustness We evaluate the performance of the proposed method and compare it to that of stateof-the-art certifiable training methods: IBP (Gowal et al., 2018), CROWN-IBP (β = 1) (Zhang et al., 2019b), and CAP (Wong et al., 2018), as in Section 4.1. On MNIST, we follow Zhang et al. (2019b) and use train ≥ test; whereas for CAP, we use the same train = test 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 s of each method.
Table 1 summarizes the evaluation results under different test for each dataset. In general, when test is low, methods with tighter linear relaxations show good performance, whereas IBP tends to perform better as test increases. In short, the state-of-the-art methods perform well for a specific range of test. For example, IBP show relatively better performance in the case of test = 0.3, 0.4 on MNIST and test = 6/255, 8/255, 16/255 on CIFAR-10. On the other hand, CAP and CROWN-IBP (β = 1) outperform IBP in the case of test = 0.1 on MNIST, test = 2/255 on CIFAR-10 and test = 0.001 on SVHN. This result is consistent with the analysis shown in Figure 1 that CAP and CROWN-IBP (β = 1) have lower loss than IBP at small , but their loss landscape is less smooth than IBP, leading to worse performance at large . Moreover, CAP cannot be trained on MNIST when train = 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 ≥ 0.4. On the other hand, the proposed method shows consistent performance in a wide range of test 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 -scheduling. We also compared our method with other prior work (Xiao et al., 2018; Mirman et al., 2018; Balunovic & Vechev, 2019) in Appendix K. We also conduct additional experiments on the hyperparameters in Appendix L, M, and N.
Unlike standard training, certifiable training requires -scheduling. It is implicitly assumed that a set of weights that makes the network robust to a small is a good initial point to learn robustness to a large train. However, linear relaxation-based methods with tighter bounds start with a lower loss at a small , 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 not generalize to a large perturbation. CAP and CROWN-IBP (β = 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 a small , while the smoothness of the proposed method helps the optimization process, which also leads to better performance for a large . To conclude, the proposed method can achieve a decent performance under a wide range of perturbations as shown in Table 1.
Understanding β-scheduling For CROWN-IBP, we use two different settings of β in (7), CROWN-IBP1→1 and CROWN-IBP1→0, where the subscript βstart → βend refers to the linear scheduling on β from βstart to βend. Zhang et al. (2019b) found that the β-scheduling of CROWNIBP1→0 could help to improve the robustness performance. And they argued that this is because training with a tighter bound of CROWN-IBP at the beginning can provide a good initialization for later IBP training. On the other hand, we provide another explanation that CROWN-IBP1→0 starts with a tighter bound (CROWN-IBP only) but not overfits to small perturbation by gradually introducing the IBP objective which has a smoother landscape. Despite using a single objective without the mixture parameter β, the proposed method can outperforms CROWN-IBP1→0 on CIFAR-10 as shown in Table 2.

heading: 7 CONCLUSION
text: 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 robust 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 demonstrated that the proposed method achieves robustness comparable to state-of-the-art methods under a wide range of perturbations. We believe that with an improved understanding of the loss landscape, better certifiably robust models can be built.

heading: A EXPERIMENTAL SETTINGS
text: Datasets and Architectures In 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 variants (Small* and Large*) as follows:
• Small: Conv(·,16,4,2) - Conv(16,32,4,1) - Flatten - FC(·,100) - FC(100,c) • Small*: Conv(·,16,4,2) - Conv(16,32,4,2) - Flatten - FC(·,100) - FC(100,c) • Medium: Conv(·,32,3,1) - Conv(32,32,4,2) - Conv(32,64,3,1) - Conv(64,64,4,2) - Flatten -
FC(·,512) - FC(512,512) - FC(512,c) • Large: Conv(·,64,3,1) - Conv(64,64,3,1) - Conv(64,128,3,2) - Conv(128,128,3,1) -
Conv(128,128,3,1) - Flatten - FC(·,512) - FC(512,c) • Large*: Conv(·,64,3,1) - Conv(64,128,3,2) - Conv(128,128,3,1) - Conv(128,128,3,1) - Flat-
ten - FC(·,512) - FC(512,c)
where Conv(c1, c2, k, s) is a conv layer with input channel c1, output channel c2, kerner size k, and stride s, and FC(d1, d2) is a fully-connected layer with input dimension d1 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 to Appendix C, D of Zhang et al. (2019b) with a single GPU (Titan Xp). We use the following mixed cross-entropy loss as in Zhang et al. (2019b):
κL (f(x;θ), y) + (1− κ)L ( (1− β)sIBP(x, y, ;θ) + βsMODEL(x, y, ;θ), y ) , (7)
where κ is the mixing weight between the natural loss and the robust loss, and β is the mixing weight between the two bounds obtained with IBP and given relaxation method (e.g. CROWN-IBP).
A.1 SETTINGS IN SECTION 4.1
Figure 1 We conduct the experiment in Figure 1 on CIFAR-10 dataset with Medium architecture over all four methods. We train the model with train = 8/255 for 200 epochs using -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 -scheduling ends.
To demonstrate the instability of each training, we describe the variation of the loss along the gradient direction as Santurkar et al. (2018). We take steps of different lengths in the direction of the gradient and measure the loss values obtained at each step. For the sake of consistency, we fix a Cauchy random matrix when evaluating CAP to obtain deterministic loss landscapes, not introducing randomness. The loss variation is computed with
L(s(θ(t))) where L(s(θ)) ≡ L(s(x, y, ;θ), y) and
θ(t) ≡ θ0 − tη∇θL(s(θ0)) for t ∈ [0, 5], (8)
where θ0(= θ(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 1 (right), θ(now) = θ(0) and θ(next) = θ(1).
Figure 2 (top) In Figure 2, with the same model used in Figure 1, we plot cosine similarity between two successive loss gradient steps during training as follows:
cos(∇θL(s(θ(0))),∇θL(s(θ(1)))),
where cos(v1,v2) is the cosine value of the angle between two vectors v1 and v2 .
A.2 SETTINGS IN TABLE 1
For MNIST, we use the same hyper-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 [130,190] epochs. As mentioned in Zhang et al. (2019b), we also found the same issue when training with small (see Appendix N for details). To alleviate the issue, we use train = min(0.4, test + 0.1) for each test as Table 2 of Zhang et al. (2019b).
For CIFAR-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 2× 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 2× 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 1, we use κ-scheduling from 1 to 0. For the corresponding results of κ-scheduling from 0 to 0, we refer the reader to Table 5.
We modify the source code for CAP1 to match our settings. For example, we introduce the warmup period and linear -scheduling. We avoid using the reported results in the literature and aim to make a 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 to the memory limit of CAP, we use a 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 3 of Wong et al. (2018)). Thus, we present the performance with Large*, Medium, and Small* on MNIST, CIFAR-10, and SVHN, respectively. Throughout the experiments, CAP uses the fixed κ = 0.
B INTERVAL BOUND PROPAGATION (IBP)
IBP (Gowal et al., 2018) starts from the interval bound I(0) ≡ {z : l(0) ≤ z ≤ u(0)} = B(x, ) in the input space with the upper bound u(0) = x+ 1 and the lower bound l(0) = x− 1 where 1 is a column vector filled with 1. Then we propagate the interval bound I(k−1) ≡ {z : l(k−1) ≤ z ≤ u(k−1)} by using following equations iteratively:
u(k) = h(k)(u(k−1)) and l(k) = h(k)(l(k−1)) (9)
for element-wise monotonic increasing nonlinear activation h(k) with the pre-activation bounds u(k−1) and l(k−1), and
u(k) = W (k) ( u(k−1) + l(k−1)
2
) + |W (k)| ( u(k−1) − l(k−1)
2
) + b(k) and (10)
l(k) = W (k) ( u(k−1) + l(k−1)
2
) − |W (k)| ( u(k−1) − l(k−1)
2
) + b(k) (11)
for linear function h(k) (k = 1, · · · ,K). Finally, IBP uses the worst-case margin s = u(K) to formulate the objective in (1) for certifiable training.
1https://github.com/locuslab/convex adversarial

heading: C DETAILS ON LINEAR RELAXATION
text: C.1 LINEAR RELAXATION EXPLAINED IN CROWN (ZHANG ET AL., 2018)
To make the paper self-contained, we provide details of linear relaxation given in the supplementary material of CROWN (Zhang et al., 2018). We refer readers to the supplementary for more details. Given a network h[k], we want to upper bound the activation h[k]i . We have h [k] i (x ′) = W (k) i,: h (k−1)(h[k−2](x′)) + b (k) i = W (k) i,: h (k−1)(z(k−2) ′ ) + b (k) i where z (k−2)′ = h[k−2](x′). With the linear function bounds of h (k−1) and h(k−1) on the activation function h(k−1), we have
h [k] i (x ′) = W (k) i,: h (k−1)(z(k−2) ′ ) + b (k) i ≤ ∑
W (k) i,j <0
W (k) i,j h (k−1) j (z
(k−2)′) + ∑
W (k) i,j ≥0
W (k) i,j h (k−1) j (z (k−2)′) + b (k) i
= ∑
W (k) i,j <0
W (k) i,j a (k−1) j z (k−2)′ j + ∑ W
(k) i,j ≥0
W (k) i,j a (k−1) j z (k−2)′ j
+ ∑
W (k) i,j <0
W (k) i,j b (k−1) j + ∑ W
(k) i,j ≥0
W (k) i,j b (k−1) j + b (k) i
= W̃ (k) i,: z (k−2)′ + b̃ (k) i
= W̃ (k) i,: h [k−2](x′) + b̃ (k) i
= W̃ (k) i,:
( W (k−2)(h[k−3](x′)) + b(k−2) ) + b̃
(k) i
= Ŵ (k−2) i,: h (k−3)(z(k−3) ′ ) + b̂ (k−2) i ,
where W̃ (k)i,: = W (k) i,: D (k−1) with the diagonal matrix D(k−1)j,j = a (k−1) j for j satisfying W (k) i,j < 0 and D (k−1) j,j = a (k−1) j for j satisfying W (k) i,j ≥ 0, b̃ (k) i = ∑ W
(k) i,j <0
W (k) i,j b (k−1) j +∑
W (k) i,j ≥0
W (k) i,j b (k−1) j + b (k) i , Ŵ (k−2) i,: = W̃ (k) i,: W (k−2), and b̂(k−2)i = W̃ (k) i,: b (k−2) + b̃ (k) i . Ap-
plying similar method iteratively, we can obtain g and b in (2) for the linear relaxation of h[k]i .
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: ẑ(k+1) = W (k+1)z(k) + b(k+1) and z(k) = h(k)(ẑ(k)) where h(k) is the k-th nonlinear activation function. We can build a primal problem with cT = Cm,: as follows:
max z(K)
cT ẑ(K) (12)
such that
x− 1 ≤ z(0), z(0) ≤ x+ 1,
ẑ(k+1) = W (k+1)z(k) + b(k+1) (k = 0, · · · ,K − 1), and z(k) = h(k)(ẑ(k)) (k = 1, · · · ,K − 1).
Note that our c is negation of that of Wong & Kolter (2018). Now we can derive the dual of the primal (12) as follows:
min ξ+,ξ−≥0
νk
sup z(k),ẑ(k)
cT ˆz(K) + ξ−T (x− 1− z(0)) + ξ+T (z(0) − x− 1)
+ K−1∑ k=0 νTk+1 ( ẑ(k+1) − (W (k+1)z(k) + b(k+1)) ) + K−1∑ k=1 ν̂Tk ( z(k) − h(k)(ẑ(k)) ) = (c+ νK)
T ẑ(K) + (ξ+ − ξ− −W (1)Tν1)Tz(0) + K−1∑ k=1 (−W (k+1)Tνk+1 + ν̂k)Tz(k)
+ K−1∑ k=1 (ν̂Tk h (k)(ẑ(k))− νTk ẑ(k)) (13)
− νT1 b(1) − ξTx− ||ξ||1.

heading: It leads to c+νK = 0, ξ+−ξ−−W (1)Tν1 = 0, and−W (k+1)Tνk+1+ν̂k = 0 (k = 1, · · · ,K−1).
text: Alternatively, they are represented as follows:
νK = −c, ν̂k = W
(k+1)Tνk+1 (k = K − 1, · · · , 1), and ξ = ν̂1.
Now we need relationship between ν̂k and νk, i.e., νk = g(ν̂k). With the further relaxation νk = αk ν̂k, we have a relaxed problem as follows:
min αk sup z(k),ẑ(k) K−1∑ k=1 (ν̂Tk h (k)(ẑ(k))− νTk ẑ(k))− νT1 b(1) − ξTx− ||ξ||1 (14)
such that
νK = −c, ν̂k = W
(k+1)Tνk+1 (k = K − 1, · · · , 1), νk = αk ν̂k (k = K − 1, · · · , 1), and ξ = ν̂1.
We decompose the first term in (14), and ignore the subscript k as follows ν̂Th(ẑ) − (α ν̂)T ẑ. Further, we decompose this for each element, ν̂h(ẑ) − αν̂ẑ = ν̂(h(ẑ) − αẑ). If the pre-activation bounds for h are both positive (active ReLU), then α should be 1 not to make the inner supremum ∞. Similarly, if the pre-activation bounds for h are both negative (dead ReLU), then α should be 0. In the case of unstable ReLU (l ≤ 0 ≤ u), if ν̂ < 0, then we need to solve maxα inf ẑ h(ẑ)−αẑ. The inner infimum is 0 for 0 ≤ α ≤ 1, and is −∞ otherwise. On the other hand, if ν̂ ≥ 0, then we need to solve minα supẑ h(ẑ)−αẑ. The inner supremum is max{u−αu,−αl}, and thus the optimal dual variable is α∗ = uu−l which yields the optimal value (multiplied by ν̂) as ν̂(u − uu−lu) = − ulu−l ν̂ which is equivalent to using linear relaxation with a z + b = uu−l (z − l). We can represent it as a z + b = u+u+−l− (z − l−) to include the case of active/dead ReLU. For the lower linear bound h(z) = a z + b in case of unstable ReLU, we can use any 0 ≤ a ≤ 1 and b = 0 according to the dual relaxation with α. While CAP and CROWN-IBP use a dual feasible solution like α = u +
u+−l− or α = 1[u + + l− > 0], our proposed method aims to optimize over the dual
variable α or equivalently optimize over 0 ≤ a ≤ 1 to further tighten the upper bound on the loss.
D ILLUSTRATION OF LINEAR RELAXATIONS
Figure 6 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 4.

heading: E LEARNING CURVES FOR VARIANTS OF CROWN-IBP
text: It seems that a certifiable training with a 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-IBP (as shown in Figure 7) but they have more unstable ReLUs (as shown in Figure 3) where p/q denotes the variant with sampling a ∈ {0, 1} with P (a = 1 | |l| > |u|) = p and P (a = 1 | |l| ≤ |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 ReLUs, which leads to small loss variations as in Figure 7. Therefore, this observation implies that it is more important to have less a = 1 to have a more smooth landscape.

heading: F PROOF
text: To prove Theorem 1, we first prove the following proposition. We note that θ and g are vectorized and the matrix norm of Jacobian is naturally defined - for example, ||∇θg|| is induced by the vector norms defined in X and Θ. Proposition 1. Given input x ∈ X and perturbation radius , let M = max{||x′|| : x′ ∈ B(x, )}. Then, for the upper bound s(x;θ) = maxx′∈B(x, ) g(x;θ)Tx′ + b(x;θ) with b satisfying Assumption 1 (1), we have
||∇θs(x;θ1)−∇θs(x;θ2)|| ≤ 2 ||∇θg(x;θ1,2)||+M ||∇θg(x;θ1)−∇θg(x;θ2)||+ Lbθθ||θ1 − θ2|| (15)
for any θ1,θ2, where θ1,2 can be any of θ1 and θ2.
Proof. Say f(x′;θ) = g(x;θ)Tx′ + b(x;θ) and the maximizer x∗i = arg maxx′∈B(x, ) f(x ′;θi) for each θi = θ1,θ2. Then, we have
||∇θs(x;θ1)−∇θs(x;θ2)|| = ||∇θf(x∗1;θ1)−∇θf(x∗2;θ2)|| = ||∇θf(x∗1;θ1)−∇θf(x∗2;θ1) +∇θf(x∗2;θ1)−∇θf(x∗2;θ2)|| ≤ ||∇θf(x∗1;θ1)−∇θf(x∗2;θ1)||+ ||∇θf(x∗2;θ1)−∇θf(x∗2;θ2)||. (16)
The first term on the RHS can be upper bounded as follows:
||∇θf(x∗1;θ1)−∇θf(x∗2;θ1)|| = ||∇θ(g̃1T x̃∗1 − g̃1T x̃∗2)|| = ||∇θ(gT1 x∗1 − g1Tx∗2)|| = ||∇θg1(x∗1 − x∗2)|| ≤ 2 ||∇θg1||,
where gi = g(x;θi), bi = b(x;θi), g̃Ti = [g T i ; bi] and x̃ T = [xT ; 1]. And the second term on the RHS can be upper bounded as follows:
||∇θf(x∗2;θ1)−∇θf(x∗2;θ2)|| = ||∇θ(g̃1T x̃∗2 − g̃2T x̃∗2)|| = ||∇θ(g̃1 − g̃2)x̃∗2|| ≤ ||∇θ(g1 − g2)||||x∗2||+ ||∇θ(b1 − b2)|| ≤M ||∇θ(g1 − g2)||+ Lbθθ||θ1 − θ2||,
Therefore, we obtain
||∇θs(x;θ1)−∇θs(x;θ2)|| ≤ 2 ||∇θg1||+M ||∇θ(g1 − g2)||+ Lbθθ||θ1 − θ2|| = 2 ||∇θg(x;θ1)||+M ||∇θg(x;θ1)−∇θg(x;θ2)||+ Lbθθ||θ1 − θ2||.
Note that θ1 in the first term is arbitrarily chosen in (16). Therefore, this leads to the final inequality (15).
Theorem 1. Given input x ∈ X and perturbation radius , let M be maxx′∈B(x, ) ||x′||. For a linear relaxation-based method with the upper bound sm(x;θ) = maxx′∈B(x, ) g(m)(x;θ)Tx′ + b(m)(x;θ), if b(m) satisfies Assumption 1 (1) for each m and ps satisfies Assumption 1 (2), then
||∇θL(s(x;θ1))−∇θL(s(x;θ2))|| ≤ max
m
( 2 ||∇θg(m)(x;θ1,2)||+M ||∇θg(m)(x;θ1)−∇θg(m)(x;θ2)||+ L(m)||θ1 − θ2|| ) (4)
for any θ1,θ2, where L(m) = Lb (m) θθ + L ps θ ||∇θs(x;θ1,2)|| and θ1,2 can be any of θ1 and θ2.
Proof. We simplify the notation ps as p. Then we have
||∇θL(s(x;θ1))−∇θL(s(x;θ2))|| = ||∇θs(x;θ1)∇sL(s(x;θ1))−∇θs(x;θ2)∇sL(s(x;θ2))|| = ||
∑ m ∇θsm(x;θ1)(pm(x;θ1)− δy,m)−∇θsm(x;θ2)(pm(x;θ2)− δy,m)||
= ||∇θs(x;θ1)(p(x;θ1)− e(y))−∇θs(x;θ2)(p(x;θ2)− e(y))|| = ||∇θs(x;θ1)p(x;θ1)−∇θs(x;θ2)p(x;θ2)|| = ||∇θs(x;θ1)p(x;θ1)−∇θs(x;θ1)p(x;θ2) +∇θs(x;θ1)p(x;θ2)−∇θs(x;θ2)p(x;θ2)|| = ||∇θs(x;θ1)(p(x;θ1)− p(x;θ2)) + (∇θs(x;θ1)−∇θs(x;θ2))p(x;θ2)|| ≤ ||∇θs(x;θ1)||||p(x;θ1)− p(x;θ2)||+ max
m ||∇θsm(x;θ1)−∇θsm(x;θ2)||
≤ ||∇θs(x;θ1)||Lpθ ||θ1 − θ2||+ maxm ||∇θsm(x;θ1)−∇θsm(x;θ2)||
≤ max m
( 2 ||∇θg(m)(x;θ1,2)||+M ||∇θg(m)(x;θ1)−∇θg(m)(x;θ2)||+ L(m)||θ1 − θ2|| )
G LEARNING CURVE FOR train
Figure 9 shows the learning curves for the target perturbation train during the ramp-up period, while Figure 1 shows the corresponding curves for the scheduled value of . The two figures use the same settings in Appendix A.1.

heading: H SMOOTHNESS
text: We empirically measure the non-smoothness of the loss landscape with the difference between the two consecutive loss gradients at θ1 = θ(0) and θ2 = θ(1) in (8), says gradient difference (≡ ||∇θL(x;θ(0))−∇θL(x;θ(1))||). It is highly related to the ratio of the number of unstable ReLUs (nonlinearity of the classifier) as shown in Figure 10.

heading: I MODE CONNECTIVITY
text: In this section, we check the mode connectivity (Garipov et al., 2018) between two models that are trained using certifiable training methods. Mode connectivity is a 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 w0 and w1 be two sets of weight corresponding to two different well-trained neural networks. Moreover, let φθc(t) with t ∈ [0, 1] be a continuous piece-wise smooth parametric curve with parameters θc such that φθc(0) = w0 and φθc(1) = w1. To find a low-loss path between w0 and w1, Garipov et al. (2018) suggested to find the parameter θc that minimizes the expectation of a loss `(w) over a distribution qθc(t) on the curve,
L(θc) = Et∼qθc (t)[`(φθc(t)].
To optimize L(θc) for θc, we use uniform distribution U [0, 1] as qθc(t) and Bezier curve (Farouki, 2012) as φθc(t), which provides a convenient parameterization of smoothness on the paths connecting two end points (w0 and w1) as follows:
φθc(t) = (1− t)2w0 + 2t(1− t)θc + t2w1, 0 ≤ t ≤ 1.
A path φθc is said to have a barrier if ∃t such that `(φθc(t)) > max{`(w0), `(w1)}. The existence of a 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 CROWNIBP and IBP, we use the loss function used on each model as a user-specified loss for training the parametric curve φθc . Therefore, we can obtain two curves as depicted in Figure 11, 12, and 13 for each pair of models. Here, we use the identical settings in Appendix A.1.
Figure 11 shows the mode-connectivity between CROWN-IBP and IBP. We use CROWN-IBP loss as user-specific loss in Figure 11a and IBP loss in Figure 11b. In this figure, we find that using CROWN-IBP loss (11a), there exists a barrier between the two models. This suggests they are not connected by the path in terms of CROWN-IBP loss. However, with IBP loss, there is no loss barrier separating the two models. This indicates that using CROWN-IBP, it is hard to optimize the parameters from w0 to w1, 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 IBP bound or OURS bound, since there exists a barrier in both curves. In this figure, we can also notify that OURS has tighter bounds than IBP because the value of the loss function using OURS is lower than that of IBP.
Finally, Figure 13 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 a loss function, the robust loss generally decreases as the t increases. It shows that OURS has much favorable loss landscape compared to CROWN-IBP. In addition, we can find that OURS has a tighter bound than CROWN-IBP, since the value of the robust loss using OURS is lower than CROWN-IBP.

heading: J RELU
text: In this section, we investigate how pre-activation bounds u and l for the activation layer change during training. For each activation node, it is said to be ”active” when the pre-activation bounds are both positive (0 < l ≤ u), ”unstable” when they span zero (l ≤ 0 ≤ u), and ”dead” when they are both negative (l ≤ u < 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 to the other three methods. Simultaneously, CROWN-IBP has the lowest ratio of dead ReLUs.
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 of dead ReLUs increases.
Figure 16 depicts the histograms of the distribution of the slope u +
u+−l− of the unstable ReLUs during the ramp-up period. In the early stages of CAP training, the slope distribution is concentrated around 0.4. However as the training progresses with a larger , the histogram distribution moves to left, which indicates unstable ReLUs change to dead ReLUs. 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. It is the same with the results in Figure 15b, which shows that number of active ReLUs increases during training.

heading: K COMPARISON WITH OTHER PRIOR WORK
text: All experiments and results (except for Table 4) in this paper are based on our own reimplementation. For the unimplemented prior work, we compare to the best reported results in the literature in Table 4. We note that the results in Xiao et al. (2018) and Balunovic & Vechev (2019) are evaluated with a MILP based exact verifier (Tjeng et al., 2017).
L β- AND κ-SCHEDULINGS
Table 5 shows the evaluation results of the models as in Table 1 but trained with different κscheduling (from 0 to 0). Table 6 shows the evaluation results of the proposed models trained with different κ- and β-schedulings.

heading: M ONE-STEP VS MULTI-STEP
text: To get a tighter bound, we propose multi-step version of (6) as follows: at+1 = Π[0,1]n ( at − αsign(∇aL(s(x, y, ;θ,φ), y)) ) . (17)
We compare the original 1-step method (α ≥ 1) to 7-step (t = 7) method with α = 0.1. The results are summarized in Table 7. 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.
N TRAIN WITH train ≥ test N.1 train ≥ test ON MNIST
Zhang et al. (2019b) and Gowal et al. (2018) observed that IBP performs better when using train ≥ test than train = test. Figure 8 shows the results with different train’s for each test. The overfitting issue is more prominent in the case of IBP and CROWN-IBP1→0 than the proposed method and CROWN-IBP1→1. However, using larger perturbations compromises the standard accuracy, and thus it is desirable to use smaller train.
N.2 train = 1.1 test ON CIFAR-10
As mentioned in Gowal et al. (2018), we also train with train = 1.1 test on CIFAR-10. The results are shown in Table 9. They attain slightly improved performances in 2/255, but not in 8/255 and larger .

heading: O TRAINING TIME
text: All the training times are measured on a single TITAN X (Pascal) on Medium for CIFAR-10. We train with a batch size of 128 for OURS, CROWN-IBP1→1 and IBP, but with a 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-IBP1→1: 51.68 sec / epoch • IBP: 14.85 sec / epoch • CAP (batch size 32, 1 GPU): 751.0 sec / epoch • CAP (batch size 64, 1 GPU): 724.6 sec / epoch • CAP (batch size 128, 2 GPUs): 387.9 sec / epoch

heading: P LOSS AND TIGHTNESS VIOLIN PLOTS
text: We plot the equivalent tightness violin plots in Section 6 for models trained with other methods. The proposed method achieves the best results in terms of loss and tightness followed by CROWN-IBP, CAP-IBP, and RANDOM. Figure 17 (a)-(b), (c)-(d), and (e)-(f) show the tightness evaluated on the model trained by CROWN-IBP1→0, CROWN-IBP1→1 and IBP, respectively.

heading: Q COMPARISON WITH CAP-IBP
text: As in section E, we train a model with CAP-IBP and compare with the proposed method and CROWN-IBP (β = 1). Figure 18 shows that CAP-IBP has gradient differences (defined in Section H) larger than the proposed method and smaller than CROWN-IBP (β = 1), which leads to a performance between the proposed method and CROWN-IBP (β = 1) (see Table 3). CAP-IBP has looser bounds than CROWN-IBP (β = 1) as shown in Figure 4 and Figure 17, but with a relatively more smooth landscape, it can achieve a better performance than CROWN-IBP (β = 1).

heading: R RELU STABILITY
text: To see the effect of unstable ReLUs on smoothness, we adopt the ReLU stability loss (RS loss) LRS(u, l) = −tanh(1 + u · l) as a regularizer (Xiao et al., 2018). We use L + λLRS as a loss and run CROWN-IBP (β = 1) with various λ settings. We plot the smoothness and the tightness in Figure 19 and Figure 20 on λ = 0, λ = 0.01, λ = 10.
We found that small λ suggested in Xiao et al. (2018) has no effect on reducing the number of unstable ReLUs since certifiable methods have smaller unstable ReLUs as shown in Figure 15, and thus not on improving the smoothness. By increasing λ, we observed that RS successfully reduces the number of unstable ReLUs with λ = 10. Figure 19 shows that large λ leads to a 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 a large λ ≥ 1 couldn’t obtain a tightness of the upper bound and significant improvement on robustness as 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 λ = 10.

Review summaries:
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.

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.