On the Certified Robustness for Ensemble Models and Beyond
Authors: Zhuolin Yang
Linyi Li
Xiaojun Xu
Bhavya Kailkhura
Bo Li
Venue:  (2021)
Keywords: Adversarial Machine Learning
Model Ensemble
Certified Robustness

Abstract: Recent studies show that deep neural networks (DNN) are vulnerable to adversarial examples, which aim to mislead DNNs to make arbitrarily incorrect predictions. To defend against such attacks, both empirical and theoretical defense approaches have been proposed for a single ML model. In this work, we aim to explore and characterize the robustness conditions for ensemble ML models. We prove that the diversified gradient and large confidence margin are sufficient and necessary conditions for certifiably robust ensemble models under the model-smoothness assumption. We also show that an ensemble model can achieve higher certified robustness than a single base model based on these conditions. To our best knowledge, this is the first work providing tight conditions for the ensemble robustness. Inspired by our analysis, we propose the lightweight Diversity Regularized Training (DRT) for ensemble models. We derive the certified robustness of DRT based ensembles such as standard Weighted Ensemble and Max-Margin Ensemble following the sufficient and necessary conditions. Besides, to efficiently calculate the model-smoothness, we leverage adapted randomized model smoothing to obtain the certified robustness for different ensembles in practice. We show that the certified robustness of ensembles, on the other hand, verifies the necessity of DRT. To compare different ensembles, we prove that when the adversarial transferability among base models is high, Max-Margin Ensemble can achieve higher certified robustness than Weighted Ensemble; vice versa. Extensive experiments show that ensemble models trained with DRT can achieve the state-of-the-art certified robustness under various settings. Our work will shed light on future analysis for robust ensemble models. 

Under review as a conference paper at ICLR 2021
ON THE CERTIFIED ROBUSTNESS FOR ENSEMBLE MODELS AND BEYOND
Anonymous authors Paper under double-blind review
ABSTRACT
Recent studies show that deep neural networks (DNN) are vulnerable to adver- sarial examples, which aim mislead DNNs make arbitrarily incorrect pre- dictions. To defend against such attacks, both empirical and theoretical defense approaches have been proposed for a single MI. model. In this work, we aim to explore and characterize the robustness conditions for ensemble ML models. We prove that the diversified gradient and large confidence margin are sufficient and necessary conditions for certifiably robust ensemble models under the model- smoothness assumption. We also show that an ensemble model can achieve higher certified robustness than single base model based on these conditions. To our best knowledge, this is the first work providing tight conditions for the ensemble robustness. Inspired by our analysís, we propose the lightweight Diversity Regu- larized Training (DRT) for ensemble models. We derive the certified robustness of DRT based ensembles such as standard Weighted Ensemble and Max-Margin En- semble following the sufficient and necessary conditions. Besides, to efficiently calculate the model-smoothness. we leverage adapted randomized model smooth- ing to obtain the certified robustness for different ensembles in practice. We show that the certified robustness ensembles, on the other hand, verifies the neces- sity of DRT. To compare different ensembles, we prove that when the adversarial transferability among base models is high, Max-Margin Ensemble can achieve higher certified robustness than Weighted Ensemble: vice versa. Extensive exper- iments show that ensemble models trained with DRT can achieve the state-of-the- art certified robustness under various settings. Our work will shed light future analysis for robust ensemble models.
INTRODUCTION
Deep neural networks (DNN) have been widely applied in various applications, such as image clas-
sification (Krizhevsky 2012 He al. 2016), face recognition (Taigman et al.] 2014 [Sun et al. 2014), and natural language processing (Vaswani et al. 2017 Devlin et al. (219). However, is
well-known that DNNs are vulnerable to adversarial examples (Szegedy al. 2013 Carlini & Wag- ner 2017 Xiao et al. 2018), and it has raised great concerns especially when they are deployed in the safety-critical applications such as autonomous driving and facial recognition.
To defend against such attacks, several empirical defenses have been proposed (Papernot et al., 20166 2016b, Buckman al. 2018 Madry al. (2088;; however, many of them have been attacked again by strong adaptive attackers (Athalye et al.) 2018 Tramer et al., 2020 On the other hand, the certified defenses (Wong & Kolter 2018 Cohen al. (2099) have been proposed to provide certi- fied robustness guarantees for given MI. models, so that no additional attack can break the model under certain conditions. For instance, randomized smoothing has been proposed as an effective de- fense providing certified robustness (Lecuyer et al. 2019 Li et al.) 2019 Cohen et al. [001 Yang ctt al. 2020). Compared with other certified robustness approaches such as linear bound propaga- tion (Weng et al. 2018: Mirman al. 2018) and interval bound propagation (Goowal et al. 2019) randomized smoothing provides a way to smooth a given DNN efficiently and does not depend on the neural network architecture.
However, existing defenses mainly focus on the robustness of a single ML model, and it is unclear whether ensemble MI. model could provide additional robustness. In this work, aim to char-

---

Under review as a conference paper at ICLR 2021
acterize the conditions for a robust ensemble and answer the question from both theoretical and empirical perspectives. In particular, we analyze the standard Weighted Ensemble (WE) and Max- Margin Ensemble (MME) protocols, and prove the necessary and sufficient conditions for robust ensemble models under mild model-smoothness assumptions. Under these conditions, we can see that ensemble model would be more robust than each single base model. The intuitive illustration of their certified robust radius is in Fig | confidence margins of base models would lead higher certified robustness for ensemble models.
Our analysis shows that diversified gradient and large
Inspired by our analysis, propose Training, a lightweight regularization- ing approach. We derive certified robustness for both WE and MME trained with DRT, and realize model-smoothness assumption via randomized smoothing. We analyze differ- ent smoothing protocols and prove that Ensemble Before Smoothing provides higher certified robustness. We further prove that when the adversarial transferubility among base models high, MME is more robust than WE.
Base Model 1
ensemble train-
True Class Deciion Region of Base Models
True-Class Decivion
Region Ensembles
Base Model 2
Figure 1: Iilustration robust ensemble.
We evaluate DRT on a wide range of datasets including MNIST, CIFAR-10, and ImageNet. Exten- sive experiments show that DRT can achieve higher certified robustness compared with the state- of-the-art art baselines with similar training cost as training a single model. Furthermore, when we combine DRT with existing robust models as the base models, DRT can achieve the highest certified robustness to our best knowledge.
We summarize our main contributions as follows: ditions for robust ensemble models including Weighted Ensemble (WE) and Max-Margin Ensem- ble (MME) under the model-smoothness assumptions. We prove that an ensemble model is more robust than single base model under the model-smoothness assumption. Our analysis shows that diversified gradients and large confidence margins of base models are the keys to robust ensembles. analysis, we propose DRT, a lightweight regularization-base -based training approach, containing both Gradient Diversity Loss and Confidence Margin Loss. 3) We derive certified robust- ness for ensemble models trained with DRT. The analysis of certified robustness further reveals the importance of DRT. Under mild conditions, we further prove that when the adversarial transferabil- ity among base models is high MME more robust than WE, 4) We conduct extensive experiments to evaluate the effectiveness of DRT on various datasets, which show that DRT can achieve the best certified robustness with similar training time as a single ML model.
1) We provide the necessary and sufficient con-
2) Based
Related work. DNNs are known vulnerable to adversarial examples (Szegedy et al., 2013). To defend against such attacks, several empirical defenses have been proposed (Papernot et al. 20 16 Madry et al., 2018). For ensemble models, existing work mainly focuses on empirical robust- ness (Pang et al. 2019 Li et al., 2020, Srisakaokul et al. 2018) where the robustness is measured by accuracy under existing attacks and certifiable robustness guarantee could be provided or en- hanced; or certify the robustness for a vanilla weighted ensemble (Zhang et al., 2019: Liu et al.) 2020) using either L.--baedd (Zhang al. 2018) verification or randomized smoothing but without diversity enforcement. In this paper, we aim to prove that the gradient diversity and base model margin are two key factors for certified ensemble robustness and based on these key factors, we propose a training approach to enhance the certified robustness of model ensemble.
Randomized smoothing (Cohen et al., 2019) has been proposed to provide certified robustness for a single ML model. It achieved the state-of-the-an certified robustness on large ImageNet and CIFAR-10 dataset under L2 norm. Several approaches have further improved it by: (1) choosing different smoothing distributions for different L.p norms (Dvijotham et al. 2019 Zhang et al. 2020
Yang et al. 2020), and (2) training more robust smoothed classifiers, classifiis,,,,,, using data augmentation (Co- hen et al. 2019). unlabeled data (Carmon et al. 2019). adversarial training (Salman et al.) 2019),
regularization (Li et al. 2019 Zhai et al. 2019). and denoising (Salman et al.) 2020). However, within our knowledge, there is no work studying how to customize randomized smoothing for en-
semble models. In this paper, we compare and select a good randomized smoothing strategy to improve the certified robustness of the ensemble.
In this paper, we mainly focus on the certified robustness under Lg norm. Though randomized
smoothing suffers from difficulties when it comes to Lae norm (Yang et al. 2020 Kumar et al.
2

---

Under review as a conference paper at ICLR 2021
2020 the analysis of certified robustness and the training approach DRT can be further extended to other Lp norms.
DIVERSITY- REGULARIZED TRAINING
In this section, will first provide the robustness conditions for the standard Weighted Ensemble and Max-Margin Ensemble. Using the robustness condition, we can compare the certified robust- ness of the ensemble models and single base model. The comparison shows that under model- smoothness assumptions, the ensemble models are more robust in terms of their certified robustness. Motivated by the key factors in the robustness conditions, we then propose Training.
Notations. Throughout the paper, we consider the classification task with C classes. We first define the classification scoring function f : IRd -> A which maps the input confidence vector, and f(x); represents the confidence for the ith class. We mainly focus on the confidence after normalization, i.c., f()) A {p Re ||pl| = 13 is the probability simplex. To characterize the confidence margin between two classes we define fuu/m (x) == f(a)) (()) The corresponding prediction F TRd + [C] is defined by F(x:) = arg max4e(c) I [(x);; We are also interested in the runner-up prediction F(2) (a) arg (( f(x).
In this paper, we mainly consider the model robustness against the Le-bounded perturbations. Definition (r-Robustness)) For a prediction function F: Fd + [C] and input Zo. if any instance {mo + 5 || |2|2 S r) satisfies F(x) = F(xo), we say model F is r-robust (at point 20)
We map existing certified robustness (Cohen et al. 2019) to r-Robustness in Appendix B.I
2.1 ROBUSTNESS CONDITIONS FOR ENSEMBLE MODELS
An ensemble model contains base models {fi) where F; and (22) are their top and runner-up
predictions respectively. The ensemble prediction is denoted by M : R F> [C], which is computed based outputs of base models following certain ensemble protocols. In this paper, consider both Weighted Ensemble (WE) and Maximum Margin Ensemble (MME).
Definition 2 (Weighted Ensemble (WE)). Given N base models {/:) |i and the weight vector {w;) E RVY, the Weighted Ensemble is constructed as MWEF Rd +
[C]
such that for any input
Mwe(Xx) = arg max Σ w (wo)) (E(C)
(1)
Definition 3 (Max-Margin Ensemble (MME)). Given N base models (f)) for input no the Max-Margin Ensemble model MMME Rdd + [C] is defined by
MaMm((F0) == (xoo)) where c arg max (fi(3)) Je p(" (m0))
(2)
iE[N]
WE sums up the weighted confidence scores of base models {f with weight vector (w; N
fim
and predicts the class with the highest value. WE is commonly-used (Zhang et al.] 2019 Liu al.
2020). Max-Margin Ensemble chooses the base model with the largest confidence margin between the top and the runner-up classes, which is direct extension from max-margin training (Huang et al. 2008).
2.1.1 GENERAL ROBUSTNESS CONDITIONS
For WE, since predicts the class with the highest aggregated confidence, we can easily observe its sufficient and necessary conditions for the certified robustness.
Proposition 1 (Robustness Condition for WE). Consider input Wo E &Rd with ground-truth label yo [C], and a Weighted Ensemble model MWE constructed by base models (ff with weights {w:) Suppose MwE (xa) = Yo- Then, the ensemble MWE is r-robust at point Dn if and only if
for any {ao 5 | < r), ming.e(c) Eÿ=1 W (x) 220200 0.
3

---

Under review as a conference paper at ICLR 2021
For MME, however, the model prediction is decided by the base model with the largest confidence margin. This "maximum" is a discrete operator and poses challenges especially in the multi-class setting. We cannot assert that the model predicts the true label by simply looking at the margins between only the true label and other labels unless carefully filtering out possible violated cases. In the following theorem, through careful analysis of the layout of confidence scores (e.g. enumerating the cases where Yo is the top class, runner-up class, or one of other classes, see details in Lemmas B. and B.2 we present succinct but sufficient and necessary condition for MME robustness.
Theorem (Robustness Condition for MME). Consider an input To E Rd with ground-truth label yo =[C]. Let MMME be an MME defined over base models {feliz Suppose: (1) MMME((Z)) =
yo: (2) for any E {ao + ô ||ô1|2 S r) given any base model E [N], either F((x) yo
or F (x) = yo. Then, the ensemble MMME is r-robust at point Do if and only if for any æ e
{ao 8: ||01| s...
max NE [C
min
fo0/ ve (x) 2 max min
1/ (z)).
In above theorem, the y/ and y associated with each base model fi and are respectively minimized among all the C' classes except class you We defer the proof to Appendix [B.2] This theorem along with the intermediate lemmas in the proof serves the foundation for our subsequent analysis.
2.1.2 DIVERSIFIED GRADIENTS AND LARGE CONFIDENCE MARGIN CONDITIONS
The conditions in Proposition and Theorem are rather general and involve x E {ar + 5 ||ö112 S r). which is challenging to verify for neural networks due to its non-convexity. In this section, we adapt the above conditions for DNNs based on confidence scores and gradient base models at input Zo. showing the diversified gradients and large confidence margin are the sufficient and necessary conditions for ensemble robustness.
RCC is B-smooth, if for any Definition 4 (B-Smoothness). A differentiable function Rd
x, y IRd and any output dimension j E [C]. [[xr) f(v)slla < 3.
The definition of B-smoothness is inherited from optimization theory literature, and is equivalent to the curvature bound in certified robustness literature (Singla & Feizi 2020). Note that smaller indicates smoother models, and when 3 = 0 the model is linear.
For Weighted Ensemble, we have the following robustness conditions.
Theorem 2 (Gradient and Confidence Margin Conditions for WE Robustness). Given input Tn Rd with ground-truie label yo E [C], and MWE as a WE defined over base models {fi) with weights {w: Mww = yo- All base models fü are 3-smooth.
(Sufficient Condition) The MwE r-robust at point To for any yi + yo.
Σ
w V.V /0/ (wo) (20) S -
w (wo) Br Wzs
(4)
(Necessary Condition) If MWE is r-robust point To. for any yi + yo.
Σ
N
/ (wr))
(mo)) + w /o/ (wr) Br
N
N
wy.
(5)
The proof directly follows from general robustness conditions and Taylor expansion at Zo-
For Max-Margin Ensemble with two base models, we derive the following robustness conditions.
Theorem 3 (Gradient and Confidence Margin Conditions for MME Robustness). Given input ap dd with ground-truth label yo E [C], and MMME as an MME defined over base models {f,, fz). MMME (x))= = yo- Both fi and f2 are B-smooth.
(Sufficient Condition) The MMME is r-robust at point To if for any yı V2 E [C] such that Y1 # yo and V2 # yo.
| /o/ (Hr) + 12 - 1 (12001114000) + - (xo)) 29r.
(6)
4

---

Under review as a conference paper at ICLR 2021
(Necessary Condition) Suppose E fao + 5 ||0||2 I r), and for i {1,2} either Fi(x) = yo or E!2) that y1 F yo and 1/2 # yo.
yo- If MMME r-robust at point 2o, for any yl, V2 [C] such
Va 2o (zo) + 2 /o0/ (xu))l2 s
1 11700/2 (av)) + (20)) ) + 28r.
The proof combines the proof procedure of Theorem with Taylor expansion zo. We remark that for MME, is challenging to extend the theorem to the case with n > 2 base models. The reason is that the "maximum" operator in MME poses difficulties for expressing the robust condition in succinct form of continuous function. Therefore, Taylor expansion is unable to apply. However, the general tendency should be the same.
We also derive the robustness conditions for a single model for comparison in Appendix B.3 Comparison of ensemble and single-model robustness. The preceding theorems enable the anal- ysis on comparing the certified robustness for an ensemble and a single ML model.
Corollary (Comparison of Ensemble and Single-Model Robustness). Given an input 2o E Rd with ground-truth label yo E [C). Suppose we have two B-smooth base models {fi,f2), which are both r- r-robust at point Vo- For any E 1):
(Weighted Ensemble) Define Weighted Ensemble MWF by base models {fi, f2] with weights {1i, W2). Suppose MMF((wo) = yoo. If for any label y; + yo- the buse models' smoothness B min( / (azo). f/n// ((oo))/(crrr) and the gradient cosine similarity v
/ (mr), V Vxl2 pool (xo)) S cos 0, then the MwE is at least R-robust at By with
1-A (1 CWE(1- - cos 0)) -1/2
R I+A
(0)-))))-_ where
(8)
OwE min VE Mo (wi /o0/ (soo)+-w2.f /0 (con))
200 wof1 (mn (mn))..0/ //0//
(ma)
max 148 (1 CC cos (oos)))= 0))
(Max-Margin Ensemble) Define Max-Margin Ensemble MMME by base models {11 Sup- yo- If for any label V1 $ and y2 * yo- the base models' (coo))(((²²2)) and the gradient cosine similarity cos(V yoo/u (xo), V va12 / (xx)) S cos 0, then the MMME is at least R-robust at Do with
pose MMME(2O) smoothness
A min mnin(ft// /oo/2n ( pgo/
1- A (1 CuMR(1 - cos 0))- where
R
(9)
I+ A
CMME
min
2 (wo) /200//2 (xa)
max 1 (1 CMMB(1 - cos -1/2 .1).
91-82-91 M2 / (r. t0 (mo))+
12 12 (mn))
The above corollary reveals the connection between ensemble and single-model robustness. As we can see, when cos < 1 c(++a) (C is either Owe or CAME). R > r. When the base models are smooth enough (3 0+ so + 0+), in Equations (8) and (9) the RHS + 1- As long as the cosine similarity of base models' gradients are not close to I. this condition can be easily satisfied, i.e., the ensemble models achieve higher certified robustness than base models. Furthermore, the diversity of gradients measured by cosine similarity is important for improving ensemble robustness. We defer the proof to Appendix B.4 Next, we discuss the implications of our theoretical analysis.
Key factors for the certified robustness of an ensemble, We observe that smaller magnitude of
joint gradients (e.g. || EE= w Vn, / (2n))l2 (Theorem 2 or /loo/1 /////// (xx)+ v / (æx) l|
(Theorem 3 indicates smaller LHS in Equations 4 to 7 Since these robustness condition has
the form LHS < RHS, implies that the robustness condition easier to be satisfied for current radius r, i.e., the certified robust radius could be improved. Therefore, smaller magnitude of joint gradients leads to higher certified ensemble robustness.
Inspired from low of cosines: for any two vectors a, b. ||a ([[a][3 + |abl| + 2||a|||||
+
bll2
|| b||2 cos b)) 1/2 the smaller magnitude joint gradients can be achieved by smaller gradient magnitude of base models or larger diversity (in terms of smaller
5

---

Under review as a conference paper at ICLR 2021
cosine similarity) between the gradient of base models. Therefore, constraining the magnitude of joint gradient is equivalent to improving gradient diversity and reducing base models' gradient magnitude, and they both contribute to improved ensemble robustness.
We can also observe that large confidence margins, such as Σ}=1 wyff f (xx) (Theorem and
/u (aro) + _2 // (xo) (Theorem 3). directly lead to larger RHS Equations (4 to 7 again implies that the robustness condition becomes casier to be satisfied and larger robust radius can be achieved. Thus, increasing confidence margins can lead to higher ensemble robustness.
Comparison between ensemble and single-model robustness. As the discussion following Corol- lary I reveals. when the base models are smooth enough, the ensemble model more robust than the base models. Moreover, we prove that certified robustness of ensembles is positively correlated with the base model (gradient) diversity, which is aligned with existing empirical observations (Tramèr
al. 2017 Pang et al. 2019).
2.2
ENVERSIYY-RGGLARRIE TRAINING
Inspired by the above key factors for the certified ensemble robustness, we propose the Diversity- Regularized Training. In particular, let zo be training sample, DRT contains the following two regularization terms in the objective function to minimize:
Gradient Diversity Loss (GD Loss):
(xn( = || an /0n/v, (2) (xo) + V Mo/l) (zo)lle-
(10)
Confidence Margin Loss (CM Loss):
LCM(wa) = f: /0/0/0 120 (xx) + 110 (2r0)
(11)
In Equations 10 and 3/ the ground-truth label of no, and yi (or (12)) ) the runner-up class of base model F; (or Fj). Intuitively, for each model pair (i,j) where i,j E [N] and * j. the GD Loss encourages the joint gradient, i.e., gradient vector between model and j. to be small. Note that the gradient computed here is actually the gradient difference between different labels. As our theorems reveal, it is the gradient difference between different labels instead of pure gradient itself that matters, which improves previous understanding of gradient diversity (Pang et al. 2019 Demontis et al. 2019). The GD Loss encourages both large gradient diversity and small base models' gradient magnitude in a naturally balanced way, and encodes the interplay between gradient magnitude and direction diversity. Compared with GD Loss, solely regularizing the base models' gradient would hurt the model's benign accuracy, and solely regularizing gradient diversity is hard to realize due to the boundedness of cosine similarity.
The CM Loss encourages the large margin between the true and rumner-up classes for base models. Both regularization terms are directly motivated by our analysis, and the detailed implementation process can be found in Section 4
ROBUSTNESS FOR SMOOTHED ML ENSEMBLES
To compute the certified robustness for different ensemble models based on Theorems 2 and 3 we need ensure the model smoothness which is challenging. Thus, in this section, we apply an adapted randomized model smoothing to compute certified robustness for general ensembles based on our conditions. We focus on Ensemble Before Smoothing (EBS) strategy: first construct the ensemble M from base models, then smooth M's prediction. M could be either MWw. or MMMEE- We also consider another strategy as smoothing base models first then ensemble. The analysis of these two strategies which proves EBS is more robust is deferred to Appendix C
3.1 CERTIFIED ROBUSTNESS OF ENSEMBLES VIA RANDOMIZED SMOOTHING
To derive the certified robustness of both MME and WE, we first define the statistical robustness and confidence for the single model and ensemble models.
Definition 5 ((e, p)-Statistical Robust). Given a random variable e and model F .R + [C]. at
point To with ground truth label yo, we call F is (e, p)-statistical robust if Pra(F((ao yo) 2 p.

---

Under review as a conference paper at ICLR 2021
Note that based on Theorem B.1 when the smoothed model G3 over Is (o (rob-tobust at point To-
F is (c, -)-ttatisttcal robust point zu.
Definition 6 ((c, A, p)-WE Confident). Let MWE be Weighted Ensemble defined over base models (Jr) with weights {w: If at point æn with ground-truth and random variable e, we have
Pr
max MyE[Cli vo
Σ wrfi(xv -cly S
we (1 fa(ou + e)vo) = -1-P.
(12)
we call Weighted Ensemble MWE (E, A, p)-WE confident at point 20-
Definition 7 ((E, A. PM-ME Confident). Let MMME be Max-Margin Ensemble over {f.) If at point Zo with ground-truth yo and random variable e, we have
filmo + f)2; S A(1 - fi(mr + E)bu))
Pr (E(N)
max ElC 7uo
(13)
call Max-Margin Ensemble MMME A, A. PM-ME confident at point Zp.
Note that the confidence of every single model lies in the probability simplex, and À reflects the confidence portion that wrong prediction class can take beyond the true class (1 - fa + c)). Now we are ready to present the certified robustness for different ensemble models.
random variable supported on Rd. Let MWE be Weighted Ensemble defined over {ft with weights {w;} The MwE is (e, (t))WW confident. Let zo E R be the input with ground-truth label yo E [C]. Assume {fe(zn + é) yo Ii= the confulence scores across base models for label yo, are i.i.d. and follow symmetric distribution with mean and variance s², where p. > x
Theorem (Certified Robustness for WE). Let
We have
Pr(Mwe(Ex + t = v0)
(14)
2 (1-(1+
Theorem 5 (Certified Robustness for MME). Let be random variable supported on RR Let MMME be a Max-Margin Ensemble defined over {f: f The MMME is (e, A2, 22.2))MMM. confident. Let Bo E Id be the input with ground-trune truth label yo E [C]. Assume {f((zo + E)go 1N Ji=1- the confidence scores across base models for label you are i.idd and follow symmetric distribution with mean y where > (1 + 1- Define 87 Var(ming fi(2 + )))))- We have
Pr(MaMME(O + vo) 2 11-p- <
(15)
2 (1 + (1+15))
The condition μ 1/(1 1/(1+A-11 guarantees normal performance of model, which is the sufficient condition for the standard setup PA > PB as (Cohen et al.) 2019)). For comparison, we also derive certified robustness for a single model in Proposition [.I We defer the proof' to Appendix D.I Based on our theoretical analysis above, we draw additional implications on the connections between the certified robustness and different losses. For Confidence Margin Loss, which aims at increasing the confidence margin of ensembles by enlarging that of base models, from Theorems 4 and 5 can see that small (A₃ in WE and A in MME) results in large Pr(M + <) Mo). i.e., large certified robustness. For Standard Training Loss, which increases base models' confidence of true class, we can view it as increasing the average confidence score, and its effectiveness is revealed from Theorems 4 and
3.2 COMPARISON FOR THE CERTIFIED ROBUSTNESS OF ENSEMBLES
The unified form of certified robustness above allows us to compare it for different ensembles.
Corollary (Comparison Certified Robustness). Let e be random variable supported on Rdd Over base models {f. let MMME be Max-Margin Ensemble, and MWE the Weighted Ensem- ble with weights {w.) Let E Rdd be the input with ground-truth label yo E [C]. Assume (ff(Zz + E) N,,, the confidence scores across base models for label yo, are i.i.d. and follow symmetric distribution with mean y and variance s², where max (1 + --1)-1,(0 +1+ -ー1)1 Define 87 = Var (minggt))) fi(2o + t)go) and assume 8f < 8.
7

---

Under review as a conference paper at ICLR 2021
When
A < 22'
(16)
A2
for any weights {ws MWE has higher certified robustness than MMMEE
When
A1
(-)))
x2"
(17)
A2
for any weights {w;) ManaR has higher certified robustness than MWFF
Here, the certified robustness is given by Theorems and
Appendix D.2 entails the detailed proofs. Note that given A is the weighted average and X2 the maximum over X's of all base models, \1/A2 reflects the adversarial transferability (Papernot et al., 2016a) among base models under the same p: If the transferability high the confidence scores of base models are similar (A's are similar), and thus A is large resulting in large \//22. On the other hand, when the transferability low, the confidence scores are diverse (X's are diverse), and thus A is small resulting in small //22.. Based on our theoretical analysis we can that MME is more robust when the transferability high; WE is more robust when the transferability is low. In Appendix D.3 we also prove that under certain distribution of fx c) when N is sufficiently large, the MME always more robust. Appendix entaails the numerical evaluations.
4 EXPERIMENTAL EVALUATION
In order to make fair comparison with existing work (Cohen et al. 2019 Salman et al. 2019). we evaluate our approach on different datasets: MNIST (LeCun et al. 2012), and ImageNet (Deng et al.) 2009). We show that by training MME/WE with DRT, our model can achieve the ofate-of-the-art certified robustness.
2010), CIFAR- Krizhevsky
4.1 EXPERIMENTAL SETUP
Baselines: We mainly consider two tatte-of-theannn baselines for certified robustness: 1) Gaussian smoothing (Cohen et al. 2019), which trains smoothed classifier by applying Gaussian augmenta- tion. 2) SmoothAdy (Salman et al., 2019), which integrates adversarial training on the soft approxi- mation. The comparison with more baselines can be found in Appendix E.4
Model structures: For each base model in our ensemble, we follow the same configuration of the baselines: LeNet (LeCun et al. 1998) for MNIST, ResNet-110 and ResNet-50 (He et al. 2016) for CIFAR-10 and ImageNet datasets.
Training: We smooth the N base models of ensemble following the baselines (Cohen et al. 2019
Salman et al. 2019). For each input 2. with ground truth you we use Do + e with e ~ N (0, o Ia) as training input for each base model. We call two base models (f; valid model pair at (æro yo)
both Fa + e) and Fy + +e) predict yo. For every valid model pair, we apply GD Loss and CM Loss with and P2 as the weight parameters. The final training loss of an ensemble is as below:
L = Σ (au + tc,00: +
Σ 1. F0( ( ++)=00
(GD( + c)ij +
Σ (.EE[N), =c(===))=00 FJ (#)
LCM(xx +) (18)
RE[N]
The standard training loss Lotd [20 + Mo); of each base model ft is either cross- loss in (Cohen et al. 2019, Yang et al. 2020). or adversarial training loss (Salman et al. 2019). We leave more training details in Appendix
Robustness Certification: During certification, we apply the MME or WE ensemble protocols over the trained base models ( to obtain ensemble M, then smooth M with noise ~ (O o² Ia). We report the standard certified accuracy under different Lg radius r as our evaluation metric (Co hen et al. 2019) (more implementation details in Appendix B
8

---

Under review as a conference paper at ICLR 2021
Table The certified accuracy under different radius MNIST dataset.
Radius
0.00
0.25
0.50
0.75
1.00
1.25
1.50
1.75
2.00
2.25
2.50
Gaussian Cohen et 2019
99.1
97.9
96.6
94.7
90.0
83.0
68.2
46.6
33.0
20.5
11.5
SmoothAdv (Salman 2019
99.1
98.4
97.0
93.0
87.7
80.2
66.3
43.2
34.3
24.0
MME (Gaussian)
99.2
98.4
96.8
84.3
69.8
48.8
34.7
23.4
12.7
DRT + MME (Gaussian)
99.5
98.6
97.5
95.5
92.6
86.8
75.2
55.8
44.3
38.0
27.0
MME (SmoothAdv)
99.2
98.2
97.3
96.4
93.2
88.1
80.6
67.9
44.8
35.0
25.2
DRT + MME (SmoothAdy)
99.2
98.4
97.6
96.7
93.1
88.5
83.2
68.9
48.2
39.2
33.5
WE (Gaussian)
99.2
98.4
96.9
94,9
90.6
84.5
70.4
49.0
35.2
23.7
12.9
DRT + (Gaussian)
99.5
98.6
97.4
95.6
92.6
86.9
75.4
55.8
44.6
38.2
27.2
WE (SmoothAdy)
98.2
97.4
88.2
81.1
67.9
24.9
DRT + WE (SmoothAdy)
99.1
98.4
97.6
96.7
93.4
88.5
83.3
69.6
48.3
39.4
33.5
Table 2: The certified accuracy under different radius for CIFAR-10 dataset.
Radius
0.00
0.25
0.50
0.75
1.00
1.25
1.50
1.75
2.00
Gaussian Cohen et al. 2019
78.9
64.4
47.4
33.7
23.1
18.3
13.6
10.5
7.3
SmoothAdy (Salman et al. 2019
68.9
61.0
54.4
45.7
34.8
28.5
21.9
18.2
15.7
MME (Gausstan)
80.8
68.2
53.4
38.4
29.0
19.6
15.6
11.6
8.8
DRT MME (Gaussian)
81.4
70.4
57.8
43.8
31.6
26.2
22.4
18.8
16.6
MME (SmoothAdv)
71.4
64.5
57.6
48.4
36.2
29.8
23.9
19.5
16.2
DRT MME (SmoothAdv)
72.6
67.2
60.2
50.4
39.4
35.8
30.4
24.0
20.1
WE (Gaussian)
80.8
68.4
53.6
38.4
29.2
19.7
15.9
11.8
8.9
DRT + WE (Gaussian)
70.4
57.9
44.0
31.7
26.2
19.1
16.8
(SmoothAdv)
71.8
64.6
57.8
48.5
36.2
29.6
24.2
19.6
16.0
DRT + WE (SmoothAdv)
72.6
67.0
60.2
50.5
39.5
36.0
30.3
24.1
20.3
4.2 EXPERIMENTAL RESULTS
In our experiments, we consider ensemble models consisting of three base models on MNIST, CIFAR-10 10. and ImageNet datasets. We observe that when training MME or WE (using different base models) with DRT, they can achieve the sfate-ofthhe-rt certified robustness.
The evaluation results on MNIST are shown in Table ! We observe that the certified accuracy can be improved slightly by applying the MME or WE compared with single base model (aligned with Corollary D After training with DRT, the improvements become significant and the DRT-trained ensemble models can achieve the highest certified accuracy under every radius r. In particular, DRT ensemble model can surpass the base model's certified accuracy around 7% under large radius r = 2.50. We further compare the certified robustness of WE and MME in Appendix D.4
that the DRT-based ensemble model can achieve the best certified robustness under different radius r (more experimen- tal details are in Appendix E..2). Note that the DRT-based ensemble with Gaussian smoothed base models can achieve comparable results to SmoothAdy with less training time (detailed efficiency analysis is in Appendix E.2pp We defer the results ImageNet to Appendix E.3 put all discus- sions about hyper-parameters under different settings in Appendix
On CIFAR-10 10 the evaluation results are shown in Table 2 Similarly, we
5 CONCLUSION
In this paper, we explore and characterize the robustness conditions for ensemble ML models the- oretically, and propose DRT for training robust ensemble practice. Our analysis provides the justification of the regularization-batt bbasd training approach DRT, as well as why an ensemble model could have higher robustness compared with a single model. Especially, we show that smaller mag- nitude of joint gradients, and the large confidence margins are the key factors that contribute to high certified robustness of an ensemble. We further compare the certified robustness of two types of en- sembles: Weighted Ensemble and Max- Max-Margin Margin Ensemble under the randomized smoothing regime. Extensive experiments show that the ensemble models trained with DRT can achieve higher certified robustness than existing approaches.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give false sense of se- curity: Circumventing defenses to adversarial examples. In International Conference on Machine Learning, pp. 274-283, 2018.
Jacob Buckman, Aurko Roy, Colin Raffel, and Ian Goodfellow. Thermometer encoding: One hot way to resist adversarial examples. In International Conference Learning Representations, 2018.
Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In 2017 ieee symposium on security and privacy (sp). pp. 39-57. IEEE, 2017.
Yair Carmon, Aditi Raghunathan, Ludwig Schmidt, John C Duchi, and Percy S Liang. Unlabeled data improves adversarial robustness. In Advances in Neural Information Processing Systems, pp. 11192-1 1203, 2019.
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. In International Conference Machine Learning, pp. 1310-1320, 2019.
Ambra Demontis, Marco Melis, Maura Pintor, Matthew Jagielski, Battista Biggio, Alina Oprea, Cristina Pita-Rotaru, and Fabio Roli. Why do adversarial attacks transfer? explaining transfer- ability of evasion and poisoning attacks. In 28th {USENIX} Security Symposium ((USENIX) Security 19), pp. 321-333 2019.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hi- erarchical image database. In 2009 IFFE conference on computer vision and pattern recognition, pp. 248-255. leee, 2009.
Jacob Devlin, Ming-Wes Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. In NAACL-HLT (1), 2019.
Krishnamurthy Dj Dvijotham, Jamie Hayes, Borja Balle, Zico Kolter, Chongli Qin, Andras Gy- orgy, Kai Xiao, Sven Gowal, and Pushmeet Kohli. A framework for robustness certification of smoothed classifiers using f-divergences. In International Conference on Learning Representa- fions, 2019.
Sven Gowal, Krishnamurthy Dj Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Uesato, Relja Arandjelovic, Timothy Mann, and Pushmeet Kohli. Scalable verified training for provably robust image classification. In Proceedings of the IEEE International Conference on Computer Vision, pp. 4842-4851, 2019.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp- 770-778, 2016.
Kaizhu Huang, Haiqin Yang, Irwin King, and Michael R Lyu. Maxi-min min margin machine: learning large margin classifiers locally and globally. IEEE Transactions on Neural Networks. 19(2):260- 272, 2008.
Alex Krizhevsky. Learning multiple layers of features from tiny images. University of Toronto, 05 2012.
Aounon Kumar, Alexander Levine, Tom Goldstein, and Soheil Feizi. Curse of dimensionality on randomized smoothing for certifiable robustness. In International Conference on Machine Learn ing, 2020.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278-2324 1998.
Yann LeCun, Corinna Cortes, and CJ Burges. Mnist handwritten digit database. ATT Labs (Online). Available: http://www..ccc....o////////////
2010.
10

---

Under review as a conference paper at ICLR 2021
Mathias Lecuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified robustness to adversarial examples with differential privacy. and Privacy (SP), pp. 656-672. IEEE, 2019.
privacc. In 2019 IEEE Symposium on Security
Bai Li, Changyou Chen, Wenlin Wang, and Lawrence Carin. Certified adversarial robustness with additive noise. In Advances in Neural Information Processing Systems, pp. 9464-9474, 2019.
Yueqiao Li, Hang Su, Jun Zhu, and Jun Zhou. Boosting the robustness of capsule networks with diverse ensemble. In 2020 10th International Conference on Information Science and Technology (ICIST). pp. 247-251. IEEE, 2020.
Chizhou Liu, Yunzhen Feng, Ranran Wang, and Bin Dong. Enhancing certified robustness of smoothed classifiers via weighted model ensembling. arXiv preprint 20Xiv:2000509363.. 2020.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference Learning Representations, 2018.
Matthew Mirman, Timon Gehr, and Martin Vechev. Differentiable abstract interpretation for prov- ably robust neural networks. In International Conference on Machine Learning, pp. 2578-3586 2018.
Tianyu Pang, Kun Xu, Chao Du, Ning Chen, and Jun Zhu. Improving adversarial robustness via promoting ensemble diversity, arXiv preprint
9990008846, 2019.
Nicolas Papernot, Patrick McDaniel, and Ian Goodfellow. Transferability in machine learning: from phenomena to black-box attacks using adversarial samples. arXiv preprint arXiv: 16Xvv16605.07277, 2016a.
Nicolas Papernot, Patrick McDaniel, Xi Wu, Somesh Jha, and Ananthram Swami. Distillation as defense to adversarial perturbations against deep neural networks. In 2016 IEEE Symposium Security and Privacy (SP), pp. 582-597. IEEE, 2016b.
Hadi Salman, Jerry Li, Ily Razenshteyn, Pengchuan Zhang, Huan Zhang, Sebastien Bubeck, and Greg Yang. Provably robust deep learning via adversarially trained smoothed classifiers. In Advances in Neural Information Processing Systems, pp. 11292-11 1303, 2019.
Hadi Salman, Mingjie Sun, Greg Yang, Ashish Kapoor, and Zico Kolter. Black-box smoothing: A provable defense for pretrained classifiers. arXiv preprint arXiv:2003.0100 009000 2020.
Saeed Saremi and Rupesh Srivastava. Provable robust classification via learned smoothed densities. arXiv preprint arXiv:2005.044: 045044, 2020.
Sahil Singla and Soheil Feizi. Second-order provable defenses against adversarial attacks. In Inter- national Conference on Machine Learning. 2020.
Siwakorn Srisakaokul, Yuhao Zhang, 7exuan Zhong, Wei Yang, Tao Xie, and Bo Li. Muldef: Multi-modell-aal -ased defense against adversarial examples for neural networks. arXiv preprint 0rXiv:1809000060 2018
Yi Sun, Xiaogang Wang, and Xiaoou Tang. Deep learning face representation from predicting 10,000 classes. In Proceedings of the IEEE conference on computer vision and pattern recogni- fion, pp. 1891-1898, 2014.
Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. arXiv preprint arXiv: 1312,619, 2013.
Yaniv Taigman, Ming Yang, Mare' Aurelio Ranzato, and Lior Wolf. Deepface: Closing the gap human-level performance in face verification. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 1701-1708. 2014.
Florian Tramèr, Nicolas Papernot, Ian Goodfellow, Dan Bonch, and Patrick McDaniel. The space of transferable adversarial examples. arXiv preprint arXiv: 1704.03453, 2017.

---

Under review as a conference paper at ICLR 2021
Florian Tramer, Nicholas Carlini, Wieland Brendel, and Aleksander Madry. On adaptive attacks to adversarial example defenses. arXiv preprint arXiv:2002.08347. 2020.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pp. 5998-6008, 2017.
Lily 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 International Conference Machine Learning, pp. 5276-5285, 2018.
Eric Wong and Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In International Conference on Machine Learning, pp. 5286-5295, 2018.
Chaowei Xiao, Jun- Yan Zhu, Bo Li, Warren He, Mingyan Liu, and Dawn Song, Spatially trans- formed adversarial examples. In International Conference on Learning Representations, 2018.
httlhttss://ee hatp::////peeeeiieeee net forum? 2 id HyydRMZC-
Greg Yang, Tony Duan, Edward Hu, Hadi Salman, Ilya Razenshteyn, and Jerry Li. Randomized smoothing of all shapes and sizes. In International Conference on Machine Learning, 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 International Conference on Learning Representations, 2019.
Dinghuai Zhang, Mao Ye, Chengyue Gong, Zhanxing Zhu, and Qiang Liu. Black-box certifica- tion with randomized smoothing: functional optimization based framework. arXiv preprint arXiv:2002.09163 2020.
Huan Zhang, Tsi Weng, Pin-Yu Chen, Cho-Jui Hsieh, and Luca Daniel. Efficient neural net- work robustness certification with general activation functions. In Advances in neural information processing systems, pp. 4939-4948, 2018.
Huan Zhang, Minhao Cheng, and Cho-Jui Hsieh. Enhancing certifiable robustness via deep model ensemble. arXiv preprint 1rXiv:1910.14633 2019.
12

---

Under review as a conference paper at ICLR 2021
Table 3: Main Theoretical Results.
Weighted Ensemble
Max- Max-Margin Ensemble
Single Model
General Robustness (Section 2
General Condition
Proposition
Theorem
Fact B.1
Gradient and Confidence
Theorem
Theorem
Proposition B.1
Margin Condition
Comparison
Corollary
Robustness with
Certified Robustness
Theorem
Theorem
Propusition
D.1
Rand. Smooth.
(Section 3
Comparison
Corollary
Appendix D.4
A TABLE OF THEORETICAL RESULTS
For quick index for the theoretical results, refer the readers to Table
B FORMAL DEFINITIONS AND PROOFS OF ROBUSTNESS CONDITIONS
In this appendix, discuss the connection between r-robustness and certified robustness given by randomized smoothing, and the detailed proofs of the robustness conditions in Section 2
B.I T-ROBUSTNESS AND RANDOMIZED SMOOTHING
In this subsection, we discuss the connection between r-robustness and the certified robustness given
by randomized smoothing (Cohen et al., 2019).
In randomized smoothing. each input's prediction given by the most probable prediction after adding noise. Formally, let (0, o² La) be Gaussian random variable, from model prediction F, we can define the smoothed classifier G Ied + [C] where G (x) = arg max (x=);;
of (x)
E L))
Pr 1 + cc) = e~N((0,0 1.)
(F(x + c)= j).
Intuitively, the confidence score for each class given by the probability of predicting that class under noised inputs.
Theorem B.1 (Simplified; Certified Robustness via Randomized Smoothing: Cohen et al. 2019 At point Zg let E ~ NO,0 IIa),, a smoothed model G.p is r-robust, where
r: σ (g)
(19)
and - the inverse fanction of Gaussian CDF
We remark that a tighter certified radius is = (of $ (of (mnu)
while for the ease of sampling, the Equation (19) is used more often in the literature. In Sec- tions 3 and 4 we use Equation (19) for analysis and empirical evaluation, and these results can be generalized to the tighter radius r easily.
B.2 GENERAL ROBUSTNESS CONDITIONS
Proposition I (Robustness Condition for WE). Consider an input Do E Rd with ground-truth label Yo [C], and an ensemble model MwE constructed by base models N f=1 with weights (w:)
Suppose MwB(xp) = Yo- Then, the ensemble MwE is r-robust at point Do if and only if for any {xo + Ôō: 161 r).
min C
w
w po0/th (x) 0.
20
Proof of Proposition 4 According the the definition of r-robust, we know MWF is r-robust if and only if for any point at + 8 where ||ōl|a I Mwr( + 6) yo. which means that for any
13

---

Under review as a conference paper at ICLR 2021
other label Ve o yo, the confidence score for label yo is larger equal than the confidence for label ys. It means that
N
Σ
Wy w
for any E {zo - 8: 11112 S r). Since this should hold for any * you we have the necessary and sufficient condition
N g (x) 2
min MC
wjff wyfgnn
(20)
Theorem (Robustness Condition for MME). Consider an input To E Rdd with ground-truth label
Vo [C]. Let MAME be MME defined over base models {ft) Suppose: (1) MMME(
Vo: (2) for any a E {Do + ||0|| I r), given any base model E [N], either F((z) = yo
or p(2)( (x) yo- Then, the ensemble MMME r-robust point wy if and only if for any
(mo + 6: |011 sr).
max N
min
f
/
x
max N
min WE CC
f/il (x)
W 1o
The theorem states the sufficient and necessary robustness condition for MME. We divide the two directions into the following two lemmas and prove them separately. We mainly use the alternative form of Equation (3) as such in the following lemmas and their proofs:
max iE[M]
min +c
(x) + min min iE(N) ME(CC)
pun/th (x)) 20.
Lemma B.1 (Sufficient Condition for MME). Let MMME be an MME defined over base models (f.) For any input xg E Rd, the
Ensemble MyME predicts MMME yo
min ie[M] cE
min iE(N) SNo/U: (xx)
min MEECC)
sun/th (a:o)
(00o) 2 0.
For brevity, for [N], we denote y: F.(wo), v/ (20) for each base model's top class and runner-up class at point
Proof of Lemma B.
Suppose MMME(Z0) * you then according to ensemble definition (see Definition 3). there exists E [N], such that (MME(#o) = Fo(xo) = Ye. and
Vi [N), # c, fe(2r))olle fa(20))r/vl.
(21)
Because Ye * No. we have fe(xx) < fe( that fe (2x))//10 2 (2x2)))//l. Now con- sider any model fo where [N], we would like to show that there exists y" # yo. such that fi (200) 2 )
If y you let y" == v/. trivially f((z)) = fi(2o))o/1';
If ya * yo. and y * yo. we let y = 1/. then f((2o)u//1l (x00)///1" 2 fi(20)oo/1'
If y: + you but vo yo. we let y == ye then fi(20) p/ =f((x)) 2 f((20) f.(2)) un/n'
Combine the above findings with Equation 21 we have:
Vi E [N], + c, Byy [C] and v. # yo. By. [C] and vf # yo, fc(xo))//m) >f fo(20))0111.
Therefore, its negation
Bi E [N]. i i c, Vy E [C] and v. # yo. Vy! E [C] and y, + yo.
+ (20))0//v:
20
(22)
14

---

Under review as a conference paper at ICLR 2021
implies M(xx) yo- Since Equation (2 holds for any V2 and yf the equation is equivalent to
Ri [N] i C, The existence qualifier over can be replaced by maximum:
min Be W.
) yo/ue (ara)
min s/([Clu
fi(wr) (o/ 0.
min 2
fa ((l0o)///(((00)) + max min ((00))o/ui 2 0.
iE[N] ME(C
is implied by
max [N
min
f/o ( + min iE MEECC)=/
min
poul 1h (200 2 0.
Thus, Equation 3
a sufficient condition for MMMM(1M) (za) yo-
Lemma B.2 (Necessary Condition for MME). For any input To Rdd for any base model i E [N], either F((z))) Yo or ((2 = yo. then Max-Margin Ensemble MAME predicting
MMMME(x)) = yo implies
1.m /o// (2o) + min min po/tl (200) (200) 2 O.
max min NE[N] =1
(E(N) M/(CO)//
Proof of Lemma B.2 Similar as before, for brevity, for E [N], we denote = Fi(xo)), oi F!(2) (x)) for each base model's top class and runner-up class at point zo.
Suppose Equation is not satisfied, it means that
Be [N], Byy E [C] and ve + yo. Vi E [N], But E [C] and vi yo: (w S/u/li (xo).
If ye = yo. then fet /2 (2o) I 0, which implies that 1 polli (aon) < O, and hence Fi(aro) # yo- Moreover, we know that f/:///(20) (xx) = ////00 (xo) 2 put /00 (xo) > fyo/vr (xx) 2 4 ( (xx) = (axo) so M(zu) + Fc(xo) yu-
If * i... v/a = yo. then f/e/ (xo) 2 vo > fr poloi (xo). If Fi(xo) = yo. then poalti (2o0) 2 poo/ol (ao)) = 1 /h/il (xa)) Thus, f f2 = /2e/ (xan) > p (po)). As the result, M(xr)= = Pa(o)) # yo-
For both cases, we show that MMMM(w0)) + yo. i.e., Equation M(xa) = yo-
is necessary condition for
Proof of Theorem 7 Lemmas B.I and B.2 exactly the two directions (necessary and sufficient
condition) of MMME predicting label yo at point æ. Therefore, if the condition (Equation (3) holds for any {xo 5 ||ō||2 I r). the ensemble MMMEE is r-robust at point 2o; vice
For comparison, here we list the trivial robustness condition for single model.
Fact B.1 (Robustness Condition for Single Model). Consider an input on E IRd with ground-truth label yo [C]. Suppose a model satisfies F(xu) = yo. Then, the model F is r-robust at point Do if and only if for any E {wo + 5 |00| I r).
min v: 3.e
f0o/ (x) 2 0.
The fact is apparent given that the model predicts the class with the highest confidence.
15

---

Under review as a conference paper at ICLR 2021
B.3 GRADIENT AND CONFIDENCE MARGIN-BASED CONDITION
We can concertize the preceding general robustness condition by gradients and confidence margins of base models leveraging Taylor expansion.
Theorem 2 (Gradient and Confidence Margin Condition for WE Robustness). Given imput zo R with ground-iruth label yoo E [C], and MwR. as a WE defined over base models {ft]s= with weights {w;) j=1- Mwr( = yo- All base model Sü are 3-smooth.
(Sufficient Condition) MWE is r-robust point Do for any ys # yo.
N
V
azjj
(
W go/ uo (20)
-3r Σ Wj-
j=1
(Necessary Condition) If MWE is r-robust point zo. then for any Yt # yo.
N w V x:
(200)
3//
(xo)
wj 5 go/ / (200 + 3r Wj.
Proof of Theorem From Taylor expansion with Lagrange remainder and the 3-smoothness as- sumption on the base models, we have
N
N
N (23w,)
Wj poo/ (200
- r
Σ ==1
Wy Vn /o (20)
1
min
wj No v (Ø)
2
mollas
1=1
j=1
f=1
N
Σ
w poo/vi (300)
- r|| Σ
w
V
(xx)
1
(2wr)),
2
j=1
j=1
(23)
1 ! Σ3= (28wg) are bounded from Lagrange remain-
where the term Em j=1 (23mg) and der.
From Proposition the sufficient and necessary condition of WE's r-robustness
E wyft (x) 2 0 for any yı E [C] such that y4 # yo, and any = xo + 8 where | S r.
Plugging this term into Equation 23 we get the theorem.
Theorem 3 (Gradient and Confidence Margin Condition for MME Robustness). Given input xo E Rd with ground-truth label yo [C*, and MMME as an MME defined over base models {fi, fe). MMME (xo) = yo- Both fi and fa are B-smooth.
(Sufficient Condition) for any y1, V/2 E [C] such that y1 + yo and 12 + yo-
// (#x) + V /00 / (mo))l S
1 -1110/01 (aro) + 1 / (xx)) 23r,
66
then MMME is r-robust at point Ø0.
(Necessary Condition) Suppose for any E fao + 5 110112 S r) for any E {1,2},
either F F((x)) Yo or (() = yo- If MMME r-robust at point Po. then for any y1,Y2 [C] such that yı f yo and y2 F yo.
1 (f7m//1) (xxo + et0/ (xo)) + 28r.
[Va/tn/v (xo)
/20 (zo)lla S
Proof of Theorem
We prove the sufficient condition and necessary condition separately.
(Sufficient Condition)
From Lemma B. since there are only base models, we can simplify the sufficient condition for MaMm((r)) = Yo as
min y0
8 (x) +
min
fz
no/vl (x) 2 0.
of
16

---

Under review as a conference paper at ICLR 2021
In other words, for any y1 yo and y2 + yo:
Nlol (2) + f (2) (x) 0.
(24)
With Taylor expansion and smoothness assumption, we have
min =a1l000al255
/1o/ (x) + f2
12 (x)
2 / (xn) + 12 p 22 (20) r|| V s: uu (xo) + V /20//2 (x00ll2 2 4,8r2.
Plugging this into Equation (44 yields the sufficient condition. In the above equation, the term -/2 4 is bounded from Lagrange remainder. Here, the 43 term comes from
the fact that 1 (a:) + 12 220/92 (ar) is (43)-smooth since it is the sum of difference of
3-smooth function.
(Necessary Condition) From Lemma [B.2] similarly, the necessary condition for MMME((>) yo is simplified to: for any y1 F Yo and y/ # yoo
/ (x) + f2 (x) 2 0.
24
Again, from Taylor expansion, we have
1 / (ar) + 12 22 (x)
min 2:11m-mall25:
<//10/911 (xo) + fl1// (ro) a 90/ (xo) + Vaf2
20/ ( (zo)ll2 + 4,
Plugging this into Equation 24 yields the necessary condition. In the above equation, the term + 4,3r² is bounded from Lagrange remainder. The 43 term appears because the same reason as before.
To compare the robustness of ensemble models and the single model, show the corresponding conditions for single-model robustness.
Proposition B.1 (Gradient and Confidence Margin Conditions for Single-Model Robustness).
Given imput wo E Rd with ground-truth label yoo [C]. Model F(xo) = yo. and is 3-smooth.
Sufficient Condition) for any y1 E [C] such that y1 + yo-
IV vo/ / (20)ll2 S - guo/ /oo/m (xx) Br.
(25)
r-robust at point Zng-
(Necessary Condition) If F is r-robust at point To. for any y1 E [C] such that yn # yo-
1 pui/ (mo) Br.
I az /oo (2ea)l2
(26)
Proof of Proposition B.I This proposition is apparent given the following inequality from Taylor expansion
/ (am)) r|| V 2o (xx) 112-3
min 2o
(enn)rla foo/ (x)) S /3n/ (xt) -r Van / wo/ (2c0) +/2
and the necessary and sufficient robust condition in Fact B.1
17

---

Under review as a conference paper at ICLR 2021
B.4 COMPARE CERTIFIED ROBUSTNESS OF ENSEMBLE MODEL AND SINGLE MODELS
Corollary 1 (Comparison of Ensemble and Single-Model Robustness). Given an input Eo E R with ground-trun truth label yo E [C]. Suppose we have two 3-smooth base models {1, which are both r-robust at point No- For any A E 1);
(Weighted Ensemble) Define Weighted Ensemble .MwE with base models f2). Sup- pose Mwe( = yo. If for any label Yi * yo. the base models' smooth- ness B S A {f ( (xo), f2n/31 f2 (xo)) (
and the gradient cosine similarity eVo/vi (ao)) S cos 0, then the MWE with weights {w1, W2} at least
cos cVel V R-robust point zo with
(xo), V Vaf2
cos 0)) 0))- ,where 1- A (1 Cwo((-cos())
R 1+
8
OWE min 0: (ws /0/ (mra) +ww w2 / (mma))²
200, W2 /20/ (22 1200/ (cep)
max (1 1WCE(1 cos c)s - 1}.
1/2
(Max-Margin Ensemble) Define Max-Margin Ensemble MMME with the base models {fi, f2). Suppose MMMEE (xo) = yo- If for any label * and Y2 * yo, the base models' smoothness I A min (foo// (aro), / ( and the gradient cosine similarity cos(V puo/ (xo), V= (mO) S cos 0, then the MMMAE is at least R-robust at point with
1 1- (1 CMME(1 cos 00)= -/2 ,where
R
I+A
CMME
min
2f/0//00 /1 (m 1.2 (ara)
max
1-A 143 (1 CMME cos 01)
3/ 3/1:
/f/0/V1 (#x)+ /20/50 (woo))²
Proof of Corollary 7 have
We first prove the theorem for Weighted Ensemble. For arbitrary ys & yo, we
V 2.
(x))
w2
V
/u//vi (2z
V
(xo) 11 + 2w w2 ( Moo//i (xa)) /20//0 (wo))
will
V VoJ 5 (mr)
V 2
/o/
(To + 2w0 wal /| V v /00/vi (om))lall V V /oo/ (mo)ll2 cos
(ppp + 3r)
1 120 (2on) + Br + 2wl w2 _ (proi (xoo) + Br ( 120//0 (200) + 3r) cos
(1
+ w
(
(20)) 3322 + f / (mo) Br
2w (noo// (wo) 3x22)
(frn/"(as)) (wo)) + Br22) cos 0
(6))
4
1
V wis
(oow) /o
w2 /20/// (ma) ? 2wn kuiww//10 /o0/// (oro//M((o))))))) 1/20 (aro) cos 0
cZ
A
v (1orAto/// (xo) + w2 / (zxo) 2(1 - cos (or /on/ (xo))u, 200 (xv)
1+ o²
(0.1
(1+
A
V1- ( (wi wo (aru) ) w2ff2 (L (xx))
(
where (i.) follows from the necessary condition Proposition B.1 (ii.) uses the condition on 33; and (Mi..) replaces 2w1 w (2ro (xx) leveraging CWE. Now, we define
1 A I+ A
K
Cwe(L - cos 0))-
All we need to do is to prove that MWF is robust within radius Kr. To do so, from Equation (4 we
upper bound ||l Vn./nn//M /2 (wo) + w2 Vn.2
/0///: (20) by KF (wi / (wo) + w2 /
(200
18

---

Under review as a conference paper at ICLR 2021
8Kr(wi + w2):
1e V Pe // (z)) W2 Vel2 f2 220/2/ (xo)ll2
v1 (1 cos O) (1 f00// (xo) + w2f2 22222 (xxo)
A)
(1 - cos
f (mo) + w2f2 2h (aoo
1- A
(1 cos OWF. 1122 (ifh p/n/ (200) + w2f2 220/ (xx)
I-A
1+3
Kr (1 A) (iili /// (200) ) + +12 12l22 /0/ (mre)
Kr (wis1 fon/// (3r0) + w2s2 120/ (xx) A min minffmm/vi f/1//v
(xo). f2 / (ao)}(w) + wz))
from I's condition, Notice that A min f/m/// (zo)) f2m/ (zu)} 7
| V v= /o/ (320) + 2/ v //// (xo))l2
W1f1 (1f//// ( (xo) w2f2 /v1 (xo)
? + w2))
Kr
²²
[wif (wnffo//i (xo) w2 fo/f0// (2o)
3Kr(wi + ww2) K2
Kr
1
(w2sto/bl (wo)) / (mo) 3Kr(w1 + w2))
Kr
From Equation 4 the theorem for Weighted Ensemble is proved.
Now prove the theorem for Max-Margin Ensemble. Similarly, for any arbitrary yıs y2 such that 21 A 3/2 f you we have
| elo (Ho)
+ V Vef2
e/0//1 (xo))l2
1
(1 cos CMMEE (1 (xx) + f20//2 (xx)
+
Now define
1-4 (1 CMMME1 - -1/2
K' = I+A
Again, from I's condition we have A Amin (//00// (2 (2ro)) 2 3²2 and
V po// (wo) + V (200)12
K'r (fto// (xx) + f20/ (Ix) 2,3"'r.
From Equation (6). the ensemble is (K'r) at point To. i.c, the theorem for Mar-Mn Ensemble is proved.
DISCUSSION
Optimizing Weighted Ensemble. As we can observe from Corollary 1 we can adjust the weights {W1, w2) for Weighted Ensemble to change CWE and the certified robust radius (Equation Then comes the problem of which set of weights achieve the highest certified robust radius.
Since larger Owe results higher radius, we need to choose
2w W2 elu/ (xx.) 1.2 (x:0
(WOPT, W2 OPPT) arg max min
yo (w0 /lol 91 (xo) + /300/ y1 (I)) )2
19

---

Under review as a conference paper at ICLR 2021
Since this quantity is ocale-invariant, can fix wi and optimize W2 get the optimal weights. In particular, if there are only two classes, we have a closed-form solution
2w w2 w 0n (xra) 122 //0/21 (20)
(w) OPPTT w2 2 arg max
122 (wi f //0//1 (20)) w2 12 21 (xn))² (ke
f2 vi (ar)), k. s1 v (xo) k E IR+):
and corresponding OwE achieves the maximum 1/2.
For special average weighted ensemble, we get the corresponding certified robust radius by setting w1 w2 and plug the yielded
2 (zon).12 / (wo)
OWE
min yo
10,
(f1o vi (x00) + f2 /20/v1 vi (xo))²
into Equation
Comparison between ensemble and single-model robustness. We expand the discussion in Sec- tion 2.1 The similar forms of R in the corollary allow us to discuss the Weighted Ensemble and Max- Ensemble together. Specifically, we let C' be either Cwe CMME, then
1 (1 C(1 - cos 0)) -/3 1+ A
R R=
Since when R > r, both ensembles have higher certified robustness than the base models, we solve this condition for cos
R>
1 A
1 1 1--(11-- cos
1+A
44
cos 1 < 1
C(1 +11
Notice that C' E (0, 1/2). From this condition, we can easily observe that when the gradient cosine similarity smaller, is more likely that the ensemble has higher certified robustness than the base models. When the model is smooth enough, according to the condition on 3, we can notice that A would be close to zero As a result,
2(++ is close to Thus, unless the gradient base models is (or close to) colinear, it always holds that the ensemble (either WE or MME) has higher certified robustness than the base models.
4A
20

---

Under review as a conference paper at ICLR 2021
C ANALYSIS OF ENSEMBLE SMOOTHING STRATEGIES
In Section S we mainly use the adapted randomized model smoothing strategy which named
Ensemble Before Smoothing (EBS). We also consider Ensemble After Smoothing (Ensemble After Smoothing). Through the following analysis, we will show Ensemble Before Smoothing is generally better than Ensemble After Smoothing which justifies our choice of the strategy.
We formally define Ensemble Before Smoothing strategy as below:
Definition C.1 (Strategy: Ensemble Before Smoothing (EBS)). Let .M be an ensemble model over base models {ff )- Let e be random variable. The EBS ensemble GM R + [C] at imput zo E Rd is defined by:
(2 = arg max Pr(M(zu+ +c) j). jE
(27)
We define the Ensemble After Smoothing strategy accordingly: Definition C.2 (Strategy: Ensemble After Smoothing (EAS)). Let M be ensemble model over IRd +> [C] at input
base models {ft).= Let e. be a random variable. The EAS ensemble H 2n E Rd is defined as:
(m))) == G.P (a20) where
argggaa max g8, (2o) (20)-
(28)
(E(N)
Here, è is the index the smoothed base model selected.
Remark. In EBS, first construct model ensemble M based on base models using WE MME protocol, then apply randomized smoothing on top of the classifier. The classifier predicts the most frequent class of when the input follows distribution No +
In EAS, we use c to construct smoothed classifiers for base models respectively. Then, for given input æg, the ensemble agrees on the base model which has the highest probability for its predicted class.
C.I CERTIFIED ROBUSTNESS
In this subsection, we characterize the certified robustness when using both strategies.
C.1.1 ENSEMBLE BEFORE SMOOTHING
Proposition C.1 (Certified Robustness for Ensemble Before Smoothing). Let G be an ensemble constructed by EBS strategy. The random variable o2)), Then the ensemble GM is r-robust at point 26 where
r r==00
(29)
Here, (0o)) (M.(M +E) j).
The proposition is direct application of Theorem B.1
C.1.2 ENSEMBLE AFTER SMOOTHING
Theorem C.1 (Certified robustness for Ensemble After Smoothing). Let Hi be an ensemble con-
structed by EAS strategy over base models (fi) The random variable ~ No,, a² 22I)). Let
Yo (2)). For each [N], define
o -1 (g (Zo)GE, (mo)):
= Yu
-o -1 gr. (wo) o5, (200)
Gf (xr)) + yo
Then the ensemble H&, is r-robust at point æn where
= [a rs min
(30)
2
21

---

Under review as a conference paper at ICLR 2021
Remark. The theorem appears be bit counter-intuitive picking the best smoothed model in terms of certified robustness cannot give strong certified robustness for the ensemble. As long as the base models have different certified robust radius (i.e., r, are different), the r. certified robust radius for the ensemble, is strictly inferior to that of the best base model (i.e., max r;). Furthermore, if there exists base model with wrong prediction (i.e., ri S 0), the certified robust radius is strictly smaller than half of the best base model.
Proof of Theorem C.1
Without loss of generality, assume r1 > r2 rN. Let the pertur- bation added to To has L2 length 6.
When 8 YN, since picking any model always gives the right prediction, the ensemble is robust.
When rN < S rItrN the highest robust radius with wrong prediction is - rN. and we can still guarantee that model fi has robust radius at least 71 - from the smoothness of function x + Sf, (a: (a))s, (ar) (Salman et al. 2019). Since ri - 2 -ーーrx 2 rN. the ensemble will agree on fi other base model with correct prediction and still gives the right prediction.
2
When 8 > TLtNN suppose fN is a linear model and only predicts two labels (which achieves the tight robust radius bound according to Cohen et al. (2019)), then fN have robust radius 8 TN for the wrong prediction. At the same time, for any other model ft which is linear and predicts correctly, the robust radius is at most r; 5. Since r; m 5 f1 TI --NN, the ensemble can probably give wrong prediction.
2
In summary, we have shown, the certified robust radius can be most For any radius 5 r, there exist base models which lead the ensemble H (20 to predict the label other than yo-
C.2 COMPARISON OF TWO STRATEGIES
In this subsection, we compare the ensemble strategies when the ensembles constructed from two base models.
Corollary C.1 (Smoothing Strategy Comparison), Given MAME, a Max-Margin Ensemble con- structed from base models and H MMAEE be the EAS ensemble. Suppose at point Bg with ground-truce label yo, G.,, (Iu) = G7. (ar0) = Yo- Dr. (2r)) > 0.5, gr, (2o) 0.5.
Let (0, T Let Gomaa be the EBS ensemble,
Let 5 be their probability difference for class yo. i.e, 8 19. (2:0) 9%. (20) Let Puin be the smaller probability for class yo between them, i.e. pmin == min (Iu) you 9F, (Zu)go We denote to the probability of choosing the correct class when the base models disagree with each other; denote Pah to the probubility of both base models agreeing on the correct class:
p = Pr PrMMMME (wo + + = -yol Fa (mro + 6) + Folwo + and (Fa(xr + E) = 30 or Polar + E) = yo))
Pob == (F +c) (x0 + <) 90))
We have:
1. 1fp> > 1/2 + (2 + 4(pmin 1 rG TH-
1fp < 1/2, TG.
Here, TG is the certified robust radius of G GMMnE computed from Equation certified robust radius of H MAnEE computed from Equation (30
29
and TH is the
Remark. Since p is the probability where the ensemble chooses the correct prediction between two base model predictions, with Max- Margin Ensemble, we think > 1/2 with non-trivial margin.
The quantity Pmin Pob and ó both measure the base model's diversity in terms of predicted label distribution, and generally they should be close. As a result, 1/2 + (2 + 4(Pmin - Po)) ss 1/2 + 1/6 = 2/3, and case (1) should be much more likely to happen than case (2). Therefore, EBS usually yields higher robustness guarantee. We remark that the similar tendency also holds with multiple base models.
22

---

Under review as a conference paper at ICLR 2021
Proof of Corollary
C.1
For convenience, define Pa. Ir. (200)a: Pb 9F, (2u0)00 where Pa
Pb + 6 and Pmin
pb-
From Proposition
C.1
and Theorem C.1 we have
0
(Pr(MMME(ZO +e) )0o), TH 2
σ (po) + (pb))
FG
24
2
Notice that Pr. (M t) 1/0) Pob + p(Pa + Pb 2pab), we can rewrite To
ra 2 2Φ 1 (Pab p(pa + pb 2pab))
1. When p 1/2+ (Pmin Pab)//)-11 since
Pa + pb + 2pab
Pa Pab
>
2 +
2 +
2+ 4(Pmin Pat)
20 + 4pps Pon))
2(pa + 2pab)
Pa. + ps 2pab
we have Pob + p(po + Pb 2pab)
> Po- Therefore, ra > oΦ (po). Whereas, TH S 0/2.
2Φ (Pa) = =0 (pa). So TG > TH.
When p s 1/2.
Pab + p(pe + pb 2pab) S Pab + 1/2 (Pa + - -2pbt) (Pa + pb)/2. Therefore, ra < oΦ (e0-1((pp /2b) Notice that Φ-1 is convex in [1/2, +00), + (p-(()) + Φ (p6) 2 24 ((pa + pb)/2), i.e., TH 2 TG.
23

---

Under review as a conference paper at ICLR 2021
D PROOFS AND EXPERIMENTS OF ROBUSTNESS FOR SMOOTHED ML ENSEMBLE
In this appendix, we provide the detailed proofs and discussions for the results in Sections 3.1 and 3.2 Moreover, to present a more intuitive understanding, we show both numerical and realistic experiments for the theorems.
D.1 CERTIFIED ROBUSTNESS VIA RANDOMIZED SMOOTIING
First, using the notion of (c. p) Statistical Robust (Definition 5) we prove the certified robustness of the single model and ensembles under the i.i.d. assumption of the confidence scores. As noted Section 3.1 and Appendix BB.1 when e follows some distribution such as (0, o² Ia), we can translate the statistical robustness guarantee to y-robustness guarantee of the smoothed classifier.
The following lemma is frequently used in our following proofs:
Lemma D.I. Suppose the random variable X satisfies EX > O, Var(X) < oo and for any & E B.p,
Pr(X 2 EX x) Pr(X EX 2)), then
Var(X)
Pr(X & 0) - 2(EX)
Proof of Lemma D.I Apply Chebyshev's inequality random variable X and notice that X is symmetric, then we can easily observe this lemma.
D.1.1 CERTIFIED ROBUSTNESS FOR SINGLE MODEL
As the start point, we first show a direct proposition stating the certified robustness guarantee of single model.
Definition D.1 ((c, X, p)-Single Confident). Given a classification model F. If at point 2g with ground-truth label yo and the random variable we have
f(xo + E)v, s X(1 f(xo + +1)==)))) 1
Pr
we call F (c, A. p)-single confident at point Do- U.
Proposition D.1 (Certified Robustness for Single Model), Let e be random variable. Let F be classification model, which is (E. A3, -isigle confident. Let xo Ra be the input with ground- truth yo E (C). Suppose f(xo + e) follows symmetric distribution with mean μ and variance s².
where μ > (1 (1+))))-1 We have
82
Pr(F(ao + +c) = vo) 2 12-12 2(
+ X33 1-112 1-12
Proof of Proposition DJI
We consider the distribution of quantity y == f(ao + c) Az(1 f(oo + y. Since the model F is (e, λa, p) -ingle confident, with probability 1 --p p. Y f( c)g - max,, E( I (wo + <) We note that since
EY = (1 Aa) A3, Var(Y) = (1
from Lemma D.I
g2
Pr(Y 20) S 2(μ (1 1ー11
Thus,
Pr(F (Do + c) vo) = Pr(F(zu + c) 4y)
f(zo + t) <0)
= 1 Pr f(zo + c)yo
max
# #
2 - p- - Pr(Y <
2
2 1 - 2(μ (1 + 23 1
24

---

Under review as a conference paper at ICLR 2021
D.1.2 CERTIFIED ROBUSTNESS FOR ENSEMBLES
Now we are ready prove the certified robustness of the Weighted Ensemble and Max-Margin Ensemble (Theorems 4 and 5)
In the following text, first define statistical margins for both WE and MME, and point their connections to the notion of (e. -S-attissti Robust. Then, we reason about the expectation, vari- ance, and tail bounds of the statistical margins. Finally, we derive the certified robustness from the statistical margins.
Definition D.2 (X1; Statistical Margin for WE MwE).. Let MWE be Weighted Ensemble defined over base models {fa]i= with weights {wi)i Suppose MwE is (e, A1, p)t-))))oofddeee We define random variable X1 which is depended by random variable
(e(c)== = (1+
Σ 1 + <)vo A1 A11120111-
(31)
Definition D.3 (X2; Statistical Margin for MME MMME). Let MMME be Max-Margin Ensem- ble defined over base models {ft))e Suppose MMME is P2 PMMMMMM) We define random variable X2 which is depended by random variable
x2(6) ==
(1 A2)
max Ji e) + min fi(w0 E)go 2A2. iE[N]
(32)
sE[N]
We have the following observation: Lemma D.2. For Weighted Ensemble,
Pr (Mwr( + =))=)) 2 1- Pr (Xi(E) < 0).
For Max-Margin Ensemble,
Pr (MMME(R0 +6) -/0) 2 1 Pr (X2(e) <)).
Proof of Lemma D.2
(1) For Weighted Ensemble, define the random variable X,:
Xi(e) == min
So v (wo + e).
Since MWE is A1, -WE-WW--iiddedd from Definition 6 with probability - we have
N
Xi( >
Σ
wi (f, + c) -de11 fz - =))a))
1=1
(1 A2)
Wy wyf5(2y + t A1|lw|11 =8((e). j=1
Σ
Therefore,
Pr(MwE(Ze +c) = yo) Pr ( Pr(X((c) 0).
(2) For Max-Margin Ensemble, we define the random variable Xy:
X2(c) = max min NE v.llol
/.n//i (mo + c)
min min sE[M p.E|Cl:u #
/.w// (x0 + c).
Similarly, since MMME (E, A2, p)- -MME-confiiennn, from Definition 7 with probability p. we have
Xz(e) 2 max (fi(Iu + E) - >2(1 - f.(xo + c)po)) + min (fi(zo + c)go -xe(1 -f((o + c))))) sE[N]
sE[N]
= (1 + X2)
max fe(20 + c) + min f( + x) (E[N
2)₂ = 82(c).
(E(N)
25

---

Under review as a conference paper at ICLR 2021
Moreover, from Lemma B.1 we know
Pr(M(ao +) = yo) 2 Pr Pr(X2(e) 2 0) 2 1 p- p-pp--PPaA Pr((X(() <0)
As the result, to quantify the statistical robustness of two types of ensembles, we can analyze the distribution of statistical margins X1 and X2.
Lemma D.3 (Expectation and variance of X, and X2). Let X1 and X2 be defined by Definition D.2 and Definition respectivey,. Assume {fi( + E) IN are i..d. and follow symmetric distri- bution with mean and variance 5². Define s = Var(minge(w] filw0 + ))))). We have
E (E) =(1 21)1(2(1111- A11/w|11,
Var Var ( = (1 )1 3² 1
Ex2(E) -21 + 22) 2A2,
Var X2(e) S 4(1 + x²)
Proof of Lemma D.3
(X,(c)= = (1 A1)
Σ
Ewy f + c)20 A11120111 (1 A1)1(w/lan- A1 \2/120111;
N
(cr (1++)
Σ
Varl + c) = + (1)² 1
According to the symmetrie distribution property of {fi(xo + E) yo J we have
E (x)(E) B(1 + A2)
max fi(xo + E)go min fa + e)m) 2A2 (E[N)
iE(N)
= 2 + X2)11 2d2.
Also, due the symmetry, we have
Var
min fi(w0 + 6)20 iE(N]
Var
max Si + +) =0g (iEN)
As a result,
Var
S (1 (1 2 4s7.
From Lemma D33 now with Lemma D.I. we are ready to derive the statistical robustness lower bound for WE and MME.
Theorem (Certified Robustness for WE). Let e random variable supported on Rdd Let MWE be Weighted Ensemble defined over {fi)N with weights {w,) The MwE is (e, (1,)) PE-WE confident. Let xo E _d be the input with ground-truce truth label yo E [C]. Assume (fi(20 + E) e) Ti= the confidence scores across base models for label you are i.i.d. and follow symmetric distribution with mean and variance s², where μ > (1 1 We have
82
Pr(Mwe(aa + 6) = =00)= 2 1
14
|
(1
Theorem 5 (Certified Robustness for MME). Let e be a random variable. Let MAME a Max- Margin Ensemble defined over (f.). The MMME is (e, X2, confident. Let an e Rd be the input with ground-truth label yo E [C]. Assume {fo + e) NN, the confidence scores across base models for label yo. are i.i.d. and follow symmetric distribution with mean P where (1 - Define 87 Var(minne(N) fi + )) We have
87
Pr(MMME(ED +c) = =0o) 2
15
(1 X3 1
2 1
26

---

Under review as a conference paper at ICLR 2021
Proof of Theorems 4
and 5
Combining Lemmas D.1 to D.3
get the theorem.
Remark. Theorems f and 5
provide two statistical robustness lower bounds for both types of ensem- bles, which is shown to be able translate certified robustness.
For the Weighted Ensemble, noticing that X1 is the weighted sum of several independent variables, can further apply McDiarmid's Inequality to get another bound
P (1- (1-(1+)7)))))
Pr(Mwe(an + E) yo) 2 1 - exp
which is tighter than Equation 14 when | /f/l/l w [ is large. For average weighted ensemble, || = N. Thus, when N large, this bound is tighter.
Both theorems are applicable under the i.i.d. assumption of confidence scores. The another assump- tion μ max + predicting the true class rather than other classes, i.., the ensembles have non non-trivial clean accuracy.
))'))- (1 + ) insures that both ensembles have higher probability of
D.2 COMPARISON OF CERTIFIED ROBUSTNESS
We first show and prove important lemma. Then, based on the lemma and Theorems 4 and 5 derive the comparison corollary.
Lemma D.4. For P. X1, A2, C' > O, when we have
12)3 < p S L, and C <
F1 (A +1)-1 11 (AT +1--1
<C
d
<x,1'
(0-1
12
+1- -1 -1). (33)
A2
1+ A2
Proof of Lemma D.4
p (A₂² + +1)
11 (X + 1) <C
C
> 11(1 CC)
A/ +1 +1++1
/1/22
C-1
\2 +1 -M(C-1-1) 1)
<
A1/D2
A1
\/ x +1 1
1
1- 1 + C-1
|1
C-1
A2 +1 11 #
d2
0-1
1 15 11) +
A2
(-1
1 - 22 -1 +1 +1-
\1
(0-1(1)
(n- d2
1 1+>2 )
+1 +1- 11) ) -1
-1)
d2
Now can show and prove the comparison corollary.
Corollary 2 (Comparison of Certified Robustness). Lei e be random variable supported on IRd. Over base models {f let M be Max-Margin Ensemble, and MwE the Weighted Ensem- ble with weights Nw Let æpp E Rdd be the input with ground-truth label yo E [C]. Assume (f. + p the confidence scores across base models for label yo, are i.i.d, and follow sym- metric distribution with mean and variance s where μ >> max + 1-1) 1,1 - Define 8 Var(min Se(20 <)go) and assume 88 <
27

---

Under review as a conference paper at ICLR 2021
When
((= + +1 1 -1).
16
X2
for any weights {wi Mwr has higher certified robustness than MaMME.
When
((vis (M + +1-H -1
A
X²
17
A2
for any weights {wi MAME has higher certified robustness than MWE.
Here, the certified robustness is given by Theorems and
Proof of Corollary
2
(1) According to Lemmal D.4 we have
(1 X )د + - -1)
<
222
1
A2
85
1
(12
+ 1)- 81
(Ai
+ +1)11
w
(A₂ + 1)-1
81
w
(X
+ +1--1
8
s²
$f 2 ( (1 x 3'
(1+
According to Theorems and we know the RHS Equation 14 Equation 15 i.e. MWE has higher certified robustnesss than MMMEE
larger than the RHS in
(2) According to Lemma D.4 we have
A A2
> xo
[Nos (p (a- (1 (1+ + -1- -1
8
(N₂² 1)
VNs1
(AT 1)-1
(A²² + 1)-1
81
(>T
+ 1)-1
[
5²
87
w
(1+ (1-11+ (
(1 + +1
2
According Theorems and
know the RHS in Equation 15) larger than the RHS in
Equation 14] i.e., MMME has higher certified robustnesss than Mwe-
Remark. As we can observe in the proof, there is a gap between Equation 16 and Equation 17
when / lies in between RHS of Equation (T6) and RHS of Equation I7pp it is undetermined
which ensemble protocol has higher robustness. Indeed, this uncertainty is caused by the adjustable weights (w, N of the Weighted Ensemble. If we only consider the average ensemble, then this gap is closed:
((138) (H (n- (1+ (1)))))1 + +1 11) -1)
A1 MAME robust
Xzz
A2 MWE more robust
28

---

Under review as a conference paper at ICLR 2021
In the corollary, assume that sy 8. Note that s² is the variance of single variable and o7 is the variance of minimum of N i.idd variables. For common symmetry distributions, along with the increase of N, of shrinks in the order of O(1/NB) where B E 2). Thus, long as N large, the assumption will always hold. An exception is that when these random variables follow the exponential distribution, where sf does not shrink along with the increase N. However, since these random variables are confidence scores which are in [0, 1], they cannot obey exponential distribution.
D.3 A CONCRETE CASE: UNIFORM DISTRIBUTION
As shown by Saremi & Srivastava 2020 (Remark 2.1), when the input dimension d is large, the Gaussian noise (0, d² La & Unif(a (d i.e., zo + is highly uniformly distributed on the (d 1)-sphere centered at zg. Motivated by this, we study the case where the confidence scores (2. c) ) also uniformly distributed.
Under this additional assumption, we can further make the certified robustness for the single model and both ensembles more concrete.
D.3.1 CERTIFIED ROBUSTNESS FOR SINGLE MODEL
Proposition D.2 (Certified Robustness for Single Model under Uniform Distribution). Let e be random variable supported on Rd. Let F be classification model, which is (c, >3, p)-single confident. Let wn E Ra be the input with ground-truth E [C]. Suppose f(20 + E) is uniformly distribuled in (a, b). We have
1/(11 + b- a
Pr(F(xo + E) y0) p cclip
where cip(=)==ax(min(( 1).
Proof of Proposition D.2
We consider the distribution of quantity Y = f(xo E) Aa
fx + y) Since the model F is (e, P). -iiigle confident, with probability 1 - Y < f(xo + c)go elC)uu f(xo E) At the same time, because f(xo + e) follows the distribution u([a, b)),
Y (1 + Aa) E)vo As
follows the distribution U[((1 + As)a - A3, (1 + Aa)b As))- Therefore,
As (1 (1+)a)a)
Pr(Y s 50) clip
(1 >b) a)
As the result,
Pr (Il2o + 6)yo
( -A3 -1(1+ Az)a
f(x0 + E) 50) S <p
max [C
((1 Az) a)
which is exactly
As (1 (1) Asta
1/(1 1/(1+
Pr (F(oo + E) = vo) 2 1 - clip
= =1 clip
(1+A))(0
b
D.3.2 CERTIFIED ROBUSTNESS FOR ENSEMBLES
Still, we define (e) and X2(E) according to Definitions D.2 and D.3 Under the uniform distribu- tion assumption, have the following lemma.
Lemma D.5 (Expectation and Variance of X, and X, under Uniform Distribution). Let X, and X. be defined by Definition and Definition D.. respectively. Assume that under the distribution of e,
29

---

Under review as a conference paper at ICLR 2021
the base models' confidence scores for true class (fi(2o + t) h are pairwise i..d and uniformly distributed in range (a, b]. We have
1
(E) 2 (1 x b) A Alwl,,,
Var (e (1
12
4
(x) (1 + x2) - 2\2,
Var = W+1
(6 (b-a)².
N +2 N N+1
Proof of Lemma D.3
We start from analyzing Xi. From the definition
xi(c) =- (1+ ((t))=(1+A)
Σ wjff(2v c)vo A1//w//1a
where (Ji(2o + te 1 are i.i.d. variables obeying uniform distribution ([ b)).
(E) = (1+ (1) x1)l(w(l
a+b
\1||w|11
/ (1+ \1) 2 (a A 11l11,
1
Var Xi(e) = (1+
Σ
w
(b - (b-a)²= - 12
(1 + A1) 1 a)?.
12
==1
Now analyze the expectation of X2. By the symmetry of uniform distribution, we know
E (2((E) (1 + X2) 2E (w + e) 2 = (1 + A2) + b) 2222
To reason about the variance, we need the following fact:
Fact D.I. Let X1, X2;-. .... Xn be uniformly distributed and independent random variables. Specifi-
cally, for each S i n, 2, u((a, b)). Then we have
2 1
Var
min xx
Var
max X3 ISiS"
+ 1 (b a)²
(b-a)²
ISi5n
n +1 1 nn+2
n2
Observing that each ii.d. fi(1o + c) is exactly identical to x; in Fact D.I we have
4
2
)
1
Var
max (xo + E) + min fi + e) (E[N]
(b-a)- a)2.
EE[M]
N
+
N +2
N N+1
Therefore,
Var 5
4
2
N N+1 -
1
(b ab-a)2
N+1
N N
Proof of Fact D.7 From symmetry of uniform distribution, we know Var (min <iss x.) Var (maxigign X;). So here we only consider Y = minigign Its CDF F and PDF f can be easily computed:
n f(w) F'()) (b 7)n F(y) = (minx; 2 2))= =1 1 11110 )
where y E (a, b).
(b a)n
Hence,
E = [ vf(v)dy= y(b 3)" + (n + 11 (b
8)
= a +
(b
30

---

Under review as a conference paper at ICLR 2021
[
(b
y)=
Y
J
ny 2
dy
(b
a)"
b 1
6
y
y
+
ydy
a
a
y/
6
2
y) n+1
y + /
(b y)
6
(6 a)n dy
b
71 + 1
(b - a)n
V/
2
(0 v) n+1
(b n)
b
YL +
(b a)
n (b a)
2
a²
(b aaaa +
(b a)².
n n+
(n + 1) + 2)
As the result, Var Y EY 2- (EE))²
(b a)² x+
n+1 n+2
Now, similarly, we use Lemma D. to derive the statistical robustness lower bound for WE and MME. omit the proofs since they are direct applications of Lemma D.5 Lemma D.I and
Lemma D.2
Theorem D.1 (Certified Robustness for WE under Uniform Distribution). Let MwE be a Weighted Ensemble defined over {file with weights {w:)). Let Dy Rd be the input with ground- truth label yo E [C]. Let E be random variable supported on Rdd. Under the distribution of e, IN suppose {f( t yo i==1 are i.i.d. and uniformly distributed in [a, b). The MWE is (e, 11,P)-WE
We have confident. Assume a+b > 144
d K2
Pr(Mwe(arg (2r + + =0)) 2
12
(34)
w
b
where
dw
K1
w
2'
1+A,
Theorem D.2 (Certified Robustness for MME under Uniform Distribution). Let MAME be a Max- Margin Ensemble over { Let To Rdd be the input with ground-truth label yo [C). Let e be random variable supported on IRd. Under the distribution of e, suppose +e) ji= are i.i.d.
and uniformly distributed in [a, b]. .MMME is (e, A2,22, ()-PP)MMMM -MEE confident. Assume 2td
1+22
We have
CN
Pr(MMME(20 + = =yo) 2 1 p-
(35)
2 2
1
b
where
CN
N+
N+2
N N+1
K₂ a+h
1+
D.3.3 COMPARISON
Now under the uniform distribution, we can also have the certified robustness comparison. Corollary D.I (Comparison of Certified Robustness under Uniform Distribution). Over base mod- els {f let MMМE be Max-Margin Ensemble, and MWE the Weighted Ensemble with weights {w:) Let Do E Rdd be the input with ground-truth label yo E [C]. Let be a random variable supported on Rd. Under the distribution of e, suppose { + e) J.N. are i.i.d. and uniformly distributed with mean μ. Suppose MWE (c, A1. p)- WE confident, and MAME is (c, X2, -MMM
confident. Assume P max
(T 1+27
When
(IN+
A < x5ل
N
+1-
-1
(36)
6N
MWE has higher certified robustness than MxME-
31

---

Under review as a conference paper at ICLR 2021
When
((** (N+1
-1
X1 X2
(
2
1
+
-1-11
-1
(37)
6
1 +
MMME has higher certified robustness than MWE.
When
N N 6
-2
(38)
p(
for any X1, MMME has higher or equal certified robustness than MWE.
Here, the certified robustness is given by Theorems D.1 and D.2
Proof of Corollary D.I First, we notice that a uniform distribution with mean jr can be any distri- bution U[[a, b)) where (a b)/2 μ.. We replace μ by (a + 6)/2.
Then (1) and (2) follow from Lemma D.4 D.4 similar to the proof of Corollary 2
(3) Since
N > 6 (1- p11 X5
N+2
-
+1
<1
1+ X5
N N+1 N V -
+2
11
1+ 1+1
+
<1,
the RHS of Equation (37 is smaller than O. Thus, for any Å1 since \1 > 0, the Equation satisfied. According (2), MMME has higher certified robustnesss than MWE.
17
is
Remark. Comparing to the general corollary (Corollary 2 under the uniform distribution, we have an additional finding that when N sufficiently large, we will always have higher certified robust- ness for Max-Margin Ensemble than Weighted Ensemble. This is due to the more efficient variance reduction of Max-Margin Ensemble than Weighted Ensemble. As shown in Lemma D.5 the quan- tity Var (E))(EX) for Weighted Ensemble is Q(1/N), while for Max-Margin Ensemble is O(1/N9). As the result, when N becomes larger, Max-Margin Ensemble has higher certified ro- bustness.
We use uniform assumption here give illustration in specific regime. Since the assumption may not hold exactly in practice, we think would be an interesting future direction to generalize the analysis other distributions such the Gaussian distribution that corresponds locally linear classifiers. The result from these distribution may be derived from their specific concentration bound for maximum/miniimmm i.i.d. random variables discussed at the end of Appendix D.2
D.4 NUMERICAL EXPERIMENTS
To validate and give more intuitive explanations for our theorems, we present some numerical ex- periments.
D.4.1 ENSEMBLE COMPARISON FROM NUMERICAL SAMPLING
As discussed in Section 3.2 X1 Ae reflects the transferability across base models. It is challenging to get enough amount of different ensembles of various transfcrability levels while keeping all other variables controlled. Therefore,
simulate the transferability of ensembles numerically by varying / (see the definitions of X and X2 in Definitions 6 and ?). and sampling the confidence scores (fi(wa + } and {max}e(C1:1# fi( + +) under determined A and X2. For each level of X1/X2, with the samples, compute the certified robust radius using randomized smooth- ing (Theorem B.J) and compare the radius difference of Weighted Ensemble and Margin En- semble. According to Corollary 2 in Section 3.2 should observe the tendency that along with
32

---

Under review as a conference paper at ICLR 2021
Certified Robustness Comparioon with
Cert Rebustness Comparson with
Certified Robusdmess Comparison with
afterencce contires (101L3
0.0
Sugres eectittnt
0.0
-6.2
-0.3
-0.4
-6.6
-0.6
NNE
MHE
(a) # of base models N
(b) of base models N 10
(c) # of base models N 20
Figure 2: Signed certified robust radius difference between MME and WE by \1/2 under different
numbers of base models N. Here we fix A2 to be 0.95 and uniformly sample Å E [0.8, 0.95). The confidence score for the true class on each base model is uniformly sampled from [a. bj. where is sampled from [0.3, 1.0) and is sampled from [a, 1.0) uniformly for each instance. Blue points correspond to the negative radius difference (i.e., WE has larger radius than MME) and Red points correspond to the positive radius difference (i.e., MME has larger radius than WF).
the increase of transferability \/ Max-Margin Ensemble would gradually hecome better than Weighted Ensemble.
Figure 2 verifies the trends: with the increase of Aι MME model tends to achieve higher certified radius than WE model. Moreover, we notice that under the same / with the larger number of base models N, the MME tends to be relatively better compared with WE. This is because we sample the confidence score uniformly and under the uniform distribution, MME tends to be better than WE when the number of base models N becomes large, according to Corollary D.1.
The concrete number settings of X1, X2, and the sampling interval of confidence scores are entailed in the caption of Figure 2
D.4.2 ENSEMBLE COMPARISON FROM CERTIFIED ROBUSTNESS PLOTTING
In Corollary D.I we derive the concrete certified robustness for both ensembles and the single model under i.i.d. and uniform distribution assumption. In fact, from the corollary, we can directly compute the certified robust radius without sampling, as long as we assume the added noise is Gaussian. In Figure we plot out such certified robust radius for the single model, the WE, and the MME.
Concretely, the figure, we assume that the true class confidence score for each base model is i..d. and uniformly distributed in (a, b). The Weighted Ensemble is (c, A1 0.01) -EE confident; the Max-Margin Ensemble is (E, A2, -MME confident; and the single model is (c, 0.01)-MMME confident. We guarantee that a Aa >2 to simulate the scenario that ensembles are based on the same set of base models to make a fair comparison. We directly apply the results from our analysis (Theorem D.I Theorem D.2 Proposition D.2p to get the statistical robustness for single model and both ensembles. Then, we leverage Theorem B. to get the certified robust radius (with 1.0, N = 100000 and failing probability a 0.001 which are aligned with realistic setting). The zaaxis is the number of base models N and the y-axis is the certified robustness. We note that N not applicable the single model, so we plot the single model's curve by a horizontal red dashed line.
From the figure, we observe that when the number of base models N becomes larger, both ensembles perform much better than the single model. We remark that when N is small, the ensembles have 0 certified robustness mainly because our theoretical bounds for ensembles are not tight enough with the small N. Furthermore, we observe that the Max-Margin Ensemble gradually surpasses Weighted Ensemble when is large, which conforms to our Corollary D.I Note that the left sub-figure has smaller transferability \ and the right subfigure has larger transferability X1 A2, it again conforms to our Corollary [ and discussion in Section 3.2 that in the left subfigure the Weighted Ensemble is relatively more robust than the Max-Margin Ensemble.
33

---

Under review as a conference paper at ICLR 2021
Certifie Comparienn
0.2, 0.33, 0.29, =
(a 0.3, 0.4, 0.48, A; 0.49)
Rabushress
Centifed Rubustrees
0.2
WE
0.2
WE
NME
MME
Single
Single
0.0
0.0
15
Base Moders (N)
of Baso Modelss (N)
(a) [a, 0.31.
[0.2, 0.3).Ax:
0.29, A2
(b) [a. b]
[0.3, 0.4],
0.48,
0.30.
0.50, Aa 0.49.
Figure 3: Comparison of certified robustness (in terms of certified robust radius) of Max-Margin Ensemble, Weighted Ensemble, and single model under concrete numerical settings. The y-axis the certified robustness and the z-axis is the number of base models. The confidence score for the true class is uniformly distributed in [a, b]. The Weighted Ensemble (shown by blue line) is (c, \1 0-O confident; the Max-Margin Ensemble (shown by green line) is (c, 22, 0.01) confident; and the single model (shown by red line) is (c, A3, 0.01) confident.
D.4.3 ENSEMBLE COMPARISON FROM REALISTIC DATA
We study the correlation between transferability \ and whether Weighted Ensemble or Max- Margin Ensemble is more certifiably robust using realistic data.
By varying the parammerrsssers of DRT, we find out a setting where over the same set of base models, Weighted Ensemble and Max-Margin Ensemble have similar certified robustness, i.c., for about half of the test set samples, WE more robust; for another half, MME is more robust. We collect 1, 000 test samples in total. Then, for each test sample, compute the transferability \1/ A2 and whether WE or MME has the higher certified robust radius. We remark that a and X2 difficult be practically estimated use the average confidence portion the proxy:
For WE,
max B, E|C);y, #yo E wiFi + E)
A E.
ΣN w1(1 fe + 6)
For MME,
max ee fo (x0 + E)y,
Aa E, max iE[N]
(1 Si(wro + ))
Now study the correlation between
:== RHS of Equation and Y = [MME has higher certified robustness].
To do so, we draw the ROC curve where the threshold on X does binary classification on Y. The curve and the AUC score is shown in Figure From the ROC curve, we find that and Y apparently positively correlated since AUC = 0.66 > 0.5, which again verifies Corollary 2 We re- mark that besides other factors such as non-symmetric non-i.i.d. confidence score distribution may also play role.
34

---

Under review as a conference paper at ICLR 2021
Thos fostro Rdto
09-
0.0
0.0
9.2
0/1
D4
0.3
1.0
Postiive Paae
Figure ROC curve of the [MEE has higher certified robustness] classification task with the threshold variable X.
E EXPERIMENT DETAILS
Evaluation metric: We use the certified test set accuracy at each radius r as our evaluation metric, which defined as the fraction of the set samples that the smoothed classifier can certify the robustness within the L2 ball of radius r. Since the computation of the accurate value of this metric intractable, we report the approximate certified test accuracy (Cohen al. 2019) sampled through the Monte Carlo procedure. For each sample, the robustness certification holds with probability at least 1 a. Following the literature, we choose a 0.001, no 100 for Monte Carlo sampling during prediction phase, and 100, 000 for Monte Carlo sampling during certification phase.
E.I MNIST
Baseline models' hyper-parameter configuration: We choose the number of noise samples per instance m and Gaussian smoothing parameter (0.25, 0.5, 1.0} for all the training methods. For SmoothAdv, without pretraining and unlabelled data augmentation. We reproduced similar results to their paper by using their open-sourced code
consider the attack to be 10-step Le PGD attack with perturbation scale d 1.0
We use LeNet architecture and trained each base model for 90 epochs. For the training optimizer,
Training details:
the CGD-momentum with the initial learning rate 0.01. The learning rate is decayed for every 30-epochs with decay ratio y = 0.1 and the batch size equals to 256. For DRT experiments, we start our training with the small learning rate a base models for another 90 epochs. During the training, we find too large regularization weights may cause the model's training collapse on MNIST. We turn to use small DRT hyper-parametens P1,P2 P2 and report the one with the best certified accuracy on each radius r.
10-4 and finetune the
Certified accuracy curve: Figure 6 and Figure show the certified accuracy curve with different base model type and smoothing parameter a among the range of the radius r. We can notice that while simply applying MME or WE can improve the certified accuracy slightly, DRT could help boost the certified accuracy on each radius with significant scale.
DRT hyper-parameters: We investigate the DRT hyper-parameteed A1 (0.1, 0.5, 1.0) and P2 E (0.5, 1.0, 2.0, 5.0} corresponding to different smoothing parameter a {0.25, 0.5. 1.0). Here we put the detailed results for every saper-parameter setting Tables 4 to 6 and bold the numbers with the highest certified accuracy on each radius among all the tables with different r's. From the experiments, we found that the GD loss's weight Pi can have the major influence on the ensemble model's functionality: if we choose larger P1, the model will achieve slightly worse certified accuracy on small radius r, but better certified accuracy on large r. We cannot choose too large #1 on small cases (e.g., 0.25). Otherwise, the training procedure will collapse. Here show the DRT-based model's 's approximate certified accuracy with different P1 in Figure 5
httpp:: www.ttthhhhh.... Hadi man hmaa:/mmoothhhing-aaeerraaaa
35

---

Under review as a conference paper at ICLR 2021
DRT-(P1: p2) model's certified accuracy under different radius on MNIST dataset. Smoothing parameter o = 0.25.
Table 4:
Radius
0.00
0.25
0.50
0.75
Gaussian Cohen al. 2019)
99.1
97.9
96.6
93.0
AmoothAdv (alman et al.
2019)
99.1
98.4
97.0
96.3
MME (Gaussian)
99.2
98.4
96.8
93.6
0.1
0.2
99.4
98.3
97.5
95.1
DRT + MME (Gaussian)
0.1
0.5
99.5
98.6
97.1
94.8
0.2
0.5
99.5
98.5
97.4
95.1
MME (SmoothAdv)
99.2
98.2
97.3
96.4
0.1
0.2
99.1
98.4
97.5
96.4
DRT MME (SmoothAdv)
0.1
0.5
99.1
98.3
97.6
96.7
0.2
0.5
99.1
98.4
97.5
96.6
WE (Gaussian)
99.2
98.4
96.9
93.7
0.1
0.2
99.5
98.4
97.3
95.1
DRT + WE (Gaussian)
0.1
0.5
99.5
98.6
97.1
94.9
0.2
0.5
99.5
98.5
97.3
95.3
WE (SmoothAdv)
99.2
98.2
97.4
96.4
0.1
0.2
99.1
98.4
97.5
96.5
DRT + WE (SmoothAdv)
0.1
0.5
99.1
98.2
97.6
96.6
0.2
0.5
99.0
98.4
97.5
96.7
Alternatively, we found that the CM loss's weight (22 can have positive influence on model's perfor- mance: the larger P2 we choose, the better certified accuracy we can get. Choosing large /2 does harm model's functionality too much, but the improvement we received will become marginal. For MNIST, (o, P2) (0.25, 0.1, 0.2), (0.5, 0.5, 5.0), (1.0, 1.0, 5.0) are good combinations.
We regard the execution time per mini-batch as our efficiency criterion. For MNIST with batch size equals to 256, DRT with the Gaussian smoothing base model only requires 1.04s to finish one mini- mini-batch training to achieve the comparable results to the SmoothAdy method which requires 1.86s. Moreover, DRT with the SmoothAdv base model requires 2.52s per training batch but achieves much better results. The evaluation is on single NVIDIA GeForce GTX 1080 Ti GPU.
Efficiency Analysis:
(SmoothAdr, P: -.2)
0.9
DRT HME (Sm.oohhAdr, -
Certified Accuracy
DRT HIEE [Sm.othhAdr, ji =.0)
6.8
Certified
DRT MME (SmoothAdv, 0,0)
DRT MME (SmoothAdy, 0.1)
(SmoothAdy, A; 0.22)
DRT MME (SmoothAdv, 0.3)
0,5
(SmoothAdv, P1 0.55
2,0
0.5
(b) 1.0
Figure 5: Effect of Comparison of approximate certified accuracy of DRT models on MNIST with different GD Loss's weight P1.
E.2 CIFAR-10
configuration: We choose the number noise samples per instance and Gaussian smoothing parameter (0.25, 0.5, 1.0) for all the training methods.
Baseline models'
36

---

Under review as a conference paper at ICLR 2021
DRT-(P1: p2) model's certified accuracy under different radius on MNIST dataset. Smoothing parameter o = 0.50.
Table 5:
Radius r
P1
P2
0.00
0.25
0.50
0.75
1.00
1.25
1.50
1.75
Gaussain (Cohen et al. 2019
99.0
97.7
96.4
94.7
90.0
83.0
68.2
43.5
AmoothAdv (Salman el a.. 2019
98.6
98.0
97.0
95.4
93.0
87.7
80.2
66.3
MME (Gaussian)
99.0
97.7
96.8
94.9
90.5
84.3
69.8
48.5
0.2
2.0
99.1
98.4
97.2
95.2
92.6
86.5
74,3
54.1
0.2
5.0
99.1
98.6
97.1
95.3
92.6
86.2
74.0
54.3
DRT MME (Gaussian)
0.5
2.0
99.2
98.3
97.4
95.5
92.1
86.4
74.7
55.6
0.5
5.0
99.0
98.2
97.3
95.1
91.6
84.8
73.7
52.4
5.0
97.2
95.2
74.4
54.4
MME (SmoothAdv)
98.6
98.0
97.0
95.5
93.2
88.1
80.6
67.8
0.1
0.5
98.4
97.8
97.0
95.5
92.7
87.7
80.9
67.9
0.1
1.0
98.4
97.9
97.0
95.5
92.9
88.1
80.8
67.2
0.1
5.0
98.5
98.2
97.0
95.4
93.1
88.4
81.2
68.3
98.4
97.7
97.2
95.3
92.3
87.7
79.3
68.4
0.2
2.0
98.4
97.6
97.1
95.3
92.3
87.8
80.2
67.7
DRT MME (SmoothAdv)
0.2
5.0
98.4
97.8
97.1
95.2
93.0
87.9
80.3
68.3
0.3
5.0
98.4
97.5
97.1
95.0
92.4
87.7
79.7
68.3
0.5
2.0
98.5
97.3
96.6
94.3
91.6
86.7
79.5
68.6
5.0
98.4
96.9
94.6
92.0
80.1
67.8
1.0
5.0
98.2
97.3
96.8
94.5
91.9
87.4
80.0
67.6
WE (Gaussian)
99.0
97.8
96.8
94.9
90.6
84.5
70.4
48.2
0.2
2.0
99.2
98.4
97.2
95.2
92.5
86.2
74.3
53.5
5.0
97.1
95.3
74.2
54.4
DRT WE (Gaussian)
0.5
2.0
99.2
98.3
97.4
95.6
92.1
86.5
74.7
55.3
0.5
5.0
99.1
98.2
97.1
95.1
91.7
85.4
73.5
51.0
1.0
5.0
99.1
98.2
97.2
95.2
92.2
85.9
75.1
55.3
WE (SmoothAdy)
98.7
98.0
97.0
95.5
93.4
88.2
81.1
67.9
0.1
98.4
97.8
97.0
95.5
92.7
87.8
80.6
68.1
0.1
1.0
98.5
97.9
97.0
95.5
93.1
88.0
81.2
67.7
0.1
5.0
98.5
98.2
97.0
95.4
93.3
88.5
81.4
68.6
0.2
0.5
98.4
97.7
97.2
95.4
92.3
87.6
79.7
68.0
0.2
2.0
98.4
97.6
97.1
95.3
92.3
87.8
80.6
68.1
DRT + WE (SmoothAdv)
98.4
97.9
97.1
95.1
88.2
80.4
69.1
0.3
5.0
98.4
97.5
97.1
95.0
92.4
87.9
79.9
69.3
0.5
2.0
98.4
97.3
96.6
94.3
91.8
86.7
79.6
68.1
0.5
5.0
98.4
97.5
96.9
94.7
92.0
87.7
79.7
67.7
1.0
5.0
98.4
97.7
97.0
95.2
92.6
88.4
81.1
68.2
For SmoothAdy, we consider the attack to be 10-step L2 PGD attack with perturbation scale d = 1.0 without pretraining and unlabelled data augmentation. We also reproduced the similar results mentioned in baseline's 's papers.
We use ResNet-110 architecture for each base model and train them for 150 epochs. During the training, We utilize the SGD-momentum with the initial learning rate a = 0.1, which is decayed for every 50-epochs with ratio y 0.1. For DRT experiments, we start the training with the learning rate = 5 x 10- and finetune our base models for another 150 epochs.
Training details:
Certified accuracy curve: Figure g and Figure 9 show the certified accuracy curve with different
base model type and smoothing parameter among the range of the radius r. We can see the same trends: Applying the MME/WE mechanism will give slight improvement and DRT can help make this improvement to be significant.
DRT syper-parameter: We studied the DRT hyper-parameter E {0.1 0.2, 1.0, 1.5) and P2 E {0.5, 2.0, 5.0} corresponding to different {0.25, 0.5, 1.0) and put the detailed results in Tables to g We bold the numbers with the highest certified accuracy on each radìus r among all the tables with different o's The results show the similar conclusion about the choosing of pi and P2. (a, Pl, P1. E {00.25, 0.1, 0.5), (0.5, 1.0, 5.0), (1.0, 1.5, 3.0)) could be the good choices on CIFAR-11 10 dataset.
37

---

Under review as a conference paper at ICLR 2021
Table 6: DRT-(P1: P2) model's certified accuracy under different radius on MNIST dataset. Smoothing parameter o = 1.00.
Radius
P1
0.00
0.25
0.50
0.75
1.00
1.25
1.50
1.75
2.00
2.25
2.50
Gaussain Smoothing
96.5
94.3
91.1
87.0
80.2
71.8
60.1
46.6
33.0
20.5
11.5
SmoothAdv
95.3
93.5
89.3
85.6
80.4
72.8
63.9
54.6
43.2
34.3
24.0
MME (Guussian)
96.4
94.8
91.3
87.7
80.8
73.5
61.0
48.8
34.7
23.4
12.7
93.9
86.3
80.7
63.0
52.0
26.9
DRT MME (Gaussian)
5.0
95.8
94.1
90.0
86.6
80.4
72.9
62.4
51.3
40.0
27.8
16.5
1.0
5.0
95.3
93.1
89.7
85.8
80.0
72.7
62.9
52.0
39.8
28.5
17.6
MME (SmoothAdv)
95.4
93,4
89.3
86.1
80.7
73,1
65.0
55.0
44.8
35.0
25.2
0.2
2,0
94.1
91.9
88.6
84.5
79.4
72.4
63.4
54.0
45.0
36.6
27.3
94.1
91.6
88.9
84.4
79.3
72.3
63.2
54.2
46.1
36.9
28.5
DRT MME (SmoothAdv)
91.3
87.7
77.3
71.2
62.2
53.3
45.5
37.0
0,5
5.0
92.5
91.2
88.0
83.5
78.5
71.2
62.2
53.8
45.2
37.7
29.2
1.0
5.0
92.1
90.0
86.3
81.3
76.2
69.4
61.1
54.0
46.4
38.6
31.1
WB (Gaussian)
96.3
94,9
91.3
87.7
80.7
73.55
61.1
49.0
35.2
23.7
12.9
2.0
93.9
90.2
86.3
80.7
63.2
38.6
27.0
WE MME (Gaussian)
5.0
94.1
80.4
62.3
51.7
39.8
27.5
16.4
1.0
5.0
95.4
93.1
89.7
85.8
80.0
72.7
62.9
52.1
39.9
28.5
17.8
WE (SmoothAdv)
95.2
93.4
89.4
86.2
80.8
73.3
64.8
35.1
44.7
33.2
24.9
0.2
2.0
94.2
91.9
88.6
84.5
79.6
72.5
63.7
53.9
44.9
36.4
27.3
94.2
91.6
88.9
84.4
79.3
72.5
63.3
54.3
45.9
36.9
28.7
DRT MME (SmoothAdv)
2.0
92.6
91.3
87.7
83.1
77.5
71.1
62.4
53.3
45.3
36.7
0.5
5.0
92.5
91.2
88.0
83.4
78.5
71.1
62.3
53.7
45.3
37.8
29.5
1.0
5.0
92.1
90.0
86.4
81.4
76.3
69.7
61.1
54.0
46.4
38.4
31.0
Table 7: DRT-(P1, P2) model's certified accuracy under different radius on CIFAR-10 dataset. Smoothing parameter 0.25.
Radius
0.00
0.25
0.50
0.75
Gaussain Smoothing
78.9
64.4
47.4
30.6
SmoothAdy
68.9
61.0
54.4
45.7
MME (Gaussian)
80.8
68.2
53.4
37.4
0.1
0.5
81.4
70.4
57.6
43.4
0.2
0.5
78.8
69.2
57.8
43.8
DRT MME (Gaussian)
0.5
2.0
73.3
61.7
51.0
39.3
0.5
5.0
66.2
57.1
46.2
34.4
MME (SmoothAdv)
71.4
64.5
57.6
48.4
0.1
0.5
72.6
67.2
60.2
50.3
DRT MME (SmoothAdv)
0.2
0.5
71.8
66.5
59.3
50.4
0.5
0.5
68.2
64.3
58.2
48.9
WE (Gaussian)
80.7
68.3
53.6
37.5
0.1
0.5
81.5
70.4
57.7
43.4
0.2
0.5
78.8
69.3
57.9
44.0
DRT + WE (Gaussian)
0.5
2.0
73.4
61.7
51.0
39.2
0.5
5.0
66.2
57.1
46.1
34.5
WE (SmoothAdv)
71.8
64.6
57.8
48.5
0.1
0.5
72.6
67.0
60.2
50.3
DRT + WE (SmoothAdv)
0.2
0.5
71.9
66.5
59.4
50.5
0.5
0.5
68.2
64.3
58.4
49.1
Efficiency Analysis: We also use the execution time per mini-batch efficiency criterion. For CIFAR-10 with batch size equals to 256, DRT with the Gaussian smoothing base model requires 3.82s to finish one mini-bate mini-batch training to achieve the competitive results to 10-step PGD attack based SmoothAdv method which requires 6.39s. All the models are trained in parallel on NVIDIA GeForce GTX 1080 Ti GPUs.
38

---

Under review as a conference paper at ICLR 2021
Table 8: DRT-(P1, p2) model's certified accuracy under different radius on CIFAR-10 dataset. Smoothing parameter o = 0.50.
Radius
P1
P2
0.00
0.25
0.50
0.75
1.00
1.25
1.50
1.75
Gaussain Smoothing
68.2
57.1
44.9
33.7
23.1
16.3
10.0
5.4
SmoothAdy
60.6
54.2
47.9
41.2
34.8
28.5
21.9
17.1
MME (Gaussian)
69.5
59.6
47.3
38.4
29.0
19.6
13.3
7.6
0.2
2.0
69.7
61.0
50.9
40.3
30.8
22.5
15.8
10.0
0.2
5.0
68.0
59.9
50.0
40.8
30.1
22.1
15.2
9.6
0.5
2.0
67.8
58.5
49.0
39.9
31.6
23.4
16.1
10.2
DRT + MME (Gaussian)
0.5
5.0
65.5
58.4
49.0
40.1
31.2
23.6
16.5
10.2
1.0
2.0
64.5
55.8
47.5
39.4
31.1
23.6
9.3
1.0
5.0
62.2
46.5
38.8
29.7
22.8
16.6
11.0
MME (SmoothAdv)
61.0
54.8
48.7
42.2
36.2
29.8
23.9
19.1
0.2
5.0
62.2
56.4
50.3
43.4
37.5
26.7
24.6
19.4
DRT MME (SmoothAdy)
0.5
5.0
61.9
56.2
50.3
43.5
37.6
31.8
24.8
19.6
1.0
5.0
61.4
55.9
50.0
43.2
37.4
32.0
19.9
WE (Gaussian)
69.4
59.7
47.5
38.4
29.2
19.7
13.3
7.5
0.2
2.0
69.7
61.2
50.8
40.2
30.8
22.4
15.9
10.0
0.2
5.0
68.0
59.9
50.1
40.8
30.1
22.1
15.4
9.7
2.0
67.8
49.2
39.8
31.7
23.5
10.4
DRT + WE (Gaussian)
0.5
5.0
65.5
58.4
49.1
40.3
31.3
24.2
16.4
10.3
1,0
2.0
64.6
55.9
47.5
39.6
31.0
24.0
14,8
9.4
1.0
5.0
62.3
54.2
46.6
38.8
29.8
22.9
16.6
10.9
WE (SmoothAdv)
61.1
54.8
48.8
42.3
36.2
29.6
24.2
19.0
0.2
5.0
62.2
56.3
50.3
43.4
37.5
26.9
24.7
19.3
DRT WE (SmoothAdv)
0.5
5.0
61.9
56.2
50.2
43,4
37.9
31.8
25.0
19.6
1.0
5.0
61.5
56.0
50.1
43.3
37.5
32.2
25.6
19.9
Table 9: DRT-(P1, P2) model's certified accuracy under different radius CIFAR-10 dataset. Smoothing parameter o = 1.00.
Radius
P
P2
0.00
0.25
0.50
0.75
1.00
1.25
1.50
1.75
2.00
Gaussain Smoothing
48.9
42.7
35.4
28.7
22.8
18.3
13.6
10.5
7.3
SmoothAdy
47.8
43.3
39.5
34.6
30.3
21.2
18.2
15.7
MME (Gaussian)
50.2
44.0
37.5
30.9
24.1
19.3
15.6
11.6
8,8
0.5
5.0
49.4
44.2
37.8
31.6
25.4
22.6
18.2
14.4
12.4
DRT MME (Gaussian)
1.0
5.0
49.8
44.4
39.0
31.6
25.6
22.6
18.2
15.0
12.0
1.5
5.0
48.0
42.4
36.4
30.4
26.2
22.0
18.4
15.4
12.8
MME (SmoothAdv)
43.7
40.1
35.4
31.3
22.6
19.5
16.2
0.2
5.0
48.2
43.9
40.1
35.4
31.5
26.7
22.9
19.8
16.8
DRT + MME (SmoothAdv)
0.5
5.0
48.1
43.8
40.3
35.7
31.8
26.9
23.1
20.1
17.5
1.0
5.0
47.9
43.6
39.8
35.6
31.7
26.9
23.2
20.2
17.6
1.5
5.0
47.8
43.4
39.5
35.4
31.6
26.7
23.1
20.4
18.1
WT (Gaussian)
50.4
44.1
37.5
30.9
24.2
19.2
15.9
11.8
8.9
5.0
49.5
44.3
37.8
31.8
25.6
18.2
14.4
12.3
DRT + WE (Gaussian)
1.0
5.0
49.8
44.4
39.1
31.7
25.6
22.8
18.4
15.1
12.1
1.5
5.0
48.2
42.5
36.6
30.4
26.1
22.1
18.2
15.7
12.6
WE (SmoothAdv)
48.2
43.7
40.2
35.4
31.5
26.2
22.7
19.6
16.0
0.2
5.0
48.2
43.8
40.2
35.3
31.6
26.8
23.0
19.9
16.7
0.5
5.0
48.2
43.8
40.5
31.9
26.8
23.3
20.2
17.5
DRT + WE (SmoothAdv)
1.0
5.0
47.8
43.6
39.9
35.5
31.7
26.9
23.3
20.1
17.5
1.5
5.0
47.8
43.4
39.6
35.4
31.4
26.7
23.0
20.4
18.0
E.3 IMAGENET
For ImageNet, we utilize ResNet-50 architecture and train each base model for 90 epochs using the SGD-momentum optimizer. The initial learning rate = 0.1. The learning rate is decayed for every 30-epochs with decay ratio y = 0.1. We tried different Gaussian smoothing parameter {0.50, 1.00). and consider the best models. We explored the DRT hyper-parameter p1 E {0.5, 1.0, 1.5), P2 {1.0, 2.0. in our experiments and started with the learning rate a 5 10-3 during the DRT. Table 10 shows the
configuration for different in the bascline
39

---

Under review as a conference paper at ICLR 2021
Geaadaa
DRT PINE (Oaro
Gaussian
Gaussian
MME (Gaussian)
MME (Gaussian)
Curtifer
DRT-MME (Gaussian)
DRT MME (Gaussian)
CH
(Gaussian)
(Gausslan)
Radit
0.25
0.50
(c) 1.00
Figure 6: Comparison of approximate certified accuracy among different Gaussian-smoothingg based methods with various smoothing parameter a E {0.25, 0.50, 1.00} on MNIST.
Sewrtthher
HINE (Sevethann
WE I5marrMsnn (Dreethaad))
Smoothldy
SmoothAdv
MME (SmoothAdv)
MME (SmoothAdv)
DAT-MMC MME (5moothAdv)
DRT MME (SmoothAdv)
mmooohhdv)
(SmoothAdr)
Aadic
Sadie
0.25
(b) 0.50
1.00
Figure 7: Comparison of approximate certified accuracy among different SmoothAdv based meth- ods with various smoothing parameter (0.25, 0.50, 1.00] on MNIST.
Guarscinn NIRE ICassalnt
Gaussian
MIE (Gausslan)
DRT-MME (Gausstan)
DVET' WE (Gausllan)
DRT-WE (Gaussian)
(Cousstan)
Gaussian
Centifec
MME (Gaussian)
DAT- MME (Gaussian)
(Gausslan)
3adic
0 0.25
(b) 0.50
1.00
Figure 8: Comparison of approximate certified accuracy among different Gaussian based methods with various smoothing parameter a E (0.25, 1.00) on CIFAR-10.
Smeothadv (SmsathMdr) WE (SimatthAd))
SmoothAdv
HHE (SmeathAde)
DRT MME (SmoothAAu)
DETTWE (5mcothAdv)
(SmoothAAv)
DRT WE (SmeothAdv)
Smoothidy
Curtife
MME (SmocthAdv)
DRT-MMM MME (SmoothAdv)
mmoothAdv)
(SmoothAdv)
Sadie
0.25
(b)
0.50
1.00
Figure 9: Comparison of approximate certified accuracy among different SmoothAdv based meth- ods with various smoothing parameter (0.25, 0.50, 1.00) on CIFAR-10.
results. We observe the same trends that MME or WE can improve the certified robustness on each radius Due to the computation cost of training the DRT ensemble model on ImageNet,
40

---

Under review as a conference paper at ICLR 2021
Table 10: The certified accuracy under different radius r for ImageNet dataset.
Radius
0.00
0.50
1.00
1.50
2.00
2.50
3.00
Gaussian (Cohen ct al. 2019
57
37
29
19
12
SmoothAdv (Salman et al. 2019
54
49
43
37
27
25
20
MME (Gaussian)
58
47
38
31
21
16
14
DRT + MME (Gaussian)
42
34
24
18
MME (SmoothAdv)
55
50
44
38
27
26
21
DRT + MME (SmoothAdv)
42
37
29
22
WE (Gaussian)
58
47
38
31
21
17
14
DRT + WE (Gaussian)
52
46
41
33
24
19
18
WE (SmoothAdv)
55
50
44
38
28
26
22
DRT + WE (SmoothAdv)
49
44
42
36
29
27
22
Table 11: Certified accuracy comparison with other baseline methods for MNIST dataset.
Radius
0.50
1.75
2.25
2.50
Gaussian Cohen
2019
97.9
96.6
90.0
83.0
68.2
46.6
33.0
20.5
11.5
SmoothAdv
Salman al 2019
99.1
98.4
97.0
96.3
93.0
87.7
80.2
66.3
43.2
34.3
24.0
MACER Zhai ct al 2019
99.2
98.5
97.4
94.6
90.2
83.5
72.4
54.4
36.6
26.4
16.5
Stability (L ct 2019
99.3
98.6
97.1
93.8
90.7
83.2
69.2
46.8
33.1
20.0
11.2
Diversity Regulanzed Tramiin
99.5
97.6
93.4
88.5
83.3
69.6
39.4
33.5
Table 12: Certified accuracy comparison with other baseline methods for CIFAR-10 dataset.
Radius
0.00
0.25
0.50
0.75
1.00
1.25
1.50
1.75
2.00
Gaussian
(Cohen
2019
78.9
64.4
47.4
33.7
18.3
13.6
10.5
SmoothAdv
Salman
2019
68.9
61.0
54.4
45.7
34.8
28.5
21.9
18.2
15.7
MACER
Zhai
2019
79.5
68.8
55.6
42.3
35.0
27.5
23.4
20.4
17.5
Stability
Li el al.
2019
72.4
58.2
43.4
27.5
23.9
16.0
15.6
11.4
7.8
SWEEN
Liu al.
2020
84.2
72.0
60.3
46.6
37.2
29.2
24.6
22.0
19.1
Diversity- Regulanzed Traming
81.5
70.4
60.2
50.5
39,5
36.0
30.4
24.1
20.3
only try one sub-optimal hyper-parameter setting for DRT and the result shows that DRT cannot bring more improvements on MME/WE results. We plan to select more suitable hyper-parameters for DRT obtain better results the ImageNet task.
E.4 COMPARISON WITH OTHER BASELINES
We compare our Aversity-Regullrizee Training with other baselines on MNIST and CIFAR-10 dataset. Baselines are: (I) Gaussian smoothing (Cohen et 2019): Training smoothed classifier by applying Gaussian augmentation. (2) SmoothAdv (Salman al.) 2019): Integrating adversarial training on the soft approximation. (3) MACER (Zhai et al. 2019): Adding the regularization term maximize the certified radius R (PA PB) on training instances.
(4) Stability (Li et al., 2019): Adding the adversarial perturbation by maintaining the Stability on classification results. (5) SWEEN (Liu et al., 2020p: Building the weighted ensemble model by composing the base models of different architectures.
For all baselines, we choose the best certified accuracy for each radius reported in their pa- pers. We do not consider the model trained by additional (unlabeled) data. Results are shown in Table II and Table 12] We can that we achieve the best certified accuracy every on MNIST dataset and achieve comparable or better results compared to the best certified accuracy on CIFAR- 10 dataset.
41

---

Under review as a conference paper at ICLR 2021
Table 13: Certified accuracy achieved by training with GD Loss (GDL) Confidence Margin Loss
(CML) for CIFAR-10 10 dataset.
Radius
0.00
0.25
0.50
0.75
1.00
1.25
1.50
1.75
2,00
MME (Gaussian)
80.8
68.2
53.4
38.4
29.0
19.6
15.6
11.6
8.8
GDL MME (Gaussian)
81.0
69.0
55.6
41.9
30.4
24.8
20.1
16.9
14.7
CMT MMF (Gaussian)
81.2
69.4
54.4
39.6
29.2
21.6
17.0
13.1
12.8
DRT + MME (Gaussian)
81.4
70.4
57.8
43.8
31.6
26.2
22.4
18.8
16.6
E.5 THE EFFECTS OF GD LOSS AND CONFIDENCE MARGIN LOSS
We studied the effects of GD Loss and Confidence Margin Loss separately by setting Pi = 0 or P2 but tuning another parameter only. We did this ablation study on CIFAR-I0 dataset with ensemble of Gaussian-smoothed base models and the results are shown in Table
We observed that both GD Loss (GDL) and Confidence Margin Loss (CML) could have positive effects on improving the certified accuracy while GDL, plays a major role in the larger radius. While combining these regularization loss together as our DRT loss, the ensemble model could achieve the best certified accuracy among all the radii.
42


Reviews:
[{"review_id": "wW8ljYGuNtD", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "Certified robustness approaches have been studied for single models based on interval propagation as well as randomized smoothing. The use of ensembles for empirical robustness has also been studied in the literature. This paper attempts to theoretically study the certifiable defense achieved by ensembles. The paper analyzes the standard Weighted Ensemble (WE) and MaxMargin Ensemble (MME) protocols, and proves the necessary and sufficient conditions for robustness under smoothness assumptions. The key idea is to show and utilize the diversification of gradients and large confidence margins. \n\nPros:\n\n+ The paper addresses an important challenge of adversarial robustness via ensembles and attempts to develop theoretical bounds for these defenses. \n\nCons:\n\n- Some theoretical discussion is rather straight-forward formulation of consequences of the definitions of robustness and ensemble methods. Proposition 1 and Theorem 1 follow directly from the definition of WE and MME, and r-robustness. \n\n- There are several notation lapses which make the paper difficult to read. In definition 2, it appears the intent is to take the partial gradient of the model at two different points x and y and then bound the ration of the difference of the gradients and the distance between two points (which would be the curvature). x,y are being used as values and the variable. The boldface font is not used consistently.  Another example is the missing relation between r and epsilon (which is described in the appendix). These make simple results difficult to parse, and negatively effect the readability of the paper and obscure the identification of novelty. \n\n- For Theorem 2, let us set N = 1 (that is the degenerate case when the ensemble is a single model), we see that the rate of change of difference between the top prediction and other predictions are now bounded by a linear spread of the difference divided by the robustness radius r and then we add or subtract (depending on sufficiency/necessity) the impact of curvature. Rearranging the terms so that first and third are on the same side, the theorem will read:\nr ( gradient term for prediction difference ) +/-  r^2 ( curvature term for prediction difference ) <=  prediction difference.\nIsn't this just a Taylor series approximation of the prediction difference using bounds on the curvature term (assumed as part of the definition)? \nNow, if we bring back any arbitrary N, the same would be applicable by the definition of how decisions are made by WE (the \"prediction difference\" term is now changed). \nTheorem 3 terms can be similarly rearranged to make the statement more obvious. Is the reviewer missing some non-obvious observation or challenge in proving Theorem 2/3?\n\n- Despite several other papers also using the general term of \"certified robustness\", it is important to note that this robustness is against a rather benign perturbation model. Typical perturbations (in particular adversarial attacks or other natural perturbations such as fog, rain for vision) do not fall into this class. But the reviewer is not concerned with this aspect heavily given the prevalence of the rather generic name of \"certified robustness\" for such approaches. \n\n- The empirical enforcement of diversity in ensembles has been studied in literature such as Pang et al 2019. https://arxiv.org/abs/1901.09981 uses cosine similarity.  Experimental evaluation with these methods is crucial to understand the value of the proposed approach. The current evaluation is very limited. \n\nQuestions and suggestions to the authors:\n\n1. It might be a good idea to bring the relationship between r and epsilon in the main text from the appendix. r-robustness is the fundamental definition and in its current presentation r does not occur anywhere. \n\n2. Could you help understand the concern in Weakness bit 3? This will help the reviewer better appreciate the theoretical novelty of the paper. Currently, the theoretical statements appear to make obvious statements once we get through the rather clunky notation and presentation choices. \n\n3. Why is cosine used for diversity? There are several ways to enforce diversity. Was cosine selected arbitrarily or is it motivated by some theoretical insight? \n\nThe paper addresses an important challenge of mathematically well-motivated defenses against perturbations. In its current form, the paper appears to formulate rather simplistic observations as theoretical results with a rather dense presentation. The empirical evaluation is significantly incomplete. \n\nAfter discussion with authors\n----------------------------------------\n\nThe reviewer thanks the authors for clarifications. With the confusion from the typos resolved, the paper is easier to follow. The technical correctness of the paper is not in doubt any more. But two major concerns still remain: \n\n1.  The diversity enforcement has been reported before, and more comprehensive discussion of related work would be useful.  A detailed empirical analysis would also make the paper balanced and not heavily reliant on the novelty/depth of theoretical contribution. \n\n2.  The main claimed theoretical contribution summarized in Lemma B.1 is tedious but a derivation of an obvious statement (as sketched out in the original review). \n\nThe reviewer is raising the score to encourage this work, but still holding to the recommendation of not accepting the paper in its current form. \n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "OACR6gJiHnD", "reviewer": "AnonReviewer1", "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 studies the following problem: How to train a certifiably robust classifier with ensemble methods? The authors considered two types of ensembles: the weighted-average ensemble and large-margin ensemble. They first derived theoretically sufficient and necessary conditions for robustness under two types of ensembles, with the conclusion that large confidence margin and diversified gradients are two factors which contributes to the robustness of ensemble models. Diversity-regularized training, a method of designing loss functions for training ensemble models, is proposed motivated by their theoretical findings. They applied this methodology to randomized smoothing, performed extensive experiments and showed non-trivial improvement over single model methods.\n\nThe paper is very well-written and provided extremely detailed discussion about many different aspects of the problem, both theoretically and empirically. From the reviewer's point of view, this is the strongest part of this work. I am very impressed by the level of detail in the appendix, which covers many interesting questions like under which scenario is WE better than MME, why is ensemble before smoothing better than ensemble after smoothing, to name a few. I wish more papers in the community are written in this way.\n\nHowever, my current evaluation to this paper is a weak accept - it is a bit conservative, but I think it's based on some valid concerns, detailed below. \n\nThe experimental results, while showed non-trivial improvements over single model baselines, may not be very strong. In most cases, the improvements are like 3~4%, sometimes a little over 5% in smaller radius settings comparing to smoothadv. This improvement is much smaller than some of the earlier works like smoothadv vs gaussian. Also in certain settings, the improvement over other single model baselines becomes very small (e.g. <2% over MACER in Table 12). The performance is also overall very similar to recent ensemble baselines like Liu et al. 2020. My understanding is that this shows a limitation of ensemble-based methods in certifiable robustness.\n\nTo summarize, despite of the limitations mentioned above, I think this work is overall good enough for recommending acceptance and thank the authors for their effort.\n\nMinor comments:\nI don't quite get the point of appendix D.3, in particular, the reasoning that trying to justify the uniform distribution assumption of confidence scores. The concentration of measure in high dimensional Gaussian does not imply the uniformity of confidence scores. Although I do understand this assumption as a concrete example  trying to get more interpretable results.", "extra_scores": {}, "extra_text": {}}, {"review_id": "K_lRYr-LCSc", "reviewer": "AnonReviewer3", "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 offers a novel idea regarding improving robustness of ensemble models with a rigorous mathematical background. A comparison between two types of ensemble models (Weighted Ensembles and Max-Margin Ensembles) and to single models offers very good insight into the theoretical dynamics of certified robustness.\nUnfortunately, the presented methods for practical applications are two simple regularization terms (of questionable form, see below), and, more importantly the authors are not able to conclusively show any benefits empirically - only MNIST and CIFAR10 show improvements vs baselines, ImageNet is evaluated as the only large-scale dataset, but with negative results.\n\nPositive:\n* a proof is offered why certain regularization is beneficial for robustness, while other works are only based on empirical results\n* the work consists of several proofs, greatly extending the theoretical background of ensemble model robustness\n* even if you ignore the proposed regularization term, theoretical insights of the robustness of Weighted Ensemble vs Max-Margin Ensemble vs single model are of value for further understanding the topic. (Figure 3 in the appendix is great)\n* the regularization term seems to work consistently well for CIFAR10 and MNIST\n\nNegative:\n* The paper has too much information in too little space - “related work” and “conclusion” seem artificially short to fit the 8 pages.\n* The paper reads like two papers glued together (one would be chapter 2 + chapter 4 + appendix E about the regularization term DRT, the other is chapter 3 + appendix C + D about the theoretical certified robustness of the ensemble types with smoothness). The paper has two main pillars (like mentioned above: chapter 2 and chapter 3), but chapter 3 offers no results/conclusions for chapter 4 (the experiments), it seems strangely misplaced between ch. 2 and ch. 4.\n* some notations are a bit sloppy, some assumptions are questionable\n* the GD regularization term (Gradient diversity loss) should have a different form: In the previous section the authors state that “..the magnitude of gradient sum could be efficiently reduced as long as their directions are diverse.”, but the GD term is still the L2 norm instead of cosine similarity. \n* Experiments are extremely limited and the proposed method does not work on large-scale data\n\nDetailed comments:\n* In Sub-Section “Key factors for the certified robustness of an ensemble” (p. 5): The authors write “Though reducing the gradient magnitude [something positive], it may hurt the model accuracy significantly” and continue showing how the L2 norm of the sum of two vectors contains the cosine similarity, which is critical for model diversity. Furthermore they argue that by reducing the L2 norm the cosine similarity is also reduced and continue using L2 as their regularization term called Gradient Diversity Loss. But if reducing the base model gradient norm is potentially so bad, then why is the regularization not exclusively the cosine similarity between the two gradients? This should be evaluated.\n* based on the analysis, the authors argue the confidence score margin has also important influence on the robustness, so it is artificially increased through another regularization term called Confidence Margin Loss. This opens two follow-up questions:\n    * naturally cross entropy already tries to reach high confidence scores, so the question is if the Confidence Margin Loss achieves anything that cross entropy implicitly does not, or if it maybe only stabilizes training convergence. I would like to see some results on that\n    * By increasing the confidence scores further, any improvement in regarding robustness may come at the cost of an increased expected calibration error - this would be interesting to evaluate\n* Ablation study: an additional evaluation of how beneficial each loss term is for the robustness is missing\n* Theorem 4 and onwards: The random variable “epsilon” cannot by element of R^d, since a random variable is a function.\n* “Definition 1” has an important typo: “epsilon” should be “r”, otherwise the term “r-robust” makes no sense, if no r is present in the definition\n* section 2.1: The whole paper is about Weighted Ensembles and Max-Margin-Ensembles, but their formal definitions are moved to the appendix, please move to main text\n* Proposition 1: In “min”, “y_i =/= y_0” is not required because if y_i == y_0, the term is equal 0 (this is not an error, but less clutter is preferable)\n* Definition 2: the second gradient is w.r.t. x, but the argument is y\n* Theorem 4 and 5, and Corollary 2 assume the confidence scores across several base models are i.i.d. and symmetric random variables. I am not usure if this assumption holds in any case and would appreciate some discussion here: How can the output be seen as symmetrical? Confidence scores are between 0 and 1, so exact symmetry is almost always impossible as long as they are close to 1 (which they are due to the training and if they are in-domain)...\n\n\n######Post-rebuttal####\nThe authors have addressed some of my concerns and I have raised my score accordingly \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "4NLO22ZbHwT", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "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": "\nThis manuscript provides proofs for certified robustness for ensembles and proposes a new approach called Diversity Regularized Training (DRT) based on the theoretical findings. In addition to the standard loss term, DRT contains two regularization terms: (i) gradient diversity (GD) loss, and (ii) confidence margin loss (CM). These loss terms encourage the joint gradient difference for each model pair and large margin between the true and runner-up classes for base models. The authors discuss some theoretical findings in detail and demonstrate the performance of DRT on several datasets. I find the work valuable in the sense that it nicely combines ideas of ensembling and certified robustness. However, it was difficult to follow all the theoretical results and how they motivated the main finding (DRT) was not clear. Below are my comments/questions:\n\n- I want to thank the authors for nice summary in Appendix B1 and B2 on certified robustness and their map to ensembles.\n\n- Theorem 1, which serves as the foundation for the paper, assumes that either best prediction or the runner-up prediction is true class for any base model. I wonder how realistic this assumption is.\n\n- Also in theorem 1, I am confused that both f and y have index i. The number of base models does not need to match the number of classes.\n\n- In proof for Theorem 2, it could be helpful to mention each step. For instance, it was not clear to me where Lagrangian reminder was applied. Also, I recommend proving necessary and sufficient conditions separately.\n\n- In theorem 3, N is assumed to be 2. Is it possible to extend this to N > 2? So, discussion on such this could be helpful.\n\n- In the first paragraph on page 5, I do not follow which equation was meant in RHS.\n\n- These statements on page 5 are not clear to me: \"... and leads to higher certified ensemble robustness.\" and \"Thus, increasing confidence margins can lead to higher ensemble robustness.\"\n\n- For GD loss, why only pairwise summations were considered? Isn't it easier to look at overall diversity of gradients?\n\n- All pair-wise computation of quantities in regularizer terms should come with some computational complexity. It would be nice to include a discussion on this.\n\n- Results for Salman et al., 2019 on Table 2 do not match the paper of Salman et al., 2019 and imagenet results are not convincing. I understand ImageNet data can take too long but should we worry that DRT requires more hyper-parameter tuning? Some discussion on this would be helpful.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: I thank the authors and reviewers for the lively discussions. Although reviewers agreed the work is interesting, there are some concerns about the significance of the results and experiments. None of the reviewers were strongly supportive of the paper while majority of them suggest that the paper needs a bit more work before being accepted. Also, reviewers suggest that the paper is not easy to follow and its writing should be improved. Given all, I think the paper , at the current stage, is below the accept threshold. I encourage authors to edit the paper according to the suggestions by the reviewers. 
Decision: Reject