Certified Training: Small Boxes are All You Need
Authors: Mark Niklas Mueller
Franziska Eckert
Marc Fischer
Martin Vechev
Venue: ICLR 2023 notable top 25% (2023)
Keywords: Certified Training
Certified Robustness
Adversarial Robustness
Robustness Verification

Abstract: To obtain, deterministic guarantees of adversarial robustness, specialized training methods are used. We propose, SABR, a novel such certified training method, based on the key insight that propagating interval bounds for a small but carefully selected subset of the adversarial input region is sufficient to approximate the worst-case loss over the whole region while significantly reducing approximation errors. We show in an extensive empirical evaluation that SABR outperforms existing certified defenses in terms of both standard and certifiable accuracies across perturbation magnitudes and datasets, pointing to a new class of certified training methods promising to alleviate the robustness-accuracy trade-off.

Published as a conference paper at ICLR 2023
CERTIFIED TRAINING:
SMALL BOXES ARE ALL YOU NEED
Mark Niklas Müller; Franziska Eckert, Mare Fischer & Martin Vechev Department of Computer Science ETH Zurich, Switzerland (mark. mueller, marc. fischer, martin. wwt...eweeev....eeeee.. wet.l/.....eeeeechheeeee eckertf@student.ethe
ABSTRACT
To obtain, deterministic guarantees adversarial robustness, specialized training methods are used. We propose. SABR, novel such certified training method, based on the key insight that propagating interval bounds for a small but care- fully selected subset of the adversarial imput region is sufficient to approximate the worst-case loss over the whole region while significantly reducing approxima- tion errors. We show in an extensive empirical evaluation that SABR outperforms existing certified defenses in terms of both standard and certifiable accuracies across perturbation magnitudes and datasets, pointing new class of certified training methods promising to alleviate the robustness-accuracy trade-off.
INTRODUCTION
As neural networks are increasingly deployed in safety-critical domains, formal robustness guaran- tees against adversarial examples (Biggio al., 2013; Szegedy et al., 2014) are becoming more important. However, despite significant progress, specialized training methods that improve certifia- bility at the cost of severely reduced accuracies are still required to obtain deterministic guarantees.
Given an input region defined by an adversary specification, both training and certification methods compute network's reachable by propagating a symbolic over-approximation of this region through the network (Singh et al., 2018: 2019a; Gowal et al., 2018a). Depending on the propagation method, both the computational complexity and pagroximaaion-tighneee can vary widely. For cer- tified training, an wveraapproiimation of the worst-case loss is computed from this reachable set and then optimized (Mirman et al., 2018; Wong et al., 2018). Surprisingly, the least precise propagation precise methods induce harder optimization
methods yield the highest certified accuracies problems (Jovanovic et al., 2021). However, the large approximation errors incurred by these impre- cise methods lead to over-regularization and thus poor accuracy. Combining precise worst-case loss approximations and tractable optimization problem thus the core challenge of certified training.
In this work, tackle this challenge and propose novel certified training method, SABR. Small Adversarial Bounding Regions, based on the following key insight: by propagating small but care- fully selected subsets of the adversarial input region with imprecise methods (i.e., Box), we can obtain both well-behaved optimization problems and precise approximations of the worst-case loss. This yields less over-regularized networks, allowing SABR to improve on state-of-the-art certified defenses in terms of both standard and certified accuracies across settings, thereby pointing to new class of certified training methods.
Main Contributions Our main contributions are:
A novel certified training method, SABR, reducing over-regularization to improve both standard and certified accuracy (53).
A theoretical investigation motivating SABR by deriving new insights into the growth of Box relaxations during propagation ($4).
An extensive empirical evaluation demonstrating that SABR outperforms all state-of-the- art certified training methods in terms of both standard and certifiable accuracies on MNIST, CIFAR-10, and TINYIMAGENET ($5).
"Equal contribution

---

Published as a conference paper at ICLR 2023
2 BACKGROUND
In this section, we provide the necessary background for SABR.
Ad Adversarial Robustness Consider a classification model h: Rd + R' that, given an input æ e X' S dh predicts numerical scores y == h(x) for every class. We say that h is adversarially robust on an é--norm ball 5," (a: of radius Ep if it consistently predicts the target class t for all perturbed inputs x' E 5 (x:). More formally, we define adversarial robustness as:
arg mygmax((a')) = Va' E B (x) = (x's E x x d'lle d Ep).
(1)
Neural Network Verification To verify that a neural network h is adversarially robust, several verification techniques have been proposed.
Box Propagation
B% (xx) = [-1,
simple but effective such method is verification with the Box relaxation (Mirman et al., 2018), also called interval bound propagation (IBP) (Gowal et al., 201 8b). Conceptually, we first compute an over-approximation of network's s reachable set by propagating the input re- gion 157 (z)) through the neural network and then check whether all outputs in the reachable set yield the cor- rect classification. This propagation sequentially com- putes a hyper-box (each dimension is described as an interval) relaxation of a layer's output, given hyper- box input. As an example, consider an L-laaer net- work h- = fL o a o fL-2 .... f1. with linear lay- ers fi and ReLU activation functions a. Given an in- put region B (x). we over-approximate as a hyper- box, centered at x= == x and with radius 50 := Cp.
T1
x' T0.5, 0.3
[0.1]
x
0.2.0.5
x² +
004]
x² ReLU(x²)
0.7, 00.3
0.4
0.3, 0.7
x²
+
0.4
Figure Comparison of exact (blue) and Box (red) propagation through a one layer network. We show the concrete points maximizing the logit difference 3/2 y/1 black x and the corresponding relaxation as red x.
such that we have the hd dimension of the input x! E [=] - 88, x! + 67]. Given a linear layer (x Wx + =: x', we obtain the hyper-box relaxation of its output with centre 2t WF + b and radius 8' = [ 11-11 where . denotes the elementwise absolute value. ReL.U activation ReLU = max(0, 11 can be over-approximated by propagating the lower and upper bound separately, resulting in output hyper-box with ø' = u'tl' and 8 = w'-l' where 1' ReI.U@='11 - 5 and u² = ReI.U(x + + Proceeding this way for all layers, we obtain lower and upper bounds on the network output and can check the output score of the target class is greater than that of all other classes by computing the upper bound on the logit difference yf² == y Yt and then checking whether of²² < 0, Vi ft.
We illustrate this propagation process for one-layer network in Fig. 1. There, the blue shapes show an exact propagation of the input region and the red shapes (m) their hyper-box relaxation. Note how after the first linear and ReL.U layer (third row), the relaxation (red) contains already many points not reachable via exact propagation (blue), despite it being the smallest hyper-box containing the exact region. These so-called approximation errors accumulate quickly, leading to an increasingly imprecise abstraction, as can be seen by comparing the two shapes after an additional linear layer (last row). To verify that this network classifies all inputs in [-1, 1|2 to class 1, we have to show the upper bound of the logit difference y/2 V1 to be less than 0. While the concrete maximum of 003 2 1/2 y1 (black x) is indeed less than O, showing that the network robust, the Box relaxation only yields 0.6 2 y22 yı (red x) and is thus too imprecise to prove it.
Beyond Box, more precise verification approaches track more relational information at the cost of increased computational complexity (Palma et al., 2022; Wang et al., 2021). A recent example is MN-BAB (Ferrari et al., 2022), which improves on Box in two key ways: First, instead of propa- gating axis-aligned hyper-boxes, it uses much more expressive polyhedra, allowing linear layers to be captured exactly and ReLU layers much more precisely. Second, if the result is still too impre- cise. the verification problem is recursively split into easier ones, by introducing case distinction between the two linear segments of the ReLU function. This is called the branch-and-Be -ndu--udd (BaB) approach (Bunel et al., 2020). We refer the interested reader Ferrari et al. (2022) for more details.
2

---

Published as a conference paper at ICLR 2023
Training for Robustness For neural networks to be certifiably robust, special training is nec- essary. Given a data distribution (a, t) ~ D, standard training generally aims to find a network parametrization 0 that minimizes the expected cross-entropy loss (sce App. B.1):
add = arg min E (eollCCeeeeee)))) (z), with Cc = In (1+ Σ exp(y - v.)) (2)
ifft
When training for robustness, we, instead, wish to minimize the expected worst-case loss around the data distribution, leading to the min-max optimization problem:
Ozab = arg min ED max x'E (a)
LCE (c'(ho(ze),))
Unfortunately, solving the inner maximization problem is generally intractable. Therefore, it is commonly under- or over-approximated, yielding adversarial and certified training. respectively. For notational clarity, we henceforth drop the subscript p.
Adversarial Training Adversarial training optimizes a lower bound on the inner optimization objective in Eq. (3) by first computing concrete examples x' E 8 (ar) maximizing the loss term and then optimizing the network parameters for these samples. Typically, æ:' is computed by initializing o/ uniformly at random in (ax) and then updating it over N projected gradient descent steps (PGD) (Madry et al., 2018) x' x' = (=)) + a sign( (V=; CcE,Co (zr),),))) ( t)). with step size and projection operator II. While networks trained this way typically exhibit good empirical robustness, they remain hard to formally verify and sometimes vulnerable to stronger or different attacks (Tramèr et al., 2020; Croce & Hein, 2020).
Certified Training Certified training optimizes an upper bound on the inner maximization objec- tive in Eq. (3), obtained via bound propagation method. These methods compute upper bound Uya on the logit differences yd == y Yt. as described above, to obtain the robust cross-entropy loss LCE.ob (Br (zz),) f) LCE ( t). We will use Box to refer to the verification and propagation approach, and IBP to refer to the corresponding training method.
Surprisingly, using the imprecise Box relaxation (Mirman et al., 2018; Gowal al., 2018b; Shi et al., 2021) consistently produces better results than methods based on tighter abstractions (Zhang al., 2020; Balunovic & Vechev, 2020; Wong et al., 2018). Jovanovic et al. (2021) trace this back to the optimization problems induced by the more precise methods becoming intractable to solve. While the heavily regularized, IBP trained networks are amenable to certification, they suffer from severely reduced (standard) accuracies. Overcoming this robustness-accuracy trade-off remains a key challenge of robust machine learning.
METHOD SMALL REGIONS FOR CERTIFIED TRAINING
To train networks that are not only robust and amenable to certification but also retain compara- tively high standard accuracies, we propose the novel certified training method, SABR Small Adversarial Bounding Regions. We leverage the key insight that computing an over-approximation of the worst-case loss over a small but carefully selected subset of the input region 8 (ar) often yields a good proxy for the worst-case loss over the whole region while significantly reducing ap- proximation errors.
We illustrate this intuition in Fig. 2. Existing certified training methods always consider the whole input region (dashed box !i' in the input panel). Propagating such large regions through the network yields quickly growing approximation errors and thus very imprecise aver-approximations of the actual worst-case loss (compare the reachable set in red and green to the dashed box t: in the output panel), causing significant over-regularization (large blue arrow 4). Adversarial training methods, in contrast, only consider individual points the input space (x in Fig. 2) and often fail to capture the actual worst-case loss. This leads to insufficient regularization (small blue arrow I in the output panel) and yields networks which are not amenable to certification and potentially not robust.
We tackle this problem by propagating small, adversarially chosen subsets of the input region (solid box O in the input panel of Fig. 2), which we call the propagation region. This leads to significantly reduced approximation errors (see the solid box in the output panel) inducing a level of regular- ization in- in-between certified and adversarial training methods (medium blue arrow I), allowing us to train networks that are both robust and accurate
3

---

Published as a conference paper at ICLR 2023
Input æ
Latent Space x!
Oulput ÿ
Box relaxation
Adversarial example
incorrect
correct
Exact propagation
Figure 2: Illustration of SABR training. Instead propagating a Box approximation (dashed box ..I) of whole input region (red and green shapes in input space), SABR propagates a small subset of this region (solid box D) selected to contain the adversarial example (black x) and thus the misclassified region ( red). The smaller Box accumulates much fewer approximation errors during propagation, leading to signifieantly smaller output relaxation, which induces much less regularization (medium blue than training with the full region (large blue 1), but more than training with just the adversarial example (small blue l).
More formally, we define an auxiliary objective for the robust optimization problem Eq. (3) as
LSABR
max LCE(=", t),
(4)
xx E'E (w')
where replace the maximum over the whole input B (x) with that carefully selected subset B (ar).. While choosing x'' = -Tg-=-7 (a)) arg max (ax) Lcn (x", 1) would recover the orig- inal robust training problem (Eq. (3)), both, computing the maximum loss over given input region (Eq. (4)) and finding a point that realizes this loss is generally intractable. Instead, we instantiate SABR by combining different approximate approaches for the key components: a) a method for choosing the location x' and size of the propagation region, and b) a method used for propagating the thus selected region. Note that we thus generally do obtain a sound over-approximation of the loss on B (x). Depending on the size of the propagated region B (x'), SABR can be seen as a continuous interpolation between adversarial training for infinitesimally small regions T = 0 and standard certified training for the full input region 7 =
Selecting the Propagation Region SABR aims to find and propagate small subset of the adversarial input region B (x) that contains the inputs leading to the worst-case loss. To this end, we parametrize this propagation region l, no-m ball 13 (xx) with centre x' and radius S || x I|p- We first choose - de by scaling the original perturbation radius e with the subselection ratio À (0, 1]. We then select x' follows: We conduct PGD attack, choosing the preliminary centre x" as the sample with the highest loss. We then ensure the obtained region is fully contained in the original one by projecting x" onto B-T((>)
Figure 3: Illustration of propagation region selection process.
(x) ) to obtain x'. We show this in Fig. 3.
Propagation Method Having found the propagation region 8T (ar',, we can use any symbolic propagation method to compute over-approximation of its worst-case loss. We chose Box prop- agation (DIFFAI Mirman al. (2018) or IBP (Gowal al., 2018b)) to obtain well-behaved opti- mization problems (Jovanovic et al., 2021). There, choosing small propagation regions (7 < 1), can significantly reduce the incurred over-approximation errors, as we will show later (see $4).
UNDERSTANDING SABR: ROBUST Loss AND GROWTH OF SMALL BOXES
In this section, aim uncover the reasons behind SABR's success. Towards this, first analyse the relationship between robust loss and ver-aaproximation size before investigating the growth of the Box approximation with propagation region size.
Robust Loss Analysis Certified training typically optimizes an overaapproximation of the worst- case cross-entropy loss LCE. computed via the softmax of the upper-bound on the logit differences y y y/- When training with the Box relaxation and assuming the target class f 1, w.l.o.g., we obtain the logit difference y Ty 02 + 8d1 and thus the robust cross entropy loss
(CExb(() = In (1+
Σ
pf +66
(5)
i=2
4

---

Published as a conference paper at ICLR 2023
We observe that samples with high (> 0) worst-case misclassification margin 8 + max, Ø + V dominate the overall loss and permit the per-sample loss term to be approximated as
max Vt + 8:2 =: 3 + م < LCE. mob < In(n)) + max Df + 6.a
(6)
Further, we note that the Box relaxations of many functions preserve the box centres, i.e., x² f( Only unstable ReLUs,, i.e., ReLUU containing 0 in their input bounds, introduce slight shift. However, these empirically few in certifiably trained networks (see Table 4).
These observations allow us to decompose the robust loss into an accuracy term A correspond- ing to the misclassification margin of the adversarial example x' at the centre of the propagation region, and a robustness term 8 bounding the difference to the actual worst-case loss. These terms generally represent conflicting objectives, as local robustness requires the network to disregard high frequency features (llyas et al., 2019). Therefore, robustness and accuracy are balanced to minimize the optimization objective Eq. (5). Consequently, reducing the regularization induced by the robust- ness term will bias the optimization process towards standard accuracy. Next, we investigate how SABR reduces exactly this regularization strength, by propagating smaller regions.
Box Growth To investigate how Box approximations grow as they are propagated, let us again consider an L-layer network o fI, with linear layers fi and ReI.U
Frequency
h ft. a fr.-2 activation functions a. Given Box input with radius 56-1 and centre distribution .²-1 ~ 'D we now define the per-layer growth rate nf as the ratio of input and expected output radius:
SABR
PGD
ED101
For linear layers with weight matrix W. we obtain an output radius 8 = [ and thus a constant growth rate x², corre- sponding to the row-wise ε norm of the weight matrix [W,,-11 Empirically, we find most linear and convolutional layers to ex- hibit growth rates between 10 and 100 (see Table 9 in App. D.4).
Pre-Actittion Value
Figure 4: Input distribution last ReLUU layer depending on training method.
For ReLU layers x' (x) computing the growth rate more challenging, as it depends on the location and size of the inputs. Shi et al. (2021) assume the input Box centres - to be symmetrically distributed around 0, i.c., PD( Po(-E--1), and obtain a constant growth rate K² = 0.5. While this assumption holds initialization, trained networks tend to have more inactive than active ReLUS (see Table 4), indicating asymmetric distributions with more negative inputs (see Fig. 4).
Output Size B(ay)
actiaal
0.5
0.4
0.3
observe that
0.2
0.1
lincar
0.0
X
We now investigate this more realistic setting. We first con- sider the two limit cases where input radii 5--1 go against 0 and oc. When input radii are 8 z 0, active neurons will stay stably active, yielding 8' = 8i-1 and inactive neurons will stay stably inactive, yielding 8
0.0
0.5
1.0
1.5 2.0
Input Size 6
Figure 5: Comparison of the actual (purple) mean output size and lin- ear growth (orange) around the black x for a ReLU layer where input box centres 5 N -1.0, o...),
Thus, we obtain a growth rate, equivalent to the portion of active neurons. In the other extreme 8i-1 > 20, all neurons will become unstable with 3'-1 < 8i-1 yielding 8' x 0.5 5'-1, and thus constant growth rate x² = 0.5. To analyze the behavior in between those extremes, we assume pointwise
asymmetry favouring negative inputs, i.c., p(zi-1 -2) > p(zi-1 2), Vz E R=0 In this setting, we find that output radii grow strictly super-linear in the input size:
Theorem 4.1 (Hyper-Box Growth). Let == (x) = max(0, x) be a ReLU function and consider box inputs with radius d and asymmetrically distributed centres & ~ D such that P = -2) > Po( 2). V2 E R>0 Then, the mean output radius 8y will grow super-linearly in the input
radius 5.. More formally:
YS,, 8 R200
8' > 8z
ED[gy] > ED1dy) 18, (z)) 0s
Ep ED(o,]-
(8)
5

---

Published as a conference paper at ICLR 2023
We defer proof to App. A and illustrate this behaviour in Fig. 5 for the box centre distribution I ~ -= a =0.)). There, we clearly observe that the actual super-lineat growth (puple) outpaces a linear approximation (orange). While even the qualitative behaviour depends on the exact centre distribution and the input box size og, we can solve special cases analytically. For example, a piecewise uniform centre distribution yields quadratic growth on its support (see App. A).
Multiplying all layer-wise growth rates, we obtain the overall growth rate == k², which ex- ponential in network depth and super-linear in imput radius. When not specifically training with the Box relaxation, we empirically observe that the large growth factors of linear layers dominate the shrinking effect of the ReLU layers, leading to a quick exponential growth in network depth. Fur- ther, for both SABR and IBP trained networks, the piper-linear growth in input radius empirically manifests as exponential behaviour (see Figs. 8 and 9). Using SABR, we thus expect the regulariza- tion induced by the robustness term to decrease super-linearly, and empirically even exponentially, with subselection ratio X, explaining the significantly higher accuracies compared to IBP.
5 EVALUATION
In this section, we first compare SABR to existing certified training methods before investigating its behavior an ablation study.
Experimental Setup We implement SABR in PyTorch (Paszke et al., 2019)' and use MN-BAB (Ferrari et al., 2022) for certification. We conduct experiments on MNIST (LeCun et al., 2010), CIFAR-10 (Krizhevsky et al., 2009), and TINYIM too perturbations, using the same 7-1ayer convolutional architecture CNN7 as prior work (Shi et al., 2021) unless indicated otherwise (see App. C for more details). We choose similar training hyper- parameters as prior work (Shi et al., 2021) and provide more detailed information in App. C.
(Le & Yang, 2015) for the challenging
5.1 MAIN RESULTS
We compare SABR to state-of-the-art certified training methods in Table and Fig. 6, reporting the best results achieved with a given method on any architecture.
00.5
Oett ACc. Pt]
Cert Aoc. [8]
MNIST
54
97.3
In Fig. 6, we show certified over standard accuracy (upper right-hand corner is best) and observe that SABR (+) dom- inates all other methods, achieving both the highest certi- fied and standard accuracy across all settings. As existing methods typically perform well either at large small per- turbation radii (see Table and Fig. 6), we believe the high performance of SABR across perturbation radii be par- ticularly promising.
Sil. Aue [4]
Sod. Anc. (h)
0.1
== 0.3
Oart, Acc. 19]
36
Cert, And [S]
CIFAR-10
6-
30-
50
30
10g
50
Methods striving balance accuracy and regularization by bridging the gap between provable and adversarial training (x, (Balunovic & Vechev, 2020; Palma al., 2022) per- form only slightly worse than SABR at small perturbation radii (CIFAR-10 < = 2/255), but much worse at large radii, e.g., attaining only 27.5% (X) and 27.9% certifiable ac- curacy for CIFAR-10 10 E = 8/255 compared to 35.1% (+).
Std. Acc. (%6
Acc.
2
2255
IBP-R
COLT
CROWN-IBP
IBP
SABR
Figure 6: Certified over standard accu- racy for different certified training meth-
ods. The upper right- hand corner is best.
Similarly, methods focusing purely certified accuracy by directly optimizing over-approximmtioon of the worst-case loss (+, m (Gowal et al., 2018b; Zhang et al., 2020) tend to perform well at large perturbation radii (MNIST 0.3 and CIFAR- c 8/255), but poorly small perturbation radii, e.g. on CIFAR-10 at e = 2/255, SABR improves natural accuracy to 79.2% (+) up from 66.8% (+) and 71.5% and even more significantly certified accuracy 62.8%
up from 52.9% (+) and
54.0% (m). On the particularly challenging TINYIMAGENET, SABE again dominates all existing certified training methods, improving certified and standard accuracy by almost 3%.
To summarize, SABR improves strictly on all existing certified training methods across all com- monly used benchmarks with relative improvements exceeding 25% in some cases.
Code released https://github. cwm/eth sri/sabr

---

Published as a conference paper at ICLR 2023
Table I: Comparison of the standard (Acc.) and certified (Cert. Acc.) accuracy for different certified training methods the full MNIST, CIFAR-I0, and TINYIMAGENET test We use MN-BAB (Ferrari al., 2022)
for certification and report other results from relevant literature.
Dataset
Training Method
Source
Acc. [%]
Cert. Acc. [%]
COLT
Balunovic & Vechev (2020)
99.2
97.1
CROWN-IBP
Zhang et al. (2020)
98.83
97.76
IBP
Shi et al. (2021)
98.84
97.95
SABR
this work
99.23
98.22
MNIST
COLT
Balunovic & Vechev (2020)
97.3
85.7
CROWN-IBP
Zhang et al. (2020)
98.18
92.98
0.3
IBP
Shi et al. (2021)
97.67
93.10
SABR
work
98.75
93.40
COLT
Balunovic & Vechev (2020)
78.4
60.5
CROWN-IBP
Zhang al. (2020)
71.52
53.97
2/255
IBP
Shi et al. (2021)
66.84
52.85
IBP-R
Palma et al. (2022)
78. 19
61.97
SABR
this work
79.24
62.84
CIFAR-10
COLT
Balunovic Vechev (2020)
27.5
CROWN-IBP
Xu et al, (2020)
46.29
33.38
IBP
Shi et al. (2021)
48.94
34.97
8/255
IBP-R
Palma et al. (2022)
51.43
27.87
SABR
this work
52.38
35.13
CROWN-IBP
Shi et al. (2021)
25.62
17.93
TINYIMAGENET
1/255
IBP
Shi et al. (2021)
25.92
17.87
SABR
this work
28.85
20.46
Accuracy [%)
Accuracy [%]
Accuracy [%)
100
100
100
80
80
80
Standard
Adversarial
MN-BAB
40
40-
DeepPoly
20
20
20
Box
0.10
1.00
0.01
0.10
1.00
0.01
0.10
1.00
(a) CNN
(b) CNN7
(c) CNN7- rOW
8/253
2 /25
2/255
Figure 7: Standard, adversarial and certified accuracy depending the certification method (Box, DEEPPOLY, and MN-BAB) for the first 1000 test samples of CIFAR-10.
In contrast to certified training methods, Zhang et al. (2022b) propose SORTNET, a generalization of recent architectures (Zhang al., 2021; 2022a; Anil et al., 2019) with inherent fo -obbusttnsss properties. While SORTNET performs well at very high pertur- bation magnitudes (e = 8/255 for CIFAR- 10), it is dominated by SABR in all other settings. Further, robustness only be ob- tained against one perturbation type at a time.
Table 2: Comparison of natural (Nat.) and certified (Cert.)
accuracy [%) to SORTNET (Zhang et al., 2022b).
SORTNET
SABR (ours)
Dataset
Nat.
Cert.
Nat.
Cert.
0.1
99.01
98.14
99.23
98.22
MNIST
0.3
98.46
93.40
98.75
93.40
2/255
67.72
56.94
79.24
62.84
CIFAR-10
8/255
54.84
40.39
52.38
35.13
TINYLMAGENET
1/255
25.69
18.18
28.85
20.46
5.2 ABLATION STUDIES
Certification Method and Propagation Region Size To analyze the interaction between the pre- cision of the certification method and the size of the propagation region, we train a range of models with subselection ratios À varying from 0.0125 to 1.0 and analyze them with verification methods of increasing precision (Box, DEEPPOLY, using a 50-step PGD attack (Madry et al., 2018) with random restarts and the targeted logit mar- gin loss (Carlini & Wagner, 2017). We illustrate results in Fig. 7 and observe that standard and
Further, compute adversarial accuracies

---

Published as a conference paper at ICLR 2023
adversarial accuracies increase with decreasing X, as regularization decreases. For À = 1, ie., IBP training, we observe little difference between the verification methods. However, as we decrease X, the Box verified accuracy decreases quickly. despite Box relaxations being used during train- ing. In contrast, using the most precise method, MN-BAB, we initially observe increasing certified accuracies, as the reduced regularization yields more accurate networks, before the level of regu- larization becomes insufficient for certification. While DEEPPOLY loses precision less quickly than BOX, can not benefit from more accurate networks. This indicates that the increased accuracy, enabled by the reduced regularization, may rely on complex neuron interactions, only captured by MN-BAB. These trends hold across perturbation magnitudes (Figs. 7a and 7b) and become even more pronounced for narrower networks (Fig. 7c), which are more easily over-regularized.
This qualitatively different behavior depending on the precision of the certification method high- lights the importance of recent advances in neural network verification for certified training. Even more importantly, these results clearly show that provably robust networks do not necessarily require the level of regularization introduced by IBP training.
Loss Analysis In Fig. 8, we compare the robust loss of SABR and an IBP trained network across differ- ent propagation region sizes (all centred around the original sample) depending on the bound propagation method used. We first observe that, when propagating the full input region (A = 1), the SABR trained net- work yields much higher robust loss than the IBP trained one. However, when comparing the respective training subselection ratios, À= = 0.05 for SABR and A == 1.0 for IBP, SABR yields significantly smaller training losses. Even more importantly, the differ- ence between robust and standard loss is significantly lower, which, recalling $4, directly corresponds to a reduced regularization for robustness and allows the SABR trained network to reach a much lower stan- dard loss. Finally, we observe the losses to clearly grow super-linearly with increasing propagation region sizes (note the logarithmic scaling of the y-axis) when using the Box relaxation, agrecing well with our theoretical results in $4. While the more precise DEEPPOLY (DP) bounds yield sig- nificantly reduced robust losses for the SABR trained network, the IBP trained network does not benefit at all, again highlighting its over-regularization. See App. C for extended results.
Loss
101
Box
DP
Std
IBP
10a
SABR
0.0
0.2
0.4
0.6
0.8
1.0
Figure 8: Standard (Std.) and robust cross- entropy loss, computed with Box (Box) and DEEPPOLY (DP) for an IBP and SABR trained network over evaluation subselection ratios A.
Gradient Alignment To analyze whether SABR training is actually more aligned with standard accuracy and empirical robustness, as in- dicated by our theory in $4, we conduct the following experiment for CIFAR-10 and c = 2/ 2/255: We train one network using SABR with 0.05 and one with IBP, corresponding to À 1.0. For both, we now compute the gradients Va of their respective robust training losses Luo and the cross-entropy loss LCE applied to unperturbed (Std.) and adversarial (Adv.) samples. We then report the mean cosine similarity between these gradients across the whole test set in Table 3. We clearly observe that the SABR loss is much better aligned with both the cross- entropy loss of unperturbed and adversarial samples, corresponding to standard accuracy and empirical robustness, respectively.
Table 3: Cosine similarity between VgLno for IBP and SABR and VeLCE for ad- versarial (Adv.) and unper- turbed (Std.) examples.
Loss
IBP
SABR
Std. Adv.
0.5586
0.8071
0.8047
0.9062
ReLU Activation States The portion of ReLU acti- vations which are (stably) active, inactive, or unstable has been identified as an important characteristic of cer- tifiably trained networks (Shi et al., 2021). We evaluate these metrics for IBP, SABR, and adversarially (PGD) trained networks on CIFAR- 10 at c = 2/255, using the Box relaxation to compute intermediate bounds, and report the average over all layers and test set samples in "Table 4. We observe that, when evaluated on concrete
Table 4: Average percentage of active, inac- tive, and unstable ReI.Us for concrete points and boxes depending training method.
Point
Whole Region
Method
Act
Inact
Unst
Act
Inact
IBP
26.2
73.8
1.18
25.6
73.2
SABR PGD
35.9
64.1
3.67
34.3
62.0
36.5
63.5
65.5
15.2
19.3
8

---

Published as a conference paper at ICLR 2023
points, the SABR trained network has around 37% more active ReLUs than the IBP trained one and almost as many as the PGD trained one, indicating a significantly smaller level of regulariza- tion. While the SABR trained network has around 3-times many unstable ReLUs the IBP trained network, when evaluated on the whole input region, it has 20-times fewer than the PGD) trained one, highlighting the improved certifiability.
RELATED WORK
Verification Methods Deterministic verification methods analyse given network by using ab- stract interpretation (Gehr et al., 2018; Singh et al., 2018; 2019a), or translating the verification into an optimization problem which they then solve using linear programming (LP) (Palma al., 2021; Müller et al., 2022; Wang et al., 2021; Zhang et al., 2022c), mixed integer linear program- ming (MILP) (Tjeng et al., 2019; Singh et al., 2019b), or semidefinite programming (SDP) (Raghu- nathan et al., 2018; Dathathri et al., 2020). However, as neural network verification is generally NP-complete (Katz al., 2017), many of these methods trade precision for scalability, yielding so- called incomplete certification methods, which might fail to prove robustness even when it holds. In this work, we analyze our SABR trained networks with deterministic methods.
Certified Training DIFFAI (Mirman et al., 2018) and IBP (Gowal et al., 2018b) minimize sound over-approximation of the worst-case loss computed using the Box relaxation. Wong et al. (2018) instead use the DEEPZ relaxation (Singh et al., 2018), approximated using Cauchy random matrices. Wong & Kolter (2018) compute worst-case losses by substiittti linear bounds using fixed relavations. CROWN-IBE (Zhang et al., 2020) uses similar back-substitution approach but leverages minimal area relaxations introduced by Zhang et al. (2018) and Singh et al. (2019a) to bound the worst-case loss while computing intermediate bounds using the less precise but much faster Box relaxation. Shi et al. (2021) show that they can obtain the same accuracies with much shorter training schedules by combining IBP training with a special initialization. COLT (Balunovic & Vechev, 2020) combines propagation using the DEEPZ relaxation with adversarial search. IBP-R (Palma al., 2022) combines adversarial training with much larger perturbation radii and a ReLU- stability regularization based on the Box relaxation. We compare favorably to all (recent) methods above in our experimental evaluation (see $5). Müller al. (2021) combine certifiable and accurate networks to allow for more efficient trade-offs between robustness and accuracy.
The idea of propagating subsets of the adversarial input region has been explored in the settings of adversarial patches (Chiang et al., 2020) and geometric perturbations (Balunovic et al., 2019), where the number of subsets required to cover the whole region is linear or constant the input di- mensionality. However, these methods not applicable to the Ep-perturbation setting, consider, where this scaling exponential.
Robustness by Construction Li et al. (2019), Lécuyer al. (2019), and Cohen al. (2019) con- struct locally Lipschitz classifiers by introducing randomness into the inference process, allowing them derive probabilistic robustness guarantees. Extended in a variety of ways (Salman et al., 2019; Yang et al., 2020), these methods can obtain strong robustness guarantees with high proba- bility (Salman et al., 2019) at the cost of significantly (100x) increased runtime during inference. We focus our comparison on deterministic methods. Zhang et al. (2021) propose a novel archi- tecture, which inherently exhibits <-p-Lipschsteeess properties, allowing them to efficiently derive corresponding robustness guarantees. Zhang et al. (2022a) build on this work by improving the challenging training process. Finally, Zhang et al. (2022b) generalize this concept in SORTNET.
CONCLUSION
We introduced novel certified training method called SABR (Small Adversarial Bounding Regions) based on the key insight, that propagating small but carefully selected subsets of the input region combines small approximation errors and thus regularization with well-behaved optimization problems. This allows SABR trained networks to outperform all existing certified training methods on all commonly used benchmarks in terms of both standard and certified accuracy. Even more importantly, SABR lays the foundation for new class of certified training methods promising to alleviate the wwwssttess-accuaag trade-off and enable the training of networks that are both accurate and certifiably robust.

---

Published as a conference paper at ICLR 2023
8 ETHICS STATEMENT
As SABR improves both certified and standard accuracy compared to existing approaches, could help make real-world AI systems more robust to both malicious and random interference. Thus any positive and negative societal effects these systems have could be amplified. Further, while we achieve state-of-the-an results on all considered benchmark problems, this does not (necessarily) indicate sufficient robustness for -afety-critical real-world applications, but could give practitioners false sense of security when using SABR trained models.
REPRODUCIBILITY STATEMENT
We publish our code, all trained models, and detailed instructions on how reproduce our results https://gi thub. com/eth- com/eth-sri/sant sri/sabr, providing anonymized version to the reviewers. Further, we provide proofs for our theoretical contributions in App. and detailed description of all hyper- parameter choices as well as discussion of the used data sets including all 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 101070617) and the SERI grant SAFEAI (Certified Safe, Fair and Robust Artificial Intelligence, contract no. MB22.00088). Views and opinions expressed are however those of the authors only and do not necessarily reflect those of the European Union European Com- mission. 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 Inno- vation (SERI).
10

---

Published as a conference paper at ICLR 2023
REFERENCES
Cem Anil, James Lucas, and Roger B. Grosse. Sorting out lipschitz function approximation. In Proc. of International Conference on Machine Learning (ICML), volume 97, 2019.
Mislav Balunovic and Martin T. Vechev. Adversarial training and provable defenses: Bridging the gap. In Proc. of ICLR, 2020.
Mislav Balunovic, Maximilian Baader, Gagandeep Singh. Timon Gehr, and Martin T. Vechev. Cer- tifying geometric robustness of neural networks. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 14, 2019, Vancouver, BC, Canada, 2019.
Battista Biggio, Igino Corona, Davide Maiorca, Blaine Nelson, Nedim Srndic, Pavel Laskov, Gior- gio Giacinto, and Fabio Roli. Evasion attacks against machine learning at test time. In Machine Learning and Knowledge Discovery in Databases European Conference, ECML PKDD 2013, Prague, Czech Republic, September 23-27, 2013, Proceedings, Part III, volume 8190, 2013, doi: 10. 10.1007/978-3-66 3-642-40994-31
Rudy Bunel, Jingyue Lu, Ilker 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.
Nicholas Carlini and David A. Wagner. Towards evaluating the robustness of neural networks, In 2017 IEEE Symposium on Security and Privacy, SP 2017, San Jose, CA, USA, May 22-26, 2017 2017. doi: 10. (0.1109/SP.0017.44
Ping-
Ping-Yeh Yeh Chiang, Renkun Ni, Ahmed Abdelkader, Chen Zhu, Christoph Studer, and Tom Goldstein. Certified defenses for adversarial patches. In Proc. of ICLR, 2020.
Jeremy M. Cohen, Elan Rosenfeld, and J. Zico Kolter. Certified adversarial robustness via random- ized smoothing. In Proc. of ICMI., volume 97, 2019.
Francesco Croce and Matthias Hein. Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attacks. In Proc. of ICML, volume 119, 2020.
Sumanth Dathathri, Krishnamurthy Dvijotham, Alexey Kurakin, Aditi Raghunathan, Jonathan Ue- sato, Rudy Bunel, Shreya Shankar, Jacob Steinhardt, Ian J. Goodfellow, Percy Liang, and Pushmeet Kohli. Enabling certification of verification-agnosiic networks via memory-efficient semidefinite programming. In Advances in Neural Information Processing Systems 33: Anmual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020.
Claudio Ferrari, Mark Niklas Müller, Nikola Jovanovic, and Martin T. Vechev. Complete verification via multi-neuron relaxation guided maach-and-bound In Proc. of ICLR, 2022.
Timon Gehr, Matthew Mirman, Dana Drachsler-Colee Petar Tsankov, Swarat Chaudhuri, and Mar- tin T. Vechev. A12: safety and robustness certification neural networks with abstract interpreta- tion. In 2018 IEEE Symposium on Security and Privacy, SP 2018, Proceedings, 21-23 May 2018, San Francisco, California, USA, 2018. doi: 10. 109/SP.20188 8.00058.
Sven Gowal, Krishnamurthy Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Ue- sato, Relja Arandjelovic, Timothy Mann, and Pushmeet Kohli. On the effectiveness of interval bound propagation for training verifiably robust models. ArXiv preprint,
201 8a.
Sven Gowal, Krishnamurthy Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Ue- sato, Relja Arandjelovic, Timothy A. Mann, and Pushmeet Kohli. On the effectiveness of interval bound propagation for training verifiably robust models. ArXiv preprint, abs/ 810.11111 2018b.
Andrew Ilyas, Shibani Santurkar, Dimitris Tsipras, Logan Engstrom, Brandon Tran, and Aleksander Madry. Adversarial examples not bugs, they are features. In Advances in Neural Information Processing Systems 32: Anmual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, 2019.
11

---

Published as a conference paper at ICLR 2023
Nikola Jovanovic, Mislav Balunovie, Maximilian Baader, and Martin T. Vechev. Certified defenses: Why tighter relaxations may hurt training? ArXiv preprint, abs/2102.06700, 2021.
Guy Katz, Clark W. Barrett, David L. Dill, Kyle Julian, and Mykel J. Kochenderfer. Reluplex: An efficient SMT solver for verifying deep neural networks. ArXiv preprint, abs/1702.01135, 135, 2017.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Ya Le and Xuan S. Yang. Tiny imagenet visual recognition challenge.
7(7), 2015.
Yann LeCun, Corinna Cortes, and CJ Burges. Mnist handwritten digit database. ATT Labs [Online). Available: hilp://yannn www.n. com/exdh/mmistt 2, 2010.
Mathias Lécuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified robustness to adversarial examples with differential privacy. In 2019 IEEE Symposium on Security and Privacy, SP 2019, San Francisco, CA, USA, May 19-23, 2019, 2019. doi: 10. 109/SP.001. 00044.
Bai Li, Changyou Chen, Wenlin Wang, and Lawrence Carin. Certified adversarial robustness with additive noise. Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, 2019.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant adversarial attacks. Proc. of ICLR, 2018.
Matthew Mirman, Timon Gehr, and Martin T. Vechev. Differentiable abstract interpretation for provably robust neural networks. In Proc. of ICML, volume 80, 2018.
Mark Niklas Müller, Mislav Balunovic, and Martin T. Vechev. Certify predict: Boosting certified robustness with compositional architectures. In 9th International Conference on Learning Rep- resentations, ICLR 2021. Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021. URL https://openrevieww net teet/foruum/dcsSSaapoott
Mark Niklas Müller, Gleb Makarchuk, Gagandeep Singh, Markus Püschell and Martin T. Vechev. PRIMA: general and precise neural network certification via scalable convex hull approximations. Proc. ACM Program. Lang., 6(POPL), 2022. doi: 10. 145/3498704.
Alessandro De Palma, Harkirat Behl, Rudy R. Bunel, Philip H. Torr, and M. Pawan Kumar. Scaling the convex barrier with active sets. In Proc. of ICLR, 2021.
Alessandro De Palma, Rudy Bunel, Krishnamurthy Dvijotham, M. Pawan Kumar, and Robert Stan- forth. IBP regularization for verified adversarial robustness via maanch-and-boum ArXiv preprint, abs/2206. 1is.2206..1772,,, 2022.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Edward Yang, Zachary Vito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. Advances in Neural Information Processing Systems 32: Annual Con- ference Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, 2019.
Aditi Raghunathan. Jacob Steinhardt, and Percy Liang. Semidefinite relaxations for certifying ro- bustness to adversarial examples. In Advances in Neural Information Processing Systems 31; Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, 2018
Hadi Salman, Jerry Li, Ilya P. Razenshteyn, Pengchuan Zhang, Huan Zhang, Sébastien Bubeck, and Greg Yang. Provably robust deep learning via adversarially trained smoothed classifiers. In Ad- vances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NewrIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, 2019.
12

---

Published as a conference paper at ICLR 2023
Zhouxing Shi, Yihan Wang, Huan Zhang. Jinfeng Yi, and Cho-Jui Hsich. Fast certified robust training via better initialization and shorter warmup. ArXiv preprint, abs/2103.17668. 2021.
Gagandeep Singh, Timon Gehr, Matthew Mirman, Markus Püschel, and Martin T. Vechev. Fast and effective robustness certification. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, 2018
Gagandeep Singh, Timon Gehr, Markus Püschel, and Martin T. Vechev. An abstract domain for certifying neural networks. Proc. ACM Program. Lang., 3(POPL), 2019a. doi: 10.1 10.1145/329035.
Gagandeep Singh, Timon Gehr, Markus Püschel, and Martin T. Vechev. Boosting robustness certi- fication neural networks. In Proc. of ICLR, 2019b.
Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian J. Goodfel- low, 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. Advances in Neural Information Processing Systems 33: Annual Conference Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020.
Shiqi Wang, Huan Zhang, Kaidi Xu, Xue Lin, Suman Jana, Cho-Jui Hsieh, and J. Zico Kolter. Beta-crown: Efficient bound propagation with per-neuron split constraints for neural network robustness verification. In Advances in Neural Information Processing Systems 34: Annual Con- ference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, 2021.
Eric Wong and Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In Proc. of ICML, volume 80, 2018
Eric Wong, Frank R. Schmidt, Jan Hendrik Metzen, and J. Zico Kolter. Scaling provable adversarial defenses. In Advances in Neural Information Processing Systems 31: Annual Conference Neural Information Processing Systems 2018, NeurlPS 2018, December 3-8, 2018, Montréal, Canada, 2018.
Kaidi Xu, Zhouxing Shi, Huan Zhang, Yihan Wang, Kai-Wei Chang, Minlie Huang, Bhavya Kailkhura, Xue Lin, and Cho-Jui Hsieh. Automatic perturbation analysis for scalable certified robustness and beyond. In Advances in Neural Information Processing Systems 33: Annual Con- ference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
Greg Yang, Tony Duan, J. Edward Hu, Hadi Salman, Ilya P. Razenshteyn, and Jerry Li. Randomized smoothing of all shapes and sizes. In Proc. of ICML, volume 119, 2020.
Bohang Zhang, Tianle Cai, Zhou Lu, Di He, and Liwei Wang. Towards certifying l-infinity robust- ness using neural networks with l-inf-dist neurons. In Proc. of ICML, volume 139, 2021.
Bohang Zhang, Du Jiang, Di He, and Liwei Wang. Boosting the certified robustness of l-infinity distance nets. In Proc. of ICLR, 2022a.
Bohang Zhang, Du Jiang, He, and Liwei Wang. Rethinking lipschitz neural networks and certified robustness: A boolean function perspective. CoRR, abs/2210.017877. 2022b. doi: 10.48550/arXiv. 2210.01787. URL https://doi... www.:/...orr/111 10 wwt./////a.....x........ 2210. 017877
Huan Zhang, Tsui- Wei Weng. Pin- Yu Chen, Cho-Jui Hsieh, and Luca Daniel. Efficient neural network robustness certification with general activation functions. In Advances in Neural Infor- mation Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NewrIPS 2018, December 3-8, 2018, Montréal, Canada, 2018
13

---

Published as a conference paper at ICLR 2023
Huan Zhang, Hongge Chen, Chaowei Xiao, Sven Gowal, Robert Stanforth, Bo Li, Duane S. 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 Hsich, and J. Zico Kolter. General cutting planes for buund-ropagation-benn based neural network verification. ArXiv preprint, ttss/2008.05740 2022c.
14


Reviews:
[{"review_id": "uMgUb9lsg_J", "reviewer": "Reviewer_6kss", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes a novel training method (SABR) that creates models balancing standard and certifiable accuracy. Conceptually, SABR combines the best of adversarial training (using strong heuristic attacks as a lower bound on the worst-case loss) and certified training (using overapproximations of the adversarial output region as an upper bound on the worst-case loss). In practice, SABR enables us to retain the high accuracy provided by adversarial training while producing networks that have a high certifiable accuracy using existing verification methods.\n\nSABR uses a fast heuristic method (e.g. PGD) to find an adversarial example $x'$ within $\\epsilon$ of the input $x$. Rather than propagating the entire input ball of radius $\\epsilon$ to the output, SABR selects a ball of radius $\\lambda \\epsilon$ that 1) is contained within the original ball and 2) contains $x'$. This approach guarantees that the overapproximation from SABR 1) is contained in the overapproximation of the full adversarial input region while 2) likely contains regions of the output that are highly adversarial. While there are no theoretical guarantees that such an approach should provide any certifiable accuracy, the work demonstrates that SABR is on the Pareto frontier for standard and certifiable accuracy on $l_\\infty$ networks.", "summary_of_the_review": "The paper presents a simple idea with a sound basis and strong empirical results which the field will be able to build on. The clarity and reproducibility of the paper is outstanding and represents a clear acceptance ( the failure to compare against results from randomized smoothing notwithstanding).", "strength_and_weaknesses": "See the \"Clarity, Quality, Novelty And Reproducibility\" section below for strengths and weaknesses split by category.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "b2XyweEcl7", "reviewer": "Reviewer_mQ2H", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors propose a variant of interval bound propagation (IBP) for certified training using a small region around a preliminary center, e.g. from a PGD attack. Following a theoretical analysis of the employed box propagation, paying special attention to the role of ReLU activations, the authors present a set of experiments showing consistent improvements in terms of both the standard and robust accuracy, along with ablation studies concerning a number of related considerations.", "summary_of_the_review": "~~I'm assigning a score of 8 since 7 is no longer available.~~\nThe revised manuscript addressed my reservations.", "strength_and_weaknesses": "- Strengths\n  - Introducing an auxiliary IBP problem admitting better approximations.\n  - Theoretical analysis of hyperbox growth, with a detailed discussion of the role of ReLU activations following Shi et al. (2021).\n  - Consistently improved accuracies corroborating the theory, in addition to a valuable ablation study.\n- Weaknesses\n  - The presentation deviates from professional technical writing in a number of critical parts. This leads to unnecessary confusion, as well as a couple inaccurate or unsubstantiated claims:\n    - Improving on all SOTA methods\n    - Promising to overcome the robustness-accuracy trade-off", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "TpLYizTq3Td", "reviewer": "Reviewer_1PLc", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors propose a way to simultaneously increase both the certified and clean accuracy of certifiable networks by reducing the regularization that IBP training imposes at train time. They provide theoretical and empirical insights into why their method leads to good performance. ", "summary_of_the_review": "I think the paper presents a well-motivated method with strong results. If the authors slightly improve their presentation, I believe this paper will be of interest to the ICLR community.", "strength_and_weaknesses": "The paper has a clear motivation and is mostly well-written. The empirical results are good and the authors provide useful insights into why their method works well. The illustrations of IBP and SABR are very intuitive and helpful.\n\nHowever, their final claim is much too strong (\"Even more importantly, SABR lays the foundation for a new class of certified training methods promising to overcome the robustness-accuracy trade-off and enabling the training of networks that are both accurate and certifiably robust.\"). While it is true that their paper eases this tension, there is no reason to believe that this will lead to the elimination of the robustness-accuracy trade-off. Maybe it could be argued it would reduce the gap between certified-robustness and robustness.\n\nThe last sentence in the 2nd to last paragraph on page 3 (\"Propagating a small region centred around the thus obtained adversarial example will then also capture the point inducing the actual worst-case loss.\") is stated without justification. I am not aware of any work showing that this is true. If it exists, it should be cited. If it doesn't, then such a claim would require significant evidence.\n\nI think the authors should be slightly more clear with the fact that the SABR loss does not provide an actual upper bound on the loss, i.e. it can only be used at train time. It would be quite helpful if they provided algorithm boxes for both train and test time in the appendix.\n\nMinor points:\n- I believe the $\\epsilon$ in Figure 3 is drawn incorrectly - it should be the box's radius and not its diameter.\n- In Figure 3, there is an $x_0^*$ that is never mentioned in the text.\n- On page 5, the authors mention the typical magnitudes for growth rates in linear layers. Surely, these depend on how the model is trained? They should clarify if this holds for all training methods or only for theirs or what.\n- Figure 6 is not great. Why are there no ticks on the x and y axes? ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "RSb4aNVnunn", "reviewer": "Reviewer_Bdkn", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work tries to improve certified training based on box propagation (DiffAI) / interval bound propagation (IBP). The proposed method tries to find a point with a high loss within the perturbation region by adversarial attack. Then box propagation is performed around the high-loss input point with a small box only, in contrast to the whole perturbation region used in previous IBP works. The goal of the modification is to improve both clean accuracy and certified robust accuracy. ", "summary_of_the_review": "The method is sound and promising, and this work has demonstrated some improvement compared to previous works:\n- Better clean accuracy\n- More consistent performance across different perturbations.\n\nHowever, experiments are not convincing enough:\n- Improvement on robustness is not quite significant\n- Different methods are evaluated using verifiers with significantly different strengths\n- Slow verification at test time\n- A lack of discussion on the choice of hyperparameters.\n", "strength_and_weaknesses": "Strength:\n- This work proposes to combine adversarial attacks and box propagation / interval bound propagation such that the boxes used in box or interval bound propagation can be small.\n- There is a theoretical analysis on the growth of boxes during interval bound propagation. The derivation has considered the imbalance between active and inactive ReLU neurons, compared to a previous work assuming symmetric input to ReLU activations at initialization only. \n- Compared to existing IBP-based works, this work has consistent improvement across different eps settings. \n\nWeaknesses:\n\n- Although neither of IBP-R and IBP (Shi et al.’s version) achieve comparable performance on 2/255 and 8/255 at the same time compared to this work, this work relies on a careful choice of $\\ell_1$ and $\\lambda$ hyperparameters for each setting respectively (with values like 0.4, 0.6, 0.1, 0.7 in Table 5), while I don’t see a principled mechanism for setting these hyperparameters. It is unclear how sensitive the performance is w.r.t. different choice of hyperparameters. \n- MN-BaB (a much stronger verifier compared to IBP) is used for evaluating the models trained by this work, while previous works such as CROWN-IBP and IBP simply use IBP. Different methods in Table 1 were evaluated using different verifiers, and thus the comparison is not fair. This work spent a long time on verification (28h on CIFAR-10), while previous works using IBP at test time should be able to finish within a minute. It is unclear what the performance of previous works would be, if MN-BaB were used for those previous works (especially for CIFAR eps=2/255). \n- Compared to both IBP and IBP-R together, the improvement of the proposed work is marginal on robustness (on CIFAR 2/255, IBP-R has 78.19/61.97 clean/robust accuracy v.s. 79.52/62.57 by this work; on CIFAR 8/255, IBP (Shi et al.’s version) has 48.94/34.97 v.s. 52.00/35.25 by this work). \n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: notable-top-25%