Boosting Randomized Smoothing with Variance Reduced Classifiers
Authors: Miklós Z. Horváth
Mark Niklas Mueller
Marc Fischer
Martin Vechev
Venue: ICLR 2022 Spotlight (2022)
Keywords: adversarial robustness
certified robustness
randomized smoothing

Abstract: Randomized Smoothing (RS) is a promising method for obtaining robustness certiﬁcates by evaluating a base model under noise. In this work, we: (i) theoretically motivate why ensembles are a particularly suitable choice as base models for RS, and (ii) empirically conﬁrm this choice, obtaining state-of-the-art results in multiple settings. The key insight of our work is that the reduced variance of ensembles over the perturbations introduced in RS leads to signiﬁcantly more consistent classiﬁcations for a given input. This, in turn, leads to substantially increased certiﬁable radii for samples close to the decision boundary. Additionally, we introduce key optimizations which enable an up to 55-fold decrease in sample complexity of RS for predetermined radii, thus drastically reducing its computational overhead. Experimentally, we show that ensembles of only 3 to 10 classiﬁers consistently improve on their strongest constituting model with respect to their average certiﬁed radius (ACR) by 5% to 21% on both CIFAR10 and ImageNet, achieving a new state-of-the-art ACR of 0.86 and 1.11, respectively. We release all code and models required to reproduce our results at https://github.com/eth-sri/smoothing-ensembles.

Published as a conference paper at ICLR 2022
BOOSTING RANDOMIZED SMOOTHING WITH VARIANCE REDUCED CLASSIFIERS
Miklós Z. Horváth, Mark Niklas Müller, Mare Fischer, Martin Vechev
Department of Computer Science ETH Zurich, Switzerland mihorvat@ethz.ch ch, {mark. {mark.muelle)) wwmemmelllerree merellle,marrre marc. messcher,martincom vetcveee
ABSTRACT
Randomized Smoothing (RS) is promising method for obtaining robustness cer- tificates by evaluating base model under noise. In this work, we: (i) theoretically motivate why ensembles are particularly suitable choice as base models for RS, and (ii) empirically confirm this choice, obtaining state-of-the-ar results in multiple settings. The key insight of our work is that the reduced variance of ensembles over the perturbations introduced in RS leads to significantly more consistent classifi- cations for given input. This, in turn, leads substantially increased certifiable radii for samples close to the decision boundary. Additionally, we introduce key op- timizations which enable an up 55-fold decrease in sample complexity of RS for predetermined radii, thus drastically reducing its computational overhead. Experi- mentally, we show that ensembles of only 10 classifiers consistently improve on their strongest constituting model with respect to their average certified radius (ACR) by 5% to 21 % on both CIFAR 10 and ImageNet, achieving a new state-of-the art ACR of 0.86 and 1.11, respectively. We release all code and models required to reproduce our results at https: //github. com/eth wwwpttsssrssmoosiiniggoooooo ensemb les
INTRODUCTION
Modern deep neural networks are successfully applied to an ever-increasing range of applications. However, while they often achieve excellent accuracy the data distribution they were trained on, they have been shown to be very sensitive to slightly perturbed inputs, called adversarial examples (Biggio et al. 2013) (Szgedy et al.) 2014). This limits their applicability to safety-critical domains. Heuristic defenses against this vulnerability have been shown to be breakable (Carlini & Wagner Tramer et al. 2020), highlighting the need for provable robustness guarantees.
2017
promising method providing such guarantees for large networks Randomized Smoothing (RS) (Cohen et al. 2019). The core idea is provide probabilistic robustness guarantees with arbitrarily high confidence by adding noise to the input of a base classifier and computing the expected classification over the perturbed inputs using Monte Carlo sampling. The key obtaining high robust accuracies is a base classifier that remains consistently accurate even under high levels of noise, i.e., has low variance with respect to these perturbations. Existing works use different regularization and loss terms to encourage such behavior (Salman et al. 2019 Zhai et al. 2020 Jeong & Shin 2020) but are ultimately all limited by the bias-variance trade-off of individual models. We show first theoretically and then empirically how ensembles can be constructed to significantly reduce this variance component and thereby increase certified radii for individual samples, and consequently,
certified accuracy across the whole dataset. We illustrate this in Fig.
Ensembles are a well-known tool for reducing classifier variance the cost of increased computational cost (Hansen& & Salamon, 1990). However, in the face of modern architectures (He et al., 2016)] Huang (et al. (017)) allowing the stable training of large models, they have been considered computationally inefficient. Yet, recent work (Wasay & Idreos 2021) shows ensembles to be more efficient than single monolithic networks in many regimes. light this, we develop a theoretical framework analyzing this variance reducing property of ensembles under the perturbations introduced by RS. Further, show how this reduced variance can significantly increase the majority class's 's prediction probability, leading to much larger certified radii than evaluating more perturbations with an individual model.

---

Published as a conference paper at ICLR 2022
(a) Individual Model
(b) Individual Model 2
(c) Ensemble
Figure I: Illustraiion of the prediction landscape of base models where colors represent classes. The bars show the class probabilities of the corresponding smoothed classifiers (0,,N F) + +e), i.e. the Gaussian weighted average around æ (dashed circles show the level sets of N(x,, o..)). The individual models in (a) and (b) predict the same class for æ: as their ensemble (c). However, the ensemble's 's lower bound on the majority class' probability PA is increased while its upper bound on the runner-up class' probability pø is decreased, leading to improved robustness through RS.
Certification with RS is computationally costly the base classifier has to be evaluated many thousands of times. To avoid exacerbating these costs by using ensembles as base models, we develop two techniques: (i) an adaptive sampling scheme for RS, which certifies samples for predetermined certification radii in stages, reducing the mean certification time up to 55-fold, and (ii) special aggregation mechanism for ensembles which only evaluates the full ensemble on challenging samples, for which there is no consensus between a predefined subset of the constituting models.
Main Contributions Our key contributions are:
A novel, theoretically motivated, and statistically sound soft-ensemble scheme for Random- ized Smoothing, reducing perturbation variance and increasing certified radii ($4 and $
A data-dependent adaptive sampling scheme for RS that reduces the sample complexity for predetermined certification radii in statistically sound manner ($6).
An extensive evaluation, examining the effects and interactions of ensemble size, training method, and perturbation size. We obtain saate-of-the-eee results on ImageNet and CIFAR10 for wide range of settings, including denoised smoothing ($7).
RELATED WORK
Adversarial Robustness Following the discovery of adversarial examples (Biggio et al. 2013
Szegedy et al. 2014), adversarial defenses aiming robustify networks were proposed (Madry et al. 2018). Particularly relevant to this work are approaches that certify or enforce robustness properties. We distinguish deterministic and probabilistic methods. Deterministic certification methods compute the reachable set for given input specifications using convex relaxations (Singh et al.) [019 Xu et al. 2020), mixed-integer linear programming TTeng et al. 2019), semidefinite programming (Dathathri et al. 2020), or SMT (Ehlers) 2017). to reason about properties of the output. To obtain networks amenable to such approaches, specialized training methods have been proposed (Mirman et al. 2018 Balunovic & Vechev 2020 Xu et al. 2020). Probabilistic certification (Li et al. Lécuee et al.
2019) introduces noise to the classification process to obtain probabilistic robustness guarantees, allowing the certification of larger models than deterministic methods. We review Randomized 2019) in $ and associated training methods (Jeong & Shin 2020
Smoothing (RS) (Cohen et al.
Zhai al. 2020 Salman et al.
2019 in App. G.3 Orthogonally training. RS has been extended
in numerous ways (Lee et al. 2019 Dvijotham et al. 2020), which we review in App. B
Ensembles Ensembles have been extensively analyzed with respect to different aggregation meth- ods (Kittler al.) 1998 Inoue 2019), diversification (Dietterich) (000). and the reduction of gen- eralization errors (Tumer& & Ghosh 1996a b). Randomized Smoothing and ensembles were first combined in Liu et al. (2020) as ensembles of smoothed classifiers. However, the method does not retain strong certificates for individual inputs; thus, we consider the work to be in different setting from ours. We discuss this in App. A While similar at first glance, Qin et al. (021) randomly sample models to an ensemble, evaluating them under noise to obtain an empirical defense against adversarial attacks. They, however, do not provide robustness guarantees.
2

---

Published as a conference paper at ICLR 2022
3 RANDOMIZED SMOOTHING
Here, we review the relevant background on Randomized Smoothing (RS) as introduced in Cnhhen et al. (2019). We let f: I + _ denote base classifier that takes d-dimensional input and produces in numerical scores (pre-softmax logits), one for each class. Further, we let F(z)- == arg max, Jg (2))
denote function R + [1....,m) m that directly outputs the class with the highest score.
For random variable ~ NV(, o2, we define a smoothed classifier G: Rd [ ml as G(w=) arg max P (c>N((0002)) (F(x + + = =c).
This classifier G is then robust to adversarial perturbations as follows: Theorem 3.1 (From Cohen al. (2019)). Let CA E [L..... ml, PA PB E [0,1]. If (a (x + +) = cA) 2 2 pa 2 max P.
x + ++) cc;
o#cA
then G(æ + 8) = for all ó satisfying | < R with R == (2 ) - + (pB)
Here, Φ-1 denotes the inverse Gaussian
Algorithm 1 Certify from (Cohen et al. 2019
CDF. Computing the exact probabilities
(F + +) =)= is generally intractable. Thus,
1: function CERTIFY(F, de E, Roo n. a)
2: cnts0 + SAMPLEUNDER (F, no, o.)
to allow practical application, CERTIFY (Cohen)
3: Ćλ top index in cnts
et al. 2019) (see Algorithm[]] utilizes sampling:
4: cnts <- SAMPLEUNDERRNOSSHEEE
First, no samples to determine the majority class,
5: PA f LOWERCONFBNDDGGTS((...
then samples compute lower bound PA the success probability with confidence - a via the Clopper-Pearson lemma (Clopper & Pearson 1934). If PA > 0.5, we set PB = 1- PA PA and obtain radius R = σ (pa) via Theorem 3.1 else we abstain (retum 2). See App. for exact definitions of the sampling and lower bounding procedures.
6: if PA 2 then
7: return prediction è and radius o, (PA))
8: return @
To obtain high certified radii, the base model F has to be trained to cope with the added Gaussian noise e. To achieve this, several training methods, discussed App. G.3 have been introduced.
We also see this in Fig. 1 where various models obtain different PA. and thereby different radii R.
4 RANDOMIZED SMOOTHING FOR ENSEMBLE CLASSIFIERS
In this section, we extend the methods discussed in 3 from single models to ensembles.
For set of classifiers {f': Rd + Rm J construct an ensemble f via weighted aggregation, f(x) = Ei= w² (x)), where w² are the weights, 7: IRm - IR is post-processing function, and (a(x) are the pre-softmax outputs of individual model. Soft-voting (where y denotes identity) and equal weights w' & perform experimentally well (see App. H.3.1 while being mathematically simple. Thus, we consider soft-ensembling via the averaging of the logits:
f(x) K
F((x)
(2)
The ensemble f and its corresponding hard classilaasifier F(x) : arg max, Fo (x)), can be used without further modification as base classifiers for RS. We find that classifiers of identical architecture and trained with the same method but different random seeds are sufficiently diverse to, when ensembled with & E [3, 50), exhibit a notably reduced variance with respect to the perturbations e. As we will show the next section, this increases both the true majority class probability PA and its lower confidence bound PA raising the certified radius as per Theorem 3.1
5 VARIANCE REDUCTION VIA ENSEMBLES FOR RANDOMIZED SMOOTHING
We now show how ensembling even similar classifiers f (cf. Eq. (2) reduces the variance over the perturbations introduced in RS significantly, thereby increasing the majority class probability pA of
3

---

Published as a conference paper at ICLR 2022
resulting ensemble f and making it particularly well-suited as base classifier for RS. To this end, we first model network outputs with general distributions before investigating our theory empirically for Gaussian distributions. We defer algebra and empirical justifications App. C and D respectively.
Individual Classifier We consider individual classifiers fl: I2 + T and perturbed inputs x + for a single arbitrary but fixed and Gaussian perturbations _N(0, o2 We model the pre- softmax logits fx() =: y' E R" as the sum of two random variables y = yr + y"- Here, y corresponds to the classifier's behavior on the unperturbed sample and models the stochasticity in weight initialization and training with random noise augmentation. yo describes the effect of the random perturbations applied during RS. Note that this split will become essential when analyzing the ensembles. We drop the superscript when discussing an individual classifier to avoid clutter.
We model the distribution of the clean component Ye over classifiers with mean c = E5 (x)) the expectation for a fixed sample x over the randomness in the training process, and covariance E. E Rm=x m characterizing this randomness. We assume the distribution of the perturbation effect yp to be zero-mean (following from local linearization and zero mean perturbations) and to have covariance Ep E Rm While Σp might depend on the noise level de. it is distinet from it. We do not restrict the structure of either covariance matrix and denote Σn of and Eg j for standard deviations and correlations Pij. As ye models the global training effects and yp models the local behavior under small perturbations, we assume them to be independent. We thus obtain logits with mean c, and covariance matrix Σ E + Ex.
A classifier's prediction (xx) = arg max, Mg is not determined by the absolute values of its logits but rather by the differences between them. Thus, to analyze the classifier's behavior, we consider the differences between the majority class logit and others, referring to them as classification margins. During certification with RS, the first step is to determine the majority class. Without loss of generality, let the class with index be the majority class, i.e., A = 1 in Theorem leading to the classification margin 2, = 1/1 - y:- Note that 2; > 0 for all i & 1, then the majority class logit yi larger than the logits of all other classes yt- Under the above assumptions, the classification margin' 's statistics for an individual classifier are:
B[z]] = C1
Var[z]] = of 7. + 0 2 20p,1:0p,,00.3 22p,,100,110.5
Ensemble Now, we construct an ensemble of le such classifiers. We use soft-voting (cf. Eq. 2) to compute the ensemble output ÿ = Σ'= y' and then the corresponding classification margins & = 51 Dr- We consider similar classifiers, differing only in the random seed used for training. Hence, we assume that the correlation between the logits of different classifiers has similar structure but smaller magnitude than the correlation between logits of one classifier. Correspondingly, we parametrize the covariance between y and yd for classifiers i A j with C.E. and similarly between yr and 3 with E. for Co: So E [0, 1]. Note that, as we capture the randomness introduced in the training process with E., we use the same Ec, Ep for each individual model. With these correlation coefficients So and Cp. this construction captures the range from no correlation (( = 0) to perfect correlation = 1). By the linearity of expectation and this construction, respectively, we obtain:
E [ = E [
C1 Ci
l: + (()) So
1 + 2(0 Co
Var [2:]
(o p,1 + - -p.1100110p.pp00++++1
(oe,
og, 2p..1.
1.2
k2
(
Variance Reduction We can split Var[z;] into the components associated with the clean prediction (k) and the perturbation effect (K), both functions of the ensemble size k. We now compare these variance terms independently to the corresponding terms of an individual classifier dropping the subscripts p and from o² (x) and ( as they follow the same structure:
2p1:010;) 1 1+ <(k o²(k) (1 + Ç(k () + of (1)
1-000 C
(3)
k(o? + of 2p1
We observe that both variance component ratios go towards their corresponding correlation coeffi- cients Ça and 6, as ensemble size grows. As we now proceed to show (see Fig. [aa explained later), this corresponds an increase in success probability p1 and thereby certified radius.
4

---

Published as a conference paper at ICLR 2022
Probability density
Success probability
Probability density
3.0
1.0
k= == 10
2.5
3
0.8
30
k=3, a=10
2.0
5
k=5, - 10
0.6
15-
k=10, n-
50
0.4
k=50. n- 10
10-
modeled
10-
k= a=5 10*
0.2
0.5-
real
0.0
0.0
0
1.5
-1.0
-0.5
0.0
0.5
1.0
5
10
50
0.0
0.2
0.4
0.6
Classification margin
Number & of classifiers
Certified &a radius
(a)
(h)
(c)
Figure 2: Comparison of the (a) modeled distribution over the classification margin 2, to the runner- up class Gaussian, (b) the resulting success probability p1 of predicting the majority class 1 for a given perturbation modeled via Gaussian and observed via sampling ("real"), and (c) the corresponding distribution over certified radii for ensembles of different sizes.
Our modeling approach is mathematically closely related to Tumer & Ghosh (1996a), which focuses on analyzing ensemble over the whole dataset. However, we condition on a single input study the interplay between the stochasticity in training and random perturbations encountered in RS.
Effect on Success Probability We can compute the probability of an ensemble of classifiers predicting the majority class by integrating the probability distribution of the classification margin over the orthan
2 Vi 2 2 where majority class 1 is predicted:
Pı P(F
(z: 20002255
P(z) dz.
(4)
2s.0. 1/ Si5m
Assuming Gaussian distributions for 2, we observe the increase in success probability shown in Fig. 2b Without assuming a specific distribution of z, can still lower-bound the success probability
using Chebyshev's inequality and the union bound. Given that a mean classification yields the majority class and hence C1
G 0, we let -1- and have: (k)
(k)2
D1 1111- P( - + all 2 24.0(()) 21
Σ 1=2 (c1 -c)
(5)
where okk) ok, pp (p) 2 is the variance of classification margin 2. We observe that as (k) decreases with increasing ensemble size (see Eq.. (3h). ). the lower bound to the success probability approaches 1 quadratically. The further larger c, the smaller the absolute increase in success probability for the same variance reduction.
away from the decision boundary, i.e., the
Given conerete success probability Pt, compute the probability distribution over the certifiable radii reported by CERTIFY (Algorithm[] [ for given confidence a, sample number n, and perturbation variance of (up choosing incorrect majority class êA) as:
P(R = a (pi n, a))) = B(n1, p.))) for R >
where (ss, r. the probability of drawing s successes trials from Binomial distribution with success probability and p(s. r, is the lower confidence bound to the success probability of Bernoulli experiment given successes trials with confidence a according to the Clopper-Peane Pearson interval (Clopper & Pearson 1934). We illustrate the resulting effect assuming Gaussian distributions
in Fig. 2c
assume y! and yo and hence also Σ, to be multivariate Gaussians. This choice is empirically well-fitting (see App. Di and follows from the central limit theorem for y! and from Gaussian perturbations and local
Empirical Analysis via Gaussian Assumption To investigate our theory,
orthant is the n-dimensional equivalent of quadrant.
5

---

Published as a conference paper at ICLR 2022
linearization for yz- To estimate the free parameters c, Le, Ex, Sex and Cp. evaluate ensembles of up to = 50 GAUSSIAN trained ResNet20 (for details, see $7 at o. = 0.25. We obtain c and Σg as the mean and covariance of the output on a randomly chosen sample æ. Subtracting the clean outputs from those for the perturbed samples, we estimate the covariance matrix Sp. We determine Çe R O and Cp Rs 0.82 as the median ratio of the inter- and intra-classifier covariance. Se Ri 0 implies that our models can be treated as independent conditioned on a single fixed and unperturbed input.
Plugging these estimates into our construction under the Gaus- sian assumption, we observe a significant decrease in the vari- ance of the classification margin the runner-up class as ensem- ble size k increases (see Fig. 2ap. This generally leads to more polarized success probabilities: the majority class' probability is increased, while the other classes' probabilities are decreased because the probability mass concentrates around the mean, and consequently one side of the decision threshold _ 0, which determines the success probability via Eq. 4 An in- crease, as in case for correct mean prediction (see Fig. 2b
Expeesed cartified radius
1.0
Pa = 1.00
0.6
0.99
PA 0.95
0.4
PA 0.90
0.2
PA 0.80
Pa 0.60
0.0
102
10
10
109
leads to much larger expected certified radii (see Fig. 2c for
# Samples n
given number of sampled perturbations (here n 10a) via Eq. (6). In contrast, sampling more perturbations will, in the limit, only recover the true success probability. In our example, going from one classifier to an ensemble of 50 increases the ex- pected certified radius by 191%, while drawing 50 times more perturbations for a single model only yields a 28% increase (see Fig. 2cp. As illustrated in Fig. 3
Figure 3: Expected certified radius over the number n of samples for the true success probabilities P.A.
these effects are strongest close to decision boundaries (pA < 1). where small increases in PA impact the certified radius much more than the number of samples which dominated at Pa 1.
COMPUTATIONAL OVERHEAD REDUCTION
To avoid exacerbating the high computational cost of certification via RS with the need to evaluate many models constituting ensemble, propose two orthogonal and synergizing approaches to reduce sample complexity significantly. First, an adaptive sampling scheme reducing the average number of samples required for certification. Second, a more efficient aggregation mechanism for ensembles, reducing the number of models evaluated per sample, also applicable to inference.
dappiiv Sampling We assume a setting where a target certification radius r is known priori, as the standard in deterministic certification, and aim show R via Theorem 3.1 After choosing the majority class č as in CERTIFY, CERTIFYADP (see Algorithm 2 leverages the insight that relatively few samples are often sufficient to certify robustness radius r. We perform an s 2 step procedure: At step i, we evaluate n. fresh samples and, depending on these, either certify radius r as in CERTIFY, abort certification if an upper confidence bound suggests that certification will not be fruitful, or continue with n1+1 >> n4, After steps, we abstain. To obtain the same strong statistical guarantees as with CERTIFY, it essential to correct for multiple testing by applying Bonferroni correction (Bonferroni 1936), i.e., use confidence 1 - 2 rather than 1 a. The following theorem summarizes the key properties of the algorithm:
Theorem 6.1. For a, 3 E [0, 1], N n1 <...< n., CERTIFYADP:
1. returns ć if at least 1 - a confident that G is robust with a radius of at least r.
2. returns @ before stage s only if at least 1 - B confident that robusiness of G at radius v can not be shown.
3. for n, [n(1 1a(1-log,, loga (s)) has maximum certifiable radii at least as large as CERTIFY for
We provide a proof in App. B For well-chosen parameters, this allows certifying radius with, in expectation, significantly fewer evaluations of F than CERTIFY as often n, < n samples suffice to certify or to show that certification will not succeed. At the same time, we choose n. in accordance with (3) in Theorem 1. to retain the ability to certify large radii (compared to CERTIFY) despite the increased confidence level required due Bonferroni correction. For an example, see Fig. 4

---

Published as a conference paper at ICLR 2022
Algorithm Adaptive Sampling
cnts|fa 2 580
onts/tal 736
1000
1: function CERTIFYADR(F, o., [ng}}=1: s,a, r)
cnts@ t- SAMPLEUNDERNOISH(PPN
oe)
ents 8588
sample with 10000
cnts 8270
3: čA t top index in cntse
clic
4: for i - to s do
ents 105007
sangle with 126000
eise
5: cnts +- SAMPLEUNDERROOISE F. oc))
PA LowFERCnNFBNNiCetts (A), Rig
7: If T (pAA) 2 r then return d
Figure 4: CERTIFYADP with 8 0.0001 obtains similar guarantee as CERTIFY at 100'000 while being more sample efficient for most inputs. Both use 0.001, o, = 0.25.
PA UPPERCON#BNDCCnts(Ce
If + 'pp)) < r then return ?
10: return
C--onsensus Aggregation To reduce both inference and certification times, we can adapt the ensemble aggregation process to return an output early when there is consensus. Concretely, first, we order the classifiers an ensemble by their accuracy (under noisy inputs) on holdout dataset. Then, when evaluating J. we query classifiers in this order. If the first K individual classifiers agree on the predicted class, we perform soft-voting on these and return the result without evaluating the remaining classifiers. Especially for large ensembles, this approach can significantly reduce inference time without hampering performance, as the ratio K can be large.
We note that similar approaches for partial ensemble evaluation have been proposed (Inoue 2019 Wang et al. 2018 Soto et al. 2016). and that this does not affect the mathematical guarantees of RS.
EXPERIMENTAL EVALUATION
In line with prior work, we evaluate the proposed methods on the CIFAR10 (Kizhevsky et al. 2009)
and ImageNet (Russakovsky et al. 2015) datasets with respect to two key metrics: (i) the certified accuracy at predetermined radii 7 and (ii) the average certified radius (ACR). We show that on both datasets, all ensembles outperform their strongest constituting model and obtain a new state-of-the-art. On CIFAR 10, we demonstrate that ensembles outperform individual models even when correcting for computational cost via model size or the number of used perturbations. Further, we find that using adaptive sampling and K-Consensus aggregation speeds up certification up to 55-fold for ensembles and up to 33-fold for individual models.
Experimental Setup
We implement our approach in PyTorch (Paszke et al. 2019) and evaluate on CIFAR10 with ensembles of ResNet20 and ResNet118 and on ImageNet with ensembles of ResNet50 (He et al., 2016), using 1 and 2 GeForce RTX 2080 Ti, respectively. Due to the high computational cost of CERTIPY, we follow previous work (Cohen et al. 2019) and evaluate every 20th image of the CIFAR10 10 test set and every 1h0 of the ImageNet test set (500 samples total).
Training and Certification We train models with GAUSSIAN (Cohen al., 2019). CONSISTENCY (Jeong & Shin (020), and SMOOTIAAY (Salman et al. 2019) training and utilize pre-trained SMOOTHADV and MACER (Zhai et al.) 2020) models. More details provided in App. G If not declared differently, we use no 100, n 100'000, a = 0.001, no CERTIFYADP or K-Consensus and evaluate and train with the same o..
7.1 MAIN RESULTS
Results on CIFAR10 In Table [] we compare ensembles of 10 ResNet110 against individual networks at a. = 0.50 w.r.t. average certified radius (ACR) and certified accuracy at various radií. We consistently observe that ensembles outperform their constituting models by up to 21% in ACR and 45% in certified accuracy, yielding a new state-of-the- art at every radius. Improvements are more pronounced for larger ensembles (see Fig. (5) and at larger radii, where larger PA required, which agrees well with our theoretical observations in $5 We present more extensive results in App. H.T including experiments for a. 0.25 and a. 1.0 yielding new state-oftthe-art ACR in all settings.
7

---

Published as a conference paper at ICLR 2022
Table CIFARIO average certified radius (ACR) and certified accuracy at different radii for ensembles of l ResNet110 (k- are individual models) at o, 0.5. Larger is better.
0.75
0.70
Radius
0.53
Training
0.0
0.25
0.50
0.75
1,00
1,25
1.50
1.75
0.80
CommETENNY RN110
GAUSSIAN
10
0.648
0.535
65.8
69.0
60.4
54.2
42.2
49.88
32.4
40.0
22.0
29.8
14,8
19.8
10.8
15.0
9.6
6.6
0.55
Garseas EN
Consertacc BN20
CONSISTENCY
10
0.708
0.756
63.2
65.0
59.0
5488
49.4
44.8
42.0
38.6
29,8
32.0
26.2
164
19.8
0.50
GAUREAN
10
50
SMOOTHADY
0.707
0.730
52.6
47.6
46.0
41.2
42.6
37.2
34.4
51.8
28.0
23.4
25.0
Figure ACR over ensemble size k for = 0.5 on CIFARIO.
Emsembie
MACER
0.668
62.4
54.4
48.2
40.2
33.2
26.8
19.8
13.0
Table 2: ImageNet average certified radius (ACR) and certified accuracy at different radii for ensembles Re (A: individual models) at o. 1.0. Larger is better.
Cortifed accurayy [3]]
50-
Radius
Training
ACR
0.0
0.50
1.00
1.50
2:00
2.50
3.00
3.50
20
CONSETIECY
0.875
43.6
37.8
32.6
26.0
19.4
14.8
12.2
9.0
GAUSSIAN
0,968
29.8
18.2
COMMITENCY
10
SMQITHABY
CONSISTENCY
1.108
1,022
44.6
43,2
29.8
37.2
35.0
34,0
29.4
24.4
23.2
22.2
16.6
16.4
13.4
0
SMOOTHABY
SMOOTHADV
3
1,011
1,065
38.6
40.6
38.6
36.0
33.8
34.0
29.8
30.0
25.6
27.4
20.6
24.6
21,2
18.0
14.4
18.8
Radins
Figure 6: Certified acc. over ra- dius r for a. = 1.0 on ImageNet.
MACER
1,008
48
43
36
30
25
18
As reported
Zhai
2020
Results on ImageNet In Table 2 we compare ensembles of 3 ResNet50 with individual models at o, = 1.0, w.r.t. ACR and certified accuracy. We observe similar trends to CIFAR1O, with ensembles outperforming their constituting models and the ensemble of 3 CONSISTENCY trained ResNet50 obtaining a new state-of-the art ACR of 1.11, implying that ensembles are effective on wide range of datasets. We visualize this in Fig. and present more detailed results App. H.2 where we also provide experiments for 0.25 and a. = 0.5, yielding new ofte-offthheart ACR in both cases.
Computational Overhead Reduction We eval-
Table 3: Adaptive sampling and K KKConsensuus
uate CERTIFYADP in conjunction with K- Consensus aggregation using 3 = 0.001, {my} (100, 1'000, 10'000, 120'000), and K = 5 in Ta- and report KCR, the percentage of inputs for which only K classifiers were evaluated and Sam- pleRF and TimeRF, the factors by which sample complexity and certification time are reduced, re-
aggregation on CIFARIO for 10 CONSISTENCY trained ResNet110.
Radius
acCeem [%]
SampleRF
KCR [%}
TimekF
0.25
0.25
70.4
55.24
39,3
67.16
0.50
0.25
60.6
18.09
57.3
25.07
0.75
52.0
5.68
10.06
1.00
0.50
38.6
14.79
78.3
24.01
1.25
0.50
32.2
8.14
92.7
15.06
spectively. We observe up to 67-fold certification speed-ups and up to 55-fold sample complexity reductions for individual predetermined radii, without incurring any accuracy penalties. This way, certifying an ensemble k = 10 networks with CERTIFYADP can be significantly faster than certifying individual model with CERTIFY while yielding notably higher certified accuracies. We observe that adaptive sampling and K-Consensus aggregation complement each other well: At larger radii r, more samples pass the later stages of CERTIFYADP, requiring more model evaluations. However, only samples with high success probabilities reach these later stages, making it more likely for K K-Consensus aggregation terminate evaluation early. We provide extensive additional experiments in App. H.4
1.50
0.50
26.2
6.41
97.5
12.31
7.2 ABLATION STUDY
Ensemble Size and Model Size Ablation In Fig. 5 we illustrate the effect of ensemble size on ACR for various training methods and model architectures, providing more extensive results in App. H.3.2, We observe that in all considered settings, even relatively small ensembles of just 3-5 models realize most of the improvements to be made. In fact, as few as 3 and 5 ResNet20 are enough to outperform a single ResNet110 under GAUSSIAN and CONSISTENCY training, respectively, while only having 47% and 79% of the parameters.
8

---

Published as a conference paper at ICLR 2022
Table 4: Adaptive sampling for different } on CIFARIO 0, 0.25. SampleRF and TimeRF are the reduction factors compared to standard sampling with n 100'000 (larger is better). ASR; is the portion of certification attempts returned in phase j.
Training
{ny)
a0Gen [%)
ASR; [%8
ASR2 (%]
ASR, [%]
ASR, [8]
SampleRF
TindRF
10000 110'000
60.0
92.2
7.8
10.34
10.45
GAUSSIAN
1'000, 10'000, 116
5.0
3,4
0.25
100, 1'000, 10'000, 120/000
75.4
1600
5.6
21.22
CONSISTENCY
100, 1'000, 10'000, 120/000
66.0
84.8
10.8
2.6
1.8
33.91
34,67
GAUSSIAN
1'000, 177000,1200000
30.2
48.8
11.6
29,4
10.2
5.92
6.10
CONSISTENCY
100, 1'000, 10'000, 120/000
46.4
32.4
8.2
49.4
10.0
5.32
5.40
Equal Number of Inferences In Fig. 7 we compare the effect of evaluating a larger number of perturbations n for an individual model compared an ensemble at the same computational cost. We observe that increasing the sample count for a single model only enables marginal improvements most radii and only outperforms the ensemble at radii, which can mathematically not be certified using the smaller sample count. See also Fig. 3 for a theoretical explanation and App. H.3.4 for more experiments.
Certified securncy [X]]
80-
CAUSSAN (s 10"
70-
GAUSSENN (s 10%
60-
1If)
50-
10
30
20
10
Other Base Classifiers While our approach works exceptionally well when ensembling similar classifiers, it can also be successfully extended to base models trained with different training methods (see App. H.3.5) and denoised classifiers (see App. H.3.6), yielding ACR improvements of up 5% and 17% over their strongest constituting models, respectively. This way, existing models can be reused to avoid the high cost of training an ensemble.
0.0
0.5
1.0
1.5
2.0
Radiue
Figure 7: Comparing an ensemble and an individual model at an equal number of total inferences on CIFARIO.
Adaptive Sampling Ablation In Table 4 we show the effectiveness CERTIFYADP for certifying robustness predetermined radii using 3 0.001, different target radii, training methods, and sampling count sets {ny}. We compare ASR,, the portion of samples returned in stage J. SampleRF. and T.meRF. Generally, we observe larger speed-ups for smaller radii (up factor 34 at 0.25). There, certification only requires small рa. which can be obtained even with few samples. For large radii (w.r.t o.), higher PA must be shown, requiring more samples even at true success rates of PA 1. There, the first phase only yields early abstentions. The more phases we use, the more often we certify or abstain early, but also the bigger the costs due Bonferroni correction. We observe that exponentially increasing phase sizes and in particular {ny} = {100, 1 1'000, 10'000, 120'000} perform very well across different settings. See App. H.4.1 for additional results.
K-Consensus Aggregation Ablation In Table 5 we
Table 5: K-Consensus aggregation at G, = 0.25 on CIFARIO.
compare ACR and certification time reduction for ensem- bles of 10 ResNet110 and 50 2e using K-Consensus aggregation isolation across different K. Even when us- ing only K = 2, we already obtain 81% and 70% of the ACR improvement obtainable by always evaluating the full ensembles (k: 10 and & = 50), respectively. The more
Architecture
K
ACR
TimeRF
KCR
0.546
10.0
100.0
CONSISTENCY
ResNet118
5
01583
1.59
74,2
0.583
0.0
conservative K = 10 for ResNet20 still reduces certifica- tion times by a factor of 2 without losing accuracy. See App. H.4.2 for more detailed experiments.
0.528
50.0
100.0
CONSISTENCY
ResNet20
10
0.551
2,01
69.8
0.551
1.00
0.0
CONCLUSION
We propose a theoretically motivated and statistically sound approach to construct low variance base classifiers for Randomized Smoothing by ensembling. We show theoretically and empirically why this approach significantly increases certified accuracy yielding state-of-the-ar results. To offset the computational overhead of ensembles, mechanism, reducing certification costs up to 55-fold for predetermined radii and an ensemble aggregation mechanism, complementing it and reducing evaluation costs its up 6-fold.
develop generally applicable adaptive sampling

---

Published as a conference paper at ICLR 2022
ETHICS STATEMENT
Most machine learning techniques can be applied both ethical and unethical ways. Techniques to increase the certified robustness of models not change this but only make the underlying models more robust, again allowing beneficial and malicious applications, c.g., more robust medical models versus more robust weaponized AI. As our contributions improve certified accuracy. certification radii, and inference speed, both of these facets of robust Al are amplified. Furthermore, while we achieve state-of-the-arr results, these do not yet extend to realistic perturbations. Malicious actors may aim convince regulators that methods such as the proposed approach are sufficient to provide guarantees for general real-world threat scenarios, leading insufficient safeguards.
10 REPRODUCIBILITY STATEMENT
We make all code and pre-trained models required to reproduce our results publicly available at https://github. com/eth- wriissoothisgg entemb-ees There, also provide detailed instructions and scripts facilitating the reproduction of our results. We explain the basic experimental setup in and provide exact experimental details in App. G where extensively describe the datasets (App. G.I.. model architectures (App. G.2 training methods (App. G.3), syper-parameter choices (App- G.4). and experiment timings (App. G.5). We remark that the datasets, architectures, and training methods we use are all publicly available. Section $ and App. H contain numerous experiments for various datasets, model architectures, training methods, noise levels, and ensemble compositions. The consistent trends we observe over this wide range of settings highlight the general applicability of our approach. In App. H.3.3] we analyze the variability of our results, reporting standard deviations for range of metrics, find that our ensembling approach reduces variability, and note that our results are statistically significant. We include complete proofs of all theoretical contributions ($5) and $66 in App. C and E In App. [ we theoretically motivate the modelling assumptions made in $5 and validate them empirically.
10

---

Published as a conference paper at ICLR 2022
REFERENCES
Mislav Balunovic and Martin T. Vechev. Adversarial training and provable defenses: Bridging the gap. Proc. of ICLR, 2020.
Battista Biggio, Igino Corona, Davide Maiorca, Blaine Nelson, Nedim Srndic, Pavel Laskov, Giorgio Giacinto, and Fabio Roli. Evasion attacks against machine learning at test time. In Machine Learning and Knowledge Discovery in Databases European Conference, ECML PKDD 2013, Prague, Czech Republic, September 23-27, 2013, Proceedings, Part III, volume 8190, 2013. doi: 10.1007/978- 3-642-40994
Aleksandar Bojchevski, Johannes Klicpera, and Stephan Günnemann. Efficient robustness certificates for discrete data: Sparsity-awars randomized smoothing for graphs, images and more. In Proc. of ICMI., volume 119, 2020.
Carlo Bonferroni. Teoria statistica delle classi e calcolo delle probabilita. Pubblicazioni del R Istituto Superiore di Scienze Economiche e Commericiali Firenze, 8, 1936.
Nicholas Carlini and David A. Wagner. Towards evaluating the robustness of neural networks. In 2017 IEEE Symposium on Security and Privacy, SP 2017, San Jose, CA, USA, May 22-26, 2017, 2017. doi: 10.1109/SP.011..44
Ping- Yeh Chiang, Michael J. Curry, Ahmed Abdelkader, Aoumon Kumar, John Dickerson, and Tom Goldstein. Detection as regression: Certified object detection with median smoothing. In Advances in Neural Information Processing Systems 33: Annual Conference Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
C. Clopper and E. S. Pearson. The use of confidence or fiducial limits illustrated in the case the binomial. Biometrika, 26(4), 1934. ISSN 00063444.
Jeremy M. Cohen, Elan Rosenfeld, and J. Zico Kolter. Certified adversarial robustness via randomized smoothing. In Proc. of ICML, volume 97, 2019.
Sumanth Dathathri, Krishnamurthy Dvijotham, Alexey Kurakin, Aditi Raghunathan, Jonathan Uesato, Rudy Bunel, Shreya Shankar, Jacob Steinhardt, Ian J. Goodfellow, Percy Liang, and Pushmeet Kohli. Enabling certification of programming. Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020.
networks via memory
semidefinite
Li Deng. The mnist database of handwritten digit images for machine learning research. IEEE Signal Processing Magazine, 29(6), 2012.
Thomas G. Dietterich. Ensemble methods in machine learning. In Multiple Classifier Systems, First International Workshop, MCS 2000, Cagliari, Italy, June 21-23, 2000, Proceedings, volume 1857, 2000. doi: 10. 10.100773-540-45014423
Krishnamurthy (Dj) Dvijotham, Jamie Hayes, Borja Balle, Zico Kolter, Chongli Qin, András György, Kai Xiao, Sven Gowal. and Pushmeet Kohli. A framework for robustness certification of smoothed classifiers using f-divergences. In Proc. of ICLR, 2020.
Rüdiger Ehlers. Formal verification of piece-wise linear feed-forward neural networks. In Automated Technology for Verification and Analysis 15th International Symposium, ATVA 2017, Pune, India, October 3-6, 2017, Proceedings, volume 10482, 2017. doi:
Mare Fischer, Maximilian Baader, and Martin T. Vechev. Certified defense image transformations via randomized smoothing. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NewrIPS 2020. December 6-12, 2020, virtual, 2020.
Mare Fischer, Maximilian Baader, and Martin T. Vechev. Scalable certified segmentation via randomized smoothing. In Proc. ICMI, volume 139, 2021.
11

---

Published as a conference paper at ICLR 2022
Zhidong Gao, Rui Hu, and Yanmin Gong, Certified robustness of graph classification against topology attack with randomized smoothing. In IEEE Global Communications Conference, GLOBECOM 2020, Virtual Event, Taiwan, December 7-11, 2020, 2020. doi: 10.1000G100BECC044200.0000000 9322576.
Lars Kai Hansen and Peter Salamon. Neural network ensembles. IEEE Trans. Pattern Anal. Mach. Intell., 12(10), 1990. doi: 10.1 10.8877/
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In 2016 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2016, Las Vegas, NV, USA, June 27-30, 2016, 2016. doi: 10.1 10.1109/CVR..006..
Gao Huang, Zhuang Liu, Laurens van der Maaten, and Kilian Q Weinberger. Densely connected convolutional networks. In 2017 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2017, Honolulu, HI, USA, July 21-26, 2017, 2017. doi: 10. 11100//VV...201..445.
Hiroshi Inoue. Adaptive ensemble prediction for deep neural networks based on confidence level. In The 22nd International Conference on Artificial Intelligence and Statistics, AISTATS 2019, 16-18 April 2019, Naha, Okinawa, Japan, volume 89, 2019.
Jongheon Jeong and Jinwoo Shin. Consistency regularization for certified robustness of smoothed classifiers. In Advances in Neural Information Processing Systems 33: Annual Conference Neural Information Processing Systems 2020, NewrlPS 2020, December 6- 12, 2020, virtual, 2020.
Jinyuan Jia, Xiaoyu Cao, Binghui Wang, and Neil Zhenqiang Gong. Certified robustness for top-k predictions against adversarial perturbations via randomized smoothing. In Proc. of ICLR, 2020.
Josef Kittler, Mohamad Hatef, Robert P. W. Duin, and Jiri Matas. On combining classifiers. IEEE Trans. Pattern Anal. Mach. Intell., 20(3), 1998. doi: 10. 199100444666.8...
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Aounon Kumar, Alexander Levine, Soheil Feizi, and Tom Goldstein. Certifying confidence via randomized smoothing. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020a.
Aounon Kumar, Alexander Levine, Tom Goldstein, and Soheil Feizi. Curse of dimensionality on randomized smoothing for certifiable robustness. In Proc. of ICML, volume 119, 2020b.
Alexey Kurakin, Ian J. Goodfellow, and Samy Bengio, Adversarial machine learning at scale. In Proc. of ICLR, 2017.
Mathias Lécuyer, Vaggelis Atlidakis, Roxana Gcambasu, Daniel Hsu, and Suman Jana. Certified robustness to adversarial examples with differential privacy. In 20/9 IEEE Symposium Security and Privacy, SP 2019, San Francisco, CA, USA, May 19-23, 2019, 2019. doi: 10.1 109///99/.. 00044.
Guang-Ht Lee, Yang Yuan, Shiyu Chang, and Tommi Jaakkola. Tight certificates of adversarial robustness for randomly smoothed classifiers. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019,
December 8-14, 2019, Vancouver, BC, Canada, 2019.
Alexander Levine and Soheil Feizi. (de)randomized smoothing for certifiable defense against patch attacks. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
Bai Li, Changyou Chen, Wenlin Wang, and Lawrence Carin. Certified adversarial robustness with additive noise. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, 2019.
Linyi Li, Maurice Weber, Xiaojun Xu, Luka Rimanic, Bhavya Kailkhura, Tao Xie, Ce Zhang, and Bo Li. Tss: Transformation smoothing for robustness certification. In ACM CCS, 2021.
12

---

Published as a conference paper at ICLR 2022
Chizhou Liu, Yunzhen Feng, Ranran Wang, and Bin Dong. Enhancing certified robustness of smoothed classifiers via weighted model ensembling. ArXiv preprint, 0aw/2005.09363. 2020.
Hongbin Liu, Jinyuan Jia, and Neil Zhenqiang Gong. Pointguard: Provably robust 3d point cloud classification, IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2021, virtual, June 19-25, 2021, 2021.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In Proc. of ICLR, 2018.
Matthew Mirman, Timon Gehr, and Martin T. Vechev. Differentiable abstract interpretation for provably robust neural networks. In Proc. of ICML, volume 80, 2018.
Jeet Mohapatra, Ching-Yun Yun Ko, Tsui-Wei Weng, Pin-Yu Chen, Sijia Liu, and Luca Daniel. Higher- order certification for randomized smoothing. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
Jeet Mohapatra, Ching- Yun Ko. Lily Weng, Pin-Yu Chen, Sijia Liu, and Luca Daniel. Hidden cost of randomized smoothing. In The 24th International Conference on Artificial Intelligence and Statistics, AISTATS 2021, April 13-15, 2021, Virtual Event, volume 130, 2021.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Edward Yang. Zachary Vito,o, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang. Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, geggh-erformnnce deep learning library. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, 2019.
Ruoxi Qin, Linyuan Wang, Xingyuan Chen, Xuehui Du, and Bin Yan. Dynamic defense approach for adversarial robustness in deep neural networks via stochastic ensemble smoothed model. ArXiv preprint, abs/2105.00 200.//2200000 2021.
Jérôme Rony, Luiz G. Hafemann, Luiz S. Oliveira, Ismail Ben Ayed, Robert Sabourin, and Eric Granger. Decoupling direction and norm for efficient gradient- L2 adversarial attacks and defenses. In IEÉE Conference on Computer Vision and Pattern Recognition, CVPR 2019, Long Beach, CA, USA, June 16-20, 2019, 2019, doi: 10. 109/CV/R.2019.0000 9.00445.
Elan Rosenfeld, Ezra Winston, Pradeep Ravikumar, and Zico Kolter. Certified robustness to label- flipping attacks via randomized smoothing. In Proc. of ICML, volume 119, 2020.
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei-Fei. ImageNet Large Scale Visual Recognition Challenge. International Journal of Computer Vision (IJCV). 115 (3), 2015. doi: 1007/s1 1263-015-0816-7
Hadi Salman, Jerry Li, Ilya P. Razenshteyn, Pengchuan Zhang, Huan Zhang, Sébastien Bubeck, and Greg Yang. Provably robust deep learning via adversarially trained smoothed classifiers. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, 2019.
Hadi Salman, Mingjie Sun, Greg Yang, Ashish Kapoor, and J. Zico Kolter. Denoised smoothing: A provable defense for pretrained classifiers. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NewrIPS 2020, December 6-12, 2020, virtual, 2020.
Jan Schuchardt, Aleksandar Bojchevski, Johannes Klicpera, and Stephan Günnemann. Collective robustness certificates. In International Conference on Learning Representations, 2021.
Gagandeep Singh, Timon Gehr, Markus Püschel, and Martin Vechev. An abstract domain for certifying neural networks. Proc. ACM Program. Lang., 3(POPI.,, 2019. doi: 10. (0.1145/3290354
13

---

Published as a conference paper at ICLR 2022
Victor Soto, Alberto Suárez, and Gonzalo Martinez-Muñoz. An um model for majority voting in classification ensembles. In Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain, 2016.
Christian Szegedy, Wojciech Zaremba, llya Sutskever, Joan Bruna, Dumitru Erhan, Ian J. Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In Proc. of ICLR, 2014.
Vincent Tjeng. Kai Y. Xiao, and Russ Tedrake. Evaluating robustness of neural networks with mixed integer programming. In Proc. of ICLR, 2019.
Florian Tramèr, Nicholas Carlini, Wieland Brendel, and Aleksander Madry. On adaptive attacks to adversarial example defenses. In Advances in Neural Information Processing Systems 33: Annual Conference Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020.
Kagan Tumer and Joydeep Ghosh. Error correlation and error reduction in ensemble classifiers. Connect. Sci., 8(3), 1996a. doi: 10.10800095400996116333
Kagan Tumer and Joydeep Ghosh. Analysis of decision boundaries in linearly combined neural classifiers. Pattern recognition, 29(2), 1996b.
Binghui Wang, Jinyuan Jia, Xiaoyu Cao, and Neil Zhenqiang Gong. Certified robustness of graph neural networks against adversarial structural perturbation. In KDD '21: The 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Virtual Event, Singapore, August 14-18, 2021, 2021.
Serena Wang. Maya R. Gupta, and Seungil You. Quit when you can: Efficient evaluation of ensembles with ordering optimization. ArXiv preprint, abs/1 806. 1202, 2018
Abdul Wasay and Stratos Idreos. More or less: When and how to build convolutional neural network ensembles. In Proc. of ICLR, 2021.
Yihan Wu, Aleksandar Bojehevski, Aleksei Kuvshinov, and Stephan Günnemann. Completing the picture: Randomized smoothing suffers from the curse of dimensionality for a large family of distributions. In The 24th International Conference on Artificial Intelligence and Statistics, AISTATS 2021. April 1 13-15, 2021, Virtual Event, volume 130, 2021.
Kaidi Xu, Zhouxing Shi, Huan Zhang, Yihan Wang, Kai-Wei Chang, Minlie Huang, Bhavya Kailkhura, Xue Lin, and Cho-Jui Hsieh. Automatic perturbation analysis for scalable certi- fied robustness and beyond. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6- 2020, virtual, 2020.
Greg Yang, Tony Duan, Edward Hu, Hadi Salman, llya P. Razenshteyn, and Jerry Li. Randomized smoothing of all shapes and sizes. In Proc. of ICML, volume 119, 2020.
Runtian Zhai, Chen Dan, Di He, Huan Zhang, Boqing Gong, Pradeep Ravikumar, Cho-Jui Hsieh, and Liwei Wang. MACER: frre and scalable robust training via maximizing certified radius. In Proc. of ICLR, 2020.
Dinghuai Zhang, Mao Ye, Chengyue Gong, Zhanxing Zhu, and Qiang Liu. Black-box certification with randomized smoothing: A functional optimization based framework. In Advances in Neural Information Processing Systems 33: Annual Conference Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020.
14

---

Published as a conference paper at ICLR 2022
A COMPARISON TO LIU ET AL.
(2020)
Liu et al. (2020) introduce Smoothed Weighted Ensembling (SWEEN), which are weighted ensembles of smoothed base models. They focus on deriving optimal ensemble weights for generalization rather than on analyzing the particularities of ensembles in the RS setting. As they do not consider multiple testing correction and the confidence of the applied Monte Carlo sampling, they obtain statements about empirical, distributional robustness of their classifiers, rather than individual certificates with high confidence. Due to this difference setting, we do not compare numerically.
B ADDITIONAL RELATED WORK
Extensions outlined in $ Cohen et al. (2019) focuses on the addition of Gaussian noise to drive fz-robustness results. However, various extensions with other types of noise and guarantees have been proposed.
By using different types of noise distributions and radius calculations, Yang et al. (2020); Zhang et al. (2020) derive recipes to determine certificates for general Ep and specifically showcase results forp 1,2, 20.
Numerous works have shown extensions to discrete perturbations such as b fe-petuurbation (Lee et al.
2019: Wang et al.) 2021 Schuchardt et al. (021), graphs (Bojehevski et al. 20200 Gao et al. 2020).
patches Levine & Feizi 2020) or manipulations of points in a point cloud Liu et al. (2021).
Dvijotham al. (2000) provide theoretical derivations for the application of both continuous and
discrete smoothing measures.
Mohapatra al. (2020) improve certificates by considering gradient information.
Beyond norm-ball balls certificates, Fischer et al. (2020 Li al. (2021) show how geometric operations such rotation or translation be certified via Randomized Smoothing.
Chiang et al. (2020): Fischer et al. 202T show how the certificates can be extended from the setting of
classification to regression (and object detection) and segmentation, respectively. In the classification setting, la et al. 2020) extend certificates from just the top-1 1 class to the top-k classes. Similarly, Kumar 2020a) certify the confidence of the classifier not, just the top class prediction.
Beyond the inference-time evasion attacks, Rosenfeld et al. (020)) showcase RS as defense against data poisoning attacks.
Many of these extensions are orthogonal to the standard Randomized Smoothing approach and thus orthogonal our improvements. We showcase that these improvements carry over from the l case to other f, norms in App. H.3.7
Limitations Recently, some works also have investigated the limitations of Randomized Smoothing: Mohapatra et al. (2021) point out the limitations of training for Randomized Smoothing as well as the impact on class- wais- accuracy. Kumar al. (2020b); Wu et al. (2021) show that for p > 2, the achievable certification radius quickly diminishes in high- dige-sinnni spaces.
C MATHEMATICAL DERIVATION OF VARIANCE REDUCTION FOR ENSEMBLES
In this section, we present the algebraic derivations for S5 skipped in the main part due to space constraints.
Individual Classifier y' y + y
In 5 define f'(x:) =: y E Th' the sum of two random variables
The behavior on a specific clean sample x is modeled by y with mean e E R" the expectation of the logits for this sample over the randomization in the training process, and corresponding covariance
15

---

Published as a conference paper at ICLR 2022
Eg:
Ely'd =
6,11 Palmmac1cmm
Covlu/] Ee
We note that: (i) we omit the lower triangular part of covariance matrices due to symmetry, (ii) e and Ne are constant across the different f' for a fixed and (iii) that due to (ii) and our modelling assump- tions all means, (coivariances and probabilities are conditioned on æ, c.g., Bly'd = Bly" æ c. However, as we define all random variables only for a fixed æ, we omit this.
Similarly, we model the impact of the perturbations introduced during RS by v with mean zero and covariance Ep:
ElyyI1
pp. p p.m
Cov(y/ Epp
p.m
That is, we assume e' to be the expected classification a model learns for the clean sample while the covariances N. and Mp encode the stochasticity of the training process and perturbations, respectively, As Jo models the local behavior under small perturbations and y! models the global training effects, we assume them be independent:
E
0211 + 02,1
Pp.1mOp.10pm + Pe.1m0c,100,m
Coviy'1=E E= E. Ep-
p.m c.m
The classifier prediction arg max, By is determined by the differences between logits. We call the difference between the target logit and others the classification margin. During certification with RS, the first step is to determine the majority class. Without loss of generality, we assume that has been determined to be index 1, leading to the classification margin majority class logit y/1 larger than those of all other classes yı- We define z = [22, Zn 1T. skipping the margin of y1 to itself. Under the above assumptions, the statistics of the classification margin for single classifier are:
y1 Y/. If z; 0 for all + 1,
E[2,] Var[z,]
oi + o7 + + 0², 2pp.1.0p.10p. 22e,,100..10ct
Ensemble Now, we construct ensemble of of these classifiers. Using soft-voting (cf. Eq. 2 to compute the ensemble output ÿ = Σi= y We assume the y and y to be correlated with 2p for classifiers + j and similarly model the correlation of v with C.Eo for Sp. E [o, 1]. Letting y" := [gy y IT denote the concatenation of the logit vectors of all classifiers, we assemble their joint covariance matrix in block-wise manner from the classifier individual covariance matrices as:
Σp + Ee
Ep + LoE
Cov "y'l Σ"
Σ,
+ M.
We then write the corresponding classification margins Ø1 Ti. in vector notation ž [22, .., 2m IT again skipping the margin of in to itself. By linearity of expectation we obtain E[a]] = B[2a] = G equivalently
C1
2
f
Cj2:m]
16

---

Published as a conference paper at ICLR 2022
We define the ensemble difference matrix D Rm-1xxm with elements di such that # Dy
j mod m =
Do
else if mod m imodmm m, j E (,, mki,, (2,..., else
This allows us to write the covariance matrix of the ensemble classification margins
Cov = D
Now we can evaluate its diagonal elements or use the multinomial theorem and rule on the variance of correlated sums obtain the variance of individual terms:
+ 2()) Sp (o), + on. - ppp110010p.1
k + ++
Var[z;]
(0 + o2 2pc,10en10es)
222
h2
Variance Reduction We can split Var[a:] into the components associated with the perturbation effect (k) and the clean prediction (k),, all as functions of the ensemble element number k.
Now, we analyze these variance components independently by normalizing them with the correspond- ing components of an individual classifier:
(k)(k) (1 (p ()) + t 2pp.110p.10..)) 1 + Cp(k- k-oo Cp
(1
k(02,,1 of. 2pp.1.pp10pp.
(k) (1+ Sokk 1)) + to? 2pc,1.0e.1c..) 1 Co - k Go (1)
k(o2,1 + oZ 2pc.1.0c10c..)
k
We observe that both variance components go towards their corresponding correlation coefficients. Sp and Ç. as ensemble size grows, highlighting the importance of non-identical classifiers.
Especially for samples that are near decision boundary, this variance reduction will lead to much more consistent predictions, turn significantly increasing the lower confidence bound p, and thereby the certified radius as per Theorem 3.1
D THEORY VALIDATION
In this section, present experiments validating the modeling assumptions made in $5 derive the reduced variance over perturbations RS resulting from using ensembles of similar classifiers. There are three main assumptions we make:
The (pre-softmax) output of single model be modeled f'(x) y, + ye where ye captures the prediction on clean samples and yp the effect of perturbations with mean zero.
The clean and perturbation components Ye and yy are independent.
The covariance of y and yo between different classifiers i + j can be parametrized as Cov 9/)) Ep and similarly Cov(y y!) C.E..
To show that these assumptions are valid, we additionally assume multivariate Gaussian distributions and evaluate an ensemble of 1 50 ResNet20 on 100 clean samples ær, each perturbed with n. = 1000 different error terms and compare the obtained distributions and covariance matrices with our modeling. We generally observe excellent agreement between observation and model at low noise level a, 0.25 and good agreement at a high noise level of 1.0.
Individual classifier predictions We model the predictions of individual classifiers f: Rd - R on perturbed inputs x + e for single arbitrary but fixed æ and Gaussian perturbations e o, with f'(x) y + ye.
17

---

Published as a conference paper at ICLR 2022
Probschility density
Probabalitt density
Probability density
0.6-
0.8
Gaustaa as per model
Gaussian as per model
Zero meon
True distribttion Mote
0.6-
Thue disaaluttion for ((4
True Distribution
0.1-
Thue discaibutton 3N- Pytn
0.4-
112-
0.0
0.0
-1
-2
0
2
-5
-1
-2
0
2
Norraulized most prodiction pyon-dd
Normalized perturbation effcet (f((z) 801/0
Mean perturb tiom offectt
(a)
0.25
Profutiilty density
Probability density
Profubality denaty
0.8
Gousion as per model
Gausiio as per model
Zero mean
True distribation Mrort
0.6
True disetiuttion for Be [x)
True Distribution
1.1-
dacatbution je Pyo-
0.1
0.4
112
0.2
11.0
-4
-2
0
0.01
8
-4
-2
0
2
0.0
-1
Notrzalized mesa prediction Myort-e/o
Normalkad petturbation ellect (f(()) ) 2.//
Moxn perturbstion ellect
(b)
1.00
Figure 9: Comparison of modeled and true distributions of clean prediction (left), perturbation effect (middle), and mean perturbation effect (right) for o, 0.25 (top) and or = 0.5 (bottom).
We can interpret the clean component Ye in two different ways: either as the prediction y. := fxx on the clean sample æ or the mean prediction over perturbations of this sample Ye := (u.,N (f + +)]. In both cases, we assume ye to be distributed with mean first case is illustrated in Fig. 8 where we rescale both our model and the predictions with the sample-wis wise mean and vari- ance over classifiers and observe excellent agreement between model and observed distribution. The second case is illustrated in the leftmost column in Fig. | for two different de, where we again observe excellent agreement between the true distri- bution and our model. Here we denote with (a)(a)) the mean prediction over perturbed samples E (0..0 [f (xc +)], cor- responding to the setting of ye == N= [f + c)) and
Probubiityy donsity
0.6
Gausian as per model
True distribution
Ptú
R and covariance Σc. The
0.4-
0.2-
0.0
-2 0 2
Normalized prediction (f(x) - ci/a
Figure 8: Comparison of the true and modelled distribution of clean predictions ye = f(x).
similarly with denote with (z(()) the mean prediction over clas-
sifiers for an unperturbed sample Ex (x)), corresponding to the setting of ye := f(x).
The perturbation effect yp assumed to be mean zero, either following from local linearization and zero mean perturbations when defining the clean component ye := f(x) or directly from the definition of the clean component as ye := VE,,,(,,.,) [f + e)]. For small perturbations (a, = 0.25), the assumption of local linearity holds, and we observe mean perturbation effect distributed very tightly around 0 (see top right pane in Fig. D. For larger perturbations (a. = 1.00), this assumption of local linearity begins to break down, and we observe much wider spread of mean perturbation effect (see bottom right pane in Fig. 9). At both perturbation levels, we observe an excellent agreement of the perturbation effect model with the observed data when using the definition of := E.-Ai(o.a (x.)))
|f [f + e)] (green in the middle column in Fig. 9.. Using := f(x). we still observe great agreement at the lower perturbation magnitude but notable disagreement high perturbation levels. While both definitions for y. are fully compatible with our derivation in $5) we choose present version based on ye == (x) it allows for better intuitive understanding.
18

---

Published as a conference paper at ICLR 2022
0.30
0.15
0.00
0.15
(a) Cov == ( yp)
(b) Cov(ye == f(x). Up)
Figure 10: Covariance (ye, Up) of clean and perturbation components and yp. respectively,
for de = 0.25 using Ye == (xy(x') (left) ye f(x) (right). The upper diagonal block corresponds
to Cov (ye, yo) and the lower one to Cov yn)"
0.30
0.15
-0.00
-0.15
True covariance
Delta
Modeled covariance
(a) Cov w²) C. 0.0051
0.10
0.05
0.00
-0.05
True covariance
Delta
Modeled covariance
Cov (v/, v/) and Sp 0.8519
Figure 11: Comparison of modeled (right) and (left) covariance matrix between the clean and perturbation components y (top) and yr, (bottom), respectively, of different classifiers for a, 0.25 using ye == fxx)
Correlation between clean and error component We model ye and yp separately to distinguish between randomness over perturbations, which are introduced during RS. and over the models introduced during training with different random seeds. As models the large scale effects of training and yp the smaller local scale local effects inference time perturbations, we assume them to be independent, corresponding to covariance Cov Ve.j) R O Vi,j. Depending on which definition of y. we use, we obtain either the two covariance matrices in Fig. I0 where the upper left-hand block is the covariance of you the lower righthand block the covariance of yp and the off-diagonal blocks (yv(yp... Ve.z). ). In the setting of ye == (x')))) the two components ye and y perfectly independent can be in Fig. 10a In the setting of y. := f(x), very small terms can be seen in the off diagona blocks shown in Fig. TOb. Overall, the agreement with model is excellent in both cases.
by the 0 off-diagonal blocks in the covariance matrix shown
19

---

Published as a conference paper at ICLR 2022
Inter classifier correlation structure In our analysis, we consider ensembles of similar classifiers which are based on the same architecture and trained using the same methods, just using different random seeds. Hence, assume that the correlation between the logits of different classifiers has similar structure but smaller magnitude than the correlation between the logits of the same classifier. Correspondingly, parametrize the covariance between y and y for classifiers i + with Dp and similarly between y and yd with G.C., for Gos Se E [0, 1]. To evaluate this assumption, we consider all (2) pairings classifiers and compute the resulting pairwise covariance matrices for the clean components y' :- f() and perturbation effects v In Fig. 11 we show the resulting covariance matrices (left column), our model (right column), and the delta between the two (center column). Again we observe excellent agreement to the point that even given the delta maps, it is hard to spot the differences in the covariance matrices.
Model fit conclusion We conclude that our model able to capture the relevant behavior even of deep networks (here ResNet20) with great accuracy that goes beyond what is required for a theoretical analysis to allow for interesting insights into the underlying mechanics.
E PROOF OF THEOREM 6.
We first restate the theorem:
Theorem (Theorem 6.1 restated). For a, B [0, E my <... < nsy CERTIFYADP:
1. returns ćA at least 1 confident that G is robust with a radius of least T.
2. returns @ before stage s only if at least 1 - B confident that robustness of G at radius r can not be shown.
3. for n, 2 log, (8)) has maximum certifiable radii at least as large as CERTIFY for
Proof. We show statements 1, 2, and individually.
Proof of I. If phase in CERTIFYADP returns čλ, then via Theorem 3.1 G will be not robust with probability most a/s. s. Via Bonferroni correction (Bonferroni) 1936). if CERTIFYADP returns čΛ. then G is robust with radius at least r with confidence s(a/s)
a.
Proof 2. If CERTIFYADP returns in phase s, have PA P/A ((r/o.) the minimum success probability for certification at r. By the definition of the UPPRACONTDDNCC probability of G will be PA PA with confidence at least 3/(s - 1). Hence, if phase j returns Ø robustness of G cannot be shown at radius r with confidence 1 - B/(s 1). even with access to the true success probability or infinitely many samples. Again with Bonferroni correction (Bonferroni 1936). the overall probability that G' is robust at r despite CERTIFYADP abstaining early is at most (s 1)(8((s 1)) B.
the true success
Proof of 3. Finally, to prove the last part, we assume cnts [čA] = yielding the largest certifiable radii for any given and a. Now, the largest radius provable via Theorem with samples
2/2 Cohen et al. 2019s. Similarly, for n., samples a/s, it (g) "*, Then have the following equivalences:
(2) (a) ())=()))0>00
3 + a-=
+ n. log n(log log 8) + n2 = n11 log, (s))
Hence, if we choose n2 [n(1 log, (s)) then we can certify at least the same maximum radius with samples at a/s as with samples at a. Thus, overall, we can certify the same maximum radius at a.
F ADDITIONAL RANDOMIZED SMOOTHING DETAILS
This section contains definitions needed for the standard certification via Randomized Smoothing, CERTIFY, proposed Cohen et al. (2019).
20

---

Published as a conference paper at ICLR 2022
cl..... Zn I + En for 61...., Cn ~ NN G.). Then it counts how often F predicts which class for these #1,...,22 nn and returns the corresponding dimensional array.
SAMPLEUNDERNOIS((FF
σ.) first samples inputs ......, 2n with
UPPLRCON:BND(A: n. - a) returns an upper bound on p with confidence at least - a where p is unknown probability such that k B(n, p). Here, ((n,p) p) is binomial distribution with parameters n and p.
LOWERCONFBNDlE n, a) is analogous to UPPERCONFBND but returns lower bound p instead of an upper bound with confidence
a.
We point the interested reader Cohen et al. (2019) for more details about Randomized Smoothing.
G EXPERIMENTAL DETAILS
In this section, provide greater detail the datasets, architectures, and training and evaluation methods used for our experiments.
G.1 DATASET DETAILS
We use the MNIST, CIFARIO, and ImageNet datasets in our experiments.
MNIST (Deng 2012) contains 60'000 training and 10'000 test set images partitioned into 10 classes for the 10 digits. We evaluate images from the test set.
CIFAR10 (Krizhevsky et al., 2009) (MIT License) contains 00000 training and 10'000 test set images partitioned into classes. We evaluate every 20th image of the test set starting with index (0, 20, 40, .... 9980) in our experiments, following previous work (Cohen et al. 2019).
ImageNet (Russakovsky et al. 2015) contains 1'287' 167 training and 000 validation images, partitioned into 1000 classes. We evaluate every 100th image of the validation set starting with index 0 (0, 100, 200, 49900) in our experiments, following previous work (Cohen et al. 2019).
G.2 ARCHITECTURE DETAILS
We use different versions of ResNet (He et al./ 2016) for our experiments. Concretely, we evaluate ensembles of ResNet20 used network architectures
Table 6: Parameter count of the
and ResNet110 on CIFAR10 and ensembles of ResNet50 on ImageNet.
Dataset
Architecture
Parumeter count
CIFAR1O
ResNet110 has about 6.35 times as many parameters as ResNet20 (see Table (). ResNet50 instantiated for ImageNet has substantially more parameters than R1sNet110 instantiated for CIFARIO 10 because of the significantly larger input dimension of ImageNet samples.
ResNet110
1'730'714
ImageNet
ResNe150
25'557'033
G.3 TRAINING METHODS
To obtain high certified radii via RS, the base model F must be trained to cope with the added Gaussian noise e. To this end, Cohen et al.] (2019) propose data augmentation with Gaussian noise during training, referred as GAUSSIAN in the following. Building on this, Salman al. (2019) suggest SMoOTHADY, a combination of adversarial training (Madry et al. 2018 Kurakin et al. 2017 Rony et al. 2019) with the data augmentation from GAUSSIAN. (Here, we always consider the PGD version.) While improving accuracy, this training procedure is computationally very expensive. MACER (Zhai et al., 2020) achieves similar performance with a cheaper training procedure, adding a loss term directly optimizing surrogate certification radius. [eong & Shin (2020), called CONSISTENCY in the following, replace this term with a more easily optimizable loss, further decreasing training time and improving performance. Depending the setting, the current state-of-fe -ortte--rttttt results are either achieved by SMOOTHADV, MACER, CONSISTENCY, or a combination thereof.
21

---

Published as a conference paper at ICLR 2022
Further, Salman et al. 2020) present denoised smoothing, where the base classifier f h o f is the composition of a denoiser h that removes the Gaussian noise from the imput and an underlying classifier f that is not specially adapted to Gaussian noise, e.g., accessed via an API.
G.4 TRAINING DETAILS
All models are implemented in PyTorch (Paszke et al. 2019) (customized BSD license).
For GAUSSIAN training (No license specified), we use the published code by Cohen et al. (2019). For each network, we chose a different random seed, otherwise using identical parameters. Overall, we trained 50 ResNet20 and 10 ResNet110 for each 0, {0.25, 0.5, 1.0] on CIFARIO. For ImageNet, we trained ResNet50 for oe = 1.0, and took the results for ae E {0.25, 0.50] from their GitHub.
For CONSISTENCY training (MIT License), use the code published by Jeong & Shin (2020) and CONSISTENCY instantiation built on GAUSSIAN training. Similarly to GAUSSIAN, we use a different random seed and otherwise identical parameters for all networks. We chose the parameters reported to yield the largest ACR by Jeong & Shin (020) for any given de, except for a, = 0.25 on ImageNet, for which no parameters were reported. In detail, for CIFAR10 10 generally use 1) = 0.5, using A = 20 for a. = 0.25 and À = 10 for o, = 0.5 and a. = 1.0 (all for both ResNet20 and ResNet110). In this way, we train 50 ResNet20 and 10 ResNet110 for each og E {0.25, 0.5, 1.0]. For ImageNet, we use 1) = 0.1 and x = 5 for = 1.0. For a. = 0.25 and a. 0.5, we use 17 0.5 with X = 10 respectively
5.
For SMOOTHADV training (MIT License), we use the PGD based instantiation of the code published by (Salman et al. (2119). Note that due to the long training times, we only train SMOOTHADY models ourselves on CIFARTÓ. The individual models we train only differ by random seed, all using PGD attacks. For a, 0.25, we train with = 10 steps, an e 255/255, 10 epochs of warm-up, and Manin = 8 noise terms per sample during training. For o, = 0.5, we train with T = 2 steps, an e = 511/255, 255, 10 epochs of warm-up, and mamin = 2 noise terms per sample during training. Finally, 512/255, 10 epochs of warm-up, and Murain = 2 noise
o. 1.0, train with T = 10 steps, terms per sample during training.
We use the same training schedule and optimizer for all models, i.c., stochastic gradient descent with Nesterov momentum (weight = 0.9, no dampening), with an f2 weight decay of 0.0001. For CIFARIO,
batch size of 256 and an initial learning rate of 0.1, reducing it by a factor of 10 every 50 epochs and training for a total of 150 epochs. For ImageNet, we use the same settings, only reducing the total epoch number to 90 and decreasing the learning rate every 30 epochs.
All single MACER (No license specified) trained models for CIFARIO are taken directly from Zhai al. (2220).
For our experiments on denoised smoothing, we use the 4 white box denoisers with DNCNN-WIDE architecture trained with learning schedules 3, 4, and for STAB ResNet110 and the ResNet110 trained on unperturbed samples for 90 epochs from [Salman et al. 2020) (MIT License).
To rank the single models for CIFARIO, we have evaluated them on a disjunct hold-out portion of the CIFAR10 test set. Concretely, we use the test images with indices 1, 21, 41, .... 9981 to rank the single models for GAUSSIAN, CONSISTENCY, and SMOOTHADV trained models. The performances of individual models values we report are those of the models with the best score on this validation set for CIFARTO 10 and the best score on the test set for ImageNet (favoring individual models in this setting). For ensembles of size k < 10 and k < 50 for ResNet110 and ResNet20, respectively, we ensemble the k models according to their performance on the hold-out set. We note that other combinations might yield stronger ensembles, but an exhaustive search of all combinatorially many possibilities is computationally infeasible.
CIFAR10 models were trained on single GeForce RTX 2080 Ti and ImageNet models on quadruple 2080 Tis. We report the epoch-wise and total training times for individual models in Table 7 (when trained sequentially one at time).
22

---

Published as a conference paper at ICLR 2022
Table Reference training times for individual models on GeForce RTX2080 Tis
Dataset
Training
Architecture
#GPUs
time per Epoch [s]
total time [h]
ResNet110
41.8
1.74
GAUSSIAN
ResNet22
9.6
0.40
ResNet110
3,31
CIFARIO
CONSISTENCY
ResNet20
18.5
0.77
SMOOTHADY (a, = 0.25)
ResNet110
2471
102,96
SMOOTHADW (o, (0.5,1.0)
ResNet110
27.5
ImageNet
CONSISTENCY
ResNet50
4
3420
85
G.S EXPERIMENT TIMINGS
To evaluate the ensembles of ResNet20 and ResNet110 CIFARIO, 2080 Ti, and to evaluate ensembles of ResNet50 on ImageNet, we use double 2080 Tis.
single GeForce RTX
For both datasets, 500 samples are evaluated per experiment as discussed in App. G.1 Below we list the time required for certification using CERTIFY and no K K-Consensus aggregation:
ResNet110 on CIFARIO (I GPU): 4.12h per single model; 41.2h per ensemble of 10
ResNet20 on CIFARIO (I GPU): 0.825h per single model; 41.3h per ensemble of 50
ResNet50 on ImageNet (2 GPUs): 8.75h per single model; 26.2h per ensemble of
The timing for different ensemble sizes scales linearly between full size and individual model timings. The time required for certification using CERTIFYADP or K-Consensus aggregation or both can be obtained by dividing the timings reported above with the speed-up factor TimeRF reported for the corresponding experiments.
H ADDITIONAL EXPERIMENTS
In the following, present numerous additional experiments and more detailed results for some of the experiments presented in 7
H.1 ADDITIONAL RESULTS ON CIFAR10
In this section, we present more experimental results on CIFAR10. Concretely, Table presents the
performance of ensembles of ResNet20 (k (1, 50)) and ResNet110 (k (1, 10)) trained using wide range of of methods for a, = 0.25, a, = 0.5, and ar 1.0. We again consistently observe that ensembles significantly outperform their constituting models, implying that ensembles are effective for various training methods and model architectures, as well as different In particular, they lead new state-of-te -fethh-rrt both in ACR and at most radii a. 0.25, a. 0.5, and o. 1.0.
Fig.
12
visualizes the evolution of ACR and certified accuracy with ensemble size for a, = 0.25. In we visualize the evolution of certified accuracy over radii for GAUSSIAN trained models.
Fig.
1
H.2
ADDITIONAL RESULTS ON IMAGENET
Extending the results from Table alsoo provides ensemble results on ImageNet for o, 0.25, and a, 0.5 with CONSISTENCY trained ResNet50. Similarly to CIFAR10, we consistently observe that ensembles significantly outperform their constituting models, implying that ensembles are effective on various datasets. In particular, achieve new state-of-the-art both in ACR and certified accuracy at most radii for a, = 0.25, σ. = 0.50, and a. = 1.00.
Additionally, we report the performance of all individual classifiers which constitute the ensembles, where & = 3 combines all three and = the first two for GAUSSIAN and CONSISTENCY, and the last two for SMOOTHADV. Note that the SMOOTHADV models taken directly from Salman et al.) (2019) and were trained with different parameter (256, 512, and 1024). We observe that if there large discrepancy between model performance at some radii (e.g., the SMOOTHAN ADV models at
23

---

Published as a conference paper at ICLR 2022
Table 8: Average certified radius (ACR) and certified accuracy various radii for ensembles of models (k- = are single models) for a various training methods and model architectures on CIFAR10. Larger is better.
Radios
Training
Architecture
0.0
0.25
0.50
0.75
1.00
1.25
1.50
1.75
2.00
2.25
2.50
ResNet110
10
1
0.541
0.450
77.6
83.4
70.6
60.0
55.4
45.6
30.6
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.9
0.0
GAUSSIAK
1
0.434
77.4
63.4
43.6
26.6
0.0
0.0
0.0
0.0
0.0
0.0
0.0
80,2
0.0
50
0.517
80.4
68.6
52.8
38.8
0.0
0.0
0.0
0.0
0.0
0.0
0.0
75.6
57.2
46.4
0.0
0.0
0.0
0.0
ResNet110
10
0.583
76.8
70.4
60.4
51.6
0.0
0.0
0.0
0.0
0.0
0.0
0.0
CONSISTENCY
0.528
71.8
64.2
$5.6
45.2
0.0
0.0
0.0
0.0
0.0
0.0
0.0
2e
0.547
73.0
65.4
57.6
47.6
0.0
0.0
0.0
0.0
0.0
0.0
50
0.551
73.0
64.8
57.0
50.2
0.0
0.0
0.0
0.0
0.0
0.527
70.4
62.8
54.2
0.0
0.0
0.0
0.0
SMOOTHADY
ResNet t110
10
0.560
71.6
64.8
$7.8
52.4
0.0
0.0
0.0
0.0
0.0
0.0
0.0
Res
77.4
0.0
ResNet110
0.535
65.8
54.2
42.2
32.4
22.0
14.8
10.8
6.6
10
0.648
69.0
60.4
49.8
40.0
29.8
19.8
15.0
9.6
0.0
0.0
GAUSSIAN
0.534
65.2
55.0
43.0
33.0
22.4
16.2
9.6
5.0
2e
5
0.615
67.6
58.4
47.4
38.8
27.4
19.8
13.2
7.0
0.0
0.0
0.0
50
0.630
67.2
59.4
48.6
39.2
29.0
21.6
14.6
8.2
0.0
0.0
1
0.708
63.2
54.8
48.8
42.0
36.0
29.8
22.4
16.4
0.0
0.0
0.0
ResNet110
32.0
26.2
0.50
CONSISTENCY
1
0.691
62.6
55.2
47.4
41.8
34.6
28.4
21.8
16.8
0.0
0.0
0.0
28
62.2
29.8
23.4
20.6
50
0.729
61.6
55.8
49.2
43.0
37.8
30.6
24.2
20.0
0.0
0.0
0.0
0.707
52.6
47.6
46.0
41.2
37.2
31.8
28.0
23,4
0.0
0.0
SMOOTHADY
ResNet110
10
0.730
52.4
48.6
45.8
42.6
38.8
34,4
30.4
25.0
0.0
0.0
0.0
MACER
ResNet110
0.668
62.4
54.4
48.2
40.2
33.2
26.8
19.8
13.0
0.0
0.0
0.0
ResNet110
48.0
22.0
13.8
11.0
10
0.607
49.4
44.0
37.6
29.6
24.8
20.0
16.4
13.6
11.2
9.4
6.8
GAUSSIAN
0.538
48.0
41.2
35.0
27.8
21.6
17.8
14.8
12.0
9.0
20
0,590
49.22
42.8
37.8
30.4
24.0
19.4
16.2
13.8
11.2
8.2
5.0
50
0.597
49.6
43.0
37.4
30.4
23.6
18.6
15.8
13.6
11.2
1
0.778
45.4
41.6
37.4
33.6
28.0
25.6
23.4
19.6
17.4
16.2
14.6
1es
10
0.809
46.4
42.6
37.2
33.0
29.4
25.6
23.2
21.0
17.6
16.2
14.6
1.00
CONSISTENCY
0.757
43.6
39.8
27.6
24.6
22.6
19.4
17.4
15.4
28
5
0.779
43.4
40.0
35.6
32.2
28.0
24.8
22.2
20.4
17.4
15.8
13.8
50
0.788
45.2
40.6
36.4
28.2
24.6
22.0
20.2
17.8
16.0
ResNet1le
1
0.844
45.4
41.0
38.0
34.8
32.2
28.4
25.0
22.4
19.4
16.6
14.8
SMOOTHADY
ResNet110
MACER
ResNet110
0.797
42.8
40.6
37.4
34.4
31.0
28.0
25.0
21.4
18.4
15.0
13.8
ACR
Cortifird aceurary [X] radius 0.25
Certiffeed necurey (90 at radii as 0.75
0.60
72
50-
45-
40-
0.45
GANSSAAN RN
64-
35-
CoNSSTESSY RN110
62-
0.10
MACER RN110
Coeserency RN20
60-
30-
SMoorHAnZ RN110
0.35
58
25
00
Ensemble size
Exsemblle sioo
Enseruble size
Figure 12: Evolution of average certified radius (ACR), certified accuracy at r = 0.25, and = 0.75 with ensemble size for various underlying models and a, 0.25 on CIFAR 10.
24

---

Published as a conference paper at ICLR 2022
Certifed aceurecy [%]
Certified meturacy [%]
Certified aecuracy (%)
100-
1000
100-
ResNEr
10 NerN
ResNer20
60
60-
60-
ResNer20
50 RisNie120
40-
40
20
0
0-
0.00
0.25
0.50
0.75
1.00
0.0
0.5
1.0
1.5
2.0
Redius
Radius
Radius
(a) C. 0.25
(b) 0. 0.50
(c) d. 1.0
Figure 13: CIFARIO certified accuracy over certified radius for GAUSSIAN trained models.
small radii), the ensemble might perform worse than the strongest constituting model. Overall and when performance homogenous, however, ensembles once again obtaín significant performance increases over individual models.
H.3 ADDITIONAL ABLATION STUDY OF ENSEMBLES
This section presents a range of experiments on different different aspects of variance reduction through ensembles for Randomized Smoothing. In particular, we cover aggregation approaches, the effect of ensemble size, the variability of our results, certifications with an equal number of inferences, ensembles of differently trained models, and ensembles of denoisers.
H.3.1 AGGREGATION APPROACHES
We experiment with various instantiations of the general aggregation approach described in $4 In particular, we consider soft-voting, hard-voting, soft-voting after softmax, and weighted soft-voting.
Soft-voting
We simply average the logits to obtain
f(x)
Σ (m))
Hard-voting
We process the outputs of single models with the post-processing function (HV (x)) that provides one-hot encoding arg max f (x) before averaging to obtain
1 j=arg (ax
f(x)
Soft-voting after softmax We process the outputs the single models by applying the softmax function procepsoo function Yeo/tmaz to obtain
ex)(
f(x) E, (x)))
Weighted soft-voting We consider soft-voting with classifier-wise weights w learned on separate holdout set and obtain
1 Σ n (x)) K
f(x)
We compare these approaches in Table 10 and observe that the two soft-voting schemes perform very similarly and outperform the other approaches. We decide to use soft-voting without soft-max for its conceptual simplicity for all other experiments.
25

---

Published as a conference paper at ICLR 2022
Table 9: Average certified radius (ACR) and certified accuracy at various radii for ensembles of models (k are single models) for various training methods ImageNet. Larger is better.
Radius
Training
k
ACR
0,0
0.50
1.00
1.50
2,00
2.50
3.00
3.50
GAUSSIAN
0.477
66.7
49.4
0.0
0.0
0.0
0.0
0.0
0.0
0.512
63.0
54.0
0.0
0.0
0.0
0.0
0.0
0.0
0,516
54.2
0.0
0.0
0.0
0.0
0.0
0.0
0.25
CONSISTENCY
0,509
0.538
65.0
56.2
0.0
0.0
0.0
0.0
0.0
0.0
0.545
65.6
$7.0
0.0
0.0
0.0
0.0
0.0
0.0
SMOOTHADY
0.528
65
56
MACER
0.544
57
0
GAUSSIAN
0.733
57.2
45.8
37.2
28.6
0.0
0.0
0.0
0.0
0.793
34.0
0.806
55.4
35.0
0.0
0.5
CONSISTENCY
0.799
54.0
48.0
41.2
35.2
0.0
0.0
0.0
0.0
43.6
37.0
0.868
57.0
52.0
44.6
38.4
0.0
SMOOTHADY
0.815
54
49
43
37
0
0
MACER
0,831
0.849
42.4
35.6
30.0
25.2
20.2
15.4
12.2
10.0
0.856
42.4
37.2
31.4
25.8
19.6
15.4
12.0
8.4
GAUSSIAN
0.839
40.8
35.6
29.4
25.8
20.4
15.6
12.2
8.0
2
0.944
45.0
37.6
33.4
29.8
22.8
18.0
14.6
11.0
0.968
43.8
38.4
34.4
29.8
23.2
18.2
15.4
11.4
1,022
43.2
39.8
35.0
29.4
24.4
22.2
16.6
13.4
0.990
42.0
37.2
34.4
29.6
24.8
20.2
16.0
13.4
1.0
CONSISTENCY
1.006
41.6
38.6
35.2
29.6
25.4
21.2
17.6
13.8
1.086
44.8
41.0
36.6
32.4
27.4
22.4
19.4
15.6
1.108
44.6
40.2
37.2
34.0
28.6
23.2
20.2
16.4
1.011
40.6
38.6
33.8
29.8
25.6
20.6
18.0
14.4
1,002
39.4
35.4
32.0
29.2
25.6
22.2
20.0
16.4
SMOOTHADV
0.927
32.0
30.8
28.6
26.0
23.6
21.0
19.2
18.6
1.022
37.4
33.4
31.4
29.4
26.6
23.8
21.0
18.6
1.065
34.0
24.6
21.2
18.8
MACER
1.008
48
43
36
30
25
18
14
reported by Zhai al. 2020
26

---

Published as a conference paper at ICLR 2022
Table 10: Comparison of various aggregation methods for ensembles of 10 ResNet110 o, 0.25 on CIFAR1O. Larger is better.
Radius
Training
Aggregation method
ACR
0.00
0.25
0.50
0.75
soft-voting
0.541
83,4
70.6
55,4
42.0
hard-voting
0.529
83.8
69.4
53.2
40.6
GAUSSIAN
soft-voting after softmax
0.540
84.0
70.8
55.2
41.8
weighted soft-voting
0.538
83.4
70.4
54.6
41.8
soft-voting
0.583
76.8
70.4
60.4
51.6
hard-voting
0.574
77.2
69.6
60.0
50.6
CONSISTENCY
soft-voting after softmax
0.584
77.0
70.4
60.6
51.8
weigthed soft-voting
0.579
76.4
70.6
59.6
51.2
Table 11: Effect of ensemble size & ACR and certified accuracy at different radii, for GAUSSIAN and CONSISTENCY trained ResNet20. Larger is better.
Radius
Training
ACR
0.0
0.25
0.50
0.75
1.00
1.25
1.50
1.75
2.00
2.25
2.50
0.434
77.4
63.4
43.6
26.6
0.0
0.0
0.0
0.0
0.0
0.0
0.486
79.6
66.0
49.6
34.6
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.25
0,500
80.2
50.4
0.0
0.0
0.0
0.0
0.0
10
0.510
80.4
67.4
51.8
37.4
0.0
0.0
0.0
0.0
0.0
50
0.517
80.4
68.6
52.8
38.8
0.0
0.0
0.0
0.0
0.0
0.0
0.0
GAUSSIAN
0.538
48.0
41.2
35,0
27.8
21.6
17.8
14.8
12.0
9.0
5.6
3,4
0.579
49.2
42.8
36.4
30.2
23.0
18.8
15.6
13.0
10.8
7.4
4.4
0.590
49.2
37.8
24.0
16.2
11.2
10
0.592
48.8
42.8
37,0
30.4
23.6
19.0
16.2
13.6
11.0
9.2
5.0
50
0.597
49.6
43.0
37.4
30.4
23.6
18.6
15.8
13.6
11.2
9.0
5.0
0.528
71.8
64.2
55.6
45.2
0.0
0.0
0.0
0.0
0.0
0.0
0.0
73.2
0.25
0.547
73.0
65.4
57.6
47.6
0.0
0.0
0.0
0.0
0.0
0.0
0.0
10
0.547
72.2
65.0
57.4
48.8
0.0
0.0
0.0
0.0
0.0
0.0
0.0
73.0
57.0
CONSISTENCY
0.757
43.6
34.8
30.8
27.6
24.6
22.6
19.4
17.4
13.8
0.777
44.2
39.6
36.8
31.8
28.4
25.0
22.4
17.6
15.6
14.0
1.0
5
0.779
43.4
40.0
35.6
32.2
28.0
24.8
22.2
20.4
17.4
15.8
13.8
0.784
44.4
40.6
36.4
32.2
29.2
24.2
22.2
20.4
17.6
16.0
14.2
0.788
45.2
40.6
36.4
32.4
28.2
24.6
22.0
20.2
17.8
16.0
14.6
H.3.2 ENSEMBLE SIZE
In Table II we present extended results on the effect of ensemble size for different training methods and dee Generally, observe that ensembles of sizes 3 and already significantly improve over the performance of a single model, while further increasing the ensemble size mostly leads to marginal gains. This aligns well with our theory from
Certified accuracy 100
H.3.3 VARIABILITY OF RESULTS
we report mean and standard deviation of ACR and certified accuracy for 50 GAUSSIAN and CONSISTENCY trained ResNet20 with different random seeds, either combined to 10 ensembles with k or evaluated individually. Generally, we observe a notably smaller standard deviation of the ensembles compared to individual models. We visualize this in Fig. 14 where we show the 43 region.
In Table 12
20-
0.00
0.25
0.50
0.75
1.00
Radius r
H.3.4
EQUAL NUMBER OF INFERENCES
Figure 14: Mean and +3 inter- of certified accuracy over ra- dius computed over 50 GAUS- SIAN trained ResNet20.
In Table S
we compare the certified accuracy of an ensemble
of k
10 ResNet110 obtained with 100'000 samples
27

---

Published as a conference paper at ICLR 2022
Table 12: Mean and standard deviation of ACR and certified accuracy for CIFARIO at various radii for 50 ResNet20 with different random seeds either evaluated as 10 ensembles with k 5 or as individual models o, 0.25.
Radius
Training
k
ACR
0.25
0.50
0.75
1
0.4350 + 0.0046
61.08 = 1.08
43.74 = 0,86
27.58 + 0.88
GAUSSIAN
5
0.4994 1 0.0025
66.58 1 0.62
51.04 1 0.76
36.38 0.42
1 0.5202 + 0.0049
63,57 + 0.86
54.22 +: 1,03
44.30
+: 0.89
CONSISTENCY
5 0.5445 + 0.0017
64,90 + 0.66
56.86 + 0.49
47.94 + 0.68
Table 13: Comparing and ensemble and individual model an equal number of total inferences on CIFAR 10: average certified radius (ACR) and certified accuracy at various radii for ensembles of k models (k 1 are single models) for various sampling sizes n. Larger is better.
Radius r
Training
ACR
0.0
0.25
0.50
0.75
1.00
1.25
1.50
1.75
2.00
100'000
0.535
65.8
54.2
42.2
32.4
14.8
10.8
6.6
0.0
GAUSSIAN
1'000'000
0.552
65.8
54.6
42.2
32.6
22.4
15.2
11.0
7.0
3.8
10
100'000
0.648
69.0
60.4
49.8
40,0
29.8
19.8
15.0
9.6
0.0
100'000
0.708
63.2
54.8
48.8
42.0
36.0
29.8
22.4
16.4
0.0
CONSISTENCY
1 00000'000
0.752
63.2
54.8
48.8
42.0
36.4
30.4
23.0
17.8
14.6
100'000
0.756
26.2
19.8
on CIFARIO with that of individual model obtained with 1'000'000, i.e. at the same computational cost.
For both GAUSSIAN and CONSISTENCY training, observe that all radii which can mathemati- cally be certified using n = 100' samples the ensemble it significantly outperforms the individual model at equal computational cost. Note that the individual models with n 1'000'000 samples have the same or just a marginally larger certified accuracy at all radii < 1.75 than the same indi- vidual model with
100'000 samples. Only at radius 2.00 where certification is mathematically impossible with n = 100' '00 samples does using additional samples increase the certified accuracy. Note however, that, in contrast our ensembles, this does influence the actual accuracy of the underlying model in any way, but simply allows to derive tighter confidence bounds. Table shows similar results for ImageNet and ensembles of k ResNet110, implying that these observations hold for various datasets.
H.3.5 ENSEMBLES OF DIFFERENTLY TRAINED MODELS
In Table 15 we show how ensembles built from differently trained base models (SMOOTIADY, MACER, and CONSISTENCY) perform. We observe that the ensemble of all three models is strictly better than any individual model, suggesting that ensembles also work for models trained with differ- training methods. However, the improvements ensembling similar classifiers in the same setting (see also Table X for comparison). This is again due very heterogeneous model performance some radii, where the strongest models are weighed down by weaker ones.
significantly smaller than the improvements of
H.3.6 ENSEMBLES OF DENOISERS
was shown (Salman et al. 2020) that standard neural networks can be robustified with respect to Gaussian noise by training a suitable denoiser and evaluating the original model on the denoised sample. Here, we aim to overcome the drawback of any ensemble, the need to train multiple diverse models, by instead training different denoisers and building ensemble by combining these denoisers with a single underlying model. We show the general applicability of ensembling approach by
Table 16: Denoised smoothing en- sembles on CIFARIO at a. = 0.25
Radius
k: ACR
0.0
0.25
0.50
0.75
0.378 0.445
76.4
56.6
36.8
19.2
75.2
62.2
45.8
29.0
28

---

Published as a conference paper at ICLR 2022
Table 14: Comparing and ensemble and an individual model an equal number of total inferences on ImageNet: average certified radius (ACR) and certified accuracy at various radii for ensembles of k models 1 are single models) for various sampling sizes n. Larger is better.
Radius r
Training
nt
ACR
1.00
1.50
2.50
3.00
3,50
4.00
100'000
1.022
43.2
39.8
35.0
29.4
24.4
22.2
16.6
13.4
0.0
CONSISTENCY
300'000
1.060
43.2
39.6
35.2
29.6
24.6
22.4
16.8
14.2
11.4
100'000
1.108
44.6
40.2
37.2
34.0
28.6
23.2
20.2
16.4
0.0
Table 15: Building ensembles with differently trained base models: average certified radius (ACR) and certified accuracy at various radii for ensembles and their constituting models. Larger is better.
Radius r
Model
ACR
0.0
0.25
0.50
0.75
SMOOTHADV MACER
0.542
74.4
65.4
56.2
48.0
0,518
77.8
69.0
52.6
39.0
CONSISTENCY
0,546
75.2
66.0
57.0
46.6
Ensemble (SMOOTHADY and CONSISTENCY)
0.572
75.6
68.6
59.8
50.6
Ensemble (SMOOTHADY, MACER and CONSISTENCY)
0.567
78.4
69.4
58.8
48.0
applying it to the setting of denoised smoothing (Salman al. 2020). We consider pre-trained denoisers and combine them with single standard ResNet 110 (see App. G.3 for details). Comparing the strongest resulting model with an ensemble all at a; 0.25, we observe a 17% ACR improvement. Training strong denoisers with current methods is challenging. However, based on these results we are confident that advances in denoiser training combined with ensembles can present an efficient way to obtain strong provable models.
H.3.7 ADDITIONAL NORMS
Below, we demonstrate that our approach generalizes beyond the f2-norm setting and generalizes well to improve the robust accuracy against ly-, f1- and -nom bounded attacks.
- -orm robustness is typically derived directly from norm bounds (Yang et al., 2020 Salman ctt al. 2019). and hence our results for the f--nomm are directly applicable.
In Table 17 and Table T8]
we show the effectiveness of our approach for fo-norm bounded perturba- tions using the training and certification method from Lee et al. (2019). For both, we use the default hyper-paramede
(which is not the same the in standard Randomized Smoothing from Cohen cct al. (2019)), i.c. a = 0.8 for MNIST and a = 0.2 for ImageNet. We observe that even an ensemble of just 3 models outperforms the individual models in every setting.
In Table 19 we similarly show the effectiveness of our approach for & no-morm bounded perturbations using training with uniform noise and the uniform noise based certification method from Yang et al.) (2020) with o, = 1.0. We observe again that even an ensemble just 3 models outperforms the single model in every setting.
H.4 ADDITIONAL COMPUTATIONAL OVERHEAD REDUCTION EXPERIMENTS
This section contains additional experiments for the computational overhead methods introduced in Whenever we use CERTIFYADP, we set 0.001.
Adaptive sampling and K K-coonemsuss Table 20 is an extensive version of Table 3, In Table 21 we
show the effect adaptive sampling and T-Consensus aggregation for GAUSSIAN trained ResNet110 on CIFAR10 10, analogously to Table 20 Certifying
ensemble with CERTIFYADP and K-Consensus aggregation achieves approximately the same certified accuracy as CERTIFY while the certification time is up to 67 times faster. In particular, for both training methods and for each radius, the certifying the ensemble of & = 10 networks with CERTIPYADR and K <--oosennus aggregation is faster than certifying individual model with CERTIFY while the certified accuracy significantly improved
29

---

Published as a conference paper at ICLR 2022
Table 17:
Effect of ensemble size on ACR and certified accuracy at different radii for norm on MNIST. Larger is better.
Radius
k
ACR
3
4
8
1
3,231
97.8
90.0
73.7
49.9
48.5
23.6
17.3
7.9
1.6
1.6
3
3.575
98.4
92.5
79.0
56.1
54.7
38.2
21.6
10.7
2.4
10
3.612
98.4
92.5
79.1
57.0
55.6
38,9
22.1
11.1
2.4
2.4
Table 18: Effect ensemble size on ACR and certified accuracy at different radii for lg norm on ImageNet. Larger is better.
Radius
ACR
7
8
2.340
53.8
48.8
42.0
30.8
25.2
24.6
23.6
22.2
16.8
3
2.986
57.4
53.6
50.4
39.0
33.8
33.0
32.8
30.0
26.0
0.0
in most cases. In addition, we confirm our previous observation that the sample reduction is most prominent for small radii (for a given σ.) while KCR increases with radius.
H.4.1 ADDITIONAL ADAPTIVE SAMPLING EXPERIMENTS
This section contains other experiments with CERTIFYADP, highlighting various aspects of adaptive sampling for ensembles and also individual models.
Adaptive sampling for ensembles on CIFARIO For comparison with Table (respectively Ta- ble ble and (1). where we show the combined effect of K-Consensus aggregation and adaptive sampling, we show results for just applying adaptive sampling to the same setting Table [2] using {n,} {100, 1 1'000, 10'000, 120'000}, o, 0.25, and ensembles of 10 CONSISTENCY trained ResNet110. We observe that the speed-ups for small radii are comparable to applying both K- K-Consensus aggregation and adaptive sampling, only few samples have to be evaluated. The additional benefit due to K-CCnnsesuus aggregation grows as the later certification stages are entered more often for larger radii, highlighting the complementary nature of the methods. Note that for radius r = 0.75, 100 samples, and even 1'000 are never sufficient for certification but can still yield early abstentions.
Adaptive sampling for ImageNet ensembles In Table 23 we demonstrate the applicability of our adaptive sampling approach to ensembles of ResNet50 on ImageNet. particular, we achieve sampling reduction factors of up to 42 without incurring a significant accuracy penalty. For fixed oe we empirically observe larger speed-ups at smaller radii. This effect, however, depends on the underlying distribution of success probabilities and would be expected to invert for model that has true success probabilities close to PA As 0.5 for most samples.
Effect of sampling stage sizes Additionally, in Table 24 investigate how the choice of the number of phases and the number of samples in each phase influence the sampling gain for various radii and models. We observe that few as 100 samples can be sufficient certify abstain from to 80% of samples, making schedules with many phases attractive. However, when the true success probability is close to the one required for certification, many samples are required to obtain sufficiently tight confidence bounds on the success probability to decide either way. This leads to many samples being discarded for schedules with many phases. Additionally, the higher per phase confidence required due to Bonferroni correction requires more samples to be drawn to be able to obtain the same maximum lower confidence bound to the success probability. This latter effect becomes especially pronounced for larger radii, where higher success probabilities required.
Ablation of a and 3 Fig. 15] we illustrate the effect of different a and on the first phase of certification with CERTIFYADP where consider just 100 perturbations. Increasing reduces
30

---

Published as a conference paper at ICLR 2022
Table 19: Effect of ensemble size ACR and certified accuracy at different radii for l norm on CIFAR10 10 for models with ResNet28 architecture. Larger is better.
Radius
ACR
0.25
0.50
0.75
0.571
71.2
65.4
60.2
51.6
0.610
72.4
10
0.622
72.4
69.6
64.8
57.2
Table 20: Adaptive sampling ((n,} {1000 1'000, 10'000, 120'000 and 5-Consensus agg- on CIFARIO for 10 CONSISTENCY ResNet1l0. SampleRF and TimeRF are the reduction factors in comparison to standard sampling with ra 100'000 (larger is better). ASR, is the % of certification attempts returned in phase j. KCR is the % inputs for which only classifiers were evaluated.
Radius
d,
acCcen [%]
ASR [%]
ASR₂ [%]
ASRa [%]
ASR4 [%]
SampleRF
KCR [%]
TimeRF
0.25
0.25
70.4
84.8
10.2
4.2
0.8
55.24
39.3
67.16
60.6
69.8
3.0
18.09
57.3
25.07
0.75
0.25
52.0
27.4
8.8
8.6
5.68
87.8
10.06
1.00
0.50
38.6
41.2
47.0
7.8
4.0
14.79
78.3
24.01
1.25
0,50
32.2
46.6
9.8
37.6
6.0
8.14
92.7
15.06
26.2
11.2
29.6
9.2
97.5
12.31
1.75
20.8
32.0
3.0
19.02
33.14
2.00
1.00
17.6
61.8
27.4
8.0
2.8
91.0
19.93
35.26
2.25
1.00
16.2
68.2
21.2
7.8
2.8
93.4
20.27
36.66
14.6
7.8
20.6
2.0
19.38
34.45
the confidence 1 1 a required for certification and hence makes early certification more likely for the same underlying true success probabilities (see Fig. 15ah. Increasing 3 reduces the confidence 1 B 3 that certification will not be possible required for early termination and hence makes early termination more likely for the same underlying true success probabilities (see Fig. 15b). Overall, we observe that evaluating even only 100 perturbations allows to, with high probability. abstain from or certify samples with wide range of true success probabilities. We only have to continue with the costly certification process for samples in narrow band of true success probabilities (see Fig. [5c). greatly reducing the expected certification cost.
H.4.2
ADDITIONAL. K- K-CONSENSUS EXPERIMENTS
In Table 25 we present a more detailed version Table We emphasize that for K and 10 for 110 and ResNet20, respectively, we achieve the same ACR with the full ensemble while reducing the certification time by factor of 1.59 and 2.01, respectively.
31

---

Published as a conference paper at ICLR 2022
Table 21: Adaptive sampling with {n,} {100, 1'000, 10'000, 120'000} and K -consenssu early stopping with = 5 on CIFARIO with an ensemble of 10 GAUSSIAN trained ResNet110. Sample and time gain the reduction factor in comparison standard sampling with 100'001 000 (larger better). ASR, is the percentage of samples returned phase j. KCR is the percentage of samples for which only K classifiers were evaluated.
Radius
0c
aCCzen [%]
ASR;
ASR2
ASRs
ASR4
SampleRI'
KCR [%]
TimeRF
0.25
0.25
70.6
76.4
17.2
4.4
2.0
28.80
26.8
32.63
0.50
0.25
55.4
30.4
59.2
7.8
2.6
19.80
63.5
28.73
0.75
0.25
42.0
39.4
10.2
41.8
8.6
6.19
89.7
11.14
1.00
0.50
30.2
53.4
31.6
10.8
4.2
13.89
77.5
22.60
1.25
1.00
20.2
74.4
16.4
7.0
2.2
24.93
71.4
38.31
1,50
1.00
16.6
66.8
26.0
29.34
75.7
45.80
1.75
1.00
73.0
20.6
4.6
30.61
51.18
2.00
1.00
32.97
88.5
56.80
2.25
1.00
9,4
82.4
8.0
6.8
2.8
21.32
92.7
38.60
2.50
1.00
6.4
82.4
6.4
6.8
4.4
14.77
95.4
27.63
Table 22: Efffec of adaptive sampling with {n,) {100, 1'000, 10'000, 120'000) for ensembles of 10 GAUSSIAN respectively CONSISTENCY trained ResNet110 on CIFARIO with o, = 0.25. ASA, and ASC, the percentages of samples abstained from and certified in phase j. respectively
Radius
Training
accunn [%6]
ASA1
ASC,
ASAa
ASCs
ASA,
SampleRF
TimcRF
0.25
GAUSSIAN
70.6
62.4
13.2
10.0
7.6
3.8
1.2
0.4
1.4
30.48
31.30
70.4
67.93
0.75
GAUSSIAN
422
52.0
0.0
27.4
39.0
0.0
9.8
8.8
37.8
51.8
3.4
4.8
5.6
3.0
6.16
5.68
6.32
5.83
Table 23: Adaptive sampling with {n,} = {100, 1'000, 10'000, 120'000) ImageNet with an ensemble of 3 CONSISTENCY trained ResNet50. SampleRF and TimeRF are the reduction factor in comparison certification with CERTIFY with n 100'000. ASR, is the percentage of samples returned in phase j.
Radius
[%]]
ASR:
ASRa
ASRs
ASR,
SampleRF
TimeRF
0.50
0.25
56.8
21.2
75.0
0.8
43.00
42.32
1.00
0.50
44.8
31.0
59.4
7.0
2.6
20.14
20.31
1.50
0.50
38.4
40.2
7.6
46.2
6.0
7.57
7.74
2,00
1.00
28.6
48.6
39.4
9.2
2.8
18.98
19.19
2,50
1.00
23.2
55.8
8.0
31.8
4.4
10.49
10.70
3.00
1.00
20.2
58.6
11.4
24.4
5.6
9.69
9.88
3,50
1.00
16.4
65.4
7.4
3.2
24.0
3.12
3.20
Exported Probnbiliny Cestifying
Exported Probubility Abstaining
Expected Prolsbility of Continuing
1.0-
1.0-
1.0-
0.8-
0.5
0.8
3.101
0.6-
0.0
0.44
0.4
0.4
=:
0.0-
0.0-
0.0
0.0
0.2
0.4
1.8
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
Underlying Profushility Magontoy Class
Underlying Probubilityy Majoenty Class
Underlying Probability of Majority Closs
(b)
Figure 15: Expected probability of certifying (a), abstaining (b) or continuing to the next phase (c) of CERTIFYADP after the first phase. conditioned on the underlying probability of the majority class. consider various a and B. We are in the setting with o, 0.25 with stage sizes Ni {100, 1'000, 10'000, 120' 120'000), i.e. the first phase whose simulated outcomes observe here has 100 samples.
32

---

Published as a conference paper at ICLR 2022
Table 24: Effect of adaptive sampling for individual ResNet110 CIFARIO 0.25. ASA, and ASC₁ are the percentages of samples abstained from and certified in phase j. respectively. We compare multiple sampling count progressions {ng) }-
Soakea
Ibaring
[n:}
32cun [S]
ASA,
ASt:
ASAr
ASK
ASA4
ASL-
ASA
A344
ASA:
ScmppieR
Tirelll!
1000 L80
00.0
53.0
30.2
3.2
4.5
0.0
0.8
6/3
0.6
10.34
10.45
201000, 1100000
00.0
53.6
35.6
1.6
1.2
0.0
0.8
0.2
10.0
7.50
1.30
21.4
GM SAAAN
100, 30T000) 1861000
09.2
13.3
31.0
10.6
13.4
1-4
1.4
04
B.
10.0
80
16.81
16:77
THERL 101000
660
514
138
180, 1000. 101000, 127000
00.0
13.5
21.8
1.8
9.2
2.0
36
188
1.2
0.6
20.00
21.22
000000 50
00.0
14.5
34.0
Du
02
0A
0.
3.00
21.6
25
120, 110
05.9
58.5
16.2
1.2
r'00 1000000
060
150
16
00
0.
sprono, 1001000
66.0
22.6
00
0.0
1.9
TDUL 1900, 1007000
06.0
68.0
11.
1.
16
98
0.
80
80
19000
19.57
CONSISTENCY
607000, 1067000
00.0
160
22.4
122
06
3.19
100,
060
580
1.3
341000 1279000
66.0
11.
06
100, 1100000
50.6
0.0
51.
30.8
18
0,
186
O0TOOLL 1001000
38.4
24.5
60.4
0M
S0/0OLL 1000000
2016
30L2
06.5
DA
2.5
68
04
137
190
00
107000 1667000
50.5
516
25.0
00
11000 101050 110000
30.4
0.0
60.
25.6
3.8
5.0
48
98
00
00
00
6.11
6.14
Smo00 007000 1101000
31.6
30.
662
044
00
00
SU SC0L 220/000
31.4
25.2
06.0
18
0.2
2/0
LOC, 500,
24 1251000
302
0.0
48.5
D0
10.8
21.2
36
1.2
1.3
26
36
7.4
7,49
0.75
1OO. LEC7000
46.2
0.0
41.
40.0
0.0
90
09
06
1.53
135
1100000
46.2
43.8
45.
522
00
08
0.
00
400
4.0
69
1'000 1100000
46.4
00
1O0, 30TCOAL 100
-6.2
1131
36.4
23.6
12.
54
4.6
04
u0
5.2
5A1
101000
-7.31
41.0
64.2
08
100, 7000. 001000 1200000
-5.4
0.0
32.4
60
83
46.
52
50
50
06
00
533
5.00
500000 60/000 00000 1201000
46.5
47.6
47.0
100
14
1.0
00
00
20
00
110
Table 25: Effect of K K-Consensus aggregation on CONSISTENCY trained ensembles of 10 ResNet110 and 50 ResNet 20 CIFARIO a. 0.25.
Radius
Architecture
K
ACR
TimeRF
KCR [
0.0
0.25
0.50
0.75
0.576
70.2
60.0
50.4
3.25
85.8
0.581
77.0
70.0
60.6
51.6
2.29
79.7
ResNet111
0.583
76.8
70.4
60.4
51.6
1.59
74.2
10
0,583
76.8
70.4
60.4
51.6
1.00
0.0
0.544
65.2
57.0
48.4
6.50
87.7
0.549
72.6
65.0
57.4
50.0
4.41
82.4
ResNet20
5
0.550
72.8
65.0
57.0
50.2
2.99
76.4
10
0.551
73.0
64.8
57.0
50.2
2.01
69.8
50
0,551
73.0
64.8
57.0
50.2
1.00
0.0
33


Reviews:
[{"review_id": "z_XscCMNetZ", "reviewer": "Reviewer_RVtN", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths\n\n+Important research problem\n\n+Well written and well-organized\n\n+Interesting analysis on why ensemble works\n\n+Extensive evaluation\n\nWeaknesses\n\n-Evaluation only on the L2 certification\n\n-Missing related work", "summary_of_the_paper": "The paper aims to boost randomized smoothing (RS). Specifically, the paper demonstrates that an ensemble of diverse base models can enhance RS both theoretically and empirically. The key insight is that reducing variance of ensembles over the introduced perturbations can lead to more consistent classifications for inputs. The paper also introduce two simple  yet effective techniques to speed up the certification. Extensive experiments are conducted to thoroughly evaluate the proposed boosted RS.\n", "summary_of_the_review": "Certifying an ensemble of models is faster than certifying an individual model through the proposed two strategies. However, training an ensemble of models requires far more computational resources and time than training an individual model. Although the authors mainly leverage the pretrained models, but in practical applications this may be infeasible. I would suggest the authors discuss the issues of training an ensemble of models.   \n\nThe authors say that “…substantially increased certifiable radii for samples close to the decision boundary..” in abstract, but no results to validate this claim. I would like to see the results for those samples having a small margin.  \n\nThe authors assume that y_c is the clean part and y_p is the perturbation/noisy part. How to define y_p and y_c when evaluating the real image datasets? Or y_p and y_c are just for analysis? \n\nWhat’s the impact of $\\alpha$ and $\\beta$? \n\nIn table 1, why ensemble is less effective than MACER when radius r is small? \n\n“Even when using only K = 2, we already obtain 81% and 70% of the ACR improvement obtainable by always evaluating the full ensembles (k = 10 and k = 50) “ => How do you calculate the numbers 81% and 70%? \n\n In Table 3, what do SampleRF, KRC, and TimeRF mean or short for? \n\nMy another concern is that the experimental results are only for certifying L2 perturbation.  There are several papers that design RS to certify $L_0$, $L_1$, $L_\\infty$ perturbation.  For example, \n\n$L_0$: Wang et al. “Certified robustness of graph neural networks against adversarial structural perturbation via Randomized Smoothing”\n\n$L_1$: Lee et al., “Tight Certificates of Adversarial Robustness for Randomly Smoothed Classifiers”, NeurIPS 2019\n\n$L_\\infty$: Yang et al., Randomized Smoothing of All Shapes and Sizes\n\nI am also really interested in whether the proposed ensemble is also effective for certifying $L_0$, $L_1$, or/and $L_\\infty$ perturbation. \n\nThe following papers also derive certified robustness based on randomized smoothing: \n\nJia et al., “Certified Robustness for Top-k Predictions against Adversarial Perturbations via Randomized Smoothing” \n\nZhang et al., “Black-Box Certification with Randomized Smoothing: A Functional Optimization Based Framework”\n\nMohapatra et al., “Higher-Order Certification for Randomized Smoothing”\n\nKumar et al., “Certifying Confidence via Randomized Smoothing”\n\nKumar et al., “Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness”\n\nFischer  et al., “Certified Defense to Image Transformations via Randomized Smoothing”", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "enlF8rj8X3G", "reviewer": "Reviewer_ZAuf", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper has several strengths.\n\n- The problem that this work is tackling is both of interest and importance.\n- The theoretical analysis presented in section 5 along with figure 2 potentially motivates the use of model ensemble.\n- The Adaptive Sampling proposed in section 6 algorithm is practical.\n- The experiments conducted in this work are extensive. They cover several frameworks for training smooth classifiers and several datasets. In most of the setups, model ensemble resulted in improvements in the certified accuracy.\n\nHowever, there are several concerns that need to be addressed:\n\n- The main claim about the time reduction that CertifyADP provides is based on an unfair comparison with Certify. The amount of information that both algorithms provide is not the same. CertifyADP tells whether an instance is certified with a pre-chosen radius $r$ or not, however it gives no hint about the actual radius that the instance is certified with, which is the output of Certify. I am not trying to lower the importance of CertifyADP since in many practical situations, it is useful to know whether an instance is certified with a given radius or not, but the comparison against Certify needs to be fair.\n\n- The writing of the paper can be significantly improved (especially section 5). \n\n\nHere are few comments/suggestions:\n\n- typo: In page 4 third paragraph, \"$y_p$ to be zero-mean\".\n\n-  While the analysis in section 5 are interesting, consider shrinking it to include more experiments in the main paper such as Table 15. It is interesting to see that the ensemble of models trained by different frameworks outperforms individual models. \n\n- Consider switching the locations of figures 5 and 6 since figure 6 is mentioned in the text before figure 5.\n\n- The definitions of SampleRF, TimeRF, and KCR are in the last page in the paper. However, they are important to understand table 3 and the \"Computational Overhead Reduction\" paragraph.\n\n- Figures 2 and 3 need more elaborative discussion.", "summary_of_the_paper": "This paper integrates model ensembles with randomized smoothing to improve the certified accuracy. The methodology is motivated theoretically by showing the effect of model ensemble on reducing the variance of smooth classifiers. Moreover, it proposes an adaptive sampling algorithm to reduce the computation required for certifying with randomized smoothing. Extensive experiments were conducted on CIFAR10 and ImageNet datasets.", "summary_of_the_review": "This work has several merits as pointed out in the main review. The key concern is the unfair comparison between Certify and CertifyADP presented in this work. Moreover, the writing of this paper can be vastly enhanced for better exposure. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "-P5d9gq-HyY", "reviewer": "Reviewer_CscF", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n1. From both theoretical and experimental perspectives, the authors demonstrate the effectiveness of combining randomized smoothing with ensembles in building certified robust classifiers.\n2. Though the theoretical arguments include many assumptions, the authors carried out experiments to validate them.\n3. They proposed Adaptive Sampling and K-consensus algorithms to reduce the computational cost, making their method more practical.\n\nWeaknesses/Concerns:\n\nWhile the empirical evidence are sufficient to support the effectiveness of using ensemble to boost the performance of RS, I have some concerns about the assumptions in the theoretical arguments. \n\nIt assumes that the \"correlation between the logits of different classifiers has a similar structure but smaller magnitude than the correlation between logits of one classifier\". Since different classifiers only differ in random seed for training, they should share behaviors in common. However, it is quite possible that such commonness is captured by $\\mathbb{E}_l[f^l(x)]$, reflecting the underlying task, network architecture, dependence on $x$, etc., while the deviations of different models $\\delta^i$ and $\\delta^j$ are uncorrelated.\n\nIn fact, as shown in Figure 11(a) in the appendix, the off-diagonal blocks in the Delta subfigure are almost identical to the ones in the True covariance subfigure. It would be possible to reconstruct an argument about the variance reduction solely based on the assumption that $Cov(y^i_c, y^j_c)$ are near zero.", "summary_of_the_paper": "In this paper, the authors propose using the aggregation of an ensemble of similar models as the base classifier in the randomized smoothing (RS). They show that the use of ensembles helps reduce the variance of the base classifier under noisy inputs, thus, improving the performance of RS. Both theoretical arguments and numerical experiments are included to support their idea. Further, the authors provide practical algorithms that significantly reduce the computational costs of their method.\n", "summary_of_the_review": "The underlying topic of constructing a certified robust classifier is important. The main idea of the paper is sound and is supported by extensive experiment investigations. Further, the authors proposed algorithms to reduce the computational cost, making their method not only workable but also practical. There also includes empirical studies to validate (to some extent) the assumptions in their theoretical arguments. Hence, I would like to support the publication of the paper.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper integrates model ensembles with randomized smoothing to improve the certified accuracy. The methodology is motivated theoretically by showing the effect of model ensemble on reducing the variance of smooth classifiers. Moreover, it proposes an adaptive sampling algorithm to reduce the computation required for certifying with randomized smoothing. Extensive experiments were conducted on CIFAR10 and ImageNet datasets.

The strengths of the paper are as follows:
+ In terms of significance of the topic, the problem tackled in the paper is significant and highly relevant. 
+ The motivation of using model ensemble is clearly illustrated via a figure and well justified with theoretical analysis. 
+ Algorithmically, the paper proposes Adaptive Sampling and K-consensus algorithms to reduce the computational cost, making the method more practical.
+ Experimentally, the paper exhibits competitive results against several frameworks for training smooth classifiers and on several datasets.
Decision: Accept (Spotlight)