Connecting Certified and Adversarial Training
Authors: Yuhao Mao
Mark Niklas Mueller
Marc Fischer
Martin Vechev
Venue: NeurIPS 2023 poster (2023)
Keywords: Certified Training
Certified Robustness
Adversarial Robustness
Robustness Verification
TL;DR: We combine certified and adversarial training, reducing over-regularization, and thus leading to state-of-the-art performance in certified accuracy.

Abstract: Training certifiably robust neural networks remains a notoriously hard problem.
While adversarial training optimizes under-approximations of the worst-case loss, which leads to insufficient regularization for certification, sound certified training methods, optimize loose over-approximations, leading to over-regularization and poor (standard) accuracy.
In this work, we propose TAPS, an (unsound) certified training method that combines IBP and PGD training to optimize more precise, although not necessarily sound, worst-case loss approximations, reducing over-regularization and increasing certified and standard accuracies.
Empirically, TAPS achieves a new state-of-the-art in many settings, e.g., reaching a certified accuracy of $22$% on TinyImageNet for $\ell_\infty$-perturbations with radius $\epsilon=1/255$. We make our implementation and networks public at https://github.com/eth-sri/taps.

Connecting Certified and Adversarial Training
Yuhao Mao, Mark Niklas Müller, Mare Fischer, Martin Vechev
Department of Computer Science
ETH Zurich, Switzerland (yuhao.man mao, mark. merkle, marc. fischer, martin. veriiiiveceee@@nnf.c wtw.i..ecceeeiii..eee...co
Abstract
Training certifiably robust neural networks remains notoriously hard problem. While adversarial training optimizes under-approximations of the worst-case loss, which leads to insufficient regularization for certification, sound certified training methods, optimize loose over-approximations, leading to over-regularization and poor (standard) accuracy. In this work, we propose TAPS, an (unsound) certified training method that combines IBP and PGD training to optimize more precise, although not necessarily sound, worst-case loss approximations, reducing over- regularization and increasing certified and standard accuracies. Empirically, TAPS achieves state-of-the-art in many settings, e.g., reaching certified accuracy of 22% on TINTEMAGENET for Eco-perturattions with radius e = 1/255. We make our implementation and networks public at aiggithub.... com/ eth st-ssti/taps
Introduction
Adversarial robustness, i.e., neural network's 's resilience to small input perturbations (Biggio et al.) 2013 Szegedy al. 2014), has established itself as important research area.
Neural Network Certification can rigorously prove such robustness: While complete verification
methods (Tjeng et al. 2019 Bunel al.) 2020 Zhang al. 2022a; Ferrari al. (022)) can decide
every robustness property given enough (exponential) time, incomplete methods (Wong and Kolter
2018
Singh et al. 2019a Zhang al. 2018 trade precision for scalability.
Adversarial training methods, such as PGD (Madry al. 2018), aim to improve robustness by training with samples that are perturbed to approximately maximize the training loss. This can be seen as optimizing an under-approximation of the worst-case loss. While it empirically improves robustness significantly, it generally does not induce sufficient regularization for certification and has been shown fail in the face of more powerful attacks (Tramer al. 2020).
Certified Training methods, in contrast, optimize approximations of the worst-case loss, thus increasing certified accuracies at the cost of over-regularization that leads to reduced standard accuracies. In this work, we distinguish two certified training paradigms. Sound methods (Mirman al. 2018 Gowal et al. 20118 (Sh et al. (202I) compute sound over-approximations Gowall
the worst-case loss via bound propagation. The resulting approximation errors induce a strong (over-) reegulariaiiiiionn that makes certification easy but causes severely reduced standard accuracies. Interestingly, reducing these approximation errors by using more precise bound propagation methods, empirically, results in strictly worse performance, as they induce harder optimization problems (Jovanović al.) (2022). This gave rise to unsound methods (Balunovic and Vechev 22020] Palma al. [022]] Müller al. 2022a), which aim to compute precise but not necessarily sound approximations of the worst-case loss, reducing lover)-regularizatii accuracies, but can be harder to certify. Recent advances in certification techniques, however, have made their certification practically feasible (Ferrari et al. 2022 Zhang et al.) 2022a).
and resulting in networks that achieve higher standard and certified
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

We illustrate this in Figure I where we compare certified training methods with regard to their worst- case loss approximation enrors and the resulting trade-off between certified and standard accuracy. On the left, we show histograms of the worst-case loss approximation error over test set samples (see Section 4.2 for more details). Positive values (right of the y-axis) correspond to over- and negative values (left of the y-axis) to under-approximmaioos. As expected, we observe that the sound IBP (Gowal et al., 2018) always yields over-approximations (positive values) while the unsound SABR (Müller et al. 2022a) yields more precise (6-fold reduction in mean error) but unsound approximation of the worst-case loss. Comparing the resulting accuracies (right), we observe that this more precise approximation of the actual optimization objective, i.e., the true worst-case loss, by SABR (+) yields both higher certified and standard accuracies than the over-approximation by IBP ). Intuitively. reducing the over-regularization induced by systematic underestimation of the network's 's robustness allows it to allocate more capacity to making accurate predictions.
The core challenge of effective certified training is, thus, to compute precise (small mean error and low variance) worst-case loss approximations that induce a well-behaved optimization problem.
This Work proposes Training via Adversarial Propagation through Subnetworks (TAPS), novel (unsound) certified training method tackling this chal- lenge, thereby increasing both certified and standard accuracies. Compared to SABR (+ the current state-of-the-art, TAPS (m) enjoys a further 5-fold mean approximation error reduction and significantly reduced variance (Figure [esuree[lfff Ieftt, leading to improved certified and natural accuracies (right). The key technical insight behind TAPS is to combine IBP and PGD training via gradient connector, a novel mechanism that allows training the whole network jointly such that the over-approximation of IBP and under-approximations of PGD cancel out. We demonstrate in an extensive empirical study that TAPS yields exceptionally tight worst-case loss approximations which allow it to improve on state-of-the art results for MNÍST, CIFAR-10 10, and TINYIMAGENET.
Froqueacy
Certified Aecuracy
IBP
SABR (SOTA)
Standard Ancuracy"
TAPS (ours)
IBP
SABR
0.5
0.31
0.5
TAPS
Loes Approddmation Ereor
Figure I: Histograms of the worst-case loss approxima- tion errors over the test set (left) for different training methods show that TAPS (our work) achieves the most precise approximations and highest certified accuracy (right). Results shown here are for small CNN3.
Background on Adversarial and Certified Training
Here, we provide the necessary background adversarial and certified training. We consider
a classifier F: X + y parameterized by weights I and predicting a class Ypred = =F(x) = arg max (z) for every imput x E X C Rd with label y E y = {I...., K} where f: X + RD> is a neural network, assigning a numerical logit o; f((@)) to each class i.
Adversarial Robustness We call a classifier adversarially robust on an e ball B2 c) it classifies all elements within the ball to the correct class, i.e., F(x') = y for all perturbed inputs a' E B, e). In this work, we focus on loo -rbbusttsssss with B (x. e) == {a' ||a| æ/1c0 S c} and thus drop the subscript co.
Neural Network Certification is used to formally prove robustness properties of neural network, i.., that all inputs in the region B(x,, e) yield the correct classification. We call samples where this is successfull, certifiably robust and denote the portion of such samples as certified accuracy, forming a lower bound to the true robustness of the analyzed network.
Interval bound propagation (IBP) (Mirman et al. 2018 Gowal et al. 2018) is particularly simple yet effective certification method. Conceptually, it computes an aprrxxpproinnaiion of a network's s reachable set by propagating the input region (xx,, e) through the network, before checking whether all reachable outputs yield the correct classification. This is done by, first, over-approximating the input
region B(x,, e) as Box [x:) x:") (each dimension described as an interval), centered at c = x and
with radius 5 e, such that we have the 7th dimension of the input x! E [c]] -6.45 + 50). We then

---

propagate it through the network layer-by-layer (for more details, see (Mirman et al. 2018 Gowal et al. 2018)) until we obtain upper and lower bounds (o o-| on the logit differences == 1. we can now show dimensionwise that o (except for oy 0), this proves robustness. Note that this is equivalent to showing that the maximum margin loss LMA(E', v) = maX of is less than for all perturbed inputs x' c).
Training for Robustness aims to find model parametrization 0 that minimizes the expected worst-case loss for some doss-function L:
arg min En
max ('EB(m..))
L(xr, .v)
As the inner maximization objective Equation (T) can generally not be solved exactly, it is often under- or over-approximated, giving rise adversarial and certified training, respectively.
Adversarial Training optimizes a lower bound on the inner maximization problem in Equation (I by training the network with concrete samples x' B(x e) that (approximately) maximize the loss function. A well-established method for this is Projected Gradient Descent (PGD) training (Madry al. 2018) which uses the Cross-Entropy loss Lce(#, y) = In (1 + Eity exp(J((x)) (0 Starting from a random initialization point 2o B(x,, <). performs N update steps
#n+1 1 ()) + 1) sign Vá., ((#n, v))
with step size 1) and projection operator II. Networks trained this way typically exhibit good empirical robustness but remain hard to formally certify and vulnerable to stronger or different attacks (Tramer
al. 2020 Croce and Hein 2020
Certified Training. in contrast, is used to train certifiably robust networks. this work, we distinguish classes of such methods: while sound methods optimize sound upper bound of the inner maximization objective in Equation (I). unsound methods sacrifice soundness to use an (in expectation) more precise approximation. Methods in both paradigms are often based on evaluating the cross-entropy loss LcE with upper bounds on the logit differences の².
IBP (a sound method) uses sound Box bounds the logit differences, yielding
LIsr(æ, y, c) = In (1 + Σ cxp(o;)))
(2)
SABR (an unsound method) (uüller al. 2022a), in contrast, first searches for an adversarial example x' E B(x', E-T) and then computes box-bound only for small region B(æ', r) C B(x,)) (with < E) around this adversarial example x'' instead of the original input x
LSABR
max ar' "'E((""' (c-T)
LIBp(wr' yy T).
This generally yields precise (although not sound) worst-case loss approximation, thereby reducing regulaaulaii and improving both standard and certified accuracy.
3 Precise Worst-Case Loss Approximation
In this section, we first introduce TAPS, novel certified training method combining IBP and PGD training to obtain more precise worst-case loss estimates, before showing that this approach is orthogonal and complementary to current state-of-the-ar methods.
3.1 TAPS Combining IBP and PGD
The key insight behind TAPS is that adversarial training with PGD and certified training with IBP complement each other perfectly: (i) both yield vell-behaved optimization problems, as witnessed by their empirical success, and (ii) we can combine them such that the over-approximation errors incurred during IBP are compensated by the under-approximations of PGD. TAPS harnesses this as follows: For every sample, we first propagate the input region part-way through the network using
3

---

Input
Embedding Space
Output
Box relaxation
TAPS
X
(A #3
fc
Exact propagation
2r
de
Gradient Connector
Training Loss C
Figure 2: Overview of TAPS training. First, forward propagation (->) of region B(x, e) left) around an input a (x) through the feature extractor fr yields the exact reachable set (I, middle) and its IBP approximation [z, (77, middle) in the embedding space. Further IBP propagation through the classifier fc would yield an imprecise box approximation (C3, right) of the reachable set (I, right). Instead, TAPS conducts adversarial attack (->) in the embedding space IBP approximation yielding an ander-approximation ("9) of its reachable set ( right). We illustrate the points realizing the worst-case loss in every output region with and enable back-propagation (.>) through the adversarial attack by introducing the gradient connector (discussed in Section
IBP and then conduct PGD training within the thus obtained Box approximation. The key technical challenge with this approach lies in connecting the gradients of the two propagation methods and thus enabling joint training of the corresponding network portions.
We now explain TAPS in more detail along the illustration in Figure We first partition a neural network f with weights 0 into feature extractor f& and a classifier fc with parameters 0g and 9c, respectively, such that we have fa fc o fr and F U We refer the output space of the feature extractor as the embedding space. Given an input sample æ (illustrated as in Figure and corresponding input region ((x,e) e) (IIl the input panel), training proceeds as follows: During the forward pass (black dashed arrows ->), we first use IBP to compute Box over-approximation [z, (dashed box L.) of the feature extractor's 's exact reachable set (blue region )) shown in the middle panel of Figure 2 Then,
conduct separate adversarial attacks (-) within this region in the embedding space () to bound all output dimensions of the classifier. This yields latent adversarial examples & [z, I defining the TAPS bounds T (dotted lines "": in the output space) the network's 's output. This way, the ander-approximationn of the classifier via PGD, partially compensates the over-approximation of the feature extractor via IBP. Full IBP propagation, in contrast, continues to exponentially accumulate approximation errors (Müller et al. 2002aa] Shi et al. (021), yielding the much larger dashed box [. We now compute the TAPS loss LTAPS analogously LImP (Equation (2) by plugging the TAPS bound estimate OTAPS into the Cross-Entropy loss. Comparing the resulting losses (illustrated not necessarily sound, they yield a much better approximation of the true worst-case loss.
and growing towards the top right), we see that while the TAPS bounds
During the backward pass (orange dotted arrows > in Figure 2), compute the gradients w.r.t. the classifier's 's parameters 0g and the latent adversarial examples 2 (classifier input) as usual. However, to compute the gradients w.r.t. the feature extractor's parameters θF, have compute (pseudo) gradients of the latent adversarial examples & w.r.t. the box bounds 2 and z. As these gradients not well defined, we introduce the gradient connector, discussed next, the feature extractor and classifier, imposing such pseudo gradients. This allows us to train fE and fc jointly, leading feature extractor that minimizes approximation errors and classifier that is resilient to the spurious points included in the remaining approximation errors.
interface between
3.2 Gradient Connector
The key function of the gradient connector is to enable gradient computation through the adversarial example search in the embedding space. Using the chain rule, this only requires to define the (pseudo) gradients Dz and úá of the latent adversarial examples 2 w.r.t. the box bounds z and z on DE
ds
the feature extractor's outputs. Below, we will focus on the 7th dimension of the lower box bound 2, and note that all other dimensions and the upper bounds follow analogously.
As the latent adversarial examples can be seen as multivariate functions in the box bounds, we obtain the general form dC de;
dC 0s, depending on all dimensions of the latent adversarial example. E, ds, 0z,"

---

We now consider a single PGD step and observe that bounds in the 1th dimension have no impact on the 7thh coordinate of the resulting adversarial example as they impact neither the gradient sign nor the projection in this dimension, as Box bounds are axis parallel. We thus assume independence of the jth dimension of the latent adversarial example 2 from the bounds in the 1th dimension 2; and E; (for i * j). which holds rigorously (up to initialization) for single step attack and constitutes a mild assumption for multi-step attacks. Therefore, we have 05, 0 for + j and obtain dc dC 0& Dg.
dz.
d2, ag.
leaving only ds for to define.
The most natural gradient connector is the binary connector, i.e., set dE 1 when é = and 0 otherwise, as it is valid sub-gradient for the projection operation in PGD. However, the latent adversarial input often does not lie on corner (extremal vertex) of the Box approximation, leading to sparse gradients and thus less well-behaved optimization problem. More importantly, the binary connector is very sensitive to the distance between (local) loss extrema and the box boundary and thus inherently ill-su to gradient- -ased optimization. For example, a local extremum at &; would for [ - e, 0). even for arbitrarily small
induce 0e in the box [2,, 0]. but d& 82,
22,
To alleviate both of these problems, we consider a lint- di E-r However, even ear connector, i.e., set 85, ac-z,"
1.0
0
0
when our latent adversarial example is very close to one bound, the linear connector would induce non- zero gradients w.r.t. to the opposite bound. To remedy this undesirable behavior, we propose the rectified lin- -
8%
0g
0.5
0.0 _
c
2) 3- c( 2)
ear connector, setting dz
H&s = max(0, 1
c(3,-2))
Coordinate 8
where E [0, 1] is constant (visualized in Figure ffor c= 0.3). Observe that it recovers the binary connector
Figure 3: Gradient connector visualization.
for 0 and the linear connector for = 1. To prevent gradient sparsity (c S 0.5) while avoiding the above-mentioned counterintuitive gradient connections (c 2 0.5). we set c = 0.5 unless indicated otherwise. When the upper and lower bounds are identical in the 1thh dimension, PGD turns into an
identity function. Therefore, we set both gradients to dis D& 0.5 turning the gradient connector into an identity function for the backward pass.
82, dzs
3.3
TAPS Loss & Multi-estimator PGD
The standard PGD attack, used in adversarial training, hence- forth called single-estimator PGD, is based on maximizing the Eross-Entropy loss LCE of a single input. In the context of TAPS, this results in the overall loss
LTAPS
o
csingle TTPPS (x. v,6) max In (1+) Σ exp(Jc(3):-(c(3))) 2E(2.=]
single TAPS
where the embedding space bounding box [z. x] is obtained via IBP. However, this loss is not necessarily well aligned with adversarial robustness. Consider the example illustrated in Figure 4 where only points in the lower-left quadrant are classified correctly (i.e., of == O Og < 0). We compute the latent adversarial example 2 by conducting a standard adversarial attack on the Cross-Entropy loss over the reachable set (optimally for illustration purposes) and observe that the corresponding output f(2 (x) is classified correctly. However, if we instead use the logit differences of and o attack objectives, we obtain two misclassified points (x). Combining their dimension- wise worst-case bounds ("), we obtain the point *, which realizes the maximum loss over an optimal box approximation of the reachable set. As the correct classification of this point (when computed exactly) directly corresponds to true robustness, we propose the multi-estimaato PGD variant of LTAPS, which estimates the upper bounds on the logit differences of using separate samples and then computes the loss function using the per-dimension worst-cases as:
Figure 4: Illustration of the bounds
on of 0; Or obtained via single estimator (- and multi-estimator (")) PGD and the points maximiz- ing the corresponding losses: x for Chimple and for LAPPS-
CTAPS (x, y, E) In (1 + Σ exp
max fc(2), -f(())))) $E[x,*]
isy
5

---

3.4 Training Objective & Regularization
While complete certification methods can decide any robustness property, this requires exponential time. Therefore, networks should not only be robust but also certifiable. Thus, we propose to combine the IBP loss for easy-to-learn and certify samples with the TAPS loss for harder samples as follows:
L(x, y, E) LTAPS x y, LIBP( (æ, y,e).
This expresses that every sample should be either certifiable with TAPS or IBP bound 1 by construction LTAPS LIBP, we add scaling term the loss gradient:
Further, as
dC = 2a
dLTAPS LIBP + (a) dLIBP d0
-TTPS
d0
d0
Here, a = 0.5 recovers the standard gradient, obtained via the product rule (both sides weighted with 1), while a and respectively. Henceforth, we express this as the regularization weight WTAPS = I-a which intuitively expresses the weight put on TAPS, using WTAPS = 5 unless specified otherwise. Lastly, we reduce the variance of by averaging LIPP and CTAPS over mini batch before multiplying (see App. AA.
correspond to using only the (weighted) IBP and TAPS gradients,
3.5 STAPS BBalancing Regularization by Combining TAPS with SABR
Recall that SABR (Müller et al.) 2022a) reduces the over-regularrzzttoon of certified training by propagating small, adversarially selected Box through the whole network. However, Box approximations grow exponentially with depth (Müller et al., 2022a Shi et al., 2021 Mao et al.) 2023), regardless of the input region size, SABR has to strike balance between regularizing early layers too little and later layers too much. In contrast, TAPS's approach of propagating the full input region through the first part of the network (the feature extractor) before using PGD for the remainder reduces regularization only in later layers. Thus, we propose STAPS by replacing the IBP components of TAPS, for both propagation and regularization, with SABR to obtain more uniform reduction of over-regularization throughout the whole network.
STAPS, identically to SABR, first conducts a PGD attack the whole network to find an adversarial example x' E (5(x'cc-7), Then, it propagates Box-bounds for small region B(x', T) C B(x, <) (with < <) around this adversarial example æ' through the feature extractor, before, identically to TAPS, conducting an adversarial attack in the resulting latent-space region over the classifier component of the network.
4 Experimental Evaluation
In this section, we evaluate TAPS empirically, first, comparing it to range of state-of-the-an certified training methods, before conducting an extensive ablation study validating our design choices.
Experimental Setup rari al. (022) for certification. We conduct experiments on MNIST (LeCun et al.) 2010). CIFAR- 10 Krizhevsky et al. 2009), and TINY IMGENNT (Le and Yang 2015) using for perturbations and the CNN7 architecture (Gowal al., 2018). For more experimental details including hyperparameters and computational costs and an extended analysis see App. B and App. C respectively.
We implement TAPS in PyTorch Paszke et al. 2019) and use MN-BAB Fer
4.1 Main Results
In Table 1. compare TAPS to state-of-the-arr certified training methods. Most closely related are IBP, recovered by TAPS the classifier size is zero, and COLT, which also combines bound propagation with adversarial attacks but does not allow for joint training. TAPS dominates IBP. improving on its certified and natural accuracy in all settings and demonstrating the importance of avoiding over-regularization Compared COLT, TAPS improves certified accuracies significantly. highlighting the importance of joint optimization. In some settings, this comes at the cost of slightly reduced natural accuracy. potentially due to COLT's use of the more precise ZONOTOPE approxima- tions. Compared to the recent SABR and IBP-R, TAPS often achieves higher certified accuracies at
See Fischer et al. 2019) for further discussion.

---

Table I: Comparison of natural (Nat.) and certified (Cert.) accuracy the full MNIST, CIFAR-10 10.
and TINGEMAGENET test sets. We report results for other methods from the relevant literature.
Dataset
Training Method
Source
Nat. [%]
Cort. [%c
COLT
Balunovic and Vechev 2020
99.2
97.1
IBP
98.84
97,95
SORINET
2 Daang el al 2022b
99.01
98.14
0.1
SABR
98.22
TAPS
Luu
99.19
98.39
MNIST
STAPS
this work
99.15
98.37
COLT
Balunovic Vechev
2020
97.3
85.7
IBP
Shi el al.
2121
97.67
93. 10
SORTNET
Zhang al. 20222
0.3
SABR
Muller of al
20224
98.75
93.40
TAPS
Lids work
97.94
93.62
STAPS
this work
98.53
93.51
COLT
Balunovic and Vechey
2020
78.4
60.5
IBP
SBi 20
2024
66.84
52.85
SORINET
2
Ziang a
67.72
56,94
IBP-R
Palma el 2022
78.19
61.97
255
SABR
Müller
79.24
62.84
TAPS
Cnis work
75.09
61.56
STAPS
this work
79.76
62.98
CIFAR-10 10
COLT
Balunovic and Vechev 2020
51.7
27.5
IBP
Sli et a..
2021
48.94
34,97
SORTNET
7han
21222h
54.84
401.99
IBP-R
Farmu el
2022
51.43
27.87
255
SABR
TAPS
this work
49,76
35. 10
STAPS
this work
52.82
34.65
IBP
Shi al. 2021
25.92
17.87
SORTNET
Zhane el ml 2022b
25.69
18.18
TINYIMAGENET
SABR
20.46
255
TAPS
This work
28.34
20.82
STAPS
this work
28.98
22.16
the cost of slightly reduced natural accuracies. Reducing regularization more uniformly with STAPS achieves higher certified accuracies in almost all settings and better natural accuracies in many. further highlighting the orthogonality of TAPS and SABR. Most notably, STAPS increases certified accuracy on TINYIMAGENET by almost 10% while also improving natural accuracy. SORTNET, generalization of a range of recent architectures (Zhang et al. 2021 2022c Anil et al. 2019). introducing novel activation functions tailored to yield networks with high foe robustness, performs well on CIFAR- 10 at 8/ 8/255, but is dominated by STAPS in every other setting.
4.2 Ablation Study
Approximation Precision To evaluate whether TAPS yields more precise approximations of the worst-case loss than other certified training meth- ods, we compute approximations of the maximum margin loss with IBP, PGD (50 steps, restarts), SABR (A = 0.4). and TAPS on a small TAPS- trained CNN3 for all MNIST test set samples. We report histograms over the difference to the exact worst-case loss computed with a MILP encoding (Tjeng et al., 2019) in Figure 5 Positive values correspond to over-approximationn while negative values correspond to under-approximation We observe that the TAPS approximation is by far the most precise, achieving the smallest mean and mean absolute error as well as variance. We con- firm these observations for other training methods in Figure in App.
Prequeey
IBP
TXPS
0.0 Figure Distribution of the worst-case loss ap- proximation errors over test set samples.
0.5
3.0
Approsimation Eroo
Proguesey
Prequcey
ISP SABR
TAPS
STAPS
0.5
0.
TAPS
STAPS SABR
(a) TAPS
(b) STAPS
To isolate the under-approximmaion effect of the PGD propagation through the classifier, we visu-
Figure 6: Bound difference between IBP and PGD propagation through the classifier depend- ing the training method.
alize the distribution over pairwise bound differ-
7

---

ences between TAPS and IBP and STAPS and SABR in Figure for different training methods. We observe that the distributions for TAPS and STAPS are remarkably similar (up to scaling), highlighting the importance of reducing over-regularisation of the later layers, even when propa- gating only small regions (SAR//TAPS) Further, we note that larger bound differences indicate reduced regularisation of the later network layers. We thus observe that SABR still induces much stronger regularisation of the later layers than TAPS and especially STAPS, again highlighting the complementarity of TAPS and SABR, discussed in Section 3.5
IBP Regularization To analyze the ef- fectiveness of the multiplicative IBP reg-
Table Effect of IBP regularization and the TAPS
gradient expanding coefficient for MNIST 0.3.
ularization discussed in Section 3.4 we
train with IBP in isolation (LIBP) IBP
WTAPS
Avg time (s)
Nat (%)
Adv. (%)
Cert. (%)
with TAPS weighted gradients (WrAPs =
Lirr 0
2.3
97.6
93.37
93.15
0), varying levels of gradient scaling for
2.7
97.37
93.32
93.06
the TAPS component (WTAPS E 20). TAPS with IBP weighting (WTAPS = oo), and TAPS loss in isolation, reporting re- sults in Table We observe that IBP isolation yields comparatively low standard but moderate certified accuracies with fast certification times. Increasing the weight WTAPS of the TAPS gradients reduces regu- larization, leading to longer certification times and higher standard accuracies. Initially, this translates to higher adversarial and certified accuracies, peaking at WTAPS = 15 and WTAPS 5, respectively, before especially certified accuracy decreases regularization becomes insufficient for certification. We confirm these trends for TINYÍMAGENET in Table 14 in App.
4.5
97.86
93.80
93.36
6.9
97.94
94.01
93.62
15.7
98.25
94.43
93.02
15t
42.8
98.53
95.00
91.55
20
73.7
98.75
94.33
82.67
oct
569.7
98.0
94.00
45.00
CTAPS
817.1
98.5
94.50
17.50
Only evaluated on part of the test set within a 2-day time limit.
Split Location TAPS splits given network into feature extractor and classifier, which are then approximated using IBP and PGD, respectively. As IBP propagation accumu- lates over-approximation errors while PGD an under-approximation, the location of this split has the
Accuracy [%]
Accurac [%]
80
60
Standard
60
50-
Adversarial
40
MN-BAB
40
30
CROWN-IBP
IBP
20
3
3
6
#ReLU Classifier
#ReLU in Classifier
(a) 2/255
(b) c 8/255
Figure 7: Effect of split location on the standard and robust accuracy of TAPS trained networks, depending the perturbation magnitude for different certification methods for CIFAR-10. O ReLUs the classifier recovers IBP training.
strong impact regularization level induced by TAPS. To analyze this effect, we train multiple CNN7S such that obtain classifier components with between 0 and 6 (all) ReLU layers and illustrate the resulting standard, adversarial, and certified (using different methods) accuracies in Figure 7 for CIFAR-10. 10. and in App. forr MNIST and TINY in Tables and respectively.
For small perturbations (e = 2/ 2/255), increasing classifier size and thus decreasing regularization yields increasing natural and adversarial accuracy. While the precise MN-BAB verification can translate this to rising certified accuracies up to large classifier sizes, regularization quickly becomes insufficient for the less precise IBP and CROWN-IBP certification. For larger perturbations (c= 8/255), the behavior is more complex. An initial increase of all accuracies with classifier size is followed by sudden drop and slow recovery, with certified accuracies remaining below the level achieved for ReLU layer. We hypothesize that this effect is due to the IBP regularization starting to dominate optimization combined with increased training difficulty (see App. App.Cfor Cfor details). For both perturbation magnitudes, gains in certified accuracy can only be realized with the precise certification (Müller et al. (002aa). highlighting the importance of recent developments in neural network verification for certified training.

---

Gradient Connector In Figure 8 we illustrate the effect of our gradient connector's parameterization (Section 3.2). We report TAPS accuracy (the portion of samples where all latent adversarial examples are classified correctly) as proxy for the goodness of fit. Recall that c = 0 corresponds to the binary connector and с 1 to the linear connector. We observe that the binary connector achieves poor TAPS and natural accuracy, indicating a less well-behaved optimization problem. TAPS accuracy peaks at c = 0.5, indicating high goodness-offfit and thus well-behaved optimization problem. This agrees well with our theoretical considerations aiming to avoid sparsity (c < 0.5) and contradicting gradients (c > 0.5).
TAPS Accurncy [X]
Natural Actuaayy 1%
57-
72-
70
55-
68-
59
00-
0
0:25
11.5
0.75
0.22
0.5
0.75
1
Figure 8: Effect of the gradient connector on TAPS (left) and natural (right) accuracy.
Single-Estimator Multi- Estimator PGD To evaluate the importance of our multi-estimator PGD variant, we compare to single-estimator PGD across a range of split positions, report- ing results in Table 3 We observe that across all split positions, multi-cstimator PGD achieves better certified and better or equal natural accu- racy. Further, training collapses reproducibly for single-estimator PGD for small classifiers, in- dicating that multi-estimate PGD additionally improves training stability.
Comparison of single- and multi- estimator PGD, depending on the split position for MNIST at 0.3.
Table 3:
ReLU in Classifier
Single
Multi
Certified
Natural
Certified
Natural
31.471
93.62
97.94
3
92,91
98. 56.56
93.03
98
92.41
98.88
92.70
98.88
Training encounters mode cullapse. Last epoch performance reported.
PGD Attack Strength To investigate the effect of the adversarial attack's strength, we use 1 or 3 restarts and vary the number attack steps used in TAPS from 1 to 100 for MNIST at e = 0.3, reporting results in Table Interest- ingly. even a single attack step and restart are sufficient to achieve good performance and out- perform IBP. As we increase the strength of the attack, we can increase certified accuracy slightly while marginally reducing natural accuracy, agreeing well with expectation of regularization strength increasing with attack strength.
Table Effect of different PGD attack strengths for MNIST at 0.3.
Restart
3 Restarts
Attack Steps
Certified
Natural
Certified
Natural
93.36
98.22
93.47
98.22
93.15
97.90
93.55
97.90
20
93.62
97.94
93.52
97.99
100
93.46
97.94
93.55
97.99
5 Related Work
Verification Methods In this work, we only consider deterministic verification methods, which analyze a given network as is. While complete (or exact) methods (Tjeng et al.) 2019 [Wang et al.)
2021 Zhang et al. [202aa] Ferrari et al. 2022) can decide any robustness property given enough time.
incomplete methods (Singh et al. 20188; Raghunathan et al. 2018 /hang al. 2018 Dathathri et al.) 2020: Müller et al.] (202b) sacrifice some precision for better scalability. However, recent complete methods can be used with a timeout to obtain effective incomplete methods.
Certified Training Most certified training methods compute and minimize sound over- approximations of the worst-case loss using different approximation methods: DIFFAI MMirman al. 2018) and IBP (Gowal et al. (2018) use Box approximations, |Wong al. (2018) use DEEPZ relaxations (Singh et al. 2018). Wong and Kolter 2018) back-substitute linear bounds using fixed relaxations, Zhang et al. (2200) use dynamic relaxations (Zhang al., 2018 Singh al. 2019a and compute intermediate bounds using Box relaxations. Shi et al. (2021) significantly shorten training schedules by combining IBP training with special initialization. Some more recent methods instead compute and optimize more precise, but not necessarily sound, worst-case loss approximations: SABR Mulleer et al., 2022a) reduce the regularization of IBP training by propagating only small but carefully selected subregions. IBP-R (Palma et al., 2022) combines adversarial training at large perturbation radii with an IBP-based regularization. COLT (Balunovic and Vechev| (echev][020) is conceptually most similar to TAPS and thus compared to in more detail below. While prior work

---

combined a robust and a precise network (üüller et al., 2021; Horváth et al. (022a). to trade-off certified and standard accuracy, these unsound certified training methods can often increase both.
COLT (Balunovic and Vechev 2020), similar to TAPS, splits the network into a feature extractor and classifier, computing bounds the feature extractor's output (using the ZoNOTOPE (Singh et al.] 2019a) instead of Box domain) before conducting adversarial training over the resulting region. Crucially, however, COLT lacks gradient connector and, thus, does not enable gradient flow between the latent adversarial examples and the bounds on the feature extractor's s output. Therefore, gradients can only computed for the weights of the classifier but the feature extractor, preventing the two components from being trained jointly. Instead. a stagewise training process is used, where the split between feature extractor and classifier gradually moves through the network starting with the whole network being treated as the classifier. This has several repercussions. not only is the training very slow and limited to relatively small networks (a four-layer network takes almost 2 days train) but more importantly, the feature extractor (and thus the whole network) is never trained specifically for precise bound propagation. Instead, only the classifier is trained to become robust the incurred imprecisions. As this makes bound propagation methods ineffective for certification, [Balunovic and Vechev (2020) employ precise but very expensive mixed integer linear programming (MILP (Tjeng al. 2019)), further limiting the scalability of COLT.
In our experimental evaluation (Section
we compare TAPS detail to the above methods.
Robustness by Construction Li ct al. (011). Lécuyer et al. (2019), and Cohen et al. (2019)
construct probabilistic classifiers by introducing randomness into the inference process of a base classifier. This allows them to derive robustness guarantees with high probability at the cost of significant (100x) runtime penalties. [Salman al. (2019) train the base classifier using adversarial training and Horvááhh et al. (2022b) ensemble multiple base models to improve accuracies at further runtime penalty. /Zhang et al. (2021 2022c) introduce disttanncc neurons, generalized to SORTNET by /Zhang et al. (2022b)) which inherently exhibits <s--Lipschitzzess properties, yielding good robustness for large perturbation radii, but poor performance for smaller ones.
Conclusion
We propose TAPS, novel certified training method that reduces ver-ragulaiization by constructing and optimizing a precise worst-case loss approximation based on a combination of IBP and PGD training. Crucially, TAPS enables joint training over the IBP and PGD approximated components by introducing the gradient connector to define a gradient flow through their interface. Empirically, we confirm that TAPS yields much more precise approximations of the worst-case loss than existing methods and demonstrate that this translates to state-of-the-art performance in certified training in many settings.
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 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

---

References
B. Biggio, I. Corona, D. Maiorca, B. Nelson, N. Srndic, P. Laskov, G. Giacinto, and F. Roli, "Evasion attacks against machine learning test time," in Proc of ECML PKDD, 2013.
C. Szegedy, W. Zaremba, I. Sutskever, J. Bruna, D. Erhan, J. Goodfellow, and R. Fergus, "Intriguing properties of neural networks," Proc. of ICLR, 2014.
V. Tjeng, K. Y. Xiao, and R. Tedrake, "Evaluating robustness of neural networks with mixed integer programming," in Proc. of ICLR, 2019.
R. Bunel, J. Lu, I. Turkaslan, P. H. S. Torr, P. Kohli, and M. P. Kumar, "Branch and bound for piecewise linear neural network verification," " J. Mach. Learn. Res., 2020.
H. Zhang, Wang, K. Xu, L. Li, B. Li, S. Jana, C. Hsieh, and Z. Kolter, "General cutting planes for gouuddpropagations based neural network verification," ArXiv preprint, vol. abs/2208.05740, 2022.
C. Ferrari, N. Müller, N. Jovanovic, and M. T. Vechev, "Complete verification via multi-neuron relaxation guided branch-and branch-and-boundd" in Proc. of ICLR, 2022.
E. Wong and J. Z. Kolter, "Provable defenses against adversarial examples via the convex outer adversarial polytope," " in Pruc. of ICML, 2018.
G. Singh, T. Gehr, M. Püschel, and M. Vechev, "An abstract domain for certifying neural networks," in Proc. of POPL, 2019.
H. Zhang, T. Weng, P. Chen, C. Hsieh, and L. Daniel, "Efficient neural network robustness certification with general activation functions," in Proc. of NeurIPS, 2018.
A. Madry, A. Makelov, L. Schmidt, D. Tsipras, and A. Vladu, "Towards deep learning models resistant to adversarial attacks," in Proc. of ICLR, 2018.
F. Tramèr, N. Carlini, W. Brendel, and A. Madry, "On adaptive attacks to adversarial example defenses," " in Proc. of NeurIPS, 2020.
M. Mirman, Gehr, and M. T. Vechev, "Differentiable abstract interpretation for provably robust neural networks," in Proc. of ICML, 2018.
S. Gowal, K. Dvijotham, R. Stanforth, R. Bunel, C. Qin, J. Uesato, R. Arandjelovic, T. A. Mann, and Kohli, "On the effectiveness interval bound propagation for training verifiably robust models," ArXiv preprint, vol.
2018.
Z. Shi, Y. Wang. H. Zhang. J. Yi, and C. Hsich, "Fast certified robust training with short warmup," in Proc. of NeurIPS, 2021.
N. Jovanovié, M. Balunović, M. Baader, and M. Vechev, "On the paradox of certified training," in Proc. of International Conference Machine Learning (ICML), 2022.
M. Balunovic and M. T. Vechev, "Adversarial training and provable defenses: Bridging the gap," in Proc. of ICLR, 2020.
A. D. Palma, R. Bunel, K. Dvijotham, M. P. Kumar, and Stanforth, "IBP regularization for verified adversarial robustness via branch-and-bound," ArXiv preprint, vol. abs/2206.14777 2022.
M. N. Müller, F. Eckert, M. Fischer, and M. T. Vechev, "Certified training: Small boxes are all you need," CoRR, vol. abs/2210.04871, 2022.
Croce and M. Hein, "Reliable evaluation adversarial robustness with an ensemble of diverse parameter-free attacks," in Proc. of ICML, 2020.
M. Fischer, M. Balunovic, D. Drachsler-Cohen, T. Gehr, C. Zhang, and M. T. Vechev, "DL2: training and querying neural networks with logie," in Proc. of ICML, 2019.
Y. Mao, M. N. Müller, M. Fischer, and Vechev, "Understanding certified training with interval bound propagation." CoRR, vol. abs/2306. 104.6.2606.1446, 2023.

---

A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin. N. Gimelshein, Köpf, E. Yang. Z. DeVito, M. Raison, A. Tejani, S. Chilamkurthy, B. Steiner, L. Fang, J. Bai, and S. Chintala, "Pytorch: An imperative style, high-performance deep learning library," in Proc. of NeurlPS, 2019.
L. Antiga, A. Desmaison,
Y. LeCun, C. Cortes, and C. Burges, "Mnist handwritten digit database," ATT Labs [Online]. Avail- able: http://aww..cccc..c/////////i///
2010.
A. Krizhevsky, G. Hinton al., "Learning multiple layers of features from tiny images," 2009.
Y. Le and X. S. Yang, "Tiny imagenet visual recognition challenge," CS 23/N, no. 7, 2015.
B. Zhang, D. Jiang, D. He, and L.. Wang, "Rethinking lipschitz neural networks and certified robustness: A boolean function perspective," CoRR, vol. abs/2210.01787, 2022.
B. Zhang. T. Cai, Z. Lu, D. He, and L. Wang. "Towards certifying l-infinity robustness using neural networks with d-inf-dist neurons," in Proc. of ICML, 2021.
B. Zhang, D. Jiang. D. He, and L. Wang, "Boosting the certified robustness of l-infinity distance nets," in Proc. ICLR, 2022.
C. Anil, J. Lucas, and R. B. Grosse, "Sorting out lipschitz function approximation." in Proc. of ICML, 2019.
S. Wang, H. Zhang, K. Xu, X. Lin, S. Jana, C. Hsieh, and J. Z. Kolter, "Beta-crown: Efficient bound propagation with per-neuron split constraints for neural network robustness verification," in Proc. of NeurlPS, 2021.
G. Singh, T. Gehr, M. Mirman, M. Püschell and M. T. Vechev, "Fast and effective robustness certification," in Proc. of NeurlPS, 2018.
A. Raghunathan, Steinhardt, and P. Liang, "Certified defenses against adversarial examples," in Proc. of ICLR,, 2018.
S. Dathathri, K. Dvijotham,
A. Kurakin, A. Raghunathan, J. Uesato, R. Bunel, S. Shankar, J. Stein- hardt, J. J. Goodfellow, P. Liang, and P. Kohli, "Enabling certification of verification-agnosti networks via memory-efficient semidefinite programming," in Proc. of NeurlPS, 2020.
M. N. Müller, G. Makarchuk, G. Singh, M. Püschel, and M. T. Vechev, "PRIMA: general and precise neural network certification via scalable convex hull approximations," Proc. ACM Program. Lang., POPI., 2022.
E. Wong, F. R. Schmidt, J. H. Metzen, and Z. Kolter, "Scaling provable adversarial defenses," in Proc. of NeurIPS, 2018.
H. Zhang, H. Chen, C. Xiao, S. Gowal, R. Stanforth, B. Li, D. S. Boning, and C. Hsieh, "Towards stable and efficient training of verifiably robust neural networks," Proc. of ICLR, 2020.
M. Müller, M. Balunovic, and M. T. Vechev, "Certify or predict: Boosting certified robustness with compositional architectures," in Proc. of ICLR, 2021.
M. Z. Horváth, M. N. Müller, M. Fischer, and M. T. Vechev, "Robust and accurate compositional architectures for randomized smoothing." " CoRR, vol. abs/2204.00483 000487, 2022.
B. Li, C. Chen, W. Wang, and L. Carin, "Certified adversarial robustness with additive noise," " in Proc. of NeurlPS, 2019.
M. Lécuyer, V. Atlidakis, R. Geambasu, D. Hsu, and S. Jana, "Certified robustness to adversarial examples with differential privacy," in Proc. of S&P, 2019.
J. M. Cohen, E. Rosenfeld, and J. Z. Kolter, "Certified adversarial robustness via randomized smoothing." " in Proc. of ICML, 2019.
H. Salman, Li, I. P. Razenshteyn, P. Zhang, Zhang, S. Bubeck, and G. Yang, "Provably robust deep learning via adversarially trained smoothed classifiers," in Proc. of NeurIPS, 2019.
12

---

M. Z. Horváth, M. N. Müller, M. Fischer, and M. T. Vechev, "Boosting randomized smoothing with variance reduced classifiers, " in Proc. of ICLR, 2022.
C. Brix, M. Müller, S. Bak, T. T. Johnson, and C. Liu, "First three years the international verification of neural networks competition (VNN-COMP)" STTT ExPLAIn, 2023.
M. N. Müller, C. Brix, S. Bak, C. Liu, and T. T. Johnson, "The third international verification of neural networks competition (VNN-COMP 2022): Summary and results," CoRR, vol. abs/2212.10376, 2022.
G. Singh, R. Ganvir, M. Püschel, and M. T. Vechev, "Beyond the single neuron convex barrier for neural network certification," in Proc. of NeurlPS, 2019.
13

---

A Averaging Multipliers Makes Gradients Efficient
Theorem 1. Let 24 be i...d. drawn the dataset and define f. (z;) and gi ge ) where
fe and go are two functions. Further, define L1 = (hi= fi) (2i=i (i) and L2 = 2 + fig.
Then, assuming the function value and the gradient are independent, Eg 88 Var, (OL) I Var, (aLa)
(0L) Eg 00 and
Proof. A famous result in stochastic optimization is that stochastic gradients are unbiased. For completeness, we give short proof of this property: Let L Ezf(x) 1-x f(x)dP(x). thus V.L= = V= f(z)dP(x)) f v=f(z)dP(z) H2 (v)(()) Therefore, V ff(;;) is an unbiased estimator of the true gradient.
Applying that the stochastic gradients are unbiased, we can write Vefi Vef + Th. where Vef is the expectation of the gradient and 77, is the deviation such that En,, = 0 and Var(n: = =.. Since T; is drawn independently, f, are independent and thus тι are independent. Similarly, we can write Vog: Vg + 5; where Eś; = 0 and Var(ó;) = o². and 6; may be dependent.
Define f = Ei J and y = E; L gs. Explicit computation gives us that VL - H.)) f. ( Vg:) and VL = Σi (f.Vg: + g. ft). Therefore,
Eg (VoL1 fv.g.) = oV + Vog = Ez (VoLz ft.
By the law of total probability,
Eg (VeL1) Ess (Eg (oL1 f()):)
E (Ez (VoL2 fi,
Ex (VoL2).
Therefore, we have got the first result: the gradients of L1 and Ly have the same expectation.
To prove the variance inequality, we will use variance decomposition formula
Var, (VoL.)
F. (Var, Vo ft,g:))+ Var (Ez (VoLx fs.9)))
k: 1. We have proved that E, (Voh ft, (V Je, thus the second term is equal. Next, we prove that Var (VoL1 fi, I Var, (VoL2 fr, gi), which implies Var, ( (VeL1) s Var. (VeL2).
By explicit computation, we have
Var(VL, 9i)
Σ 1
Var
+ Var
1 og)
+ - o. (f)2,
(4)
n
and
Var(VL2 fs.gi)
Var
Σ n
fide
Var
Σ 9:7
-
1
n
of
Σ n
gi
02
f2
(5)
n
n
n
Applying Jensen's formula the convex function 2², we have (E; 2a,) 2 < Lo for any a,
thus (f)² Σ. / and (g)² Σ, L Combining Equation (4) and Equation (5) with these two inequalities gives the desired result.
hhupp://en.wwikee www.pppdia.rr/wwikki..... of total variance
14

---

Algorithm Train Loss Computation
Input: data XB {(zs, bo) current e, target e`, network Output: A differentiable loss L
LIPP EbeB Linp (I06, (1ne( Vb, c)/13).
if < é' 'ten
c annealing regularisation from Shi et al. (2021)
Listt
(Lrightness + Lrelu)
return LIBP + -e/e' Lixs
LTAPS- = -Eoeg (TP, You e)/lBl.
return LIP LIAPS
Table 5: The training epoch and learning rate settings.
Dataset
Batch size
Total epochs
Annealing epochs
Decay-1
Decay-2
MNIST
256
70
20
50
60
CIFAR-I0
128
160
80
120
140
TINYIMAGENET
128
60
70
B Experiment Details
B.1 TAPS Training Procedure
To obtain state-of-the-art performance with IBP, various training techniques have been developed. We use two of them: 6-annealing (Gowal et al. (2018) and initialization and regularization for stable box sizes (Shi et al. 202I). e-annealing slowly increases the perturbation magnitude e during training to avoid exploding approximation sizes and thus gradients. The initialization of (Shi al. (202 scales network weights to achieve constant box sizes over network depth. During the e-annealing
phase, we combine the IBP loss with the ReLU stability regularization Liss (Shi et al. [02 l), before
switching to the TAPS loss as described Section 3.4 We formalize this in Algorithm
I We follow
Shi al. 2021 I) in doing early stopping based validation set performance. However, accuracy (see App. C) instead of IBP accuracy as a performance metric.
TAPS
B.2 Datasets and Augmentation
We use the MNIST LeCun et al. 2010), CIFAR-10 (Krizhevsky et al., 2009), and TINYIMAGENET (Le and Yang 2015) datasets, all of which are freely available with no license specified.
The data preprocessing mostly follows Müller et al. (202a)). For MNIST, we do not apply any preprocessing. For CIFAR-10 and TINYIMAGENET, we normalize with the dataset mean and standard deviation (after calculating perturbation size) and augment with random horizomtal flips. For CIFAR-10, we apply random cropping 32 x 32 after applying
2 pixel padding at every margin. For TINYIMAGENET, we apply random cropping to 56 x 56 during training and center cropping during testing.
B.3 Model Architectures
Unless specified otherwise, we follow Shi et al. (021): Batch Norm for our main experiments. CNN7 is convolutional network with 7 convolutional and linear layers. All but the last linear layer are followed by a Batch Norm and ReLU layer.
:): Müller et al. (002a)) and use a CNN7 with
B.4 Training Hyperparameter Details
We follow the hyperparameter choices of Shi et al. (2021) for e-annealing, learning rate schedules. batch sizes, and gradient clipping (see Table We set the intiil learning rate to 0.0005 and decrease it by factor of 0.2 at Decay-1 and -2. We the gradient clipping threshold 10.
We use additional T regularization some settings where we observe signs of overfitting. We report the Lj regularization and split position chosen for different settings in Table and Table
15

---

Table Hyperparameters for TAPS.
Dataset
ReLUss Classifier
0.1
le-6
MNIST
0.3
0
2/255
CIFAR-10
8/255
20-6
TINYIMAGENET
1/255
Table 7: Training and certification times for TAPS-trained networks.
Dataset
Train Time (s)
Certify Time (s)
0.1
42622
17 117
0.3
12417
41 624
2/255
141 281
CIFAR-I0
8/255
27017
26968
TINYIMAGENET
1/255
306
23497
We train using single NVIDIA GeForce RTX 3090 for MNIST and CIFAR-10 and single NVIDIA TITAN RTX for TINYIMAGENET. Training and certification times are reported in Table 7 and
Table g
B.5
Certification Details
We combine IBP (Gowal et al. 2018), CROWN-IBP (Zhang et al. 2020). and MN-BAB (Ferraii al. 2022) for certification, running the most precise but also computationally costly MN-BAB only on samples not certified by the other methods. We use the same configuration for MN-BAB as Müller et al. (2022a). The certification is run on single NVIDIA TITAN RTX.
MN-BAB Ferrari et al. (2022) is a statc-of-the-ee (Brix et al. 2023 Müller et al. 2022c) neural network verifier, combining the branch-and-bound paradigm (Bunel al. 2020) with precise multi- neuron constraints (Müller et al. 20226 Singh et al. 2019b).
We use mixture of strong adversarial attacks to evaluate adversarial accuracy. First, we run PGD attacks with 5 restarts and 200 iterations each. Then, we run MN-BaB to search for adversarial examples with timeout of 1000 seconds.
C Extended Evaluation
TAPS Accuracy as GoF In practice, we want to avoid certifying every model with expensive certification methods, especially during hyperparameter tuning and for early stopping. Therefore, need a criterion to select models. this section, we aim to show that TAPS accuracy (accuracy of the latent adversarial examples) is good proxy for goodness of fit (GoF).
We compare the TAPS accuracy to adversarial and certified accuracy with all models we get on MNIST and CIFAR-10. The result is shown in Table [Q] We can see that the correlations between TAPS accuracy and both the adversarial and the certified accuracy are close to 1. In addition, the differences small and centered zero, with a small standard deviation. Therefore, we conclude that TAPS accuracy is good estimate the true robustness, thus good measurement of GoF, In all the experiments, perform model selection based on the TAPS accuracy.
Training Difficulty Since TAPS is merely a training technique, we can test using a different classifier split. By design, if the training is successful, then under given classifier split for testing, the model trained with the same split should have the best TAPS accuracy. Although this is often true, we find that in some cases, smaller classifier split results in higher TAPS accuracy, indicating optimization issues.
models
We measure TAPS accuracy for models trained with IBP and TAPS using different splits for CIFAR- 10 (Figure 10 and MNIST (Figure 11). We observe that for CIFAR-10 e = 2/ and MNIST, the models trained and tested with the classifier/extractor split achieve the highest TAPS accuracies, as expected, indicating relatively well-hehaved optimization problem. However, for CIFAR-10
8/255, the model trained with classifier size of achieves the highest TAPS accuracy for all
16

---

Table 8: Hyperparameter for STAPS.
Dataset
# ReLUss Classilier
r/c
0.1
2e-5
5
0.4
MNIST
0.3
20-6
5
0.6
CIFAR-10
8/255
1
20-6
5
0.7
TINYIMAGENET
1/255
le.6
5
0.6
Table 9: Training and certification times for STAPS-trained networks.
Dataset
Train Time (8)
Centify Time (s)
0.1
19865
12943
MNIST
0.3
23613
125 768
2/255
17 636
398 245
CIFAR-10
793
TINYIMAGENET
1/255
831.639
35 183
test splits and also the best adversarial and certified accuracy (see Figure 7b and Table 12 This indicates that, in this setting, an earlier split and thus larger classifier component induces (too) difficult optimization problem, leading to worse overall performance.
Split Position
We report detailed results for the experiment visualized Figure 7b (Section 4.2) in
Table I1 and Table 12 We additionally report results on TINYIMAGENET in Table 13
IBP Regularization We repeat the experiment reported on for MNIST in Table 2 for TINYIM- AGENET, presenting results in Table 14 We generally observe the same trends, although peak certification performance is achieved slightly later at 0TAPS = 10 instead of 0TPPS =
Repeatability Due to the large computational cost of up 10 GPU-days for some experiments (see Tables / and 9 we could not repeat all experiments multiple times to report full statistics. However, report statistics for the best-performing method for MNIST at 0.1 and 0.3 and CIFAR-10 at 2/255 and e = 8/255 (see Table 15). We generally observe small standard deviations, indicating good repeatability of our results.
D Limitations
TAPS and all other certified training methods can only be applied to mathematically well-defined perturbations of the input such by-balls, while real-world robustness may require significantly more complex perturbation models. Further and similarly to other unsound certified training methods, TAPS introduces a new hyperparameter, the split position, that can be tuned to improve performance further beyond the default choice of ReLU layer in the classifier. Finally, while training with TAPS is similarly computationally expensive as with other recent methods, notably more computationally expensive than simple certified training methods such as IBP.
E
Reproducibility
We publish our code, trained models, and detailed instructions on how to reproduce our results at github. wwt.etoeeeeetteeeeeeee sri/taps providing anonymized version to the reviewers Additionally, provide detailed descriptions of all hyper-parameter choices, data sets, and preprocessing steps in App.
'We provide the codebase with the supplementary material, including instructions on how to download our trained models.
17

---

Frequeey
Prequemcy
Proquency
IBP
SABR
TAP3
Loss Approcimatin Error
Loss Approsimation Error
Loes Apprestmation Eror
(a) IBP-trained
(b) B-ttaidd
(c) PS-traineed
Figure 9: Distribution of the worst-case loss approximation errors over test set samples, depending on the training and bounding method. Positive values correspond over-approximations and negative values to under-approsn inder-approximation.. We use an exact MILP encoding (Tjeng et al. (219)) as reference.
Table 10: Comparison of TAPS accuracy with certified and adversarial accuracy.
Dataset cor(TAPS, cert.)
cor(TASS, adv.)
TAPS cert.
TAPS adv.
MNIST
0.9139 0.9973
0.9633
0.0122 + 0.0141
0.0033 + 0.0079
CIFAR-10
0,9989
0.0028 + 0.0095
-0,0040 + 0.0077
9.349
0.559
0.342
0.500
0.405
0.433
0.645
0.949
0.352
0.328
0.324
0:330
0.323
0:322
Thu #fecle in Qssaterr
0.356
2.3/1
0/3
0.379
0310
0.111
0.339
9.338
0.355
0.065
0.22
0.545
The #hell
9.359
0.933
0.53
0.500
0.592
0.50
0.31
0.355
0.345
0.346
0:351
0.344
0.368
3.509
3.503
0.500
0
023
0.326
0.206
0.346
0.350
0.254
0.349
0.557
PR tie Cleneer
#8 Cheeiter
255
255
Figure 10: TAPS accuracy of models trained with different classifier sizes for CIFAR-10.
0.300
2.382
0.777
0.722
0.343
0.342
0.220
0.337
0.225
0.21
Toss SouA Caatter
m- 0.221
2.383
0.285
0.385
0.85
0.83
0952
0.054
0.342
0.245
0.255
0.200
0.24
0.45
0.555
Ther
5.486
0485
605
3.440
0.350
0.954
0.6
066
0.282
2.384
0.386
0.955
0.885
0.85
0395
0.945
0.340
0.152
0.965
0.664
0382
0373
Thin Peillc Cheniieer
Trair Wi lie Choritter
0.1
0.3
Figure TAPS accuracy of models trained with different classifier sizes MNIST.
18

---

Table 11: Effect of split position accuracies [%] for fixed model size MNIST.
Cert.
ReLUs Classifier
MN. BaB
IBP
98.87
98.16
98.13
97.83
99.16
98.
98.25
87.82
0.1
3 99.19
98.51
98.39
62.83
99.28
98.17
98.03
4.75
99.09
98.45
95.27
81.89
0
97.60
93.37
93.15
93.08
97.91
94.01
93.62
92.76
98.63
94.4S
93.03
89.40
4
98.7
91.85
93:44
89.52
98.63
94. 64
93.26
89.15
Table 12: Effect of split position on accuracies [%] for fixed model size on CIFAR-10.
Cert.
#ReLUs
Nat.
Adv.
MN-BaB
IBP
67.27
56.32
56. 14
53.54
70.10
57.78
57.48
41.86
70.74
57.83
57.39
40.24
58.89
58.23
34.41
72.45
60.38
59.47
31.88
75.09
63.00
61.56
24.36
75.40
62.73
61.11
24.90
48.15 15
34.63
34,60
34.26
35.29
35.10
32.92
47.28
33.54
33.12
28. 94
48.76
33.50
33.12
29.14
253
50.19
34.78
34.35
29.14
34.33
33.72
28.83
51.03
35.25
34.44
29.97
Table Effect split position on accuracies [%] for fixed model size on TINYIMAGENET.
TAPS
STAPS
ReLU
Nat. (%)
Adv. (%)
Cest. (%)
Train
Certify (s)
Nat. (%)
Adv. (%)
Cert. (%)
Train (s)
Certify (6)
1
28.34
20.94
20.82
306
23:497
28.75
22.25
22.04
350924
35 894
2
27.02
20.94
20.84
407
28.98
22.40
22.16
861 639
35 183
Table 14: Effeec of IBP regularization and the TAPS gradient expanding coefficient a for TINYIMA- GENET 255
WTAPS
Avg
(%)
Adv. (%)
Cert. (%)
CIPP
0.28
25.00
19.72
19.72
1.17
25.83
20.24
20.22
2.34
28.34
20.94
20.82
10
4.12
28.23
21.05
20.59
20
5.94
28.44
20.68
20.44
Table 15: Mean and standard deviation (over three repeats) for the method with best certified accuracy.
Dataset
6oo
Method
Nat. [%]
Adv. [%]
Cert. [%]
0.1
TAPS TAPS
99.22 +: 0.03
98.45 + 0.06
98.28 + 0.10
MNIST
0.3
97.96 + 0.04
93.96 + 0.04
93.57 = 0.02
2/255
STAPS
79.75 + 0.23
65.91 + 0.12
62.72 + 0.23
CIFAR-10
8/255
TAPS
49.07 + 0.61
34.75 + 0.47
34.57 + 0.46
19


Reviews:
[{"review_id": "Prc4qi3gIB", "reviewer": "Reviewer_jSFD", "summary": "The paper proposes TAPS -- a method to combine IBP and PGD to train better certified networks. The authors observe that IBP on its own leads to overestimation of the inner adversarial loss, where as PGD leads to an underestimation. Therefore, intuitively, the approximation errors may compensate for each other during training. Thus, TAPS leverages PGD on the pre-classification logits output using IBP to generate a better loss approximate. Given the non-differentiable nature of this, the authors propose a rectified linear gradient approximation to allow end to end training. Empirical results are provided for CIFAR10, MNIST and TinyImagenet, showing improvement over pure IBP and other IBP-approximation approaches.", "questions": "1. What is the computational overhead of TAPS/STAPS over other methods?", "limitations": "The authors have clearly mentioned limitations.", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The proposed approach is well-motivated and the authors provide clear justification through experimental analysis.\n2. The gradient connector is novel mechanism allowing end to end training of PGD + IBP networks. This is a creative approach towards combining two connected but complementary methods, essentially improving on COLT which sequentially leverages both.\n3. The experiments are thorough and support the claims in the paper. \n4. The paper is well-written and thoughtfully explains the intuition for every step in the algorithm.", "weaknesses": "While not a major weakness, I would be interested to see if leveraging stronger or weaker attacks during the PGD training step significantly changes results. Perhaps a simple experiment with varying PGD iterations, or even a stronger attack like Autoattack would clearly answer this.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer $\\Ro$ for their insightful feedback, helpful suggestions, and interesting questions. Below, we address their questions.\n\n**Q1. What is the computational overhead of TAPS/STAPS over other methods?**  \nWhen using single-estimator PGD, TAPS is strictly faster than SABR [1], as it only requires a partial IBP propagation and adversarial search only over the classifier component. When using multi-estimator PGD, the runtime trade-off depends on the number of classes and size of the classifier component. Here, TAPS requires multiple PGD attacks over a smaller network (component) while SABR requires a single attack over the whole network. Compared to TAPS, STAPS requires an additional adversarial attack over the whole network and is thus always slightly slower than SABR. However, both TAPS and STAPS are notably faster than COLT [2], as IBP propagation is much faster than DeepZ [3] and the gradient connector makes COLT’s complex training in multiple stages obsolete. For TinyImageNet, we find TAPS to already be consistently slower than SABR but believe that designing strategies between single- and multi-estimator PGD to be an interesting item for future work that has the potential to change this. We provide runtimes in Table 6 and 8 in Appendix B, for TAPS and STAPS, respectively.\n\n**Q2: What is the effect of the adversarial attack’s strength on the obtained results?**  \nGreat questions! We have conducted a corresponding experiment using 1 to 100 attack steps with 1 or 3 restarts to investigate this for MNIST $\\epsilon=0.3$ and the CNN7 architecture used for our main results and report results in the table below. Interestingly, even a single attack step and restart are sufficient to achieve good performance with TAPS, in particular, outperforming standard IBP. As we increase the strength of the attack, we can increase certified accuracy slightly while marginally reducing natural accuracy, agreeing well with our expectation of regularization strength increasing with attack strength. We are happy to include these results in the next revision of the paper. We also provide nicely rendered version of this table in the PDF attached to the general reply.\n\n \n| Restarts | Number of Steps |   Natural  |  Certified |\n|:--------:|:---------------:|:----------:|:----------:|\n|     1    |        1        | **0.9822** |   0.9336   |\n|          |        5        |   0.9790   |   0.9315   |\n|          |        20       |   0.9778   |   0.9343   |\n|          |       100       |   0.9794   | **0.9346** |\n|     3    |        1        | **0.9822** |   0.9347   |\n|          |        5        |   0.9790   | **0.9355** |\n|          |        20       |   0.9799   |   0.9352   |\n|          |       100       |   0.9799   | **0.9355** |\n\n**References**  \n[1] Müller et al. \"Certified Training: Small Boxes are All You Need.\", ICLR’23  \n[2] Balunovic and Vechev. \"Adversarial training and provable defenses: Bridging the gap.\" ICLR’19  \n[3] Singh et al. \"Fast and effective robustness certification.\" NeurIPS’18  \n"}, {"review_id": "QMb2iOspDf", "reviewer": "Reviewer_8yjL", "summary": "This paper proposes a method called Training via Adversarial Propagation through Subnetworks (TAPS) for improving certified adversarial robustness. Specifically, TAPS splits the network $f$ into a feature extractor $f_E$ and a classifier $f_C$. During training, TAPS first uses interval bound propagation (IBP) to bound the feature extractor's exact reachable set in the embedding space and conducts adversarial attacks (PGD) in the embedding space to the classifier. This method can also be combined with other state-of-the-art methods like SABR (called STAPS) that can further improve its performance.\n\n## post-rebuttal\nI've updated my score since my concerns are adequately addressed.", "questions": "1. Line 36: Can you explain what \"tractable\" means in this context?\n2. Lines 114-115: How is $x'$ selected for SABR? I suggest adding more details here since SABR is the main baseline of your method.\n3. Although the code is provided, this reviewer strived to understand it. In particular, where is the command and variable for splitting the network?\n4. What is the constraint ($\\epsilon$-ball) for PGD attack in TAPS? Since PGD is conducted in the embedding space, the constraint on the input space may not be effective.\n5. How about using PGD for the feature extractor and IBP for the classifier?", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. This paper is well-motivated and well-organized.\n2. The idea of connecting adversarial training and IBP training is novel and impressive.\n3. The experiments show that the proposed method can outperform state-of-the-art methods for several settings.", "weaknesses": "1. The certified robustness for a larger perturbation bound (8/255) is not comparable with SortNet, showing the limitation of TAPS/STAPS under certain settings. Additionally, the comparison under a larger perturbation bound (>1/255) for TinyImageNet is not provided. Based on the comparison under 8/255 for CIFAR-10, this reviewer infers that SortNet may also outperform TAPS/STARPS for a larger dataset with a larger perturbation bound.\n2. The details of how to combine TAPS and SABR are not provided in Section 3.5.\n3. This work only focuses on $\\ell_\\infty$ robustness and does not show scalability to other metrics of robustness, such as $\\ell_2$-norm.\n4. It seems that several experiments in this paper were not completed when submitted (Tables 2 and 3). However, I think this is acceptable since the main comparison is complete. The authors should complement the missing results if accepted.\n\n### Minor Comments\n\n1. Line 11. I personally suggest removing the claim of publication for your implementation and networks, even though you have anonymized the code link. As this paper is still under review, the code has not yet been published.\n2. Line 44. Lack of the full spelling and reference for SABR. Also, the details for SABR are not sufficiently introduced in this paper.\n3. Line 105. I suggest replacing the claim \"vulnerable\" of adversarial training under stronger attacks with a more moderate tone. Even under AutoAttack, the robustness of an adversarially trained model is slightly lower than PGD. So far, adversarial training is still one of the most effective methods to improve adversarial robustness. Thus, this assertion on adversarial training methods is unfair for this research area and may mislead the community.\n4. Line 148. Is $\\theta_F$ exactly $\\theta_E$?\n5. Line 595. The author stated that they provided detailed descriptions, but the location is shown as \"??\".", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer $\\Rt$ for their insightful feedback, helpful suggestions, and interesting questions. Below, we address their questions.\n\n**Q1: Why is only $\\ell_\\infty$-norm robustness and no $\\epsilon$ larger than $1/255$ for TinyImageNet evaluated? How would SortNet perform in such a setting?**  \nWe follow the conventions of the field in both of these respects: First, works investigating convex relaxation based certified robustness (such as TAPS) almost always investigate only $\\ell_\\infty$-norm robustness [1,2,3,4,5,...]. Second, obtaining non-trivial certified accuracy on TinyImageNet is already highly challenging for $\\epsilon = 1/255$, thus larger radii are typically not considered in the literature [1,3,4,6] (we are not aware of any results). Further, while SortNet’s [6] performance on CIFAR-10 for $\\epsilon = 8/255$ is impressive, we believe this to not necessarily be an indication of great performance on TinyImageNet at larger radii. In fact, on TIN at $\\epsilon = 1/255$ it is only on par with IBP and on MNIST, it is dominated by STAPS regardless of radius.\n\n**Q2: Can you expand the background on SABR and add how TAPS and SABR combine to STAPS?**  \nPlease see the main response for a detailed reply!\n\n**Q3: Are the results in Tables 2 & 3 complete?**  \nA: Great question, we will clarify this in the text. Table 3 is complete and missing results simply show the instability of single-estimator PGD, thus highlighting the importance of our multi-estimator PGD.\nIn Table 2, we decided to not complete the evaluation of the last two rows as this would require well over 100 GPU days and the partial results already show a severe drop in certified accuracy. \n\n**Q4: Can you clarify the meaning of ``tractable'’ (L36)?**  \nA: Generally the verification problem is NP-hard [7]. However, recent branch-and-bound-based approaches [8] can solve many practical instances efficiently. We will clarify this.\n\n**Q5: In your code, what is the command and parameter for splitting the network?**  \nA: TAPS is implemented in ```torch_model_wrapper.py``` in the class ```BoxModelWrapper```. The method ```split_net_to_blocks``` of this class splits the network into feature extractor and classifier. When the code is publicly released, we will provide documentation containing such details.\n\n**Q6: What are the constraints/bounds for PGD in the embedding space utilized in TAPS?** \nA: As we outline in L133ff, we first propagate $\\mathcal{B}(x, \\epsilon)$ via IBP through $f_E$. This results in interval bounds $[\\underline{\\mathbf{z}}, \\overline{\\mathbf{z}}]$, describing a hyper-rectangle (i.e., a stretched $\\ell_\\infty$-ball). We then conduct an adversarial attack using PGD within this hyper-rectangle in the latent space of the model.\n\n**Q7: Could you use PGD for the feature extractor and IBP for the classifier?**  \nA: While this is possible in theory, in practice this is infeasible. For each bound (upper and lower) in each dimension we require 1 PGD attack. As the latent space in many layers has over 20.000 dimensions, this requires large amounts of compute and memory per sample. Note, that when using the last layer, we only need to upper bound logit differences and thus require only (#classes - 1) attacks.\n\n\n**References**\n[1] Müller et al. \"Certified Training: Small Boxes are All You Need.\", ICLR’23  \n[2] Balunovic and Vechev. \"Adversarial training and provable defenses: Bridging the gap.\" ICLR’19  \n[3] De Palma et al. \"IBP regularization for verified adversarial robustness via branch-and-bound.\"  \n[4] Shi et al. \"Fast certified robust training with short warmup.\" NeurIPS’21  \n[5] Zhang et al. “Towards Stable and Efficient Training of Verifiably Robust Neural Networks” ICLR’20  \n[6] Zhang et al. ““Rethinking lipschitz neural networks and certified robustness: A boolean function perspective” arXiv  \n[7] Katz et al. \"Reluplex: An efficient SMT solver for verifying deep neural networks.\" CAV’17  \n[8] De Palma et al. \"Improved branch and bound for neural network verification via lagrangian decomposition.\" arXiv  \n"}, {"review_id": "yxBlAjh7ue", "reviewer": "Reviewer_5pzA", "summary": "This paper aims to improve the combination of adversarial training and certified training for certified robustness. A gradient connector is proposed for jointly conducting these two kinds of training. Results show some improvement on the certified robustness after the training, as well as a more precise approximation on the worst-case loss.", "questions": "See \"Weaknesses\".", "limitations": "Not discussed.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- This paper proposes a \"gradient connector\" which enables end-to-end training with both adversarial training and IBP-based certified training. \n- There is some empirical improvement on the certified accuracy on some settings (TinyImageNet), compared to prior works combining adversarial training and IBP training. \n- The proposed method can more precisely estimate the worst-case loss, compared to PGD, iBP, or prior methods doing the combination.", "weaknesses": "The empirical improvement on the major metric, certified accuracy, is very marginal and sometimes negative:\n- Compared to SABR (Muller et al., 2022a), the absolute improvement on MNIST is only 0.17% or 0.22%. \n- On CIFAR, simply using the proposed method does not bring any improvement but may even yield lower certified accuracy.\n- On CIFAR eps=2/255, combining SABR and the proposed method only has an absolute improvement of 0.14%. On CIFAR eps=8/255, doing this combination still leads to worse results compared to SABR alone. \n\nOverall, the current results on all the three datasets do not sufficiently demonstrate that the proposed method is effective in practice. It is still possible that the tiny difference on MNIST and CIFAR may come from randomness, yet standard deviation is not reported. \n\n==Updates==\n\nThanks to the authors for the explanations. I understand that both TAPS and STAPS are contributions of this work. However, while this paper looks overall good, empirical results still look kind of weak to me (as mentioned in the first point and the third point in my original review). Thus I am maintaining my original rating.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer $\\Rtr$ for their insightful feedback, helpful suggestions, and interesting questions.  We are delighted they appreciate our novel gradient connector and found our performance improvements on the challenging TinyImageNet satisfactory. Before addressing the reviewer’s remaining questions, we would like to respectfully ask them to outline any soundness concerns they might have (leading to a soundness score of 2) as their review does not touch on any such point.\n\n**Q1: Can you comment on the magnitude of improvement of TAPS and STAPS over SABR?**  \nA: First, we want to highlight, that both TAPS and STAPS are core contributions of this work and thus believe the fact that TAPS alone can realizes a comparable or bigger improvement over prior work than SABR (which achieved the biggest improvement in years) to highlight the promise of our method rather than being a weakness. \nSecond, in settings where low regularization strength is particularly desirable (CIFAR-10 2/255 and TinyImageNet 1/255), TAPS and SABR can be efficiently combined to STAPS to achieve even higher performance and highlighting the complementarity of the two methods (discussed in more detail in Section 3.5).\nThird, while the absolute improvements on MNIST might be small, they are a much bigger than e.g. those of SABR over SortNet and correspond to significant portions of the remaining error (9.5% and 3.3%), highlighting their importance.\t\n\n**Q2: Can you report the standard deviation of the considered performance metrics**  \nWe first want to highlight that we already report standard deviations for MNIST in Table 14. We are happy to also report statistics for all other settings in the next revision of this work. However, given that prior work often only reports the best observed results, putting these results in the right context would require reproducing and reporting statistics for all baseline methods as well, thus carrying significant computational costs.\n"}, {"review_id": "xxbHIPqbAp", "reviewer": "Reviewer_hZus", "summary": "The paper presents TAPS, an unsound certified training method that combines the advantages of certified training IBP and adversarial training PGD. TAPS first splits the neural network into two parts, the feature extractor, and the classifier. TAPS then uses IBP to propagate the over-approximation through the feature extractor. TAPS uses PGD to estimate multiple adversarial examples inside the over-approximated box and trains with these adversarial examples. The challenge is how to backpropagate gradients through the PGD part in the middle. TAPS designs a gradient estimator to connect the backpropagation. TAPS can also be combined with the current state-of-the-art method, SABR, to reduce the regularization in the feature extractor further, leading to higher natural accuracy and certified accuracy. \nThe experiment results show that TAPS and STAPS (TAPS+SABR) achieve the highest certified accuracy on MNIST, CIFAR10, and TinyImageNet, except for CIFAR-10 8/255. \n", "questions": "Comment:\n1. In line 92, $\\bar{\\mathbf{o}}^\\Delta > 0$ should be  $\\bar{\\mathbf{o}}^\\Delta < 0$.\n2. In Section 3.4, between lines 123 and 124, the gradient has an additional factor $2$. \n\nQuestions:\n1. In lines 162-164, the paper states that the j-th dimension of the latent adversarial examples is independent of the bounds in the i-th dimension. However, PGD will be affected by each dimension. Is this statement in the paper an assumption or these dimensions are in fact independent?\n2. In Figure 3, it seems $c$ cannot be greater than 0.5, otherwise the gradient connector cannot be a valid function. However, in Figure 7, $c$ can be larger than 0.5, and even achieves higher natural accuracy. What do I miss here?\n3. In Table 2, some settings have a time limit on MN-BaB. Does it means the certified accuracy is over-approximated, e.g., time-outed ones are considered as not certified?", "limitations": "The paper does not address any limitation. How to efficiently select hyper-parameters is a large problem for this type of training methods. For example, in Table 2, it might not be possible to completely compute the certified accuracy and to compare settings based on these metrics.  ", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "1. The paper presents a training method that beats the state of the art. \n2. The paper conducts extensive abolition studies.  ", "weaknesses": "1. In Table 1, STAPS has the best results in two out of five settings. And TAPS has worse results than SABR in two out of five settings. It seems SABR is as important as TAPS for STAPS. Then the discussion in Section 3.5 needs more rigorous justification. For example, the paper states that \"the exponential growth of BOX abstractions still causes a strong regularization of later layers\". The experimental illustration of this claim is missing. A layer by layer comparison of Figure 5 would be interesting to see. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer $\\Rf$ for their insightful feedback, helpful suggestions, and interesting questions. Below, we address their questions.\n\n**Q1: Is the independence of a given dimension of the PGD adversarial example from the IBP bounds in a different dimension an assumption?**  \nA:  Great question! This depends on the setting on considers:\nWhen doing an additional step of PGD, the bounds in the jth dimension have no impact on the obtained adversarial example as they impact neither the gradient sign nor the projection in this dimension, as Box bounds are axis parallel. However, when assuming an optimal adversarial attack capable of finding the global minimum over its perturbation space, the resulting adversarial example would indeed depend on all dimension-wise bounds jointly. Thus, this independence holds rigorously (up to initialization) for a single step attack and constitutes a mild assumption otherwise, we are happy to add a corresponding discussion to the relevant section.\n\n**Q2: In Table 2, some settings are noted to have timed out. What does this imply for certified accuracy?**  \nA: Typically, branch-and-bound based neural network verifiers such as MN-BaB, the one we use, apply a time-out per sample and consider all samples where verification times out to be uncertified. However, in Table 2, we refer to a total timeout for the verification process. The affected settings in Table 2 are particularly hard to certify, leading to frequent time-outs and thus very long verification times. As the obtained partial results already showed these settings to be less attractive, we decided to only evaluate part of the test set and then report the mean across the evaluated portion. Evaluating the slowest setting would require roughly 100 GPU days.\n\n**Q3: Can you extend the discussion of STAPS in Section 3.5, e.g. expanding on mentioned exponential growth of box abstractions?**  \nA: Yes! Please see the main response for a more detailed discussion of STAPS which we are happy to include in Section 3.5.\nWhile, due to space constraints, Section 3.5 focuses more on outlining the mechanics behind the complementarity of SABR and TAPS rather than a full discussion of all intricacies of STAPS, we are happy to add an extended version of the below discussion and corresponding plots to the appendix.\n\nThe exponential growth of Box abstractions, mentioned there, has been established both theoretically and empirically in prior work [1,2] which we are happy to highlight in the relevant section. As Figure 5 shows the worst-case loss approximation error, which can only be computed on the output, a directly analogous layerwise comparison is not possible. While we could compute and compare the mean side lengths of the Box abstractions obtained in different layers, this is very computationally expensive for PGD propagation, as the bound in every dimension requires a separate attack to estimate. However, as the TAPS and IBP and STAPS and SABR bounds are identical in the feature extract (before the split), their pairwise difference shows the isolated effect of the under-approximating effect of the PGD propagation through the classifier. While this can already be seen in Figure 5, we have added versions of the figure showing the distribution of the pairwise differences directly to the PDF attached to the general reply. We are happy to include these in our next revision.\n\n**Q4: Does the gradient in line 213-214 have an extra factor of 2?**  \nA: No, when choosing $\\alpha = 0.5$, both scaling terms ($2\\alpha$ and $(2-2\\alpha)$) evaluate to $1$ and we recover the standard gradient as given by the product rule. Choosing different $\\alpha$ allows us to scale the gradients of the two loss components in the employed multiplicative regularization, as is common for additive regularizations.\n\n**Q5. Why can the parameter $c$ in the gradient link, illustrated in Figure 3, be greater than 0.5?** \nWe believe the confusion might stem from Figure 3 showing two functions corresponding to the partial derivative with respect to the upper and lower bound, respectively. Both can generally have non-zero gradient for the same coordinate of the adversarial example, as is possible for $c > 0.5$\n\nThanks for pointing out the typo in Line 92, we will correct it.\n\n**References**  \n[1] Müller et al. \"Certified Training: Small Boxes are All You Need.\", ICLR’23  \n[2] Shi et al. \"Fast certified robust training with short warmup.\" NeurIPS’21  \n"}]

Author rebuttal:
$\newcommand{Ro}{\textcolor{purple}{jSFD}}$
$\newcommand{Rt}{\textcolor{green}{8yjL}}$
$\newcommand{Rtr}{\textcolor{blue}{5pzA}}$
$\newcommand{Rf}{\textcolor{orange}{hZus}}$


We thank all reviewers for their insightful feedback, helpful suggestions, and interesting questions. We were encouraged that they found our work well-motivated ($\Ro$, $\Rt$), novel ($\Ro$, $\Rt$) and well supported by our state-of-the-art empirical results ($\Ro$, $\Rt$, $\Rtr$ $\Rf$) and extensive ablations ($\Rf$). We answer the sole shared question here, before addressing the reviewer-specific ones in individual responses and look forward to the reviewers’ replies.

**Q1: Can you expand the discussion on STAPS in Section 3.5 and the relevant background on SABR? ($\Rt$, $\Rf$)**  
Yes! We are happy to extend the background on SABR as well as the discussion of STAPS in Section 3.5, as outlined below.

At a high level: IBP training propagates the entire input region $\mathcal{B}(x, \epsilon)$ for each sample $x$ in order to evaluate and then optimize the IBP loss (Eq. (2)).
In contrast, SABR propagates only a small subset $\mathcal{B}(x’, \tau) \subseteq \mathcal{B}(x, \epsilon)$, chosen by performing an adversarial attack to select $x’$, but otherwise uses the same loss and training procedure. In STAPS, we simply replace the IBP component with SABR, thus only propagating a small subset $\mathcal{B}(x’, \tau) of the input region, selected using an adversarial attack, to compute the bounds for the adversarial attack in the latent space of the feature extractor.

**In the attached PDF we provide a version of Figure 5 that highlights the difference between IBP and TAPS (as well as SABR and STAPS) for Q3 of $\Rf$.**


Meta-review: I have read all the submitted reviews, rebuttals, and ensuing discussions. The initial reviews were generally positive, and I'm pleased to note that the authors' rebuttal has effectively addressed the concerns raised by some reviewers. All reviewers recognize the contributions and novelty of the work, concurring that this is indeed a high-quality contribution.

The primary concern emerged from two reviewers, highlighting the somewhat less competitive results obtained on MNIST and in one particular setup of CIFAR. A discussion to address these points would be beneficial. Furthermore, the overall discussion of STAPS would enhance the paper's readability.

I would also suggest that the authors consider citing [A]. As far as I understand, [A] is the first approach to marrying certified and empirical methods within the training framework to enhance certified accuracy. Notably, they undertake adversarial training (PGD) on the smooth certified classifier using randomized smoothing. While closely related to this work, the distinction lies in the certification approach, where this paper employs IBP.

In summation, my recommendation is to accept the paper.

[A] Provably Robust Deep Learning via Adversarially Trained Smoothed Classifiers
Decision: Accept (poster)