Certify or Predict: Boosting Certified Robustness with Compositional Architectures
Authors: Mark Niklas Mueller
Mislav Balunovic
Martin Vechev
Venue: ICLR 2021 Poster (2021)
Keywords: Provable Robustness
Network Architecture
Robustness
Adversarial Accuracy
Certified Robustness

Abstract: A core challenge with existing certified defense mechanisms is that while they improve certified robustness, they also tend to drastically decrease natural accuracy, making it difficult to use these methods in practice. In this work, we propose a new architecture which addresses this challenge and enables one to boost the certified robustness of any state-of-the-art deep network, while controlling the overall accuracy loss, without requiring retraining. The key idea is to combine this model with a (smaller) certified network where at inference time, an adaptive selection mechanism decides on the network to process the input sample. The approach is compositional: one can combine any pair of state-of-the-art (e.g., EfficientNet or ResNet) and certified networks, without restriction. The resulting architecture enables much higher natural accuracy than previously possible with certified defenses alone, while substantially boosting the certified robustness of deep networks. We demonstrate the effectiveness of this adaptive approach on a variety of datasets and architectures.  For instance, on CIFAR-10 with an $\ell_\infty$ perturbation of 2/255, we are the first to obtain a high natural accuracy (90.1%) with non-trivial certified robustness (27.5%). Notably, prior state-of-the-art methods incur a substantial drop in accuracy for a similar certified robustness.

thus benefiting Published as a conference paper at ICLR 2021
CERTIFY OR PREDICT: BOOSTING CERTIFIED ROBUSTNESS WITH COMPOSITIONAL ARCHITECTURES
Mark Niklas Müller, Mislav Balunović, Martin Vechev
Department of Computer Science, ETH Zurich, Switzerland (ma rk. muel ler, m mislav. ba lnovic,, martin.vecher (anchhv)@iin..e winf.ethz.cl.
ABSTRACT
A core challenge with existing certified defense mechanisms is that while they improve certified robustness, they also tend to drastically decrease natural accu- racy, making it difficult to use these methods in practice. this work, we propose a new architecture which addresses this challenge and enables one to boost the certified robustness of any state-of-the-ar deep network, while controlling the overall accuracy loss, without requiring retraining. The key idea is to combine this model with (smaller) certified network where at inference time, an adaptive selection mechanism decides on the network used to process the input sample. The approach is compositional: one can combine any pair of state-of-the-art (e.g.. EfficientNet or ResNet) and certified networks, without restriction. The resulting architecture enables much higher natural accuracy than previously possible with certified defenses alone, while substantially boosting the certified robustness of deep networks. We demonstrate the effectiveness of this adaptive approach on a variety of datasets and architectures. For instance, on CIFAR-10 with an foo per- turbation of 2/255, we are the first to obtain high natural accuracy (90.1 10) with non-trivial certified robustness (27.5%). Notably, prior state-of-the-art methods incur substantial drop in accuracy for similar certified robustness.
INTRODUCTION
Most recent defenses against adversarial examples have been broken by stronger and more adap- tive attacks (Athalye et al.) 2018 Tramer al.) 2020), highlighting the importance of investigating certified defenses with suitable robustness guarantees (Raghunathan et al.) 2018 Wong & Kolter
2018 Zhang et al. 2020 Balunović & Vechev 2020). And while there has been much progress in developing new certified detenses, a fundamental roadblock to their practical adoption is that they tend to produce networks with an unsatisfying natural accuracy.
In this work propose novel architecture which brings certified defenses closer to practical use: the architecture enables boosting certified robustness of sfte-of-the-ar deep neural networks with- out incurring significant accuracy loss and without requiring retraining. Our proposed architecture compositional and consists of three components: (i) a core-network with high natural accuracy, (ii a certification-networr with high certifiable robustness (need not have high accuracy), and (iii a selection mechanism that adaptively decides which one of the two networks should process the input sample. The benefit of this architecture that we can plug in any state-of-the-art deep neural network as core-netwer nore-network and any certified defense for the certification-netee from any future advances in standard training and certified defenses.
A key challenge with certifying the robustness of a decision made by the composed architecture obtaining a certifiable selection mechanism. Towards that, we propose two different selection mechanisms, one based on an auxiliary selection-network and another based on entropy, and design effective ways to certify both. Experimentally, we demonstrate the promise of this architecture: we are able to train model with much higher natural accuracy than models trained using prior certified defenses while obtaining non-trivial certified robustness. For example, on the challenging CIFAR- 10 dataset with foo perturbation of 2/255, obtain 90.1% natural accuracy and certified robustness of 27.5%. On the same task, prior approaches cannot obtain the same natural accuracies for any non-trivial certified robustness.

---

Published as a conference paper at ICLR 2021
Main contributions Our main contributions are:
A new architecture, called ACE (short for Architecture for Certification), which boosts certified robustness of networks with high natural accuracy (e.g., EfficientNet).
Methods to train our newly proposed architecture and to certify the robustness of the entire composed network, including the certification of the selection mechanism.
Experimental evaluation demonstrating the promise of ACE: at the same non-trivial certified robustness levels, we can achieve significantly higher accuracies than prior work.
the CIFAR-10, Imageee and ImageNer200) datasets,
We release our code open source: http::/tttt//ggtt....oooo//////e http://ggghuu..ccc/tetttttte/
RELATED WORK
There has been much recent work on certified defenses, that is, training neural networks with prov- able robustness guarantees. These works include methods based on semidefinite relaxations (Raghu- inathan et al. 2018), linear relaxations and duality (Wong & Kolter 2018 Wong et al. 2018 Xu
et al. 2020), abstract interpretation (Mirman et al., (208)) and interval bound propagation (Gowal ctt al. 2018 The three most recent advances are COLT (Balunović Vechev 2020). based on con-
combination of linear relaxations Zhang et al. (2018) and interval propagation, and LiRPA (Xu et al., 2020) scaling to problems with many more classes by directly bounding the cross entropy loss instead of logit margins. As mentioned earlier, a key challenge with these methods is that in order to gain certified robustness, they tend incur drastic drop in natural accuracy.
vex layer-wise adversarial training, CROWN-IBP (hang al.] 2020), based
In parallel to certified defenses, there has also been interest in sertifying already trained models (Katz al. 2017; Tjeng et 2017 Gehr al. 2018 Weng al. 2018 Bunel et al.) 2018 Wang al., 2018 8a Singh et al. 2019). While these methods were initially focused mostly on Lp robustness, these works (as well ours) can be naturally extended to other notions of robustness, such as geometric (Balunović et al. 2019) or semantic (Mohapatra et al. 2020) perturbations. A line of work that weakens deterministic guarantees so scale larger networks is that of randomized smoothing which offers probabilistic guarantees (Lecuyer et al., 2018 Cohen et al. 2019 Salman et al. 2a) While interesting, this technique incurs overhead at inference time due to additional sampling, and further, generalizing smoothing to richer transformations (e.g., geometric) is non-trivial (Fischer cct al. 2020). In contrast, our work handles large networks while providing deterministic guarantees and because of its compositional nature, directly benefits from any advancements in certification and certified defenses with richer perturbations.
Our proposed architecture is partially inspired by prior work designing custom architectures for dynamic routing in neural networks (Teerapitayanon et al.] 2016)] Bolukbasi et al., 2017; McGill & Peronal 2017 Wang al., 2018b). While the main goal of these architectures is speed up inference, our observation is that similar type of ideas are applicable to the problem of enhancing certifiable robustness of existing neural networks.
BACKGROUND
We now present the necessary background needed to define our method.
Adversarial Robustness We define adversarial robustness of model h requirement that classifies all inputs in p-norm ball (x) of radius around the sample æ to the same class:
arg max h(x),; = arg maxh(x')) Va' E BP(x) = (=') =
|m - cp
(1)
In this work we focus on an too based threat model and use the notation ép indicate the upper bound to the f--norm of admissible perturbations. The robust accuracy a network is derived from this definition as the probability that unperturbed sample from the test distribution is classified correctly and Equation [ holds. As is usually infeasible to compute exact robustness, we define certifiably robust accuracy (also certifiable accuracy certifiable robustness), provable lower
2

---

Published as a conference paper at ICLR 2021
Kg. (a))
MA. (a) T
H(P(U)) <T
H(p())) T
1
hgg
lig.
softmax
p(y)
(a) SelectionNet ACE
(b) Entropy ACE
Figure I: Two variants of ACE. Dashed and solid arrows represent selection mechanism and classi- fication networks, respectively. The colored, dashed arrows represent the selection decision obtained by thresholding either the output of the selection network or the entropy. Based on this selection, we output either the result of the inlfficationnnewwann h2, (red) or the core-network hig (blue).
bound to the robust accuracy of network. This lower bound is obtained by attempting to prove adversarial robustness for all correctly classified samples æ using any certification method. For fixed, arbitrary certification method, we introduce the binary function cert(X, f, y) the result of an attempt to certify that f()) = Vo E X. In practice, adversarial robustness is usually evaluated as an upper bound to the exact robust accuracy of network and denoted as adversarial accuracy. This upper bound is usually computed using an adversarial attack such as PGD (Madry et al., 2017)
Certification and Training with Convex Relaxations Here we briefly summarize robustness cer- tification via convex relaxations. The idea is to start with an initial convex set capturing all admissi- ble perturbations an original sample æ, denoted as Co 2 (xx(a) and then propagate this convex set sequentially through all layers of the network. The key challenge is to design transformer T' that maps a convex input set to a convex output set for every function f corresponding to a network layer, while ensuring soundness: we need to guarantee that each point in the convex input set Can is mapped to a point in the convex output set, i.e. f(x) E Cout == (C(C.n). Finally, we obtain convex shape that captures all possible outputs of the network. To prove robustness, have to show that the output of the target class is greater than that of any other class, which is often simple. Depending on the type of transformer I'y used, this framework leads various certification methods such as IBP (Gowal et al. 2018) or DeepZ (Singh et al. 2018). A more comprehensive description of these methods can be found in Salman al. (2019b). There has recently been plethora of work which uses these methods to train provably robust neural networks, which we reference in Section In this work we use models pretrained with CROWN-IBP (Zhang et al., 2020), LiRPA (Xu et al, 2020) and COLT (Balunović & Vechev| (020) and train selection- and Certificationnnetworre using CROWN-IBE IBP, IBP and COLT. IBP (Mirman et al.) 2018; Gowal et al. 2018) and CRONW-IBP compute convex relaxations of the loss using intervals and restricted polyhedra, respectively, and minimize this loss during training. COLT (Balunović & Vechev 2020) proceeds layer by layer and tries find adversarial examples inside the convex relaxations of the latent spaces of perturbed samples, using PGD adversarial attacks.
4 COMPOSITIONAL ARCHITECTURE FOR CERTIFIABLE ROBUSTNESS
In this section, we formally introduce our proposed compositional architecture.
Overview We first describe the idea behind the two variants of our architecture, illustrated in Figure [] The first variant, named SelectionNet ACE, is shown Figure Ta Here, the selection mechanism is auxilliary selection network hž which decides whether to pass sample through the core- or the certification-network. we pass through the certification-netwool ha.- and otherwise we pass it through the core-network hg The second variant, Entropy ACE, is shown in Figure 1b Here we perform the selection for
the output of the selection network is greater than T. then
3

---

Published as a conference paper at ICLR 2021
every sample based on the output probabilities p(y) produced by the certification-networi hA, via the softmax function. If the entropy H (p(z)) of the output probability distribution exceeds fixed threshold T' we pass the sample through the core-network hig- otherwise we return the output of the ietificaationnetwownn In Figure I we show the selection mechanism using dashed arrows and the two possible outputs of the end-to-end architecture using solid, red and blue arrows.
Formally, propose the compositional neural network architecture he X y defined as
(x) = go. (x) hi, (x) + (1 go. (x)) hτ, (x)
(2)
The architecture combines three components: A
go,
+ {0,1} de-
cides whether to forward input æ through the core- certification- netwoor (go, instantiated in two different ways below). while the core-network h2. : : + y and the certification-netvee network hg, X' + y' assign output label y E y to an input z E X. We note that arbitrary network architectures and training methods can be used for each of the component networks. We evaluate some of these choices in our experimental evaluation section later.
4.1 SELECTION MECHANISM
The core of ACE is a selection mechanism that decides which network to use for inference. Ideally, the selection mechanism should pass inputs for which the pertifcaationneetoor. is correct and cer- tifiably robust through the certification-netoors and all other inputs through the core-network. To train this mechanism, we the following selection target for each sample in the training set:
(h. a) cert _ (x)), k,,,.)
The output of the binary function cert, explained in Section 3 is if and only if we can certify that network ngg classifies all inputs from the region (xx) to a label
If the separation described above were fully accurate and certifiable, the certifiable robustness of the sertficcationnnetoork would be retained by the combined network, while the natural accuracy and adversarial robustness would be lower bounded by those of the core-network. However, as the task of predicting certifiable correctness is strictly more difficult variant of the meta recognition task (Scheirer et al.) 2012). a perfect selection is usually unattainable. Here, we balance a trade- off between certifiable and natural accuracy, as a higher selection rate and consequently recall will generally increase certifiable accuracy at the cost of a larger drop in natural and adversarial accuracy. Clearly, a lower selection rate and consequently higher precision have the opposite effect. Note that, there exist perturbations 2 2/2 E B such that 9o, (21) = 0 and gu, (a²) = 1. then we would have certify the robustness of both the core- and certification-netoor avoid certifying the nore-nerwork). Thus, only if we can prove that such a pair does not exist, meaning that the selection is robust, we can certify only one of these two networks.
(we would like to
As the typically large and deep core-network tends to have very low certifiable accuracy, low robustness of the selection mechanism leads directly to low certifiable accuracy of the composed network (because we would need to certify the core-network more often). An ideal selection mech- anism has be robust, accurate, and allow tuning of the selection rate.
Towards that, we suggest two variants that fit these requirements: (i) SelectionNet, a selection- network trained on the binary selection task, and (ii) Entropy Selection, based on a threshold on the entropy of the output of the certification-network, We refer to the resulting architectures as SelectionNet ACE and Entropy ACE.
4.1.1 SELECTIONNET
We propose using a selection-network h; X - R to make the decision, which leads to the archi- tecture illustrated in Figure Ta with the following inference procedure: (i) Pass sample æ through the selection-netwer
resulting in the output hj. (x). (ii) If the output is greater than the threshold iiniictttoonnettrk...
T. the sample is passed through the certification network, and otherwise through the core-network. Formally, we define the selection mechanism as go. (a:) = I hú (#)>T-
Training After training a provable certification networkk using any choice of a provable training mechanism, we obtain the selection targets according to Equation 3 We then frame the selection
4

---

Published as a conference paper at ICLR 2021
problem binary classification task and train the selection-network network directly the inputs from the training set using the selection targets obtained above as labels. We note that for the selection- network, similarly to the certification network, training mechanism. Further, we propose to reduce the training time by using the certífication- network feature extractor and only training the last linear layer of the selection-network. This also reduces the selection overhead during inference and certification with convex relaxation based methods. The core-network trained completely independently, typically using pre-trained model.
can any network architecture and provable
4.1.2 ENTROPY SELECTION
As a second variant we propose using an entropy based selection mechanism go, (æ) := H (softmaxx(M, (a))) < <T, inspired by TTerapittayanon et al. (016)). which leads to the network architecture illustrated in Figure Tbland slightly different interence procedure:
We first map the output of the certification-networr yb = n2 (a>) to a discrete probability distribution p(ys) over the labels, via the softmax function. Then we can compute the entropy H (p(y))) as
H(p(y))) = Σ p(v), log(p(()))
j=1
If the entropy is below threshold T, return the certification- network output, otherwise pass the sample through the core-network.
Certification Using convex relaxation- based certification methods requires sound over- approximations of all layers. To derive an approximation the entropy, we first recast Equation including softmax and introduce the log-sum-exp trick improve numerical stability, as
H Hp(()) = c + log( E e
Σ Yb.j exp(yn.j c c cogo (h.
(5)
We can now construct an entropy transformer from element- transformations corresponding to individual operations in Equation [ In this work we use intervals and zonotopes (Appendix HD. however, one can explore other approximations.
We provide proof of this identity in Appendix H.6
Joint Training Using vanilla provable training for the certificationnnetoof leads significant dependence of the entropy on the difficulty of a sample perturbation. This causes wide range of possible entropies over the admissible perturbations, reducing the robustness of a thresholding based selection. To address this, we would like to decrease the width of the entropy range, while ideally decreasing the entropy for certifiable samples and increasing it for non-certifiable samples. We do this by introducing an entropy loss term L (36, ys (x)) sign(y.(z)) H (softmax(36)) using the convention s0g = 11, and the weighting factor X:
(6) We replace the cross entropy loss LCE with the joint loss Ljoint enabling adversarial and prov- able training against perturbations targeting both classification and entropy, improving selection robustness. We train the intfffaaationnetworr with this joint loss, completely independent from the core network. The selection target ys (h),,aa x) for the natural, adversarial, and robust losses is, unlike in Equation 3 computed based on the natural, adversarial, and certifiable correctness of the certification-nete netkok,,, respectively, and not always on the certifiable correctness. Using this loss with networks low accuracy has the disadvantage that the entropy loss encourages a more ambiguous output distribution for samples that not classified (provably) correctly. Therefore, perform pretraining with À 0.
Gjonn x. v) = (1 - A) LCE( + X (yb, ys (hb, x)).
4.2 BNN-TO-BNT END CERTIFICATION
After the network is trained, need to prove that the classification by the compositional network
y arg max go, (x') hig (xx) (1 ge, (x')) h/g (3));; Ya'
(x)
(7)
correct and robust (as defined by Equation []] Using one of the certification methods introduced in Section 3 to instantiate the certification function cert (X, f. v). the proof of robustness can be broken
down into the following steps:
5

---

Published as a conference paper at ICLR 2021
1. Evaluate the selection mechanism 90, on the unperturbed sample resulting in 90, (z))
2. Certify robustness of the decision of the selection mechanism ( (a:), go,, Sa, (z)).
3. If this certification was successful, certify the network selected for the unperturbed sample, otherwise certify both the core- and the pertificationnetwooff cert [ (zz), (0pp.) y).
The deep core-network is typically not trained for certifiability and certification is often computa- tionally infeasible. Therefore, we assume that certification of the core-network always fails. Conse- quently, only samples with positive natural selection decision can be certified, making certification independent of the core-network. The results of the first and the second step can be used to de- termine which network will classify the unperturbed sample and which networks could classify perturbed sample. This information can be used to compute the natural and adversarial accuracy of the combined network without evaluating them jointly.
EXPERIMENTAL EVALUATION
In this section, we demonstrate the effectiveness ACE by showing that existing certified defenses cannot achieve the high natural accuracies at non-trivial provable accuracies that we obtain.
Models and Datasets We evaluate ACE on 3 different certification-networr architectures sim- ilar to the models used in Gowal al. (2018) and [allunvić & Vechev (2020), on CIFAR-10, 10, ImageNet200, and Tinylmas FinlImaeNNet with 6 perturbations between 1/255 and 8/255, reporting Top- accuracies. Imageet
a selection of 200 classes from ImageNet with samples cropped to meaningful regions of the image and downscaled to 64 x 64. ImageNer200 is the full sized ImageNet restricted to the same 200 classes but always center cropped for evaluation. We denote as Conv2, Conv3 and Conv5 feed-forward networks with 2, 3, and 5 convolutional layers, respectively. Conv3 corresponds to the largest network from Balunovic & Vechev (200)). and Conv5 corresponds to the largest network from Zhang et al. (2020). DarLer More details be found in Appendix Ta- 3] We use an adversarially trained EfficientNet-Bi (Tan & Le 2019) with ImageNet pretraining cote-network, using adversarial instead of natural training, as we believe empirical robustness to also be relevant in domains where deterministic guarantees are desired.
Training and Certification We perform all experiments, with the exception of reference network training. single GeForce RTX 2080 Ti GPU and implement training and certification in Py PyTorch Paszke et al. (019)). We train selection- and certification networrs using IBP (Gowal et al. 2018), CROWN-IBP (Zhang et al. 2020) and COLT (Balunović & Vechev 2020). The hyperparameters can be found in Appendix [. We use adversarial pretraining for COLT trained models. For Entropy Selection we set the joint loss factor
0.5. We only use the relatively fast, convex relaxation- based certification methods IBP (Gowal et al. 2018). CROWN-IBP (Zhang et al. 2020)), and DeepZ (Singh et al. 2018) for IBP and COLT trained networks respectively, unless specified otherwise. We use 40 step PGD to evaluate adversarial accuracy, using the strategy described in Appendix E to avoid gradient masking effects (Papernot et al. 2017).
Comparison with Existing Architectures We show that ACE can, in contrast to state-of-the- art provable training methods, achieve both high natural and non-trivial provable accuracies, by enabling an efficient trade-off between natural and certifiable accuracy instead of maximizing prov- able robustness at any cost. As direct comparison with prior work is difficult, we show that using our best effort we were not able to achieve comparable combinations of natural and certifiable accuracy using the state-of-the COLT and CROWN-IBP provable training methods.
COLT computationally expensive, restricting it to relatively small models. We train the biggest model evaluated by Balunović & Vechev (200)) Conv3, on C1FAR-10 at c 2 2/255 using COLT with a varying natural loss component and use DeepZ for certification. Figure show certified vs natural accuracy for each of these models (yellow points). To compare with our approach, we train an ACE model (teal squares) using one of these networks (teal triangle) as -etttiatttiooeeeokk.... We observe that the ACE model obtains higher certified accuracies at all natural accuracies, still yielding a certified accuracy of 36.8% at the highest natural accuracy (85.1%) obtained using an individual, naturally trained Conv3 network. Using the Cony3 model trained by Balunovic & Vechev (2020)
expensivee

---

Published as a conference paper at ICLR 2021
Certifialle Accuracy. [%]]
60-
40-
Conv3, COLT DeepZ Conv3, COLT MILP, ACE
COLT DeepZ, ACE
20-
Efficientiet- 80, ADV
0-
70
100
Natural Accuracy [%]
Figure 2: Natural and certified accuracy of different COLT trained models on CIFAR-10 with 6 2/255. We compare individual Conv3 networks (yellow dots). trained with COLT and varying natural loss components, with different ACE models (squares) based on an EfficientNet-BH core- network (purple) and different certification-netoorss (triangles): Conv3 with DeepZ certification (teal) and Conv3 with MILP certification (blue). Further up and to the right is better. The horizontal distance between the yellow and teal line is the increase in natural accuracy due to using ACE instead of changing the natural loss component int COLT training.
40
Certitable Accuracy
Conv5, CIBP
20
Conv5 k50, CIBP/IBP, ACE Conv5 k0o, CIBP/IBP, ACE Conv3, IBP, ACE
20
EfficientNet-BB ADV
40
50
60 70
80
90
100
Accuracy [%]
Figure 3: Natural and certified accuracy CIFAR-10 with 6xc 8/255. We compare individ- ual Conv5 networks (yellow dots), trained with CROWN-IBP and varying natural loss components, with different ACE models (squares) based EfficientNet-BO core-network (purple) and differ- ent certification-networks (triangles): CROWN-IBP trained Conv5 from Zhang et al. (2020) (red), CROWN-IBP trained Conv5 with Kend 0.5 (teal) and IBP trained Conv3 (blue). All selection- networks are IBP trained.
(blue triangle) in combination with MILP certification as certification-netaor we obtain an even stronger ACE model (blue squares). We compare CROWN-IBP trained reference networks in Appendix yielding the same conclusion.
CROWN-IBP be applied to larger models, includes an inherent tobustness-accurace trade-off parameter k, weighting the natural and robust loss components, and outperforms COLT on CIFAR- 10 at 8/255, making it the perfect benchmark for these larger perturbations. Using the original implementation and the largest model [Zhang et al.) (2020) evaluate on CIFAR- 10, Conv5, we vary Kend to obtain several models. We show certified vs natural accuracy for each of these CROWN- IBP models (yellow points) in Figure 3 Using the Conv5 network published by Zhang et al. (2020) with Kend 0.0 (red triangle) and one we trained with Kend 0.5 (teal triangle), we train ACE models (red and teal squares) using IBP for the selection network training, which both outperform the individual Conv5 networks over a wide range of natural accuracies. Even when using much weaker sewtiffiaationnnetwwoe such an IBP trained Conv3 (blue triangle), we obtain an ACE model (blue squares) yielding more attractive trade-offs at high natural accuracies.
These results show that across different provable training and certification methods, network ar- chitectures and perturbation sizes, ACE produces much more favorable robustness-accuracy trade- offs than varying hyperparameters of existing certified defenses. ACE models can always use pertificationnnetworkk
certification network trained at the efficiency sweetspot of the employed provable training method, allowing any improvements in certified defenses be utilized, while allowing for flexibility in the trade-off between accuracy and robustness. As ACE is truly orthogonal to all of these methods, should be complement to and not replacement for provable training methods.

---

Published as a conference paper at ICLR 2021
Certifiable Accuracy
15-
WideResNet, LIRPA/IBP, ACE
DenseNet, LiRPA ResNeXt, LIRPA CNN7+8N, LiRPA EfficientNet-Bo, ADV
10
5-
40 50 60
70
Natural Accuracy [%6]
Figure 4: Natural and certified accuracy on TinyImageNer with c = 1/255. We compare the LiRPA trained networks from Xu et al. (2020) WideResNet (black triangle), DenseNet (teal), ResNeXt (yellow), and CNN7+BN (red) with an ACE model (black squares) using the same LiRPA trained WRN certificationnnetwork and feature extractor for the otherwise IBP trained selection-network. The ACE model uses an EfficientNet-BO core-network (purple).
Table I: Natural, adversarial and certifiable accuracy for various ACE models. The training methods COLT, LiRPA with loss fusion, IBP and CROWN-IBP (C-IBP) used the training of certification- (CERT) and selection-networks (SELECT) indicated separately.
Selection
ACE Training
Certification Network
Top-1 Model Accuracy [%)
Dataset
Method
CERT
SELECT
Natural
Adversarial
Certified
SelectionNet
COLT
COLT
Conv3
90.1
78.4
27.5
CIFAR-I0
265
SelectionNet
C-IBP
IBP
Conv5
80.1
48.8
10.5
265
ImageNet200
SelectionNet
COLT
COLT
Conv3
70.0
60.5
255
TinylmageNet
SelectionNet
LiRPA
IBP
WRN
50.0
35.9
10.5
265
LiRPA trained WideResNet from et
2020
used as feature extractor for selection-network.
The compositional structure ACE has the additional advantage of permitting every component network to work at different resolution. For tasks where high resolution images are available, the core network can process full-scale images, while down-scaled versions can passed through selection and certification network. For ImageNet200, to obtain a high natural (70.0%) accuracies, while the certification- and selection-networt yields non-trivial certifiable accuracy (3.1%) 6 1/255 using samples scaled down to 64 x 64. Here, the certifiable accuracy is limited by the lack of a strong certifiably robust network to use as a certification- network.
use full-scale images in the core-network
For TinylmageNet no full size images are available, reducing the advantage of an ACE model. However using the LiRPA trained WideResNet (black triangle in Figure 4 from Xu al. (2020) as certification-networkk and feature extractor for the otherwise IBP trained selection-network, we train ACE model (black squares) showing very similar trade-off characteristic as the CIFAR-10 models, demonstrating that ACE scales to larger tasks.
In Table we present results on the CIFAR-I0 and TinylmageNet datasets for selected models. An extended table showing more results can be found in Appendix
Selection Recall that the key our compo- sitional architecture is a provably robust selec- tion mechanism that can differentiate samples based on their certifiability by the certification- network. We try to certify the natural selection decision made by Conv3 selection-networt on CIFAR-10 at Eoo = 2/255 and split sam- ples into three groups: samples selected for all admissible perturbations (provably selected), samples not selected for any admissible pertur- bation (provably selsseec,,,d), and the remain- der for which cannot prove either decision
Table Certifiable accuracy of the certification- network depending on selection decision using COLT trained Conv3 selection- and certification- network for CIFAR-10 at 6 = 2/255.
Certifiable Accuracy [%]
provably selected non-provably selected
72.9
52.3
selected
28.4
full test set
47.9
8

---

Published as a conference paper at ICLR 2021
100
no adv
80
Accuracy (14)
Sample 4-
40
adv
Notw-Rebwork
Conva
Without Entrapy Loss
With Entropy Loss
Subset SelectionNet
Subset Entrapy
Width of entrapy range
Figure 5: Natural and adversarial accuracy for two ACE networks: with SelectionNet Conv3 and one with entropy selection + Conv2. We evaluate classification networks the full test set and its subsets selected by the two selection mechanisms.
Figure 6: Width of the entropy range over admissible perturbations. Samples de- noted as adversarial we can successfully attack the certification-netwrrk and non- adversarial otherwise.
(non-pun mhon-provably selected). In Table 2 we show that for the provably selected samples the certifiable accuracy (72.9%) is much higher than the full test set (47.9%). while it is much lower for the provably non-selected samples (2).4)). This shows that the selection-network successfully sepa- rates samples based certification difficulty.
Evaluating Core- and Certification-Networr Next, we train two ACE networks for CIFAR-10 with 6 = 2/255 using COLT: one with selection-network and Conv3 certification-netwee and another with entropy selection and a Conv2 certifcattionneeworr.. Both use EfficientNer-Bi core-network. We evaluate the natural and adversarial accuracy of both the core- and certification- network the full test set and its subsets selected by the selection mechanism. The results shown in Figure 5 We observe that the accuracy both certification-networks is significantly higher on their respective selected datasets, while the accuracy of the core-nete nete-networks decreases. This indicates that the selection mechanism can successfully separate samples by classification difficulty and assign easier samples the certification- and more difficult samples to the core-network.
Effectiveness of the Entropy Loss Recall that we introduced the entropy loss to make Entropy Selection more robust, by decreasing the sensitivity to different perturbations. To assess its effec- tiveness, we train two Conv2 certification crrtifiattionnettoork using COLT for CIFAR- 10 with 6 = 2/255, with and without entropy loss. Note that using entropy loss corresponds to À 0.5 and not using it corresponds to X = 0.0 in Equation 6 We split the test set into two groups based on whether an adversarial attack on the certificationnnetwork is successful (adversarial) or not (non-adversarial), For each sample, compute the difference between the largest and the smallest entropy that can be obtained by perturbing it. Figure|6]show histograms of these differences (or widths) for both the adversarial and con-adversarial group. Clearly, the non-adversarial samples lead to much narrower entropy ranges if an entropy loss was used, while there no significant difference if no entropy loss used. This demonstrates that the entropy loss successfully increased the robustness of the entropy selection mechanism for non-adversarial samples (as adversarial ones are not certifiable anyway).
6 CONCLUSION
We proposed a new architecture that boosts the certifiable robustness of any state-of-the-art net- work, while retaining high accuracy and without requiring retraining. The key idea is to combine this network with provably trained certification-networr and certifiable selection mechanism, which adaptively decides inference-time which of the two networks use. We presented two such selection mechanisms with corresponding training and certification methods. Our experiments show that using this method, one can achieve both high natural accuracies and non-trivial certifi- able robustness, beyond the reach of state-of-the-ar certified defenses. Our architecture is also fully orthogonal certified defenses, allowing any advances this field to carried over directly.

---

Published as a conference paper at ICLR 2021
REFERENCES
Anish Athalye. Nicholas Carlini, and David Wagner. Obfuscated gradients give false sense of security: Cireumventing defenses to adversarial examples. arXiv preprint 10Xiv:8802.002000 2018.
Mislav Balunović and Martin Vechev. Adversarial training and provable defenses: Bridging the gap. In International Conference on Learning Representations, 2020.
Mislav Balunović, Maximilian Baader, Gagandeep Singh, Timon Gehr, and Martin Vechev. Certi- fying geometric robustness of neural networks. In Advances in Neural Information Processing Systems, 2019.
Tolga Bolukbasi, Joseph Wang, Ofer Dekel, and Venkatesh Saligrama. Adaptive neural networks for efficient inference. arXiv preprint
2017.
Rudy Bunel, llker Turkaslan, Philip Torr, Pushmeet Kohli, and Pawan K Mudigonda. A unified view of piecewise linear neural network verification. In Advances in Neural Information Process- ing Systems, pp. 4790-4799, 2018.
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. Proceedings of the 36th International Conference on Machine Learning, 2019.
Mare Fischer, Maximilian Baader, and Martin Vechev. Certification of semantic perturbations via randomized smoothing. arXiv preprint arXiv:2002. 2020.
Timon Gehr, Matthew Mirman, Dana Drachsler- Cohen, Petar Tsankov, Swarat Chaudhuri, and Mar- tin Vechev. Ai2: Safety and robustness certification neural networks with abstract interpreta- tion. In 2018 IEEE Symposium Security and Privacy (SP), pp. 3-18. IEEE, 2018.
Khalil Ghorbal, Eric Goubault, and Sylvie Putot. The zonotope abstract domain taylorl++ In Inter- national Conference on Computer Aided Verification, pp. 627-633. Springer, 2009.
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 arXiv: 18100 2018.
Guy Katz, Clark Barrett, David I. Dill, Kyle Julian, and Mykel Kochenderfer. Reluplex: An efficient smt solver for verifying deep neural networks. In International Conference Computer Aided Verification, pp. 97-117. Springer. 2017.
Mathias Lecuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified robustness to adversarial examples with differential privacy. 2019 IEEE Symposium on Security and Privacy (S&P), 2018.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant adversarial attacks, arXiv preprint arXiv:1706.0660 06083, 2017.
Mason McGill and Pietro Perona. Deciding how to decide: Dynamic routing in artificial neural networks. arXiv preprint 1033v:1703.06217 2017.
Matthew Mirman, Timon Gehr, and Martin Vechev. Differentiable abstract interpretation for prov-
ably robust neural networks. In International Conference on Machine Learning, 2018.
Jeet Mohapatra, Tsui-Wei Wei Weng, Pin-Yu Chen, Sijia Liu, and Luca Daniel. Towards verifying robustness of neural networks against family of semantic perturbations. In Proceedings of the JEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 244-252, 2020.
Nicolas Papernot, Patrick McDaniel, Ian Goodfellow. Somesh Jha, Z Berkay Celik, and Ananthram Swami. Practical black-bor box attacks against machine learning. In Proceedings of the 2017 ACM Asia conference computer and communications security, pp. 506-519, 2017.
10

---

Published as a conference paper at ICLR 2021
Adam Paszke, Sam Gross, Francisco Massa, Adam Lever, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high- performance deep learning library. In Advances in neural information processing systems, pp- 8026-8037, 2019.
Aditi Raghunathan, Jacob Steinhardt, and Percy Liang. Certified defenses against adversarial exam- ples. In International Conference on Learning Reprexentations, 2018.
Hadi Salman, Greg Yang. Jerry Li, Pengchuan Zhang, Huan Zhang, Ilya Razenshteyn, and Sebastien Bubeck. Provably robust deep learning via adversarially trained smoothed classifiers. arXiv preprint arXiv:1906.045:0 2019a.
Hadi Salman, Greg Yang, Huan Zhang, Cho-Jui Hsieh, and Pengchuan Zhang. A convex relaxation barrier to tight robustness verification of neural networks. Advances in Neural Information Processing Systems, pp. 9035-993--80 9846, 2019b.
Walter Scheirer, Anderson de Rezende Rocha, Jonathan Parris, and Terrance Boult. Learning for recognnnnnnn IEEE Transactions on Information Forensics and Security, 1(4):1214-1224, 2012.
Gagandeep Singh, Timon Gehr, Matthew Mirman, Markus Püschel, and Martin Vechev. Fast and effective robustness certification. In Advances in Neural Information Processing Systems, pp. 10802-10813, 2018.
Gagandeep Singh, Rupanshu Ganvir, Markus Púschel, and Martin Vechev. Beyond the single neuron convex barrier for neural network certification. Advances Neural Information Processing Systems, 2019.
Mingxing Tan and Quoe Le. Efficientnet: Rethinking model scaling for convolutional neural networks. arXiv preprint arXiv: /9t1//995./996,,,.. 2019.
Surat Teerapittayanon, Bradley McDanel, and Hsiang- Kung. Branchynet: Fast inference via early exiting from deep neural networks. 2016 23rd International Conference on Pattern Recognition (ICPR), pp. 2464-2469, IEEE, 2016.
Vincent Tjeng, Kai Xiao, and Russ Tedrake. Evaluating robustness of neural networks with mixed integer programming. arXiv preprint arXiv:1711.073366 2017.
Florian Tramer, Nicholas Carlini, Wieland Brendel, and Aleksander Madry. On adaptive attacks to adversarial example defenses. arXiv preprint arXiv:2002.083447 2020.
Shiqi Wang. Kexin Pei, Justin Whitchouse, Junfeng Yang. and Suman Jana. Efficient formal safety analysis of neural networks. In Advances in Neural Information Processing Systems, pp. 6367- 6377, 2018a.
Xin Wang, Fisher Yu, Zi-Yi Dou, Trevor Darrell, and Joseph Gonzalez. Skipnet: Learning dy- namic routing in convolutional networks. In Proceedings of the European Conference on Com- puter Vision (ECCV), pp. 409 424, 2018b.
Tsui- Wei Weng, Huan Zhang, Hongge Chen, Zhao Song, Cho-Jui Hsieh, Duane Boning, Inderjit Dhillon, and Luca Daniel. Towards fast computation of certified robustness for relu networks. arXiv preprint 1804:0880099999 2018
Eric Wong and Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In Proceedings of the 35th International Conference on Machine Learning. PMLR, 2018.
Eric Wong, Frank Schmidt, Jan Hendrik Metzen, and J. Zico Kolter. Scaling provable adversarial defenses. In Advances in Neural Information Processing Systems 31. 2018.
Kaidi Xu, Zhouxing Shi, Huan Zhang, Minlie Huang, Kai- Wei Chang, Bhavya Kailkhura, Xue Lin, and Cho-Jui Hsich. Automatic perturbation analysis on general computational graphs. arXiv preprint a a00iv:2002. /2920, 2020.
11

---

Published as a conference paper at ICLR 2021
Huan Zhang, Tsui-We Wei Weng. Pin- Yu Chen, Cho-Jui Hsieh, and Luca Daniel. Efficient neural net- work robustness certification with general activation functions. In Advances in neural information processing systems, 2018.
Huan Zhang, Hongge Chen, Chaowei Xiao, Sven Gowal, Robert Stanforth, Bo Li, Duane Boning, and Cho-Jui Hsieh. Towards stable and efficient training of verifiably robust neural networks. In International Conference on Learning Representations. 2020.
12

---

Published as a conference paper at ICLR 2021
A NETWORK ARCHITECTURES
In Table 3 we list the detailed architectures for CIFAR-10 and ImageNet200, respectively, used in the experiments described in Section The Conv3 architecture for CIFAR-10 identical to the largest network from Balunović & Vechev (2020).
Table 3: Network architectures of the certification- and selection-networks used for CIFAR- 10 and ImageNet200 (Conv3 (IN)). All layers are followed by a ReLU activation. The last fully connected layer is omitted. For Conv3 (IN) global average pooling layer precedes this last linear layer. "CONV с h x w/s" corresponds to a 2D convolution with output channels, a hxw w kernel size, and a stride of in both dimensions.
Conv2
Conv3
Conv5
Conv3 (IN)
CONY 32 4x4/2
CONV 32 3/3/1
CONV 64 3/1
CONY 32 5
CONV 32 4x4/2
CONV 32 4x4/2
CONV 64 3/1
CONV 64 5
FC 200
CONV 128 4x//
CONV 128 3x3/2
CONV 128 5
FC 250
CONV 128 3x3/1
CONV 128 3x3/1
FC 512
B TRAINING HYPERPARAMETERS
CIFAR-10 Training For CIFAR-I0 IBP training is conducted for 200 epochs, annealing and over the first 100 epochs, with an initial learning rate of 1e-3, reducing by half every 10 epochs after annealing is completed. We choose Kend 0.5 for all models. COLT training is conducted for 40 epochs per stage with an initial learning rate of le-3, decreasing by a factor of 0.75 between stages and by factor of 0.5 every epochs after an initial loss mixing period of epochs.
ImageNet Training For IBP training ImageNet200 and TinylmageNet we train for 50 epochs using a batch size of 100, an initial learning rate of 1e-3, reducing it by half every 5 epochs after annealing both and for 10 epochs. We choose Kend 0.5 for all models. For COLT training on ImageNe1200 we use feature extraction and freeze all weights up to the last linear layer. We train for 20 epochs per stage, using an initial learning rate of le-3, reduced by factor of 0.75 between stages and 0.5 every 3 epochs after an initial loss mixing period of 5 epochs.
C ADDITIONAL EXPERIMENTS COMPARING WITH CROWN-IBP
In this section we present additional experiments comparing ACE models with CROWN-IBP.
CROWN-IBP trained networks can not match the performance of COLT trained and MILP certified networks CIFAR-10 10 at 6xo- 2/255 (Balunović & Vechev 2020 Zhang et al. 2020). However, as their certification is notably cheaper, we still compare their approach in isolation to an ACE compositional using the largest model/Zhang et al. (2020) evaluate CIFAR-10, Conv5. We follow their instructions for multi GPU training and obtain several models by varying the parameter Rend (yellow dots in Figure 7. obtaining very similar results for the settings they report (Send E (0, 0.5)). Note that every setpoint requires about 4 GPU days, while training an ACE model on top of an available certification-netwee
only takes few hours and new setpoints can be evaluated in minutes. In Figure 7 we show certifiable vs natural accuracy for each of these CROWN-IBP models (yellow points). To compare it with our method, we chose the CROWN-IBP trained Conv5 with Kend = 0.5 as sertificationnnetoor (teal triangle) and use it to train our ACE models with various thresholds T, shown as teal squares in Figure 7 Clearly, our models achieve much better robustness-accuracy trade-offs, especially in regions of high natural accuracy. We do not compare the CROWN-IBP results to those obtained using MILP in the abstract, as the latter requires a much more expensive certification approach. However,
when using a much weaker certification network, such as an IBP trained Conv3 (black triangle), we can still train ACE models (black squares) obtaining more attractive trade-offs high natural accuracies.
13

---

Published as a conference paper at ICLR 2021
Certifiable Accuracy [%]
60
40
Conv5, CROWN-IBP CROWN-IBP, Conv3, IBP, ACE
20
EfficientNet-BO, ADV
60
70
75
85
90
95
100
Natural Accuracy [%)
Figure 7: Natural and certified accuracy CIFAR-I0 with Exc 2/255. We compare individual Conv5 networks (yellow dots), trained with CROWN-IBP and varying natural loss components, with different ACE models (squares) based EfficientNet-BO core-network (purple) and different perificattionnnetwrkks (triangles): CROWN-IBP trained Conv5 (teal) and IBP trained Conv3 (black). Further up and the right is better.
D ADDITIONAL EXPERIMENTS ON COLT TRAINED ACE MODELS
In this section we describe additional experiments using COLT trained Conv3 networks.
We use the Conv3 network published by Balunovic & Vechev 2020) and certify it using DeepZ (Singh et al. 2018) and MILP (Tjeng et al. (2017). To unlock the full potential of this MILP certified certificaiton network, we would ideally want to train our selection network with MILP based labels. However, certifying the whole or significant portion of the training set using MILP is infeasible. Therefore, we have to use surrogate labels when training the selection-network We evaluate three approaches to training selection network and present the results Figure 8
Transfer the selection network of different ACE model based certification-network with higher zonotope certified accuracy (teal)
Compute selection labels using zonotope certification (brown)
Compute selection labels using adversarial correctness (yellow)
We observe that using the last approach consistently, over a range of selection rates, performs worse than both other methods, suggesting that the selection network can learn features that make sam- ple hard to certify while not necessarily leading to successful adversarial attacks. Interestingly, the selection network transferred from a different Conv3 network (with higher zonotope certified ac- curacy), does not only help to improve the performance of the ACE model at high natural accuracies when certified using MILP, but also when using DeepZ. This suggests that the properties making a sample difficult to certify show at least some level of stability over different networks.
E ADVERSARIAL ACCURACY COMPUTATION
The adversarial accuracies listed in Table are intended to be purely informative and not to be considered as a strong indicator the true robust accuracy. Nevertheless, we consider the poten- tial problem of gradient masking (Papernot et al. 2017) caused by the compositional structure and developed the following three approaches to calculate adversarial accuracy:
We compute separate adversarial samples attacking the core-, sclection- and certification- network. If we find any perturbation leading to the selection of classification network, we consider it reachable and evaluate the corresponding adversarial example. Only if no attack on a reachable network is successful, we consider the adversarial attack to have failed. Note, that successful adversarial example either classification network would not necessarily be classified by this network. Therefore, this approach does not provide true upper bound to the robust accuracy.
We attack the classification networks described above, but use certifiable instead of empirical reachability, that is consider a network reachable unless we can proof that it can not be reached. This approach provides an even conservative adversarial accuracy.
14

---

Published as a conference paper at ICLR 2021
50
Certifiable Accuracy (96
40-
Transfer, MILP Cert. MILP
30-
Transfer, DeepZ
20
Cert. DeepZ
Adv, DeepZ
10
0
84
86
88
90
92
94
Natural Accuracy [%]
Figure 8: Natural and certified accuracy on CIFAR- 10 at c.o = 2/255. ACE networks using a COLT trained Conv3 network directly from Balunovie & Vechev (2020) certification network and three different selection networks, certified using Deep2. (dots) or MILP (squares) networks transferred from different Conv3 network (teal), trained on certifiable correctness (brown) and on adversarial correctness (yellow).
We compute two adversarial attacks. One aimed at the core- and the other the certification-networr To this end, we combine the classification networks loss term with loss component from the selection network, designed to perturb the sample such that the currently targeted network gets selected. We only consider an attack successful, an adversarial example gets classified incorrectly by the compositional network. To reduce the gradient obfuscation problem in this setting, we weight the selection network loss term based on whether we already select the currently targeted network.
While the gap between the first two approaches is usually very small at less than 1%, the third approach sometimes yields notably higher adversarial accuracies. Therefore, we decided report the most conservative numbers, obtained using the second approach. We use PGD with 40 steps, step size of 0.035 and one restart with random initialization of the perturbation.
F NATURAL AND ADVERSARIAL CORE NETWORKS
In this section, we compare ACE models obtained using naturally and adversarially trained core- networks.
In both cases we use an EfficientNet-BO with ImageNet pretraining. On CIFAR-10 Goo 2/255, natural training leads to a natural accuracy of 97.4% but only 6.7% of adversarial accuracy, while FigureDww we show certified over natural
adversarial training yields 95.1% 1% and 85.6%, respectively. accuracy and compare individual Conv3 networks (yellow dots), trained with COLT and varying natural loss components, with ACE models (squares) using the same Conv3 certificationnnetoorf (triangles), but different core-networks. The ACE model with naturally trained core-network is shown in blue and that with an adversarially trained core-network in teal. At very high natural accuracies the relative drop in natural accuracy from core-network to ACE model is significantly higher when naturally trained core-network is used. This permits a much higher selection rate, leading to a significant increase in certified accuracy for any given natural accuracy. Despite these improvements, we maintain that using an adversarially trained core network is more representative of potential real world usage, where empirical robustness guarantees also considered.
G RESULTS ON SELECTED SETPOINTS
In Table 4 present selected setpoints of ACE models trained CIFAR-10, TinyImageNet and ImageNet200, demonstrating that ACE can be applied to a range of models, datasets and provable training methods.
15

---

Published as a conference paper at ICLR 2021
Certifiable Accuracy
40-
Conv3, COLT DeepZ
Conv3, COLT DeepZ, ACE,
Conv3, COLT DeepZ, ACE_adv
EfficientNet-B0 NAT
20
EfficientNet-BB
70 75
80
85 90
95
100
Natural Accurary [%)]
Figure 9: Natural and certified accuracy of different COLT trained models CIFAR-10 with Coo = 2/255. We compare individual Conv3 networks (yellow dots), trained with COLT and varying natural loss components, with ACE models (squares) using the same Conv3 certification-networf (triangles), but different core-networks: a naturally trained EfficientNet-BO (blue) and an adversari- ally trained EfficientNet-BO (teal).
Table 4: Natural, adversarial and certifiable accuracy for various ACE models. The training methods COLT, LiRPA with loss fusion, IBP and CROWN-IBP (C-IBP) used for the training of certification- (CERT) and delection-networgg (SELECT) are indicated separately.
Selection
ACE Training
Certification Network
Top-1
Model Accuracy [%]
Dataset
Method
CERT
SELECT
Natural
Adversarial
Certified
COLT
COLT
Conv2
90.4
79.0
20.5
COLT
COLT
Conv3
90.1
78.4
27.5
SelectionNet
IBP
IBP
Conv3
90.5
80.5
18.5
206
C-IBP
C-IBP
Conv5
88.6
77.6
25.6
CIFAR-10
COLT
Conv2
93.4
85.1
19.4
Entropy
IBP
Conv2
90.2
71.7
7.2
COLT
COLT
Conv3
77.1
46.7
7.4
SelectionNet
IBP
IBP
Conv3
83.1
49.9
6.4
255
C-IBP
IBP
Conv5
80.1
48.8
10.5
COLT
COLT
Conv3
70.0
60.5
3.1
ImageNet200
SelectionNet
255
IBP
IBP
Conv3
68.3
57.4
3.8
TinyImageNet
SelectionNet
LiRPA
IBP
WRN
50.0
35.9
10.5
Evaluated using MILP certification Tieng al 2017 on the first 1000 samples of the test set.
LiRPA trained WideResNer from et al. 2020 used as feature extractor for the selection-network.
H ZONOTOPE TRANSFORMERS
For both training and certification with convex relaxations is essential to have precise, also called tight, transformers to reduce the accumulation of errors. Singh et al. (2018) provide such trans- formers for the ReLU, tanh and sigmoid function. this section a general approach to construct- ing transformers for the zonotope domain and Cl continuous, concave be described and transformers for the exponential and logarithm function, and the product of two zonotopes introduced. These then be combined into transformer for the entropy function.
convex functions will
H. ZONOTOPE DOMAIN
The zonotope domain Ghorbal et al. (2009) classic numeric abstract domain, shown to be suit- able as convex relaxation for analyzing neural networks Gehr et al. (2018). it is exact for affine transformations and efficient abstract transformers for the ReLU, sigmoid and tanh function exist
Singh al. (201)). A zonotope Z RR approximation of n-dimensional variable R is described by an affine form é for every dimension æÿ as
8 = =000 +
aji Gr
Ojs E, G3 6 [-1,1
(8)
16

---

Published as a conference paper at ICLR 2021
with the center coefficient d, error coefficients aj and shared enror terms 4, These shared error terms allow the representation of implicit dependencies between dimensions and make the zonotope domain strictly more powerful then the interval domain (equivalence is given for diagonal error matrix). Further, the matrix notation
= ag + Ac,
ag <R"xl A E R"XP, ,ce [-1,1]
(9)
makes affine transformations of the form y Bæ + very simple to apply:
y = B in +ct (BAm) c= aoiin + Aoute
(10)
a0.oout
Aout
H.2 GENERAL TRANSFORMER CONSTRUCTION
Sound ncuron- wiis transformers for the zonotope domain can be visualized in the input-output- plane of the to be approximated function parallelograms with vertical left and right edges, fully enclosing the function on the input interval. They can be described as
ú وy + & + PyCp+1
(11)
for the didmensoo of the input zonotope à with p error terms and the neuron-Glimension-wis. parameters slope Xj. offset E and looseness μij
The height of the parallelogram 2p, corresponds to the magnitude of the new error term. As the width is only dependent the range of the imput, the parallelogram' 's area is only dependent this height. A transformer is strictly more precise than another, the parallelogram representation of the former is fully enclosed in the one of the latter. While smaller area generally corresponds to smaller loss of precision, no guarantees can be given.
Viability shall be defined the absence of strictly more precise transformers of the same form. The looseness of viable transformers is uniquely determined by the slope X, as the offset & and can be chosen so that both the upper and lower edges touch the function plot in least one point. All transformers with different offsets and looseness but the same slope will enclose this viable transformer and are therefore strictly less precise.
If one of these contact point lies within the input interval x E [att, rubl, the slope is by definition a subgradients to the function at this point. If one contact points lie on the borders of the input interval, the slope can be reduced/increased in the direction of the local one-sided gradient until either is the tangent to that point or an additional contact point is made. The new slope is in both cases by definition subgradient to the function on the input domain at both contact points. This new transformer is also strictly more precise than the original one. It follows, that all viable slopes subgradients the function at one point in the interval.
Convexity can be assumed without loss of generality for convex and concave functions as the latter can be negated ensure convexity, For convex, C³ continuous functions all tangents to the curve of the function yield viable transformers, consequently they can be parametrized by the x- position Tib < S Fub of the contact point. Using the mean value theorem and convexity it follows that there will be a point ferit where the upper edge of the parallelogram will connect the lower and upper endpoints of the graph. For < ferst it will make contact on the upper endpoint and for t > ferit on the lower endpoint. This allows to describe the parameters X, & and of zonotope transformer for an element-wise function f(x) R - R on the interval [zw,, Fubl as
ft)
(12)
1(1) N [f(w)
Am
if 2 torit
(13)
(T(ut) ATau:
if tarit
1 / =
Xt f(t) + [((W) A016.
if > terit
(14)
(I(xu) Arru:
if terit
f (wuss) ((116)
Vuf V=)())la=tow)
(15)
Pub Ibb
17

---

Published as a conference paper at ICLR 2021
Minimum Area Transformer A minimum area transformer now be derived by minimizing the looseness y for 2ibb $ E terit and terit I t I Zub. This yields the constrained optimization problems:
min (((1(1 Inb) - [(() + ((Snb)
s.t. t 2 3/bb
t S teri
(16)
2 min [t(t) - -i1) - -f(t) + f(xw)
8.1. Lerits
1 S Tuh
(17)
These can be solved using the method of Lagrange multipliers. Equation function:
16 yields the Lagrangian
C(t,7) 2 (f(())t -wbb) f(t) + fzzw)) 7) xm.) + 122(t terie)
(18)
vel(t, (f" -mub) + (((((= - 7 o
(19)
V 7, [(t, 7) =t =t rib 1
(20)
V 7x, =t terit" 0
(21)
As 2/b < terst < Tub. at most one of the two constraints can be active at any time. This yields three cases:
Case 1: neither constraint is active, 72 722 0
v,C(t,7) = ("(t)
(t - Iub) =
20 convex
>0 strictly
t = Jub
6 t terit
(f2) =
+ saddlepoint
Case 2: 1 rib; 71 * 0, =0
`11 = (1 (Tw)) - xubb)
t3 = 2/b & Vep(t)ll=an = (x10 (In Inb) S 0 = boundary maximum
20
<0
Case 3: t terit, 71 0,,2
1
72 2 (f" (2 Iab)
t4 = terit Vep(())l=teri
(terri)t (terit Rub) S 0 + boundary minimum
20
50
Analogously, equation 17 yields a boundary minimum t ferit. Consequently t taris yields the minimum area transformer for convex functions. ferit can be computed either analytically or numerically by solving equation 15 as the point where the local gradient is equal to the mean gradient over the whole interval. It can be observed that this yields the same slope as the minimum area transformer for the ReLU function (Singh al. (2018) even though this derivation can not be applied there directly due to the ReLU functions C* discontinuity.
H.3 EXPONENTIAL TRANSFORMER
The exponential function has the feature that its output is always strictly positive, which is important when used as input to the logarithmic function to compute the entropy. Therefore, guarantee of positivity for the output zonotope desirable. constraint yielding such a guarantee can be obtained by inserting ; Tib, pp+1 sign((u) and ùJ 2 O with X(t) = e into equation 11
1
< Azn +
2 (f(t) - At + f(Eus Akwx)) - 2 (At - -(() + f(wwb - Aa
< Max - 1) + f(1)
0 5 e' c(( - +
t $ + Zib terit,2
(22)
18

---

Published as a conference paper at ICLR 2021
This constitutes the additional upper limit terit,2 on Therefore it is sufficient to reevaluate 16 as will either inactive in equation| if terat S teraz for the solutions computed previously or the constraints will be insatiable ensuring that [7 will have solutions. If strictly positive output is required a small delta can simply be subtracted from the upper limit lrra,. It is easy to see that is now constrained [2i6, min(Tab, f and that the minimum
solution will be obtained with e"uub-=""
topt min(tera, tera,,)) The critical points can be computed explicitly ferit log(
aus #us-aij
and ferit,2 = Fi 1. This can be inserted into equations [T to [4 obtain positive, sound and viable transformer. This transformer is visualized for different choices of f. in figure T0
Figure 10: Illustration of the transformer for the exponential function for, from left to right t 2/b> minimum area: lerits = Fab and minimum area while strictly positive: Lerit,2
If there is no point in the input interval where the gradient the to be approximated function is O, as is always the case for the exponential function, the box transformer is not a viable zonotope transformer. the viable transformer with the smallest gradient at 216 is strictly more precise than the box transformer (cf. figure 10)
H.4 LOGARITHMIC TRANSFORMER
The logarithmic transformer can be constructed by plugging f(t) -log(t) and f'(t) -1 into equations 12 to 14 and their results into equation Equation 15 can be solved to terit 2tt Sub In(zu) - The resulting transformer visualized figure becomes apparent that the choice of À can have significant impact on the looseness of the oblained transformer.
x
4-
2-
-2
-4
Figure 11: Illustration of the transformer for the logarithmic function for, from left to right 2ib> minimum area: i. lorit and f. Fub-
Similar to the exponential transformer, the box transformer is not viable logarithmic zonotope transformer, but the viable transformer with the smallest gradient at Tab is strictly more precise than the box transformer (ef. figure IT).
19

---

Published as a conference paper at ICLR 2021
H.5 PRODUCT TRANSFORMER
The pointwise or Hadamard product is different from the previously introduced transformers as it involves two zonotopes instead of just one. For this derivation the two one-dimensional zonotopes and 2 with shared error terms and k and k2 individual error terms shall be considered. Typically, error terms will be shared up to a certain index (potentially 0) and all following error terms will be individual one of the zonotopes. In any case this form can obtained by reordering the error terms and can therefore be assumed without loss of generality.
61
61
:
ag Aind
Cp cp+1
+Bin
Cp cpti++1
0o, bo E R, Aind E Bptki BBid Beth
:
Epthi
Epthitke
shared eгrоr vector with q - p + l2 error terms be obtained, by concatenating the individual eπrо terms of the second zonotope 2 to the error vector of the first and padding the error coefficient matrices correspondingly with zeros:
A
T
ind
0
f 0gg +
Ept
ag AR, 1-1,1
0
A
1
61
:
bp
Cp
0
8 60 +
ER []1
bp+1
+p
6 bpt
Eq
Now the Hadamard product can be written
f' - 0 2 ag
by
(ao + AD + TAB
(23)
(+)
(+) = Σ bbb
2 +
+Σ
(a,by + axbi) E
(24)
i j=it1
E|O.1]
E(-1.1)
20

---

Published as a conference paper at ICLR 2021
To bring d' into zonotope form y. the term 24 has to be approximated by adding term c--1 with the error coefficient Cy+1 and a constant c/-
c4+1 = 2 Σ
laşbal +
Σ
Σ 1=1-1
Læbby + aabal
(25)
% = 2 asb;
Σ
(26)
9 = (6 + c
C'
c
(27)
Ep+1
Cnew
Unfortunately evaluating equation 25 and 26 is quadratic in the number of error terms in time and when using matrix formulation utilizing GPU vector operations in space. When the number of emorr terms is too high and using the transformer described above becomes infeasible, a switch to the box transformer possible:
Mts min (11b
Dlu2tbs Rub2ibb Tub
(28)
Fub max 21b.
Tbb FubZubb)
(29)
1 Yub + Ydb
Yub
Vib
Enewr
knew
E [-1,1]]
(30)
2
H.6 ENTROPY TRANSFORMER
Based on these elementary transformers, the entropy transformer can be assembled by chaining transformers for the individual component functions according to equation 5 which is reproduced below for convenience.
e
e
H(y) Σ
log(
E, et
Ex ctli
Σ Ells
(y/ - log Σ e
Ej etli
eVi
log(
elii Σ y1
Σ, E3
log(
cVi) Σ Uj exp(y; - loog( Σ chhi)
c log( Σ e Σ 81 exp(y, log( Σ eui-c)
The second term requires four transformers (product, exponential, logarithmic, exponential) adding Relass error terms (Nelass, Relass. 1, Necaas)) to the output. Since the log-sum-exp term has to be computed only once the first term does not add any additional error terms, while still increasing corresponding error coefficients.
H.6.1 TIGHTNESS
The tightness of the entropy transformer was evaluated in comparison box transformer and an upper bound obtained from an optimization approach. To compute the looseness, random input zonotopes with fully populated error coefficient matrices drawn from A' o²) and centre coef- ficients drawn from (1, were created and then propagated through an entropy transformer. before the looseness was computed as the difference between upper and lower bounds. When an in- put box required, the zonotopes where converted to box representation with the same bounds. The mean over 50 samples is reported. The following five different transformer versions were con- sidered:
21

---

Published as a conference paper at ICLR 2021
Zonolter - The zonotope transformer obtained by chaining the previously introduced trans- formers and optimizing the slopes À of all transformers sample- wise to minimize looseness.
ZonolterLM As Zonolter, but using the box transformer for the product to obtain a low memory requirement transformer.
Zono - As Zonolter, but using minimum area slopes instead.
ZonoLM - As Zono, ut using the box transformer for the product to obtain a low memory
requirement transformer.
Box The transformer obtained by using interval arithmetic to propagate bounds.
An analysis of the looseness over input error size, illustrated in figure 12 shows that while the box transformer is clearly the least precise over the whole domain, different errors dominated the behaviour of the various zonotope transformers in different regimes.
The high looseness of Zono and ZonoLM large input errors suggest that minimum area slopes are not ideal in this regime, while the small penalty for switching to the low memory versions indicates that the error terms incurred from the product transformer are small by comparison the log and exp contributions. Reducing the input errors on step, flips this behaviour. The product error dominates differences between minimum area and optimized slopes by a significant margin.
102
looseness bounds on entropy
10
109
10-1
10-2
adv
10-3
zono iter
zono iter [m
10
zono
10-5
zono Jm
box
10-6
10
10 3
std of input zono errors
Figure 12: Comparison of the looseness of various versions of the entropy transformer over the standard deviation a. of the entries of the input zonotope error coefficient matrix drawn from the distribution A(0, o²). Adv is a lower bound to the optimal looseness obtained by adversarially attacking the input region, described by the input zonotope.
22


Reviews:
[{"review_id": "f9zniUAE9E", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper focuses on improving the standard (clean) accuracy for certifiably\nrobust models.  To achieve good certified accuracy, previous works typically\nmake the standard accuracy much worse than naturally trained models. The\nauthors propose a selection mechanism to choose between a certified model with\nlow clean accuracy and a naturally trained model with high clean accuracy.  At\na high level, when the certified model cannot certify, there is no point to use\nit for classification. A naturally trained model (which cannot be certified as\nwell) is selected to improve standard accuracy.\n\nStrengths:\n\nMost previous works on certified defense focus on improving certified accuracy,\nand standard accuracy is usually sacrificed. This paper focuses on a different\nand important setting where high standard accuracy is desired, which is\nneglected by many previous works. I think this is a good step.\n\nThe proposed selection scheme can balance a certifiably robust model with a\nnaturally trained but highly accurate model. Such a combination can be helpful\nin the settings where high prediction accuracy is required.\n\nThe proposed method is technically sound. Using a certified selector makes the\nwhole network certified when it chooses the certified network. To improve clean\naccuracy, The core network is used when the certified selector chooses the core\nnetwork (i.e., the selector believes the certified network cannot make a good\nprediction on this example) or cannot certify.\n\nThe paper overall is well motivated and organized.\n\nIssues and questions:\n\nAt a high level, this certification scheme does not improve certified accuracy\n(it only makes it worse); it only helps with the verified accuracy vs. clean\naccuracy trade-off.  Thus, a crucial part of evaluation is to show the verified\naccuracy vs.  clean accuracy tradeoff.  However, it is not well demonstrated in\nthe experiments. Especially, I think results Table 1 are not so useful because\nwe can't see how the baseline certified defense models perform and cannot see\nthis tradeoff. Also, the certified accuracy numbers are really low compared to\nother works, and sometimes close to 0 (e.g., on ImageNet-200 only 3% accuracy).\nThus, it is important to show a tradeoff figure here.\n\nI recommend using figures similar to Figure 2 to present the results for all\nsettings (CIFAR 2/255 and 8/255; downscaled ImageNet-200 at 1/255) (but be\naware Figure 2 has its own issues, see comments below). Importantly, we should\nfix a well known certified model (e.g., COLT or CROWN-IBP) and then, apply ACE\nwith different thresholds to see how the clean accuracy improves with dropped\nverified accuracy.  For CIFAR, COLT or CROWN-IBP pretrained models can be used\nas the base certified model.  For Imagenet-200, I found a recent work [1]\npresented certified defense models on 64*64 TinyImageNet and ImageNet datasets\nwhich can be helpful. They reported around 15% certified accuracy and also uses\nmuch larger model structures which should improve the results in this paper by\nusing their pretrained models as the base certified model for selection (I\ndoubt the simple CNN models in this paper are sufficient for ImageNet). Again,\nthe trade-off part is the most important results to see in this paper, which is\nnot well demonstrated.\n\nFigure 2 made a misleading comparison because the ACE based methods are using\nCOLT as the base certified classifier and it is inappropriate to compare it to\nCROWN-IBP with different kappas. We should either also use COLT trained with\ndifferent weights on natural loss (similar to the kappa in CROWN-IBP) to see\nthis tradeoff, or use CROWN-IBP as the base certified classifier in this\nfigure.  Especially, in the CIFAR 2/255 setting, COLT achieves better clean\naccuracy than CROWN-IBP, so this gives ACE an advantage in this comparison, and\nthe claim that ACE achieves a better trade-off than using the tuned kappa\nparameters in (CROWN-)IBP training cannot be justified.\n\nIt also seems to me that in Figure 2 the CIFAR 2/255 CROWN-IBP numbers are much\nworse than the ones reported in CROWN-IBP paper (they reported 28.48% standard\nerror and 46.03% verified error), but in Figure 2 it is much worse (~35%\nstandard error and ~50% verified error). If we use the correct CROWN-IBP model,\nit should start at a similar place at the ACE based methods in Figure 2, rather\nthan on the far left. Can you explain?\n\nConclusion:\n\nI like the aim on standard accuracy and the network selection idea proposed in\nthis paper, but its current evaluation is partially missing or misleading and\ncannot justify all claims. So I cannot recommend accepting its current version.\nHowever I will be glad to discuss with the authors and re-evaluate the paper\nbased on new evaluation results from the authors. I will be happy to accept this\npaper if the authors can address my issues mentioned above.\n\n---\n### After rebuttal\n\nSee my reply below for my comments after rebuttal. Overall I feel the paper still has room for improvement and there are several open issues, but it has been improved so it is marginally above acceptance threshold now.\n\n---\nReference:\n\n[1] Xu, Kaidi, et al. \"Provable, Scalable and Automatic Perturbation Analysis on General Computational Graphs\" https://arxiv.org/pdf/2002.12920", "extra_scores": {}, "extra_text": {}}, {"review_id": "MI72dQDfmd", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a new network architecture that combines 1) a state-of-the-art deep neural network with high accuracy (but potentially no robustness certificate), and 2) a small certification network with high certifiable robustness (but not necessarily very high accuracy), using a selection network that adaptively chooses between these two networks. They show that by doing so, the new architecture is able to take advantage of both networks and thus obtain good natural accuracy with better certified robustness that significantly improves upon prior benchmarks.\n\nThe main advantage of this framework is its flexibility in allowing arbitrary combinations of STOA deep networks with any networks with certified robustness and their selection mechanism is able to make good use of both.\n\n1. I like this simple idea and I am glad to see its good performance, although I wish the author can develop more theoretical results to quantify the value of a hybrid model.\n\n2. According to (2), the objective may not be differentiable because of the binary function $g$. Can you elaborate on how gradient-based algorithms are applied to this formulation?\n\n3. Can you provide some interpretation of the learned selection mechanism $g_{\\theta_s}$? In particular, what features of the samples make them be passed through the core or the certification network? \n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "ER0nvrQIU5r", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "# Summary of Contributions\nThe paper presents an approach to trade off natural accuracy and certified robustness by combining a network with high natural accuracy (the “core network”) with a second network with high certifiable robustness (the “certification network”). A selection mechanism is used to decide which network an input sample should be processed by. The selection mechanism allows the combined system to perform significantly better than a weighted average of the core and certification networks (e.g. randomly assigning input to the core network with some probability $p$) would. \n\n# Score Recommendation\nDespite the weaknesses in experimental evidence, clarity and reproducibility identified below, I recommend an acceptance because the authors have demonstrated that the selection mechanism presented works for non-trivial problems, providing a simple way to trade off natural accuracy and certified robustness. \n\nACE can consistently benefit from advances that improve the natural accuracy of the core network. In addition, as long as a selection mechanism can be found that is compatible with the certification network, it would be possible for ACE to leverage improvements in certified defenses.\n\nWhile results are only presented for $l_\\infty$ perturbations, I expect that the same approach can be applied to different perturbations, as long as it is possible for the selection mechanism to have a tunable selection rate while having non-trivial robustness to the perturbation of choice.\n\n# Weaknesses\n## Missing Experimental Evidence\n- The paper claims in the abstract that it is the first to obtain a high natural accuracy with non-trivial certified robustness; the results (91.6% natural accuracy, 22.8% certified robustness) are compared to the prior state-of-the art (77.4% natural accuracy, 16.5% certified robustness). However, I am concerned that the comparison may not be completely fair (if the network the comparison is made to is one of the CROWN-IBP trained DM-Large networks; see the section on “Clarity” below). The paper itself acknowledges (in the first paragraph of page 7) that they did not conduct the extensive training required to obtain the performance reported in the CROWN-IBP paper.\n  - The authors should either train the CROWN-IBP DM-Large network with at least as much resources as in the original paper, or clearly identify in both the abstract and introduction that the amount of compute used was constrained.\n\n- The paper claims that “ACE produces much more favorable robustness-accuracy trade-offs than varying hyperparameters of the existing certified defenses” on the basis of comparing DM-Large CROWN-IBP to the Conv2 COLT-based ACE SelectionNet. I believe that more evidence is required to substantiate this claim, since the choice of a base network is rather arbitrary (why choose one comparable to the second DM-Large network, not the first or the third?).\n  - One possible set of experiments is to use each of the 5 DM-Large networks with non-trivial certifiable accuracy as the certification network, and then showing that the resulting families of  ACE SelectionNets have a better robustness-accuracy tradeoff.\n\n## Possible Experimental Errors\nThe Conv3-COLT network in Figure 2 has a performance (~75% natural accuracy, ~50% certifiable accuracy) that is significantly worse than that reported in the original COLT paper (78.4% natural accuracy, 60.5% certified robustness). What is the cause of this significant gap?\n\n## Clarity\n- The term “ConvMedBig” is used in the caption for Figure 2 and elsewhere in the paper, but is not defined in the original paper. (It appears that the authors may be referencing [the name in code](https://github.com/eth-sri/colt/blob/20f30b073558ae80e5e726515998c1f31d48b6c6/code/networks.py#L79)). The authors should provide more detail about specifically which network this is. In fact, it appears from the third paragraph of Section 7 (and the code linked above) that “ConvMedBig” matches the network Conv3 exactly. If this is the case, the same name should be used.\n\n- The authors compare to a prior approach with 77.4% accuracy and 16.5% certified robustness but do not specify what this approach is. (It appears from Figure 2 that this may be one of the DM-Large CROWN-IBP networks)\n\n- At the bottom of page 6, the paper states that “the smaller networks to which COLT scales lack capacity to obtain the kind of robustness-accuracy trade-off that we target”. What does this mean? A significant proportion of the results in Table 1 are presented for COLT, so I’m confused by this statement.\n\n## Reproducibility\n- Hyperparameters for the PGD attacks used are not provided, making it difficult to understand the strength of the adversarial attack being used. (If the adversarial attack is weak, the adversarial accuracy presented in Table 1 may be significantly higher than the actual robust model accuracy).\n- More details should be provided about the algorithm used for certifying the networks in Table 1 (other than the Entropy-COLT-Conv2 network). The third paragraph of Section 5 states that “we only use … convex relaxation-based certification methods based on intervals and zonotopes”, but I couldn’t find any further details (for example, what zonotopes were used to verify the certification network?)\n\n# Questions for Authors\n- I’d like to better understand how the adversarial accuracy of the network was evaluated; the paper only mentions that it is “usually computed using an adversarial attack such as PGD” (see the first paragraph of Page 3). One of my concerns is that the selection mechanism (particularly where a selection network is used) may reduce the success of PGD adversarial attacks without increasing the robustness of the network, possibly via gradient masking [1].\n- In paragraph 2 of Section 5, the paper specifies that an adversarially trained network was used as the core network. Given that the last paragraph of Section 4 states that “we assume that certification of the core-network always fails”, why did you choose an adversarially trained network (which presumably has slightly worse natural accuracy?)\n\n[1]: Papernot, Nicolas, Patrick McDaniel, Ian Goodfellow, Somesh Jha, Z. Berkay Celik, and Ananthram Swami. \"Practical black-box attacks against machine learning.\" In Proceedings of the 2017 ACM on Asia conference on computer and communications security, pp. 506-519. 2017.\n\n\n# Additional Feedback\n- hyperparamters → hyperparameters (4th line, third paragraph of section 5)\n- Figure 2 presents many different networks but it is not clear what the point of the figure is. Compounding the issue is the fact that the corresponding discussion begins almost an entire page later. For improved clarity, the authors should consider adding more to the caption for Figure 2 or moving it closer to the discussion.\n- The term “natural accuracy” and “standard accuracy” is used interchangeably; the paper should settle on one.\n- Figure 7 labels the y-axis “std of input zono errors” but this term is never introduced anywhere else in the text. (Is this the standard deviation, perhaps?)\n\n# Post-Rebuttal Comments\nI've maintained my score at 6.\n\nDuring the comment period, the authors made progress in improving the clarity of their presentation. As with reviewer 3, I feel that there is still room for improvement; in particular, moving some experiments in Section 5 to the appendix could make for a more focused paper with a clearer message for the reader. (Unfortunately, we did not have enough time during the comment period to get there). \n\nI'd also note that the paper is now at nine pages; this means that I am holding it to a higher bar.\n\nOverall, however, I continue to recommend an acceptance as the method to trade off natural accuracy and certified robustness is simple and significantly improves on the state of the art; for me, these strengths outweight the remaining issues. ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a selection mechanism to choose between a certified model with low clean accuracy and a naturally trained model with high accuracy, to improve the standard clean accuracy for certifiably robust models.  At a high-level, the idea behind this combined system is that when the certified model cannot certify, one should avoid using it for classification, but rather should use a naturally trained model.  A state-of-the-art naturally trained networks is used as the "core network", and a small certification network with high certifiable robustness is used as the "certification network". The major contribution is a selection network that adaptively chooses between these two networks. 

Pro
+ The idea of using two networks adaptively is novel. The proposed selection mechanism has been shown to be able to combine the merits of both networks to obtain better natural accuracy with good certified robustness. 


Con
- The experiment section still has room for improvement. Specifically, the presentation of the results were not convincingly conveying the tradeoff between the clean accuracy and the certified accuracy.  After the rebuttal, the authors made some improvements that addressed many of the concerns about the clarity and reproducibility issues. However, reviewers suggest further polishing the experiment section. 

Overall, I think the novelty of the paper combined with the promising results achieved outweigh the presentation issues. I would recommend accepting this paper. 
Decision: Accept (Poster)