{'fraction_non_alphanumeric': 0.044582522047875384, 'fraction_numerical': 0.0188552284961631, 'mean_word_length': 4.410037952133839, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 4, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
On the Paradox of Certified Training

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.


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 , hBox (Mirman et al., 2018)), which provide robustness guarantees by approximating the effect of network layers on the input specification. A key property of a convex relaxation is its tightness, indicating how close it is to the non-convex shape it overapproximates.
The Paradox of Certified Training. As tighter relaxations are more desirable for certification (Salman et al., 2019b;Singh et al., 2019b), a natural belief is that tightness is also favorable for relaxations when used in training as part of a certified defense. Surprisingly, several prior works (Gowal et al., 2018;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 a real model in Table 1. We easily observe a paradox: tighter relaxations obtain worse results. More specifically, none of the tighter relaxations can consistently outperform the loose IBP. 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) convex 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 precisely those which affect certified training, is difficult. In light of this, recent advances primarily focus on mitigating the practical effects of the paradox by improving the underlying optimization (Balunovic & Vechev, 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 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 sensitive 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 1 seem contradictory if considering only tightness, additionally considering continuity and sensitivity provides a more viable explanation and helps demystify the paradox. Concretely, tighter relaxations in Table 1 are harmed by discontinuity or high sensitivity of their loss, shedding light on why they do not outperform the continuous and non-sensitive IBP. On a range of datasets and architectures, our experimental evaluation further substantiates the importance of considering these two additional properties in order to gain a deeper understanding of certified training dynamics.

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 of popular relaxations. In Section 5, we provide detailed experimental evidence supporting our findings. Finally, in Section 6 we present a study of relaxation modifications, demonstrating complex dependencies between properties which complicate the process of improving unfavorable properties of existing relaxations.

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 et 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 Gehr et al., 2018;Singh et al., 2018;Raghunathan 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 relaxations, 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), or rely on SMT (Katz et al., 2017) and MILP (Tjeng et al., 2019) solvers. Two fundamentally different competitive approaches, not our focus, are l ∞ -distance nets (Zhang et al., 2021), used together 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 an L-layer feedforward ReLU network h = h L • h L−1 • · · · • h 1 with parameters θ, where h i : R ni−1 → R ni is the transformation applied at layer i. Let the network input be x 0 ∈ R n0 and let Each h i is either a dense/convolutional layer, both of which can be viewed as an affine transformation , where max is applied componentwise. Further, we assume the two layer types alternate, with h 1 and h L being affine. We focus on classification, where inputs x 0 are classified to one of n L classes based on the logit vector z ≡ x L , and the case of ∞ robustness. Namely, to certify robust classification to label y in an ∞ ball of radius > 0 around x, we prove that for every y = y where c y = e y − e y , by upper bounding the left-hand side with a negative value.
Given some , and a set D of input examples (x, y) ∈ R n0 × [n L ], we use CR(θ, , m) ∈ [0, 1] to denote the certified robustness of a network with parameters θ under certification method m, i.e., 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 a 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, overapproximating (i.e., relaxing) the effect of non-linear 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 x i , l i ∈ R ni and u i ∈ R ni respectively. Starting from l 0 = x − and u 0 = x + we aim to obtain l L and u L , which yields the desired upper bounds of c T y z for all y , allowing us to verify the robustness property. To this end, all following methods (linear relaxations) maintain one upper and one lower linear bound for each neuron x i,j of layer i: where a ij , a ij ∈ R ni−1 and d ij , d ij ∈ R for all j ∈ [n i ]. Excluding the IBP relaxation, all methods use for stable ReLU bounds, and calculate l i and u i using backsubstitution introduced next. Unstable ReLU (l i−1,j < 0 < u i−1,j ) bounds are method-specific and can depend on l i−1 and u i−1 .

Backsubstitution.
Starting with x i,j ≤ a ij T x i−1 + d ij (similarly for the lower bound), we substitute x i−1 by replacing each x i−1,j with its respective upper bound a i−1,j x i−2 + d i−1j if (a ij ) j is positive and with its 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 where p j T , p j T ∈ R n0 and q j , q j ∈ R for all j ∈ [n i ]. Here, we can in turn substitute the appropriate side of l 0 ≤ x 0 ≤ u 0 for each element in x 0 , to obtain a lower and upper bound l i,j and u i,j on x i,j solely w.r.t. the bounds of x 0 . 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 x, 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 l i,j and u i,j on each x i,j . For a small number of relaxation pairs (r 1 , r 2 ), e.g., hBox and IBP (see Appendix B.2), we can prove that r 1 is strictly tighter than r 2 (i.e., each bound is strictly tighter), implying that for any fixed network and perturbation, every example that is certified by r 2 is also certified by r 1 . 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 DeepZ relaxation (Singh et al., 2018), equivalent to CAP , Fast-Lin , and Neurify (Wang et al., 2018b), uses the following for unstable ReLUs (Figure 1a): IBP/hBox. The IBP (Gowal et al., 2018) or Box (Mirman et al., 2018;Gehr et al., 2018) relaxation uses interval arithmetic instead of backsubstitution, ignoring other dependencies. For affine layers, the upper bound (similarly for the lower bound) is Figure 1b). hBox 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 ≤ x i,j ≤ u i−1,j , for unstable ReLUs, replacing x i,j with these bounds in the rest of backsubstitution. For stable ReLUs and affine layers, as with all other methods except IBP, it uses  and DeepPoly (Singh et al., 2019b) have the same upper bound as DeepZ for unstable ReLUs, but choose the lower bound adaptively: Figure 1c). CROWN-IBP (R)  is a variant which efficiently computes l i and u i using IBP at all layers except the last, which uses CROWN and performs a full backsubstitution.

CROWN/CROWN-IBP (R). CROWN
Certified Training. While adversarial training often improves empirical robustness, certified robustness (ratio of inputs where we can guarantee robustness as in Equation 1)   known observation reaffirmed in Appendix B.1. Certified training Mirman et al., 2018;Gowal et al., 2018;Raghunathan et al., 2018a;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 L CE (ẑ, y), whereẑ is the worst case logit, s.t.,ẑ y = l L,y andẑ y = u L,y 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 (β : 1 → 1 in ) from the certified defense CROWN-IBP (β : 1 → 0 in ) which combines CROWN-IBP (R) and IBP losses in training.

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 in practice, and discuss existing hypotheses that attempt to explain it.
Tightness Should Help Training. Recall from Section 2 that while we can rarely prove that a relaxation is strictly tighter than another relaxation, there is a consistent empirical understanding of their relative tightness. We illustrate this in Figure 2 by comparing certified robustness (CR) curves of relaxations on a 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 it in the following when referring to tightness. As tighter relaxations certify more examples when applied to 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.

Training with Tighter Relaxations Leads to Worse Results
. Surprisingly, it is well established (Gowal et al., 2018;Balunovic & Vechev, 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 to 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 test = 0.3) after certified training of the same MNIST network with each relaxation.
Existing Hypotheses. While recent state-of-the-art certified defenses based on convex relaxations (Balunovic & Vechev, 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 , yield hard optimization problems (Balunovic & Vechev, 2020), or simply state that they unexpectedly underperform (Gowal et al., 2018;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 (e.g., hBox, CROWN, CROWN-IBP (R)) as these are discontinuous (Section 4.2), thus directly violating their Lipschitz continuity assumptions.

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 of prior work, to improve our understanding of the paradox.

Tightness of Convex Relaxations
While tightness alone cannot explain the performance differences, it still has a significant role in the final certified robustness. We highlight this with the following theorem: Theorem 1. Let r 1 and r 2 be two convex relaxations, where r 1 is known to be strictly tighter than r 2 . For a network parametrized by θ and any ≥ 0, it holds that max θ CR(θ, , r 1 ) ≥ max θ CR(θ, , r 2 ).
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 is strictly tighter than the other. However, our results in Table 1 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, gradient-based optimization in practice leads to worse parameters for tighter relaxations and the underlying reasons are unclear. While convex relaxations represent layer constraints as convex sets, the training loss is not necessarily convex with respect to network weights. Moreover, we observe that some relaxations create a discontinuous loss landscape, harming first-order optimization as gradients near the discontinuity do not provide any information about the function values after the discontinuity (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 relaxations have many discontinuities when instantiated on a 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 as counting the number of discontinuities (see for example Figure 6 or 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 I for a further discussion.

Continuity of Convex Relaxations
We focus on the discontinuity of the output layer lower bounds l L , treating each l L,j as a function of the network weights. Note that all findings can be easily extended to the actual loss function L CE (ẑ, y). We construct a minimal example to produce the discontinuities: a 3-layer network with input x 0,1 ∈ [−1, 1], affine layer x 1,1 = x 1,2 = x 0,1 + w where w is the only network parameter, ReLU layer x 2,1 = ReLU(x 1,1 ), x 2,2 = ReLU(x 1,2 ), and the output layer given as x 3,1 = x 2,1 + 1 and x 3,2 = x 2,2 − x 2,1 (see Appendix C.1 for an illustration of the network). Figure 3 shows the discontinuities that arise when varying the parameter w.
As our example shows, few neurons are sufficient to produce discontinuities. Thus, we expect large networks to have a large number of discontinuities, appearing at any ReLU neuron x i,j , whenever −l i−1,j = u i−1,j (for CROWN) or l i−1,j = 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
For both, the unstable case bounds (in the limit) match the stable case ones; therefore, there is no discontinuity.

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 δ 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 δ as R N (δ) = {p(δ)/q(δ) | p(δ), q(δ) ∈ P N (δ)}, where P N (δ) denotes the polynomials of degree up to N . Note that P N (δ) ⊆ R N (δ). We say that some neuron x i,j is in the set P N (δ) (or R N (δ)) if that set contains both l i,j and u i,j , now treated as functions of δ where δ = 0 corresponds to the concrete l i,j and u i,j used in Section 2. Everything else is treated as a constant. During backsubstitution for x i,j , all encountered x i ,j are repeatedly replaced with bound expressions from Equation 2, until we reach Equation 3 to obtain linear expressions for l i,j and u i,j . If the output neurons of the network are in R N (δ), we say that the sensitivity of a relaxation is N . Sensitivity is an undesirable 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 l L , 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 is exact. This is summarized in Table 2.
Computing the Sensitivity. As the first layer is affine, we have x 1,j ∈ P 1 (δ) for all relaxations. To compute the sensitivity, we sequentially analyze the effect of each layer.
IBP/hBox. For IBP, assume that at layer i, all x i−1,j ∈ P N (δ). For an affine layer, as l i,j and u i,j are linear combinations of elements of u i−1 and l i−1 , we have x i,j ∈ P N (δ). For a ReLU layer, as u i,j = ReLU(u i−1,j ) (same for l i,j ) we again have x i,j ∈ P N (δ). Thus, all neurons are in P 1 (δ) ⊆ R 1 (δ) so the sensitivity of IBP is 1. For hBox, the only difference are affine layers, where now As linear combinations of elements of P N (δ) are in P N (δ), all neurons stay in P 1 (δ) and the sensitivity of hBox is also 1. DeepZ/CROWN. The ReLU bounds of DeepZ, λx i−1,j and λx i−1,j − λl i−1,j , significantly increase the sensitivity. After the first ReLU layer, we have that x 2,j ∈ R 2 (δ) as λ ∈ R 1 (δ). This changes the behavior of all following affine layers, as a linear combination of M elements of For the following ReLU layers, if we assume the inputs are in R N (δ), we have that λ ∈ R 2N (δ), and thus the outputs are in R 3N (δ). Putting this together, each ReLU-affine block from layer 4 onwards multiplies the sensitivity by 3M . As there are B ≡ L/2 − 1 such blocks, we obtain 2 · 3 B M B+1 for the final sensitivity. CROWN uses the same upper ReLU bounds as DeepZ, so we can apply the same analysis, and show that the sensitivity of CROWN is 2 · 3 B M B+1 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 l i−1,j and u i−1,j separately from x i−1,j . While the former were precomputed with IBP, and are thus in P 1 (δ), the latter get substituted as usual and can carry larger sensitivity. Assuming x i−1,j ∈ R N (δ) (N ≥ 1) and observing that we always have λ ∈ R 1 (δ), it follows that x i,j ∈ R N +1 (δ). As the affine layers have the same effect as before, each ReLU-affine block now increases sensitivity from N to (N + 1)M . As before, x 3,j ∈ R 2M (δ), so summing the arising geometric series gives the final sensitivity of . Clearly, CROWN-IBP (R) is also significantly more sensitive than IBP and hBox.

Continuity and Sensitivity Impact Optimization
We now discuss how discontinuity 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 maximize 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 δ = 0 (see Appendix D for details).
The Impact of Discontinuities. The key issue with discontinuous relaxations is that GD can, at a discontinuity, fall off a cliff in the landscape to a 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 literature stating that optimizing discontinuous functions requires complex algorithms (Conn & Mongeau, 1998;Martínez, 2002;Wechsung & Barton, 2014).
The Impact of High Sensitivity. Sensitive relaxations introduce a 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 δ, IBP has the minimum sensitivity and is thus piecewise linear, allowing GD to quickly converge to a higher value. Extensive theory (Pardalos & Vavasis, 1991;Jibetean & de Klerk, 2006;Zoej et al., 2007) confirms that high-degree polynomial and rational functions, which appear for sensitive relaxations, are hard to optimize.

Experimental Evaluation
In this section we perform an experimental evaluation, further substantiating our hypothesis on the properties of relaxations that explain the paradox of certified training. First, in 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. First, we measure continuity and sensitivity on a naturally trained network. Namely, we train FC, a 5-layer network (see Appendix F.1) on MNIST. Then, we measure the change in the lower bound of one output neuron as we shift all first layer weights by δ in the gradient direction of that neuron. In Figure 5, we show the resulting bounds depending on δ, on a representative input with = 0.15. Similar results are observed for different choices of δ and . The experiment 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.1.

Continuity and Sensitivity in Practice
Additionally, in Figure 6 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 discontinuous at the start of training when more ReLUs are changing stability, and becomes more continuous as they stabilize, when CROWN is more discontinuous due to a larger percentage of consistently unstable ReLUs. These observations match our results on continuity from Section 4.2. While DeepZ is continuous, we 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.

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 architectures: FC, a 5-layer dense network, and CONV, a 3-layer convolutional network. For CIFAR-10 we use the larger 4-layer CONV+, here necessary to obtain nontrivial accuracies after certified training. Note that further increasing network size only marginally boosts the results , but prevents training with time and memory intensive CROWN, which can already not be trained on CONV+. We focus on well-established and challenging cases  Table 3: Certified training of two MNIST networks with modifications of relaxations aimed at improving unfavorable properties. The first row shows the favorability of tightness (T), continuity (C) and sensitivity (S) for each relaxation. The following rows show certified robustness (in %). Reproducing the Paradox. Our main results are shown in Table 2. Whereas prior work provides certain evidence, our comprehensive experiments over 5 relaxations, 4 datasets and several networks, confirm that the well-known paradox of certified training generally holds: tighter relaxations obtain worse results, and no tight relaxation can consistently outperform the loose IBP. Note that we 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 (see 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 it is favorable. Considering tightness as a sole property of a relaxation led to a 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 discontinuous and sensitive relaxations will not produce satisfactory results. This is confirmed in Table 2.
Namely, we can attribute the poor results of hBox and CROWN-IBP (R) to the discontinuities in their loss which harm gradient descent. While DeepZ is continuous, it 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 sensitivity, and achieves the best results. This provides novel insights on the paradox-relaxations with unfavorable properties get worse results.
Excluding Alternative Explanations. Exactly quantifying the impact of each property (tightness, continuity, and sensitivity) on the result is challenging, as it might heavily depend on the setting, e.g., dataset or network (see discussion in Section 6). However, to exclude the possibility that our conclusions are an artifact of a specific setting (e.g., they hold only for a particular weight initialization), we repeat a subset of 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 LooseIBP-DC 300 86.2 ± 0.4 82.3 ± 0.2 79.0 ± 0.2 71.9 ± 1.2 24.9 ± 13.8 11.3 ± 0.0 11.3 ± 0.0 LooseIBP-DC 1000 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.

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 relaxation to make it more successful in certified training? To investigate this question we systematically 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 a complex tradeoff.

Discovering Modifications.
To obtain the modifications, we 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 ReLU), and those for which there is a strictly 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 a CROWN-inspired heuristic; (ii) changing the same bounds in a soft way, eliminating the discontinuity introduced by the switching heuristic, and (iii) 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 favorability of each property, and certified robustness after certified training of FC and CONV networks. Our claims on tightness of these modifications are based on empirical CR-AUC measurements in the same setting as in Figure 2 (see Appendix H for details). We defer complete descriptions of each modification, including the intended as well as unintended effects on properties, to Appendix H.
The main observation from Table 3 is that properties are not independent-modifying a relaxation to improve a property often negatively affects another one. For example, by fixing the lower bound x i−1,j ≤ x i,j for unstable ReLUs in CROWN to eliminate the discontinuities due to heuristic switching, we obtain CROWN-1 , which introduces a new kind of discontinuities at u i−1,j = 0 and is slightly looser. Further, using x i−1,j ≤ x i,j for the negative case creates CROWN-1-C , which is now continuous, but significantly looser. Both of these relaxations perform worse than CROWN, while some similar changes result in improvements, implying a complex tradeoff between properties, where they differently affect the certified training in different scenarios, as previously observed in Section 5.2. 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-art 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 we focus on in this work.
Towards Understanding the Tradeoff. To further demonstrate that properties can affect training in different ways for different settings, as opposed to previously explored discrete modifications, we consider two parametrized modifications of IBP-continuous LooseIBP-C(ω), which before every ReLU layer replaces the interval arithmetic bounds [l, u] with [l − ω, u + ω], and discontinuous LooseIBP-DC F (ω), which uses , and is further parametrized by F , where larger F leads to more discontinuities. Increasing the looseness parameter ω reduces the tightness of all relaxations. For fixed ω, all LooseIBP-DC F (ω) have intuitively comparable tightness, and are all strictly tighter than LooseIBP-C(ω).
In Table 4 we present the certified training results for various values of ω and F , with the CONV network trained on the MNIST dataset, following the setting 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 ω, we do not expect improvements over IBP (which achieves 86.8% CR in this case, see Table 2). However, it is interesting to determine when sacrificing the continuity of LooseIBP-C(ω) for tightness of LooseIBP-DC F (ω) is beneficial (we highlight such cases for each ω in bold). Namely, we can see that in tight regimes (low ω), the advantage of tightness on average outweighs the harm of discontinuities, and we get comparable or slightly more favorable results for most F . As we move to looser regimes (high ω), 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 ω, where some of the relaxations are comparable, our conclusion still stands. Note that for high ω, 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 a 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.

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 Croce et al., 2020) on 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 continuity 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 a 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  or using better initialization (Shi et al., 2021), and have shown to be a promising way to obtain state-of-the-art certified robustness. Future work could attempt 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 altogether 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 certification-friendly model architectures (Zhang et al., 2021;2022) have achieved strong results, which may suggest that this avenue is the most promising. However, these methods come with their own set of challenges and tradeoffs, previously discussed in Section 2. x 0,1 x 0,2 x 1,1 x 1,2 x 2,1 x 2,2 x 3,1 x 3,2

A Backsubstitution Example
Here we illustrate the process of backsubstitution concretely on the toy network shown in Figure 7, using DeepZ. The same example but with the CROWN/DeepPoly relaxation is shown in (Singh et al., 2019b).

B Additional Results on Tightness
Here we present results related to tightness, namely our experiments measuring empirical tightness 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 1 and further in Figure 2.
Setup. We conduct 8 experiments (labeled A-H), varying the dataset (MNIST, FashionMNIST, CIFAR-10), the network (CONV and CONV+, described in Appendix F.1, and FC-S, a 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, we 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 as warm-up (natural training), and the following 50 as ramp-up, where we slowly increase the perturbation radius from 0 to . We use L2 regularization with strength 5e-3 for experiment E, and 5e-5 for other experiments. The experiments are summarized in Table 5.
After training the networks, we sample 100 values from 0 to 0.07 for natural, 0 to 0.15 for PGD = 0.1, and 0 to 0.4 for PGD = 0.3 models. For every radius , we use each relaxation to attempt 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 1 contains CR-AUC values of curves from Figure 2 (experiment A), and certified robustness after certified training of the same network with train = 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 6. From these results, we can confirm two claims given in the main paper: It is necessary to use certified training to obtain a certifiably robust network. We can see that adversarial training, along with improving empirical robustness, also has a positive effect on 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 certifies the most at = 0.3 is 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) to 86.8% (best method), as seen in Table 2.
The relative tightness of relaxations is well established and can be empirically 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 tightness discussion to more complex relaxation-based methods that do not necessarily fit the framework presented in Section 2 can be challenging. As an example, recently introduced β-CROWN (Wang et al., 2021b) can in practice outperform the provably tighter Triangle (Ehlers, 2017) (Wang et al., 2021b) andpreviously in (Salman et al., 2019b).

B.2 hBox is Strictly Tighter Than IBP
Here we sketch a 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 3 (Informal). Given a neural network architecture parametrized by θ ∈ R d , for any choice of θ, hBox can certify robust classification for more inputs 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 same constraints: 0 ≤ x i,j ≤ u i−1,j . When u i−1,j < 0, both set x i,j = 0. The only difference is when l i−1,j > 0: in this case IBP uses l i−1,j ≤ x i,j ≤ u i−1,j , while hBox sets x i,j = x i−1,j . By definition we have l i−1,j ≤ x i−1,j ≤ u i−1,j , implying that hBox constraints are indeed tighter.

B.3 Strictly Tighter Relaxations have Better Certified Robustness Optima
Here we restate and prove Theorem 1. Theorem 1. Let r 1 and r 2 be two convex relaxations, where r 1 is known to be strictly tighter than r 2 . For a network parametrized by θ and any ≥ 0, it holds that max θ CR(θ, , r 1 ) ≥ max θ CR(θ, , r 2 ).
Here, the first inequality follows from the fact that r 1 is a strictly tighter relaxation than r 1 for any parameter choice. The second inequality follows from the definition of θ 2 as maximum, completing the proof.

C.1 Network Used to Show Discontinuities
The sketch of the network described in 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 i and u i are computed directly as a function of l i−1 , u i−1 , and θ. For affine layers, this function is a sum of products of elements in l i−1 , u −1 and θ, which is continuous w.r.t. all variables. If i is a ReLU layer, the lower (upper) bound function is ReLU(l i−1,j ) (resp. ReLU(u i−1,j )), which is also clearly continuous. As compositions, sums, and products of continuous functions are continuous functions, this directly shows that l L,j are ultimately continuous.
DeepZ: For DeepZ, computing each l i and u i includes backsubstitution, where to obtain the final expressions (as in Equation 3), we repeatedly substitute in lower/upper bound expressions, based on the values of θ and l i and u i from all previous layers. As before, it suffices to show that for some i, l i and u i are continuous w.r.t. θ and all previous l i and u i .
First, recall that during each step of backsubstitution we encounter terms of the form α · x i ,j , and based on the sign of α substitute the lower or the upper bound expression for x i ,j . When one such α = 0, α · x i ,j is continuous (both the left and the right limit equal the function value at that point, 0). Thus, we can reduce 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 fixed.
Next, recall that even if 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 l i and u i 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. θ that uses only elementary operations, which is continuous.
It is left to discuss the behavior in points where some elements of some l i or u i are zero. In this case the ReLU is still stable, but switches to being unstable on one side of zero. If l i ,j = 0 both upper and lower bound expressions for x i +1,j are x i ,j , which is also the right limit. In the left limit, we use the unstable ReLU bounds λx i ,j and λx i ,j − λl i ,j and see that for l i ,j → 0, λ → 1, and thus these bounds approach x i ,j as well, so there is no discontinuity. Similarly, for u i ,j = 0 (the other stable case) the bounds (as well as the left limit) are 0. 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. To conclude, we showed that l i and u i are continuous w.r.t. θ and all previous l i and u i . This can be composed to conclude that l L,j is continuous w.r.t. θ, using the same argument we used for IBP.

D Details of Gradient Descent Experiments
In this section we provide details of the experiments with used to generate Figure 4, discussed in Section 4.4.
For both examples we consider an architecture consisting of 2 hidden layers with 10 neurons each, and 2 output neurons. The network receives a 1-dimensional input. We randomly sample the input, weights, and biases as integers in [−4, 4], and sample the perturbation radius 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 learning rate to 0.005, learning rate decay to 0.99, and ran for 100 epochs. We sampled a number of different networks for both scenarios, and chose the one which best illustrates the behavior of gradient descent.

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 sensitivity with same setup 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 a network 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. Next, we can see that if the network was trained with CROWN or hBox, there is a significantly smaller number of discontinuities than in 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 4 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 ∇ θ L w.r.t. current parameters θ, where L is the loss that each relaxation attempts to minimize at the current epoch for a fixed input sample. Then, we consider the line segment between θ − α∇ θ L and θ + α∇ θ L for α = 0.03. We discretize this line segment into n = 500 parameter points θ 1 , θ 2 , ..., θ n . For each parameter value, we compute the loss values l 1 , l 2 , ..., l n , and define the differences ∆ i = |l i+1 − l i |. Intuitively, there is a discontinuity between θ i and θ i+1 if ∆ i is significantly bigger than its neighbors ∆ i−1 and ∆ i+1 . Formally, we say there is a discontinuity if there exists i ∈ {1, . . . , n − 2} for which we have that ∆ i > C · ∆ i−1 + D and ∆ i > C · ∆ i+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 our 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 sensitivity of 1 which corresponds to log sensitivity of 0. For CROWN-IBP (R), we previously derived worst case sensitivity of O(M B+1 ), 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 test . 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 as a single affine layer, and obtain a tighter sensitivity upper bound of O(M B +1 ), where B denotes the number of ReLU-affine blocks where the ReLU 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 O(3 B M B +1 ), taking logarithm and factoring out log M , we obtain their log sensitivity is (B + 1) · (1 + log 3 log M ). We set M = 400 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 certifying 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. Table 7: The architectures used in our main experiments. "FC n" denotes a dense (fully-connected) layer with n neurons. "CONV k w × h + s" denotes a convolutional layer with k kernels of size w × h and stride s. All activations are ReLU. CONV+ is equivalent to "small" in Gowal et al. (2018

F.1 Networks and Hyperparameters
Here we detail the setup of the main experiments shown in Table 2. All runs use a single GeForce RTX 2080 Ti GPU. The details of networks FC, CONV, and CONV+ are shown in Table 7. The hyperparameters vary by dataset.
For MNIST, we tune all hyperparameters thoroughly. We train all models for 200 epochs, starting with a warm-up (N w epochs) followed by a ramp-up period (N r epochs) to 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 κ start = 1 to κ end (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 α. Finally, we use L 1 regularization with the strength hyperparameter λ. We tune (N w , N r , κ end , λ, α), as well as the learning rate schedule (milestones, where we reduce the learning rate 10× at epochs 130 and 190, or steps, where we halve it every 20 epochs), and the choice of last layer elision (where we elide the final layer h L of the network with the specifications c y as in Gowal et al. (2018) For FashionMNIST, 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 parameters 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 α = 1e-3 (reduced 10× at 60% and 90% of the training steps), and use train = 1.1 test . We do not use random translations (as we notice these harm the results on large test ), and we tune κ end (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 IBP, with λ = 5e-5), tune the initial learning rate (we end up using α = 5e-4 for IBP and CROWN-IBP). For hBox, DeepZ and CROWN, we use the parameters from : batch size of 20, training for 100 epochs (training longer does not improve the results), using Adam with initial learning rate α = 1e-3 halved every 10 epochs, ramp-up w.r.t. of 50 epochs where we start from = 0.001. We introduce ramp-up w.r.t. κ with κ end = 0. As before, we exclude the data transformations. For all three methods we use L1 regularization with λ = 5e-6.
For CIFAR-10, we similarly use the parameters from prior work. For IBP, CROWN-IBP (R), and CROWN-IBP, we use the values from : 3200 epochs, 320 of warm-up and 1600 of ramp-up (using κ end = 0 and train = 1.1 test for all methods, κ start = 1 for IBP and κ start = 0 for other methods), Adam with α = 5e-4 reduced 10× at epochs 2600 and 3040, and random horizontal flips and crops as augmentation.
We halve the batch size to 512 for all three methods. For DeepZ and hBox we use 50 random Cauchy projections  and the parameters based on  but with extended training length and introduced ramp-up w.r.t. κ: we train with batch size 50 for 240 epochs, 80 of which are ramp-up, using Adam optimizer with α = 5e-4, halved every 10 epochs. During ramp-up we start from = 0.001, and use κ start = 1 and κ end = 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 9. Note that, for both MNIST networks, the results we report in Table 2 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 took 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 sensitivity, alongside tightness, can explain the results in Table 2.

F.3 Training and Certifying with Different Relaxations
In this section, we investigate the effect of varying the convex relaxation used to certify a network trained using some method M, to justify our choice of using the same relaxation for training and certification in our main experiments.
We use the MNIST models with test = 0.3 from Table 2 and the corresponding models for test = 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 our previous statement that training with M produces a 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 a better result (by more than the minimal 0.1% after rounding), are marked in bold. We can see that certification with tighter CROWN often slightly improves DeepZ-trained 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 et al., 2019;Singh et al., 2019a;Tjandraatmadja et al., 2020) which are not fast enough to be used in training. However, here we focus on analyzing training properties of a single relaxation, and not on 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, Acc denotes accuracy, PGD denotes empirical robustness against PGD attacks (we use 100 steps with step size 0.01), and CR denotes certified robustness. For MNIST/FashionMNIST datasets we include two smaller perturbation radii, test = 0.1 and test = 0.2. Note that the paradox of certified training can rarely be observed for such small radii, and we thus in the main paper focus on the challenging case of strong adversaries, i.e., test = 0.3 for MNIST/FashionMNIST and test = 8/255 for SVHN/CIFAR-10, as it most clearly illustrates the differences between relaxations. Further, this case is of greater interest as it is a well-established benchmark for robustness even outside of the area of certified robustness (Madry et al., 2018;Croce et 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 κ end = 0.5 (as opposed to κ end = 0). All other methods could reach similar standard accuracy with κ end = 0.5, but their certified robustness would drop.

G Excluding Alternative Explanations
Here we extend a subset of our evaluation given in Section 5.2 to a wider range of settings, aiming to show that our claims about continuity and sensitivity of existing 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), andIBPInit (Shi et al., 2021). The column marked L2 indicates the use of L2 regularization instead of L1. For the following two columns, BigLR and TinyLR, 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.  relaxations, as can be seen in Table 15. These two relaxations can be further made continuous: using x ≤ x − l for the negative and l ≤ x for the positive case in CROWN-0-Tria leads to CROWN-0-Tria-C , and using x ≤ x for the negative and x ≤ u for the positive case in CROWN-1-Tria leads to CROWN-1-Tria-C , both sacrificing most of their tightness to obtain two other favorable properties. Further, we investigate the continuous variant of CROWN, CROWN-Soft , obtained analogously to DeepZ-Soft, and CROWN-Soft-IBP obtained by combining both the ideas of soft switching from CROWN-Soft and computing intermediate bounds with IBP in CROWN-IBP (R) .

I Generalizing Continuity and Sensitivity
We now discuss how continuity 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 discontinuities along one direction in the loss landscape as we have done in Figure 5 and Figure 6 (left). These experiments show that CROWN indeed has more discontinuities 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 Section 4.3. This would explain that DeepZ, which has the sensitivity of O(3 B M B+1 ), performs worse than CROWN-IBP (R) which has the sensitivity of O(M B+1 ). Overall, while our properties were designed to compare IBP with other relaxations, they could be extended to compare any pair of relaxations.

J Detailed Derivations of Sensitivity
In this section we provide more detailed derivations of sensitivity, expanding on those presented in Section 4.3.
As the first layer is always affine, we have x 1,j ∈ P 1 (δ) for all relaxations. To compute the sensitivity of each relaxation, we will sequentially analyze the effect of each network layer.
IBP/hBox. For IBP, assume that at layer i, all x i−1,j ∈ P N (δ). For an affine layer, as l i,j and u i,j are linear combinations of elements of u i−1 and l i−1 , the degree stays the same and x i,j ∈ P N (δ). For a ReLU layer, as u i,j = ReLU(u i−1,j ) (same for l i,j ) we again have x i,j ∈ P N (δ) (we consider two cases: u i,j = 0 and u i,j = u i−1,j , both of which are in P N (δ)). 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 P 1 (δ) ⊆ R 1 (δ), i.e., the sensitivity of IBP is 1. For hBox, the only difference are affine layers, where now x i,j = (W i x i−1 ) j + b i,j . As linear combinations of elements of P N (δ) are in P N (δ), all neurons stay in P 1 (δ) and the sensitivity of hBox is also 1.
DeepZ/CROWN. The ReLU bounds of DeepZ, λx i−1,j and λx i−1,j − λl i−1,j , significantly increase the sensitivity. Recall that here λ := u i−1,j /(u i−1,j − l i−1,j ). After the first ReLU layer, we have that x 2,j ∈ R 2 (δ) because λ ∈ R 1 (δ) and x 1,j ∈ P 1 (δ). This changes the behavior of all following affine layers, as a linear combination of M elements of R N (δ) is in R M N (δ). Thus, x 3,j ∈ R 2M (δ). For the following ReLU layers, if we assume the inputs x i−1,j are in R N (δ), we have that λ ∈ R 2N (δ), and thus the outputs x i,j are in R 3N (δ). This is because we are multiplying elements of R N (δ) and R 2N (δ), and we get an expression in R 3N (δ). Putting this together, each ReLU-affine block from layer 4 onwards multiplies the sensitivity by 3M .
As there are B ≡ L/2 − 1 such blocks, we obtain 2 · 3 B M B+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 ≤ x i,j if −l i−1,j ≥ u i−1,j , or x i−1,j ≤ x i,j otherwise. Both of these options do not change the degree: if x i−1,j is in R N (δ), then also x i,j is in R N (δ). However, CROWN uses the same upper ReLU bounds as DeepZ with the slope λ := u i−1,j /(u i−1,j − l i−1,j ), so we can apply the same analysis as before for the upper bound, and show that the sensitivity of CROWN is 2 · 3 B M B+1 as well, despite having a simpler expression for the lower bound. Thus, both DeepZ and CROWN are highly sensitive.

CROWN-IBP (R).
Here, at ReLU layer i during the (only) backsubstitution, we have to consider l i−1,j and u i−1,j separately from x i−1,j . Recall that the former were precomputed with IBP, and are thus in P 1 (δ) (using the same analysis explained earlier for IBP). Then, x i−1,j get substituted as usual for CROWN and can carry larger sensitivity. The main difference here is that λ := u i−1,j /(u i−1,j − l i−1,j ) is in R 1 (δ) because l i−1,j and u i−1,j were computed using IBP, meaning they are in P 1 (δ), and this implies that λ ∈ R 1 (δ). Assuming x i−1,j ∈ R N (δ) (N ≥ 1) and using the previous observation that we always have λ ∈ R 1 (δ), it follows that x i,j ∈ R N +1 (δ). As the affine layers have the same effect as in the case of CROWN, each of B following ReLU-affine blocks now increases sensitivity from N to g(N ) = (N + 1)M , and we have, as before, x 3,j ∈ R 2M (δ). Thus, the final sensitivity is g B (2M ) = 2M B+1 + M B + . . . + M , which can be proven by induction. We have g 1 (2M ) = 2M 2 + M and assume the identity holds for g B−1 (2M ). Now: . . + M + 1) and using the closed-form formula for the sum of first B + 2 terms of a geometric series (assuming M = 1) simplify this to: which is in O(M B+1 ). Clearly, CROWN-IBP (R) is also significantly more sensitive than IBP and hBox.