Understanding Certified Training with Interval Bound Propagation
Authors: Yuhao Mao
Mark Niklas Mueller
Marc Fischer
Martin Vechev
Venue: ICLR 2024 poster (2024)
Keywords: Certified Robustness
Adversarial Robustness
Neural Network Verification
Certified Training
Primary area: societal considerations including fairness, safety, privacy
TL;DR: We theoretically investigate certified training with Interval Bound Propagation, using a novel metric measuring the tightness of the resulting bounds.

Abstract: As robustness verification methods are becoming more precise, training certifiably robust neural networks is becoming ever more relevant. To this end, certified training methods compute and then optimize an upper bound on the worst-case loss over a robustness specification. Curiously, training methods based on the imprecise interval bound propagation (IBP) consistently outperform those leveraging more precise bounds. Still, we lack a theoretical understanding of the mechanisms making IBP so successful. In this work, we investigate these mechanisms by leveraging a novel metric measuring the tightness of IBP bounds. We first show theoretically that, for deep linear models (DLNs), tightness decreases with width and depth at initialization, but improves with IBP training. We, then, derive sufficient and necessary conditions on weight matrices for IBP bounds to become exact and demonstrate that these impose strong regularization, providing an explanation for the observed robustness-accuracy trade-off. Finally, we show how these results on DLNs transfer to ReLU networks, before conducting an extensive empirical study, (i) confirming this transferability and yielding state-of-the-art certified accuracy, (ii) finding that while all IBP-based training methods lead to high tightness, this increase is dominated by the size of the propagated input regions rather than the robustness specification, and finally (iii) observing that non-IBP-based methods do not increase tightness. Together, these results help explain the success of recent certified training methods and may guide the development of new ones.

Published as a conference paper at ICLR 2024
UNDERSTANDING CERTIFIED TRAINING WITH INTERVAL BOUND PROPAGATION
Yuhao Mao, Mark Niklas Müller, Mare Fischer & Martin Vechev Department of Computer Science, ETH Zürich, Swizterland (yuhao.man mao, ma mrrkmueller, marc. fischer, martin. wei..eeeeeeeee.....eeee ethz..ch
ABSTRACT
As robustmess verification methods are becoming more precise, training certifiably robust neural networks is becoming ever more relevant. To this end, certified training methods compute and then optimize an upper bound on the worst-case loss over a robustness specification. Curiously, training methods based on the imprecise interval bound propagation (IBP) consistently outperform those leveraging more precise bounds. Still, we lack a theoretical understanding the mechanisms mak- ing IBP so successful. In this work, we investigate these mechanisms by leveraging a novel metric measuring the tightness of TBP bounds. We first show theoretically that, for deep linear models (DLNs), tightness decreases with width and depth at initialization, but improves with IBP training. We, then, derive sufficient and necessary conditions weight matrices for IBP bounds to become exact and demonstrate that these impose strong regularization, providing an explanation for the observed robustness-accuracy trade-off. Finally, we show how these results on DLNs transfer to ReLU networks, before conducting an extensive empirical study, confirming this transfcrability and yielding tffe-oofthhe-ar certified accuracy, (ii) finding that while all IBP-based training methods lead to high tightness, this increase dominated by the size of the propagated input regions rather than the robustness specification, and finally (iii) observing that non-IBP-basee methods do not increase tightness. Together, these results help explain the success of recent certified training methods and may guide the development of new ones.
INTRODUCTION
The increasing deployment of deep-learning-bute based systems in safcty-critical domains has made their trustworthiness and especially formal robustness guarantees against adversarial examples (Biggio et al. 2013 Szegedy et al., 2014) an ever more important topic. As significant progress has been made on neural network certification (Zhang al. 2022 Ferrari et 2022), the focus in the field is increasingly shifting to the development of specialized training methods that improve certifiable robustness while minimizing the accompanying reduction in standard accuracy.
Certified Training These certified training methods aim to compute and then optimize approxima- tions of the network's worst-case loss over an input region defined by an adversary specification. To this end, they compute an over-approximation of the network's 's reachable set using symbolic bound propagation methods (Singh et af., 2018 2019b Gowal al. 2018). Surprisingly, training methods based on the least precise bounds, obtained via interval bound propagation (IBP), empirically yield the best performance (Shi et al. 2021 Jovanović al. (2022) investigate this surprising observation theoretically and find that more precise bounding methods induce harder optimization problems.
As result, all methods obtaining state-of-the--e performance leverage IBP bounds either directly (Shi et al. 202I). as regularizer (Palma et al., (022). to precisely but unsoundly approximate the worst-case loss (Miller et al./ 2022b) Mao et al. [023] Palma et al,, 2023). However, while IBP is crucial to their success, none of these works develop a theoretical understanding of what makes IBP training so effective and how affects bound tightness and network regularization.
This Work We take first step towards building deeper understanding of the mechanisms making IBP training so successful and thereby pave the way for further advances in certified training. To this end, derive necessary and sufficient conditions network's weights under which IBP

---

Published as a conference paper at ICLR 2024
bounds become tight, a property we call propagation invariance, and prove that it implies an extreme regularization, agreeing well with the empirically observed trade-off between certifiable robustness and aceuracy (Tsipras et al. 2019; Müller et al., 2022b). To investigate how close real networks are to full propagation invariance, we introduce the metric propagation tightness as the ratio of optimal and IBP bounds, and show how to efficiently compute it globally for deep linear networks (DLNs) and locally for ReLU networks.
This novel metric enables us theoretically investigate the effects of model architecture, weight initialization, and training methods on IBP bound tightness for deep linear networks (DLNs). We show that (i) at initialization, tightness decreases with width (polynomially) and depth (exponentially), (ii) aufficient iith width becomes crucial for trained networks.
tightness is increased by IBP training, and (iii) sufficient
Conducting an extensive empirical study, we confirm the predictiveness of our theoretical results for deep ReLU networks and observe that: (i) increasing network width but not depth improves state-of-the-ar certified accuracy, (ii) IBP training significantly increases tightness, almost to the point of propagation invariance, (iii) unsound IBP-based training methods increase tightness to smaller degree, determined by the size of the propagated input region and the weight of the IBP-loss, but yield better performance, and (iv) con-IIBPbaseee training methods barely increase tightness, leading to higher accuracy but worse robustness. These findings suggest that while IBP-based training methods improve robustness by increasing tightness the cost of standard accuracy. high tightness is not generally necessary for robustness. This observation explains the recent success of unsound IBP-based methods and, in combination with the theoretical and practical insights developed here, promises to be a key step toward constructing novel and more effective certified training methods.
2 BACKGROUND
Here, we provide background adversarial and certified robustness. We consider classifer f: Rdd + R predicting a numerical score y = f(x) )) per class given an input æ E X C I...
Adversarial Robustness describes the property of classifer f to consistently predict the target class for all perturbed inputs x' in an f--norm ball B (a:) of radius Cp- As we focus on fo perturbations in this work, we henceforth drop the subseript p for notational clarity. More formally, we define adversarial robustness as:
arg max f(x') = 1, Vad E (x) = (a' E x ||ac x'Ilp S {p)
Neural Network Certification can be used to formally prove the robustness of a classifier f for given input region B (z:) Interval bound propagation (IBP) (Gowal et al.) 20188 Mirman et al. 2018) simple but popular such certification method. It is based propagating an input region 8 (x) through a neural network by computing Box over-approximations (each dimension is described as an interval) of the hidden state after every layer until we reach the output space. There, it is checked whether all points in the resulting over-approximation of the network's 's reachable set yield the correct classification. As an example, consider an L-layer network f f= h2 o h o... h1, with linear layers h; and ReLU activation functions a. We first over-approximate the input region B (²(x)) as Box with radius 8 = and center 1 æ. such that we have the 7th dimension of the input x E [g T. = [ 50,49 P.. + 5%]. Propagating such a Box through the linear layer h, = W x -1 + =: æ;, we obtain the output hyperbox with centre X' = W
and radius 8' = | where |- denotes the element-wise absolute value. To propagate Box through the ReLU activation ReLU(xx-1) = max(0, x==1), we propagate the lower and
upper bound separately, resulting in an output Box with 3² #'+ø' and 8 ''-e' where æ' = ReI.U - 8111) and x ReI.U( + 86-1). We proceed this way for all layers obtaining first lower and upper bounds the network's 's output y and then upper bound ÿ" on the logit difference いي := y/s yt- Showing that 3F < O, Vi * t is then equivalent to proving adversarial robustness on the considered input region.
2
2
We illustrate this propagation process for a two-layer network in Figure There, we show the exact propagation of the input region in blue, its optimal box approximation in green, and the IBP approximation as dashed boxes L Note how after the first linear and ReLU layer (third column), the box approximations (both optimal and IBP contain already many points outside the reachable set
2

---

Published as a conference paper at ICLR 2024
Decision boundary
IBP Box
21
Exact propagation
Optmal Box
(x") = [-,
0.3
0.2.0.5
0.4 0.4
RcLU(w²)
0.3,0.7
-0.4
0.4
Comparison of exact (,, optimal box and IBP (c) propagation through one layer network. We show the concrete points maximizing the logit difference y/2 Y1 as black x and the corresponding relaxation red x.
Figure 1:
despite being the smallest hyper-box containing the exact region. These so-called approximation errors accumulate quickly when using IBP, leading to increasingly imprecise abstraction, can be seen by comparing the optimal box and IBP 2 approximatio after an additional linear layer (rightmost column). To verify that this network classifies all inputs in [-1, 1]2 to class 1, have to show the upper bound of the logit difference y/2 y/1 to be less than While the concrete maximum of 0.3 2 y/2 y1 (black x) is indeed less than O, showing that the network is robust, IBP O only yields 0.6 2 1/2 y1 (red x) and is thus too imprecise to prove it. contrast, the optimal box yields precise approximation of the true reachable set, sufficient to prove robustness.
required to obtain (certifiably) robust neural networks. For a data distribution (ar, D, standard training optimizes the network parametrization @ to minimize the expected cross-entropy loss:
Training for Robustness
ad = mig
min Ep (fo(((((()) with (yr = In (1+ + exply: v.))
(2)
To train for robustness, we, instead, aim to minimize the expected worst-case loss for given robustness specification, leading to min-mat max optimization problem:
0zbb = arg min Ep
max E'EB'
(ce(So(x().0)
As computing the worst-case loss by solving the inner maximization problem is generally intractable, is commonly under- or over-approximated, yielding adversarial and certified training, respectively.
Adversarial Training optimizes lower bound on the inner optimization objective in Equation (3) It first computes concrete examples x' E B (a) that approximately maximize the loss term LcR and then optimizes the network parameters 0 for these examples. While networks trained this way typically exhibit good empirical robustness, they remain hard to formally certify and are sometimes vulnerable to stronger attacks (Tramer al. 2020 Croce & Hein 2020).
Certified Training typically optimizes an upper bound on the inner maximization objective in Equation 3). The resulting robust cross-entropy loss LCE.ab (B (a:) = Lcu - obtained by first computing an upper bound y on the logit differences y y 3/1 with bound propagation method as described above and then plugging it into the standard cross-entropy loss.
Surprisingly, the imprecise IBP bounds (Mirman et al., 2018 Gowal al. 2018 Shi al. 202 consistently yield better performance than methods based on tighter approximations (Wong et al. 2018 Zhang et 2020 Balunovic & Vechev 2020). Jovanović al. (2022) trace this back the optimization problems induced by the more precise methods becoming intractable to solve.
However, the heavy regularization that makes IBP trained networks amenable certification also severely reduces their standard accuracy. To alleviate the resulting robustness-accuree trade-off,, all current state-of-the-ar certified training methods combine IBP and adversarial training by using IBP bounds only for regularization (IBP-R (Palma et al.) (2222), ). by only propagating small, adversarially selected regions (SABR (Müller et al. (022b)), using IBP bounds only for the first layers and PGD bounds for the remainder of the network (TAPS Mao al. 2023)). combining losses adversarial samples and IBP bounds (CC-IBP, MTL-IBP (Pallaa et al. (023)). ).
In light of this surprising dominance of bbsed training methods, understanding the regularization IBP induces and its effect on tightness promises to key step towards developing novel and more effective certified training methods.

---

Published as a conference paper at ICLR 2024
3 UNDERSTANDING IBP TRAINING
In this section, we theoretically investigate the relationship between the box bounds obtained by layer- wise propagation, i.e., IBP, and optimal propagation. We illustrate both in Figure and note that the latter are sufficient for exact robustness certification (see Lemma First, we formally define layer- wise (IBP) and optimal box propagation, before deriving sufficient and necessary conditions under which the resulting bounds become identical. Then, we show that these conditions induce strong regularization, motivating us to introduce the propagation tighteess T as a relaxed measure of bound precision, which can be efficiently computed globally for deep lincar (DLN) and locally for ReLU networks. Based on these results, we first investigate how tightness depends on network architecture at initialization, before showing that it improves with IBP training. Finally, even linear dimensionality reduction is inherently imprecise for both optimal and IBP propagation, making sufficient network width key for tight box bounds. We defer all proof' to App. B
demonstrate that
Setting
We focus our theoretical analysis on deep linear networks (DLNs), i.e. f(x)
I W (1) x, popular for theoretical discussion of neural networks (Saxe et al. 2014 Ji & Tel
garsky 2019: Wu al., 2019). While such a reduction of ReLU network an overall linear function may seem restrictive, it preserves many interesting properties and allows for theoretical insights, while ReLU networks are theoretically unwieldy. As ReLU networks become linear for fixed activation patterns, the DLN approximation becomes exact for robustness analysis at infinitesimal perturbation magnitudes. Further, DLNs retain the layer-wise structure and joint non-convexity the weights of different layers of ReLU networks, making them a widely popular analysis tool (Ribeiro) ct al. 2016). After proving key results on DLNs, we will show how they transfer to ReLU networks.
3.1 LAYER WIRE AND OPTIMAL BOX PROPAGATION
We define the optimal hyper-box approximation Box" (f, (f)) as the smallest hyper- [z, z such that it contains the image fax) of all points x' in (x)), i.e., f(x') E [z, z), Va' B (z). Similarly, we define the layer-wise box approximation as the result of sequen- tially applying the optimal approximation to every layer individually: Box (f, (x)) = Box" (WL, (.x" (xx((WW)), ("""),)(()))) (x)))). We write their upper- and lower-bounds as [z" x²1 and |z] I respectively. We note that optimal box bounds on the logit differences O = yr
(instead of the logits y as shown in Figure I are sufficient for exact robustness verification:
Lemma 3.1. Any Co continuous classifier f. computing the logit difference y := y/ yr, vi + 1, is
robustly correct on B (a)) if and only if Box" (f,)(( S RRo01 i.e., D. < 0, #
For DLNs, we can efficiently compute both optimal Box* and layerwise Box box bounds as follows:
Theorem 3.2 (Box Propagation). For an L-layer DLN f -I (h),, we obtain the box centres 1 = f(x) and the radii
E, and zl =t (n/ w(ll)e
w(t//
2
Comparing the radius computation of the optimal and layer- wise approximations, we observe that the main difference lies in where the element-wise absolute value | of the weight matrix is taken. For
the optimal box, we first multiply all weight matrices before taking the absolute value ITT W()), thus allowing for cancellations of terms of opposite signs. For the layer-wise approximation, in contrast, first take the absolute value of each weight matrix before multiplying them together Wk_lW(M thereby losing all relational information between variables. Let us now investigate under which conditions layer-wise and optimal bounds become identical.
3.2 PROPAGATION INVARIANCE AND IBP BOUND TIGHTNESS
Propagation Invariance We call a network (globally) propagation invariant (PI) if the layer- wise and optimal box over-approximations are identical for every input box. Clearly, non-negative weight matrices lead to PI networks (Lin et al.) 2022). as the absolute value in Theorem loses its effect. However, non-negative weights significantly reduce network expressiveness and performance
4

---

Published as a conference paper at ICLR 2024
(Chorowski & Zurada 2014), raising the question of whether they are necessary condition. We show that they are not, by deriving a sufficient and necessary condition for a two-layer DLN:
Lemma 3.3 (Propagation Invariance). A two-layer DLN (2)) is propagation invariant if and only if for every fixed (i,j), we have
>x 1,k W = Σx i,k W i.., either
w:B t, w 2 0 for all k or w
w(O) i,k kJj S f0 all k.
Conditions for Propagation Invariance To see how striet the condition described by Lemma 3.3 is, we observe that propagation invariance requires the sign of the last element in any two-by-two block in (22) (1)) to be determined by the signs of the other three elements:
Theorem 3.4 (Non-Propagation Invariance). Assume 3i, ,i,', such that w.G wiy w and W are all non-zero. If (W W())).s ( (()) ( (WW() (W(W)))) O. then f = (2) (1)) is not propagation invariant.
To obtain propagation invariant network with weights (2)) Raxd can thus only choose 2d 1 (c.g., one row and one column) of the of signs freely (see Corollary A.1 in App. A).
The statements of Lemma 3.3 and Theorem 3.4 naturally extend to DLNs with more than two layers L > 2. However, the conditions within Theorem 3.4 become increasingly complex and strict as more and more terms need to yield the same sign. Thus, we focus analysis L = 2 for clarity.
IBP Bound Tightness To analyze the tightness of IBP bounds for networks that do not satisfy the strict conditions for propagation invariance, we relax it to introduce propagation tightness as the ratio between the optimal and layer-wise box radii, simply referred to as rightness in this paper.
Definition 3.5. Given a DLN f. we define the global propagation tightness T as the ratio between optimal Box" (f, Bfx" 15,B(( (x)) and layer-wise Box (f. 1 (x)) approximation radius, ie.,
Intuitively, tightness measures how much smaller the exact dimension Box" " bounds are, com- pared to the layer-wish approximation Box!, thus quantifying the gap between IBP certified and true adversarial robustness. When tightness equals 1, the network is propagation invariant and can be certified exactly with IBP; when tightness is close to 0, IBP bounds become arbitrarily imprecise. We highlight that this is orthogonal to the box diameter A z z!, considered by Shi et al. (2021).
ReLU Networks The nonlinearity of ReLU networks leads to locally varying tightness and makes the computation of optimal box bounds intractable. However, for infinitesimal perturbation magnitudes the activation patterns of ReLU networks remain stable, making them locally linear. We thus introduce a local version of tightness around concrete inputs.
Definition 3.6. For an L-layer ReLU network with weight matrices W(k) and activation pattern
( (x) = 1 (0 E (0,1)*t for active and 0 for inactive ReLUs), depending on the input x, we define its local tightness as
de [z" -2")|
1 diag(d W d (z ==) (T diag (d() ((0))
c=
de
calculate tightness as the ratio of box size growth rates, evaluated for an infinitesimal input box size e. In this setting, the ReLU network will not have any unstable neurons, making our analysis exact. Only when considering larger perturbation magnitudes will neurons become unstable, making our analysis an approximation of the tightness at that However, for the networks and perturbation magnitudes typically considered in the literature, only a very small fraction ( 1%) of neurons are unstable (Müller et al.) 20226). To assess the estimation quality of our local tightness, we show its mean relative error compared to the exact tightness computed with MILP for a small CNN3 in Figure 2 for MNIST and in Figure 14 for CIFAR- 10. We find that for perturbations smaller than those used during training (e < 0.05) relative errors are extremely small (<c 0,5%), and only increase slowly after, reaching 2.2% at = 0.1.
In Definition 3.6]
15- Mean Relative Ervor [%]
0-
15 0
0.05
0.1
Figure 2: Mean relative error between local tightness (Def- inition 3.6) and true tightness computed with MILP for a CNN3 trained with PGD or IBP at e 0.05 on MNIST.
5

---

Published as a conference paper at ICLR 2024
3.3 TIGHTNESS AT INITIALIZATION
We first investigate the (expected) tightness r symmetry) at initialization, i.e. w.r.t. a weight distribution Dg. Let us consider a two-layer DLN at initialization, ie., with i.i.d. weights following a zero-mean Gaussian distribution N/ o²) with an arbitrary but fixed variance o² (Glorot & Bengio 2010 He al. 2015).
Engl= (independent of the dimension due to
Er, (3 =
Lemma 3.7 (Initialization Tightness w.n.t Width), Given a 2-layer DLN with weight matrices W Rd xdo, ( E Rd2x with i.i.d. entries from N of) and // o3) (tagether denoted as O).
we obtain the expected tightness r(d,) Ba = 2
(FT(((d)+) (
diT()d1))
Tightness at initialization, thus, decreases quickly with internal width (0( (0(
ya. 1). e.g., by a factor of (500) se 0.056 for the penultimate layer of the popular CNN7 (Gowal et al., 2018) Zhang et al. 2020 It, further, follows directly that tightness will decrease exponentially w.r.t. network depth.
Corollary 3.8 (Initialization Tightness w.r.t Depth). The expected lightness of an L-layer DLN f with minimum internal dimension dmin is at most T S T (ddmin) 4) at initialization.
This result is independent of the variance of. ... Thus, tightness at initialization can not be increased by scaling o², as proposed by Shi et al. 22021) to achieve constant box radius over network depth.
ReLU Networks We extend Lemma 3.7 to two-layer ReLU networks (Corollary A.2 in App. A
obtain an expected tightness of (2r (d1), and empirically validate it in Section 4.1
3.4 IBP TRAINING INCREASES TIGHTNESS
We now show theoretically that IBP training increases this tightness. To this end, we again consider a DLN with layer-wise propagation matrix Wt II [W() and optimal propagation matrix W
ITT W(), yielding the expected risk for IBP training as R(e) Ee,y (f, B (x)).. y).
Theorem 3.9 (IBP Training Increases Tightness). Assume homogenous tightness, i.e. W -W!,
N. T,W S
IIVoW for all i,j, then, the gradient difference between the IBP and standard W!
and
loss is aligned with an increase in lightness, i.e., (Vo(R(e) - R(O)), Vor) S for all E > O.
3.5 NETWORK WIDTH AND TIGHTNESS AFTER TRAINING
Many high- nigh-ddmensional computer vision datasets shown to have low intrinsic data dimensionality (Pope et al., 202T). Thus. we study the reconstruction loss of linear embedding into a low- dimensional subspace
proxy for performance and find that tightness decreases with the width of bottleneck layer as long as is smaller than the dita-dimensionalityy d, ie.,, w < d. Further, while reconstruction becomes lossless for points as soon the width w reaches the intrinsic dimension of the data, even optimal box propagation requires a width of at least the original data dimension d achieve loss-less reconstruction. For a k-dimensional data distribution, linearly embedded into d dimensional space with d > k, the data matrix X has a low-rank eigendecomposition Var(X) = UAUT with l non-zero eigenvalues. The optimal reconstruction X = ULU by choosing Uj as the is columns of U with non-zero eigenvalues. Yet, box propagation is imprecise:
gg X is exact
Theorem 3.10 (Box Reconstruction Error). Consider the linear embedding and reconstruction a URU of d dimensional data distribution ~ X into i dimensional space with d >>>>>> k and eigenmatrices U drawn uniformly at random from the orthogonal group. Propagating the input box B (x: layer-wise and optimally, thus, yields 15 (á:), and 135 (æ)), respectively. Then, we have, (i) E(5,/c) = ck E (kk) for a positive constant e depending solely on d and > 2 0.64 for large d: and (ii) (E /e) + V ((
r(H(+) E @(Vk).
Intuitively, Theorem 3.10 implies that, while input points can be embedded into and reconstructed from a l dimensional space losslessly, box propagation will yield box growth of e /k) for optimal and (I)) for lase propagation. However, with = d, we can choose U₂ to be an identity matrix, thus obtaining lossless "reconstruction" highlighting the importance of network width.

---

Published as a conference paper at ICLR 2024
10-6- Tightnes
Tightness
Radius Ratio
10-2.
15
Optimal
10- IBP
10-9.
10-10.
ReLU
ReLU
5-
DLN
DLN
10
2
2 Width
2
10
13
0
10 Width
20
Depth
Figure 3: Dependence of tightness at initialization on width (left)
Figure 4: Box reconstruction error over bottleneck width w.
and depth (right) for a CNN7 and CIFAR-10.
4 EMPIRICAL EVALUATION ANALYSIS
Now, we conduct an empirical study of IBP-based certified training, leveraging our novel tightness metric and specifically its local variant (see Definition 3.6) to gain a deeper understanding of these methods and confirm the applicability of our theoretical analysis to ReL.U networks. For certification, use MN-BAB (Ferrari et al. 2022), state-of-the- art verifier, and defer further details to App.
4.1 NETWORK ARCHITECTURE AND TIGHTNESS
First, we confirm the predictiveness of our theoretical results on the effect of net- work width and depth on tightness at ini- tialization and after training. In Figure 3 we visualize tightness at initialization, de- pending on network width and depth for DLNs and ReLU networks. As predicted by Lemma 3.7 and Corollary [38], tight- ness decreases polynomially with width (see Figure 3 left) and exponentially with right), and ReLU networks. We confirm our results on the inherent hardness of linear reconstruction in Figure 4 where we plot the ratio of recovered and original box radii, given a bottleneck layer of width w and synthetic data with intrinsic dimensionality k- w. As predicted by Theorem 3.10 IBP propagation yields linear and Box" sublinear growth.
Ascurncy (
Accuzzzy (%6
Tightres
Tichinme
mitred
0.85
isiiial
0.70
inzid
0.7
D.T
Depth
Widsh:
Figure Effect of network depth (top) and width (bot- tom) on tightness and training set IBP-certified accuracy.
depth (see Figure right, both for DLNs
Next, we study the interaction of network architecture and IBP training. To this end, we train CNNs with 3 to 13 layers on CIFAR-10 for 2/255, visualizing results in F To quantify the regularizing effect of propagation tightness, we report training set IBP accuracy as a measure of the goodness of fit. Generally, we would expect increased depth to increase capacity and thus decrease the robust training loss and increase training set accuracy. However, we only observe such an increase in accuracy until a depth of 7 layers before accuracy starts to drop. We can explain this by analyzing the correspond- ing tightness. As expected, tightness is high for shallow networks but decreases quickly with depth, reaching a minimum for 7 layers. From there, tightness increases again, indicating significant regularization, and thereby decreasing accuracy. This is in line with the popularity of the 7-layer CNN7 in the certified training literature (Shi
Table 1: Certified and standard accuracy depending on network width.
Danset
Mettod
Widtt
Accuracy
Cemmied
98.58
0.1
98:20
MNIST
I5P
4x
1x
97.66
97.44
93.35
93.26
03
SAUR
4%
1x
93.45
9882
93.38
93.8
IBF
2x
1x
67.93
65.06
55.85
1x
SABR
2x
62.84
CHPAR-10
IBP
2x
1x
47.35
47.83
33.95
34.17
1x
50.74
14.12
SABR
2x
$1.56
34.95
0.5x
1x
2x
25.40
et al. 2021 Müller et al.) 2022b).
TimyImageNet
SABR
11:21
Continuing our study of architecture effects, we train net-
2x
21.36
works with 0.5 to 16 times the width of standard CNN7 using IBP training and visualize the resulting IBP certified train set accuracy and tightness in Figure (left). We observe that increasing capacity via width instead of depth yields monotone although diminishing increase in accuracy as tightness decreases gradually. The different trends for width and depth agree well with our theoretical results, predicting
7

---

Published as a conference paper at ICLR 2024
Accuraty (%)
Certified Accuracy (%)
Tightness
80
80-
1.0
60-
60-
0.8
0.981
PGD
0.6-
40-
IBP
0.4-
0.085
20
SABR
20-
0.2
0
10-5
10-3
10-1
10-5
10
10-1
10
10
10
Figure 7: Tightness, standard, and certified accuracy for CNN3 on CIFAR-10, 10, depending on training method and perturbation magnitude used for training and evaluation.
that sufficient network width is essential for trained networks (see (3.orrmm3.10)) It can further be explained by the observation that increasing depth, at initialization, reduces tightness exponentially, while increasing width only reduces it polynomially. Intuitively, this suggests that less regularization is required to offset the tightness penalty of increasing network width rather than depth.
Cest. Acc.
[X]]
91
will
98.5
with
As these experiments indicate that optimal architectures for IBP- based training have only moderate depth but large width, we train wider versions of the popular CNN7 using IBP, SABR, and IBP-R, showing results in Table T and Figure 6 We observe that this width increase improves certified accuracy all settings. We note that, while these improvements might seem marginal, they are of similar magnitude as multiple years of progress on certified training methods, see Figure 6 where CROWN- C-BP (Zhang et al.) 2020) and MTL--BBP (Paima et al.) 2023) (the previous SOTA on MNIST) are shown for reference.
97
96
Std. Acc. [%6]
CROWN-IRP
SABR
IBP
MTL-IBP
Figure 6: Effect of a 4-fold width increase on certified and standard
accuracy for MNIST at e = 0.3.
4.2 CERTIFIED TRAINING INCREASES TIGHTNESS
To assess how different training methods affect tightness, we train a CNN3 on CIFAR-10 for a wide range of perturbation magnitudes (e E [10-5,5- 10-2)) using IBP, PGD, and SABR training and illustrate the resulting tightness and accuracies in Figure 7 Recall, that while IBP computes and optimizes a sound over-approximation of the worst-case loss over the whole input region. SABR propagates only a small subregion with IBP, thus yielding an unsound but generally more precise approximation of the worst-case loss. PGD, in contrast, does not use IBP at all but rather trains with samples that approximately maximize the worst-case loss. We observe that training with either IBP-based method increases tightness with perturbation magnitude until networks become almost propagation invariant with 0.98 (see Figure 7 right). This confirms our theoretical results, showing that IBP training increases tightness with (see Theorem (.9). In contrast, training with PGD barely influences tightness. Further, the regularization required for such high tightness comes at the cost of standard accuracies being severely reduced (see Figure 7 left). However, while this reduced standard accuracy translates to smaller certified accuracies for very small perturbation magnitudes (e < 5 10-3), the increased tightness improves certifiability sufficiently to yield higher certified accuracies for larger perturbation magnitudes (e 10-2).
We further investigate this dependency between (certified) robustness and tightness by varying the subselection ratio À when training with SABR. Recall that À controls the size of the propagated regions for a fixed perturbation magnitude e, recovering IBP for X = and PGD for X = 0. Plotting results in Figure 8 we observe that while decreasing X, severely reduces tightness and thus regularization, it not only leads to increasing natural but also certified accuracies until tightness falls below 7 < 0.5 at x= = 0.4. We observe similar trends when varying the regularization level for other unsound certified training methods, discussed in App. D.I In Figure 9 we vary the perturbation size e for three different and show tightness over the size of the propagation region & = de for a CNN3 and 10. Here, we observe that tightness is dominated by the size of the propagation region E and not the robustness specification c, indicating that while training with IBP-bounds increases tightness, the resulting high levels of tightness and thus regularization robustness. This helps to explain SABR's 's success and highlights the potential for developing novel certified training methods that reduce tightness while maintaining sufficient certifiability.
not generally necessary for
8

---

Published as a conference paper at ICLR 2024
Aocuracy (%)
T Tightness
Tightuess
80
0.8
75
A- (IRP)
0.6-
A= 1/4
65
Natural
Certified
0.4-
0.4-
A 1/16
60-
55
0.2
0.0
0.2
0.4
0.6
0.8
1.0
0.2
0.4
0.6
0.8
1.0
10
4 x 10 4' x 10
X
X
{ Ae
Figure 8: Accuracies and tightness of a CNN7 for CIFAR-10
Figure 9: Tightness over propa- gation region size & for SABR.
255 depending on regularization strength with SABR.
To study how certified training methods that do not use IBP- bounds at all (COLT) or only as a regularizer with very small weight (IBP-R) affect tightness, we compare tight-
Table 2: Tightness and accuracies for various training methods on CIFAR-10.
ness, certified, and standard accuracies on a 4-layer CNN (used by COLT and IBP-R) in Table 2 We observe that the orderings of tightness and accuracy are exactly inverted, highlighting the accuracy penalty of strong regularization for tightness. While both COLT and IBP-R affect much smaller increase in tightness than SABR or IBP, they still yield networks an order of magnitude tighter than PGD, suggesting that slightly increased tightness might be desir- able for certified robustness. This is further corroborated by the more heavily regularizing SABR outperforming IBP-R at larger while being outperformed at smaller
Melhod
Accuracy
Tighiness
Certiied
2/255
81.2
0.001
PGD
8/255
69.3
0.007
2/255
78.4"
0.009
60.7
COLT
8/255
51.7"
0.057
26.7
IBP-R
2/255
78.2"
0.033
62.0"
8/255
51.4"
0.124
27.9"
2/255
75.6
0,182
57.7
SABR
8/255
48.2
0.950
31.2
2/255
63.0
0.803
51.3
8/255
42.2
0.977
31.0
result.
5 RELATED WORK
Baader et al. (2020) show that continuous functions can be approximated by IBP-certifiable ReLU networks up to arbitrary precision. WWan et al. (2022b) extend this result to more activation functions and characterize the hardness of such a construction. Wang et al. (2022a) find that Ita-tiagn converges to a global optimum with high probability for sufficient width. Mirman et al. (2022) show that functions with points of non-invertibility can not be precisely approximated with IBP. Zhu et al. (2022) show that width is advantageous while depth is not for approximate average case robustness.
Shi et al. 2021 define tighmess as the size of the layerwise Box', i..., A = - =", rather than its ratio to the size the optimal box (Definition (.6)). They thus study the size of the approximation irrespective of the size of the ground truth, while we study the quality of the approximation. This leads to significantly different insights, e.g., propagation tightness remains the same under scaling of the network weights, while the abstraction size A is scaled proportionally.
Wu al. (202T) study the relation between empirical adversarial robustness and network width. They observe that in this setting, increased width actually hurts perturbation stability and thus potentially empirical robustness while improving natural accuracy. In contrast, we have shown theoretically and empirically that width is beneficial for certified robustness when training with --seed methods.
6 CONCLUSION
Motivated by the recent and surprising dominance of IBP-based certified training methods, we investigate its underlying mechanisms and trade-offs. By quantifying the relationship between IBP and optimal Box bounds with our novel propagation tightness metric, we are able to predict the influence of architecture choices on deep linear networks at initialization and after training. We experimentally confirm the applicability of these results to ReLU networks and show that wider networks improve the performance state-of-the-an methods, while deeper networks do not. Finally, we show that P-ased training methods increase propagation tightness, depending of the propagated region, at the cost of strong regularization. This observation not only helps explain the success of recent certified training methods but, in combination with the novel metric of propagation tightness, might constitute a key step towards developing novel training methods, balancing certifiability and the (over- rrgulaaraaaai resulting from propagation tightness.
the size
9

---

Published as a conference paper at ICLR 2024
REPRODUCIBILITY STATEMENT
We publish our code, trained models, and detailed instructions on how to reproduce our results at https://githhb www.ghtthbb...m comm/eth-srriippppoee proppagatpppopaatiiioooo propagation tiggtssssss Additionally, we provide detailed descriptions of all hyper-parameter choices, data sets, and preprocessing steps in App. C
ACKNOWLEDGEMENTS
We would like to thank our anonymous reviewers for their constructive comments and insightful questions.
This work has been done as part of the EU grant ELSA (European Lighthouse on Secure and Safe AI, grant agreement no. 101070617) and the SERI grant SAFEAI (Certified Safe, Fair and Robust Artificial Intelligence, contract no. (BB22.00088). Views and opinions expressed are however those of the authors only and do not necessarily reflect those of the European Union or European Commission. Neither the European Union nor the European Commission can be held responsible for them.
The work has received funding from the Swiss State Secretariat for Education, Research and Innova- tion (SERI).
10

---

Published as a conference paper at ICLR 2024
REFERENCES
Maximilian Baader, Matthew Mirman, and Martin T. Vechev. Universal approximation with certified networks. In Proc. of ICLR, 2020.
Mislav Balunovic and Martin T. Vechev. Adversarial training and provable defenses: Bridging the gap. In Proc. of ICLR. 2020.
Battista Biggio, Igino Corona, Davide Maiorca, Blaine Nelson, Nedim Smniic, Pavel Laskov, Giorgio Giacinto, and Fabio Roli. Evasion attacks against machine learning test time. Proc of ECML PKDD, volume 8190, 2013. doi: 10. 10.1007/978-3-4424409944
Christopher Brix, Mark Niklas Müller, Stanley Bak, Taylor T. Johnson, and Changliu Liu. First three years of the international verification of neural networks competition (VNN-COMP), CoRR, abs/2301 008815, 2023, doi: 10.48550/arXiv23066 .05815.
Rudy Bunel, Jingyue Lu, llker Turkaslan, Philip H. S. Torr, Pushmeet Kohli, and M. Pawan Kumar. Branch and bound for piecewise linear neural network verification. J. Mach. Learn. Res., 21, 2020.
Jan Chorowski and Jacek M Zurada. Learning understandable neural networks with nonnegative weight constraints. IEEE transactions neural networks and learning systems, 26(1), 2014. doi: 10.1
JM Cook. Rational formulae for the production of a spherically symmetric probability distribution. Mathematics of Computation, 11(58), 1957.
Francesco Croce and Matthias Hein. Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free free attacks. In Proc. of ICML, volume 119, 2020.
Claudio Ferrari, Mark Niklas Müller, Nikola Jovanovic, and Martin T. Vechev. Complete verification and-bound.....a. In Proc. of ICLR, 2022.
via multi-neuron relaxation guided
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proc. of AISTATS, volume 9, 2010.
Sven Gowal, Krishnamurthy Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Uesato, Relja Arandjelovic, Timothy A. Mann, and Pushmeet Kohli. the effectiveness of interval bound propagation for training verifiably robust models. ArXiv preprint, abs// 180./150... 2018.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-leve level performance imagenet classification. In Proc. of ICCV, 2015. doi: 10.1109/ 2015.123.
Ziwei Ji and Matus Telgarsky. Gradient descent aligns the layers of deep linear networks. In Proc. of ICLR, 2019.
Nikola Jovanović, Mislav Balunović, Maximilian Baader, and Martin Vechev. On the paradox of certified training. In Transactions on Machine Learning Research, 2022.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Yann LeCun, Corinna Cortes, and CJ Burges. Mnist handwritten digit database. ATT Labs [Online]. http://www.cu....////////m/ia/// www.ee/b/////iisrr.......m 2, 2010.
Available: http://yann.lecur
Vivian Lin, Radoslav Ivanov, James Weimer, Oleg Sokolsky, and Insup Lee. T4V: exploring neural network architectures that improve the scalability of neural network verification. In Principles of Systems Design Essays Dedicated to Thomas Henzinger on the Occasion of His 60th Birthday, volume 13660, 2022. doi: 10.
Yuhao Mao, Mark Niklas Müller, Mare Fischer, and Martin Vechev. Taps: Connecting certified and adversarial training, 2023.
George Marsaglia. Choosing a point from the surface of a sphere. The Annals of Mathematical Statistics, 43(2), 1972.
11

---

Published as a conference paper at ICLR 2024
Matthew Mirman, Timon Gehr, and Martin T. Vechev. Differentiable abstract interpretation for provably robust neural networks. In Proc. of ICML, volume 80, 2018.
Matthew B Mirman, Maximilian Baader, and Martin Vechev. The fundamental limits of neural networks for interval certified robustness. Transactions on Machine Learning Research, 2022.
ISSN 2835-8856.
Mark Niklas Müller, Christopher Brix, Stanley Bak, Changliu Liu, and Taylor T. Johnson. The third international verification of neural networks competition (VNN-COMP 2022): Summary and results. CoRR, abs/2212.10376 2022a. doi: 10.48550/arXi..2122..00
Mark Niklas Müller, Franziska Eckert, Marc Fischer, and Martin T. Vechev. Certified training: Small boxes are all you need. CoRR, 1ttb//220.04811,,2222
Mark Niklas Müller, Gleb Makarchuk, Gagandeep Singh. Markus Püschel, and Martin T. Vechev. PRIMA: general and precise neural network certification via scalable convex hull approximations.
Proc. ACM Program. Lang., 6(POPL), 2022c. doi: 10. 10.1145/3498704
Alessandro De Palma, Rudy Bunel, Krishnamurthy Dvijotham, M. Pawan Kumar, and Robert Stanforth. IBP regularization for verified adversarial robustness via branch-and-bound. ArXiv preprint, abs/2206. 14772, 2022.
Alessandro De Palma, Rudy Bunel, Krishnamurthy Dvijotham, M. Pawan Kumar, Robert Stanforth. and Alessio Lomuscio. Expressive losses for verified robustness via convex combinations. CoRR, abs/2305. 13991, 2023. doi: 10.488550/rxX1.22355.. 13991. URL. 0ttps////6l..0r/11.48550000
arXiv 2305. 13991 13991
Iosif Pinelis and Raymond Molzon. Optimal-order bounds on the rate of convergence to normality in the multivariate delta method, 2016.
Phillip Pope, Chen Zhu, Ahmed Abdelkader, Micah Goldblum, and Tom Goldstein. The intrinsic dimension of images and its impact on learning. In Proc. of ICLR, 2021.
Marco Túlio Ribeiro, Sameer Singh, and Carlos Guestrin. "why should trust you?": Explaining the predictions of any classifier. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Duta Mining, San Francisco, CA, USA, August 13-17, 2016, 2016. doi: 10.11457293967222997778.
Andrew M. Saxe, James L. McClelland, and Surya Ganguli. Exact solutions the nonlinear dynamics of learning in deep linear neural networks. In Proc. of ICLR, 2014.
Zhouxing Shi, Yihan Wang, Huan Zhang, Jinfeng Yi, and Cho-Jui Hsieh. Fast certified robust training with short warmup. In Proc. of NeurlPS, 2021.
Gagandeep Singh, Timon Gehr, Matthew Mirman, Markus Püschel, and Martin T. Vechev. Fast and effecctiee robustness certification. In Proc. of NeurIPS, 2018.
Gagandeep Singh, Rupanshu Ganvir, Markus Püschel, and Martin T. Vechev. Beyond the single neuron convex barrier for neural network certification. In Proc. of NeurlPS, 2019a.
Gagandeep Singh, Timon Gehr, Markus Püschel, and Martin T. Vechev. An abstract domain for certifying neural networks. Proc. ACM Program. Lang., 3(POLL) 2019b.
Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian J. Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In Proc. of ICLR, 2014.
Vincent Tjeng, Kai Y. Xiao, and Russ Tedrake. Evaluating robustness of neural networks with mixed integer programming. In Proc. of ICLR, 2019.
Florian Tramèr, Nicholas Carlini, Wieland Brendel, and Aleksander Madry. On adaptive attacks to adversarial example defenses. In Proc. of NeurIPS, 2020.
Dimitris Tsipras. Shibani Santurkar, Logan Engstrom, Alexander Turner, and Aleksander Madry. Robustness may be odds with accuracy. In Proc. ICLR, 2019.
12

---

Published as a conference paper at ICLR 2024
Yihan Wang, Zhouxing Shi, Quanquan Gu, and Cho-Jui Hsich. On the convergence of certified robust training with interval bound propagation. In Proc. of ICLR, 2022a.
Zi Wang, Aws Albarghouthi, Gautam Prakriya, and Somesh Jha. Interval universal approximation for neural networks. Proc. ACM Program. Lang., 6(POPL), 2022b. doi: 10.1145/3498655.
Eric Wong, Frank Schmidt, Jan Hendrik Metzen, and Zico Kolter. Scaling provable adversarial defenses. In Proc. of NeurlPS, 2018.
Boxi Wu, Jinghui Chen, Deng Cai, Xiaofei Hc, and Quanquan Gu. Do wider neural networks really help adversarial robustness? In Mare' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan (eds.), Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pp. 7054-7067, 2021. /RL/pttts///rrocceedngg.... neurips..e Abstract. html
Lei Wu, Qingcan Wang, and Chao Ma. Global convergence of gradient descent for deep linear residual networks. In Proc. of NewrlPS, 2019.
Huan Zhang, Hongge Chen, Chaowei Xiao, Sven Gowal, Robert Stanforth, Bo Li, Duane Boning, and Cho-Jui Hsich. Towards stable and efficient training of verifiably robust neural networks, In Proc. of ICLR, 2020.
Huan Zhang, Shiqi Wang, Kaidi Xu, Linyi Li, Bo Li, Suman Jana, Cho-Jui Hsieh, and J. Zico Kolter. General cutting planes for suund-rroaggation-basse neural network verification. ArXiv preprint, abs/2208.05740, 2022.
Zhenyu Zhu, Fanghui Liu, Grigorios Chrysos, and Volkan Cevher. Robustness in deep learning: The good (width), the bad (depth), and the ugly (initializa- tion). In NewrIPS, 2022. URL http::/pappers cttppper/ppppr.../ (attaaprrfflleepppprrrree files//paper22222//ash/
e55657700225022261111111431332.3 -ttp::/aaae--A-bbtttt----oooooo oacrraarreeeaattttccttcoooooonnn Conference.htmm
13

---

Published as a conference paper at ICLR 2024
A ADDITIONAL THEORETICAL RESULTS
Below we present a corollary, formalizing the intutions we provided in Section 3.2
Corollary A.I. Assume all elements of W W and W ( are non-zero and W (2) W(l) is propagation invariant. Then choosing the signs of one row and one column of W (()) fixes all signs of (22) W
Proof. For notational reasons, we define W == W()), Without loss of generality, assume we know the signs of the first row and the first column, i.e., Wi, and W., We prove via construction of the signs of all elements. The construction is given by the following: whenever Bi, J. such that we know the sign W,,,, WiJ+1 and W1+. we fix the sign of W1-1g++1 be positive if there are an odd number of positive elements among Wi.. Wi.++1 and W4115 otherwise negative.
propagation invariance requires us to fix the sign of the last element in the Wes+1,;1+1 block in this way. We only need to prove that when this process terminates, we fix the signs of all elements. We show this via recursion.
By Theorem 3.4
When i 1 and = 1, we have known the signs of W..j. Wi and W WeL1j. thus the sign of W W+15+1 is fixed. Continuing towards the right, we gradually fix the sign of 22j+1 for j 1...., d - 1. Continuing downwards, we gradually fix the sign of W1+12 for i = 1.....d ......dd- Therefore, all signs of the elements of the second row and the second column are fixed. By recursion, we would finally fix all the rows and the columns, thus the whole matrix.
We extend our result Section 3.3 to two-layer ReLU networks. The intuition is that when the input data is symmetric around zero, ReLU status (activated or not) is independent to weights and the probability of activation is exactly 0.5.
Corollary A.2. Assume the input distribution is symmetric around zero, ie., Px(x) = px (-x) for all x > O, and P(X = =) = Then for a two-layer ReLU network f = (2) (eLU(W(()))) initialized with i..dd Gaussian, the expected local tightees T' V2T, where T is the expected righmess of corresponding deep linear network.
Proof. Since the input X is symmetric around O, the distribution of ( symmetric around as well, regardless of the initialized weights. By assumption
the input and weight distribution,
P(W(1) = 0) = 0. thus P(ReLU(W(()z) = 0) 0.5. In addition, the status of activation is independent the initialized weights. Thus, the effect can be viewed as randomly setting rows of (1) to zero with probability 0.5. Following Equation (8) and Equation (9). we get that the size of Box is scaled by 0.5, and the size of Box* scaled by (VVx(((//2)/BBVXX( ~ Therefore, r' ~ /2T.
2
We perform Monte-Carlo estimation of the ratio / with two-layer fully connected network and two-layer convolutional network on MNIST. The estimation is + and respectively, which is close to the theoretical value v2 x 1.4142. This confirms the correctness of our theoretical analysis and its generalization even to convolutional networks which do not fully satisfy the assumption.
B DEFERRED PROOFS
Proof of Lemma 3.1
Here we prove Lemma 3.1 restated below for convenience.
Lemma 3.1. Any C continuous classifier f. computing the logit difference of = y, St. Vi + is robustly correct on (3x if and only if Box" (f,B(()) C RS-l i.e., of < 0, vi + t.
Proof. On the one hand, assume y; Vime < for all Then for the 7th output dimension, the optimal bounding box is max y; Vrree Since the classifier is continuous, fBB(x, E)) is closed and
14

---

Published as a conference paper at ICLR 2024
bounded set. Therefore, by extreme value theorem, Bnj B(x c) such that arg max y/ Yurue
thus max y4- Ylue < 0. Since this holds for every i, Box (f. B(x, E)) S R k-1
On the other hand, assume Box" (f. (x. e)) _ Rk-l. Since f f(B(z, e)) Box" (f. B(x, e)) S RK-1_ we get y4
Vtree < for i.
Proof of Theorem 3.2
We first prove Theorem 3.2 for 2-layer DLN Lemma B.1
Lemma B.1. For a two-layer DIN f = W() (z" - -2 |wiewww) and (zt
2 2 [
|WO)e In addition, Box" and Boxt have the same center f (xx).
Proof. First, assume W() Rd W Rd and B, 1]4, for 0, 1, where d, E Z+ are some positive integers. The input box can be represented as diag(co) co Bo + for co = e.
For single linear layer, the box propagation yields
Box(W (diag(<o) Bo + b)) = (ox( diag(eo) + +
da Σ
= diag
W [obi]]
Bi + W
diag(( ( + W
(5)
Applying Equation linear network:
iteratively, we get the explicit formula of layer-wise propagation for two-layer
Box(W (Bx(WW)))diggtl) By b]))
Box
(W(a(ddia((e)))) w()b))
d
diag
Σ
Br + (())
do
d2
diag
Σ
colil
Σ
Cw s. wayl
B2 + w(1))
(6)
Applying Equation
W (2)) (1), get the explicit formula of the tightest box:
Box (d Bo + b))
do
diag
(W (2) (1) 1cloli
B2 + B2+
do Σ
d
diag
coli]
Σ
w w/y
B2 + 112)
Now, we use induction and Lemma B. to prove Theorem 3.2 restated below for convenience. The key insight is that multi-layer DLN is equivalent to single-layer linear network. Thus, we can group layers together and view general DLNs as two-layer DLNs.
Theorem 3.2 (Box Propagation). For L-layer DLN f IIf W(k), obtain the box centres E" øl f(x) and the radii
2"
II
wiWle, and
zl zt
(II
wr(l)e
(4)
2
2
15

---

Published as a conference paper at ICLR 2024
Proof. For L 2, by Lemma B.1 the result holds. Assume for L S m, the result holds. Therefore,
for = m + 1, we group the first m layers as single layer, resulting in a "two" layer equivalent
network. Thus, (z 2²)/2 W (m++1)) R=1 W
6= [TT [ 6. Similarly, by Equation (
we can prove (z" /²//2 - (W(m+)) I w( = (m ( 6. The claim about
center follows by induction similarly.
Proof of Lemma 3.3
Here, we prove Lemma restated below for convenience.
Lemma 3.3 (Propagation Invariance). A two-layer DIN (1) is propagation invariant
if and only if for every fixed (i,j), we have
Σx w W(
kgj = Ex W ( Whib i.e., either
w w 2 for all k or (
w(())
i.k kJ S ffror all
Proof. We prove the statement via comparing the box bounds. By Lemma
B.1
we need
with E w 4, kJ
Ede
[ w The triangle incquality of absolute function says this (! w()) I 0 for all kt
f.6 AJ
holds if and only if ( k.j 2 0 for all k or
Proof of Theorem 3.4
Here, we prove Theorem 3.4. restated below for convenience.
Theorem 3.4 (Non-Propagattion Invariance). Assume 3i, J'J'', such that W w: w and W are all non-zero. If (W(2) (())) (W ( )as) ( (w())()) (w(() < 0, then f (2 (L)) is not propagation invariant.
"g"
(WW)) Proof. The assumption (w12) (()) )a3 (w(2) ((()) (W())()) w )r < 0 implies three elements are of the same sign while the other element has a different sign. Without loss of generality, assume (W()))(())
and the rest three are positive.
Assume (1() is propagation invariant. By Lemma 3.3 this means w!!) .ign .g sign, w!? sign w:() ..-- sign, W sign w.y sign and W p.. sign - (!( - sign. Therefore, we have -w()) of sign w sign, which implies all elements of (1) (yr))w))) = 0, contradiction.
. must be zero. However, this results in
Proof of Lemma 3.7
Here, we prove Lemma 3.7 restated below for convenience.
Lemma 3.7 (Initialization Tightness w.r.t. Width). Given a 2-layer DLN with weight matrices (11) Rd xdo (2) e Rd with i.i.d. entries from (0, of) and ( oι) (together denoted as 0). obtain the expected tighiness r(di) [=(x'_z") (F (
di d((())))))
Proof. We first compute the size of the layer-wisely propagated box. From Equation we get that for the i-th dimension,
do
di
B(u, - 4,) =
Σ
coli
Σ
w
1=1
da
d1
>
Goli]
j=1
1=1
dn
di Σ E(LA (113)
= 0102
colil
j=1
16

---

Published as a conference paper at ICLR 2024
Since B((A(O,,))
we have
2
B(u, 41)
o1oddd
(8)
π
Now compute the size of the tightest box. From Equation 7 get that for the i-th dimension,
E(u - (7)) = E
do
colil
Σ
d1
kJ w
= 0102 Σ
E
Σ
di
Exaral
where Xạ and Yx are i.idd standard Gaussian random variables. Using the law of total expectation, we have
E
X&Yi
E
E
Y
d2
)
E
NO
N
2 1=1
x
Yx
di
E
2
π
E( (d))
Since E( B(vx²(di)
(2 + 1))/T(
we have
E(u - 11) v 01022 (4 + +))
(9)
Combining Equation 8 and Equation 1 we have:
[(u: 1:)
(r)
(10)
E(u - 17) V ( + 1))
To see the asymptotic behavior, use [( + (x) (x)) ~ x
we have
E [4 - 4)
(11)
E(u; - 11) V
To establish the bounds on the minimum expected slackness, use Lemma B.2
() Lemma B.2. Let g(n) Val( (n+1)) g(n) monotonically increasing for n 1. Thus, for
2 2, g(n) 2 9(2) > 1.27.
Proof. Using polygamma function (2) = [=<=))(((= we have
g'(n) x 1 n
(5())
(0)
( (m++))) +1))
"https://en. hwkkii/diaarg/wwiiihhiiiiiieee distribution
thups://een wwk.peeii.oogwiii//llaaaaaaaaam function
17

---

Published as a conference paper at ICLR 2024
g(n)
g(n) squared
40000
20000
50
20000
40000
60000
80000
20000
40000
100000
Figure 10: g(n) and (2(n) visualized.
Using the fact that (2) is monotonically increasing for 2 > 0 and 2h:00) (3 + 1) (2) + we have
14 +
T1
(b)
2 72
(6:0)
[n + 1)
1
+
n2
2 11
(0)
2 +
2
= 1 +
11
2
0.
Therefore, g'(n) is strictly positive for n 2 1, and thus g(n) is monotonically increasing for 1.
As final comment, we visualize g(n) in Figure 10 As expected, g(n) is monotonically increasing in the order of ((vn).
Proof of Corollary 3.8
Here, we prove Corollary 3.8 restated below for convenience.
Corollary 3.8 (Initialization Tightness w.r.. Depth). The expected tightness of an L-layer DLN f with minimum internal dimension dini is at most S [ddmin) 1 at initialization.
Proof. This is pretty straightforward and only requires coarse application of Lemma 3.7 Without loss generality, we assume even. If L is odd, then we simply discard the slackness introduced by the last layer, i.e., assume the last layer does not introduce additional slackness.
We group the 2i 1-th and 2i-th layer as new layer. By Lemma 3.7 these I./2 subnetworks all introduce additional slackness factor of т. Note that Equation ( implies that the size of the output box is proportional to the size the input box. Therefore, the Mayer-wisely propagated box of I2 W; is 4/2 looser than the layer-wisely propagated box of L/2 (W2 W2j). In addition, the size of the tightest box for I W; is upper bounded by layer-wisely propagating 11 (W W2;).
Therefore, the minimum expected slackness is lower bounded by 44/2,
Proof Theorem 3.9
Here, we prove Theorem Theorem 3.9 (IBP Training Increases Tightness). Assume homogenous tightness, ie.. W =!
3.9
restated below for convenience.
and V. W&Will S IIVoW!lle for all i,j, then, the gradient difference between the IBP and standard
W!
loss is aligned with an increase in tightness, i.e., (Vo(R(e) R((0),, V < 0 for all > O.
Proof. We prove a stronger claim: (Vo(R(E+ Ae) - R(e)), VTT) < for all e 2 and Ae Let yields the theorem.
18

---

Published as a conference paper at ICLR 2024
R(c) Ei= R(EE + 1 A6) R(E + 1-1 Ae), thus proving the claim since each summand satisfies the theorem.
We prove the claim for De + O. For large Åc, can break it into R(e Δe)
Let L1 R(c) and L2 R(c+ Ac). By Taylor expansion, we have L2 = L + Ac A ug = L + W ug, where Vug- - Vug(u) evaluated at u = W'e. Note that the increase of would increase the risk, thus Vug 2 0.
For the 2th parameter 0, Vo, (L2 I V. = 7 T (vV W W V'Ve,TVVul
Thus, (Vo(L2 - L1). Vor) = ,2 Ac (T E, Vo,T Vo, W W (B) Vug. Since Ac > and Vug 2 0, it sufficies to prove that 7 Ei Va,T Vo, W W Vor is nonpositive, i...
OVO, Vo W)) Wij VV is nonpositive for every i.
Since | 1112 2 (ze, v), we have
VoW
1
W
2
W!}
V log W 112 2 2 log W 1l2
Vo log
11 2 2(V log w V log W*)
Therfore,
V e log 1
= Vo W log W II
V log W 11
2(V, log Wt V log W*)
I log w 2 Vo log W This means
V W. ll |orlle
Wi
thus W T 2 2 V
2 BT BT, V W which fulfills our goal.
Proof of Theorem 3.10
Here, we prove Theorem 3.10 restated below for convenience.
Theorem 3.10 (Box Reconstruction Error). Consider the linear embedding and reconstruction á URU of a d dimensional data distribution ~ X into k dimensional space with d >>> k and eigenmatrices U drawn uniformly at random from the orthogonal group. Propagating the input box 8 (x) layer-wise and optimally, thus, yields 8 (i), and B (ø), respectively. Then, we have, (i) E(d:/e) ck E (kk) for a positive constant depending solely on d and + 2 s 0.64 for large d; r((K+) E (((E).
and (ii) (E5, + VE T(2
Proof. Since box propagation for linear functions maps the center of the input box to the center of the output box, the center of the output box is exactly X. By Lemma B.1 we have |Ux||U&| e1. For notational simplicity. let V [Uk| thus
d
k
k ViS = Σ j=l
=
Σ
V1J
VT ip
VilllVll..
p=l
Therefore, /8,/c= E(V (V ck, where E(V, ([V.)]lV,yll11 Since VyJ is the absolute value of a column of the orthogonal matrix uniformly drawn, V.j itself is the absolute value of a vector drawn uniformly from the unit hyper- ball. By Cooo (9577) and Marsaglia (1972). V., is equivalent in distribution to i.i.d. draw samples from the standard Gaussian for each dimension and then normalize
it by its L2 norm. For notational simplicity, let Vi, _ v ju/. where = //|l and all dimensions of å are i.i.d. drawn from the standard Gaussian distribution, thus ((v, [|]|1)).
Expanding ||0/]1, we have c = E(of) + Ed E(vre; 1 [[(()))
+ (d 1)E(c10s) =
(d ())((r))))))))))) 02). From page 20 of Pinelis & Molzon (2016), we know each entry in converges to (0, 1/d) at O(1d)) speed in Kolmogorov distance. In addition, E(v = E(E(w, vi)
v1) = E(m / - of B(2)). where o' is the absolute value of random vector uniformly drawn from the d dimensional sphere. Therefore, for large d, (d 1)E(vr /1 -()))(
(d - (m E(v)) (d 1)E((IV(O, ( 1/d)))(((V(O, 1/(d 1))l) 3.
19

---

Published as a conference paper at ICLR 2024
0.65
2-
10a
20
40
d
k
Figure 11:
Monte-Carke estimations of Theorem 3.10 Result bases on 10000 samples for each d. Left: plotted against d in log scale. Right: (6(6)) plotted against for d 2000 (blue), together with the theoretical predictions (orange).
To show how good the asymptotic result is, we run Monte-Carlo to get the estimation of c. As shown in the left of Figure I1 the Monte-Carlo result is consistent to this theorem. In addition, it converges very quickly, e.g. stablizing at 0.64 when 2 100.
Now we start proving (2). By Lemma
B.1
we have 8
112UU k E1. Thus,
+ k
e(
Σ E Σ
Σ
E
Σ U
ip
ip
UP (d (
Σ
Unp
Un 10
j
In addition, we have
Uū )
1dE
-
Upp /p
(d -1)BB;
Bus
Σ Upp 3p
EØ= U?
)
+ (d - 1)BU,
E
W
0,
d
d-1
(d 11,
2
E
Σ
U2
(tdd 1)
p=1
2(d 1)
E
xx²(6))
(1+
((2
where we use again that for large d, the entries of column tends to Gaussian. This proves (2). The expected tightness follows by definition, i.e., dividing the result of (1) and (2).
The right of Figure 11 plots the Monte-Carlo estimations against our theoretical results. Clearly, this confirms result.
C EXPERIMENTAL DETAILS
C.I DATASET
We use the MNIST (LeCun et al., 2010) and CIFAR-10 (Krizhevsky et al.) 2009) datasets for our experiments. Both are open-source and freely available. For MNIST, we do not apply any preprocessing or data augmentation. For CIFAR-10, we normalize images with their mean and standard deviation and, during training, first apply 2-pixel zero padding and then random cropping to 32 x 32.
C.2 MODEL ARCHITECTURE
We follow previous works (Shi et al., 2021 Müller al.) 2022b Mao et al. 2023) and use 7-layer convolutional network CNN7 in most experiments. We also use simplified 3-layer convolutional network CNN3 in Section 4 Details about them can be found in the released code.
20

---

Published as a conference paper at ICLR 2024
Accuary
Tighttncss
0:55
73
70-
Natural
0.35-
Advomsriial
0.30
63
Cectilie
0.25
00
0.20
55
0.15
2
ReLUs
# Re1.Us
Figure 12: Accuracies and tightness of CNN7 for CIFAR-I0 strength with STAPS.
depending on regularization
255
C.3 TRAINING
Following previous works (Müller et al. 2022b; Mao et al. 2023). we use the initialization, warm-up regularization, and learning schedules introduced by Shi al. (202T) Specifically, for MNIST, the first 20 epochs are used for c-scheduling, increasing smoothly from 0 to the target value. Then, we train an additional 50 epochs with two learning rate decays of 0.2 at epochs 50 and 60, respectively. For CIFAR-10, we use 80 epochs for e-annealing, after training models with standard training for 1 epoch. We continue training for 80 further epochs with two learning rate decays of 0.2 at epochs 120 and 1 140, respectively. The initial learning rate is 5 x 10-3 and the gradients are clipped to an L norm at most 10.0 before every step.
C.4 CERTIFICATION
We apply MN-BAN BAB (Ferrari et al., 2022). sate-of-the-art (Brix et al. 2023 Müller et al. 2022a) verifier based on multi-neuron constraints (Müller et al.] [002cc] Singh et al. 2a) and the branch- and-bound paradigm (Bunel et al.) 2020) to certify all models. MN-BAB is a of-te-of-the-ne complete certification method built on multi -eultnn relaxations. For Table we use the same hyperparameters for MN BAB as Müller et al. (2022b) and set the timeout to 1000 seconds. For other experiments, we use the same hyperparameters but reduce timeout to 200 seconds for efficiency reasons.
D EXTENDED EMPIRICAL EVALUATION
D.1 STAPS-TRAINING AND REGULARIZATION LEVEL
To confirm our observations the interaction of regularization level, accuracies, and propagation tightness from Section 4.2 we extend our experiments to STAPS (Mao et al. 2023), an additional state-of-the-ar certified training method beyond SABR Muüller al. 2022b) p. Recall that STAPS combines SABR with ad adversarial training as follows. The model is first (conceptually) split into feature extractor and classifier. Then, during training IBP used to propagate the input region through the feature extractor yielding box bounds in the model's 's latent space. Then, adversarial training with PGD is conducted over the classifier using these box bounds as input region. As IBP leads to over-approximation while PGD leads an under-approximation, STAPS induces more regularization as fewer (ReLU) layers are included in the classifier.
We visualize the result of thus varying regularization levels by changing the number of ReLU layers in the classifier in Figure I2 We observe very similar trends as for SABR in Figure g although to a lesser extent, 0 ReLU layers in the classifier still recovers SABR and not standard IBP. Again, decreasing regularization (increasing the number of ReLU layers in the classifier) leads to reducing tightness and increasing standard and certified accuracies.
D.2 TIGHTNESS AND PROPAGATION REGION SIZE
We repeat the experiment illustrated in Figure D for CIFAR-I0 on MNIST using a CNN3 in Figure I We again observe the propagation region size dominating the tightness (except for very large perturbation sizes of e > 0.2), and smaller perturbation magnitudes leading to slightly larger tightness.
21

---

Published as a conference paper at ICLR 2024
Tightness
0.7
== (IBP)
A 1/4
0.4-
A= 1/16
0.1
10-3
4 x 10-3
42 x 10-3
{=
Figure 13: Tightness over propagation region size & for SABR and MNIST.
D.3 TIGHTNESS APPROXIMATION ERROR
Mean Relative Error [%]
To investigate the approximation quality of our local tight- ness as defined Definition 3.6 we compare it against the true tightness computed using MILP (Tieng et al. 2019). We confirm our results from Figure on MNIST on CIFAR- 10 in Figure 14 where we again observe small approxima- tion errors across a wide range of perturbation magnitudes. Interestingly, the effect of the chosen perturbation magni- tude on the approximation error is less pronounced than on MNIST, remaining low even for large perturbation magni- tudes (e = 0.01 > 8/255). While the approximation error remains below 0.3% for a D-trninddd net, our approxima- tion exhibits a consistent bias for the IBP-trained network, overestimating tightness by approximately 1.2%.
10
PGD
-10-
0.003
0.01
Figure 14: Mean relative error between local tightness (Definition (36) and true tightness computed with MILP for CNN3 trained with PGD or IBP c 0.005 on CIFAR-10.
D.4 COMPARING TIGHTNESS TO (INVERSE) ROBUST CROSS-ENTROPY Loss
To investigate to what extent our novel tightness metric is complimentary the (inverse) robust cross-entropy loss (see Section 2 computed with IBP, we repeat the key experiments confirming our theoretical insights with the inverse IBP- and observe significantly different, partially opposite
trends.
IBP Loss at Initialization We repeat our experiments on the dependence of tightness at initialization on network depth and width, illustrated F and additionally report the inverse IBP loss in Figure 15 For all experiments, we use the initialization of al. (202T which has become the de-facto standard for IBP-based training methods. While we (theoret- ically and empirically) observe an exponential reduction in tightness with increasing depth, the inverse IBP loss increases slightly. Similarly, while we (thcoretically and empirically) observe polynomial reduction in tightness with increasing width, the inverse IBP loss stays almost constant. Note the logarithmic scale (and orders of magnitude larger changed) for tightness and the linear scale for the inverse IBP loss. This difference in trend is unsurprising as the custom initialization of Shi et al. (222T) is designed to keep IBP bound width constant over network depth and width. We thus conclude that tightness and (inverse) IBP loss yield fundamentally different results and insights when analyzing networks at initialization.
Tightarss
1/IBP
10-2
10
0.3
10-15
0.2
13
Depth
Tightness
1/1BP
10-6
0.3
10-12
27
220
0.2
Width
Tightness and inverse IBP loss at initialization depending on width and depth.
Figure 15:
IBP Loss after Training We show the inverse IBP loss (left and center) and tightness (right) after IBP training depending on training perturbation size e, evaluated at training (left) or constant 10 (center) in Figure 16 We observe that inverse IBP loss, in contrast to tightness, is heavily dependent on the perturbation magnitude used for evaluation (compare left and center), making poorly suited to analyze the effects of changing perturbation magnitude. Further, when using the most natural perturbation magnitude, the e used during training and certification (left), we observe completely different trends to tightness. For very small perturbation magnitudes, the inverse IB P
22

---

Published as a conference paper at ICLR 2024
1/IBP
1/IBP
Tightness
1.0
1.0-
1.5
PGD
IBP
0.8-
0.981
1.0-
SABR
0.5
0.6
0.4
0.085
0.5
0.0
0.0
0.0
10
10
10
10-3
10
10-8
10-3
10
(a) Evaluated at training
(b) Evaluated at 6 10-3
(c) Evaluation e-independent
Figure 16: Tightness (right) and inverse IBP loss (left and center) after IBP training depending on training perturbation size evaluated at training (left) constant
10 (center).
Table 3: Certified and standard accuracy depending on network width.
Datasel
Method
Width
Accuracy
Certified
Tightness
1x
85.70
67.71
0.871
MNIST
0.1
IBP
2x
88.42
73.77
0.857
4x
90.31
79.89
0.803
loss is very high, suggesting high (perturbation) robustness, but both inverse IBP loss evaluated with larger and tightness are low, showing that it neither permits precise analysis with IBP is necessarily robust, again highlighting the difference between tightness and (inverse) IBP loss.
D.5 TIGHTNESS AFTER IBP TRAINING
To confirm that wider models improve certified accuracy while slightly reducing tightness across network architectures, also consider fully connected networks, which used to be the default in neural network verification (Singh et al.] [2019; 2018). We increase the width of a fully connected ReLU network with 6 hidden layers from 100 400 neurons and indeed observe significant increase in certified accuracy (see Table
23


Reviews:
[{"review_id": "4U90XUGY5y", "reviewer": "Reviewer_FpVR", "summary": "This paper provides theoretical analysis on IBP training and helps explain the success of IBP training over other non-IBP methods.", "questions": "1. In figure 5, why does a decreasing tightness lead to higher accuracy? If a looser bound is better due to weaker regularization, why is increasing the depth worse than increasing the width?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper gives a definition of the global and local propagation tightness which is new in the literature.\n2. Theorem 3.9 gives a pretty interesting result that IBP improves tightness by proving the alignment between gradients.", "weaknesses": "1. Some analysis in Section 4.1 is not clear, please see the questions below.\n2. What can be the potential improvement for certified training methods from your analysis?\n3. Some missing related works:\n     - [1] has a relevant conclusion on the diminishing improvement with increasing width in IBP training.\n\n[1] On the Convergence of Certified Robust Training with Interval Bound Propagation", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ckVwmKEQO3", "reviewer": "Reviewer_HbFM", "summary": "This work studies the certified training from the theoretical perspective and applies it to explain and understand the mechanism of certified training with IBP in robustness certification. The idea of propogation tightness is formulated to analyze how IBP works and extensive experiments validate the theories from different aspects, including network width and depth, tightness and accuracy, etc.", "questions": "See weakness", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The motivation of the work makes sense to me and the theory is sound, especially I like the formulation of tightness in terms of optimal box and layerwise box.\n- The paper is generally well-written and easy to read, and there are some easy examples to help the audience follow.\n- The experiments are comprehensive, which mostly validates the theory part and gives many interesting insights for certified training.", "weaknesses": "-  Although there are some examples in the introduction and formulation, the theory details lack some intuitive insights or explanations, e.g. Theorem 3.9 needs more insights to make it intuitive as it is one of the core theorems in this work.\n- The details of the experiments are not given in the main text; specifically, the datasets and models used in Fig. 3 are not clear. It is better to re-organize experiments part by adding a setup subsection for these necessary details.\n- Why is the certified accuracy decreasing when $\\epsilon$ increases in the middle figure in Fig. 7? More explanations and justifications are needed. Besides, it seems that there is no explanation of the trade-off between accuarcy and robustness as claimed in the abstract and introduction, excpet for tightness defined in the work, how about the certified robustness (e.g. certified accuracy or certifed radii) for the trade-off?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "zdpzuBcupz", "reviewer": "Reviewer_C4Wz", "summary": "This paper studies the interval bound propagation-based (IBP-based) training method, one of the most popular approaches to obtaining neural networks with certifiable guarantees. Although existing work demonstrated the effectiveness of this approach, the theoretical understanding of IBP is limited. Under the assumption of linear neural networks and Gaussian weights, this paper proposed a new measure of bound tightness and derived a few theorems to show how the bound tightness changes when propagating among linear layers, and how the width and depths of a randomly initialized network impact bound tightness.\n\nSome empirical results on a few MNIST and CIFAR-10 models demonstrate that certified training indeed improves the tightness measure proposed in this paper. Some interesting empirical results were demonstrated with models varying depths and widths, demonstrating their correlations with bound tightness and accuracy.\n\nThe paper studies an important topic with some novel results, however, its current version has some weaknesses and unresolved questions, see below, so I feel the current version of the paper is below the acceptance threshold.", "questions": "1. Figure 6 shows that increasing model width is beneficial, however, it is on a simple MNIST network. Can you demonstrate this result on larger networks and datasets? In particular, if we use a state-of-the-art method and model, and enlarge the model size by 4x, how much gain can we obtain over the state-of-the-art? Is the gain consistent over multiple models (e.g., CNN, resnet), training methods (IBP, CROWN-IBP, SABR, MTL-IBP), and datasets (CIFAR10, CIFAR100, TinyImageNet)?\n\n2. Based on Theorem 3.4, can we reparameterize the network such that the bounds are always tight, and the training process just needs to search from a subspace of weights that lead to tight bounds, rather than using gradient descent to enforce tight bounds? For L2 norm certified defense, the state-of-the-art methods use this approach (such as orthogonal convolution layers and their variants).", "limitations": "", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "1. The topic of the paper is relevant, and it is an open challenge. We still don’t understand certified training very well, and this paper is a great attempt to bring in some new understanding.\n\n2. Some novel theoretical insights are given, such as on the tightness of bound propagation and propagation invariance. Also, the growth of the bounds under initialization and its relation with model width may be a useful result to guide practical training.\n\n3. The bound propagation invariance condition may lead to new insights into the design of neural network architecture to make the bounds tighter.\n\n4. Some results are extended to a 2-layer ReLU network, although this part was not emphasized in the paper.", "weaknesses": "1. The theoretical results have strong assumptions such as linear neural networks, and neural network weights under Gaussian distribution. This is generally not a big concern if the authors can demonstrate that these theoretical insights can lead to great practical improvements, \n\n2. but here the theoretical results developed do not lead to a better model that can outperform existing approaches, and some evaluations are quite weak (e.g., on a single MNIST model only). Since only a few models and networks are shown, it is unsure how general the results are.\n\n3. Although some empirical results are shown to support the theory for ReLU networks, it is hard to argue these observations are indeed the consequence of the theory. For example, “certified training increases tightness” and “larger networks lead to better accuracy” are very generic conclusions, and it is hard to convince the readers that they result from the theory developed in this work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "SbliAA4cd3", "reviewer": "Reviewer_KaHF", "summary": "The paper introduces a notion of IBP tightness, defined as the ratio between the optimal output interval bounds and those obtained via IBP.\nA series of technical results, mostly on Deep Linear Networks (DLN) is presented, describing the requirements for perfect tightness (\"propagation invariance\") and the influence of width, depth and IBP training on tightness.\nExperimental results supporting the technical results are shown.", "questions": "The main question I had throughout the paper is: why would this notion of tightness be any more useful than measuring the standard IBP loss of a network? Tightness does not necessarily imply robustness, as IBP bounds could be very close to optimality but the network may still display adversarial examples. On the other hand, a lower IBP loss will imply robustness. For instance, the custom initialization by (Shi et al., 2021) clearly improves certified training performance (as it brings down the IBP loss at initialisation) but this is not captured by the technical results on tigthness (as stated after corollary 3.8).\nFurthermore, I am under the impression that most of the plots of the paper about tightness would apply to the (inverse of) the IBP loss too: decrease with width, depth, increase with IBP training and so on.\nI believe this should be addressed and made an integral part of the paper.", "limitations": "", "rating": 5, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 1, "strengths": "The research goal, providing further understanding to certified training and on the role of IBP in state-of-the-art methods, is of great interest to the community.\nThe paper is well-written and technical results are relatively coherent and well-structured.\nThe results detailing conditions for propagation invariance are novel and of potential interest to the community.", "weaknesses": "While the motivation is great, I am not sure this work is an actual step forward in understanding certified training.\n\nMost of the results are either fairly obvious within the certified training community (at initialisation tightness will increase with width and depth) or follow from relevant and non-cited previous work on adversarial robustness [1] (for trained networks, width will help but depth won't).\nThe authors repeatedly overclaim: I do not see why this work would \"pave the way for further advances in certified training\", or \"explain the success of recent certified training methods\". For instance, concerning the latter, the SABR paper already shows quite clearly (in its Figure 7) that strong IBP regularization is not required to obtains state-of-the-art results.\nI am also not fully convinced by the repeated arguments being made about the relevance of DLNs in this context. As it is also clear in the paper, if a network was locally linear in a perturbation region, any linear relaxation would imply exact certification. This is clearly extremely far from the networks that yield state-of-the-art certified training results, which typically require the use of branch-and-bound post-training to reach high certified accuracy (e.g., SABR).\nFinally, the presented improvements over literature results (table 1) are somewhat overstated: for SABR, the best-performing methods amongst the ones considered, they are not even necessarily a strict improvement on both standard and certified accuracy (MNIST 0.3) and they come at the cost of memory and runtime overhead. Would these result hold on different perturbation magnitudes, for instance MNIST 0.1 and CIFAR-10 8/255?\n\n[1] Robustness in deep learning: The good (width), the bad (depth), and the ugly (initialization), Zhu et al., NeurIPS 2022", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)