On the Paradox of Certified Training
Authors: Nikola Jovanović
Mislav Balunovic
Maximilian Baader
Martin Vechev
Venue: Accepted by TMLR ()

Abstract: Certified defenses based on convex relaxations are an established technique for training provably robust models. The key component is the choice of relaxation, varying from simple intervals to tight polyhedra. Counterintuitively, loose interval-based training often leads to higher certified robustness than what can be achieved with tighter relaxations, which is a well-known but poorly understood paradox. While recent works introduced various improvements aiming to circumvent this issue in practice, the fundamental problem of training models with high certified robustness remains unsolved. In this work, we investigate the underlying reasons behind the paradox and identify two key properties of relaxations, beyond tightness, that impact certified training dynamics: continuity and sensitivity. Our extensive experimental evaluation with a number of popular convex relaxations provides strong evidence that these factors can explain the drop in certified robustness observed for tighter relaxations. We also systematically explore modifications of existing relaxations and discover that improving unfavorable properties is challenging, as such attempts often harm other properties, revealing a complex tradeoff. Our findings represent an important first step towards understanding the intricate optimization challenges involved in certified training.

Published in Transactions on Machine Learning Research (10/2022)
On the Paradox of Certified Training
Nikola Jovanović*
Deportment of Computer Science, ETH Zurich
Mislav Balunovié*
Deportment of Computer Science, ETTH Zurich
Maximilian Baader
vbbaader www..........ccc....o..
Deportment of Computer Science, ETH Zurich
Martin Vechev
marlin.vecheeiinf.ce
Department of Computer Science, ETH Zurich
* Equal contribution
Reviewed on OpenReview: https: // openreview. net/ forum? id= aHJLLyy448
Abstract
Certified defenses based on convex relaxations provably robust models. The key component is the choice of relaxation, varying from simple intervals to tight polyhedra. Counterintuitively, loose interval-based training often leads to higher certified robustness than what can be achieved with tighter relaxations, which a well-known but poorly understood paradox. While recent works introduced various improvements aiming to circumvent this issue practice, the fundamental problem of training models with high certified robustness remains unsolved. In this work, we investigate the underlying reasons behind the paradox and identify two key properties of relaxations, beyond tightness, that impact certified training dynamics: continuity and sensitivity. Our extensive experimental evaluation with number of popular convex relaxations provides strong evidence that these factors can explain the drop in certified robustness observed for tighter relaxations. We also systematically explore modifications of existing relaxations and discover that improving unfavorable properties challenging, as such attempts often harm other properties, revealing complex tradeoff. Our findings represent an important first step Lowards understanding the intricate optimization challenges involved in certified training.
established technique for training
1 Introduction
Recent years have witnessed an increased interest in developing methods for efficiently training provably robust machine learning models. Several core techniques are based on convex relaxations (e.g., CROWN (Zhang et al., 2018), hBox (Mirman et al., 2018)), which provide robustness guarantees by approximating the effect of network layers on the input specification. key property of convex relaxation is its lightness, indicating how close it to the non-convex shape it overapproximates.
The Paradox of Certified Training. As tighter relaxations more desirable for certification (Salman et al., 2019b; Singh et al., 2019b), natural belief is that tightness is also favorable for relaxations when used in training as part of certified defense. Surprisingly, several prior works (Gowal et al., 2018; 2019; Zhang et al., 2020; Balunovic & Vechev, 2020; Lyu et al., 2021; Lee et al., 2021) have noticed that training with IBP (Gowal et al., 2018), which is a loose relaxation that performs poorly for certification of undefended models, allows for higher certified robustness compared to training with tighter relaxations. We illustrate this on real model in Table 1. We easily observe a paradox: tighter relarations obtain worse results. More specifically, none of the tighter relaxations can consistently outperform the loose IBP.

---

Published in Transactions on Machine Learning Research (10/2022)
Table The Paradox of Certified Training: training with tighter relaxations leads to worse certified robustness, failing to outperform the loose IBP relaxation. Tightness formalization and further details given in Section 3.
Relaxation
Tightness
Certified (%)
IBP / Box
0.73
86.8
hBox / Symbolic Intervals
1.76
83.7 7
CROWN / DeepPoly
3.36
70.2
DeepZ / CAP FastLin / Neurify
3.00
69.8
CROWN-IBP (R)
2.15
75.4
The paradox has strongly influenced the field of certified training, While some hypothesize that it occurs due to tighter relaxations introducing difficult optimization problems (Balunovic & Vechev, 2020; Lee et al., 2021), the underlying reasons for this difficulty remain unclear. Identifying these reasons and understanding how relaxations affect training is important yet very challenging as: (i) couvex relaxations require more complex (symbolic) computations than those of standard (concrete) forward passes, and thus cannot directly benefit from existing convergence results, and (ii) relaxations come with different, previously unexplored properties, and identifying preciscly those which affect certified training, is difficult. In light of this, recent advances primarily focus miligating the practical effects of the paradox by improving the underlying optimization (Balunovic & Vechev, 2020; Zhang et al., 2020; Shi et al., 2021; Lyu et al., 2021). While these developments have advanced the state of the art, a large gap between empirical and provable robustness of models remains (Li et al., 2020; Croce et al., 2020), and we still lack principled investigations of the paradox.
This Work. In this work we take a step towards addressing this void and understanding the paradox of certified training. We hypothesize that two additional properties beyond tightness strongly impact certified training. First, we notice that some relaxations optimize discontinuous losses during training. Second, we find that some relaxations are sensilive to changes in weights, introducing locally non-linear loss landscapes. As they induce more complex losses, both of these properties can have negative impact on optimization, and consequently lead to low certified robustness.
While the results in Table seem contradictory considering only tightness, additionally considering continuity and scnsitivity provides a more viable explanation and helps demystify the paradox. Concretely, tighter relaxations in Table they do not outperform the continuous and non-sensitive IBP. On range of datasets and architectures, experimental evaluation further substantiates the importance of considering these two additional properties in order to gain deeper understanding of certified training dynamics.
harmed by discontinuity or high sensitivity of their loss, shedding light on why
Main Contributions. Our key contributions are:
Two fundamental properties, continuity and sensitivity, that along with tightness influence the success of a convex relaxation when used in certified training (Section 4).
Extensive experiments on a range of convex relaxations, substantiating our hypothesis that considering continuity and sensitivity is necessary to understand the paradox of certified training (Section 5).
A study of systematic changes to existing relaxations, showing that improving an unfavorable property of a relaxation is challenging, as this often negatively affects other properties (Section 6).
We believe the ideas presented in our work benefit further investigations of the paradox, as well as future attempts to derive new certified defenses that obtain state-of-the-art experimental results. Our paper is structured as follows. First, we provide the necessary background (Section 2) and state the paradox more formally (Section 3). In Section 4, we present our core results on continuity and sensitivity popular relaxations. In Section 5, we provide detailed experimental evidence supporting our findings. Finally, Section we present a study of relaxation modifications, demonstrating complex dependencies between properties which complicate the process of improving unfavorable properties of existing relaxations.
2

---

Published in Transactions on Machine Learning Research (10/2022)
2 Background and Related Work
We now discuss related work and provide the necessary background on training and certifying with convex relaxations. We present this background within a common framework (Salman et al., 2019b), capturing various single neuron relaxations to simplify analysis and comparison.
The discovery that neural networks are not robust to small input perturbations (Szegedy al., 2013) led to defenses based on adversarial training (Goodfellow et al., 2015; Madry et al., 2018), hardening the model by training with adversarial examples. While adversarial defenses attain good empirical robustness, they lack robustness guarantees. Popular certification methods leverage convex relaxations (Wong & Kolter, 2018; Gehr et al., 2018; Singh et al., 2018; Raghmaatha et al., 2018b; Singh et al., 2019b; Dathathri et al., 2020; Xu et al., 2020; Lyu et al., 2021), a comprehensive exposition of which can be found in Salman et al. (2019b)- here, we only provide an overview needed to understand our work. We focus on linear relarations, as they are scalable (e.g,, can certify ResNet34 (Serre et al., 2021)), contrary to SDP (Raghunathan et al., 2018b; Dathathri et al., 2020) which is limited to smaller networks. Other, prohibitively costly approaches, use multi-neuron relaxations (Singh et al., 2019a; Tjandraatmadja et al., 2020; Müller et al., 2021; Wang et al., 2021a), rely on SMT (Katz et al., 2017) and MILP (Tjeng et al., 2019) solvers. Two fundamentally different competitive approaches, not our focus, are -di-ittancce nets (Zhang el al., 2021), used logether with relaxations, that also give rise to optimization difficulties (recently tackled in Zhang et al. (2022)), and randomized smoothing (Cohen et al., 2019; Salman et al., 2019a) which is more scalable than convex relaxations but offers only probabilistic guarantees, and introduces work at inference time, making it unsuitable for certain applications.
Setting. We consider L-layer feedforward ReLU network h = h2 h .... o h2 with parameters 0, where h;: 1R=--1 + R" is the transformation applied at layer i. Let the network input be To E "0 and let a; := h4 o...o o h1 (2x) be the result after layer i, for i E [L], where [4] := (1..... L}. Each h2 is either a dense/convolutional layer, both of which can be viewed as an affine transformation æ; = W + b;, or a nonlinear ReLU layer x, = max(x;-1.0)) 0), where max is applied componentwise. Further, we assume the two layer types alternate, with h, and h,. being affine. We focus on classification, where inputs zo are classified to one of ny classes based on the logit vector = æt, and the case of loe robustness. Namely, to certify robust classification to label y in an foo ball of radius
around æ, we prove that for every y # y
<=><0, <0 = h(@r), Yæo, || zoll,0 <e,
(1)
where Cy' = Ey Ey. by upper bounding the left-hand side with negative value.
Given some e, and a set D of input examples (ax, y) E I" x [nz], we use CR(O,e,m) E [0, 1] to denote the certified robusiness of network with parameters under certification method m, ie., the ratio of examples from D for which m is able to prove that the network satisfies Equation 1.
Convex Relaxations. On an intutive level, convex relaxations are class of methods for robustness certification of neural networks that attempt to prove Equation 1 by deriving and propagating bounds on possible values of intermediate results, ovcrapproximating (i.c., relaring) the effect of non-lincar activations in the network to obtain a computationally efficient certificate.
More formally, certification with convex relaxations proceeds through the network layer by layer, producing elementwise lower and upper bounds of æ,, 4 E l and u, E R. respectively. Starting from 4n x c and uo- x + we aim to obtain 4t and ut, which yields the desired upper bounds of oi for all y', allowing to verify the robustness property. To this end, all following methods (linear relaxations) maintain one upper and one lower lincar bound for each neuron Fijj of layer i:
a.j² T x + dy S Fzy S a.j T x1 + dej.
(2)
where agy aij E TR and dey, E for all j E [m.). Excluding the IBP relaxation, all methods use Fig = (Wa0,=1); + bay for linear layer bounds, It,j = 0 if 4-115 < 0 and Tig = xz-1 if 4-1, 2 0 for stable ReLU bounds, and calculate 4 and u, using backsubstitution introduced next. Unstable ReLU (4-1J < 0 < 1.5) bounds are method specifc- and can depend on 4-1 and u-11
Backsubstitution. Starting with æ.j S a.j" x1-1 + diy (similarly for the lower bound), we substitute x;-1 by replacing each 11 with its respective upper bound a 222 di-13/ if (aig)y is positive and with its
3

---

Published in Transactions on Machine Learning Research (10/2022)
Fi.j
Zig
Fig ^
I 1111
1,j
1,j
(a) Deep'
(b) IBP
(c) CROWN & CROWN-IBP (R)
& hBox
Figure 1: Illustration of unstable ReLU convex relaxations for methods introduced in Section 2.
lower bound otherwise. This is repeated recursively through the layers until we reach constraints of the form
Pj T xo qj Jz, p. xo Tj.
(3)
where Pj_ Pj" E To and Jz 25 R for all j E [nx]. Here,
in turn substitute the appropriate side of to Eo ug for each element in Lo to obtain lower and upper bound 4.j and Way Fif solely w.r.t. the bounds of Zo. We provide further details of this procedure in Appendix A.
Note that while some of the relaxations have more efficient implementations, they produce the same outputs as our formulation. We use this formulation as it allows us to capture all of the needed relaxations, and further, our results are conceptual and hold for any implementation.
Tightness. Given a network robust around æ, the success of certification with a relaxation depends on its tightness. Intuitively, tighter relaxations utilize overapproximations that are closer to the approximated non-convex shapes, and produce tighter bounds 4.j and uaj on each Fig. For small number of relaxation pairs r2), e.g., hBox and IBP (see Appendix B.2), we can prove that Ti is strictly tighter than (i.e., each bound is strictly tighter), implying that for any fixed network and perturbation, every example that is certified by r2 is also certified by r1- For most other pairs there is a consistent empirical understanding of relative tightness (Salman et al., 2019b; Singh et al., 2019b), which we will aim to quantify in Section 3. We now proceed to introduce the specifics of commonly used relaxations.
DeepZ. The Deep2 relaxation (Singh et al., 2018), equivalent to CAP (Wong & Kolter, 2018), List-Lin (Weng et al., 2018), and Neurify (Wang et al., 2018b), uses the following for unstable ReLUs (Figure la):
Axi-15 I mij S A M4-1,1
where A x= 1:---1//(u--1 - 44-1))
IBP/hBo /hBox. The IBP (Gowal et al., 2018) or Box (Mirman al., 2018; Gehr al., 2018) relaxation uses interval arithmetic instead of backsubstitution, ignoring other dependencies. For affine layers, the upper bound (similarly for the lower bound) is (W,h;-1); + bij where hi-1. M4-1.j if the corresponding element of W; is positive, and h = 4-11, otherwise. For ReLU, it uses ReLU(4-1,) S æijj S (ReLU(u;1.)) (Figure 1b). hBor is an instantiation of a hybrid zonotope (Mirman et al., 2018), also called symbolic interval in Wang et al. (2018a). It uses the same bounds as IBP, 0 S Fij I u4-15, for unstable ReLUs, replacing Vi with these bounds in the rest of backsubstitution. For stable ReLUs and affine layers, as with all other methods except IBP, it uses Fi.j (W, + big and vi.j = I1-1. (I = 0), respectively.
(R). CROWN (Zhang et al., 2018) and DeepPoly (Singh et al., 2019b) have the same upper bound as DeepZ. for unstable ReLUs, but choose the lower bound adaptively: 0 S 2s if -4411,3 2 un-1jj or I;-1,5 S Fi,y otherwise (Figure Ic). CROWN-IBP (R) (Zhang et al., 2020) is a variant which efficiently computes I; and u; using IBP at all layers except the last, which uses CROWN and performs a full backsubstitution.
FROWN/CROWN.R
Certified Training. While adversarial training often improves empirical robustness, certified robustness
(ratio of inputs where we can guarantee robustness as in Equation 1) usually remains low for all relaxations,
4

---

Published in Transactions on Machine Learning Research (10/2022)
Certified Robustness
100%
IBP
80%
hBox
60%
CROWN
DeepZ
40%-
CROWN-IBP (R)
20%
0.00
0.01
0.02
0.03
0.04
0.05
0.06
0.07
Perturbation Radius
Figure 2: CR (certified robustness) curves of relaxations on convolutional network trained on MNIST.
known observation reaffirmed in Appendix B.1. Certified training (Wong & Kolter, 2018; Mirman et al., 2018; Gowal et al., 2018; Raghunathan et al., 2018a; Zhang el al., 2020; Lyu et al., 2021) addresses this, aiming to produce networks amenable to certification by incorporating the certification method into training, and minimizing the cross-entropy loss (c where & is the worst case logit, s.t., 2y L, and by u1, for all y' + y-
All above relaxations can be used in certified training, but certified robustness obtained this way is far from the theoretical limit Baader et al. (2020) proved that IBP-certified networks can approximate any continuous function arbitrarily precisely. Note that in the following, we differentiate certified training with the CROWN-IBP (R) relaxation (3: 1-1 in (Zhang et al., 2020)) from the certified defense CROWN-IBP (8: 1 in (Zhang al., 2020)) which combines CROWN-IBP (R) and IBP losses in training.
3 The Paradox of Certified Training
We now present the paradox of certified training, a well-known observation that has limited the applicability of certified defenses practice, and discuss existing hypotheses that attempt to explain it.
Tightness Should Help Training. Recall from Section 2 that while can rarely prove that relaxation is strictly tighter than another relaxation, there is a consistent empirical understanding of their relative tightness. We illustrate this in Figure by comparing cerlified robusiness (CR) curces of relaxations fixed naturally trained MNIST network. We further quantify empirical tightness as CR-AUC, the area under the CR curve. While CR-AUC varies based on network choice and the training method, for a fixed setting, it can be used to compare tightness of methods, and we use in the following when referring to tightness. As tighter relaxations certify more examples when applied naturally trained networks, it is natural to assume that this effect extends to certified training, i.e., training with a tighter method should lead to higher CR.
a
Training with Tighter Relaxations Leads to Worse Results. Surprisingly, it is well established (Gowal et al., 2018; 2019; Balunovic & Vechev, 2020; Zhang et al., 2020; Lee et al., 2021) that this is not the case in practice, and tightness can in fact harm certified robustness when a relaxation is used in training, Most notably, it has been observed that IBP training often outperforms training with DeepZ and CROWN which are (empirically) tighter. We refer this phenomenon as the paradox of certified training. We illustrate this paradox in Table 1, where we report CR-AUC (from the experiment in Figure 2) and certified robustness (with etest 0.3) after certified training of the same MNIST network with each relaxation.
Existing Hypotheses. While recent state-of-the-art certified defenses based convex relaxations (Balunovic & Vochev, 2020; Zhang et al., 2020; Shi et al., 2021; Lyu et al., 2021) focus on mitigating the paradox in practice, the fundamental reasons behind it were so far poorly understood. Some conjecture that tighter relaxations over-regularize the network (Zhang et al., 2020), yield hard optimization problems (Balunovic & Vechev, 2020), or simply state that they unexpoctedly underperform (Gowal et al., 2018; 2019; Lyu et al., 2021), but they have not investigated this further. Lee et al. (2021) provide limited theoretical results that attempt to give insights into the paradox, but are unable to explain the results of most relaxations
5

---

Published in Transactions on Machine Learning Research (10/2022)
(e.g., hBox, CROWN, CROWN-IBP (R)) as these are discontintous (Section 4.2), thus directly violating their Lipschitz continuity assumptions.
4 Properties of Convex Relaxations
We investigate the reasons behind the paradox discussed in Section 3. Concretely, we introduce two key properties of relaxations, continuity and sensitivity, and use them alongside tightness, which was the main focus prior work, to improve our understanding of the paradox.
4.1 Tightness of Convex Relaxations
While tightness alone cannot explain the performance differences, it still has significant role in the final certified robustness. We highlight this with the following theorem:
Theorem 1. Let r and r2 be two conver relaxations, where r1 is known to be strictly tighter than r2- For a network parametrized by 0 and any c 2 O, it holds that maxe CR(O, c, 2 maxe CR(O,, c, r2).
The theorem (see the proof in Appendix B.3) tells us that with a perfect optimizer, tightness would be the sole performance factor of relaxations, provided that one strictly tighter than the other. However, our results in Table demonstrate that this does not happen in practice, e.g., despite hBox being strictly tighter than IBP, training with it results in worse certified robustness. Clearly, pradient-based optimization in practice leads to worse parameters for tighter relaxations and the underlying reasons are unclear.
4.2 Continuity of Convex Relaxations
While convex relaxations represent layer constraints as convex sets, the training loss is not necessarily convex with respect to network weights. Morcover, we observe that some relaxations create a disconlinuous loss landscape, harming first-order optimization as gradients near the discontinuity do not provide any information about the function values after the discontimuity (see Section 4.4). We show that CROWN, CROWN-IBP (R), and hBox all suffer from this problem. In Section 5.1 we show that these relaxalions have many discontinuities when instantiated on realistic network, but here we focus on a minimal example to better illustrate the core issue. Note that our definition of continuity is binary and depends only on the convex relaxation, without requiring knowledge of the architecture nor the training process. There could be other, more fine-grained numerical definitions, such counting the number of discontinuities (see for example Figure 6 Table 4) along a certain trajectory, but these may depend on the setting and necessarily require running the training, as they cannot be computed beforehand. See Appendix 1 for a further discussion.
2.
Lower Bound
1
-1-
CROWN
hBox
-1
Parameter Value (w)
Figure Discontinuity of CROWN and hBox.
We focus on the discontinuity of the output layer lower bounds L1 treating each 4,f as a function of the network weights. Note that all findings can be easily extended to the actual loss function (er y). We construct a minimal example to produce the discontinuities: a 3-layer network with input Fp E 1- 1, 1], affine layer I1,1 x1,2 = T0,1
where is the only network parameter, ReLU layer 22,1 ReLU(x).); 22.2 Re),( and the output layer given Ø3,1 22,1 and 23,2 F2,2 I2,1 (see Appendix C.1 for illustration of the network). Figure 3 shows the discontinuities that arisc when varying the parameter w.
Discontinuity of CROWN and CROWN-IBP (R). For CROWN, the discontinuities arise due to its adaptive choice of the lower bound for unstable ReLUs (Figure 1c), used as a heuristic to tighten the bounds, In our example, assume we use CROWN compute the lower bound la,1 of x3,1- For w E [-1, 1], the ReLUs are unstable with the preactivation range [-1+ + w, + w]. Thus, for E [-1, 0], as -2,11 2 Ug,1, CROWN picks the lower bound 22,1 2 0 so 1,,1 1, and for E (0, 1] the lower bound 22,1 æ1,1 1 This

---

Published in Transactions on Machine Learning Research (10/2022)
creates discontinuity when -12,1 12,1, i..,, at 0. This implics the discontimiity of CROWN-IBP (R) as it uses CROWN for its final bounds.
Discontinuity of hBox. The discontinuities of hBox are caused by hBox switching from simple IBP bounds (Figure 1b), to the tight relation I.,j = 2,-1.- Assume we are deriving 13.2. For w E (-1,1), the ReLUs are unstable, so we use TBP bounds 0 S 22.j S "1,j = 1 + w for j E (1,2), obtaining 13,2 = -1 w, which approaches -2 as w approaches 1. However, for w 2 1, we tighten the bound using 22,j = Z resulting in 4,22 0, thus a discontimuity when 12,11 = 12,2 0, i.c., at w 1.
As our example shows, few neurons are sufficient to produce discontinuúties. Thus, we expect large networks to have a large number of discontinuities, appearing at any ReLU neuron Ti,j, whenever -4-1, = "4 "4-1 (for CROWN) or 4ー11- = 0 (for hBox). Backsubstitution accumulates this effect, creating an unfavorable landscape. As mentioned earlier, we demonstrate this in practice on a realistic network in Section 5.1.
Continuity of Other Relaxations. The remaining two relaxations, IBP and DeepZ, are always continuous, as formalized in the following theorem (full proof in Appendix C.2):
Theorem 2. The output bounds lts of IBP and Deep2 are continuous w.r.t network parameters 0.
Proof Sketch. For IBP, 4 and u, depend only on the previous layer either linearly or via ReLU, both being continuous. For DeepZ, the key step is proving that the ReLU relaxation bounds are continuous in points where the ReLU changes stability. Recall that the unstable case bounds are A and An.- X44-1.j+ where À = uk-15/(4-11 unstable case bounds (in the limit) match the stable case ones; therefore, there is no discontinuity.
4-15)- Then, as li-1,j + 0, X + 1 and Wj-1,j + 0, x + O. For both, the
]
4.3 Sensitivity of Convex Relaxations
Next, we analyze the effect of small weight changes on the output loss by measuring the degree of change in the output when the first layer weights are shifted by 8 in the gradient direction. While changes in other layers also matter, we consider only changes in the first layer to make the computation of the bounds tractable.
To this end, we define a set of rational functions of 8 as Rv(d) = (p(6)//(8) p(5). (6) denotes the polynomials of degree up N. Note that Px(6) S (x))). We say that some neuron æt, is in the set (ō) (or (o)) if that set contains both l,j and Wj.j now treated as functions of 8 where 8 8=0 O corresponds to the concrete l.j and ui, used in Scction 2. Everything else is treated as constant. During backsubstitution for æij, all encountered ær.j' are repeatedly replaced with bound expressions from Equation 2, until we reach Equation 3 to obtain linear expressions for 4, and u.y. If the output neurons of the network are in (6), we say that the sensitivity of a relaxation is N. Sensitivity is an undosirable property, as it introduces a complex loss landscape that hinders optimization, as further explained in Section 4.4. Note that while coefficients of the polynomials also matter, they are influenced by the weights which makes it difficult to compute the worst-case bound in closed form. In the following, we compute the sensitivity of convex relaxations (more detailed derivation is deferred to Appendix J), to show that DeepZ, CROWN and CROWN-IBP (R) are highly sensitive, while IBP and hBox are not, inducing more favorable landscapes. As before, while we focus on l1, the conclusions can be extended to the actual loss. We always consider the worst case w.r.t. all bound choices and ReLU stability, and assume all layers are of size M. While the sensitivity values we obtain represent an upper bound, they clearly demonstrate that some relaxations are highly sensitive, as opposed to IBP and hBox, for which our result on insensitivity exact. This is summarized in Table
E Px(6)), where
Computing the Sensitivity. As the first layer is affine, we have æ1 E P1) for all relaxations. To compute the sensitivity, we sequentially analyze the effect of each layer.
IBP /hex. For IBP, assume that al layer i, all Ii- E Po) For an afline layer, as 4i5 and uij are linear combinations of elements of u:-1 and 4--1, we have Ti E PN (6). For a ReLU layer, as u, = ReLU(u.)1,)) (same for 1,,)) we again have Fi,; E (6) Thus, all ncurons are in (8) S (6) so the sensitivity of IBP is 1. For hBox, the only difference are affine layers, where now Fz, (Wæz,-1) + by.j. As linear combinations of elements of (8) are in Pv (6); all neurons stay in Pi and the sensitivity of h hBx is also 1.
7

---

Published in Transactions on Machine Learning Research (10/2022)
-150
-100
-200
Lower Bound
Lower Bound
-220
-250
-140
-300
-160
3350
IBP
IBP DeepZ
-400
CROWN
-180
-3
-2
-1
0
1
Weight shift (6)
Weight shift (6)
Figure 4: Convex relaxations with discontinuous (left) and highly sensitive (right) losses.
DeepZ/CROWN. The ReLU bounds of DeepZ, Arę-1,5 and Ari-1,J X4-1111 significantly increase the sensitivity. After the first ReLU layer, we have that 22.j E R2(5) À E (8). This changes the behavior of all following affine layers, as a linear combination of M elements of (x( is in (0). Thus, I3.j E (2) For the following ReLU layers, if we assume the inputs are (o), we have that E Rev(6), and thus the outputs are in (8)( Putting this together, each ReLU-affine block from layer 4 onwards multiplies the sensitivity by 3M. As there are [L/2] 1 such blocks, we obtain 2- 3 BBI for the final scnsitivity. CROWN uses the same upper ReLU bounds DeepZ, we can apply the same analysis, and show that the sensitivity of CROWN is 2 3 B++ as well. Thus, both DeepZ and CROWN are highly sensitive.
CROWN-IBP (R). Here, at ReLU layer i during the (only) backsubstitution, we have to consider 4-1,5 and u.-1,j separately from I;-1, While the former were precomputed with IBP, and are thus in (7))), the latter get substituted as usual and can carry larger sensitivity. Assuming Z4-1,5 E (x( (N 2 1) and observing that we always have E (6), follows that Vig E (6). As the affine layers have the same effect as before, each ReLU-affine block now increases sensitivity from N (N + 1)M. As before, 23. E 122(()) so summing the arising geometric series gives the final sensitivity of 2M M -M111MM 11-M which
M M-1
is in O(MB+1). Clearly, CROWN-IBP (R) is also significantly more sensitive than IBP and hBox.
4.4 Continuity and Sensitivity Impact Optimization
We now discuss how discontimuity and high sensitivity negatively affect optimization with gradient descent (GD). We consider a randomly initialized network and optimize first layer weights via GD, trying to mazimize the lower bound of one output neuron, produced using a particular relaxation. For plotting, we restrict the optimization to the direction of the gradient in the initial point d 0 (see Appendix D) for details).
The Impact of Discontinuities. The key issue with discontinuous relaxations is that GD can, at discontinuity, fall off cliff in the landscape to region from which it fails to recover-i.e. where gradients lead it to a suboptimal local maximum. Figure 4 (left) shows a manifestation of this issue. Even though the landscape of CROWN allows for a higher solution than IBP, GD with CROWN converges to a worse value than IBP. Contrary to this, continuous relaxations such as IBP allow GD to easily navigate the landscape. This matches the litcrature stating that optimizing discontinuous functions requires complex algorithms (Conn& & Mongeau, 1998; Martinez, 2002; Wechsung & Barton, 2014).
The Impact of High Sensitivity. Sensitive relaxations introduce complex loss landscape with a larger number of local optima and saddle points, where GD can get stuck. Figure 4 (right) is an example where DeepZ has a highly non-linear landscape that traps GD at a local maximum with a low objective value, not allowing it to progress to better solutions. While DeepZ is tighter for all 8, IBP has the minimum sensitivity and is thus piecewise linear, allowing GD to quickly converge a higher value. Extensive theory (Pardalos & Vavasis, 1991; Jibetean & de Klerk, 2006; Zoej al., 2007) confirms that high-degree polynomial and rational functions, which appear for sensitive relaxations, hard to optimize.
8

---

Published in Transactions on Machine Learning Research (10/2022)
IBP hBox
CROWN-IBP
IBP hBox
CROWN
CROWN-IBP
DeepZ
DeepZ
0.6
Log Sensitivity
Discontinuity
0.4
0.2
0.0
0-
20k
60k
8ök
100k
120k
100
16k
120k
Training Step
Training Step (Log Scale)
Figure 6: Discontinuity (left) and sensitivity (right) during certified training with different relaxations.
5 Experimental Evaluation
In this section we perform an experimental evaluation, further substantiating our hypothesis on the properties of relaxations that explain the paradox of cortified training. First, Section 5.1 we show that discontinuities and high sensitivity appear in practice. Then, in Section 5.2, we provide a deeper insight into the paradox by evaluating certified training and confirming our claims regarding the effect of continuity and sensitivity.
5.1 Continuity and Sensitivity in Practice
First, we measure continuity and sensitivity on a naturally trained network. Namely, we train FC, 5-layer network (see Appendix F.1) on MNIST. Then, we measure the change in the lower bound of one output neuron we shift all first layer weights by 5 in the gradient direction of that ncuron. In Figure 5, we show the resulting bounds depending on 6, on a representative input with = 0.15.
CROWN
CROWN-IBP (R)
DeepZ
Lower Bound
-300
Similar results are observed for different choices of and c. The exporiment confirms our results: hBox, CROWN, and CROWN-IBP (R) indeed suffer from discontinuities, while IBP and DeepZ do not. We observe that CROWN has more discontinuities than other relaxations due to its adaptive lower bound. We further confirm our findings on more networks in Appendix E.
-0.02
0.00
0:04
Weight shift (5)
Figure Continuity and sensitivity on a naturally trained MNIST network.
Additionally, in Figure we measure continuity and sensitivity during certified training for each convex relaxation (complete details of the experiment provided in Appendix E.2). We can observe (left) that hBox is discontimuous at the start of training when more ReLUs are changing stability, and becomes more continuous they stabilize, when CROWN is more discontinuous due to a larger percentage of consistently unstable ReLUs. These observations match our results continuity from Section 4.2. While DeepZ is continuous, can notice (right) that it is highly sensitive already very early in training, which explains its bad performance when used in certified training, contrary to what might be expected given its favorable tightness.
5.2 Evaluation of Certified Training
Next, we perform a thorough evaluation of certified training with all relaxations introduced in Section 2 on 4 widely used datasets (MNIST, FashionMNIST, SVHN, CIFAR-10) and 2 archilectures: FC, a 5-layer dense network, and CONV, a 3-layer convolutional network. For CIFAR-10 we use the larger 4-layer CONV+, here nccessary to obtain nontrivial accuracies after certified training. Note that further incrcasing network size only marginally boosts the results (Zhang al., 2020), but prevents training with time and memory intensive CROWN, which can already not be trained CONV+. We focus well-established and challenging cases
9

---

Published in Transactions on Machine Learning Research (10/2022)
Table Certified robustness (in %) after certified training with convex relaxations. Symbol x indicates that property unfavorable, i... the relaxation has discontimuous loss landscape or highly sensitive. We use Eteat 0.3 for MNIST and FashionMNISST, and Etest 8/255 for SVHN and CIFAR-10 datasets.
MNIST
MashionMNIST
SVHN
CIFAR-10
Method
Continuity
Sensitivity
FC
CONV
FC
CONV
CONV
CONV+
IBP
74.0
86.8
40.4
52.0
28.9
29.0
hBox
X
57.0
83.7
39.6
47.1
23.6
20.0
CROWN
57.3
70.2
30.2
31.5
23.4
0OM
DeepZ
X
64.2
69.8
35.0
34.0
24.5
22.8
CROWN-IBP (R)
70.5
75.4
41.1
40.0
27.5
24.3
Table 3: Certified training of two MNIST networks with modifications of relaxations aimed at improving unfavorable properties. The first shows the favorability of tightness (T), continuity (C) and sensitivity (S) for each relaxation. The following rows show certified robustness (in %).
CROWN-- Na-TT
CROWN TrineC
CROW N-IBP (8)
CROW NROW N-Sutt 101
Mitees Drgs
DeeyZ-Bar Baz
DepiZ-Dias Dan
Drepi DrepE-Digge
Daap Switel
DeepZ-Sott
RepdABB (R)
CROWN
CROVN-O
CROWN-O-TE NOO
GROWN-]
CROW
CROW Tai
CROW Sult
Thspit
100
T/C/8
rC
74.0
57.0
10.4
9.9
38.7
84.2
45.4
30.4
17.7
40.8
00.0
72.1
57.3
44.6
72.4
18.3
17.6
28.0
18.4
18.2
17.8
65.5
70.5
72.0
146
18.5
75.4
of strong adversaries (Madry et al., 2018; Croce et al., 2020), i.e., Ctest = 0.3 for MNIST FaSS and feeet = 8/255 for SVHN /CHN//0 We use the same relaxation for training and certification, as this is usually optimal (see Appendix F.3). Further experimental details are provided in Appendix F.1.
Reproducing the Paradox. Our main results are shown in Table 2. Whereas prior work provides certain evidence, our comprehensive experiments over 5 relaxations, datasets and several networks, confirm that the well-known paradox of certified training generally holds: tighter relazations obtain worse results, and no tight relaxation can consistently outperform the loose IBP. Note that aim to understand the behavior of certified training with a single relaxation. As previously noted, the paradox can in some cases be circumvented with advanced training schemes, e.g., the hybrid CROWN-IBP defense can often outperform IBP by combining CROWN-IBP(R) and IBP relaxations in training (sce Appendix F.4 for expanded results).
Understanding the Paradox. We use to highlight cases when one of our two key properties, continuity and sensitivity, is unfavorable for training (discontinuous loss, high sensitivity), and when is favorable. Considering tightness as sole property of relaxation led to seemingly contradictory conclusion. Once we complement. tightness with our two properties, the results are less puzzling, as we can explain the inferior performance of each method compared to IBP. As discontinuity and sensitivity manifest for realistic networks (Section 5.1), and can have negative effect on gradient descent (Section 4.4), we can now expect that discontinoous and sensitive relaxations will not produce satisfactory results. This confirmed in Table
Namely, we can attribute the poor results of hBox and CROWN-IBP (R) the discontinuitics in their loss which harm gradient descent. While Deepž continuous, is highly sensitive which again poses a difficulty for optimization and hurts the results. Notably, CROWN suffers from both issues, thus failing despite its tightness. We see that IBP, while loose, has favorable continuity and scnsitivity, and achieves the best results. This provides novel insights on the paradox relarations with unfavoruble properties get worse results.
Excluding Alternative Explanations. Exactly quantifying the impact of each property (tightness, continuity, and scnsitivity) on the result is challenging, it might heavily depend on the setting, e.g., datasct. or network (see discussion in Section 6). However, exclude the possibility that our conclusions are an artifact of specific setting (e.g., they hold only for a particular weight initialization), repeat subset of
10

---

Published in Transactions on Machine Learning Research (10/2022)
Table 4: Mean and standard deviation (4 random seeds) of certified robustness after certified training of the CONV network on MNIST dataset (as in Table 2) using loose paramctrized relaxations described in Section 6, illustrating that the tradeoff between properties, namely contimuity and tightness, can change across settings.
Looseness Parameter w
0.01
0.5
1.5
2
LooseIBP-C
85.4 + 0.5
82.0 + 0.6
80.0 - 0.6
77.3
+ 0.6
73.4 +
2.0
45.4 + 12.2
13.4 + 0.9
LooscIBP-DCS
85.8 + 0.6
83.1 + 0.4
81.8 + 0.4
79.6 + 0.4
78.3 + 0.8
73.8 1 0.6
21.1 + 19.1
LooscIBP-DC1p
85.8 + 0.3
82.5 + 0.7
80.8 + 0.5
77.6 + 1.3
75.6 + 1.3
32.7 + 22.1
11.3 + 0.0
Loos:1BP-DD1or
86.1 + 0.5
82.0 + 0.5
79.9 + 0.5
76.7 + 1.0
68.0 + 2.5
20.1 + 15.2
11.3 + 0.0
Loos:IBP-DCaor
86.2 + 0.4
82.3 = 0.2
79.0 + 0.2
1.2
24.9 + 13.8
11.3 + 0.0
11.3 + 0.0
LooseIBP-DChoo
86.1 + 0.3
81.9 = 0.3
57.0 + 12.9
11.3
# 0.0
11.3 +
0.0
11.3
+ 0.0
11.3 = 0.0
our experiments for a wider range of parameter choices, including various initializations, regularization norms, learning rates, optimizers, as well as training on subsets of the data. In all considered settings we reach the same conclusions as in Table 2, further strengthening our insights. The detailed results are in Appendix G.
6 Improving Unfavorable Properties of Relaxations
Given our previous results that demonstrate the negative effect of unfavorable properties on certified training, a natural follow-up question is: can we simply improve the unfavorable properties of a relazation to make if more successful in certified training? To investigate this question we systenatically explore and evaluate modifications of previously considered relaxations, and demonstrate that this does not immediately lead to better results, as such changes often harm other properties, inducing complex tradeoff.
Discovering Modifications. To obtain the modifications, generate all combinations of suitable choices for lower and upper linear bounds (as in Equation 2) for all three ReLU stability cases, filtering out unsound candidates (i.e., those that do not properly overapproximate ReLUU,, and those for which there is a strietly more favorable relaxation (i.e., provably strictly tighter and not worse in continuity and sensitivity). Additionally, we include several relaxations obtained via (i) discretely switching between bound choices for unstable ReLU based on CROWN-inspired heuristic; (ii) changing the same bounds in a soft way, eliminating the discontinuity introduced by the switching heuristic, and (fi) computing the intermediate bounds using IBP to reduce sensitivity, as in CROWN-IBP (R).
Properties are Entangled. The resulting relaxations are shown in Table 3. We interpret each relaxation as a modification of one of the relaxations from Table 2 aimed at improving one property, and name them accordingly. We show the lavorability of each property, and certified robustness after certified training of FC and CONV networks. Our claims on tightness of these modifications are based on empírical CR-AUC measurements in the same setting as in Figure? (see Appendix H for details). We defer complete descriptions of each modification, including the intended as well unintended effects properties, to Appendix H.
The main observation from Table 3 is that properties are not aadependent-modijeee property often negatively affects another one. For example, by fixing the lower bound Ii-1,j S Ti,j for unstable ReLUs in CROWN mm to eliminate the discontinuitiss due to heuristic switching, we obtain CROWN-1 mm which introduces a new kind of discontinuities at 41-1, = 0 and is slightly looser. Further, using 1;-1, S 2i for the negative case creates CROWN-1-C mm, which is now continuous, but significantly looser. Both of these relaxations perform worse than CROWN, while some similar changes result in improvements, implying complex tradeoff between properties, where they differently affect the certified training in different scenarios, as previously observed in Section 5.2.
a relazation to improve
Crucially, no modification is able to outperform IBP, strengthening the conclusion that modifying existing relaxations to improve unfavorable properties is not simple and does not directly lead to state-of-the-a results. Note that the same phenomenon affects most prior work in designing convex relaxations, where tightness was the sole focus in relaxation design, which unknowingly harmed other two properties and caused bad results in certified training, leading to the paradox which focus in this work.
11

---

Published in Transactions on Machine Learning Research (10/2022)
Towards Understanding the Tradcoff. To further demonstrate that properties can affect training in different ways for different settings, as opposed to previously explored discrele modifications, we consider two perumetrized modifications of IBP continuous LooseIBP-C(w)) which before every ReLU layer replaces the interval arithmetic bounds [2, u] with [t - w. u + w]. and discontinuous LooseIBP-DG. (w), which uses [ [ + [] - F 1), u + w(F * u - [F * []]], and is further parametrized by F; where larger leads to more discontinuities. Increasing the looseness parameter w reduces the tightness of all relaxations. For fixed w, all LooseIBP-DCr(w)) have intuitively comparable tightness, and are all strictly tighter than LooselBP-C(w))
In Table 4 we present the certified training results for various values of w and F, with the CONV network trained on the MNIST dataset, following the sctting of Table 2. We perform 4 runs with different random seeds, and report the mean and the standard deviation. As all considered relaxations are strictly looser than IBP for any fixed w, we do not expect improvements over IBP (which achieves 86.8% CR in this case, see Table 2). However, is interesting to determine when sacrificing the continuity of LooseIBP- P(ww)) for tightness of LooseIBP-DDe DDp (w) is beneficial (we highlight such cases for cach in bold). Namely, we can see that in light regimes (low w), the advantage of lightness on average outweighs the harm of discontinuities, and we get comparable or slightly more favorable results for most F. As move to looser regimes (high w)), the differences between relaxations become more pronounced, and discontinuities become more important relative to tightness, i.e., increasing tightness improves results only if the cost paid in discontinuities is not too large. Even taking into account the standard deviation of results for small 4; where some of the relaxations are comparable, our conclusion still stands. Note that for high w, relaxations sometimes fully diverge in training. dropping CR to trivial 11.3%, which explains cells with unusually high standard deviation.
This illustrates that while the three properties of relaxation are indicative of its performance, the underlying tradeoff can vary, and estimating the exact effects of each property in a particular setting is challenging.
7 Conclusions, Discussion and Future Work
Our theoretical (Section 4) and experimental (Section 5) results demonstrated that attempts to use tighter relaxations in certified training have lead to unfavorable properties such as discontinuity and high sensitivity of the loss. These novel insights on the failure of these relaxations to outperform the loose IBP represent a first step towards deeper understanding of this phenomenon. As the difference between the best empirical and certified robustness is more than 25% based on current leaderboards (Li et al., 2020; Croce et al., 2020) CIFAR-10, we now provide a brief outlook, in light of new evidence, on possible techniques that could help close this gap, and identify several high-level directions that could be explored in future work.
New Relaxations with Favorable Properties. First, one could try to design a novel relaxation that is tight, and has both favorable contimuity and favorable sensitivity. The results of our follow-up study in Section 6 indicate that this might be difficult, as trying to improve a property of an existing relaxation often negatively affects other properties, inducing a tradeoff with complex effects on training. Nevertheless, a relaxation with all favorable properties could still exist, as for instance Lyu et al. (2021) have obtained competitive results by using new relaxation, and such search could be further guided by our findings.
New Training Methods for Existing Relaxations. Second, one could attempt to utilize existing convex relaxations in certified training with a modified training procedure, which is designed to exploit the benefits of each relaxation. Examples of this in recent work include searching for counterexamples (Balunovic & Vechev, 2020), combining several relaxations (Zhang et al., 2020) or using better initialization (Shi et al., 2021), and have shown to be a promising way to obtain statc-of-tho-art certified robustness. Future work could attompt to explicitly incorporate the notions of continuity and sensitivity when designing such a training procedure.
Going Beyond Convex Relaxations. Finally, under the assumption that the tradeoff between tightness and other properties represents a fundamental obstacle for convex relaxations, a promising possibility could be to move away from training with convex relaxations altoget and adopt a fundamentally different approach. Recently, alternative methods based on the technique of randomized smoothing (Cohen et al., 2019; Salman et al., 2019a; Yang et al., 2020) or new -rriiication-friendlly model architectures (Zhang et al., 2021; 2022) have achieved strong results, which may suggest that this avenue the most promising. However, these methods come with their own set of challenges and tradeoffs, previously discussed in Section 2.
12

---

Published in Transactions on Machine Learning Research (10/2022)
References
Maximilian Baader, Matthew Mirman, and Martin T. Vechev, Universal approximation with certified networks. In International Conference on Learning Representations, 2020.
Mislav Balunovic and Martin Vochev. Adversarial training and provable defenses: Bridging the gap. In International Conference on Learning Reyresentalions, 2020.
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. In Proceedings of the 36th International Conference on Machine Learning, 2019.
Andrew R Conn and Marcel Mongeau. Discontinuous piecewise linear optimization. Mathemalical programeming, (0(3)33153880 1998.
Francesco Croce, Maksym Andriushchenko, Vikash Sehwag, Edoardo Debenedetti, Nicolas Flammarion, Mung Chiang, Prateek Mittal, and Matthias Hein. Robustbench: standardized adversarial robustness benchmark. arXiv preprint Xtv:2000 09670, 2020.
Sumanth Dathathri, Krishnamurthy Dvijotham, Alexey Kurakin, Aditi Raghunathan, Jonathan Uesato, Rudy Bunel, Shreya Shankar, Jacob Steinhardt, Ian J. Goodfellow, Percy Liang, and Pushmeet Kohli. Enabling certification of verification-agnoste networks via memory- semidefinite programming. In NewrIPS, 2020.
Rüdiger Ehlers. Formal verification of pieco-wise linear feed-forward neural networks. In International Symposium on Automated Technology for Verification and Analysis, 2017.
Timon Gehr, Matthew Mirman, Dana Drachsler-Cohen, Petar Tsankov, Swarat Chaudhuri, and Martin Vechev. Ai2: Safety and robustness certification of neural networks with abstract interpretation. In 2018 IEFE Symposium on Security and Privacy (SBP), 2018.
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Yee Whye Teh and D. Mike Titterington (eds.), AISTATS, 2010.
lan Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In International Conference on Learning Representations, 2015.
Sven Gowal, Krishnamurthy Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Uesato, Timothy Mann, and Pushmeet Kohli. On the effectiveness of interval bound propagation for training verifiably robust models. arXie preprint 1xXi:18100.1215, 2018.
Sven Gowal, Krishnamurthy Dvijotham, Robert Stanforth, Timothy Mann, and Pushmeet Kohli. A dual approach to verify and train deep networks. In Proceedings of the Conference on Artificial Intelligence, IJCAI-19, 2019.
International Joint
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification.
Dorina Jibetean and Etienne de Klork. Global optimization of rational functions: a semidefinite programming approach. Mathemalical Progrumsming, 106(1):93 109, 2006.
Guy Katz, Clark Barrett, David L Dill, Kyle Julian, and Mykel J Kochenderfer. Reluplex: An efficient smt solver for verifying deep neural networks. In International Conference on Computer Aided Verification, 2017.
Sungyoon Lee, Woojin Lee, Jinseong Park, and Jaewook Lee. Towards better understanding of training certifiably robust models against adversarial examples. In Advances in Neural Information Processing Systems, 2021.
Linyi Li, Xiangyu Qi, Tao Xie, and Bo Li. Sok: Certified robustness for deep neural networks. orXiv preprint arXiv:2009.04139 2020.
13

---

Published in Transactions on Machine Learning Research (10/2022)
Zhaoyang Lyu, Minghao Guo, Tong Wu, Guodong Xu, Kehuan Zhang, and Dahua Lin. Towards evaluating and training verifiably robust neural networks. In CVPR, 2021.
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.
José Mario Martíncz. Minimization of discontimnous cost functions by smoothing. Acta Applicandae Muthemalica, 71(:)2245 260, 2002.
Matthew Mirman, Timon Gehr, and Martin Vechev. Differentiable abstract interpretation for provably robust neural networks. In Proceedings of the 35th International Conference on Machine Learning, 2018.
Mark Niklas Müller, Gleb Makarchuk, Gagandeep Singh, Markus Püschel, and Martin Vechev. Prima: Precise and general neural network certification via multi-neuron convex relaxations, 2021.
Panos M Pardalos and Stephen A Vavasis. Quadratic programming with one negative eigenvalue is np-hard. Journal of Global optimization, 1(1):15-22, 1991.
Aditi Raghumathan, Jacob Steinhardt, and Perey Liang- Certified defenses against adversarial examples. In International Conference on Learning Representations, 2018a.
Aditi Raghunathan, Jacob Steinhardt, and Percy Liang. Semidefinite relaxations for certifying robustness to adversarial examples. In Advances in Neural Informalion Processing Systems 31. 2018b.
Hadi Salman, Greg Yang, Jerry Li, Pengchuan Zhang, Huan Zhang, Ilya Razenshteyn, and Sebastien Bubeck. Provably robust deep learning via adversarially trained smoothed classifiers. Advonces in Neural Information Processing Systems 32, 2019a.
Hadi Salman, Greg Yang, Huan Zhang, Cho-Jui Hsich, and Pengchuan Zhang. A convex relaxation barrier to tight robustness verification of neural networks. In Advances in Neural Information Processing Systems 32. 2019b.
Andrew M. Saxe, James L. McClelland, and Surya Ganguli. Exact solutions to the nonlinear dynamics of learning in deep linear neural networks. In Yoshua Bengio and Yann LeCun (eds.), ICLR, 2014.
François Serre, Christoph Müller, Gagandeep Singh, Markus Püschel, and Martin Vechev. Scaling polyhedral neural network verification on GPUs. In Proc. Machine Learning and Systems (MLSys), 2021.
Zhouxing Shi, Yihan Wang, Huan Zhang, Jinfeng Yi, and Cho-Jui Hsich. Fast certified robust training with short warmup. In Advances in Neural Information Processing Systems, 2021.
Gagandeep Singh, Timon Gehr, Matthew Mirman, Markus Püschel, and Martin Vechev. Fast and effective robustness certification. In Advances in Neural Information Processing Systems 31, 2018.
Gagandeep Singh, Rupanshu Ganvir, Markus Püschel, and Martin Vechev. Beyond the single neuron convex barrier for neural network certification. In Advances in Neural Information Processing Systems 32, 2019a.
Gagandeep Singh, Timon Gehr, Markus Püschel, and Martin Vechev. An abstract domain for certifying neural networks. Proceedings of the ACM Programming Languages, 2019b.
Christian Szegedy, Wojciech Zaremba, Tlya Sutskever, Joan Bruna, Dumitru Erhan, Tan Goodfellow, and Rob Fergus. Intriguing properties of neural networks. arXiv preprint arXiv:1312, 6199,, 2013.
Christian Tjandraatmadja, Ross Anderson, Joey Huchette, Will Ma, Krunal Patel, and Juan Pablo Vielma. The convex relaxation barrier, revisited: Tightened single-ncuron relaxations for neural network verification. In Advances in Neural Information Processing Systems 33, 2020.
Vincent Tjeng, Kai Y. Xiao, and Russ Todrake. Evaluating robustness of neural networks with mixed integer programming. In International Conference Learning Representations, 2019.
14

---

Published in Transactions on Machine Learning Research (10/2022)
Shiqi Wang, Kexin Pei, Justin Whitchouse, Junfeng Yang, and Suman Jana. Formal security analysis of neural networks using symbolic intervals. In USENIX Security Symposium, pp. 1599-1614. USENIX Association, 2018a.
Shiqi Wang, Kexin Pei, Justin Whitehouse, Junfeng Yang, and Suman Jana. Efficient formal safety analysis of neural networks. In Advances in Neural Information Processing Systems 31. 2018b.
Shiqi Wang, Huan Zhang, Kaidi Xu, Xue Lin, Suman Jana, Cho-Jui Hsieh, and J. Zico Kolter. Brta-crown: Efficient bound propagation with per-neuron split constraints for complete and incomplete neural network 2021a.
verification. CoRR,
Shiqi Wang, Huan Zhang, Kaidi Xu, Xue Lin, Suman Jana, Cho-Jui Hsieh, and J. Zico Kolter. Bela-crown: Efficient bound propagation with per-neuron split constraints for complete and incomplete neural network verification. 2021b.
Achim Wechsung and Paul I Barton. Global optimization of bounded factorable functions with discontinuities. Journal of Global Oplimization, 58(1):1 30, 2014.
Lily Weng, Huan Zhang, Hongge Chen, Zhao Song, Cho-Jui Hsich, Luca Daniel, Duane Boning, and Inderjit Dhillon. Towards fast computation of certified robustness for ReLU networks. In Proceedings of the 35th International Conference on Machine Learning, 2018.
Eric Wong and Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In Proceedings of the 35th International Conference Machine Learning, 2018.
Eric Wong, Frank Schmidt, Jan Hendrik Metzen, and J. Zico Kolter. Scaling provable adversarial defenses. In Advances in Neural Information Processing Systems 31. 2018
Kaidi Xu, Zhouxing Shi, Huan Zhang, Yihan Wang, Kai-Wei Chang, Minlie Huang, Bhavya Kailkhura, Xue Lin, and Cho-Jui Hsieh. Automatic perturbation analysis for scalable certified robustness and beyond. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Aaoiina Balcan, and Hsuan-The Tien Lin (eds.), NeurIPS, 2020.
Greg Yang, Tony Duan, J. Edward Hu, Hadi Salman, Tlya P. Razenshteyn, and Jerry Li. Randomized smoothing of all shapes and sizes, In 1CML, 2020.
Bohang Zhang, Tianle Cai, Zhou Lu, Di He, and Liwei Wang. Towards certifying l-infinity robustness using neural networks with l-inf-dist neurons. In Marina Mcila and Tong Zhang (cds.), ICML, 2021.
Bohang Zhang, Du Jiang, Di He, and Liwei Wang. Boosting the certified robustness of l-infinity distance nets. ICLR, 2022.
Huan Zhang, Teui-Wei Weng, Pin-Yu Chen, Cho-Jui Hsich, and Luca Danicl. Efficient neural network robustness certification with general activation functions. In Advances in Neural Information Processing Systems 31, 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, 2020.
MJ Valadan Zoej, Mchdi Mokhtarzade, Ali Mansourian, Hamid Ebadi, and S Sadeghian. Rational function optimization using genetic algorithnus. International journal of applied earth observation and geoinformation, 944):403444 413, 2007.
15

---

Published in Transactions on Machine Learning Research (10/2022)
ReLU((1,))
F0.1
F1,1
22,1
23,1
102
112
#2,2
33,2
ReLU(2122)
Figure 7: Toy network (from Singh al. (2019b)).
A Backsubstitution Example
Here illustrate the process of backsubstitution concretely on the loy network shown in Figure 7, using DeepZ. The same example but with the CROWN/DeepPoly relaxation is shown in (Singh et al., 2019b).
The components of the input zo. namely z0,1 and 20,2; have bounds -1 and 1, meaning that - S 20,1, C0.2 I 1.
Because the first layer h an affine layer we have
11,1 = 10,1 + T0.2:
(4)
1,, To,1 - I0.2-
(5)
To obtain the bound 411 we replace both 20,1 and z022 with lo.1 - and lo,2 -1 as their signs are both
positive in Equation 4 and obtain h,, 22 To obtain 41, replace F0,1 with t,1 =1 and 20,2 with N0,1 = 1 in Equation 5 as the sign of 2a, is negative and get 1, = 2. Similarly get u1,1 = 2 and u1,2 = 2.
The second layer h2 is a ReLU layer. As both ReLUs are unstable, we need to calculate À for each of them. As the bounds are equal, 411 = 4,2 = - and u1,1 = U122 = 2, we get that X is also equal, X = 2. Using the formula for unstable ReLUs we get
1 S x2,1 2 -1, + 1,
2 1 & 82, S 11.2 + 1.
Now backsubstituting the bounds for 20,1 and 20,2 gives
2 (no,1 + x0,2) S x2, S (To,1 + xb,2) 1, $ ( To,2) S x2 _ (Jo.1 Tp,2) + 1.
1
The lower and upper bounds 12,1, 42,1 and l2,2; u22 for 22 and 22,2 respectively follow immediately:
12 2 1 (lo,1 + lo,2) = =- = =12,11
22 S 2 {"o. + u0,2) =1 U2,1
F22 {(o,1 u0,2) = =-1= =12,21
222 ( lo,2) =1 =
The third layer hy is again affine layer, hence get F3,1 22,1 22,2 and 23,2 I2,1 22,2- In the backsubstitution step, replace 22,1 and 22,2 with their upper and lower bounds and arrive at
Fo.1 < F3,1 - F0.1 + +2,
0022 1 < 23. S Øo.2 + 1.
Again, the lower and upper bounds 13,1, 43,1 and la,2, U3.2 for K3,1 and Da,2 respectively follow:
T3,1 2 lo,1
= =-1 =13,11
T3.1 S N0,1 + 2 = 13,1
43.2 2 4,2
-2 1,21
33,2 102 +1
2 03.2.
16

---

Published in Transactions on Machine Learning Research (10/2022)
Table 5: The summary our tightness experiments. Acc denotes standard accuracy (in %). ER denotes empirical robustness (in %), evaluated using PGD with the same e used training.
Dataset
Network
Training
Acc
ER
A
MNIST
CONV
Natural
98.7
B
MNIST
CONV
PGD 0.1
99.0
94.4
C
MNIST
CONV
PGD = 0.3
98.2
91.0
PashionMNIST
CONV
Natural
91.4
F.
CIFAR-10
CONV+
Natural
70.0
MNIST
FC-S
Natural
98.2
G
MNIST
FC-S
PGD c 0.1
99.0
91.8
MNIST
FC-S
PGD 0.3
92.3
78.3
Table 6: The results of tightness experiments, showing CR-AUC each method.
Method
A
B
D
E
F
H
IBP
0.73
0.91
1.94
0.20
0.02
0.47
0.63
2.22
bBox
1.76
4.76
10.45
0.33
0.09
1.42
2.70
11.44
CROWN
3.36
9.77
22.75
1.19
0.28
2.86
6.74
22.63
Deep%
3.00
9.21
20.97
1.11
0.25
2.63
6.21
21.57
CROWN-IBP (R)
2.15
4.20
8.85
0.70
0.04
1.50
2.73
13.55
B Additional Results Tightness
Here we present results related to tightness, namely our experiments measuring empirical lightness of relaxations, and two proofs omitted from the main paper.
B.1 Quantifying the Tightness of Relaxations
We present the complete results of our tightness experiments, one of which (experiment A) was shown in Table and further in Figure 2.
Setup. We conduct 8 experiments (labeled A-H), varying the dataset (MNIST, FashionMNISST, CIFAR-10), the network (CONV and CONV+, described Appendix F.1, and FC-S, 100-100-10 fully-connected network), and the training method (natural training, adversarial training with PGD with 0.1, and adversarial training with PGD with 0.3). For PGD, use 100 steps with step size 0.01. We train all models for 200 epochs. For PGD with = 0.3, as necessary for convergence, we use the first 10 epochs warm-up (natural training), and the following 50 as ramp-up, where we slowly increase the perturbation radius from 0 to e. We use L2 regularization with strength 5e-3 for experiment E, and 5e-5 for other experiments. The experiments are summarized in Table
After training the networks, we sample 100 values from 0 to 0.07 for natural, 0.15 for PGD c 0.1, and to 0.4 for PGD 0.3 models. For every radius e, we each relaxation attemtt to certify the examples from the test set. We calculate the certified robustness of each network under all relaxations, and plot the resulting CR curves. The CR curves shown in Figure 2 correspond to the results of experiment A. Further, we quantify the tightness of each relaxation as CR-AUC, the area under the CR curve, calculated using the trapezoidal rule. Table contains CR-AUC values of curves from Figure 2 (experiment. A), and certified robustness after certified training of the same network with Etrain 0.3 (part of results in Section 5.2).
Discussion. As the curves are similar among experiments, we summarize the results (CR-AUC) in Table From these results, confirm two claims given in the main paper:
17

---

Published in Transactions on Machine Learning Research (10/2022)
It is necessory to certified training to obtain certifiably robust network. We see that adversarial training, along with improving empirical robust also has positive effect certified robustness. However, these results are significantly worse from those that can be obtained using certified training. To illustrate this point, for experiment C (MNIST, CONV, PGD with = 0.3), the method that certifics the most at 0.3 CROWN, with 11.9% certified robustness (not. visible from the results shown here). Using certified training in the same setting, all relaxations obtain significantly better results: from 69.8% (worst method) 86.8% (best method), as seen in Table 2.
The relative tightness of relazations is well established and can be empírically confirmed. While individual CR-AUC values may vary between settings, the conclusions are consistent across all experiments.
It is worth noting that while we cover all commonly used convex relaxations, extending the lightness discussion methods that do not necessarily fit the framework presented in Section 2
to more complex relaxation-bas can be challenging. As an example, recently introduced 3-CROWN (Wang et al., 2021b) can in practice outperform the provably tighter Triangle (Ehlers, 2017) relaxation in certification of naturally trained networks, which may seem contradictory. However, this holds in a setup in which the former optimizes the slopes for all bounds including the intermediate layer ones, while the latter uses fixed intermediate layer bounds. For the same set of fixed intermediate bounds, as we would expect, 3-CROWN can not produce better final bounds than Triangle (as stated in Corollary 3.2.1. in (Wang et al., 2021b) and previously in (Salman et al., 2019b).
B.2 hBox is Strictly Tighter Than IBP
Here we sketch proof that for any neural network parameters hBox certifies more than IBP. For a formal proof see Wang et al. (2018a) or Mirman et al. (2018).
Theorem (Informal). Given a neural network architecture parametrized by 0 Rd, for any choice of 0, hBor can certify robust classification for more imputs than IBP.
Proof. To prove the statement, it is sufficient to show that the constraints introduced for each layer for hBox are tighter than IBP constraints (see Equation 3 in (Wang et al., 2018a) for more details on this claim). This is relatively straightforward for affine layers, so here we focus on ReLU layers. For unstable ReLU both use the samee constraints: 0 < Tijj S Uz-1,f" When U4-1, 0, both set Vi, = 0. The only difference is when 4-1.j > 0: in this case IBP uses 4--1,j S Fig S u4-1,j while hBox sets Jaj Mi- By definition have 4-1. S 24-15 u411j implying that hBox constraints are indeed tighter.
B.3 Strictly Tighter Relaxations have Better Certified Robustness Optima
Here restate and prove Theorem
Theorem 1. Let and r2 be two conver relazations, where is known to be striclly lighter than r2. For network parametrized by 0 and any c 2 0, it holds that maxo CR(O,
c, r,r1) maxe CR(),,,rr).
Proof. Let 0, arg max, CR(0, and analogously 02 arg max c2)) We can observe that:
max CR((O, = C2(
CR((,,,,
< &,
Here, the first incquality follows from the fact that rı is strictly tighter relaxation than r' for any parameter choice. The second incquality follows from the definition of 0g maximum, completing the proof. E
18

---

Published in Transactions on Machine Learning Research (10/2022)
+
+1
ReLU((111)
1
21.1
22,1
23.1
[-1,]]
_0,1
21,2
22,2
33,2
ReL.U(112))
1
+
Figure 8: The network used in Section 4.2 to show that the discontimuity of CROWN and hBox manifest already for small networks.
C Omitted Details on Continuity
C.1 Network Used to Show Discontinuities
The sketch of the network described Section 4.2, used to show discontinuities of hBox and CROWN relaxations is given in Figure 8.
C.2 Proof for Continuity of IBP and DeepZ
We expand on the proof sketch given in the main paper to provide a complete proof of Theorem 2.
Proof. IBP: Recall that for IBP, L and u, are computed directly as a function of 4,11, u;-1: and 0. For affine layers, this function is a sum of products of clements in 4,-1, u-1 and 0, which is continuous w.r.t. variables. If i is a ReLU layer, the lower (upper) bound function ReLU((-11.)) (resp. ReLU(u--IJ)) which is also clearly continuous. As compositions, sums, and products of continuous functions are continuous functions, this directly shows that L.j are ultimately continuous.
For DeepZ, computing each 4; and includes backsubstitution, where to obtain the final expressions (as in Equation 3), we repeatedly substitute in power/upper bound expressions, based on the values of 0 and bo and uy from all previous layers. As before, it suffices to show that for some i, lq and are continuous w.r.t. and all previous by and uys
DeepZ:
First, recall that during each step of backsubstitution we encounter terms of the form a ae. and based on the sign of substitute the lower or the upper bound expression for zy When one such = 0, a zy is continuous (both the left and the right limit equal the function value at that point, 0). Thus, these cases to cases where no values encountered are zero, i.e., all choices for the upper/lower bound to be substituted during backsubstitution are fized.
reduce
Next, recall that even we fix this choice, the actual expression we substitute in for the upper or lower bound may depend on the ReLU stability case. If all lp and uy are nonzero the stability is fixed, and by substituting affine and ReLU relaxation bounds during backsubstitution we can arrive at a closed form expression w.r.t. O that uses only elementary operations, which is continuous.
It is left to discuss the behavior in points where some elements of some 4y or uy are zero. In this case the ReLU is still stable, but switches to being unstable one side of zero. If L = 0 both upper and lower bound expressions for Ir41, are Tz.j, which is also the right limit. In the left limit, we use the unstable ReLU bounds λ and \ Xlp and see that for 4r_ + 0, + 1, and thus these bounds approach zy as well, so there no discontinuity. Similarly, for uy, = (the other stable case) the bounds (as well the left limit) are O. For the right limit, we again have the unstable case, but now 0, so both bounds approach 0, implying that this is also not a discontinuity.
19

---

Published in Transactions on Machine Learning Research (10/2022)
CAOAN
Dee22
CADON
CROWN
CHOWN
Lower Bound
Lower Bound
-20-
-100
-40
-0.20
-0'15
-0.30
-0.05
0.00
0.05
0.50
-0.20
-6'15
-6.10
0.00
0.05
c.
0.15
Weight shift
Weight shift
(a) IBP trained
(b) HBox trained
CAOWN
Dees2
CADWN
CROWN
CROWN
Lower Bound
Lower Bound
-100
-50
-100
-300-
-150
-0.00
-0.15
-0.10
-0.05
0.08
0.05
0.10
-0.70
-0.15
-0.18
0.00 0.05
6.10
0.70
Weight shift (6)
Weight shift (6)
(c) CROWN trained
(d) Deep7 trained
cRiwn
Desppe
CROWN
CRIOWN
Desp?
CROWN-4
Lower Bound
Lower Bound
-50
-100-
-0.15
-0.10
-0.05
0.5s 0.10
0.s
-0.15
-0.05
0.50
ois
0.20
Weight shift (5)
Weight shift (5)
(e) CROWN-IBP (R) trained
(f) CROWN-IBP trained
Figure Lower bounds of convex relaxations for FC networks from Table with Etest 0.3, and a network trained with CROWN-IBP, showing continuily and sensitivity of each relaxation. Each subfigure shows the name of the relaxation used to train the corresponding network.
To conclude, we showed that 4 and u, are continuous w.r.t. and all previous by and up. This can be composed to conclude that I. is continuous w.r.t. 0, using the same argument we used for IBP.
D Details of Gradient Descent Experiments
In this section provide details of the experiments with used to generate Figure 4, discussed in Section 4.4. For both examples consider architecture consisting of 2 hidden layers with 10 neurons each, and 2 output neurons. The network reccives 1-dimensional input. We randomly sample the input, weights, and biases as integers in [-4, 4], and sample the perturbation radius e between 0.1 and 4.1. For the experiment with the discontinuous CROWN relaxation, we set the initial learning rate to 0.02, learning rate decay to 0.99, and ran for 20 epochs. For the experiment with the sensitive DeepZ relaxation, we set the initial lcarning rate to 0.005, learning rate decay to 0.99, and ran for 100 epochs. We sampled number of different networks for both scenarios, and chose the one which best illustrates the behavior of gradient descent.
20

---

Published in Transactions on Machine Learning Research (10/2022)
E
Continuity and Sensitivity in Practice
We present more results and discuss the details of experiments presented in Figure 5 and Figure 6.
E.1
Additional Figures
Here we show additional figures for continuity and scnsitivity with same sctup as for Figure 5. In Figure 9 we show the bounds for each of the MNIST FC networks from Table 2, using étest = 0.3, and net trained with CROWN-IBP in the same setup. All plots are generated on the same example. We can highlight some differences compared to the naturally trained network. First, as explained earlier, the relaxation used for training typically obtains the tightest bounds. .Nxxt, we can see that if the network was trained with CROWN or hBox, there is a significantly smaller number of discontimuities than the cases when the network was trained naturally or using some other relaxation. Even though there is a lack of discontinuities in these cases, these networks do not perform well (see Table 2) which suggests that, while the network learned to eliminate the discontinuities, the performance was still hurt by them earlier in the training. Finally, we see that evaluating IBP and hBox trained models using the DeepZ relaxation shows its increased sensitivity.
E.2 Measuring Continuity and Sensitivity in Training
We provide details on the experiment discussed in Section 5.1 where we measure continuity and sensitivity of relaxations during certified training. For this experiment, we use the FC network and train on MNIST, using the same hyperparameters used to produce our main results. We measure sensitivity at every training step for the first epochs, and once per epoch afterwards. Continuity is measured every 50 steps. Next, we describe the exact methods used to compute the two quantities shown in Figure 6.
To measure continuity, we compute the gradient VeL w.rtt. current parameters 0, where C is the loss that each relaxation attempts to minimize at the current epoch for fixed input sample. Then, we consider the line segment between 0 - aVoL and 0 + aV&L for a 0.03. We discretize this line segment into n = 500 parameter points 01, H1,02,..,0, On. For each parameter value, we compute the loss values 4 12, ... Ins and define the differences A = 14++1 - 4/. Intuitively, there is a discontinuity between 0 and 0,+1 if A, is significantly bigger than its neighbors D,- and A,+1- Formally, we say there is a discontinuity there exists E (1,...., n 2 for which we have that A, > C-A;-I+ D and A, > C. A1+1 + D, where we set C = 10 and D= 10-5 We measure discontinuity using this approach for a batch of 100 input samples and in Figure 6 report the proportion of samples inside the batch for which we have found a discontinuity. For IBP and DeepZ, we could also use theoretical results from Section 4.2 proving that they are always continuous.
When computing sensitivity, recall from Section 4.3 that IBP and hBox always have the trivial scnsitivity of which corresponds to log sensitivity of O. For CROWN-IBP (R), we previously derived worst case sensitivity of OMMB+),, where B is the number of ReLU-affine blocks in the network. This bound assumes that all ReLU layers are unstable (meaning they contain at least one unstable ReLU neuron), which usually holds for trained networks and practical values of Gest. As this is not always the case when observing the whole training procedure, we extend the previous analysis with the observation that a sequence of consecutive affine and stable ReLU layers can be treated a single affine layer, and obtain a tighter sensitivity upper bound of O(MB'+1), where B' denotes the number of ReLU-affine blocks where the RcLU layer is unstable. In Figure 6 we report the log sensitivity B' + 1, averaged across all samples in a single batch. Similarly, for DeepZ and CROWN, their sensitivity is (33B' MB' MB'+1), taking logarithm and factoring out log M, we obtain their log sensitivity is (B' + 1 +1+ log Mr). We set M = -00 as this is the biggest number of neurons in a layer for the network in this experiment.
F Details and Additional Results of Main Experiments
We provide all omitted details of our main experiments given in Section 5.2, including details of networks and training parameters (Appendix F.1), additional investigations into the effect of the seed (Appendix F.2), and cortifying with different relaxations to those used in training (Appendix F.3), as well as complete results omitted from the main text (Appendix F.4), including the hybrid CROWN-IBP defense.
21

---

Published in Transactions on Machine Learning Research (10/2022)
Table 7: The architectures used in main experiments. "FC n" denotes dense (fully-connected) layer with n neurons. "CONV & w x h + s" denotes a convolutional layer with & kernels of size w h and stride All activations are ReLU. CONV+ is equivalent to ,,small" in Gowal et al. (2018).
FC
CONV
CONV+
FC 400
CONV 16 4x4+22
CONV 16 4x4+-2
FC 200
FC
CONV 1x1+1
FC 100
FC 10
FC 100
FC 100
FC 10
FC 10
Table 8: The best choice hyperparameters for each MNIST model in our evaluation.
Net.
Frest
Method
étrain
Nw
N,
LR schedule
Flision
FC
0.1
IBP
0.2
10
100
0.5
56-6
5o-4
milestoncs
yos
FC
0.2
IBP
0.2
10
100
5e-6
5e-4
milestones
yes
FC
0.3
IBP
0.3
10
100
5e-6
5e-4
milestones
yes
FC
0.1
hBox
0.1
0
50
5e-5
5e-4
milestones
yes
FC
0.2
hBox
0.2
10
50
0.5
5e-5
5e-4
milestones
yos
FC
0.3
hBox
0.3
0
50
0.5
5e-5
5e-4
milestones
FC
0.1
CROWN
0.1
0
100
5e-4
milestones
FC
0.2
CROWN
0.2
10
50
5o-4
milestoncs
yes
FC
0.3
CROWN
0.3
10
100
5e-4
milestones
FC
0.1
DeepZ
0.1
10
50
56-6
5o-4
milestones
yes
FC
0.2
DeepZ
0.2
0
50
5e-6
1e-3
steps
FC
0.3
Deep7
0.3
5e-6
1e-3
steps
FC
CROWN-IBP (R)
50
5o-6
5e-4
milestones
yes
0.2
CROWN-IBP (R)
50
5e-6
5e-4
milestones
yes
0.3
CROWN-IBP (R)
0.3
0
50
5e-6
5e-4
milestones
yes
FC
0.1
CROWN-IBP
0.2
10
50
0.5
5e-4
milestones
yes
FC
0.2
CROWN-IBP
0.2
10
50
5o-4
milestoncs
yos
FC
0.3
CROWN-IBP
0.3
10
100
5e-4
milestones
yes
CONV
0.1
IBP
0.2
0
50
0.5
5e-6
5e-4
milestones
yes
CONV
0.2
IBP
0.3
0
50
0.5
5o-6
5e-4
milestones
yes
CONV
0.3
IBP
0.3
0
50
0.5
5e-6
5e-4
milestones
yes
CONV
0.1
hBox
0.3
0
50
0.5
5o-5
5o-4
milestoncs
yos
CONV
0.2
hBox
0.3
0
50
0.5
5e-5
5e-4
milestones
CONV
0.3
hBox
0.3
0
50
0.5
5e-5
5e-4
milestones
CONV
0.1
CROWN
0.2
10
100
5e-4
milestones
CONV
0.2
CROWN
0.2
10
100
5o-4
milestones
yes
CONV
0.3
CROWN
0.3
10
100
5e-4
milestones
yes
CONV
Deep7
0.2
50
5e-6
5e-4
milestones
yes
CONV 0.2
DeepZ
0
50
50-6
5o-4
milestones
yes
CONV
0.3
DeepZ
0
50
5e-5
5e-4
milestones
yes
CONV 0.1
CROWN-IBP (R)
0.1
10
50
5e-4
milestones
yes
CONV 0.2
CROWN-IBE (R)
0.2
10
50
5e-4
milestones
yes
CONV
0.3
CROWN-IBP (R)
0.3
10
50
0.5
5e-6
5e-4
milestones
yes
CONV
0.1
CROWN-IBP
0.2
10
100
0.5
56-6
5o-4
milestones
yes
CONV
0.2
CROWN-IBP
0.3
10
50
0.5
5e-6
5e-4
milestones
yes
CONV
0.3
CROWN-IBP
0.3
10
50
5e-6
5e-1
milestones
yes
22

---

Published in Transactions on Machine Learning Research (10/2022)
F.1 Networks and Hyperparameters
Here we detail the setup of the main experiments shown in Table 2. All runs use a single GePorce RTX 2080 Ti GPU. The details of networks FC, CONV, and CONV+ are shown in Table 7. The hyperparameters vary by datasct.
For MNIST, we tune all hyperparameters thoroughly. We train all models for 200 epochs, starting with a worm-up (Nwr epochs) followed by a ramp-up period (N, epochs) stabilize the training procedure (Gowal et al., 2018). During the warm-up we train the network naturally, During the ramp-up we gradually increase the perturbation radius from 0 to étrain: decrease from Kstort 1 to Kend (shifting from natural to certified training), and for CROWN-IBP gradually shift. from CROWN-IBP (R) to IBP loss. We use a batch size of 100 (50 for memory intensive models) and train using the Adam optimizer with the initial learning rate a. Finally, we use L, regularization with the strength hyperparameter X. We tune NN,
X, a), as well as the learning rate schedule (milestones, where we reduce the learning rate 10x at epochs 130 and 190, or steps, where we halve it every 20 epochs), and the choice of last layer clision (where we clide the final layer hr. of the network with the specifications Cy' as in Gowal et al. (2018)). For each perturbation radius Eteat {0.1, 0.2, 0.3), we train with étrain E {0.1, 0.2, 0.3, 0.4) and report the best result. In Table 8 show the best choice of hyperparameters for each model used in our evaluation (see Appendix F.4 for full results).
For FNshionMNIST, we reuse the best. hyperparameter choice of the corresponding MNIST model.
For SVHN, we use the parameters given in prior work as a starting point, and introduce minimal changes. For IBP, CROWN-IBP (R), and CROWN-IBP, we start from the paramcters given in Gowal et al. (2018): we train for 2200 epochs with batch size 50, warm-up for 10 epochs, ramp-up for 1100 epochs, use Adam with initial learning rate of a = 1e-3 (reduced 10x at 60% and 90% of the training steps), and use Ctrain 1.l We do not use random translations (as we notice these harm the results on large Étest), and we tune Kend (trying 0 and 0.5 for each method-0 performs better for all methods except CROWN-IBP (R)), introduce L1 regularization (improves the results only for TBP, with A = 5e-5), tune the initial learning rate (we end up using a = 5c-4 for IBP and CROWN-IBP). For hBox, DecpZ and CROWN, we use the parameters from Wong & Kolter (2018): batch size of 20, training for 100 epochs (training longer does not improve the results), using Adam with initial learning rate a 1e-3 halved every 10 epochs, ramp-up w.r.t, e of 50 epochs where we start from 0.001. We introduce ramp-up w.r.t. x with Rend = 0. As before, we exclude the data transformations. For all three methods we use L1 regularization with A 5e-6.
For CIFAR-10, we similarly use the parameters from prior work. For IBP, CROWN- (R), and CROWN- IBP, we use the values from Zhang et al. (2020): 3200 epochs, 320 of warm-up and 1600 of ramp-up (using Kend = 0 and étrain = 1.16test for all methods, Kstart = 1 for IBP and Kstort = 0 for other methods), Adam with a = 5e-4 reduced 10x at epochs 2600 and 3040, and random horizontal flips and crops as augmentation. We halve the batch size 512 for all three methods. For Deep' and hBox we use 50 random Cauchy projections (Wong et al., 2018) and the parameters based on Wong al. (2018) but with extended training length and introduced ramp-up w.r.t. 8: we train with batch size 50 for 240 epochs, 80 of which are ramp-up, using Adam optimizer with a = 5c-4, halved every 10 epochs. During ramp-up we start from c 0.001, and use Kstart 1 and Kend = 0.
F.2 Estimating the Effect of the Seed
To estimate variability and demonstrate that it does not significantly impact our main conclusions, we use one efficient method (IBP) and perform the same run with best parameters from Appendix F.1 with 10 seed values, across two datasets (MNIST and FashionMNIST) and both networks (FC and CONV). In all experiments we use étest = 0.3. The results, with the mean and the standard deviation of obtained results, are given in Table Note that, for both MNIST networks, the results we report in Table are the best out of all 10 seeds (74% and 86.8% respectively), as expected given that the hyperparameters were tuned on this seed. As is it too expensive to run repetitions for relaxations other than IBP, we can not estimate the confidence intervals of their results. Nonetheless, if we look the confidence interval of the size of two standard deviations for our IBP results, it would not change the conclusions we made based on single experiment runs reported in Table 2. Namely, continuity and scnsitivity, alongside tightness, can explain the results in Table 2.
23

---

Published in Transactions on Machine Learning Research (10/2022)
Table 9: The variability of the results when changing the seed.
Seed
Dataset
Net
10
12
13
15
16
18
19
Mean
Stddev
MNIST
FC
74
70.8
70.6
71.5
70.9
69.9
72.7
72.2
66
69
70.7
2.45
MNIST
CONV
86.8
86.6
85.7
86.5
86.1
86.2
86.1
85.4
86.3
85
86.1
0.56
MNIST
FC
40.4
40.4
38.8
40.6
42.1
39.8
45
42.5
42.6
42.7
41.5
1.82
MNSSI
CONV
52
51.7
50
52.1
51.6
50.2
50.4
52.1
52.2
51.3
0.86
Table 10: The evaluation of models trained with certified training using different convex relaxations.
Method (certification)
Net
Etest
Method (training)
IBP
hBox
CROWN
DeepZ
CROWN-IBP (R)
FC
0.1
IBP
89.5
89.5
44.7
84.1
FC
0.3
IBP
74
74
3.7
25.5
64.5
FC
0.1
hBox
88.4
88.4
36.6
55.9
83.4
FC
0.3
hBox
57
2.4
7.1
10.8
FC
0.1
CROWN
0
90.9
91.6
0
FC
0.3
CROWN
0
54.3
57.3
0
FC
0.1
DeepZ
0
0.1
92.5
93
0.6
FC
0.3
DeepZ
0
0.1
64.2
63.5
1.8
0.1
CROWN-IBP (R)
5.7
76.8
90.2
90.6
FC
0.3
CROWN-IBP (R)
1.8
10.4
37.4
56.8
70.5
FC
0.1
CROWN-IBP
91.2
91.2
65.3
78.2
88.2
FC
0.3
CROWN-IBP
77.9
77.9
8.6
29
72.6
CONV
0.1
IBP
94.6
94.7
92.3
93.1
CONV
0.3
IBP
86.8
86.8
12.4
46.7
64.9
CONV
0.1
hBux
92.7
92.7
90.6
91.2
91.7
CONV
0.3
hBox
83.7
83.7
26.3
50.3
73.4
CONV
0.1
CROWN
0.1
87.8
94.4
94.5
93.6
CONY
0.3
CROWN
65.2
55.1
CONV
0.1
DeepZ
12
92.6
94.9
95.1
94.7
CONV
0.3
DeepZ
0.4
25.8
69.8
74
60.9
CONV
0.1
CROWN-IBP (R)
0
59.1
93.1
93.5
93.4
CONV
0.3
CROWN-IBP (R)
0
0.2
59.5
67.6
75.4
CONV
0.1
CROWN-IBP
94.4
94.5
92.4
92.9
93.3
CONV
0.3
CROWN-IBP
86.6
86.6
32.8
60.3
78
24

---

Published in Transactions on Machine Learning Research (10/2022)
Table 11: Complete evaluation results on the MNIST dataset.
Ctcat 0.1
Gcest 0.2
Ecout = 0.3
Method
Ace (%)
PGD (%)
CR (%)
Ace (9)
PGD (%)
CR (%)
Acc (%)
PGD (%)
CR (%)
IBP
94.8
90.7
89.5
92.6
86.6
82.4
88.7
80.8
74.0
hBox
95.6
90.6
88.4
93.2
82.1
76.6
89.2
65.7
57.0
CROWN
98.6
94.6
91.6
93.0
85.5
80.6
84.9
71.7
57.3
FC
Decp2
98.3
96.1
92.5
95.0
90.9
85.1
87.4
77.9
64.2
CROWN-IBP (R)
9-.9
91.8
90.6
81.6
80.9
79.9
70.5
CROWN-IBP
95.5
92.0
91.2
93.3
88.6
86.0
90.8
83.6
77.9
IBP
97.2
95.0
94.6
95.9
92.3
91.3
89.7
86.8
hBox
95.1
93.0
92.7
95.1
90.9
89.5
95.1
87.9
83.7
CROWN
96.8
95.1
94.5
96.8
92.6
88.0
92.6
84.3
70.2
CONV
DeepZ
97.0
95.7
94.9
97.0
94.0
88.8
92.5
87.0
69.8
CROWN- IBP (R)
98.5
95.2
93.4
95.5
90.9
86.9
93.4
84.5
75.4
CROWN-IBP
96.9
94.8
94.4
95.6
92.0
90.9
94.8
89.1
86.6
F.3
Training and Certifying with Different Relaxations
In this scction, investigate the effect of varying the convex relaxation used to certify network trained using some method M, to justily our choice of using the same relaxation for training and certification in our main experiments.
We use the MNIST models with éxest = 0.3 from Table 2 and the corresponding models for éxest = 0.1 from the full results given in Appendix F.4, on both FC and CONV architectures. We evaluate their certified robustness using all five introduced methods. The results are given in Table 10. Observe that almost all IBP trained models have extremely low certified robustness when certified with DeepZ, even though it is tighter, and vice versa. This confirms previous statement that training with M produces network particularly suitable to certification with M, and justifies our decision to focus on this case. The few exceptions, i.e., the instances where a method different than M achieved better result (by more than the minimal 0.1% after rounding), are marked in bold. We can see that certification with lighter CROWN often slightly improves BeepZ-traines networks. However, this improvement mostly leaves the relative order of methods unchanged and does not affect our conclusions. Note that if we are interested in the highest certified robustness of an already trained model, the best approach is to always use more expensive certifiers (Tjeng al., 2019; Singh et al., 2019 9a; Tjandraatmadja et al., 2020) which not fast enough to be used in training. However, here we focus analyzing training properties of single relaxation, and not maximizing certified robustness.
F.4 Complete Results of Main Experiments
In Tables 11 to 13 we present complete certified training evaluation results, expanding the ones given in Section 5.2. In all tables, Ace denotes accuracy, PGD denotes empirical robustness against PGD attacks (we use 100 steps with step size 0.01), and CR denotes certified robustness. For UNTST/FashionMNNT we include two smaller perturbation radii, érest = 0.1 and étest = 0.2. Note that the paradox of certified training can rarely be observed for such small radii, and we thus the main paper focus on the challenging case of strong adversaries, i.e. Etest = 0.3 for MNIST PasTTToMNSo and Étest = 8/255 for SVHN CCIFAR-10, as it most clcarly illustrates the differences between relaxations. Further, this case of greater interest as it is well-established benchmark for robustness even outside of the area of certified robustness (Madry et al., 2018; Croce al,, 2020). To explain the unusually high standard accuracy of CROWN-IBP (R) in our CIFAR-10 experiments, note that it is the only method that performs better with Kend 0.5 (as opposed to Kend = 0). All other methods could reach similar standard accuracy with Rend 0.5, but their certified robustness would drop.
datasets
25

---

Published in Transactions on Machine Learning Research (10/2022)
Table 12: Complete evaluation results the PashionMNIST dataset.
0.1
0.2
0.3
Method
Ace (%)
PGD (%)
CR (%)
Ace (%)
PGD (%)
CR (%6
Acc (%)
PGD (%)
CR (%)
79.2
71.4
67.9
73.7
65.2
57.9
hBox
79.2
73.1
70.0
76.3
62.5
56.4
68.7
49.2
39.6
CROWN
80.8
70.6
67.8
70.9
53.7
49.5
52.4
35.9
30.2
FC
DeepZ
81.2
73.7
70.2
71.2
57.6
51.6
51.0
39.2
35.0
CROWN IBP (R)
76.6
68.1
66.5
69.6
54.7
51.3
69.6
46.7
41.1
CROWN IBP
78.1
72.1
69.6
74.7
64.7
58.9
66.7
55.9
47.9
IDP
80.3
74.1
72.7
76.5
65.5
61.4
76.5
58.8
52.0
hBox
72.9
65.2
72.9
61.3
CROWN
71.9
64.3
62.8
71.9
55.2
49.4
56.4
39.9
31.5
CONV
DeepZ
72.3
64.8
72.3
60.1
40.7
34.0
CROWN-IBP (R)
$1.0
72.5
69.9
71.8
58.2
54.5
68.9
50.2
40.0
CROWN-IBP
80.0
73.5
72.1
74.7
63.7
00.2
65.3
56.5
50.9
Table 13: Complete evaluation results SVHN dataset with the CONV network and Ctest 8/255 (lcft),
and on CIFAR-10 datasel with the CONV+ network and étest 8/255 (right).
Method
Acc (%)
PGD (%)
CR (%)
Method
Acc (%)
PGD (%)
CR (%)
IBP
41.6
30.9
28.9
IBP
39.8
32.4
29.0
hBox
35.0
26.9
23.6
hBox
36.2
25.9
20.0
CROWN
44.0
27.3
23.4
CROWN
OOM
0OM
OOM
DeepZ
38.7
27.7
24.5
DeepZ
36.5
28.6
22.8
CROWN-IBP (R)
65.8
37.2
27.5
CROWN-IBP (R)
37.4
28.7
24.3
CROWN-IBP
43.9
32.6
29.3
CROWN-IBP
41.1
32.8
30.3
Table 14: The extension of our main experimental results in various alternative settings. All experiments are done on the MNIST dataset.
Method
Original
Kaiming
Ortho
Xavier
IBPInit
L2
BigLR
ThnyLR
SCD
10%
30%
50%
IBP
74.0
61.7
71.2
67.3
67.6
71.0
61.1
74.3
23.8
49.0
64.3
69.4
hBox
57.0
37.4
48.7
41.5
11.3
47.7
44.3
52.4
10.0
17.9
35.2
45.8
CROWN
57.3
58.3
59.9
61.8
55.2
58.3
61.0
55.8
11.3
31.3
48.3
52.9
FC
DeepZ
61.2
60.1
63.4
63.1
64.1
64.2
60.9
59.1
11.3
42.1
60.7
64.0
CROWN-IBP (R)
70.5
61.5
67.5
64.8
65.8
69.6
70.3
63.4
4.5
44.2
62.8
68.6
CROWN-IBP
77.9
76.4
76.7
77.2
77.7
77.4
76.0
77.9
19.0
67.7
73.5
75.4
85.7
86.1
85.8
85.8
86.6
83.3
80.7
84.2
85.0
bBox
83.7
82.4
69.3
69.5
83.1
85.0
69.0
85.9
80.7
81.8
83.4
85.3
CROWN
70.2
70.1
70.5
67.1
68.6
70.6
67.5
68.1
67.8
61.6
68.5
67.3
CONV
DoepZ
69.7
67.1
67.6
69.0
69.5
66.7
67.8
67.2
62.6
67.9
68.5
CROWN-IBP (R)
75.4
77.9
76.7
77.7
73.7
73.9
72.4
73.5
72.0
58.5
69.2
71.9
CROWN-IBP
86.6
87.0
86.8
86.7
86.5
86.4
86.5
86.3
82.8
78.4
84.7
85.5
26

---

Published in Transactions on Machine Learning Research (10/2022)
G Excluding Alternative Explanations
Here we extend subset of our evaluation given in Section 5.2 to a wider range of settings, aiming to show that our claims about contimuity and sensitivity of cxisting relaxations are not strictly dependent on one of the concrete settings used in our main experiments. We use MNIST and both FC and CONV networks.
The results are presented in Table 14. Each column represents evaluation with one modified setting compared to the base run from Section 5.2, repeated in the first column. The next four columns correspond to different weight initializations: Kaiming Normal (He et al.,, Orthogonal (Saxe et al., 2014), Xavier Normal (Glorot & Bengio, 2010), and IBPInit (Shi et al., 2021). The column marked L2 indicates the use of L2 regularization instead of L1. For the following two columns, BigLR and TingLR, we increase (respectively, decrease), the learning rate two times. We further experiment with using the SGD optimizer instead of Adam, and training on stratified subsets of the training set with 10, 30, and 50 percent of data, respectively. We can see that the relative order of relaxations is fairly consistent across all settings, implying that our conclusions from Section 5.2 hold and are not tied to a specific choice of a setting.
H Details of Relaxation Modifications
We give more details on modifications of relaxations explored in Section 6. For each, we describe the relaxation used as base (also shown in the diagram in Figure 10), the performed change, the intended effect on properties, and the resulting unintended effect on properties. The summary of CR-AUC scores for all modifications is given in Table 15, produced by an experiment in the same setting as Figure 2. We treat the relaxation as loose its tightness is closer to IBP than hBox. While we choose names indicative of the origin of each modification, note that we rediscover some less prominent relaxations considered in prior work, as an example, DeepZ-Diag corresponds to zDiag from (Mirman al., 2018). In the following, when describing linear bounds, use x',x, to refer to Fi 1--1, 1 for brevity. Further, we refer to two stable ReLU cases as positive and negative.
Starting from hBox ب and selting x S x' < x -1 (unstable case) produces a theoretically non-comparable hBoz-Diag em which is empirically much less tight. Going further to remove the discontinuity by setting the same bounds for the negative case, we arrive at hBox- hBoo-Diag-CC m, completely sacrificing tightness (0.00 AUC in Table 15). Finally, we partially remedy tightness by switching between hBox and h hBox-Diag using a heuristic similar to one in CROWN to get hoor-Switch m which as side-effect. introduces discontinuity.
h-oo--bsedd Modifications.
DeepZ- Modifications. Fixing 0 5 x' S u and x S x' - for the unstable case in Deep2 mm produces Deep I and Deep ID both now not sensitive, but looser and discontinuous. We construct DeepZ-Diag-G C mm and DeepZ-Switch un analogously to hBox-Diag-C and hBox-Switch. Further, we introduce DeepZ-Soft amm to eliminate the discontinuity of Deep7-Switch, by set = (0(l/u u/I) with parameter y, where o denotes the sigmoid function. Then, for the unstable case we set Ax S x' < Ax - when x 2 u/(u- I) and Az <x' < Ax + u Au otherwise. We find that y works best. While this both resolves the discontimuity and makes Deept-Switch tighter, it reintroduces the problem of sensitivity, leading to properties comparable to original Deep7. Finally, we explore DeepZ-IBP (R) mm relaxation analogous to CROWN-IBP (R) using IBP for intermediate bounds, which partially alleviates the sensitivity issue of DeepZ by slightly sacrificing tightness.
CROWN-based Modifications. We obtain CROWN-0 a and CROWN-1 - by fixing 0 S x' (and I S x' respectively) as the lower bound for the unstable case, in an attempt to remove the discontinuity caused by heuristically switching between them in CROWN m. However, this introduces new kind of discontinuities at / /=0 0 and = 0 respectively and slightly harms tightness, making these relaxations still both discontinuous and highly sensitive. If we aim to obtain continuity, we can set I 5 for the positive case in CROWN-O to obtain CROWN-O-C س , and analogously set x S x' for the negative case in CROWN-1 to get CROWN-1-C mm. While the latter becomes prohibitively loose, the former retains some tightness (i.c., it is tighter than IBP). Alternatively, modifying CROWN-O and CROWN-1 to alleviate high scnsitivity
instead of discontinuity by setting x' < x I for the unstable case of CROWN-0, or x' S u for the unstable case of CROWN-1, we obtain CROWN-O-TT Tria and - mm both looser than their original
27

---

Published in Transactions on Machine Learning Research (10/2022)
Table 15: Tightness of relaxation modifications quantified as CR-AUC, calculated the setting of Figure 2.
CROWN C
CROWN 1-IaleCC
CROW IBP (R)
CROWN N N-Suk Ipp
MBere Dast
Miss Dast
Aitee Soileh
DeydZ-Kar
DoepZ-Dii Ding
Devy Ding
DeveZ Swithi
Denpt Sulf
Despi tBe (8)
CROWN
CROWX-
CROWN-G
CROW Piia
CROWN.
CROWN-L-
CROWN P11a
CROW Sult
Mikes
Degui
CR-AUC 1.70
1.38
1.98
1.50
147
324
215
-wix-hwitch
Box
hBox
hBox- Diag
hBox-Diag-
DeepZ-Box
DeepZ-Switch
DeepZ-Soft
DeepZ-IBP (R) <
DeepZ
DeepZ-Diag
DeepZ-Diag-C
CROWN-O-Tris -> CROWN-O-Tria 7
CROWN-IBP (R)
CROWN-0
CROWN-O-C
CROWN-Soft-IBP
CROWN
CROWN-1
CROWN-1-C
CROWN-Soft
CROWN-1-Tria >> CROWN-1-Tria-
Figure 10: display of explored relaxation modifications indicating the origin of each proposed modification.
relaxations, as can be seen in Table 15. These two relaxations can be further made continuous: using x' S x for the negative and 1 5 x' for the positive case in CROWN-O-Tria leads to CROWN-O-Trio- an and using æ S x' for the negative and S for the positive case CROWN-1-Trie leads to CROWN- 1 Tria-C mm both sacrificing most of their tightness to obtain two other favorable properties. Further, investigate the continuous variant of CROWN, CROWN-Soft me obtained analogously to Deep'-Soft, and CROWN-SOfftIBP obtained by combining both the ideas of soft switching from CROWN-Soft and computing intermediate bounds with IBP in CROWN-IBP (R) mm
Generalizing Continuity and Sensitivity
We now discuss how contimuity and sensitivity could be generalized from binary to numerical metrics to compare any pair of relaxations. For continuity, this can be done by empirically measuring the number of discontinuitics along one direction in the loss landscape as we have donc in Figure 5 and Figure 6 (left). These experiments show that CROWN indeed has more discontimuities than CROWN-IBP (R). Similarly, sensitivity can be generalized by considering the exact upper bound degree (instead of only whether it is greater than 1), as derived in Soction 4.3. This would explain that DeepZ, which has the sensitivity of O(3 MB+1), performs worse than CROWN-IBP (R) which has the sensitivity of ((M Overall, while our properties were designed to compare IBP with other relaxations, they could be extended to compare any pair of relaxations.
28

---

Published in Transactions on Machine Learning Research (10/2022)
J Detailed Derivations of Sensitivity
In this scction we provide more detailed derivations of sensitivity, expanding on those presented in Scction 4.3. As the first layer is always affine, we have Fı,j E (6) for all relaxations. To compute the sensitivily of each relaxation, we will sequentially analyze the effect of each network layer.
IBP IBP/hBox. For IBP, assume that at layer i, all 25-1, E (5). For an affine layer, as l and Us are linear combinations of elements of u:-1 and 1;,1 the degree stays the same and Fi E Pv((). For a ReLU layer, as U ReLUU(;111)) (same for 1.z) we again have Fı,j E Px (5) (we consider two cases: Ui = 0 and "i --1يj: both of which are in (o))... Thus, since the degree does not change neither in affine nor ReLU operations, and in the first layer the degree is 1, all neurons are in (0) C (8),), i.e., the sensitivity of IBP is 1. For hBox, the only difference are affin layers, where now Iijj = (W j + bag- As linear combinations of elements of (r) are in (6), all neurons stay in (6) and the sensitivity of hBox is also 1.
Deepz/CROwn The ReLU bounds of DeepZ, AT;-1.5 and λT;-1.J - M4-1, significantly increase the 1-))))- After the first ReLU layer, we have that 22, R2(6) because À E R1 (5) and 21,j E (6). This changes the behavior of all following affine layers, a linear combination of M elements of (o) is in (0) Thus, T3.j E (6). For the following ReLU layers, if we assume the inputs Iz-1, are in (o), we have that XE R2x( and thus the outputs Fa, are in (5) This is because we are multiplying elements of (o) and (2)( and we get an expression in (5). Putting this together, each ReLU-affine block from layer 4 onwards multiplies the sensitivity by 3M. As there are B = [T/2] - such blocks, we obtain 2 3B MB+1 for the final sensitivity. Recall that CROWN has the same upper bound as DeepZ for unstable ReLUs, but chooses the lower bound adaptively: 0 S æij if -1-11 2 14- or 2t-1, I Fi,z otherwise. Both of these options do not change the degree: if 1ą-1,1 is in (x), then also Fij is in (6) However, CROWN uses the same upper ReLU bounds as Deep7 with the slope À := (1-1,/(u;-1, - 11-1,),, ) so we can apply the same analysis as before for the upper bound, and show that the sensitivity of CROWN is 2 3 MB+1 as well, despile having a simpler expression for the lower bound. Thus, both DeepZ and CROWN are highly sensitive.
sensitivity. Recall that here À == 14-13/ (44-1J 44-15/(44-15
CROWN-IBP (R). Here, at ReLU layer i during the (only) backsubstitution, we have consider 4-1.5 and 1 separately from 1;-1,j- Recall that the former were precomputed with IBP, and are thus in Pi (using the same analysis explained earlier for IBP). Then, Zμ-1, get substituted as usual for CROWN and can carry larger sensitivity. The main difference here is that X == 0;-1.;/( - 4-1.)) is in R1 because 4-1.j and 44-1, were computed using IBP, meaning they are in Pi(6), and this implies that X E (8).). Assuming Æ4-1,5 E (ō) (N 2 1) and using the previons observation that we always have À E (o),, it follows that Izij E (6). As the affine layers have the same effect as in the case of CROWN, each of B following ReLU-afine blocks now increases sensitivity from N to g(N) (N + 1)M, and we have, as before, 33. E Rear (6). Thus, the final sensitivity is g (2M) 2M/+11 + M + +... M, which can be proven by induction. We have g¹ (2M) 2M2 + M and assume the identity holds for g (2M) Now:
(2M) (g0-1(2M) 1)M
= =(2MB + M MB B-1
+... + M+1)M
B+1 + +M +...+M).
(M B-1 completing the proof. We further write g2(2M = .M B+1 (MB-1 + M + ... + M +1) and using the closed-form formula for the sum of first B 2 terms of a geometric scries (assuming M 1) simplify this to:
B = MB+1 M -
B2 M M
(6)
M 1
M-1
which is in O(MB+1). Clearly, CROWN-IBP (R) is also significantly more sensitive than IBP and hBox.
29


Reviews:
[{"review_id": "Xz95c9XUJ4", "reviewer": "Reviewer_nPi7", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The proposed work is well written and motivated. It seems to thoroughly study the properties of different approaches in certified robustness  and provides a plausible mechanism to explain the \"paradox of certified training\". \n\nI am not an expert in the literature on certified training but based on my reading, I recommend the paper to be accepted. ", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The proposed work is concerned with certified robustness, in particular certified training of neural networks. In this approach to mitigating the sensitivity of neural networks, an upper and lower bound of the output change effected by a bounded change of the input. \nThe resulting bounds are optimized during training, allowing to optimize models that achieve a high degree of *certifiable* robustness. \n\nThe starting point of the proposed work is the \"paradox of certified training\", an observation in the literature that using tighter bounds in the certification of robustness does not usually improve the results. This should not be possible for globally optimally trained neural networks, suggesting that optimization difficulties are at the heart of the issue.\n\nTo illucidate this mechanism, the present work studies two related properties of certificates that impact optimization. The discontinuity of the resulting loss function and it's sensitivity to small perturbations of the network parameter. \nThe authors proceed to measure these quantities for multiple certificates and observe that indeed the tighter certificates produce more irregular and/or sensitive loss functions than that obtained by interval bound propagation (IBP), a simple application of interval arithmetic.\nThis explains the fact that the IBP outperforms all other approaches in terms of certified robustness, even though the latter are based on tighter certificates.  ", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "I do not request any changes.", "broader_impact_concerns": "I do not have any concerns about the broader impact of this work. ", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "73SMTtwxGL", "reviewer": "Reviewer_bUar", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Robust training is a large topic and the question being pursued by the paper is definitely of interests to wide audience. The extensive experimentation over several common methods is valuable to the literature. I particularly find the parameterization in Table 4, as a way to probe understanding, quite interesting.\n\nMy main reservation is that the two identified properties are argued to be key influencing factors to robustness mainly by the comparison between IBP vs other methods (Table 2 and relevant discussions). What about other pairs? For example, CROWN-IBP (R) has worse tightness (Table 1) than CROWN, is discontinuous like CROWN, and shares the same order of sensitivity as CROWN, but Table 2 shows it consistently beats CROWN. Can the hypothesized properties predict this outcome? A similar observation for CROWN-IBP (R) vs DeepZ.\n\nThe paper proposes that worse continuity and sensitivity tend to impede optimization as an explanation, but is it clear that the loss region where discontinuity or high sensitivity occurs is responsible for the bad final performance? Or is it that methods that have worse continuity / sensitivity in this paper actually have an overall loss landscape that is unfavorably non-convex to gradient descent training? Recall that the loss landscape is inherently non-convex, regardless of tightness, continuity, sensitivity. In other words, what the paper has shown is that continuity and sensitivity can be used to qualitatively predict if a method may offer more robust performance, but it is unclear from the paper if continuity and sensitivity have a causal relation with performance.\n\nThere are a few weaknesses of the specific measures of continuity and sensitivity:\n- Continuity does not seem quantifiable, so one can only compare continuous vs discontinuous methods. \n- Sensitivity is defined w.r.t. the first layer only. Why shouldn’t other layers matter to the optimization?", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studies the phenomenon that certified training methods of the (ReLU-network) convex relaxation type may have better robustness performance despite worse tightness. The paper identifies two further properties, (dis)continuity (of the loss landscape) and sensitivity (w.r.t. perturbation of the first layer’s weight), which are argued via extensive experiments to influence the optimization and thereby the performance. In particular, the paper points out that a method which has worse tightness can have better continuity and sensitivity properties, leading to better performance, though the paper also demonstrates that the interdependency among these properties is complex.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "Aside from addressing my criticisms:\n- Can the paper clarify why it makes sense to conclude, say, CROWN-IBP (R) is more sensitive than IBP, based on the estimate $O(M^{B+1})$? These estimates seem worst-case, and clearly $R_m(\\delta) \\subseteq R_n(\\delta)$ for any $m \\leq n$. There is still the possibility that the effective sensitivity that the gradient descent trajectory experiences under CROWN-IBP (R) is much less than $O(M^{B+1})$.\n- Can the paper clarify why the only difference accounted for hBox, in the comparison with IBP on Page 7, is the affine layers? Doesn’t it make sense that hBox, a discontinuous method, should have very high sensitivity?\n- Can the paper specify the confidence interval / error margin for Table 4, if possible? Some of these numbers are too close to make a clear comparison.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "kHMoeYy36Q", "reviewer": "Reviewer_BLjF", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- The problem is relevant and interesting, and the authors provide a novel perspective.\n- The parts of the paper which are supposed to convey intuition are well-written and convincing.\n- The experimental evidence is compelling.\n- The results are interesting and suggest new directions of research. Specifically, the results suggest that one may wish to construct a tight relaxation with few discontinues and low sensitivity. Alternatively, proving that such a tight relaxation cannot exist is also interesting.\n\nWeaknesses:\n\n\n- The paper misses some key definitions. To make the paper friendlier to the casual reader, it would be helpful to add definitions for convex relaxations, tightness of relaxation, certified robustness, etc. Currently, those terms are defined in a very vague, non-quantitative, and intuitive manner. Just an example (but certainly not the only one), Theorem 1 refers to $CR(\\theta,r)$, the certified robustness, which is not defined anywhere in the paper, at least not where I could see.\n\n- The experimental evidence is not supported by theory, and the contribution itself is somewhat limited. The paper does make an interesting observation, but it would have been more interesting to follow up on this observation.\n\n- I found the explanation and intuition about the sensitivity property (Section 4.3) to be too vague. \n1. First, just looking at the degree of rational function seems to be too coarse. It suggests that the sensitivity of $\\frac{1}{1+x^2}$ should be treated the same as $1+x^2$, which is not very meaningful. Also, depending on the domain, the coefficients of the polynomial should also matter. Usually, sensitivity is measured with respect to Lipschitz constants or modulus of continuity; why is it justified to only look at the degree?\n\n2. Second, I would appreciate a discussion about why sensitivity is measured with respect to changes in the first layer. While the importance of the first layer is intuitively clear in this context, I think there is room for discussion in the scope of the paper.\n\n3. Finally, I found it a bit hard to track the calculation of sensitivity for the different models. Adding a section to the appendix where those calculations are carefully derived would be a good idea.", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper addresses a so-called paradox in certified robust training of neural networks, where tighter convex relaxations tend to produce lower certified robustness. This phenomenon is counterintuitive; tighter relaxations serve as better approximations to the network layers, and one would expect that training a network with such relaxations would produce better results.\n\nThe paper proposes a possible explanation for this effect. Tighter relaxations tend to produce undesirable properties which hinder training algorithms. Specifically, the authors identify two main properties:\n\n- Discontinues: the training loss function, after the relaxation, exhibits discontinues. This is clearly unfavorable for gradient-based algorithms and will have a negative impact on the training algorithm.\n\n- Sensitivity: The effect of small weight changes on the output loss. This affects the stability of the training algorithm, and stable algorithms tend to perform better.\n\nThe authors show, through numerical evidence, that tighter relaxations tend to either posses many discontinues of the loss function or have large sensitivity (or both). This provides a possible way to explain the apparent paradox. It is not the tightness of the relaxation that matters but rather its interplay with the training procedure.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "As I indicated above, the claims made in the paper are mostly supported by convincing and clear evidence, and I do think that some of TMLR's audience would be interested in the findings. So, conditional on addressing the issues I raised above, I would be inclined to recommend acceptance.\n\nSpecifically, I ask that:\n1. parts of the paper be made more formal, with proper preliminaries.\n2. Better discussion and explanations concerning the sensitivity property.", "broader_impact_concerns": "I do not have concerns about the broader impact.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: After one round of discussion with the reviews, the reviewers concurred that the authors addressed their concerns, and the paper is in a much better shape. With that in mind, the paper will be a good contribution to TMLR. 
Decision: Accept (poster)