Enhancing Certified Robustness of Smoothed Classifiers via Weighted Model Ensembling
Authors: Chizhou Liu
Yunzhen Feng
Ranran Wang
Bin Dong
Venue:  (2021)
Keywords: Adversairal Robustness
Randomized Smoothing
Ensembling

Abstract: Randomized smoothing has achieved state-of-the-art certified robustness against $l_2$-norm adversarial attacks. However, it is not wholly resolved on how to find the optimal base classifier for randomized smoothing. In this work, we employ a Smoothed WEighted ENsembling (SWEEN) scheme to improve the performance of randomized smoothed classifiers. We show the ensembling generality that SWEEN can help achieve optimal certified robustness. Furthermore, theoretical analysis proves that the optimal SWEEN model can be obtained from training under mild assumptions. We also develop an adaptive prediction algorithm to reduce
the prediction and certification cost of SWEEN models. Extensive experiments show that SWEEN models outperform the upper envelope of their corresponding candidate models by a large margin. Moreover, SWEEN models constructed using a few small models can achieve comparable performance to a single large model with a notable reduction in training time.

Under review as a conference paper at ICLR 2021
ENHANCING CERTIFIED ROBUSTNESS OF SMOOTHED CLASSIFIERS VIA WEIGHTED MODEL ENSEMBLING
Anonymous authors Paper under double-blind review
ABSTRACT
Randomized smoothing has achieved state-of-the-art certified robustness against 12-norm adversarial attacks. However, it is not wholly resolved on how to find the optimal base classifier for randomized smoothing. In this work, we employ a Smoothed WEighted ENsembling (SWEEN) scheme to improve the performance of randomized smoothed classifiers. We show the ensembling generality that SWEEN can help achieve optimal certified robustness. Furthermore, theoretical analysis proves that the optimal SWEEN model can be obtained from training under mild assumptions. We also develop an adaptive prediction algorithm to reduce the prediction and certification cost of SWEEN models. Extensive experiments show that SWEEN models outperform the upper envelope of their corresponding candidate models by a large margin. Moreover, SWEEN models constructed using few small models can achieve comparable performance single large model with notable reduction in training time.
INTRODUCTION
Deep neural networks have achieved great success in image classification tasks. However, they are vulnerable adversarial examples, which are small imperceptible perturbations the original inputs that can cause misclassification (Biggio et al., 2013; Szegedy et al., 2014). To tackle this problem, researchers have proposed various defense methods train classifiers robust adversarial perturbations. These defenses can be roughly categorized into empirical defenses and certified defenses. One of the most successful empirical defenses is adversarial training (Kurakin et al.. 2017, Madry et al. 2018), which optimizes the model by minimizing the loss over ad adversarial examples generated during training. Empirical defenses produce models robust to certain attacks without theoretical guarantee. Most of the empirical defenses are heuristic and subsequently broken by more sophisticated adversaries (Carlini & Wagner 2017 Athalyy et al., [018] |esato et al.) 2018)] Tramer et al. 2020). Certified defenses, either exact or conservative, are introduced to mitigate such deficiency in empirical defenses. In the context of (p. norm-bounded perturbations, exact methods report whether an adversarial example exists within an I, ball with radius centered
given input
Exact methods are usually based on Satisfiability Modulo Thcories (Katz et al.] 2017 Ehlers] (017))
mixed-intege integer linear programming (Lomuscio & Maganti 2017 Fischetti & Jo 2017), which
computationally inefficient and not scalable (Tjeng et al.) (019). Conservative methods are more
computationally efficient, but might mistakenly flag safe data point vulnerable to adversarial
examples (Raghunathan et al. [201 Sal [Wong& & Kolter 22018; WWong et al. 2018 Gehr et al. 2018)
Mirman et al. 22188; Weng et al. [0.88) Zhang et al.] 2018] Raghunathan al. 201 1bb Dvijotham
2018b Singh et al. 2018 Wang et al. [218b; Salman et al. 2019b] Croce et al. 2019 Gowal jet al. 2018 Dvijotham al.) 2018a| Wang 2018a)) However, both types of defenses are not
et al.)
scalable to practical networks that perform well on modern machine learning problems (e.g., the
ImageNet (Deng et al. 2009) classification task).
Recently, new certified defense technique called randomized smoothing has been proposed [Lecuyer ct al. 2019; Cohen et al. 2019). A (randomized) smoothed classifier is constructed from a base classifier, typically deep neural network. It outputs the most probable class given by its base classifier under a random noise perturbation of the input. Randomized smoothing is scalable due to its independency over architectures and has achieved -fate-of-the-art certified Ig-robustness. In theory, randomized smoothing can apply to any classifiers. However, naively using randomized smoothing on standard-trained classifiers leads poor robustness results. It is still not wholly

---

Under review as a conference paper at ICLR 2021
resolved on how a base classifier should be trained that the corresponding smoothed classifier has good robustness properties. Recently, Salman et al. (2019a) employ adversarial training to train base classifiers and substantially improve the performance of randomized smoothing, which indicates that techniques originally proposed for empirical defenses can be useful in finding good base classifiers for randomized smoothing.
In this paper, we take a step towards finding suitable base models for randomized smoothing by model ensembling. The idea of model ensembling has been used in various empirical defenses against adversarial examples and shows promising results for robustness (Liu et al. 2018 Strauss
ct al. 2018 Pang et al., 2019; Wang et al.) 2019; Meng al., 2020 [enn et al.) 2020p. Moreover, an ensemble can combine the strengths of candidate models to achieve superior clean accuracy (Hansen
Salamon 1990 Krogh& Vedelsby, 1994). Thus, we believe ensembling several smoothed models can help improve both the robustness and accuracy. Specifically for randomized smoothing, the smoothing operator is commutative with the ensembling operator: ensembling several smoothed models is equivalent to smoothing an ensembled base model. This property makes the combination suitable and efficient. Therefore, we directly ensemble a base model by taking some pre-trained models as candidates and optimizing the optimal weights for randomized smoothing. We refer to the final model as a Smoothed WEighted ENsembling (SWEEN) model. Moreover, SWEEN does not limit how individual candidate classifiers trained, thus is compatible with most previously proposed training algorithms on randomized smoothing.
Our contributions are summarized follows:
1. We propose SWEEN to substantially improve the performance of smoothed models. Theo- retical analysis shows the ensembling generality and the optimization guarantee: SWEEN can achieve optimal certified robustness w.r.t. the defined y-robustness index, which is an extension of previously proposed criteria certified robustness (Lemmal TT and SWEEN
can be easily trained to near-optimal risk with surrogate loss (Theorem 2
2. We develop an adaptive prediction algorithm for the weighted ensembling, which effectively reduces the prediction and certification cost of the smoothed ensemble classifier.
3. We evaluate our proposed method through extensive experiments. On all tasks, SWEEN models consistently outperform the upper envelopes of their respective candidate models in terms of the approximated certified accuracy by large margin. In addition, SWEEN models can achieve comparable or superior performance to large individual model using a few candidates with a notable reduction in total training time.
RELATED WORK
In the past few years, numerous defenses have been proposed to build classifiers robust adversarial examples. Our work typically involves randomized smoothing and model ensembling.
Randomized smoothing Randomized smoothing constructs a smoothed classifier from a base classifier via convolution between the input distribution and certain noise distribution. It is first proposed as a heuristic defense by (Liu et al., 2018 Cao & Gong 2017). [ecuyer et al. (2019)
first prove robustness guarantees for randomized smoothing utilizing tools from differential privacy. Subsequently, a stronger robustness guarantee is given by Li ct al. (2018). [ohhnn et al. (2019)
provide tight robustness bound for isotropic Gaussian noise in le robustness setting. The theoretical properties of randomized smoothing in various norm and noise distribution settings have been further discussed in the literature (Blum al. 2020 Kumar et al., 2020; Yang et al., 2020 Lee al. 2019 Teng et al, 2219:; Zhang et al. (2020). Recently, a series of works (Salman et al.) [019a] /haii al. 2020) develop practical algorithms train a base classifier for randomized smoothing. Our work improves the performance of smoothed classifiers via weighted ensembling of pre-trained base classifiers.
Model ensembling Model ensembling has been widely studied and applied in machine learning as technique to improve the generalization performance of the model (Hansen & Salamon 1990) Krogh & Vedelsby 1994). Krogh & Vedelsby (1994) show that ensembles constructed from accurate
In this paper, "candidate model" and "candidate" refer to an individual model used in an ensemble. The term "hase model" refers model which randomized smoothing applies.
2

---

Under review as a conference paper at ICLR 2021
and diverse networks perform better. Recently, simple averaging of multiple neural networks has been a success in ILSVRC competitions (He et al. 2016: Krizhevsky et al., 2017 Simonyan & Zisserman 2015). Model ensembling has also been used in defenses against adversanal examples (Liu et al.
2018 Strauss et al. 2018 Pang et al. 2019, Wang et al. 2019] Meng et al. 2020 Sen et al. (020). Wang al. (2019) have shown that jointly trained ensemble of noise injected ResNets can improve clean and robust accuracies. Recently, Meng et al. (2020) find that ensembling diverse weak models can be quite robust to adversarial attacks. Unlike the above works, which are empirical or heuristic, we employ ensembling in randomized smoothing to provide theoretical robustness certification.
3 PRELIMINARIES
Notation Let (1. M). We overload notation slightly, letting refer the M-dimensional one-hot vector whose k-th entry is 1 for lo = 1,.., M as well. The choice should be clear from context. Let A {(11. P2.... ................................ pk]pp:
E. =} be the k-dimensional probability simplex for k E N., and A = AM- For an M-dimensional function f. we use f; to refer to its i-th entry, i i= 1,2, 0 and variance 1² We use d- to denote the inverse of the standard Gaussian CDF, and use I to denote the gamma function. We use R denote the of non-negative real numbers. For a), b]. We use S2(-) to denote Big-Omega
.M. We use (N o² to denote the d-dimensional Gaussian distribution with mean
T, a, b E R, S 6, we define clip(æ;; a, b) notation that suppresses multiplicative constants.
Neural network and classifier Consider classification problem from X C IRd to classes y. Assume the input space X has finite diameter D sup || - x2ll2 < oc. The training set {[x,, 3;)) is i.i.d. drawn from the data distribution D. We call f probability function or classifier if it is mapping from Rd A or Y, respectively. For a probability function f. its induced classifier I* is defined such that (xx = arg m M (z)). For simplicity, we will not distinguish between f and f when there is no ambiguity, and hence all definitions and properties for classifiers automatically apply to probability functions as well. f(; O) denotes neural network parameterized by 9 e θ Here O can include hyper- pappe-parameters, thus the architectures of f(; 0)'s do not have to be identical.
Certified robustness We call x 6 an adversarial example of a classifier f. if f correctly classifies but [x + d) # fzx) Usually [|ōl|2 is small enough so + 8 and x appear almost identical for the human eye. The (lz-)robust radius of ʃ defined as
r(z, 15 f)
inf ||0||.
(1)
F(x+5)
which is the radius of the largest lz ball centered at x within which ff consistently predicts the true label y of x. Note that r(z; ys /) 0 if [xx) jf y. As mentioned before, we can extend the above definitions to the case when f is a probability function by considering the induced classifier f". A certified robustness method tries to find some lower bound re(ar, y; f) of r (2, y: f), and we call re certified radius of f.
Randomized smoothing Let f be probability function or classifier. The (randomized) smoothed function of f is defined as
g(x) 1o 6)].
The (randomized) smoothed classifier of f is then defined as g". Cohen et al. (2019) first provide a tight robustness guarantee for classifier based smoothed classifiers, which is summerized in the following theorem:
Theorem 1.
(Cohen el al. (2019) For any classifier S. denote its smoothed function by g. Then
r r(z, y: g)
| (gy(x) - Φ (m-ammaxamxfb
(3)
k7g
Later on, Salman al. (2019)): Zhai et al. (2020) extends Theorem | for probability functions.
4 SWEEN: SMOOTHED WEIGHTED ENSEMBLING
In this section, we describe the SWEEN framework we use. We also present some theoretical results for SWEEN models. The proofs of the results in this section can be found in Appendix A
3

---

Under review as a conference paper at ICLR 2021
4.1 SWEEN: OVERVIEW
To be specific, we adopt a data-dependent weighted average of neural networks to serve as the base model for smoothing. Suppose we have some pre-trained neural networks ((;00),,- [(;; (<)0x) as ensemble candidates. A weighted ensemble model is then
K
fens(:;,,w)
Σ (off(:0)).
(4)
where 0 (0)..... E ØK and wo E A is the ensemble weight. For a specific fens, the corresponding SWEEN model defined as the smoothed function of fens. denoted by Jens- We have
K
Jens (2; w) E.g wx + 6;0x)]
wgBss(< 0;0k) E weg(w; 0k),
(5)
where g(: 0) is the smoothed function of f(:;0) This result means that Jens is the weighted sum of the smoothed functions of the candidate models under the same weight w, or more briefly, randomized smoothing and weighted ensembling
commutative. Thus, ensembling under the randomized smoothing framework can provides benefits in improving the accuracy and robustness.
To find the optimal SWEEN model, obtain the value of appropriate weights. These data-dependent weights can make the ensemble model robust the presence of some biased candidate models, they will be assigned with small weights.
minimize a surrogate loss of gene
the training set to
4.2 CERTIFIED ROBUSTNESS OF SWEEN MODELS
For smoothed function the certified radius at (a, v) provided by Theorem D is re( g) = clip( g { (x))
(mmaxx/y I (x)))); D). We now formally define 7-robustness index as criterion of certified robustness.
Definition 1. (y-robustness index). For r R R' and a smoothed functioon g. the r-bouustssss index of g is defined
(g) = E (r 9:9))
(6)
be easily observed that 7-robustness index is an extension of many frequently-used criteria of certified robustness of smoothed classifiers.
= T( d Then, 7 -nrrouustsess index the certified accuracy radius R (Cohen al. 2019); ; rigbrouust index is the average certified
Proposition
Let (r) 1rr 2 R}, (2(r)=
radius (Zhai et al. 2020); "/s "ly-robustmess index is the average volume of the certified region.
We note that criteria considering the volume of the certified region more comprehensive than those only considering the certified radii in sense, as they take the input dimension into account.
Now consider F (f( Fd + A }}. the set neural networks parametrized over θ. The corresponding of smoothed funetions is [o(x;; 0) (o.= + 5; 0)] E θ). Suppose 01.-. ... AK are drawn i..dd from a fixed probability distribution p on @. The set SWEEN models then
K
((x))
Σ
wag(2; ; 0x) wk
0,
=
A=1
Similar to Rahimi & Recht (2008). we consider mixtures of the form Φ(x) = - w(0)g(x; 0)00 For
a mixture d we define 10 supo
wo()) P(P)
Define
8, 8 = (())g(<; do 1 < co, w0) 2 0, w/ w( -1
(8)
Note that for any & E Fp. o a smoothed probability function. Intuitively, p is quite a rich set. The following result shows that with high probability, the best n-robustness index SWEEN model can obtain is near the optimal n-robustness index the class F,,- Thus, the ensembling generality also holds for the y-robusttnsss index defined for robustness.
4

---

Under review as a conference paper at ICLR 2021
Lemma 1. Suppose y is Lipschitz, Given dj O. For any E O. for sufficently large K, with probability least 1 1) over 01, ......0 0g drawn i.i.d. from p. there exists & E Fo which satisfies
[Ø) sup (6) &
Moreover, if there exists Φo E Fp such that (0o) sup sup (0), K= (
In practice, the defined robustness index I-(-) may be hard to optimized directly, in which case we choose a surrogate loss function / R x y + to approximate it. Now the optimization for the ensemble weight w of SWEEN model over training set {(4,, y: y:) can be formulated as
min Σ
wxg(r;; 0.).
(10)
However, this process typically invovles Monte Carlo simulation since we only have access to I(; 02), 1,... K. We define the risk and empirical risk w.r.t. the surrogate loss
Definition 2. (Risk and empirical risk). For a surrogate loss function l :R x y - R, the risk of probability function & are defined as
R|ø D(c.))-
(11)
If TÓ(x)= = k== - wag(2; 02) E So. for training set (1)) and sample size 8, the empirical
risk of & is defined
Remp [0]
wk Σ fa; + digki 0x),,
(12)
71
where 8igk 1id
Now solving for w reduced to finding the minimizer of Remp- When the loss function is convex, this problem is -ww-dimensional convex optimization, minimizer using traditional convex optimization algorithms. Furthermore, we have:
obtain the global empirical risk
Theorem 2. Suppose for all y e y. U(. y) is a functionn with constant L and is uniformly bounded. Given 1) > 0. For any > O, for sufficently large K, if 2 K2
S2( log Kn
g² ), then
with probability least 1 1) over the training dataset {(x;, }=) drawn i.i.d. from D and the parameters 0,...., 0g drawn i.i.d. from and the noise samples drawn i.idd from (O0 I21), the
empirical risk minimizer é over F9 satisfies
R(0)
inf R(Ø) <. E
(13)
Moreover: if there exists Φu E Fp such that R[øu] inf inf R(Ø), K 2(
Theorem 2 gives guarantee that, for large enough K, n, the gap between the risk of the empirical risk minimizer& à and inf P, R[ø] can be arbitrarily small with high probability. Note that we can solve e to any given precision when / is convex. Moreover, Theorem reveals the accessibility of ó in Lemma when approximates the 7-robustness index well. While the number of candidate models and the number of training samples need to large to ensure good theoretical properties, we will show that the performance of SWEEN models of practical settings is good enough in Section
4.3 ADAPTIVE PREDICTION ALGORITHM
major drawback of ensembling is the high execution cost during inference, which consists of prediction and certification costs for smoothed classifiers. The evaluation of smoothed classifiers relies on Monte Carlo simulation, which is computationally expensive. For instance, CCohen et al. (2019) use 100 Monte Carlo samples for prediction and 100,000 samples for certification. If 100 candidate models to construct SWEEN model, the certification a single data point will require 0,000 local evaluations (10,000 for prediction and 10,000,000 for certification). Inoue (019)
5

---

Under review as a conference paper at ICLR 2021
observes that ensembling does not make improvements for inputs predicted with high probabilities even when they are mispredicted. He proposes an adaptive ensemble prediction algorithm to reduce the execution cost of unweighted ensemble models. We modify the algorithm to make it applicative to weighted ensemble models, which is detailed in Appendix [ For a data point, classifiers are evaluated in descending order with respect their weights. Whenever early-exit condition is satisfied, we stop the evaluation and return the current prediction.
5
EXPERIMENTS
In this section, we design extensive experiments on CIFAR-10, SVHN and ImageNet to evaluate the performance of SWEEN models.
5.1 SETUP
Model setup We train different network architectures on CIFAR-I0 and SVHN to serve as candidates for ensembling, including LeNet (LeCun et al. 1989), AlexNet (Krizhvsky et al. 2017 ResNet-20 (He et al. 2016). ResNet-26, 32, ResNet- 10, DenseNet (Huang et al. 2017)
(depth=100), VGG-16 16 (Simonyan & Zisserman 2015). and VGG-19. We particularly evaluate two compositions of SWEEN models. The first is a relatively rich set of models, including LeNet, AlexNet, Re,,et-20, ResNet- 10, DenseNet, VGG-16, VGG-19, denoted by the SWEEN-7 model. The second is small set of small models, including ResNet-20, ResNet-26, ResNet-32. denoted by the SWEEN-3 model. The SWEEN-7 model and the SWEEN-3 model simulate how much SWEEN can help in scenarios when have adequate and limited numbers of candidate models, respectively. On ImageNet, we train three candidate models including ResNet-18, ResNet-34 and ResNet-50. We evaluate the SWEEN model containing the three models, denoted by the SWEEN-IN model. A SWEEN model and its candidate models are trained and evaluated with the same noise level a.. The detailed algorithm for obtaining a SWEEN model is presented in Appendix B.2
Candidate model Training We train candidate models using two training schemes, including Gaussian data augmentation training (Cohen et 2019),, which denoted as the standard training for simplicity, and MACER training (Zhai et al. 2020). All hyper-parameters used in our experiments are listed in Appendix C.I.
Solving the ensembling weight From Section 4 we know that we can obtain the empirical risk minimizer by solving a convex optimization. However, this requires first to approximate the value of smoothed functions of candidate models at every data point, which can be very costly when the number of candidates or training data samples large. Hence, we use Gaussian data augmented freeze the parameters of candidate
training to solve the ensembling weight. More precisely. models and minimize the cross-entropy loss of the SWEEN model on Gaussian augmented data from the evaluation set. Empirically we find that this approach is much faster and yields comparable results.
Certification Following previous works, report the approximated certified accuracy (ACA), which is the fraction of the test set that can be certified to be robust at radius r approximately (see Cohen et al. (2019) for more details). We also report the average certified radius (ACR) following Zhai et al. (020). The ACR equals to the area under the radius-accuracy curve (see Figure T.. All results were certified using algorithms in Cohen et al. (2119) with N 100, 000 samples and failure
probability = 0.001.
5.2 RESULTS
Standard training on CIFAR-10 Table displays the performance of two kinds of SWEEN models under noise levels E {0.25, 0.50, 1.00J. The performance of single ResNet-110 is included for comparison, and we also report the upper envelopes of the ACA and ACR of their corresponding candidate models as UE. In Figure we display the radius-accuracy curves for the SWEEN models and all their corresponding candidate models under o = 0.50 on CIFAR-10. 10. We also include full-size figures in Appendix
The results show that SWEEN models significantly boost the performance compared to their corre- sponding candidate models. According to Figure the SWEEN-7 model consistently outperforms

---

Under review as a conference paper at ICLR 2021
Table 1: ACA (%) and ACR 11FAR-10.
All models trained via the standard training. UE stands for the upper envelope, which shows the largest ACA and ACR among the candidate models.
Model
0.00
0.25
0.5
0.75
1.00
1.25
1.50
1.75
2.00
ACR
ResNet-110 110
79.6
65.2
50.8
34.4
0
0
0
0
0
0.489
UESWEEN-3
80.5
65.6
47.9
30.2
0
0
0
0.470
0.25
SWEEN-3
82.3
69.8
54.7
35.9
0
0
0
0
0
0.520
UFSWEEN-7
80.5
67.9
52.2
36.1
0
0
0
0
0
0.506
SWEEN-7
84.2
72.0
58.7
43.0
0
0
0
0
0.560 0
ResNet-
68.7
58.6
46.7
35.4
25.0
17.0
9.0
4.6
0
0.573
UESWEEN-3
69.6
58.3
45.8
33.7
23.0
15.8
9.2
4.7
0
0.556
0.50
SWEEN-3
70.9
61.4
50.8
38.3
27.7
20.1
12.8
6.7
0
0.630
UFSWEEN-7
68.6
58.9
46.6
34.8
24.7
16.5
10.2
5.3
0
0.574
SWEEN-7
71.2
63.0
52.2
41.9
31.2
22.9
15.3
8.3
0.678
ResNet- 10
51.4
44.9
37.9
31.8
24.6
18.8
13.8
10.2
6.7
0.559
UESWEEN
50.6
44.7
38.2
30.8
24.6
18.5
13.6
10.5
7.0
0.555
1.00
SWEEN-3
51.9
45.5
39.3
32.3
25.9
19.7
15.4
11.4
8.1
0.595
UESWEEN-7
52.0
45.7
37.9
31.9
25.1
19.2
13.9
10.1
7.2
0.557
SWEEN-7
52.7
46.3
39.8
34.0
27.6
22.7
17.9
12.6
9.2
0.631
Lakid
BaeNeDD HesWeeDd
BeeNer110
Annfel
SWELE-
Rashet22
Reahettz SWEEN-
SWEEN-3
Rochet110
Cantfeed iccaaay
0.5
Densekot
64
0.0
0.35 1.00
0.0
025
1.00
2.30
0000
0.5
4.30
Rodis
Radiee
Racius
Figure 1: Radius-aceuracy curves under o = 0.50. All models are trained via standard training. (Left) The SWEEN-7 model and all its candidate models. (Middle) The SWEEN-3 model and all its candidate models. (Right) The SWEEN-7 model, the SWEEN-3 model and the ResNet-110.
all its candidates in terms of the ACA at all radii. The ACR of the SWEEN-7 model is 0.678, much higher than that of the upper envelope of the candidates, which is 0.574. confirms our theoretical analysis in Section 4 that SWEEN performance. Besides, SWEEN is effective when only limited numbers of small candidate models available. The SWEEN-3 model using ResNet-20. ResNet-26, and desNet-32 achieves higher ACA than the R 10 at all radii on all noise levels. The total training time and the number of parameters of the SWEEN-3 model The improvements can be further amplified by increasing the number and size of candidate models. As an instance, the ACR of the SWEEN-7 model least 1 13% higher than that of the ResNet- in Table The above results verify the effectiveness of SW SWEEN for randomized smoothing.
combine the strength of candidate models and attain superior
36 % and 30% less than those of ResNet- 10, respectively.
Table 2: Training time, #parameters and #FLOPs for models under a = 0.50 via MACER training. All the experiments run on a single NVIDIA 1080 Ti GPU.
Model
sec/epoch
#epochs
Total hrs
#parameters
#FLOPs
ResNet- 10
404.2
440
49.4
1.73M
255.27M
ResNet-20
72.2
440
8.8
0.27M
41.21M
ResNet-26
92.9
440
11.3
0.36M
55.48M
ResNet-32
113.2
440
13.8
0.46M
69,75M
Weight Ensemble
0.6
150
0.025
33.9
1.10M
166.44M

---

Under review as a conference paper at ICLR 2021
Table 3: ACA (%) and ACR CIFAR-10. All models are trained via MACER training. UE stands for the upper envelope candidate models.
Model
0.00
0.25
0.5
0.75
1.00
1.25
1.50
1.75
2
ACR
ResNet-110
81
71
59
43
0
0
0
0
0
0.556
0.25
UESWEEN-3
77.4
66.9
56.8
41.9
0
0
0
0.529
SWEEN-3
77.7
68.7
60.3
46.6
0
0
0
0
0.558 0
ResNet-110
66
60
53
46
38
29
19
12
0
0.726
0.50
UEswEEN-3
64.9
57.1
49.7
41.1
34.1
26.2
20.2
11.7
0
0,685
SWEEN-3
64.7
58.4
51.8
43.9
37.2
29.2
22.8
14.6
0
0.727
ResNet-110
45
38
32
25
18
0.792
1.00
UESWERN-3
39.4
38.2
35.8
33.4
30.3
27.6
24.5
22.0
19.0
0.793
SWEEN-3
39.5
37.9
35.8
33.2
30.4
27.5
24.6
22.0
19.1
0.796
MACER training on CIFAR-10 Since SWEEN is compatible with previous training algorithms, we adopt MACER training for the SWEEN-3 model. The results are summarized in Table For ACA and ACR of the ResNet- model,
the original numbers from Zhai et al. (2020).
In the results, the SWEEN-3 model achieves comparable results to the ResNet- 10 but more efficient. From Table 2 and the SWEEN-3 model takes 33.9 hours achieve 0.727 in terms of the ACR for o 0.5, using three small and easy-to-train candidates models. Meanwhile, takes 49.4 hours for the ResNet- 10 to achieve similar performance CIFAR-10 10. This 32% speed up reveals the efficiency of applying SWEEN to previous training methods.
Standard training ImageNet Table displays the performance of ResNet-50 and SWEEN-IN under the noise levels a E (0.25, 0.50, 1.00]. We note that the performance of ResNet-50 is also the upper envelope of the three models in SWEEN-IN. We can see that the SWEEN-IN model significantly outperforms its corresponding candidate models, similar to the results on CIFAR-10 The results again confirm the effectiveness our proposed SWEEN framework.
Table 4: ACA (%) and ACR on ImageNet. All models are trained via standard training.
Model
0.00
0.25
0.5
0.75
1.00
1.25
1.50
1.75
2
ACR
ResNet-50
66.8
58.2
49.0
38.2
0
0
0
0
0
0.469
0.25
SWEEN-IN
67.8
60.2
51.6
41.6
0
0
0
0
0
0.489
Re
56.4
52.4
46.4
42.2
37.8
32.6
28.0
21.4
0
0.726
0.50
SWEEN-IN
56.4
52.4
49.6
45.0
40.8
37.0
31.6
25.2
0.781
ResNet-50
43.6
40.6
37.8
35.4
32.4
28.8
25.8
22.4
19.4
0.863
1.00
SWEEN-IN
44.6
42.0
38.6
36.4
35.0
32.6
29.4
25.6
22.4
0.948
Other experimental results Due to space constraints, we only report the main results here. The results further experiments (e.g., the results on SVHN, the results the adaptive prediction algorithm, the results of the SWEEN model with identical architectures, and the results of SWEEN versus real attacks) can be found Appendix
CONCLUSIONS
In this work, we introduced the smoothed weighted ensembling (SWEEN) improve randomized smoothed classifiers in terms of both accuracy and robustness. We showed that SWEEN can achieve optimal certified robustness w.r.t. our defined 7-robustness index. Furthermore, we can obtain the optimal SWEEN model w.r.t. surrogate loss from training under mild assumptions. We also developed an adaptive prediction algorithm to accelerate the prediction and certification process. Our extensive experiments showed that properly designed SWEEN model was able to outperform all its candidate models by a significant margin consistently. Moreover, SWEEN models using few small and casy-to-train candidates could match exceed a large individual model on performance with notable reduction total training time. Our thcoretical and empirical results confirmed that SWEEN viable tool for improving the performance of randomized smoothing models.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give false sense of security: Circumventing defenses adversarial examples. In ICML 2018: Thirty-fifth International Conference on Machine Learning, pp. 274 283, 2018.
Peter Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. The Journal of Machine Learning Research, 3:224-240 240, 06 2001. doi: 10.1007/
3-540-44581-1_15.
Battista Biggio, Igino Corona, Davide Maiorca, Blaine Nelson, Nedim Smdiić, Pavel Laskov, Giorgio Giacinto, and Fabio Roli. Evasion attacks against machine learning at test time. european conference on machine learning, 81 8190:387-402, 2013.
Avrim Blum, Travis Dick, Naren Manoj, and Hongyang Zhang. Random smoothing might be unable to certify 2o robustness for high-dimensional images. arXiv preprint N0Kiv:2002.03517. 2020.
Xiaoyu Cao and Neil Zhenqiang Gong. Mitigating evasion attacks to deep neural networks via region-bascd classification. In Proceedings of the 33rd Annual Computer Security Applications Conference on, pp. 278-287, 2017.
Nicholas Carlini and David Wagner. Adversarial examples not easily detected: Bypassing ten detection methods. In Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security, pp. 3-,4, 2017.
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. In ICML. 2019: Thirty-sixth International Conference on Machine Learning, pp. 1310-1320, 2019.
Francesco Croce and Matthias Hein. Reliable evaluation of adversarial robustmess with an ensemble of diverse parameter-free free attacks. In ICML, 2020.
Francesco Croce, Maksym Andriushchenko, and Matthias Hein. Provable robustness of relu networks via maximization of linear regions. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 2057-2066, 2019.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hier- archical image database. 2009 IEEE Conference on Computer Vision and Puttern Recognition, pp. 248-248-255 1148-255,20 2009.
Krishnamurthy Dvijotham, Sven Gowal, Robert Stanforth, Relja Arandjelovic, Brendan O'Donoguue, Jonathan Uesato, and Pushmeet Kohli. Training verified learners with learned verifiers. arXiv preprint arXiv: 1805. 10265, 2018a.
Krishnamurthy Dvijotham, Robert Stanforth, Sven Gowal, Timothy Mann, and Pushmeet Kohli. A dual approach to scalable verification of deep networks. In UA/ 2018: The Conference on Uncertainty in Artificial Intelligence (UAI), pp. 550-559, 2018b.
Rüdiger Ehlers. Formal verification of piece-wise linear feed-forward neural networks. In In- ternational Symposium on Automated Technology for Verification and Analysis, pp. 269-286. 2017.
Matteo Fischetti and Jason Jo. Deep neural networks as 0-1 mixed integer linear programs: A feasibility study. arXiv preprint arXiv: 1712.06777 2017.
Timon Gehr, Matthew Mirman, Dana Drachsler- Cohen, Petar Tsankov, Swarat Chaudhuri, and Martin Vechev. Ai2: Safety and robustness certification of neural networks with abstract interpretation. In 2018 IEEE Symposium on Security and Privacy (SP), pp. 3-18. 2018.
Sven Gowal, Krishnamurthy Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Uesato, Relja Arandjelovic, Timothy A. Mann, and Pushmeet Kohli. On the effectiveness of interval bound propagation for training verifiably robust models. arXiv preprint arXiv:1810.12715. 2018.

---

Under review as a conference paper at ICLR 2021
L.K. Hansen and P. Salamon. Neural network ensembles. IEEE Transactions Pattern Analysis and Machine Intelligence, 12(10))993-1001, 1990.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 770-778, 2016.
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), pp. 2261-2269, 2017.
Hiroshi Inoue. Adaptive ensemble prediction for deep neural networks based on confidence level. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 1284-1293, 2019.
Guy Katz, Clark W. Barrett, David L. Dill, Kyle Julian, and Mykel J. Kochenderfer. Reluplex: An efficient smt solver for verifying deep neural networks. In International Conference on Computer Aided Verification, pp. 97-117, 2017.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E. Hinton. Imagenet classification with deep convolu- tional neural networks. Communications of The ACM, 60(6):84 90, 2017.
Anders Krogh and Jesper Vedelsby. Neural network ensembles, cross validation, and active learning. In Advances Neural Information Processing Systems pp. 231 1994.
Aounon Kumar, Alexander Levine, Tom Goldstein, and Soheil Feizi. Curse of dimensionality on randomized smoothing for certifiable robustness. arXiv preprint 2Xiv:20002.03239, 2020.
Alexey Kurakin, Ian J. Goodfellow, and Samy Bengio. Adversarial machine learning at scale. In ICLR 2017: International Conference on Learning Representations 2017, 2017.
Y. LeCun, B. Boser, S. Denker, D. Henderson, R. E. Howard, W. Hubbard, and L.. D. Jackel. Backpropagation applied to handwritten zip code recognition. Neural Computation, 1(4):541-551, 1989.
Mathias Lecuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified robustness to adversarial examples with differential privacy. In 2019 IEEE Symposium Security and Privacy (SP), pp. 656-672, 2019.
Guang-He Lee, Yang Yuan, Shiyu Chang, and Tommi S. Jaakkola. Tight certificates of adversarial robustness for randomly smoothed classifiers. Advances in Neural Information Processing Systems, pp. 491 4911-4922, 2019.
Bai Li, Changyou Chen, Wenlin Wang, and Lawrence Carin. Second-order adversarial attack and certifiable robustness. 2018.
Xuanqing Liu, Minhao Cheng, Huan Zhang, and Cho-Jui Hsieh. Towards robust neural networks via random self-ensemble. In Proceedings of the European Conference on Computer Vision (ECCV), pp. 381-397, 2018.
Alessio Lomuscio and Lalit Maganti. An approach to reachability analysis for feed-forward relu neural networks. arXiv preprint arX1v:1706.07351, 2017.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In ICLR 2018: International Conference on Learning Representations 2018, 2018
Ying Meng, Jianhai Su, Jason O' Jane, and Pooyan Jamshidi. Ensembles of many diverse weak defenses be strong: Defending deep neural networks against adversarial attacks. arXiv preprint arXiv:2001.00308 2020.
Matthew Mirman, Timon Gehr, and Martin Vechev. Differentiable abstract interpretation for provably robust neural networks. In JCML 2018: Thirty-fifth International Conference on Machine Learning, pp. 3578-3586, 2018.
10

---

Under review as a conference paper at ICLR 2021
Tianyu Pang, Kun Xu, Chao Du, Ning Chen, and Jun Zhu. Improving adversarial robustness via promoting ensemble diversity. In ICML 2019: : Thirty-sixth International Conference on Machine Learning, pp. 197004979, 2019.
Aditi Raghunathan, Jacob Steinhardt, and Percy Liang. Certified defenses against adversarial examples. In ICLR 2018: International Conference on Learning Represenlations 2018, 2a.
Aditi Raghunathan, Jacob Steinhardt, and Percy Liang. Semidefinite relaxations for certifying robustness to adversarial examples. In NIPS 2018: The 32nd Annual Conference on Neural Information Processing Systems, pp. 10877-10887, 2018b.
Ali Rahimi and Benjamin Recht. Weighted sums of random kitchen sinks; Replacing minimization with randomization in learning. In Advances in Neural Information Processing Systems 21, pp. 1313 1320, 2008.
Hadi Salman, Jerry Li, Ilya Razenshteyn, Pengchuan Zhang, Huan Zhang, Sebastien Bubeck, and Greg Yang. Provably robust deep learning via adversarially trained smoothed classifiers. NeurlPS 2019 Thirty-third Conference on Neural Information Processing Systems, pp. 1 11292-1133 1303, 2019a.
Hadi Salman, Greg Yang. Huan Zhang, Cho-Jui Hsieh, and Pengchuan Zhang. A convex relax- ation barrier to tight robustness verification of neural networks. In NeurlPS 2019: Thirty-third Conference on Neural Information Processing Systems, pp. 9832-9842, 2019b.
Sanchari Sen, Balaraman Ravindran, and Anand Raghunathan, Empir: Ensembles of mixed precision deep networks for increased robustness against adversarial attacks. In ICLR 2020 Eighth International Conference Learning Representations, 2020.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. In ICLR 2015 International Conference on Learning Representations 2015, 2015.
Gagandeep Singh, Timon Gehr, Matthew Mirman, Markus Püschel, and Martin Vechev. Fast and effective robustness certification. In NIPS 2018: The 32nd Annual Conference on Neural Information Processing Systems, pp. 10802-10813, 2018.
Thilo Strauss, Markus Hanselmann, Andrej Junginger, and Holger Ulmer. Ensemble methods as defense to adversarial perturbations against deep neural networks. arXiv preprint arXiv:1709.0342: 2018.
Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In ICLR 2014 International Conference on Learning Representations (ICLR) 2014, 2014.
Jiaye Teng, Guang-He Lee, and Yang Yuan. & adversarial robustness certificates: randomized smoothing approach. 2019.
Vincent Tjeng, Kai Xiao, and Russ Tedrake. Evaluating robustness of neural networks with mixed integer programming. In ICLR 2019 7th International Conference on Learning Representations, 2019.
Florian Tramer, Nicholas Carlini, Wieland Brendel, and Aleksander Madry. On adaptive attacks to adversarial example defenses. arXiv preprint arXiv:2002.08334. 2020.
Jonathan Uesato, Brendan O' D'Donoghue, Pushmeet Kohli, and Aäron van den Oord, Adversarial risk and the dangers of evaluating against weak attacks. ICML 2018: Thirty-fifth International Conference Machine Learning, pp. 5025-5034, 2018.
Bao Wang, Zuoqiang Shi. and Stanley Osher. Resnets ensemble via the feynman -ac formalism to improve natural and robust accuracies. In NeurIPS 2019 Thirty-third Conference on Neural Information Processing Systems, pp. 1657-1667, 2019.
Shiqi Wang. Yizheng Chen, Ahmed Abdou, and Suman Jana. Mixtrain: Scalable training formally robust neural networks. arXiv preprint 1811:/81 2018a.

---

Under review as a conference paper at ICLR 2021
Shiqi Wang, Kexin Pei, Justin Whitehouse, Junfeng Yang, and Suman Jana. Efficient formal safety analysis of neural networks. In NIPS 2018: The 32nd Annual Conference on Neural Information Processing Systems, pp. 6367-6377, 2018b.
Tsui-We Wei Weng, Huan Zhang, Hongge Chen, Zhao Song, Cho-Jui Hsieh, Luca Daniel, Duane Boning, and Inderjit Dhillon. Towards fast computation of certified robustness for relu networks. In ICML 2018: Thirty-fifth International Conference Machine Learning, pp.
2018.
Eric Wong and Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In (CML2018, Thirty-fift International Conference on Machine Learning, pp. 51-55283-555 52922, 2018.
Eric Wong, Frank Schmidt, Jan Hendrik Metzen, and J. Zico Kolter. Scaling provable adversarial defenses. In NIPS 2018: The 32nd Annual Conference on Neural Information Processing Systems, pp. 8400-8409, 2018.
Greg Yang, Tony Duan, Edward Hu, Hadi Salman, Ilya P. Razenshteyn, and Jerry Li. Randomized smoothing all shapes and sizes. arXiv preprint arXiv:2002.08/ 18, 2020.
Runtian Zhai, Chen Dan, Di He, Huan Zhang, Boqing Gong, Pradeep Ravikumar, Cho-Jui Hsieh, and Liwei Wang. Macer: Attack-free and scalable robust training via maximizing certified radius. In ICLR 2020 Eighth International Conference on Learning Representations, 2020.
Dinghuai Zhang, Mao Ye, Chengyue Gong, Zhanxing Zhu, and Qiang Liu. Black-box certifica- tion with randomized smoothing: A functional optimization based framework. arXiv preprint 20Xiv:2002.09 169,, 2020.
Huan Zhang, T'ui-Wei Weng, Pin-Y Yu Chen, Cho-Jui Hsieh, and Luca Daniel. Efficient neural network robustness certification with general activation functions. In NIPS 2018: The 32nd Annual Conference on Neural Information Processing Systems, pp. 4939-4948, 2018.
A PROOFS
A. PROOF OF LEMMA
Define
F ((xx) = 1/ w(0)g(z;;))l |1o1|> < oo, oo, w(0)
(14)
k
wag(=; 0n) 02) 2 20} )
81 = 6(0) = Σ
(15)
We have Fp F 9.950 C &/.
Fo
Lemma 2. Let μ be any probability measure on Rdd, For o RRd + RM define the norm || A See (1 (dd(a)) Fix & E Fy. then for any 17 >> 0, with probability at least 1 over OI...., OK
drawn i.i.d. frum p, there exists H(x) = Σ cag(a; 0x) E Sy which satisfies
llll
-
2l1 S VK
(1 + v log ,
(16)
Proof. Sine E F,, we can write d(x) So w(O)g(z; 0)d0, where w(0) 2 0. Con- w(6x)
struct db = B.g(: 0k),k = 1,2,... K, where Bx = p then Ede.e = Φb || =
View (2119(2; 0+) (x))ddu(())) < 18x| S || We then define
K
u(O2.... ,0k = K
Σ Ox - E11a-
(17)
12

---

Under review as a conference paper at ICLR 2021
First, by using Jensen's inequality and the fact that
| I 1løllp- we have
1
Elu(O)] S [[u2(00] Bll
Σ th
11E -
VK
Next, for 01, ... Ar and 0, we have
(u(01.
BM) -u(0,, ... 8 , ,81))
K
K
Øk
Φ1 - K
ΦR + Φ55) -
K
R=1
1=1,
Φk
Σ
Φk 71)11
k=1,
|
Talla
K
2 2|1lpp
K
Now we can use McDiarmid's inequality to bound u(O), which gives
|
K=²
(l)
2 E) < P(u(0) - Eu( 2 s| < exp(
(18)
VK
21?
The theorem follows by setting 8 to the right hand side and solving
Lemma 3. Let y be any probability measure on Rd. For Φ Rdd - RR,, define the norm |
fau (1((x) [[du(z), then for any 1) for K 2 M [|]1] +
2 log 1, 2) with probability at least
k
1 - over o.,... 0x drawn i.i.d. from p. there exists δ(x) = Σ
Crg(:; 02) E So which satisfies
2 log - )
| - &1l < 2 |0l
K (1 +
(19)
Proof. Fix O E F, Sy by using Lemma 2
we have that for any > with probability least
K
1 1- 17 over 0I,..., Ox drawn i..dd. from p, there exists Ō(x) = Σ
cag(2; 0x) Sg which satisfies
k=
|@lle VK
(1 + v 22 log _ & B(K).
1/ - -olla <
(20)
K Σ
M Σ
Denote C = Ck. and define s(t)
ta as the sum of all elements of t E RM, Then
k=1
s(g(2; 0)) Vx Vx Rd A E O Thus,
M s(o(z)) Σ (x)x)= Σ
/ w(8) Σ g: 0) / w())d
(x;)g(x;0))
M
M K
K
M
k
s(ō(x)) = Σ )i(x) = Σ Σ
Ckga 0x) = Σ
Ck
(x; 0x)
9i (x;
Σ c = C.
1=1
k=
km
k=
13

---

Under review as a conference paper at ICLR 2021
Now have
| 1Ø(x) - o(x))
B(K)² > 11 -01
Rd
(s(0(x) - x(x)))² du(x)
2
M
(C 1)² du(xx)
M
(C 1)²
M
which gives VMB(K) < <0< (B Construct x(x) Ó(x) -
then ò E Sy and
J ld(x)) (d)))()((x))
l| - +13
J(c |I0 |IC))(()) o(x) (z))(())(()
J [(((()) -xx))=())))))))))>)>)))) + (C 11)(s))
[ - o(x)) ||C - 1)0(z) -10
1)(((2) o(x), x(z)) ((((=))))dd ddu(z)
[ (10(1) - <()]l
2 H()))
Sine we have C S 11 S C2, [K(()) 1102011300000 - C, it holds that
(i) When 1 < <
|| 611 $ f (10(z)- - -(x))1 + C-
+ 2((C 1))dp(x)
M
< B(K) + C-
+ +2(C 1)
M
S 2B(K) +2VMB(K);
VM
ii) When 1 - VMB(K) <0S1.
[ (10(()) - -0x)1 + -1- + 2(1 ())d((x)
11 111 5
5 W1
B(K)² +4 (1+C)²
AVMB(K) (M- - B()
AVMB(K).
Thus, with probability at least 17 over 0I...., 0x drawn i.i.d. from p.
M |1 Φ1l <2 VMB(K) 2 1l0 V
(1+ K
V 2
Lemma 4. Suppose .(:,)) is L-Lipschitz in its first argument. Fix Φ E Fy,, then for any nj > for K 2 M1 + 2 1),, with probability at least 1 over 01,..., Og drawn i.i.d. from there exists å So which satisfies
M (1 + 2log ) E (( v)] - E(aw (ába), v)]l < 22 110lp V K
1
14

---

Under review as a conference paper at ICLR 2021
Proof.
[B((((()) v]] B[(((()), v)ll
x Elc(o(x), v) c(0(x), ()) 3)1
LE) x(x)) l2
- L Bllo(z) - x(x)
L 2bDD)=
The desired result follows from Lemma 3
Lemma 5. (Corollary of Proposition 1 in Zhai al. (2020) Given any P1.P2."" P2.... PM satisfies p1 2
P2 2 ... -2 PM 2 and p1 P = with respect to pı and p2 bounded.
The derivative of clip( (p-1(pr)) (pz)- (p2)); D)
Now can prove Lemma
Proof of Lemma Let Φo E Pp such that (0o) > Su [,()) 2- From Lemma we know (max* Pt) 0, D) Lipschitz in its first argument. Since m is Lipschitz, c(p, v) m(((p, v)) is also Lipschitz in its first argument with some constant L.
that q(p. y) & clip( ] Φ (py))
Apply Lemma we have that for K 2 M [ + / v1+ 2 log }),², with probability at least 1 01, -.., 0K drawn ii.dd from p. there exists & f which satisfies
(000) (3)
(( (1 (()(())))) (x)) v)) - -E ((E))
2 1ooll V K (1+ v 2log _
256L 3361"1000|32a011+ / Isa
When K
we have
sup [o) Iz((0) = (sup (Ø) - ( + - E + =E
$E
$
2
If [ 3 (o), which means [oollp is independent of K = (
A.2 PROOF OF THEOREM 2
First we introduce some results from statistical learning theory.
Definition 3. (Gaussian complexity). Let μ be probability distribution set X and suppose that Ii, In are independent samples selected according to μ. Let F be a class of functions mapping from X to R. The Gaussian complexity of F is
2 "
G. E sup fE3
Σ
(f(x)))) Dni Ei. Enl
where E1,..., are independent (0, random variables.
Definition 4. (Rademacher complexity) Let p. be probability distribution set X and suppose that 21, ..., In are independent samples selected according p. Let F be a class of functions mapping from X to R. The Rademacher complexity of F is
2
R
sup FEF
o=f(xx)l(1)..... Eni di, Tn)
where Oi,..., on are independent uniform valuee random variables.
Lemma 6. (Part of Lemma in Bartlett & Mendelson (001)).. There are absolute constants 3 such that for every class F and every integer n, R2 (3) 3G,
15

---

Under review as a conference paper at ICLR 2021
Lemma 7. (Corollary of Theorem 8 in Bartlett & Mendelson 2001)).
). Consider loss function c: A x Y - [0, 1]. Let F be a class of functions mapping from X to A and let (Iz, Us) 1 be independently selected according the probability measure μ. Then, for any integer and any over samples of length n, every f in I satisfies
0 < 1j < 1, with probability at least
n
8 llgg 2
(( (aa))=(c(((()) (c(f(x)) v) - E u(( + Rn $1+1
where ō & == ((x,)) (f((),)) c(0.v)) E
Lemma 8. (Corollary of Theorem 14 in Bartlett & Mendelson 2001)). Let A R and let F be a class of functions mapping from X to A. Suppose that there are real-valued classes F F M such that F is subset of their Cartesian product. Assume further that e A x Y -> IR is such that, for all y E E, y) is a Lipschitz, function with constant which passes through the origin and is uniformly bounded. Then
M
G. (
Σ (..))..
Now we prove the following lemma:
Lemma 9. Let c, F, (zi, 3:) čo F be as in Lemmaly
7 Then, for any integer n and any 1) 1. with probability at least 1 over samples of length ni, every f in I satisfies
n
8 Slog* 2
Σ cf(x)). s (xx,)= ((c.))/l R2 [0 +1+1 n
n
Proof.
c(f(zz) y:) - (()))=lc(f(()....
<
sup (E,, Eh)
he
sup (Lnt - Eh) + En y) Ec(0,y). y).
hE20.
When an (x4, pair changes, the random variable
sup (E,,h Eh) can change by no more than hE/o
McDiarmid's inequality implies that with probability at least 1 z.
log 2
sup (i Eh) < E sup (E,,h Eh)
hE
hEc0
similar argument, together with the fact that c(0, y) = EEe(0, y). shows that with probability at least 1 - 7)
8 log
Remp [f] < R[f] + E sup (L,,h- Eh) +
It's left to show that E sup (IE,, Eh) I Rr 1o 3). Let (x', vi), .... (a' vnn) be drawn i.i.d.
AEEO from and independent from (c), then
1
E sup (B.,h Rh)
E sup heBo
E
h 71
< EE sup
E,,
ha2 vt)
i=1
= sup
h(w,, 9:)
Σ
h(24 v(0)
heto
1
2E sup
oeh Vo)
KECo n
< R₂ t o F).
16

---

Under review as a conference paper at ICLR 2021
We prove the following result:
Theorem 3. Let = R and let F be a class of functions mapping from X to A. Suppose that there are real-valued classes F1,... F M such that F is a subset of their Cartesian product. Assume further that the loss function A X R is such that, for all y E Y, c(.,y) is Lipschitz.unnction with constant and is uniformiy bounded. Let { 91) be independently selected according to the probability measure p.. Then, for any integer and any 0 n < 1, there is probability of at least 1 - that every f E I has
8 log
df(x)))))) - ((aa)) ((a.))n(((((x)).))) & BL Σ G Gn
3=1
where B is constant.
Proof. From Lemma and we have that with probability at least 7y over samples of length n, every f in I satisfies
8log
((())) (tl.)i/l(((((x)...)))) R. R2 I
follows by applying Lemma 6 and
Lemma 10. Let cl:.)), be as in Theorem 3
Let (I y1) be independently selected according to
the probability measure D. For any integer and any 0) < 17 < 1, there is probability of at least
1 that every f E Fo has
28LMK Vn
8 log
(f(r)).)) B(a,)) y)]l
Proof. Denote
Fo(1) (
K
K
((x)) Σ
wkgs (x; wx) wk 2 0, Σ wk =
1 1 $ M.
k=
17

---

Under review as a conference paper at ICLR 2021
M (i),, where X
We have that fg C
X k=1
stands for a Cartesian product operation. The Gaussian
comlexities of (o))'ss 's can be bounded
G Gn(P0()
Eyyl sup
2 Σ
n
{o((x)]]
(EFFo())
1
i=1
2
= ssup
Whgj (z wx)l
i=1
Espg/sup
Wk
Eags (mn;; wx)
K
72
< Eg
(2
E.gy (21 wxll
71
i=1
K
<
E 12
E
Eıg, (x))
K
= E, 12
Ij (44 w
72
K
(2
k=1
2K
Vn"
The desired result follows by applying Theorem
3 to S. $o1),,,
(((M)) and D.
Next, we give the definition of semi-empirical risk. The term "semi-" implies that it is empirical with respect to the training set but not the smoothing operation.
Definition 5. (Semi-empirical risk). For a surrogate loss function I(,,)) : RM x RM - R and
training set (xx vi) )a the semi-empirical risk of (xx) Σ wag(a; 0k) Po are defined as
K
Wag( 0k), v:)-
(21)
71
1=1
We can use Lemma and 10 to prove the following result:
Theorem 4. Suppose for all y E y, I[., y) is a Lunsciitrfunction with constant L and is uniformly bounded. Fix & E F,, then for any 1) > O, with probability at least over the training dataset (x,, ) drawn i..dd from D and the parameters 01,... 0g drawn i.idd from p. the semi-empirical risk minimizer à over Fo satisfies
43LMK + 4, 2 2og
M K
2 (1 + 22og 2)², n
R(o] R(Ø)
2L
||dllp
where 3 is constant.
18

---

Under review as a conference paper at ICLR 2021
Proof. Let 6 be the minimizer of R over Fg. Combine Lemma 4 and 10
derive that, with
probability at least 1 26 over the training dataset and the choice of the parameters 81. 8x.
R[Ø] R[Øo
(R|0) Re (o]) + (Ree [o] Roe [o)) + (Ree [6 R(ø"1) + (R[ - -R[p]
23LMK - 2 22
23LMK K + 2 2 log 4
+ 21 222 /lll V M (1 v 2 )
+0+
Vn
n
43LMK 4 22log
M K
+ 2L
/l0llp V
(1 + 2 log -
Lemma 11. Let be probability distribution on A. For any O, with probability at least 1 over Fiy.. Fg drawn ii.d. from p., it holds that
xj E [x]l22
S Jo
(1+ 2 2 1
(22)
Proof. Define u(x1," (I)))
1 Ex T; ||,]||2. By using Jensen's inequality, we have
E [(u(x)) & E u (x:)
Bill Σ
E|x[112]
[B|a=11 | = Vs
1=1
Next, for .1. RM and Tys we have
|u(01, ... [.) - u(x11 Tb. ... ,I,)
E[x]112 - 11
1
+ xx) -E[x]122
i=1
1=1,isk
< ||
04 Fx)112
1=1,14
||
Txl12
s
2
Now we can use McDiarmid's inequality to bound u(z), which gives
1 Ts 2 s Plu()) - Eu(x) 2 s] S exp(
852
P(u(())
(23)
The result follows by setting y to the right hand side and solving 8.
Now we are ready to prove Theorem 2
Proof of Theorem Let do E Fp such that R(Øn) < infaes, R(o) + G. By Lemma 11 with probability least
n
1 + log 3Kn
| Σ fa, + (.gni 0x) - 0x)l22
Isisn, (24)
19

---

Under review as a conference paper at ICLR 2021
hold simultaneously. So with probability at least 1 3. for every o Σ wrg(æ; Fo. holds that
|Rempl [0) Rosc (15]]
Wk
Mai 8132; (a);
wag(o; 0k), 9:)]
[(: + dejue 0n) g 0x)]
Wk
Σ
(as + diyk; 0s) - g( 0z)
R=1
/=1
14 2 log
3Kn
<
Wk
V8
1=1 k=1
L + v 2 log 3kn)
"
E1
V
By Lemma 10
with probability at least
3. for every Fo, it holds that
23LMK Vn
8 8log 12 v A 82.
Ris (0) - R(001 S
Let Ø² be the minimizer of R over $.. By Lemma 1] + / /2 log 7) ))²
with probability at least 1 - $. for K 2
M (1 K
3 ) E3. v 2 22
R10"1 Ridol 2 Ilolln
7)
So with probability at least 1 17, it holds that
R( R(Øl (R(a) Rue (Ø)) (Ree Rempl() + (Rempl)) "Remp(o")
inf O
+ (Remp (00) Rec((")) + (R RR(0") (R[0") - R((oo)) + (R(oo] - inf R(ø)) dE
E2 + 0 + E2 E3
28 + 282 + E3 4'
2567 256l*110o1 M(1+
2 }
64(28LMK + Slog 22
641. 2 log 3km )2
When K have
R[0]
inf RS0 <E S
(25)
If R[[o]] inf R(Ø), which means || hp is independent of K = 2
B ALGORITHMS
B. ADAPTIVE PREDICTION ALGORITHM
The entire adaptive prediction algorithm is shown in Algorithm is modified from Inoue (2019) to generalize to weighted ensembles. The exit condition is the weighted version of the confidence-leve based early-exit condition in Inoue (2019). The algorithm accelerates the evaluation of the ensemble function of and the smoothed operation g(z) = Ef (z + 5)] remains the same, so it does not affect the Monte Carlo estimation and certification procedure of smoothed classifiers.
20

---

Under review as a conference paper at ICLR 2021
Algorithm 1 Adaptive prediction for weighted ensembling
1: Input: Ensembling weight w E R** candidate model parameters E O significance level a, threshold T, data point x:
2: Compute
d (1-
3: Set π as the permutation of indices that sorts descending order and 0
4: repeat
5: Set +++
6: Compute the War -th local prediction Ps, f- (P PP,,M) E A
7: Compute Pi. Σj-1 Wr,PT for & = 1, ..
21=1 We; 8: Compute K; f- arg max; Pi,k
until PL.M > T or Ps.k. + v 2i wiz 21j-1 We,
23 Wxy (pr,, ),,,,
9:
i lori= = K
25 Wr
return k; and Pi,K. k 1,2, ... M
B.2 DETAILED SWEEN ALGORITHM
Algorithm 2 SWEEN
1: Input: Training set Pumin. evaluation set Peval, Ensembling weight wo E RR candidate model
parameters 0 -..,
.... 0x} OK
2: Initialize 0 .... 0x w
3: for i 1 K do
4: Train candidate models 0; using Purain.
5: end for
6: Construct SWEEN model Isween (:; = > (x
7: Train w using Peval
8: return w and 01, :..... 0K
C SUPPLEMENTARY MATERIAL FOR EXPERIMENTS
C.I DETAILED SETTINGS AND HYPER-PARAMETER
We perform all experiments on CIFAR-10 10 and SVHN with single GeForce GTX 1080 Ti GPU. For eight V100 GPUs.
the experiments ImageNet,
For training the SWEEN models on CIFAR- 10 and SVHN, we divide the training set into two parts, for training candidate models, and the other for solving weights. We employ 2,000 images for solving weights on CIFAR-10 10 and 3000 images for solving weights on SVHN. For ImageNet, we use train candidate models and 1/1000 of the training
the whole training
solve weights.
For Gaussian data augmentation training, all the models are trained for 400 epochs using SGD on CIFAR-I0 and SVHN. The models on ImageNet are trained for 90 epochs. The learning rate is initialized set as 0.01, and decayed by 0.1 at the 150th/300th epoch.
For MACER training, 16, 3 16.0, y = 8.0, and we use À = 12.0 for a 0.25 and À = 4.0 for a 0.50. We train the models for 440 epochs, the learning rate initialized set as 0.01, and decayed by 0.1 at the 200th/400th epoch.
the same hyper-parameters as Zhai al. (2020), i.e., use k
C.2 RESULTS ON SVHN
To further evaluate method, also experiment on SVHN. The results in Table 5 show that SWEEN models outperform the upper envelopes of their corresponding candidate models as well. Figure plots plots the results CIFAR-10 and SVHN for comparison.
21

---

Under review as a conference paper at ICLR 2021
1.
SMEEM
SWEEN
GHEENOTOOES Uppe Er Er
0.8
Upper Ennkkseg--0255
SW 50
SWEEE amo.33
Upper Er
64
SHEEN
Upper Enollpsg700.00
Upper Enwnspeppso 80
Uppar Er eellppppo)
0.8
SWEBEM
EWNEEN p-
Enwelcpejomt
0.4
0.2
00
35
1.3
1.
2.0
25 0.0
9.
0.
35
1.5
20
20
3.5
08
3.0
0.25
0.30
0.70
0:30
1.20
1.30
1.70
Figure 2: Comparing SWEEN models to the upper envelopes of their corresponding candidate models. All models are trained via the standard training. (Left) The SWEEN-3 model CIFAR-10. (Middle) The SWEEN-7 model on CIFAR-10. (Right) The SWEEN-7 model on SVHN.
Table 5: Certified accuracy (%) and ACR on SVHN. All models are trained via standard training. UE stands for the upper envelope of candidate models.
Model
0.00
0.25
0.5
0.75
1.00
1.25
1.50
1.75
ACR
UESWEEN-7
90.3
74.6
53.4
29.5
0
0
0.517
0.25
SWEEN-7
91.0
76.4
56.8
34.7
0
0
0
0.547
UESWEEN-7
72.7
58.1
42.1
28.4
17.7
11.0
6.5
3.1
0.498
0.50
SWEEN-7
72.8
59.2
43.9
29.4
19.8
11.9
7.3
3.7
0.524
C.3 SWEEN MODELS USING CANDIDATES WITH IDENTICAL ARCHITECTURES
The SWEEN-3 and SWEEN-7 models are using candidate models with diverse architectures. For more comprehensive result, we also experiment with SWEEN models using candidates with identical architectures. For a E {0.25, 0.5, 1.0]. train ResNet-l 10 models using different random seeds on CIFAR-10 via the standard training. We then these models to ensemble SWEEN models.
The results are shown in Table 6 and Figure 3
We can see that SWEEN is still effective in this scenario and significantly boosts the performance compared to candidate models.
We also run experiments on ImageNet using models with identical structure but with different random initialization. We train 3 ResNet-50 ImageNet via the standard training ensemble the SWEEN models. 7 shows the results. The improvement of SWEEN is substantial compared with the AVG and UE results.
10
SWEENEOW
SIEEE
0.8
Cortant
0.8
0.
0.
00
02
2.4
0.5
21
1.0
12
1.4
000
025
0.60
0.75
1.00
1.25
1,00
2.50
08
05
1.0
1.5
20
23
33
33
48
Figure Radius-accuracy curves of SWEEN models and their candidate models. All candidate models are using the 10 architecture and trained via the standard training, (Left) 0.25. (Middle) a 0.50. (Right) 1.00.
22

---

Under review as a conference paper at ICLR 2021
Table 6: ACA (%) and ACR on CIFAR-10. All candidate models are ResNet-1 10s trained via the standard training. UE stands for the upper envelope, which shows the largest ACA and ACR among the candidate models. AVG stands for the average ACA ACR of candidate models.
0
Model
0.00
0.25
0.5
0.75
1.00
1.25
1.50
1.75
2.00
ACR
AVG
79.9
67.2
50.3
33.5
0
0
0
0.491
0.25
UE
80.4
68.3
52.0
34.6
0
0
0
0.496
SWEEN
83.5
73.0
60.4
43.8
0
0
0
0.572 0
AVG
68.4
58.0
46.1
34.5
24.4
16.2
9.7
4.4
0
0.568
0.50
69.7
59.3
47.1
35.7
24.9
17.6
10.8
5.1
0
0.581
SWEEN
71.3
63.3
53.1
44.0
32.6
22.9
15.8
9.2
0
0.691
AVG
51.9
45.0
37.8
30.9
24.7
18.7
13.5
9.9
7.1
0.558
0.50
UE
53.0
46.0
38.6
31.8
25.5
19.3
14.1
10.5
7.7
0.566
SWEEN
54.1
47.3
41.0
34.7
27.6
22.9
16.7
12.2
9.2
0.623
Table 7: ACA (%) and ACR on ImageNet. All candidate models are ResNet-50s trained via the standard training. The SWEEN model here contains 3 ResNet-50s. UE stands for the upper envelope, which shows the largest ACA and ACR among the candidate models. AVG stands for the average ACA or ACR of candidate models.
Model
0.00
0.25
0.5
0.75
1.00
1.25
1.50
1.75
2.00
ACR
AVG
56.8
52.1
46.1
42.3
37.5
32.8
28.1
21.6
0
0.723
0.50
UE
57.2
52.4
46.4
42.4
37.8
33.0
28.2
21.8
0
0.727
SWEEN
60.0
55.2
50.2
46.0
42.6
37.8
33.2
28.4
0
0.816
C.4 ADAPTIVE PREDICTION ENSEMBLING
To alleviate the higher execution cost introduced by SWEEN, we apply the previously mentioned adaptive prediction algorithm speed up the certification. Experiments are conducted the SWEEN-7 models via the standard training on CIFAR- 10 and the results are summarized in Table g It can be observed that the adaptive prediction successfully reduce the number of evaluations. However, the performance the adaptive prediction models only slightly worse than their vanilla counterparts.
Table ACA (%) and ACR on CIFAR-10. 10. All models are trained via the standard training. means the upper envelope of candidate models.
Model
0.00
0.25
0.5
0.75
1.00
1.25
1.50
1.75
ACR
#evals/img
Normal Adaptive
84.2
72.0
58.7
43.0
0
0
0
0
0.560
700,700
0.25
84.3
71.5
57.6
41.2
0
0
0
0.549
283,727
Normal
71.2
63.0
52.2
41.9
31.2
22.9
15.3
8.3
0.678
700,700
0.50
Adaptive
70.9
62.8
52.3
41.6
31.1
22.8
14.5
7.8
0.672
382,426
C.5
THE SCATTER PLOT OF CERTIFIED ACCURACY
This section plots the scatter diagram of the certified accuracy of test data points for SWEEN-7 versus ResNet- 110 Figure Most of the points lie under the line ø, implying that SWEEN-7 performs superior ResNet-T10.
23

---

Under review as a conference paper at ICLR 2021
2,00
1.75
1.50
ResNet-110
1.25
1.00
0.75
0.50
0.25
0.00
6.00
0.25
0.50
1.00
1.25
1.50
1.75
SWEEN-7
Figure 4: The scatter diagram of the certified accuracy of test data points for SWEEN-7 versus
ResNet- 110. 0.50.
C.6 SWEEN VERSUS ADVERSARIAL ATTACKS
We further investigate the performance of SWEEN models versus AutoAttack (Croce & Hein 2020), which is ensemble of four diverse attacks reliably evaluate robustness, Similar to Salman al. (2019a), we used 128 samples to estimate the smoothed classifier. We share the results below in Table It can be seen that SWEEN can improve the empirical robustness as well.
Table Certified accuracy and empirical accuracy versus AutoAttack on CIFAR- 10. All candidate models are trained via the standard training.
Model
0.00
0.25
0.5
0.75
1.00
SWEEN-3 (certified)
70.9
61.4
50.8
38.3
27.7
SWEEN-3 (AA)
75.0
67.0
58.9
48.4
39.9
0.50
ResNet-20 (AA)
72.5
64.7
55.4
46.2
37.0
ResNet-26 (AA)
74.5
65.4
57.3
46.3
35.7
ResNet-32 (AA)
73.8
64.5
55.3
45.0
35.3
C.7 MACER TRAINING ON CIFAR- 10
In this section, we plot the radius accuracy curves for SWEEN models with candidate models trained by MACER on CIFAR-10 in Figure 5
D FIGURES
24

---

Under review as a conference paper at ICLR 2021
ResNel20
ResNe120 ResNet26
ResNet26
0.8
ResNet32 Ensemble
0.8
ResNet32
cortifed accuracy
certified accuracy
Ensemble
0.4
0.00
0.5
0.50
0.75
1.00
1.25
1.50
1.75
2.00
0.00
0.25
0.50
0.75
1.00
1.25
1.50
1.75
2.00
radius
Figure 5: Radius-accuracy curves for SWEEN models with candidate models trained by MACER on
CIFAR-10. 10. (Left) a 0.25. (Right) a = 0.50.
1.0
LeNet
AlexNet
0.8
ResNet20
certified accuracy
ResNet1 10
DenseNet
0.6
VGG16
VGG19
0.4
SWEEN-7
0.2
0.0
0.00
0.25
0.50
0.75
1.00
1.25
1.50
1.75
2.00
radius
Figure 6: Radius-accuracy curves w.r.t. the SWEEN-7 model and all its candidate models under 0.50. All models are trained via standard training.
25

---

Under review as a conference paper at ICLR 2021
1.0
ResNet20 ResNet26
0.8
ResNet32
certified accuracy
SWEEN-3
0.6
0.4
0.2
0.0
0.00
0.25
0.50
0.75
1.00
1.25
1.50
1.75
2.00
radius
Figure 7: Radius- accuracy curves w.r.t the SWEEN-3 model and all its candidate models under 0.50. All models are trained via the standard training.
1.0
SWEEN-3 SWEEN-7
0.8
ResNet1 10
certified accuracy
0.6
0.4
0.2
0.0
0.00
0.25
0.50
0.75
1.00
1.25
1.50
1.75
2.00
radius
Figure 8: Radius-accuracy curves w.r.t. the SWEEN-7 model, the SWEEN-3 model and the ResNet- 110 under a = 0.50. All models are trained via the standard training.
26


Reviews:
[{"review_id": "sDR5hdsZUOG", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper claims that an ensemble of multiple classifiers can achieve better certified robustness than a single model with comparable cost in terms of the total # parameters. It also proposes to optimize the ensemble weights for maximizing the robustness, and an adaptive prediction scheme to reduce extra # inferences from the ensemble computation required for the certification. Experimental results show that their proposed ensemble models (which are smaller than ResNet-110 in total) achieves better ACR than standard training with ResNet-110, and comparable ACR when applied to MACER. \n\nOverall, the paper is clearly written and easy-to-follow. However, I generally feel both the theoretical and empirical results of the paper are somewhat weak to meet the ICLR bar for the current submission:\n- It seems to me that Lemma 1 and Theorem 2 are somewhat straightforward (or incremental) implications of the (well-known) generalization theory (e.g., [1]), and I could not find a significant reason why they should be presented in the main text. The paper could highlight why those results are surprising compared to existing generalization bounds.\n- I think Algorithm 1, on the other hand, should be rather justified more rigorously instead of SWEEN itself: \"could Algorithm 1 really recover the MC estimate?\", or \"is there a theoretical guarantee that this algorithm is more efficient than MC?\", just to name a few. Also, the paper should provide more detailed explanation and rationale on Algorithm 1.\n- The empirical results are not fully convincing to show that model ensemble reliably improve robustness: the paper only present two specific configurations of ensemble, namely SWEEN-3 and SWEEN-7, but there should be much more combinations to verify the effectiveness of ensemble. Also, I feel the results on MACER ensemble (Table 2) are too marginal.\n\n[1] Kawaguchi et al., Generalization in Deep Learning, 2017.\n\nMinor comments\n- p4, \"the volume of the certified region are more comprehensive ... \": then why the volume measure was not considered for evaluation in the experimental results?\n- p5, \"... will require 10,010,000 local evaluations ...\": it would be a bit confusing for some readers to figure out why it requires additional 10,000 inferences in the count. I guess it is from a rough prediction cost in the CERTIFY algorithm, but I could not find any related explanation of this in the paper.\n- Could SWEEN further improve ResNet-110 if one consider ResNet-110 x 3 ensemble model?\n- Why SWEEN-7 is not considered in Table 2?", "extra_scores": {}, "extra_text": {}}, {"review_id": "ollPhK1oUWT", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper demonstrates the advantages of ensembles of smoothed classifiers to achieve better approximately provable robustness.\nTheoreotically, it proves that under certain conditions, given enough amount of individual models, the function which the ensemble model represent can be archibitarily close to the optima within a function class. Empirically, the ensemble models have better performance in approximately provable robustness than an individual model of even more trainable parameters.\n\n--Novelty and Contribution\n\nPros:\n\n1. It is well known that adversarial robustness needs higher model capacity, so ensemble model can improve empirical robustness. Although not surprising, as far as I know, there is no prior work investigating ensemble in the context of randomized smoothing. \n\n2. The experimental result shows ensemble models can really improve the robustness. The results on CIFAR10 and SVHN is comprehensive. The authors also show that adaptive prediction ensembling can accelerate the computation.\n\nCons:\n\n1. There is a significant gap between theoretical analysis and experimental settings. Based on the condition above Equation (25), both the number of individual models and the number of training samples are trivially large. Theorem 2 should also emphasize the need of sufficient training samples.\n\n2. One assumption of Theorem 2: $l(0, y) = 0$ might be inconsistent with the practice. The most popular loss function is cross-entropy loss, which does not meet this assumption. I notice that this assumption is first used in Lemma 8 to prove Theorem 3. Removing this condition might result in a negative term on RHS of Theorem 4. I think the author should discuss on this assumption at least.\n\n3. It is better to have results on ImageNet or its downsampled version,  like [Salman 2019].\n\n--Presentation\n\nPros:\n\nGenerally, this paper is well-written. The notation and formulation are easy to follow.\n\nCons:\n\n1. The author should discuss more about the condition to finish the loop in Algorithm 1. This part is not well-justified. Especially, the authors should point out what is new in Algorithm 1 compared with [Inoue 2019].\n\n2. It is better to make an algorithm box demonstrating the whole method.\n\n--Summary\n\nFrom my point of view, this is a borderline paper. It systematically study the ensemble of randomized smooth models and demonstrate interesting results. The idea and the algorithm itself is somehow not intriguing.", "extra_scores": {}, "extra_text": {}}, {"review_id": "Uo_JBRkhbz", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this work, the authors study the effect of ensembling on randomized smoothing certification.  By learning diverse classifiers and then applying randomized smoothing the authors arrive at an ensemble of smoothed classifiers. Predictions are then made based on a linear combination of the models outputs which are weighted based on empirical risk and robustness of each model. The authors make an argument for the optimality of the proposed approach and show that it performs favorably compared to randomized smoothing certification of only a single model.\n\nWhile I can confirm that the notion of certified robustness that the authors propose in (6) is sensible and sound in terms of probabilistic guarantees of robustness, it is not clear to me exactly how Theorem 2 is the consequence of a using the proposed SWEEN model and not a property which is generally true of ensembles. Using a linear combination of models based on their empirical risk seems to be something which one could do in general, just that in theorem 2 the authors are using a notion of risk which also includes the certified robustness of the models. Perhaps I have missed something here. Given some time, I will read further into the exact details in the supplementary which I was unable to do sufficiently during the initial review period. \n\nThe results that the authors show for their models are favorable and show increased robustness wrt the adversarial smoothing criterion. I wonder if the authors have any results on adversarial attacks (e.g. FGSM, PGD) as there is some notion that using a diverse set of models can lead to a more robust predictor wrt attacks [1] but then there is evidence that for deterministic ensembles this may not be the case [2].\n\n[1] https://arxiv.org/abs/2002.04359\n\n[2] https://nicholas.carlini.com/papers/2017_woot_ensembles.pdf\n\n\nPost rebuttal response:\n\nI thank the authors for their response to my review and I take their point that establishing theorem 2 points to a limitation of using smoothing with ensembles, but I think this point could be made much more clear in the main text. Following a reading of all of the other reviews and re-evaluating the paper I remain optimistic and slightly positive about the paper as I think it is an important and interesting research direction; however, I am not fully convinced to increase my score given that some of the empirical comparisons could be greatly strengthened to be more than marginal improvements over MACER trained networks. I think that any insights that arise during the process of strengthening the results would contribute to a better understanding of the method and a stronger paper. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "JLw5UsQ2CSh", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors introduce SWEEN, an ensembling scheme for smoothed classifiers. This scheme uses pre-trained models and learns the weights used to sum the output predictions. During deployment, smoothed models rely on sampling a large number of input perturbations and ensembling exacerbates the computation burden. Hence, the authors also propose an adaptive scheme that automatically adjusts the number of samples.\n\nOverall, the paper is well-written and provides solid evidence that ensembling can improve certified robustness.\n1) In the experiments, the authors focus on SWEEN-3/7 with standard training and SWEEN-3 with MACER. Have the authors tried SWEEN-7 with MACER? (or simply to add the ResNet-110 to the SWEEN-3 ensemble). I am generally curious about the limits of the approach.\n2) While the adaptive scheme is useful, it distracts the reader from the main message. I'd suggest moving it to the appendix and consider experiments on ImageNet.\n3) The wording is slightly unclear on how exactly the ensemble weights are trained. From the supplementary material, I gathered that the weight are trained to minimize the cross-entropy loss on perturbed inputs (perturbed by Gaussian noise) - as done for \"standard training\". Is that correct?\n4) It is unclear why the $\\gamma$-robustness index needs to be introduced to demonstrate that SWEEN can be trained to near-optimal risk with a surrogate loss.\n\nDetails:\nA) Fig. 1 is not color-blind friendly and difficult to read (small font).\n\n\n---------\nUpdate post-rebuttal: Thank you for addressing most of my comments. The new results on ImageNets are greatly appreciated too. However, in light of other reviews, I would have hoped that the authors try better training procedures on SWEEN-7 (e.g., MACER even if it means using other ResNets instead of VGG), as otherwise it is difficult to judge whether ensembling really helps. It is unclear why MACER was not used on ImageNet (since all models are ResNets). Overall, the work explores a really important direction of research, but could benefit from further improvements.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper considers ensambling of smooth classifiers to improve certified robustness. Theoretical results are provided showing that taking ensambles of a large number of models is useful, while experiments show that combining only a small number of models improves performance. On the negative side, the experiments are somewhat inconclusive, as the base models are not state-of-the-art, and the combined results do not achieve state-of-the-art performance. In  this respect, further studies would be necessary to explore the effectiveness of the proposed technique.

In summary, while the topic of the paper is interesting and timely, the proposed ensambling technique is not especially exciting (as it is what one would naturally expect). On the other hand, the problem is reasonably well investigated (e.g., details are worked out well, both theoretical and experimental results are presented), although further experiments are needed (as recommended by the reviewers) to properly assess the potential and limitations of the approach. Accordingly, all reviewers agreed in the discussion that this is a borderline paper. Therefore, unfortunately, it cannot be accepted this time due to the heavy competition at the conference. The authors are encouraged to resubmit a revised version to the next venue, taking into consideration the reviewers' recommendations.
Decision: Reject