On the Certified Robustness for Ensemble Models and Beyond
Authors: Zhuolin Yang
Linyi Li
Xiaojun Xu
Bhavya Kailkhura
Tao Xie
Bo Li
Venue: ICLR 2022 Poster (2022)
Keywords: robustness
ensemble
certified robustness

Abstract: Recent studies show that deep neural networks (DNN) are vulnerable to adversarial examples, which aim to mislead DNNs by adding perturbations with small magnitude. To defend against such attacks, both empirical and theoretical defense approaches have been extensively studied for a single ML model. In this work, we aim to analyze and provide the certified robustness for ensemble ML models, together with the sufficient and necessary conditions of robustness for different ensemble protocols. Although ensemble models are shown more robust than a single model empirically; surprisingly, we find that in terms of the certified robustness the standard ensemble models only achieve marginal improvement compared to a single model. Thus, to explore the conditions that guarantee to provide certifiably robust ensemble ML models, we first prove that diversified gradient and large confidence margin are sufficient and necessary conditions for certifiably robust ensemble models under the model-smoothness assumption. We then provide the bounded model-smoothness analysis based on the proposed Ensemble-before-Smoothing strategy. We also prove that an ensemble model can always achieve higher certified robustness than a single base model under mild conditions. Inspired by the theoretical findings, we propose the lightweight Diversity Regularized Training (DRT) to train certifiably robust ensemble ML models. Extensive experiments show that our DRT enhanced ensembles can consistently achieve higher certified robustness than existing single and ensemble ML models, demonstrating the state-of-the-art certified $L_2$-robustness on MNIST, CIFAR-10, and ImageNet datasets.

Published as a conference paper at ICLR 2022
ON THE CERTIFIED ROBUSTNESS FOR ENSEMBLE MODELS AND BEYOND
Zhuolin Yang' Linyi Li Xiaojun Xu'
Bhavya Kailkhura²
Tao Xie
Bo Li
'University of Illinois Urbana- -haamaaaa Lawrence Livermore National Laboratory
*Peking University
1zhuolin5, linyi2, xiao ( eeillinois.e... edu Sailkhurai@e gov taoxie@pku. certepkku.edu..... en
Equal contribution
ABSTRACT
Recent studies show that deep neural networks (DNN) vulnerable to adver- sarial examples, which aim to mislead DNNs by adding perturbations with small magnitude. To defend against such attacks, both empirical and theoretical defense approaches have been extensively studied for a single ML model. In this work, we aim analyze and provide the certified robustness for ensemble ML models, together with the sufficient and necessary conditions of robustness for different en- semble protocols. Although ensemble models are shown more robust than a single model empirically; surprisingly, we find that in terms of the certified robustness the standard ensemble models only achieve marginal improvement compared to a single model. Thus, to explore the conditions that guarantee to provide certifiably robust ensemble ML models, we first prove that diversified gradient and large confi- dence margin are sufficient and necessary conditions for certifiably robust ensemble models under the smooth-smoo assumption. We then provide the bounded wwwbblee-beor-SSmooolle strategy. We also prove that an ensemble model can always achieve higher certified robustness than a single base model under mild conditions. Inspired by the theoret- ical findings, we propose the lightweight Diversity Regularized Training (DRT) to train certifiably robust ensemble ML models. Extensive experiments show that our DRT enhanced ensembles can consistently achieve higher certified robustness than existing single and ensemble ML models, demonstrating the state-of-the-art certified Lg-robustness on MNIST, CIFAR-10, 10, and ImageNet datasets.
model-smoothness analysis based on the proposed
INTRODUCTION
Deep neural networks (DNN) have been widely applied in various applications, such as image classification (rizhevskyy) 2012 He et al. (016)), face recognition (Sun et al.) 2014), and natural language processing (Vaswani
2017 Devlin al. 2019). However, it is well-known that DNNs are vulnerable to adversarial examples (Szegedy et al. 2013 Carlini & Wagner 2017 Xiao et al. 2018a b Bhattad al., 2020 Bulusu al. 2020), and has raised great concerns especially when DNNs are deployed in salety-critice applications such as autonomous driving and facial recognition.
To defend against such attacks, several empirical defenses have been proposed (Papernot al. 2016b)
Madry et al. 2018); however, many of them have been attacked again by strong adaptive attack- ers (Athalye et al. 2018 Tramer et al. 2020 To end such repeated game between the attackers and defenders, certified defenses (Wong& & Kolter 2018 Cohen et al. 2019) have been proposed to provide the robustness guarantees for given MI. models, so that no additional attack can break the model under certain adversarial constraints. For instance, randomized smoothing has been proposed
effective
defense providing certified robustness (Lecuyer et al., 2019: Cohen et al., 2019 Yang et al,, 2020a). Among different certified robustness approaches (Weng al. 2018 Xu et al. 2020 Li al. 2020al Zhang et al.] 2022),, randomized smoothing provides a model-inden iideependent way to smooth a given ML model and achieves state-of-the-a art certified robustness on large-scale datasets such ImageNet.
Currently, all the existing certified defense approaches focus on the robustness of a single ML model. Given the observations that ensemble MI. models able to bring additional benefits in standard

---

Published as a conference paper at ICLR 2022
learning Opitz & Maclin 1999
Rokach 2010), in this work aim to ask: Can ensemble ML model provide additional benefits in terms of the certified robustness compared with a single model? so, what are the sufficient and necessary conditions guarantee such certified robustness gain?
Empirically, we first find that standard ensemble models only achieve marginally higher certified robustness by directly appling randomized smoothing: with L2 perturbation radius 1.5, single model achieves certified accuracy as 21.9%, while the average aggregation based ensemble of three models achieves certified accuracy as 24.2% on CIFAR-IO (Table Given such observations, next we aim to answer: How to improve the certified robustness of ensemble ML models? What types of conditions are required improve the certified robustness for ML ensembles?
In particular, from the theoretical perspective, we analyze the standard Weighted Ensemble (WE) and Max-Marge Ensemble (MME) protocols, and prove the sufficient and necessary conditions for the certifiably robust ensemble models under mrodel-smoothness. assumption. Specifically, we prove that: (1) an ensemble ML model is more certifiably robust than each single base model; (2) diversified gradients and large confidence margins of base models are the sufficient and necessary conditions for the certifiably robust ML ensembles. We show that these two key factors would lead to higher certified robustness for ML ensembles. We further propose Ensemble- seee-beeo----ooolie as the model smoothing strategy and prove the bounded model-smoothness with such strategy, which realizes our model-smoothnes, assumption.
Inspired by our theoretical analysis, we propose Seersitt-Regulariizeee Training (DRT), lightweight regularization- based ensemble training approach. DRT is composed of two simple yet effective and gen- eral regularizers to promote the diversified gradients and large confidence margins respectively. DRT can be easily combined with existing ML approaches for training smoothed models, such as Gaussian augmen- tation (Cohen et al., (219)) and adversarial smoothed training (Salman et al. 2019), with negligible training time overhead while achieves significantly higher certified robustness than state-of-the-ar approaches consistently.
Base Model
True-Class Decision Region of Baw Models
True-Class Decision
Region of Ensembles
Model
Figure 1: Illustration of a robust ensemble.
We conduct extensive experiments on a wide range of datasets including MNIST, CIFAR-10, and Im- ageNet. The experimental results show that DRT can achieve significantly higher certified robustness compared to baselines with similar training cost as training a single model. Furthermore, as DRT is flexible integrate any base models, by using the pretrained robust single ML models as base models, DRT achieves the highest certified robustness so far to our best knowledge. For instance, on CIFAR-10 10 under L2 radius 1.5, the DRT-traines ensemble with three base models improves the certified accuracy from SOTA 24.2% to 30.3%; and under L2 radius 2.0, DRT improves the certified accuracy from SOTA 16.0% to 20.3%.
Technical Contributions. In this paper, we conduct the first study for the sufficient and necessary conditions of certifiably robust MI. ensembles and propose an efficient training algorithm DRT to achieve the state-of oh-the-art certified robustness. We make contributions on both theoretical and empirical fronts.
We provide the necessary and sufficient conditions for robust ensemble ML models including Weighted Ensemble (WE) and Max-Margin Ensemble (MME) under the mmoothess assumption. In particular, we prove that the diversified gradients and large confudence margins of base models are the sufficient and necessary conditions of certifiably robust ensembles. We also prove the bounded model- soooth-smootneess via proposed Ensemble- bellle--eff-e-eeeee Sefffori-mmootiigg strategy. assumption.
which realizes our
To analyze different ensembles, we prove that when the adversarial transferability among base models is low, WE is more robust than MME. We also prove that the ML ensemble is more robust than a single base model under the model-smoothness assumption.
Based on the theoretical analysis of the sufficient and necessary conditions, we propose DRT, lightweight regularization-basee training approach that can be easily combined with different training approaches and ensemble protocols with small training cost overhead.
We conduct extensive experiments evaluate the effectiveness of DRT on various datasets, and we show that to the best of your knowledge, DRT can achieve the highest certified robustness, outperforming all existing baselines.
2

---

Published as a conference paper at ICLR 2022
Related work. DNNs are known vulnerable to adversarial examples (Szegedy et al. 2013 To defend against such attacks, several empirical defenses have been proposed (Papemot et al. 2016b Madry et al.] 2018). For ensemble models, existing work mainly focuses on empirical robustness (Pang et al. 2019 Li et al. 2020b, Cheng et al., 2021) where the robustness is measured by accuracy under existing attacks and certified robustness guarantee could be provided or enhanced; or certify the robustness for standard weighted ensemble (Zhang et al., 2019 Liu et al., 2020) using either LP-based (Zhang et al. 2018 verification randomized smoothing without considering the model diversity (Liu et al. (2020) to boost their certified robustness. In this paper, we aim to prove that the diversified gradient and large confidence margin are the sufficient and necessary conditions for certifiably robust ensemble ML models. Moreover, our best knowledge, we propose the firxt training approach to boost the certified robustness of ensemble ML models.
Randomized smoothing (eecyyer et al., 2019 Cohen et al. 2019) has been proposed to provide certified robustness for a single MI. model. achieved the state-of-the-art certified robustness on large-scale dataset such as ImageNet and CIFAR-10 under Le norm. Several approaches have been proposed to further improve it by: (1) choosing different smoothing distributions for different Lp norms (Dvijotham et al.. 2019 Zhang al. 2020; Yang et al. (2020a). and (2) training more robust smoothed classifiers, using data augmentation (Cohen et al. 2019). unlabeled data (Carmon et al.) 2019), adversarial training (Salman et al. 2019), regularization (Li et al. (019 Zhai al.] 2019). and denoising (Salman et 22.00. In this paper, we compare and propose a suitable smoothing strategy to improve the certified robustness of ML ensembles.
2 CHARACTERIZING ML ENSEMBLE ROBUSTNESS
In this section, we prove the sufficient and necessary robustness conditions for both general and smoothed ML ensemble models. Based on these robustness conditions, we discuss the key factors for improving the certified robustness of an ensemble, compare the robustness of ensemble models with single models, and outline several findings based on additional theoretical analysis.
2.1 PRELIMINARIES
Notations.
Throughout the paper, we consider the classification task with C' classes. We first define the classification scoring functiin f : Ed + A which maps the input to confidence vector, and f f(x); represents the confidence for the ith class. We mainly focus on the confidence after normalization, i.e., f(x) A {p E RC ||pl|1 1} in the probability simplex. To
characterize the confidence margin between two classes, we define f (x) = f(x)y) - f(x) The corresponding prediction F Rd - [C] is defined by F(x) == arg max f();;- We are also interested in the runner-up prediction F(2
arg (c f(x);
r-Robustness. For brevity, we consider the model's s certified robustness, against the Le-bounded perturbations as defined below. Our analysis can be generalizable for L, and Los perturbations, leveraging existing work (Li et al., 2019; Yang al. 2020al Levine & Feizi| (022]).
Definition (r-Robustness). For prediction function Rdd + [C] and input æo, if all instance E {wo + 8: ||0 |2<r] satisfies F(x)- F(xo), we say model F is v-robust (at point 2n).
Ensemble Protocols. An ensemble model contains N base models (F.) where F(( and (x) are their top and runner-up predictions for given input æ respectively. The ensemble prediction is denoted by M Rd + [C], which is computed based on outputs of base models following certain ensemble protocols. In this paper, we consider both Weighted Ensemble (WE) and Maximum Margin Ensemble (MME).
Definition 2 (Weighted Ensemble (WE)). Given N base models (Fi) and the weight vector {w,) R, the weighted ensemble Mwe: Rd + [C] is defined by
MwE(2o) := arg max Σ wy (xu)). (E[C]
(I)
Definition 3 MMax-Margin Ensemble (MME)). Given N base models (Fi) for input æo the max-mare max-margin ensemble model MMME: dd + [C] is defined by
Mame (mo) = Fc(m)) where
c = arg max (f(())) - f((2)) ((9))) sE(N]
3

---

Published as a conference paper at ICLR 2022
The commonly-used WE (Zhang et al. 2019 Liu et al. 2020) sums up the weighted confidence of base models [; with weight vector { i- and predicts the class with the highest weighted confidence. The standard average ensemble can be viewed as special case of WE (where all are equal). MME 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 al. 2008).
Randomized Smoothing. Randomized smoothing (Lecuyer et al., 2019; Cohen et al. 2019) provides certified robustness by constructing smoothed model from given model. Formally, let è ~ (0, o² Ia) be a Gaussian random variable, for any given model F : IRd + [C] (can be an ensemble), we define smoothed confidence function 97 R A C such that
( ;=
E [x + = j] E~ Lo,00,011.
Pr
(F(æ +
(3)
E~\(0.0011))
Intuitively, gf is the probability of base model F's prediction on the jth class given Gaussian smoothed input. The smoothed classifier G I2 + [C] outputs the class with highest smoothed confidence: (xx)
arg max]e[c] ( Let CA be the predicted class for input æn, i.e., CA == (aro) Cohen et al. show that G.p is (of -rrbbust input æp, i.e., the certified radius is の " ((o))))))e)) where Φ-1 is the inverse cumulative distribution function of standard normal distribution. In practice, we will leverage the smoothing strategy together with Monte-Cari sampling to certify ensemble robustness. More details can be found in Appendix A
2.2 ROBUSTNESS CONDITIONS FOR GENERAL ENSEMBLE MODELS
We will first provide sufficient and necessary conditions for robust ensembles under the model- smoothness assumption.
Definition 4 (B-Smoothness), A differentiable function / Rd + RCC is B-smooth, if for any 31, 32 RC and any output dimension j E [C], [[V,, f(m:); Va S B.
21 -02222
The definition of 8-smoothness is inherited from optimization theory literature, and it is equivalent to the curvature bound in certified robustness literature (Singla & Feizi 2020 quantifies the non-linearity of function f. where higher / indicates more rigid functions/models and smaller B indicates smoother ones. When 3 = the function/model linear.
For Weighted Ensemble (WE), we have the following robustness conditions.
Theorem (Gradient and Confidence Margin Conditions for WE Robustness). Given imput xo E Rd with ground-truth label yo [C], and MwE WE defined over base models (FiN with weights {w, )xx Mwe(#F)) = Yo- All base models F; are B-smooth.
(Sufficient Condition) The MWE is r-robust at point To if for any yb # yo.
N
N
w. Vof f00/ol (zo0
wy wyf
foo/ (aro) 3r wys
(Necessary Condition) If MWE is r-robust point æo, for any F yo.
w. VaI / (zx)
w S (wo) Br
wy.
(5)
The proof follows from Taylor expansion at Ty and we leave the detailed proof in Appendix B.2 When it comes to Max-Margin Ensemble (MME), the derivation of robust conditions more involved. In Theorem 3 (Appendix 1. we derive the robustness conditions for MME composed of two base models. The robustness conditions have highly similar forms those for WE in Theorem T Thus, for brevity, we focus on discussing Theorem for WE hereinafter and similar conclusions can be drawn for MME (details are in Appendix B.I.I.
To analyze Theorem I
we define Ensemble Robustness Indicator (ERI) as such:
Iy Σ
w. V f00// (w))
|||||
w 1 (xro)
(6)
r||
ERI appears in both sufficient (Equation 4 and necessary (Equation (5) conditions. In both conditions, smaller ERI means more certifially robust ensemble. Note that can analyze the
4

---

Published as a conference paper at ICLR 2022
robustness under different attack radius r by directly varying in Equations and (5) When becomes larger, the gap between the RHS of two inequalities (2,3r Σ wy also becomes larger, and thus it becomes harder to determine robustness via Theorem This is because the first-order condition implied by Theorem |
becomes coarse when r is large. However, due to bounded / as we will show, the training approach motivated by the theorem still empirically works well under large r.
The core of first term in ERI is the magnitude of the vector sum of gradients: || E w, Vaff (22) According to the law of cosines: ||a + b|l2 2| bl2 (o, b). to reduce this term, we could either reduce the base models' gradient magnitude or diversify their gradients (in terms of cosine similarity). Since simply reduc- ing base models' gradient magnitude would hurt model expressivity (Huster et al., 2018), during regularization the main functionality of this term would be promoting diversified gradients.
Diversified Gradients.
[bb +
Large Confidence Margins. The core of second term in ERI is the confidence margin: Σ)=1 W3S5 f/ (zo). Due the negative sign of second term in ERI, we need increase this term, i.e., need to increase confidence margins to achieve higher ensemble robustness.
In summary, the diversified gradients and large confidence margins are the sufficient and necessary conditions for high certified robustness of ensembles. In Section 3 two key factors to promote certified robustness of ensembles.
we will directly regularize these
Impact of Smooh-ems Bound B. From Theorem 1 we observe that: ming Iu: S - -Br.Mwe MWE is guaranteed to be r-robust (sufficient condition); and (2) if min Ly. >> Br,, MWE cannot be r-robust (necessary condition). However, if miny, Ly, E (-Br, Br], we only know MwE is possibly r-robust. As a result, the model-smoothness bound /3 decides the correlation strength between min Iy. and the robustness of MWWE: if 3 becomes larger, min I, is more likely to fall in (-Br, 3r), inducing versa. Specifically, when 3 0, i.e., all base models are linear, the gap closed and we can always certify the robustness of MwE via comparing min with O. Similar observations can be drawn for MME. Therefore, to strengthen the correlation between Iy, and ensemble robustness, we would need model-smoothness bound / to be small.
undetermined robustness status from Theorem vice
2.3 ROBUSTNESS CONDITIONS FOR SMOOTHED ENSEMBLE MODELS
Typically neural networks are nonsmooth or admit only coarse smoothness bounds (Sinha et al. 2018), i.c./ 8 is large. Therefore, applying Theorem | for normal nonsmooth models would lead to near-zero certified radius. Therefore, we propose soft smoothing enforce the smoothness of base models. However, with the soft smoothed base models, directly applying Theorem to certify robustness is still practically challenging, since the LHS of Equations (4) and (5) involves gradient of the soft smoothed confidence. A precise computation of such gradient requires high-confidence estimation of high-ding sigh--imensional vectors via sampling, which requires linear number samples with respect to imput dimension (Mohapatra et al.) (2020) (Salman et al. 2019) and is thus too expensive in practice. To solve this issue, we then propose trssemlle-befor-be Smrroohi-m as the practical smoothing protocol, which serves as an approximation of soft smoothing, so as to leverage the randomized smoothing based techniques for certification.
Soft Smoothing. To impose base models' smoothness, we now introduce soft smoothing (Kumar jet al. 2020), which applies randomized smoothing over the confulence scores. Given base model's
confidence function ʃ Rd - C (see Section 2. we define soft smoothed confidence by
9f : x + E. f(x + E). Note that soft smoothed confidence is different from smoothed confidence gf
defined in Equation (3). We consider soft smoothing instead of classical smoothing in Equation (3)
since soft smoothing reveals differentiable and thus practically regularizable training objectives. The following theorem shows the smoothness bound for 0z-
Theorem 2 Moodel-Smoothness Upper Bound for 9ÿ). NO, be a Gaussian random variable, then the soft smoothed confidence function of is (2/o2)
We defer the proof to Appendix B.4
The proof views the Gaussian smoothing the Weierstrass transform WWeiertrras 1885) of a function from IRd to J0. 1]C, leverages the symmetry property, and bounds the absolute value of diagonal elements of the Hessian matrix. Note that Lipschitz constant / 2 is derived for smoothed confidence in previous work (Salman et al. 2019 Lemma 1),
5

---

Published as a conference paper at ICLR 2022
which characterizes only the first-order smoothness property; while our bound in addition shows the second-order smoothness property. In Appendix B.4, we further show that our smoothness bound in Theorem 2 is tight up to a constant factor.
Now, we apply WE and MME protocols with these soft smoothness confidence [ as base models' confidence scores, and obtain soft ensemble G MMwwE and G MMMMm respectively. Since each take WE as an example, we can study the ensemble robustness with Theorem We state the full statement in Corollary 2 corollary, we observe that the corresponding ERI for the soft smoothed WE can be written as
of is (2/o")-smoote
(and in Corollary for MME) in Appendix [.1.3] From the
L L.V
W
/ / (zu + /telll ||ll==
1
E. > f,,, (2o +).
r|[w||1
5=1
We have following observations: (1) unlike for standard models with unbounded B. for the smoothed ensemble models, this ERI (Equation 7 would have guaranteed correlation with the model robust- ness since 3 ((1/a²) is bounded and can be controlled by tuning a for smoothing. (2) we can still control ERI by diversifying gradients and ensuring large confidence margins as discussed in Section 2.2 but need to compute on the noise augmented input zy + E instead of original input 2o.
Towards Practical Certification. As outlined at the beginning of this subsection, even with smoothed base models, certifying robustness using Theorem | is practically difficult. Therefore, introduce
Seabbll--bfoor-SSootiiiiii strategy below to construct G MMw.. and G MMMMR as approximations of soft ensemble GiMw and G ManaE respectively. Definition (Ensemble-before wewrublleebffor-SSmotteeeee
(EBS)). Let M be an ensemble model over base models {F.) and be random variable. The EBS strategy construct smoothed classifier G Rd [C]
that picks the class with highest smoothed confidence of M: (z) := arg maxje;c] 9 (x)
Here M could be either MWE or MMME. EBS aims to approximate the soft smoothed ensemble. ΣS= mzys ||||| to be WE ensemble's confidence, then ΣN 1,, JMwE( (x);
Formally, use WE an example, we let fMwE
MMw (z); = E.I[MwE(# + = i] Be/Mwe (a + +e); Σ wj
(8)
where LHS is the smoothed confidence of EBS ensemble and RHS is the soft smoothed ensemble's confidence. Such approximation is also adopted in existing work (Salman et al. 2019: Zhai et al. 2019; Kumar et al. 2020) and shown effective and useful. Therefore, our robustness analysis of soft smoothed ensemble still applies with EBS and we can control ERI in Equation 7 to improve the certified robustness of EBS ensemble. For EBS ensemble, we leverage randomized smoothing based techniques to compute the robustness certification (see Proposition C.I in Appendix C
2.4 ADDITIONAL PROPERTIES OF ML ENSEMBLES
Comparison between Ensemble and Single-Model Robustness. In Appendix B. we show Corollary T a corollary of Theorem D which indicates that when the base models are smooth enough, both WE and MME ensemble models are more certifiably robust than the base models. This aligns with our empirical observations (see Table and Table 2). though without advanced training approaches such as DRT, the improvement of robustness brought by ensemble itself is marginal. In Appendix B.II we also show larger number of base models N can lead to better certified robustness. Comparison between WE and MME Robustness. Since in actual computing, the certified radius of smoothed model is directly correlated with the probability of correct prediction under smoothed input (see Equation [T] in Appendix [A), we study the robustness of both WE and MME along with single models from the statistical robustness perspective in Appendix D From the study, we have the following theoretical observations verified by numerical experiments: (1) MME is more robust when the adversarial transferability is high; while WE is more robust when the adversarial transferability is low. (2) If we further assume that fx + e) follows marginally uniform distribution, when the number of base models N is sufficiently large, MME is always more certifiably robust. Appendix D.5 entails the numerical evaluations that verify our theoretical conclusions.
3
REGULARIZEL TRAINING
Inspired by the above key factors in the sufficient and necessary conditions for the certifiably robust ensembles, we propose the sample, DRT contains the following two regularization terms in the objective function to minimize:
Training (DRT). In particular, let in be a training

---

Published as a conference paper at ICLR 2022
Gradient Diversity Loss (GD Loss): LGD(Xo) = VV,, (lo/m)
(x Vall v (zo)lla-
voios
(9)
Confidence Margin Loss (CM Loss): LCM (20)1; = 1 /20 (10) + 1/ //0 (2r0)- (3ro)-
(10)
In Equations (9) and (1)., yo is the ground-trun label of zo. and y (or 8/ (2)) is the runner-up class of base model F; (or F,). Intuitively, for each model pair ( FF F2) where i.j j E [N] and * j. the GD loss promotes the diversity of gradients between the base model F; and Pj. Note that the gradient computed here is actually the gradient difference between different labels. As our theorem reveals, is the gradient difference between different labels instead of pure gradient itself that matters, which improves existing understanding of gradient diversity (Pang et al.] 2019; Demontis et al.) 2019)) Specifically, 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. In contrast, solely regularizing the hase 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 runner-up classes for base models. Both regularization terms are directly motivated by theoretical analysis in Section 2
For each input By with ground truth you we use Zy + E with E ~ N(O, [a) as training input for each base model (i.e., Gaussian augmentation). We call two base models (F,; F5) a valid model pair at (æo, yo) if both Fx + and (20 +e) equal yo. For every valid model pair, we apply DRT: GD Loss and CM Loss with 01 and p2 as the weight hyperparameters as below.
Lirain
Laaa + E. + PI (E[N]
Σ
Σ
LCD(E0 + E) + P2
Σ (.
LaM + +))g
N. (F., F8) is valid
(Fi. F2) is valid
The standard training loss (a0 + e, Mo); of each base model F. is either cross-entropy loss (Cohen et al., 2019). or adversarial training loss (Salman et al. 2019). This standard training loss will help to produce sufficient valid model pairs with high benign accuracy for robustness regularization. Specifically, as discussed in Section 2.3 we compute LGD and LCM on the noise augmented inputs (Irg + e) instead of za improve the certified robustness for the smoothed ensemble.
Discussion. To our best knowledge, this is the first training approach that is able to promote the certified robustness of ML ensembles, while existing work either only provide empirical robustness
without guarantees (Pang al. 2019: Kariyappa & Qureshi 2019 Yang al. 2020b; 202T). or tries
to only optimize the weights of Weighted Ensemble (Zhang et al. 2019 Liu et al. (020). We should notice that, though concepts similar with the gradient diversity have been explored in empirically robust ensemble training (e.g., ADP (Pang et al. 2019). GAL (Kariyappa & Qureshi 2019)), directly applying these regularizers cannot train models with high certified robustness due to the lack of theoretical guarantees in their design. We indicate this through ablation studies in Appendix G.4] For the design of DRT, we also find that there exist some variations. We analyze them and show that the current design is usually better based on the analysis in Appendix [E] Our approach is generalizable for other -ooundddd perturbations such as Ln and Log leveraging existing work (Li et al. 2019
Lecuyer et al. 2019 Yang et al. 2020a Levine &
EXPERIMENTAL EVALUATION
To make a thorough comparison with existing certified robustness approaches, we evaluate DRT on different datasets including MNIST (LeCun et al., 2010), CIFAR-10 (Krizhevsky 2012). and ImageNet (Deng et al. 2009). based on both MME and WE protocols. Overall, we show that the DRT enabled ensemble outperforms all baselines in terms of certified robustness under different settings.
4.1 EXPERIMENTAL SETUP
Baselines. We consider the following state-of-the- baselines for certified robustness: Gaussian smoothing (Cohen et al. 2019). SmoothAdy (Salman et al. 2019). MACER (Zhai et al.) 2019). Stability eL al. 2019), and SWEEN (Liu et al. 2020). Detail description of these baselines can be found in Appendix F We follow the configurations of baselines, and compare DRT-based ensemble with Gaussian Smoothing, SmoothAdy, and MACER on all datasets, and in addition compare with other baselines on MNIST and CIFAR-10 considering the training efficiency. There are other baselines, e.g., (Jeong & Shin 2020). However, SmoothAdy performs consistently better across different datasets, mainly consider Ady our strong baseline.
7

---

Published as a conference paper at ICLR 2022
Train Ensemble Models with GD loss & CM loss
Aggregate with WE or MME protocol
Smooth via EBS
Compute Certified Radius
Strategy
Eq. (9)
Fq. (1) and (2)
Definition 5
Sec 2.1 and Appendix A
Robust Ensemble Training
Smoothed Ensembl Construction
Robustress Robustress Cortifiction
Figure 2: Pipeline for DRT-based ensemble.
Table 1: Certified accuracy under different radii MNIST dataset. The grey rows present the performance of the proposed DRT approach. The brackets show the hase models we use.
Radius
0.00
0.25
0.50
0.75
1.00
1.25
1.50
1.75
2.00
2.25
2.50
Gaussion
(Colen al. 2019
96.6
90.0
83.0
68.2
46.6
33.0
20.5
11.5
SmoothAdF
maniman e m 2019
99.1
98.4
97.0
96.3
93.0
87.7
80.2
66.3
43.2
34.3
24.0
MACER Zhin al 2019
99.2
98.5
97.4
94.6
90.2
83.5
72.4
54.4
36.5
26.4
16.5
Stahility
trerra 2019
99.3
98.6
97.1
93.8
90.7
46.8
33.1
20.0
11:2
SWEEN Gansssan] (Li al. 2020
99.2
98.4
96.9
94.9
90.5
84.4
71.1
48.9
35.3
23.7
12.8
SWEEN (Smpolhhdd7
2020
44.5
34.9
25.0
MINE (Gaussian)
99.2
98.4
96.8
94.9
90.3
841.3
69.8
48.8
34.7
23.4
12.7
DKT MME (Gaussian))
99.5
97.5
95.5
43.9
29.1
MME (SmoothAdv)
99.2
98.2
97.3
96.4
93.2
88.
80.6
67.9
44.8
35.0
25.2
DRT MME (SmmothAddv
99.2
98.4
97.6
96.7
93.1
88.5
83.2
68.9
48.2
40.3
34.7
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 + WE (Gaussian)
99.5
98.6
97.4
95.6
92.6
86.7
76.7
60.2
43.9
35.8
29.0
WF (SmoethAdv)
99.1
98.2
97.4
DKT + WE (SmoothAdv)
99.1
98.4
97.6
96.7
93.4
88.5
83.3
69.6
48.3
40.2
34.8
Models. For base models in our ensemble, we follow the configurations used in baselines: LeNet (Le
Cun et al.) [998], ResNet- 110, and ResNet-50 (He et al. 2016) for MNIST, CIFAR- 10, and ImageNet datasets respectively. Throughout the experiments, we use N = 3 base models to construct the ensemble for demonstration. We expect more base models would yield higher ensemble robustness.
Training Details. We follow Section to train the base models. We combine DRT with Gaussian smoothing and SmoothAdv (i.e., instantiating Lard by either cross-entropy loss (Cohen al. 2019 Yang et al. (2020)) or adversarial training loss (Salman el al. 2019)). We leave training details along with hyperparametes in Appendix F
Pipeline. After the base models are trained with DRT, we aggregate them to form the ensemble M. using either WE or MME protocol (see Definitions and B If we use WE, to filter out the effect of different weights, we adopt the average ensemble where all weights are equal. We also studied how optimizing weights can further improve the certified robustness in Appendix G.3] Then, we leverage Ensemble-before- Srrfforr-Smootting strategy to form a smoothed ensemble (see Definition3] [ Finally, we compute the certified robustness for the smoothed ensemble based on Monte-Carlo sampling with high-confidence (99.9%). The training pipeline is shown in Figure
Evaluation Metric. We report the standard certified accurucy under different Ly radii r's as our evaluation metric following existing work (Cohen et al. 2019 Yang et al. 2020b Zhai al. 2019 Jeong& & Shin 2020). More evaluation details are in Appendix
4.2 EXPERIMENTAL RESULTS
Here consider ensemble models consisting of three base models. We show that 1) DRT-based ensembles outperform the SOTA baselines significantly especially under large perturbation radi;; 2) smoothed ensembles are always more certifiably robust than each base model (Corollary | in Appendix [: 3) applying DRT for either MME or WE ensemble protocols achieves similar and consistent improvements on certified robustness.
Certified Robustness of DRT with Different Ensemble Protocols. The evaluation results on MNIST, CIFAR-10, ImageNet are shown in Tables certified accuracy of a single model can be improved by directly applying either MME or WE ensemble training (proved in Corollary [ such improvements are usually negligible (usually less than 2%). In contrast, in all tables we find DRT provides significant gains on certified robustness for both MME and WE (up to over 16% as Table shows).
respectively. It is clear that though the
From Tables D and 2 on MNIST and CIFAR-10, we find that compared with all baselines, DRT-based ensemble achieves the highest robust accuracy, and the performance gap is more pronounced on large 2.50 on MNIST and 6% for the scalability of DRT by training on ImageNet, and Table shows that DRT achieves the highest certified robustness under large radii. It is clear that DRT can be easily combined with existing training approaches (e.g. Gaussian smoothing or SmoothAdv), boost their certified robustness, and set the state-of-the-art results to the best of our knowledge.
radii (over 8% for
1.50 on CIFAR-10), We also demonstrate
8

---

Published as a conference paper at ICLR 2022
Table 2: Certified accuracy under different radii on CIFAR-10 dataset. The grey rows present the performance of the proposed DRT approach. The brackets show the base models we use.
Rudius
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
al. 2019
68.9
61.0
54.4
45.7
34.8
28.5
21.9
18.2
15.7
MACER Zhili et aL 2019
79.5
68.8
55.6
42.3
35.0
27.5
23.4
20.4
17.5
Stability Li et al. 2019
72.4
58.2
43.4
27.5
23.9
16.0
15.6
11.4
7.8
SWEEN (Gaussian) [Liu et 2020
81.2
68.7
54.4
38.1
28.3
19.6
15.2
11.5
8.6
SWEEN (SmoothAdy)
2020
69.5
62.3
55.0
46.2
35.2
29.5
22.4
19.3
16.6
MMF (Caussian))
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
34.4
29.6
24.9
20.9
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)
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)
81.5
70.4
57.9
44.0
34.2
29.6
24.9
20.8
16.4
WE (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
To evaluate the computational cost of DRT, we analyze the theoretical complexity in Appendix and compare the efficiency of different methods in practice in Appendices (F.tiicce//[]]]. and In particular, we show that DRT with Gaussian Smoothing base models even achieves around two times speedup compared with Ado with comparable or even higher certified robustness, since DRT does not require adversarial training. More discussions about prpeer-paramtee settings for DRT can be found in Appendix F In Appendix G.4 we also show that our proposed DRT approach could
achieve 6% ~ 10% higher certified accuracy compared to adapted ADP (Pang et al. 2019) and
GAL (Kariyappa Qureshi 2019) training on large radii for both MNIST and CIFAR- 10 datasets.
Certified Accuracy with Different Perturbation Radius. We visualize the trend of certified accuracy along with dif- ferent perturbation radii in Figure For each radius we present the best certi- fied accuracy among different smoothing parameters E {0.25, 0.50, 1.00J. We notice that while simply applying MME or WE protocol could slightly improve the certified accuracy, DRT could signif- icantly boost the certified accuracy un- der different radii. We also present the trends of different smoothing parameters separately in Appendix which lead to similar conclusions.
Table 3: Certified accuracy under different radii on ImageNet dataset. The grey rows present the performance of the proposed DRT approach. The brackets show the base models we usc.
Nadius
Gaussian
Coben all
2019
57.2
37.0
29.2
SmoothhArT
2019
54.6
49.0
43.8
37.2
27.0
25:2
20.4
MACER Plaro wi 2019
68.8
57.0
43.0
31.0
25.0
18.0
14.0
SWEEN (oosstan Lig
A020
58.4
47.0
37.4
29.8
20.2
15.8
12.8
SWEEN (SmoothAuly
2000
55.2
50.0
44.2
37.8
27.6
26.6
21.6
MME (Gamssian)
(Caussin))
34
(SmocthsAdk)
(SmoothAdv)
WE (Gaussiun)
58.2
47.2
38.5
31.2
21.6
17.0
14.4
DRT - WE (Ginssinn)
52.2
46.8
41.8
33.6
24.2
198
18.4
WE (SmoothAdv)) DRI WE (SaoothhAd))
55.2
50.2
44.4
38.6
26.2
26.2
22.0
49.8
46.5
44.4
39.8
38.4
29.0
25.2
Effects of GD and CM Losses in DRT. To explore the effects of individual Gra- dient Diversity and Confidence Margin Losses in DRT, we set P1 or P2 to sepa- rately and tune the other for evaluation on MNIST and CIFAR-10. The full results shown in Appendix G.I We observe that both GD and CM losses have positive effects on improving the certified accu- racy, and GD plays major role on larger radii. By combining these two regular- ization losses as DRT does, the ensemble model achieves the highest certified accuracy under all radii.
Gaussian NNE (Gausslan)
MNE
DET HHE (Causalan)
9.6
6.1
*g
85
2.
Rad
Racha
(a) MNIST
(b) CIFAR-10
Figure 3: Certified accuracy for ML ensembles with Gaus- sian smoothed base models, under smoothing parameter o E (0.25, 0.50, 1.00} on (Left) MNIST; (Right) CIFAR-10.
5 CONCLUSION
In this paper, we explored and characterized the robustness conditions for certifiably robust ensemble ML models theoretically, and proposed DRT for training robust ensemble. Our analysis provided the justification of the regularization basedd training approach DRT. Extensive experiments showed that DRT-enhanced ensembles achieve the highest certified robustness compared with existing baselines.

---

Published as a conference paper at ICLR 2022
Ethics Statement. In this paper, characterized the robustness conditions for certifying ML en- semble robustness. Based on the analysis, we propose DRT to train a certifiably robust ensemble. On the one hand, the training approach boosts the certified robustness of ML ensemble, thus significantly reducing the security vulnerabilities of MI. ensemble. On the other hand, the trained MI. ensemble can only guarantee its robustness under specific conditions of the attack. Specifically, we evaluate the trained ML ensemble on the held-out test set and constrain the attack to be within predefined L2 distance from the original input. We cannot provide robustness guarantee for all possible real-world inputs. Therefore, users should be aware of such limitations of -trinndd ensembles, and should not blindly rely on the ensembles when the attack can cause large deviations measured by L2 distance. As result, we encourage researchers to understand the potential risks, and evaluate whether our attack constraints align with their usage scenarios when applying our DRT approach to real-world applications. We do not expect any ethics issues raised by our work.
Reproducibility Statement. All the theorem statements are substantiated with rigorous proofs in Appendices B to D In Appendix F we list the details and hyperparameters for reproducing all experimental results. Our evaluation is conducted on commonly accessible MNIST, CIFAR- 10, and ImageNet datasets. Finally, we upload the source code the supplementary material for reproducibility purpose.
ACKNOWLEDGEMENTS
This work was performed under the auspices of the U.S. Department of Energy by the Lawrence Livermore National Laboratory under Contract No. AEEACC22-7NA22344 and LLNL LDRD Program Project No. 20-ER-014. This work is partially supported by the NSF grant 1910000 NSF CNS 20-46726 CAR, Alfred P. Sloan Fellowship, and Amazon Research Award.
REFERENCES
Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give false sense of security: Circumventing defenses to adversarial examples. In International Conference on Machine Learning, pp. 274-283, 2018
Anand Bhattad, Min Jin Chong, Kaizhao Liang, Bo Li, and David A Forsyth. Unrestricted adversarial examples via semantic manipulation. In International Conference on Learning Representations, 2020.
Saikiran Bulusu, Bhavya Kailkhura, Bo Li, Pramod Varshney, and Dawn Song. Anomalous example detection in deep learning: A survey. IEEE Access, 8: 1333300-132347, 2020.
Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In 2017 ieee symposium security and privacy (sp). pp. 39-57. IEEE, 2017.
Yair Carmon, Aditi Raghunathan, Ludwig Schmidt, John C Duchi, and Percy Liang. Unlabeled data improves adversarial robustness. In Advances Neural Information Processing Systems, pp. 11192-11203, 2019.
Hao Cheng, Kaidi Xu, Chenan Wang, Xue Lin, Bhavya Kailkhura, and Ryan Goldhahn. Mixture of robust experts (more); A flexible defense against multiple perturbations. arXiv preprint arXiv:2104. 10586, 2021.
Charles Clopper and Egon S Pearson. The use of confidence fiducial limits illustrated in the case of the binomial. Biometrika, 26(4):404-413, 1934.
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. In International Conference on Machine Learning, pp. 1310-13200 2019.
Ambra Demontis, Marco Melis, Maura Pintor, Matthew Jagielski, Battista Biggio, Alina Oprea, and Fabio Roli. Why do adversarial attacks transfer? explaining transferability of evasion and poisoning attacks. In 28th {USENIX) Security Symposium (!USENIX) Security 19), pp. 321-338, 2019.
Cristina
10

---

Published as a conference paper at ICLR 2022
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A durge-scale hierarchical image database. In 2009 JEEE conference on computer vision and pattern recognition, pp. 248-255, Icee, 2009.
Jacob Devlin, Ming- Ming-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 Gyorgy, Kai Xiao, Sven Gowal, and Pushmeet Kohli. A framework for robustness certification of smoothed classifiers using f-divergences. In International Conference Learning Representations, 2019.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 770-778, 2016.
Kaizhu Huang, Haiqin Yang, Irwin King, and Michael R Lyu. Maxi-min margin machine: learning large margin classifiers locally and globally. IEEE Transactions on Neural Networks, 19(2): 260-272, 2008.
Todd Huster, Cho-Yu Yu Jason Chiang, and Ritu Chadha. Limitations of the lipschitz constant defense against adversarial examples. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 16-29. Springer, 2018.
Jongheon Jeong and Jinwoo Shin. Consistency regularization for certified robustness smoothed classifiers. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 10558-10570, Curran Associates, Inc., 2020.
Sanjay Kariyappa and Moinuddin Qureshi. Improving adversarial robustness of ensembles with diversity training. arXiv preprint arXiv: 2019.
Alex Krizhevsky. Learning multiple layers of features from tiny images. University of Toronto, 05 2012.
Aounon Kumar, Alexander Levine, Soheil Feizi, and Tom Goldstein. Certifying confidence via randomized smoothing. In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 5165-5177. Curran Associates, Inc., 2020.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86( 86(11):2278-2324, 1998.
Yann LeCun, Corinna Cortes, and CJ Burges. Mnist handwritten digit database. ATT Labs [Online]. Available: http://yann.lecun.comm wwt.///b////iisttto.tmom////// 2, 2010.
Mathias Lecuyer, Vaggelis Atlidakis. Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified robustness to adversarial examples with differential privacy. In 2019 IEEE Symposium on Security and Privacy (SP), pp. 656-672. IEEE, 2019.
Alexander J Levine and Soheil Feizi. Improved, deterministic smoothing for l certified robustness. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 6254-6264. PMLR, 18-24 Jul 2021.
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.
Linyi Li, Tao Xie, and Bo Li. Sok: Certified robustness for deep neural networks. arXiv preprint arXiv:2009.044 0131,, 2020a.
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, 2020b.

---

Published as a conference paper at ICLR 2022
Chizhou Liu, Yunzhen Feng, Ranran Wang, and Bin Dong. Enhancing certified robustness of smoothed classifiers via weighted model ensembling. arXiv preprint arXiv:2005.09360 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.
Jeet Mohapatra, Ching- Yun Ko, Tsui-Wa Weng, Pin- Yu Chen, Sijia Liu, and Luca Daniel. Higher- order certification for randomized smoothing. Advances in Neural Information Processing Systems, 33, 2020.
Jerzy Neyman and Egon Sharpe Pearson. Ix. on the problem of the most efficient tests of statistical hypotheses. Philosophical Transactions of the Royal Society of London. Series A, Containing Papers of a Mathematical or Physical Character, (31
1933.
David Opitz and Richard Maclin. Popular ensemble methods: An empirical study. Journal of artificial intelligence research, 11:169-198, 1999.
Tianyu Pang, Kun Xu, Chao Du, Ning Chen, and Jun Zhu. Improving adversarial robustness via promoting ensemble diversity. In International Conference on Machine Learning, pp. 4970-4979. PMLR, 2019.
Nicolas Papernot, Patrick McDaniel, and Ian Goodfellow. Transferability in machine learning: from phenomena to black-box attacks using adversarial samples. arXiv preprint arXiv: arXiv:I605.072 1605.07277, 2016a.
Nicolas Papernot, Patrick McDaniel, Xi Wu, Somesh Jha, and Ananthram Swami. Distillation defense to adversarial perturbations against deep neural networks. In 2016 IEEE Symposium on Security and Privacy (SP), pp. 582-597. IEEE, 2016b.
Lior Rokach. Ensemble-based classifiers. Artificial intelligence review, 33(1):1-39 2010.
Hadi Salman, Jerry Li, Ilya 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-11303, 2019.
Hadi Salman, Mingjie Sun, Greg Yang, Ashish Kapoor, and Zico Kolter. Black-box smoothing: A provable defense for pretrained classifters. arXiv preprint wxxv:20033009900 2020.
Saeed Saremi and Rupesh Srivastava. Provable robust classification via learned smoothed densities.
arXiv preprini arXiv:2005.0455 2020.
Sahil Singla and Soheil Feizi. Second-order provable defenses against adversarial attacks. In International Conference on Machine Learning, 2020.
Aman Sinha, Hongseok Namkoong, and John Duchi. Certifying some distributional robustness with
principled adversarial training. In International Conference Learning Representations, 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 recognition, pp. 1891-1898, 2014.
Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties neural networks. arXiv preprint arXiv:1312.6199 2013.
Florian Tramer, Nicholas Carlini, Wieland Brendel, and Aleksander Madry. On adaptive attacks to adversarial example defenses. arXiv preprint arXiv:2002.088 08.407 0024
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.
Karl Weierstrass. Über die analytische darstellbarkeit sogenannter willkürlicher functionen einer reellen veränderlichen. Siraangsberichte der Königlich Preußischen Akademie der Wissenschaften zu Berlin, 2:633-639 1885.
12

---

Published as a conference paper at ICLR 2022
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, Bo Li, Jun-Yan Zhu, Warren He, Mingyan Liu, and Dawn Song. Generating adversarial examples with adversarial networks. arXiv preprint arXiv:1801.022: 00,000000, 2018a.
Chaowei Xiao, Jun- Yan Zhu, Bo Li, Warren He, Mingyan Liu, and Dawn Song. Spatially transformed adversarial examples. In International Conference on Learning Representations, 2018b. URL
htttps://openrevilte
net htaee//oooommmityyyddo...
Kaidi Xu, Zhouxing Shi, Huan Zhang, Yihan Wang, Kai-Wei Chang, Minlie Huang, Bhavya Kailkhura, Xue Lin, and Cho-Jui Hsieh. Automatic perturbation analysis for scalable certified robustness and beyond. In Advances in Neural Information Processing Systems, 2020.
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, 2020a.
Huanrui Yang. Jingyang Zhang, Hongliang Dong, Nathan Inkawhich, Andrew Gardner, Andrew Touchet, Wesley Wilkes, Heath Berry, and Hai Li. Dverge: Diversifying vulnerabilities for enhanced robust generation of ensembles. Advances in Neural Information Processing Systems, 33, 2020b.
Zhuolin Yang, Linyi Li. Xiaojun Xu, Shiliang Zuo, Qian Chen, Pan Zhou, Benjamin P. Rubinstein, Ce Zhang, and Bo Li. Trs: Transferability reduced ensemble via promoting gradient diversity and model smoothness. In Advances Neural Information Processing Systems, 2021.
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.
Bohang Zhang, Du Jiang, Di He, and Liwei Wang. Boosting the certified robustness of l-infinity distance nets. In International Conference on Learning Representations, 2022. URL https
//operreiiew net http://wwww.eeee/ooooeeoo-100000 wtt.:/mmmdm00o/1mat..
Dinguua Zhang, Mao Ye, Chengyue Gong, Zhanxing Zhu, and Qiang Liu. Black-box certifica- tion with randomized smoothing: A functional optimization based framework. arXiv preprint arXiv:2002.09169, 2020.
Huan Zhang, Tsui- Wei Weng, Pin-Yu Chen, Cho-Jui Hsieh, and Luca Daniel. Efficient neural network robustness certification with general activation functions. Advances in neural information processing systems, pp. 4939-4948, 2018.
Huan Zhang, Minhao Cheng, and Cho-Jui Hsich. Enhancing certifiable robustness via a deep model ensemble. arXiv preprint arXiv: /4655, 2019.
13

---

Published as a conference paper at ICLR 2022
In Appendix provide more background knowledge about randomized smoothing. In Ap- pendix B we first discuss the direct connection between the definition r-robustness and the robustness certification of randomized smoothing, then prove the robustness conditions and the comparison results presented in Section 2 In Appendix C we formally define, discuss, and the- oretically compare the smoothing strategies for ensembles. In Appendix [ characterize the robustness of smoothed ML ensembles from statistical robustness perspective which is directly related the robustness certification of randomized smoothing. In Appendix E present and analyze some alternative designs of DRT. In Appendix FF) we show the detailed experimental setup and full experiment results. Finally, in Appendix G] we conduct abalation studies on the effects of Gradient Diversity and Confidence Margin Losses in DRT in Appendix G.1 certified robustness of single base model within DRT-trained ensemble in Appendix [G.2] and investigate how optimizing ensemble weights can further improve the certified robustness of DRT-trained ensemble in Appendix G.3) We also analyze other gradient diversity promoted regularizers' performance and compare them with DRT in Appendix G.4
A BACKGROUND: RANDOMIZED SMOOTHING
Cohen et al. (Cohen et al. 2019) leverage Seyman-PParsow Lemma Neyman & Pearson
1933) to
provide a computable robustness certification for the smoothed classifier.
Lemma A.1 (Robustness Certificate of Randomized Smoothing; (Cohen et al. 2019)). As point vo. let random variable NN0,0 a² Ia), smoothed model G is r-robust where
2 ( 1 (gr(2))))) --1 (0f()))))))
(11)
where CA (zo) and cg 2 (zo) are the top and runner-up class respectively, and 4-1 is the inverse cumulative distribution function (CDF) of standard normal distribution.
In practice, for ease of sampling, the standard way of computing the certified radius is using the lower bound of Equation 11
o (g (x))c,). Now we only need to figure out g (3)))a) The common way is to use Monte-Carlo sampling together with binomial confidence interval (Cohen et al. (2019;; Yang et al. (2020a): Zhai et al. (2019); Jeong Shin (2020), Concretely, from definition of ( PTe.:N(U.021.) (F'w +
CA), we sample n Gaussian noises: 61, En (0, o² Ia and compute the empirical mean: (x0))
n Σi= [[F (mo + e.) ca). The binomial testing Clopper & Pearson 1934) then gives a high-confidence lower bound of (Zo)cs based on (20 We follow the setting in the literature: sample
10a samples and set confidence level be 99.9% Cohen et al. (2019); Yang et al. (2020a); ZZai et al. )2019); Jeonn & Shin (2020). More details are available in Appendix F Note that F could be either single model or any ensemble models with Ensemble- Sermmbllebeforr--Smooiinnnn strategy.
B DETAILED ANALYSIS AND PROOFS IN SECTION 2
In this appendix, we first show the omitted theoretical results in Section 2 which are the robustness conditions for Max-Margin Margin Ensemble (MME) and the comparison between the robustness of ensemble model and single model. We then present all proofs for these theoretical results.
B. DETAILED THEORETICAL RESULTS AND DISCUSSION
Here we present the theoretical results omitted from Section along with some discussions.
B. ROBUSTNESS CONDITION OF MME
For MME, we have the following robustness condition.
Theorem 3 (Gradient and Confidence Margin Condition for MME Robustness). Given input Zy Rd with ground-trutt label yo E [C), and MAME as an MME defined over base models {Fi, F2). MMME (x))= yo- Both Fi and F2 8-smooth.
14

---

Published as a conference paper at ICLR 2022
(Sufficient Condition) for any V1, U2 [C] such that y1 yo and y2 # yo-
V fi (xo) V / V (zo) ll2 = - (J (xo) + 52 (xx)) 28r, (12)
then MMME r-robust at point zo-
(Necessary Condition) Suppose for any a E {wu + + 11812 S r. any i E {1, either F((x)) yo F(2) (x) yo- If MMME is r-robust at point wo, then for any yı, V2 E [C]
such that yı + yo and 1/2 + yo-
9 (3r)
Var2 / (200 l12 S 1 2 (mo0) + 520/1a (3ro) + 28r.
(sp0/
(13)
Comparing with the robustness conditions of MME (Theorem D). the conditions for MME have highly similar forms. Thus, the discussion for ERI in main text (Equation (6)) still applies here, including the positive impact of diversified gradients and large confidence margins towards MME ensemble robustness in both sufficient and necessary conditions and the implication of small model-smoothhess bound B. A major distinction is that the condition for MME limited to base models. This is because the "maximum" operator in MME protocol poses difficulties for expressing the robust conditions succinet continuous functions of base models' confidence. Therefore, Taylor expansion cannot be applied. We leave the extension to N > 2 base models as future work, and we conjecture the tendency would be similar as Equation (5) The theorem proved Appendix B.2
B.1.2 COMPARISON BETWEEN ENSEMBLE ROBUSTNESS AND SINGLE- MODEL ROBUSTNESS
To compare the robustness of ensemble models and single models, we have the following corollary that is extended from Theorem I and Theorem
Corollary (Comparison of Ensemble and Single-Model Robustness). Given input No Re with ground-truft truth label yo E [C]. Suppose we have two 8-smooth base models {Fi, F2 which are both r-robust at point Vo. For any A E 1):
(Weighted Ensemble) Define Weighted Ensemble MWE with base models F2). Sup- pose MwE(20) = Yo- If for any label yi # yo- the base models' smooth- ness B S A min min(ftm//. (2o)) (zo), p2o//: (z)))/((r²)) and the gradient cosine similarity cos(Ve //0/ (zo), V Vaf2 //0/uu (2o)) I 0, then the MWE with weights {wi, w2} is at least R-robust at point zo with
R=r. 1 A (1 CwE(1-com cos -1/2 ,wheee
(14)
2n0 Wa f po0/Ms (mn)) 12 /20// (mmp) CWB min
2at Mo (wyJ." /20/ bi ((e (e)) f2 (ma))) max L-A (1 - Cwe(1 cos c)s 1// .1. 144
(Max-Margin Ensemble) Define Max- Max-Margin Ensemble MMME with the base models {Fi, , F2). Suppose MMME((00) = y0- If for any label # and + yo. the base models' smoothness B E A ( (Ix), puo/ (/zo))((2 and the gradient cosine similarity /20/v2 (xo)) I cos 0, then the MMME is at least R-robust at point xo
cos(Væ / (xo), Vel2
with
A (1 CMME(1 - cos co) -1/2 wheee
R I+
(15)
CMME
min 2/20/01 (20 (www
max 1+A
CMME cos 1/2
(1 ( 1 (=m)))²
31.30
The proof is given in Appendix B.3
Optimizing Weighted Ensemble. As we can observe from Corollary D we can adjust the weights (WI, w2) for Weighted Ensemble to change OwE and the certified robust radius (Equation (14)
15

---

Published as a conference paper at ICLR 2022
Then comes the problem of which set of weights achieve the highest certified robust radius. Since larger CwE results in higher radius, we need to choose
2w1 w2 f1 (2 f20/ (xo)
(m) T
W2 w2 ( arg max min wy Mey: (wi / (10) + w2 /20/ (xo)))
Since this quantity is scale-invariant, we can fix wi and optimize In particular, if there are only two classes, we have a closed-form solution
w2 get the optimal weights.
2w w2 f 21 (x0)).2 f (xo)
(wprr, 222 wDPT) = arg max (w //o// (zo) + W252 /20/ m (zn))²
[k. f2 / (zn), k. 1 up (xo) k R+).
and corresponding OWE achieves the maximum 1/2.
For special case aase-average weighted ensemble, we get the corresponding certified robust radius by setting W1 w2 and plug the yielded
2//m/ (200) (20 (xo)
CwE
min
(0,
Mo (S (aro) + /20 21 (22))2
into Equation
Comparison between ensemble and single-model robustness. corollary allow us to discuss the Weighted Ensemble and Max-Margin Ensemble together. Specifically, we let C be either CWE or CMME, then
The similar forms of R in the
1- (1 C(1 1+A
R -
-css
Since when R >>> r, both ensembles have higher certified robustness than the base models, we solve this condition for cos 0:
1 1-4 I+A
4A
1 1 111- cas = cos f S
C(1+ AJ²
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 B, we can notice that A could be close to zero. As a result,
сリ-Aソz is close to 1. Thus, unless the gradient of 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.
Larger certified radius with larger number of base models N. Following the same methodol- ogy, we can further observe that larger number base models N can lead to larger certified radius as the following proposition shows.
Proposition B.1 (More Base Models Lead to Higher Certified Robustness of Weighted Ensemble). At clean input æp E TRd with ground-truth label yo E [C], suppose all base models [f N+M are B- 8-smooth. Suppose the Weighted Ensemble M1 of base models {f and M2 of base models N
[Ja) ++ are both r-robust according to the sufficient condition in Theorem I and any yi # yo N the Mi and M2's M ensemble gradients (Ei=1 w. VN 2e egn/vi (wo) and Σ}=N+1 N+ W/ V. /20/// (xo)) are non-zero and not colinear, then the Weighted Ensemble M of (1) r'-robust for some >>> r.
Proof of Proposition B.I For any * yo. since both Mi and Ma are r-robust according to the
sufficient condition of Theorem we have
wy Va poo/ (zo)
1 <
Σ
poo
(xo)
Br Σ
Wi. (16)
j=1
j=1
16

---

Published as a conference paper at ICLR 2022
N+-M
1 N+M
N+
Σ
w/ V /
(20)
-= Σ
( Br
Wj.
(17)
2
j=N+1
j=N+1
j=N+1
Adding above two inequalties we get
N
N+M
N+M
N+M
wy Vor
(mo0)l2 +
Σ
Wj
V
/ (mo)
-
Σ
fga/ir (200) - Br
Σ
Wj.
J=N+1
j=1
(18)
Since gradients of ensemble are not colinear and non-zero from the triangle inequality,
N+M
N
N+M
Σ
my V 1u (100)
Σ
wy
V m
( 112 +
Σ
1000// (200)
(19)
==1
-=N+1
and thus
N+M fu (xo)
N+M
N+M
Σ
3 Val
1
Σ
f (zo)
-Br
wy.
(20)
which means we can increase r to r' and still keep the inequality hold with "s", and in turn certify a larger radius r' according to Theorem
Since DRT imposes diversified gradients via GD Loss, the "not colinear"' condition easily holds for DRT ensemble, and therefore the proposition implies larger number of base models N lead to higher certified robustness of WE. For MME, we empirically observe similar trends.
B.1.3 ROBUSTNESS CONDITIONS FOR SMOOTHED ENSEMBLE MODELS
Following the discussion in Section 2.3 for smoothed WE and MME, with the mooet-smoothsess
bound (Theorem 2 we can concretize the general robustness conditions in this way.
We define the soft smoothed confidence function of (x:) == f + E). This definition is also used in the literature (Salman et al., 2019) Zhai al.) 2019 Kumar et al. 2020). As result, we revise the ensemble protocols of WE and MME by replacing the original confidences (zo)) with these soft smoothed confidences {o (xo)) ) These protocols then choose the predicted class by treating these (of (xr)) J.M as the base models' confidence scores. the experiments, we did not actually evaluate these revised protocols since their robustness performance are expected to be similar as
original ones (Salman et al. 2019 Zhai et al., 2019 Kumar et al. 2020). The derived results connect smoothed ensemble robustness with the confidence scores.
Corollary (Gradient and Confidence Margin Conditions for Smoothed WE Robustness). Given input Io Rd with ground-trutt label yo [C]. Let ~ NN00, o Ia) be Gaussian random variable. Define soft smoothed confidence of (a) == Ee(x + for each base model F3 (1 < sis N). The GMM is a WE defined over soft smoothed base models { N with weights {w.) Mom (xo) = yo-
(Sufficient Condition) The G G'Mwe r-robust at point By for any ys F yo.
N Σ
N
w V /o (zo) |1,
S S r
W w5(ي5 Vo/
uo (xo)
2r
Σ
Wjj
(21)
σ² ==1
(Necessary Condition) If G GMMws is r-robust at point No, for any yo # yo-
N
N
N
wy V u0/ (2o) Σ
1 Σ <
wy (3,
(x0) +
2r -
Wj.
(22)
Corollary (Gradient and Confidence Margin Condition for Smoothed MME Robustness). Given input To Ed with ground-triee trnnh label yo [C]. Let ~ (00 Ia) be Gaussian random
variable. Define soft smoothed confidence J. (z) := E.fi(x + E) either base model F, or F2. The G MMsoe is MME defined over soft smoothed base models (0f 08. C G (#o) yo-
17

---

Published as a conference paper at ICLR 2022
(Sufficient Condition) for any V1, U2 [C] such that y1 yo and y2 # yo-
4r
2 (xo) + V ( ( mo)ll 2 - (( (xo) + (06)
02
(23)
then G Masse is r-robust at point Zu.
(Necessary Condition) Suppose for any a E {wo + 1|8112 S r) for any i E {1,2}.
either Gp,, (x) yo G (x) yo- If MMMaR is r-robust point Vo. then for any y1, 3/2 [C] such that yı + Yo and 1/2 + yo.
4r
V (91) 000 (xx) + V 32 /0/
ao))2 - (xx) + (05)00/12 (2))))
+
σ²
(24)
Remark. The above corollaries are extended from Theorem and Theorem 3 respectively, and correspond to our discussion in Section 2.3 We defer the proof's to Appendix B.5 From these two corollaries, we can explicit see that the Ensemble smoothed classifiers G Mwe and G Mange with bounded model smoothness; and we can see the correlation between the robustness conditions and gradient diversity/confidence margin for smoothed ensembles.
(see Definition provides
B.2 PROOFS OF ROBUSTNESS CONDITIONS FOR GENERAL ENSEMBLE MODELS
This subsection contains the proofs robustness conditions. First, we connect the prediction of ensemble models with the arithmetic relations of confidence scores of base models. This connection straightforward to establish for Weighted Ensemble (shown in Proposition [.2)). but nontrivial for Max-Margin Ensemble (shown in Theorem 4. Then, prove the desired robustness conditions using Taylor expansion with Lagrange reminder.
Proposition B.2 (Robustness Condition for WE). Consider input Do E Rd with ground-truth label yo E [C]. and an ensemble model Mwr. constructed by base models ( (Fi with weights {w, ) Suppose MwE(x0) = yo- Then, the ensemble MWE is r-robust at point xo if and only if for any {aa 5: 2 S r).
5 gon/u (x) 2 O.
According the the definition of r-robust, we know MWF is r-robust if and only if for any point x 2o + å where | S <r, MwE(wx + 6) yo. which means that for any other label y * you the confidence score for label yo is larger or equal than the confidence score for label ys. It means that
Proof of Proposition B.2
N
(w) 8o Σ w15s())
J=1
for any {mo 8 |01|2 S r). Since this should hold for any ys * yo. we have the sufficient and necessary condition
min W EC
w
g00/si (x) 2
(25)
1=1
Theorem 4 (Robustness Condition for MME). Consider input To Rd with ground-truth label 90 [C]. Let MMME be an MME defined over base models [F. Suppose: (1) MMMME(O)) =
No: (2) for any E {Na + 1 < r), given any base model [N]. either F,(x) = Mo
or (2) (x) = 90- Then, the ensemble MMME is r-robust at point Do if and only if for any
(wo 8: 100 r).
min iE[N] c.
/ (3))())))))))))) 2
min
P/ (ar).
(26)
[N[ e/(C
18

---

Published as a conference paper at ICLR 2022
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 26 as such in the following lemmas and their proofs:
fth / (x) + min N W #C
fta ///
min
min VE M(((C)u((
x
2 0.
26
Lemma B.1 (Sufficient Condition for MME). Let MMMEE be an MME defined over base models (R.)er- For any input vn E IR,,, the Max-Margin Ensemble MAME predicts MaMEE yo if
max [ d: [C
min
f! (xo) + min min iE ME
8u (200 2 0.
26
Proof of Lemma B.1 For brevity, for [N]. we denote yi Fi(x))) 2/ (x0) for each base model's top class and runner-up class at point Zip.
Suppose MMME(xa) (x²a) * you then according to ensemble definition (see Definition there exists E [N], such that .MMME (Zo) = Fe(w))) = ye. and
Vi [N], i c, fo(20))oolve fo(200)oi/vl.
(27)
Because Ve * yo. we have fo( n0 I fo( so that fo(2o))o/ ue/wo 2 fo(2o) Now consider any model F; where i [N], would like to show that there exists y² + you such that (20))/./) 2 far)) "o/w"
If y: = yo. let y² := y/: trivially f(( -f((x))///
If y: + yo. and y + yo. let y" = v/. then f((2))m/// (200))/11) 2 (0
If * yo. but sf you we let y² == ys. then f:(oo)///1l = f((20)) fo f1(2o)
Combine the above findings with Equation 27 we have:
Vi E [N], + c, Zye E [C] and ve # yo: Bye E [C] and yf + you fc(2o)))/10 > f
Therefore, its negation
Di E [N], i i e, V E [C] and v. + yo, Vyt E [C] and yf + yo. fo( + f( ) >
(28)
implies M(xx) you Since Equation 28 holds for any v. and yf the equation is equivalent to
3i E [M, i i c,
min v.
) /o/ (xo) +
min fi(wo) /0/ vi (20)) 2 0.
The existence qualifier over can be replaced by maximum:
(o/o)))/0 + max min t0
min
(oco))// 2 O.
SE[N 1/CC
is implied by
max NE
min too
/oo/l (xx) + min min NE v
(w/ 2 0.
26
Thus, Equation 26 is a sufficient condition for MMME( = yo-
Lemma B.2 (Necessary Condition for MME). For any input to E Rd. if for any base model i E [N], either F (= yo (T(2(())) yo, then Max-Margin Ensemble MMME predicting MMMME(0o) = Yo implies
max N
min (o
f /0 (xo) + min min v/
f
ga/n/ (xo) 2 0.
26
NE
19

---

Published as a conference paper at ICLR 2022
Proof of Lemma 8.2 Similar as before, for brevity, for i E [M,, we denote y/ Fi(xu))
F(()) (xo) for each base model's top class and runner-up class at point To-
Suppose Equation 226 is not satisfied, it means that
Be M ByC E [C] and ve # yo, Vi E [N], Bug E [C] and of + yo: 1e > pllo/vi (2:0)-
If ye = yo, then 10 (2o) S O, which implies that volli (xx0) < O, and hence F:(20)) 4 yo- Moreover, we know that f. f.u/8sh (2o) = 1. z s /wo (oo) > 1gul (x0) 2
fonlul (xo) = 1e (( so M(xa) # Fo(20) = yo-
If Ve + yo. i.e. voa = yo. then fee/ (x00) 2 fee (20o) > prolul (200). If F((xo) = you then s.ulvi (xo) 2 S (zo) (x0)) (aro). As the result, M(200) = Fo( # yo-
f/h/v((an (20)). Thus, fie//e (20o) = foe (xx) >
For both cases, we show that MMME j you i.e., Equation (26 is a necessary condition for M(xx)= yo.
Proof of Theorem 1 Lemmas B.I and B.2 are exactly the two directions (necessary and sufficient condition) MMME predicting label yo at point æ. Therefore, if the condition (Equation (26) holds for any (mo + d: ||ā||2 S r). the ensemble MMME is r-robust at point Zo; vice versa.
For comparison, here we list the trivial robustness condition for single model.
Fact B.1 (Robustness Condition for Single Model). Consider an input an Rdd with ground-truth label yo E [C]. Suppose a model satisfies F(xa)) = yo- Then, the model F is r-robust at point wo and only for any x {wo + 8: | r}
min e c
fuo/ (x) 2 0.
The fact is apparent given that the model predicts the class with the highest confidence.
Now we are ready to apply Taylor expansion to derive the robustness conditions shown in main text. Theorem I (Gradient and Confidence Margin Condition for WE Robustness). Given input To Rd with ground truth label yo [C], and MwF, as a WE defined over base models {F)) with weights {w, N Mwe( = yo- All base model F. 's are B-smooth.
(Sufficient Condition) MWE is r-robust at point Do if for any ys # yo.
N
N
<
w
10/ (aro) - 33r Wi-
(Necessary Condition) If MwE is r-robust at point vp. then for any yi # yo-
N
N
N
w
V x
(x))
||
w w
200/16
(wo) + 3r
Wj.
Proof of Theorem 7 From Taylor expansion with Lagrange remainder and the 3-smoothness assump- tion on the base models, we have
N
NN
N
wzf pao 1o (axo) - r| Σ wi ao.f pan/ih (200)
1 , Σ (23w,)
S
min
wy
(x))
2 jml
w:
Sr
jm1
N
Σ W / (xc)) +|| Σ
W/ V
+
2 2
1
Σ (2,ww))
2
j=l
(29)
20

---

Published as a conference paper at ICLR 2022
where the term - Σド= 1j=((2 (23w,) and 2²¹ 1 are bounded from Lagrange remainder. Note that the difference 51 vn is (23) instead of 3-smooth since it is the difference of two 8-smooth function, and thus Σÿ= Wj f is Σ)= ( (2B8rr))smmon -smooth. From Proposition B.2 the
sufficient and necessary condition of WE's r-robusttesss is Σj= / (x) 2 0 for any y E
[C]
such that yi + yo, and any æo where || Plugging this term into Equation (29 get the theorem.
Theorem 3 (Gadiiet and Confidence Margin Condition for MME Robustness). Given input xo E R with ground-truth label yo E (C), and MMмE MME defined over base models {F1, F22) MMME (ro) = yo- Both F1 and F2 are 3-smooth.
(Sufficient Condition) for any Vl, V2 E [C] such that y1 # yo and 1/2 # yo-
/ /1 (2r) /oo u2 (xo) 1l2 S - (1 (xx) + 12 w2 (xo)) 2,r
12
then MMME is r-robust at point 20-
(Necessary Condition) Suppose for any x E {wo + 6: 1|8112 S for any i E {1,2}, either F((x)) = yo or F!22) (x) yo- If MMME r-robust at point Do, then for any y1 V2 e [C]
such that y1 # yo and 1/2 + yo.
V V / (xo)
V fe (2o))l2 I 1 (spu// (xo) + f20/ (xo)) + 28r.
13
Proof of Theorem
We prove the sufficient condition and necessary condition separately.
(Sufficient Condition)
From Lemma B.I since there are only two base models, we can simplify the sufficient condition for MMME = Yo as
min #
fu (x)
min //(C0/;
f /o/vl (x) 0.
In other words, for any y1 yo and 1/2 F yo.
/oo m (2) + yo / (x) 2 0.
(30)
With Taylor expansion and model-smoothner assumption, we have
min 2: 20 10100-zall 2 Sr
puo/ve y1 (x) + puo/ (x))
// /1 91 (ID) + // 22 (xo)
r|| V ft / (xr)) + V Vaf2 (x0))l 2
4,8y
Plugging this into Equation 30 yields the sufficient condition.
In the above equation, the term -1 4.3 is bounded from Lagrange remainder. Here, the
4,3 term comes from the fact that f/w// (xx + f va (x)) is
since it is the sum
difference of 3-smooth function.
(Necessary Condition) From Lemma B.2 similarly, the necessary condition for MMMEE()) Mo is simplified to: for any y1 + yo and 1/2 + yo.
(x) + pua/ v2 (x) 2 0.
30
Again, from Taylor expansion, we have
min 2: 2
p / (x: + /lhu/ 22 (x))
< / (zo) + 1 /3 (xx) - r|| Va / (zxn) + Va /0/ (20)) + 2.3
21

---

Published as a conference paper at ICLR 2022
Plugging this into Equation 30 yields the necessary condition.
the above equation, the term + 4.r²² is bounded from Lagrange remainder. The 4,3 term appears because of the same reason before.
Since we will compare the robustness of ensemble models and the single model, we show the corresponding conditions for single-model robustness.
Proposition B.3 (Gradient and Confidence Margin Conditions for Single-Mode Model Robustness). Given inpul Zo R with ground-truth label yo E [C]. Model F(xo) you and it is 8-smooth.
(Sufficient Condition) for any E [C] such that y1 * yo-
v / (x S - puo/ua (ou/u((xo) (oo) - Br,
(31)
F is r-robust at point Zn.
(Necessary Condition) If F is r-robust at point To. for any E [C] such that y1 F yo.
V v v (za)lla - - fwo/v (xo) + Br.
(32)
Proof of Proposition B.3 This proposition is apparent given the following inequality from Taylor
expansion
fuo/ (xo) 2 (zo) 112 112-1122
<
min -=|
f8o/21 (x) S fuo/ (xo)~rll ve fo/ (x 1
2o Sr
and the sufficient and necessary robust condition in Fact B.1
B.3 PROOF OF ROBUSTNESS COMPARISON RESULTS BETWEEN ENSEMBLE MODELS AND SINGLE MODELS
Corollary (Comparison of Ensemble and Single-Model Robustness). Given an input Do Rd with ground-trute truth label yo E [C]. Suppose we have two 8-smooth base models {Fi, F2), which are both r-robust at point To. For any E 1);
(Weighted Ensemble) Define Weighted Ensemble MWE with base models {Fi, F2]. Sup- pose Mwe(xxo
yo- If for any label y: * the base models' smooth- ness B A min// (xo), /oo/ (20)) (x)))/((r)) and the gradient cosine similarity cos Vee //0//: (x0)) V vx12 /30/15 (wo)) S cos0, then the MWE with weights {wi, w2} is at least R-robust at point zu with
(x)))
1 1- A (1 CWE(1 (000001-0000) cos 1/2 where
R=
14
I+A
200, Wo poo (20 /200/ (sea)
OwE min
max 1- (1
,1}.
yo (ws f (wx) +- 120 f
(mz)))²
(Max-Margin Ensemble) Define Max-Margin Ensemble MMME with the base models {Fi, F2). yo- for any label z! # Yo and y2 + yo. the base models' Suppose MaME((E (x0) / (xx), piu/va (xo))/ and the gradient cosine similarity smoothness B < A m
f
/uo/v: (xo), Val2 2bo//0 (xo)) I co then the MMME is at least R-robust at point xo cos(V V gool with
R I+A
(1 CMME (1- - cos cos 1/2 where
15
CMME
min
2020/01 (20) (200)
max
1-4 (1 CMME cos ()s 01)
91.92: J12
(120/11 (#.)+ 100/ (200))
1+A
22

---

Published as a conference paper at ICLR 2022
Proof of Corollary 7 have
We first prove the theorem for Weighted Ensemble. For arbitrary ys # you
1101
V. /00
( + w2 V
22 /30//s (moo (zzo)]l2
V /
V / (2z 113 + 2w1 W2 ( VV (xo)) f2 (axo))
wfll
V a... (2o) + w3 V /o (xo + 2wn wa V s. /oo (22o)]22 V v / (200)l22 cos
1A3
(100 3r) + w
- 12 (200) 3r)
+ 2wl L Froo/ (azo) (r) (2 (s0o) + 3r) cus 0
(x0o)
(fNo/Mi + (eie 3g (20 Bra)² 2
(fuo/ (200) 3ra)
( ui (200) Br? cos 0 (120
2w W2
1
(2
1
V uu /i (2a) w2 ////// /i (wa)2 2w ww M (wo) / (zxa) cos
(1+
4
(wiLfto// (mro + uz /o (moo 2
2(1 cos Olw1 (2o)) / ( (2z0)
6801
(1+ (1s (w / (wr) + ur uz /2 (azo)
S
where (i.) follows from the necessary condition in Proposition B.3 (ii.) uses the condition on 33; and (tii.) replaces 2w; f (xo) f20// (zo) leveraging CWE. Now, we define
1 A I+ (1 Cwe(1 - cos 1/2
K
All we need do is to prove that MWE robust within radius Kr. To do so, from Equation 4 we 1
upper bound ||w] V. f1o/ / (xo) + u2 v 3Kr(wi + w2):
guo/ (2o))l2 by Kr (wi u/ (mr) + w2 / /v. (3:0)
| V /No/ 8/ (x00) + w2 v /o/ (xo)ll2
1 1+
VI (1 cos cos CWWE (WIf fww/// (x0) + w2f2 / (xo)
<
(1 + A)
(1 - cos ()
P10/// (xO) + w2f2 120/ (Ioo)
1-A
(W 1///// (200 + wrs s (oo)
(1 (1 cos CWF:
I+A
1
(1-A)
/on.////i (zo) + /20//1 (zz)
Kr
1
(01f/o/Vi(a00 (2:0) + 20 /v: (xxn) - A min ( f/0/ (œo), f (xx) + wz))
Kr
Notice that A min pin/vi (zo), 12 /1 (xx)) 2 362,2 from I's condition, so
|| V xz /o/ (x00 + w22 V2 V2.20// (xo))12
S Kr
+ w2 / (xo) - -Bc2r2(w1 + w22)
c²
(t + w2s (mo)
[KKr(w + wz) K²
Kr
/0n (wo) + w2 / (mo)
3Kr(ww wz).
Kr
From Equation 4 the theorem for Weighted Ensemble is proved.
23

---

Published as a conference paper at ICLR 2022
Now prove the theorem for Max-Margin Ensemble. Similarly, for any arbitrary y1, 82 such that y1 * you 3/2 * yo, we have
| a
/o0//11 (xx)
+ V 2J2 Ve
//////2 (zu))l2
A
v (1 cos CMMME (foo/ (arA) + 120 (m00)
Now we define
1- (1 CMME((1 - cos c)ss)) -008 -1/3
K" = 1+
Again, from I's condition we have A min (f (2o0), f20//a (2xo) 2 Bc2 and
V /00/11 (x0o) + V V 220/11 (2o))l2 S (1 + f2u/3 (xc0) - 23K''. KTr
1
From Equation 112 the ensemble is (K'r)-robust at point æo, i.e., the theorem for Max-Margin Ensemble is proved.
B.4 PROOFS OF SMOOTHNSSS BOUNDS FOR RANDOMIZED SMOOTHING
Theorem 2
(Model-Smoothness Upper Bound for of). Lete N of,,o² be a Gaussian random variable, then the soft smoothed confidence function Fj is (2200")ssmoois
Proof of Theorem 2 Recall that 9j ( = Ve. + E)G, where f(x + E)5 is a function only need show that for any function f _ + [0, 1]. the function f := (O0, o² Ia) is (2/oo)-smooth..
from R.d to {0, 1). Therefore, to prove that gf is (2/a )-smooth, (2moo)-smooth,
According to (Salman et al. 2019, Lemma 1), we have
[ f(t) gd
(-1 | t1
1-1x--11 dt.
f(x) =
(33)
(2mo2)d/2 1
20²
||
tll
f(()) (2no2)d/20
[(t)(x - exp
dt.
(34)
JRd
2a
To show f is )2/oo))smmoki Hessian matrix of f. Thus, we only need to show that for any unit vector u, |u Hy(x)u jul S 2/02. By the isotropy of (2)), it is sufficient to consider H (w) Now we only need to bound the absolute value of H
only need to show that V is (2/o²) Lipschitz. Let H (z) be the
(1, 0,0....,0) 0)T, where u H (a)
y (a=)
1
a
x
t
H (x)11
f(t)-
(x t) exp
dt
(2m02)di202
dx
20
Rd
1
(x) )1
|| - t t
(2ma2)d/2
f(t).
1
x²
cxp
202
dt
Rdd
1
t|2
<
(2
exp
20
dt
Rd
1
[E 21
|
12
(2T02)d/20
R2d
22
exp
2
dt
1
1
exp
dr
02
2
02
20
0
1
2
exp( (spp--//2ddtt
(35)
0²
Let I(-) be the Gamma function, we note that
1 2 exp(-1/2)dtt =
- 1.² toxp((t//2d(=""p)> V2 lm Viexp(-t)dt= = V2T(1/2) = Va/2
24

---

Published as a conference paper at ICLR 2022
and thus
Hy(ar) -
+ 0²
2 π o²
1
π 2
(36)
σ²
which concludes the proof.
Remark. The model-smoothness upper bound Theorem 2 is not limited to the ensemble model with sanembble-eeforr--mmoooinn strategy. Indeed, for arbitrary classification models, since the confidence score is in range [0, 1J. the theorem still holds. If the confidence score is bounded in (a, bj. simple scaling yields the model-smoothness upper bound 33 2(6-a)
Proposition B.4 (Model-Smoothness Lower Bound for 9f). There exists a smoothed confidence
function oj that is B-smooth if and only B
22Teo
Proof of Proposition B.4 We prove by construction. Consider the single dimensional input space R. and model f that has confidence 1 if and only input 2 0. As a result,
1
!
(t - x)²
1
t²
2
exp
20
dt
V2TO
exp
20
dt.
Thus,
dgf( Mo
1
x²
(x)
x²a
dr
v 2no
exp
20
and
d²x
2To²
exp
20
By symmetry, we study the function h(x) = x eexp(=22/10 for x 2 We have 1((x) = (1
r)) exp()=>/22) Thus, h(x) obtains its maximum at 20 1: h(ro)) = exp(-1/2) which implies that
(z)
exp(-1/2)
max
d=x
V2TO²
V2TeO2
which implies B 2
for this of per smoothness definition (Definition 4
V2Teg22
B.5 PROOFS OF ROBUSTNESS CONDITIONS FOR SMOOTHED ENSEMBLE MODELS
Corollary (Gradient and Confidence Margin Conditions for Smoothed WE Robustness). Given imput xo Rd with ground-truth label yo [C]. Let
o² o0 be Gaussian random variable. Define soft smoothed confidence Je (œ) == E. f((x + for each base model F& (1 < Kis N). The G.M is a WE defined over soft smoothed base models {gī N with weights {w;) GiMwws (Io) = yo-
(Sufficient Condition) The G MMwe is r-robust at point Do for any ys + yo.
Σ
w Vz 2o (o))
< W [g 2o/ (xo)
1 r
2r
Wj:
σ² j=1
(Necessary Condition) If G GMw is r-robust at point Lo, for any y: # yo-
N
w. V Vo (
|| S r
Σ
W
(gg
Vo (2x) +
2r
Σ Wj.
σ² j=l
Since Gi is WE defined over for G G.we- Notice that each 9f has model-smoothness bound 2/0² from Theorem 2 and the corollary statement follows.
Proof of Corollary 2
11 1
apply Theorem
directly
Corollary 3 (Gradienn and Confidence Margin Condition for Smoothed MME Robustness). Given
input To Rd with ground-truft label yo [C]. Let (00 of be Gaussian random
variable. Define soft smoothed confidence J. (x) := E.fi( + E) for either base model F, or Fz.
The G MMMuE is MME defined over soft smoothed base models (0f. (5. G (mo) yo-
25

---

Published as a conference paper at ICLR 2022
(Sufficient Condition) for any y1, U2 E [C] such that y1 # yo and y2 # yo-
(20)) + V ( (15 (o))l 1 S - (17))o// (2r0) + )0 (20
4r
02
23
then Mause is r-robust at point To-
(Necessary Condition) Suppose for any a E {wo + Ō 1|81|2 S r) for any i E {1,2}.
either Gr, (m) Yo or GP. (x) = yo- If G MMaaR is r-robust at point Do, then for any ,1, 3/2 [C] such that yı + yo and y/2 + yo.
(0) vo/m (2)) + V (55 / ya xo)ll2 1 ((gi) (x0o) + (05)
4r
+
σ 24
Since MMMME is constructed over confidences of and Øā. we can directly apply Theorem Again, with the model-smoothness bound 3 2/0² easily derive the corollary statement.
Proof of Corollary
3
C ANALYSIS OF ENSEMBLE SMOOTHING STRATEGIES
In main text we mainly use the adapted randomized model smoothing strategy which named Sewtmbll-befor-SSmooeee
(EBS). We also consider Ensemble-after-Smen Smoothing). Through the following analysis, we will show wewphhlle-beooo---oottiet generally provides higher certified robust radius than Ensemble--ffer--Soooll which justifies our choice of the strategy.
(Ensemble-afer
The Ensemble-before before-Smoothing strategy is defined in Definition strategy defined as such.
5 The Ensemblle-affer-Snooohing
Definition 6 Sinsembleeaffer-Smmotti (EAS)). Let M be an ensemble model over base models {F)) Let be a random variable. The EAS ensemble HM R + [C]] at input vy E Rd is defined as:
(x0)) == G (zo) where c= arg max gr. (2o) (20)-
(37)
kE(N]
Here, c is the index the smoothed base model selected.
Remark. In EBS, we first construct model ensemble M based on base models using WE or MME protocol, then apply randomized smoothing on top of the ensemble. The resulting smoothed ensemble predicts the most frequent class of M when the input follows distribution Eo
In EAS, we use E to construct smoothed classifiers for base models respectively. Then, for given input Ze. the ensemble agrees on the base model which has the highest probability for its predicted class.
C.1 CERTIFIED ROBUSTNESS
In this subsection, we characterize the certified robustness when using both strategies.
C.1.1 Fassemble-before-Smmoolll
The following theorem gives an explicit method (first compute L' ( (Fa) G (#o) via sampling then compute r) to compute the certified robust radius for EBS protocol. This method is used for computing the certified robust radius in our paper. All other baselines appeared in our paper also use this method.
Proposition C.1 (Certified Robustness for constructed by EBS strategy. The random variable e NO0 o² Ia). Then the ensemble G is r-robust at point D6 where
www.-bbbeooo----otnnnggg Let G be an ensemble
r r:=00
(38)
Here, (zo)) Pr. (M.(0 + + (M)
The proposition is direct application of Lemma A.I
26

---

Published as a conference paper at ICLR 2022
C.1.2 thsemblle-afee--Soootie
The following theorem gives an explicit method to compute the certified robust radius for EAS protocol.
Theorem (Certified robustness for Ensemble-after - Let HM be an ensemble con- structed by EAS strategy over base models yo H (mo)). For each i E [N], define
{Fi) The random variable e NN, o² Ia). Let
o$ - (fe (20)),, (aw)
10 (Xo) = 9/
T ==
-o (or, (2o) (mo) if Gr (zo) # you
Then the ensemble M is r-robust at point where
[ rs minie(N Pi
(39)
Remark. The theorem appears to 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., ry's 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., r, 0), the certified robust radius is strictly smaller than half of the best base model.
Proof of 5 Without loss of generality, we assume ri > r2 > TN- Let the perturbation added to Zo has L length 5.
When S TN. since picking any model always gives the right prediction, the ensemble robust.
When IN < < = the highest robust radius with wrong prediction is 6 - -ry, and we can still guarantee that model F, has robust radius at least 1i from the smoothness of function + fr, (2) (axa) (Salman et al. 2019). Since - 5 2 - 2 5 Y', the ensemble will agree on Fi or other base model with correct prediction and still gives the right prediction.
When 8 >> E suppose fN is linear model and only predicts two labels (which achieves the tight robust radius bound according to Cohen et al. (2019)) then fN can have robust radius 0 3-rr ry for the wrong prediction. At the same time, for any other model F; which is linear and predicts correctly, the robust radius at most r; Since r; - < ri 8 TI-N 8 TN. the ensemble can probably give wrong prediction.
In summary, as we have shown, the certified robust radius can be at most r. For any radius > there exist base models which lead the ensemble H (wo + ōe) to predict the label other than yo- O
r.
C.2 COMPARISON OF TWO STRATEGIES
In this subsection, we compare the two ensemble strategies when the ensembles are constructed from two base models.
Corollary 4 (Smoothing Strategy Comparison). Given MMME, a Max--Margh Ensemble constructed from base models {fa. Let No, I² Let G GMMas be the EBS ensemble, and H MAMDE be the EAS ensemble. Suppose at point Dy with ground -rrnh label yo. Gr (zu) = GG,, (Io) yo. gF. (xo) 0.5, SP. (xo) > 0.5.
Let 8 be their probability difference for class yo. i.e, 8= l9f (wo mo - De. (20)) pol Let pmiin be the smaller probability for class yo between them, ie., Puin min (oo))oo Fr. (2 We denote p to the probability of choosing the correct class when the base models disagree with each other; denote Pab to the probability of both base models agreeing on the correct class:
p = Pr (MMMEEXX0 (x0 + ++) = yo Fa (20 + +) + Fo(x0 + E) and (Fa (2t + +s) = yo or Fb(20o + + = =20)),
Pub ==
Pr (x00 + = Fb Fx + E) = y0)
We have:
27

---

Published as a conference paper at ICLR 2022
1. 1fp 1/2+ (2 (2+ 4(Pmin p TG TH-
Ifp S 1/2, TG.
Here, TG the certified robust radius of G MMMa computed from Equation certified robust radius of Manaa computed from Equation 39
38 and rH is the
Remark. Since 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 Pas 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
R 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.
Proof of Corollary 4 and Pmin = Pb.
For convenience, define pa == rr, (mo)) == Ir, (200) where Pa: P6-6
From Proposition and Theorem 5 we have
24 (Pr(MMMBB(D) + +))= =80)). TH = 2 (pa) + 4 (p=))
FG = 2
Notice that Pr. (MMME(E0 =yo) = Pab + p(Pa + Pb 2pab), we can rewrite TG
rg 24 (Pob p(Pa + Po 2pot)).
When p 1/2 + (2 4(mmn Paat)/8- since
Pa pb 5 - 2ppb
Pa Pab
p
>>
2 +
2+
A(prin Pat)
26 + 4(p, - Pab) 2
2(pa + Pb 2Pob)
Pa + ps 2pab
we have Pab + p(Po + Ph 2pab)
> Pa- Therefore, ra > o o Whereas, rn S 0/2.
2Φ (pa) = = 100-1(pp) (po). So ra > TH.
2. When - 1/2.
Pab + p(pa + pb 2pah) S Pab 1122 (pa + ps 2pab) =(pa + ppb)/2.
Therefore, rG < oΦ a ((pa + 22). Notice that Φ-1 1 is convex in [1/2, +00), so Φ -- (p-(
(pb) 2 2Φ 1 (pp + pb)p/// 2), i.e., TH TG.
D ROBUSTNESS FOR SMOOTHED ML ENSEMBLE: STATISTICAL ROBUSTNESS PERSPECTIVE
In this appendix, we study the robustness of ensemble models from the statistical robustness perspec- tive. This perspective is motivated from Lemma A. where the certified robust radius of model smoothed with Gaussian distribution E ~ (0, T²Ta) directly proportional the probability of the original (unsmoothed) model predicting the correct class under such noisc.
We first define the notation of statistical robustness in Appendix D.I then we show and prove the certified robustness guarantees of WE, MME, and single models respectively in Appendix D.2 next we use these results to compare these ensembles under both general assumptions (Appendix D.3) and more specific uniform distribution assumptions (Appendix D.4) where several findings also discussed; finally, we conduct extensive numerical experiments to verify all these findings in Appendix D.5
28

---

Published as a conference paper at ICLR 2022
D.1 DEFINITIONS OF STATISTICAL ROBUSTNESS
Definition ((s, p)-Statistical Robust), Given random variable and model F IR + [C], at point 2o with ground truth label yo. we call F (e, p)-statistical robust if Pre (F -) yo) p.
Remark. Note that based Lemma A.1 when (O of La). if F is (e, p) statisticca robust at point 2o, the smoothed model G over F is (or (p))-robuse at point Zo-
The following three definitions are used in the theorem statements in the following subsections. They be viewed the "confidence margins" under noised inputs 26 + for single model and ensemble respectively.
Definition ((e, X, --nigl Confident). Given a classification model F. If at point zu with ground- truth label yo and the random variable e, we have
f(zo E)y, A(1 f(zo + +))oo)
Pr
we call F' (s, A, single confident point æp. Definition 9 ((c, A, p)-WE Confident). Let MwE be weighted ensemble defined over base models (R)) with weights [w:){1]
If at point zo with ground-truth yo and random variable e, we have
Pr
max [CE 7so
Σ wiSilar + <)
A
(1 - fi + <)
-1- p.
(40)
i=1
call weighted ensemble MWE (e, p)- confident point Øg.
Definition 10 ((e, À, -MEE Confident). Let MMME be max-margin ensemble over {P:) If at point vo with ground-truth yo and random variable E, we have
max filo + E) S A(1 fi( + +))o)) ICC
Pr e
A iE|N)
P.
(41)
we call max-margin ensemble MMME (EMM,)E 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 - fi + =)).
To reduce ambiguity, we usualy use in WE Confident, A2 MME Confident, and Xa in Single Confident. Note that given Aι is the weighted average and X2 the maximum over X's of all base models, under the same p. \1/De < Furthermore, under the same p. \//>2 reflects the adver- sarial transferability (Papernot et al.) (2166a) among base models: If the transferability is high, the confidence scores base models are similar (A's are similar), and thus λ₁ large resulting in large /2 On the other hand, when the transferability is low, the confidence scores are diverse (X's are diverse), and thus X is small resulting in small X \
The following lemma is frequently used in our following proofs:
Lemma D.I. Suppose the random variable X satisfies E.X > 0, Var(X) < oo and for any x E Rt, Pr(X > EX x) Pr(X EX x), then
Var(X) 2(EX)²
Pr(X <0)
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.
Now we are ready to present the certified robustness for different ensemble models.
D.2 STATISTICAL CERTIFIED ROBUSTNESS GUARANTEES
The main results in this subsection Theorem 6 and Theorem 7
29

---

Published as a conference paper at ICLR 2022
D.2.1 CERTIFIED ROBUSTNESS FOR SINGLE MODEL
As the start point, we first show direct proposition stating the certified robustmess guarantee of the single model.
Proposition D.1 (Certified Robustness for Single Model), Let s be random variable. Let F be classification model, which (E, X3. sinsgee confidens. Let æy R be the input with ground-truth yo [C]. Suppose fxo + E)yo follows symmetric distribution with mean and variance s², where We have
(1 1+1g)) )-1
8
Pr(F(ao+ = -30) ( 2( - (1 + Ag 1-1
Proof of Proposition D.I
We consider the distribution of quantity Y := f(zo + E) Az [(ro + ). Since the model F is (e, Aa, -ssigle confident, with probability p. Y S (wo E) We note that since
f + y)
BY = (1 + Az)L A3 Var(Y) = (1 83)
from Lemma D.I
s²
Pr(Y 50) < 2( (1 Ag 1-1
Thus,
Pr(F(zo + yo) = 1 - Pr(F(ax + +5) # yo)
f(r + teuu <0)
1 Pr [(mo + e)no
max
,,
2 1 - Pr(Y 5)
8²
2 1 p- 2(u - (1 + \3 -
D.2.2 CERTIFIED ROBUSTNESS FOR ENSEMBLES
Now we are ready to prove the certified robustness of the Weighted Ensemble and Max-Margin Ensemble [Theorems 7).
In the following text, we first define statistical margins for both WE and MME, and point out their connections the notion of (e. Statissiiaa Robust. Then, we reason about the expectation, variance, and tail bounds of the statistical margins. Finally, we derive the certified robustness from the statistical margins.
Definition D.1 (X1; Statistical Margin for WE Mwe). Let MWE be Weighted Ensemble defined over base models { with weights {w;) V.V. Suppose MWE is (c, -a..p))WE-coofffeeee We define random variable X, which depended by random variable e:
x1(e)==11AI
Σ 1=1
wf (x0 + E)Ho X ||w||
(42)
Definition D.2 (X2; Statistical Margin for MME MMME). Let MMME be Max-Margin Ensemble defined over base models {F. J. Suppose MMME is 12. p) 110)--MMMofdeen We define random variable X2 which is depended by random variable
x2(c)= = (1 + X2) max fa <) + min fi E)go
2A2-
(43)
iE[N]
:E[N]
We have the following observation:
30

---

Published as a conference paper at ICLR 2022
Lemma D.2. For Weighted Ensemble,
Pr (Mwe(ao + =-0)=)))) yo) 2 1 - p-p Pr (Xi(e) < <0).
For Max-Margin Ensemble,
Pr (MaMe((o (5) -Va) 2 1 p Pr (X2(e) <0).
Proof of Lemma D.2 (1) For Weighted Ensemble, define the random variable X1:
(i(e): = min we|CCluu
S (xr0 + E).
Since MWE is (s,)1, 2) (.ap))------odeeen from Definition 9 with probability p, we have
N
X1(=) 2
y (f) + t) -22(1 fx + +))sa))
j=1
N
= (1 + A2)
Σ
= =X((e). w (20 + +2 11112011==x11
j=1
Therefore,
Pr( Pr(Mwe(zo+ + = yo) = Pr(Xi(s)
< <0).
(2) For Max-Margin Ensemble, define the random variable X2:
X2(c) max min N) w0(
f.u (aro + c) + min min
f /o (mo + c).
Similarly, since MMME is (E, A2, -MM--coffiieet,, from Definition 10 with probability 1 p. have
X2(c)= 2 max (fi(zu 2) A2(1 fo + E) iE[N]
min (fi + E) -22(1 fi(20 + E)
iE(N]
= (1 + X2)
max felang c) + min fi(x0 + k)g0 2)² 82(e). iE(N)
vE[N]
Moreover, from Lemma
we know B.I
Pr(M(zo + yo) Pr(X2(s) 2 1
Pr( < 0).
As the result, to quantify the statistical robustness of two types of ensembles, we can analyze the distribution statistical margins X, and X2.
Lemma D.3 (Expectation and variance X1 and Xz). Let X, and X₂ be defined by Definition D.1 and Definition D.2 respectively. Assume (i( 1. are i..dd. and follow symmetric distribution with mean and variance s?. Define of Var(min:e|M] fi(wo =.))). We have
E (x) -(1 + A1)l - -
Var 81(() = (1+ + A1 8² |
E (xx -2(1 + 22221 -222,
Var x2(2) - 4(1 + 233
Proof of Lemma D.3
(X1(E) = (1 A1)
Σ
Ew, (x + t) -1llwol11 = (1 A1)ll - >
1=1
( (1+ 11) Σ
w Var(f + +))))) (1 A,) 23 1
31

---

Published as a conference paper at ICLR 2022
According to the symmetric distribution property of (fi(2z + e) 1i we have
x2(e)) = E[1 + X2)
max Si( + E) min iE(N]
fi + e)1o 2\₂
iE(N)
2(1 + 22) 222.
Also, due the symmetry, we have
Var
min fi + E)vo) = [E[N]
-Var max fi + +0)0o) ) s3. [iE|N]
As result,
Var Xx((e X2)² 45².
From Lemma D.3 now with Lemma D.I we are ready derive the statistical robustness lower bound for WE and MME.
Theorem 6 (Certified Robustness for WE). Let be random variable supported on R Let MWE be a Weighted Ensemble defined over [F:) with weights {wa) The MWE is (e, p)) confident. Let 2o E IRd be the input with ground-trutt label yo [C]. Assume {fi E) f F==
the confidence scores across base models for label yo, are ii.d and follow symmetric distribution
with mean y and variance s², where ps > (1+ 1 We have
w
Pr(MwE(an (2o +E) =30) 121 11-pp
(44)
2
H (1+
Theorem (Certified Robustness for MME). Let be random variable. Let MMME be Max- Margin Ensemble defined over {F. The MMME (s, X2, PMME confident. Let Do E Rdd be the input with ground-truce truth label yo E [C]. Assume {fe(wo + E) Ti=1 1 the confidence scores across base models for label yo, are i.i.d. and follow symmetric distribution with mean where Ju > (1 + 11 2 Define 07 Var(min,e(N1] Ji(mo + e) have
$7
Pr(MMME(Rs + + = -Bo) 2
(45)
2 n
(1+
Proof of Theurems and 7 Combining Lemmas D.I to D.3
we get the theorem.
Remark. Theorems and provide two statistical robustness lower bounds for both types of ensembles, which is shown to be able to translate to certified robustness.
For the Weighted Ensemble, noticing that X; is the weighted sum of several independent variables, we can further apply McDiarmid's Inequality to get another bound
|
( (1-(1+XX (#-(1+
Pr(Mwe(#n + +&) yo) 2 1 exp
which tighter than Equation 44 when || am 2/2 is large. For average weighted ensemble, | /1/////w/// = N. Thus, when N large, this bound is tighter.
Both theorems are applicable under the i.i.d. assumption confidence scores. The another assumption > max((1 + x, / (1 + Xラ ー)ー} insures that both ensembles have higher probability of predicting the true class rather than other classes, i.c., the ensembles have non-trivial clean accuracy.
D.3 COMPARISON OF CERTIFIED ROBUSTNESS
We first show and prove an important lemma. Then, based on the lemma and Theorems and we derive the comparison corollary.
32

---

Published as a conference paper at ICLR 2022
Lemma D.4. For μl X1; X2, C > O, when max(X1/(1 + A2/ + )2)) < S 1, and C < 1, we have
11 - (A7 +1) 11 (27 +1)-1 <C =
| (0-1(1
X2
+ +1 -1 -1) (46)
)
< 2²²
(--
1 22
A2
Proof of Lemma D.4
" - (1₂ + 1)
11 (Mi +1)-1 <C
C
A2 +1+1 x >
(1
X1/D2
C-1
(1(C--11 1)
A2
11/122
12 +1
\1
\/ x-++1 1
1+
C-1
11
~/² (-1
\ + + m) )
A2
C-1
17 1- 11 +
22
A2
C-1
1 - --x5++1 +1 - 11
(0-1
(14 14- 1 x2
d2 ) +1 -p) ) {²)² -1 1)
-1 11)
-1)
A2
Now can show and prove the comparison corollary.
Corollary 5 (Comparison of Certified Robustness). Let be a random variable supported on Rdd Over base models (F,) (F.) let MAME be Max-Margin Ensemble, and MwE the Weighted Ensemble with weights { {w; \ Let æg E Rd be the input with ground label yo E &CC) Assume (Ji(zn + ) the confidence scores across base models for label yo. are i.idd and follow symmetric distribution with mean p and variance s², where p max --, 1-13. Define 8 Var(mmin,e(]] fi + E) and assume 8f < 8.
When
A1
25 ((s)
(1-(1+ +1 +1- 11 -1)
(47)
22
for any weights { MwE has higher certified robustness than MMME-
When
((ri)) s 1--0=ppp (w- (1+ +1 11-11 -m) -
-1 -1))
A1
(Nos
(48)
X2
for any weights {w:) MMME has higher certified robustness than MWE. Here, the certified robusiness is given by Theorems and
33

---

Published as a conference paper at ICLR 2022
Proof of Corollary
5
(1) According to Lemma D.4
we have
A1
8
-- (1 11) + -1- +1-n)=-11 -1)
-1 -1)
< 22
A2
85
1
(A₂² +1 31
/
(Ai
+1)-1
w 18 (A₂ + 1)-1 81
+1) <
1/ l (A7
8²
of
( n 1--
2 2m (1+
According to Theorems 6 and we know the RHS Equation (44) is larger than the RHS in Equation 45 i.e., MWE has higher certified robustnesss than MMME-
(2) According to Lemma D.4 we have
-1
A1
> 121
VNss (I (1 X2 -) + 11 -1
8
A2
1
(A7 + 1)
N88
(AT +1)-1
/ (A²² 1 + 1)-1
81
|
(Xi
+ +1)-1
8
[
g²
87
1 (1+ (1+
2 (1 + (
According to Theorems 6 and we know the RHS Equation (45)
larger than the RHS in Equation 44.. i.e., MMME has higher certified robustnesss than MWB-
Remark. (1) Given that \r/A2 reflects the adversarial transferability among base models Ap- pendix D.I. the corollary implies that, MME is more robust when the transferability is high; WE is more robust when the transferability is low.
(2) As we can observe in the proof, there is a gap between Equation (47) and Equation (48) when / lies in between RHS of Equation (47) and RHS of Equation 448). it is undetermined which ensemble protocol has higher robustness. Indeed, this uncertainty is caused by the adjustable weights {w;) ) of the Weighted Ensemble. If we only consider the average ensemble, then this gap is closed:
((75)) [NNs) (n-(1 (1+ + 11 -1) -1)
A1 MAME more robust E Ag Mwe more robust
(3) Note that we assume that sy < 8, where s2 is the variance of single variable and 8? the variance of minimum of N i.idd. variables. For common symmetry distributions, along with the increase of N, s shrinks in the order of B1/NBB) where B E (0, 2]. Thus, as long as N is large, the assumption 8 < s will always hold. An exception is that when these random variables follow the exponential distribution, where 8y does not shrink along with the increase of N. However, since these random variables are confidence scores which are [0, 1), they cannot obey exponential distribution.
D.4 A CONCRETE CASE: UNIFORM DISTRIBUTION
As shown by Saremi& & Srivastava (0200) (Remark 2.1), when the input dimension d is large, the Gaussian noise (10 & Unif(o 1), i.e., my + is highly uniformly distributed on
34

---

Published as a conference paper at ICLR 2022
the (d 1)-sherre centered at zy- Motivated by this, we study the case where the confidence scores (f + e)yo 1 are also uniformly distributed.
Under this additional assumption, and both ensembles more concrete.
further make the certified robustness for the single model
D.4.1 CERTIFIED ROBUSTNESS FOR SINGLE MODEL
Proposition D.2 (Certified Robustness for Single Model under Uniform Distribution). Let be a random variable supported on Rd. Let F be a classification model, which (e, A3, -isingl confident. Let no E IRd be the input with ground-truth yo E [C]. Suppose (wo E)vo is uniformly distributed in (a, b). We have
11((1+ 111+11111
Pr(F(xo +) 20) - p- clip
a
where clip(x) max(min(( 1),
Proof of Proposition D.2
We consider the distribution of quantity ; S(ro + +) da(1
[(ro )) Since the model is (c, λa, p)-siglee confident, with probability p, Y S f(zo + g) maxy, 7 f(zo + E)yy. At the same time, because f(zo c)yo follows the distribution U([a, b)).
Y = (1 + Aa)5 E)9O A3
follows the distribution U([(1 Az)a A3, (1 A²)b Aa))- Therefore,
As - (1 (1+)3)a (1+ As)(b (a)(6-a)) a)
Pr(Y (0) = clip
As the result,
s s clip ( (A: (1-(1+20p (As-11+20)) Az)a
Pr [ + E)vo
max b,E(Cl,,
f(zo + t =0)
(1+ As)(b a)
which is exactly
PF + = yo) 2 p- clip ( as 11+ (
(11(L a
11-p clip
(1+ a)
b b-a a
D.4.2 CERTIFIED ROBUSTNESS FOR ENSEMBLES
Still, we define (E) and (= according to Definitions D.I and D.2 Under the uniform distribution assumption, we have the following lemma.
Lemma D.5 (Expectation and Variance of X, and X2 under Uniform Distribution). Let X1 and X₂ be defined by Definition D.I Definition D.2 respectivy.... Assume that under the distribution of the base models' confidence scores for true class (f( + E) I are pairwise i..dd and uniformly distributed in range (a, b). We have
E (x) {1 +1)+)//lll1ee + b))--1llull. Var X
-1 (1
1
11)2112011330 11100133--a3)) a)²,
12
4
E (x2( (1+ A2) + -222,
Var (1+)))(11))))) N+1 N N
(6 (b-
Proof of Lemma D.5
We start from analyzing X,. From the definition
{i(e) (1 (1+Ai)
Σ wi f E) - Ar||w|]1
42
35

---

Published as a conference paper at ICLR 2022
where (fi(zu + c) Jim are iid. variables obeying uniform distribution U((a,, 6)),
EXi(E) = (1 X1) 1))1(wl
a a+b
\11/w011
_/1 =1+ +1)l w/I1 + - X1 ////1/1,
2
2
Var Xi(e)= (1 + X1 )
Σ
w
a)² 12 (1 A1) 1 [B a)².
12
j=1
Now analyze the expectation of Xz. By the symmetry of uniform distribution, we know
E (2(EE) (1 A2) 2E fi + E) 22 (1 (2) + 6) -22..
To reason about the variance, we need the following fact:
Fact D.1. Let X1, X2, Xn be uniformly distributed and independent random variables. Specift- cally, for each Siis nu 24 u(aa, b)). Then we have
1
2
Var
min xx Isisn
= Var
max X3 1sish
(b - a)²
(b-a)²
n +
1
n2
+
2
n2 n+1
Observing that each i.i.d. fi(20 + E)yo exactly identical x; Fact D.I we have
Var max fi + c)o + min fi(2ro + +),0 xE[M]
S
(b - a)a N W+1
iE[N]
N +
N N+
Therefore,
4
2
1 1 (6- a)- N+1
51+ Var 5 N ++
N +2
Proof of D.I From symmetry of uniform distribution, we know Var Amininsss x.) Var (maxigign X,). So here we only consider Y == minigign Xy. Its CDF F and PDF f can
be easily computed:
-1-(b-a) f(v) = F'(()) = n (b y)n -1- b- 1-1---60
(b- -1-
Fly) = 1 Pr (minx; 2 21) =
(b - a)n wherey y E (a, 6).
Hence,
EY= = lf(y)dy y(b 4)th + (n + 1)-1(b - 8) n+1
= a +
(b a)n
b
+ 1
EY Y f 8 f = 1d my (b 4)n dy
(b a)m
b 1
y
y
2
ydy
b
0
b 1
10
6
2
(b 8) n+1
V + /
(b n)
6
11
(b - a)m dy
b-a a
7L + 1
(b a)n
b b- y
6
2
8) n+1
8) +t)
16
b b-a
11
7L + 1
(b a)m
n (b a)m
2
d
(b
a)a +
(b a)².
n
(n +
1)(n + 2)
As the result, VarY Y EY² (EY)²
(b a)²
n
n
Now, similarly, we use Lemma t. derive the statistical robustness lower bound for WE and MME, We omit the proofs since they direct applications of Lemma D.5 Lemma D.T and Lemma D.2
36

---

Published as a conference paper at ICLR 2022
Theorem (Certified Robustness for WE under Uniform Distribution). Let MWE be Weighted Ensemble defined over [F. with weights { {wr)i=1- Let Dy IR' be the input with ground-trune label yo E [C). Let & be a random variable supported on TR. Under the distribution of e, suppose {fi(zo + No ii are i..dd. and uniformly distributed in [a, b). The MWE is (E, X1, A1, p)- confident. We have
Assume a+b
14x1""
K2
Pr(MWE(10) + yo) 2
12
(49)
b a
where
dw
K1
w
1+A1
Theorem (Certified Robustness for MME under Uniform Distribution). Let MMME be a Max- Margin Ensemble over { Let we Rd be the input with ground-truth label yo [C], Let be random variable supported Fd. Under the distribution of suppose {f((zo + IN li=1 are i.id
and uniformly distributed in (a, b). MMME is (c, (2,22 PM-ME confident. Assume a+b 1425
We
have
Cx
Pr(MMME(20 + 30)
2 1
(50)
2 2
1
b
where ON N
Kg
N
N+1
0+h
1+11
D.4.3 COMPARISON OF CERTIFIED ROBUSTNESS FOR ENSEMBLES
Now under the uniform distribution,
also have the certified robustness comparison.
Corollary (Comparison of Certified Robustness under Uniform Distribution). Over base models {F)) let MMME be Max-Margin Ensemble, and MWE the Weighted Ensemble with weights {w;) Let 2n E Rdd be the imput with ground-truth label yo E [C]. Let a random variable supported on IRd. Under the distribution of E, suppose [fi(zo + y) \N are i..dd and uniformly distributed with mean Suppose MwE is (e. A1. M.Pp)-We -EE confident, and MAME is (E, X2. MMME
confident. Assume >> max
[+
1+47
When
(IN
-1 11
N 2
X2 < X5²
+1
+1
-
(51)
6N
1
A
MwF has higher certified robustness than MaMM..
When
-1
A1 >>>0
(*+1V
N N+11
N +
+
11
-1
(52)
A2
6
1 +
X
MMMe has higher certified robustness than MwF.
When
-2
N N
2
(53)
p(1+X,
for any X1. MMME has higher or equal certified robustness than MWE-
Here, the certified robustness is given by Theorems
Proof of Corollary D First, notice that uniform distribution with mean y can be any distribution U(aa, bl) where (a b)/2 μ. We replace by (a + 22/2.
Then (1) and (2) follow from Lemma D.4 similar the proof of Corollary
37

---

Published as a conference paper at ICLR 2022
(3) Since
N > 6 (1
1 1a11 +
N +2
x 2イ5)
-2 -
+1 +1-1 14
<1
6
1 12
N N
2 1
+ +1-
1,
6
1+ X2
the RHS of Equation 52 is smaller than O. Thus, for any \1, since \1/ 0, the Equation (48 satisfied. According to (2), MMME has higher certified robustnesss than MWE-
Remark. Comparing to the general corollary (Corollary 5). under the uniform distribution, we have an additional finding that when N is sufficiently large, we will always have higher certified robustness for Max- Mar-Mn 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 quantity Var X (e) for Weighted Ensemble (211NN,, while for Max- Max-Margin Ensemble is O(1/N²). As the result, when N becomes larger, Max-Margin Ensemble has higher certified robustness.
We use uniform assumption here to give an illustration in specific regime. We think it would be an interesting future direction to generalize the analysis to other distributions such as the Gaussian distribution that corresponds to locally linear classifiers. The result from these distribution may be derived from their specific concentration bound for maximum/minimum i.i.d. random variables as discussed at the end of Appendix D.3
D.5 NUMERICAL EXPERIMENTS
To validate and give more intuitive explanations for our theorems, we present some numerical experiments.
D.5.1 ENSEMBLE COMPARISON FROM NUMERICAL SAMPLING
As discussed in Appendix D.I A /2 reflects the transferability across base models. It is challenging to get enough amount of different ensembles of various transferability levels while keeping all other variables controlled. Therefore, we simulate the transferability of ensembles numerically by varying Aι / (see the definitions of Xι and )a in Definitions confidence scores {.f((z) + y.. and (max)e[C]:>// f((20 + ε)y} } under determined x and X2. For each level of Xı />2, with the samples, we compute the certified robust radius r using randomized smoothing (Lemma A.I and compare the radius difference of Weighted Ensemble and Max-Margin Ensemble. According to Corollary 5 we should observe the tendency that along with the increase of transferability A Max-Margin Ensemble would gradually become more certifiably robust than Weighted Ensemble.
9 and 10), and sampling the
Figure 4 verifies the trends: with the increase \1 A2, MME model tends to achieve higher certified radius than WE model. Moreover, we notice that under the same Å1/A2, with the larger number of base models N, the MME tends to relatively more certifiably robust compared with WE. This because we sample the confidence score uniformly and under the uniform distribution, MME tends to be more certifiably robust than WE when the number base models becomes large, according to Corollary 6
The concrete number settings of X1, A2, and the sampling interval confidence scores are entailed in the caption of Figure 4
D.5.2 ENSEMBLE COMPARISON FROM CERTIFIED ROBUSTNESS PLOTTING
In Corollary 6 we derive the concrete certified robustmess 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 5 we plot out such certified robust radius for the single model, the WE, and the MME.
38

---

Published as a conference paper at ICLR 2022
Certified Robustness Comparison with
Certified Rebustness Comparaon with N
Certified Robusdmess Comparison with
afterencc contires (101L3
0.0
0.0
-0.2
-0.3
-0.4
Sugres
-6.6
-0.6
NNE
MHE
(a) # of base models N 3
(b) # of base models N 10
(c) # of base models N 20
Figure 4: Signed certified robust radius difference between MME and WE by / under different numbers of base models N. Here we fix 22 to be 0.95 and uniformly sample A 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).
Concretely, in 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)-WE confident; the Max-Margin Ensemble is (s, A2, 0.01)-MME confident; and the single model is (3, MMME confident. We guarantee that A < As S X2 to simulate the scenario that ensembles are based on the same set of base models to make fair comparison. We directly apply the results from our analysis (Theorem 8 Theorem 9 Proposition D.2) to get the statistical robustness for single model and both ensembles. Then, we leverage Lemma A. to get the certified robust radius (with = 1.0, N = 100000 and failing probability a = 0.001 which are aligned with realistic setting). The araxi is the number of base models N and the y-axis is the certified robustness. We note that N is not applicable to 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 O 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 N is large, which conforms to our Corollary [ Note that the left sub-figure has smaller transferability \1/Ag and the right subfigure has larger transferability A1/ /2, it again conforms to our Corollary 5 and its following remarks in Appendix D.3 that in the left subfigure the Weighted Ensemble is relatively more robust than the Max Max-Margin Ensemble.
D.5.3 ENSEMBLE COMPARISON FROM REALISTIC DATA
We study the correlation between transferability x A2 and whether Weighted Ensemble or Max- Margin Ensemble is more certifiably robust using realistic data.
By varying the hyper- apper-parameters 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.e., for about half of the test set samples, WE more robust; for another half, MME is more robust. We collect 1, 000 test set samples in total. Then, for each test set sample, compute the transferabilityy A and whether WE or MME has the higher certified robust radius. We remark that x and X2 are difficult to be practically estimated so we use the average confidence portion as the proxy:
For WE,
\ E max y, E(C],, Au ΣN wiff + E)us
ΣN w,(( f( + E)
For MMF,
max y, #uo fi + E)ys
A2 = E. max
[E[N]
(1 fi(w0 + E)
39

---

Published as a conference paper at ICLR 2022
Certifie Comparienn
0.2, 0 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
10
15
Base Moders (N)
of Baso Modelss (N)
(a) [a, [0.2, 0.3].
0.29, A2
(b) [a, b]
[0.3, 0.4],
0.48,
0.31, 0.30.
0.50, Aa 0.49.
Figure 5: 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 r-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-01)-Wr confident; the Max-Margin Ensemble (shown by green líne) is (c, A2, 0.000.00-MMM confident; and the single model (shown by red line) is (c, Aa, 0.01)-MMEE confident.
1.-
ABC 0.65
The Poobve 52ta
0.2
0.0
02
0.3
1.0
Figure 6: ROC curve of the [[MME has higher certified robustness] classification task with the threshold variable X.
Now we study the correlation between
X A
RHS of Equation (48) and
[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, find that X and Y apparently positively correlated since AUC 0.66 > 0.5, which again verifies Corollary 5 We remark that besides X, other factors such as mon-symmetric non-i.i.d confidence score distribution may also play role.
Closing Remarks. The analysis in this appendix mainly shows two major findings theoretically and empirically: (1) MME is more robust when the adversarial transferability is high; while WE is more robust when the adversarial transfcrability is low; (2) each fi(zo + E)s, follows uniform distribution, when number of base models N is sufficiently large, the MME is always more certifiably robust. Our analysis does have limitations: we assume the symmetric and i.id. distribution of f( E)
more strict uniform distribution derive these findings. Though they model the real-world scenario in some extent as our realistic data results show, they are not perfect considering the transferability among base models and boundedness of confidence scores. We hope current
40

---

Published as a conference paper at ICLR 2022
analysis open angle of theoretical analysis of ensembles and leave general analysis as the future work.
E ANALYSIS OF ALTERNATIVE DESIGN OF DRT
In the main text, we design our DRT based on GD Loss
(aD( a p/o/v1 (mo) + Valj
po0lvs (20))l2
(
and CM Loss
CCM((1))) = S: (3) /00 (z 13 2/ (wz).
TT
Following the convention, we apply Gaussian augmentation to train the models, i.e., replacing zo by 2o + where e ~ (0, o²Ia) Equation (9) and Equation (10). We apply these two regularizers to every valid base model pair (Fi, F)), where the valid pair means both base models predict the ground truth label yo: (z + E) = F (20 + E) = yo-
One may concern that in the worst case, there could be ( valid pairs, i... O(N2) regularization terms in the training loss. However, we should notice that each base model F; only appears in O(N) valid pairs. Therefore, when N large, we can optimize DRT by training iteratively, i.e., by regularizing each base model one by one to save the computational cost.
An alternative design inspired from the theorems (e.g.. Theorem D to use overall summation instead of pairwise summation, which directly correlates with I, (Equation (6))
N
CGD(
///
(2o)
(54)
i=1
N /v0 (20).
CCM((E))
(55)
Although this design appears to be more aligned with the theorem and more efficient with O(N) regularization terms, it also requires all base models F; to have the same runner-up prediction y/ as observed from both theorem and intuition (otherwise diversified gradients and confidence margins are for different and independent labels that meaningless to jointly optimize). It is less likely have all base models having the same runner-up prediction than a pair of base models having the same runner-up prediction especially in the initial training phase. Therefore, this alternative design will cause fewer chances of meaningful optimization than the previous design and we use the previous design for our DRT in practice.
F EXPERIMENT DETAILS
Baselines. We consider the following state-of-the-art baselines for certified robustness: (1) Gaussian smoothing (Cohen et al. 2019) trains a smoothed classifier by applying Gaussian augmentation.
2. MACER (Zhai al. 2019): Adding the regularization term maximize the certified radius
(2) SmoothAdy (Salman et al. 2019) combines adver- sarial training with Gaussian augmentation. (3) MACER (Zhai al. 2019 improves single
R = (PA PB) on training instances.
model's 'ss certified robustness by adding regularization terms to minimize the Negative Log Likelihood (NLL) between smoothed classifier's output gi gF(x)) and label y, and maximize the certified radius o² Ia) and of is as defined in Equation (3) (4) Stability (Li et al., 2019) maintains the stability of the smoothed classifier
R - (gf
(max, su gf (xrr)r)) )), where ~ (N
OF by minimizing the Rényi Divergence between gF(x) and gF(x E) where (0, o oa)a). (5) SWEEN (Liu et al. 2020) builds smoothed Weighted Ensemble (WE), which the only prior work computing certified robustness for ensemble to our knowledge.
Evaluation Metric. We report the standard certified accuracy under different L2 radii r's as our evaluation metric following Cohen et al. (2019), which is defined as the fraction of the test 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 is intractable, report the approximate certified
41

---

Published as a conference paper at ICLR 2022
test accuracy (Cohen al. 2019) sampled through the Monte Carlo procedure. For each sample, the robustness certification holds with probability least 1 a. Following the literature, we choose 0.001, Ro 100 for Monte Carlo sampling during prediction phase, and n 10yh for Monte Carlo sampling during certification phase. On MNIST and CIFAR-10 we evaluated every 10-th image in the test set, for 1, 000 images total. On ImageNet evaluated every 100-th image in the validation set, for 500 images total. This evaluation protocol is the same as prior work (Cohen et al.
2019
Salman al. 2019).
F.1 MNIST
Zhai ct al., 2019), in each batch, each training sample is Gaussian augmented twice (augmenting more times yields negligible difference Salman al. (2019) show). We choose Gaussian smoothing variance E (0.25, 0.5, 1.0} for traiingg and evaluation for all methods. For SmoothAdy, we consider the attack be 10-step L2 PGD attack with perturbation scale 8 1.0 without pretraining and unlabelled data augmentation. We reproduced results similar to their paper by using their open-sourced code
Baseline Configuration. Following the literature (Salman et al., 2019: Jeong & Shin 2020;
Training Details. First, we use LeNet architecture and train each base model for 90 epochs. For the training optimizer, we use the SGD-momentum with the initial learning rate a 0.01. The learning rate is decayed for every 30 epochs with decay ratio y = 0.1 and the batch size equals to 256. Then, we apply DRT finetune our model with small learning rate a for another 90 epochs. We explore different DRT certified accuracy on each radius r among all the trained ensemble models.
P1, P2 together with the initial learning rate a, and report the best
Table Certified accuracy of (RT- P2) under different radii r on MNIST dataset. Smoothing parameter = 0.25. The grey rows present the performance of the proposed DRT approach. The brackets show the base models we use.
Radius
P1
P2
0.00
0.25
0.50
0.75
Gaussian (Cohen al. 2019)
99.1
97.9
96.6
93.0
SmoothAdv
(Slman 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
MMF (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 (SmoothAdy)
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
Trend of Certified Accuracy with Perturbation Radius. We visualize the trend of certified accu- racy along with different perturbation radii on different smoothing parameters separately in Figure and Figure For each radius r, we present the best certified accuracy among all the trained models. We can notice that while simply applying MME or WE protocol could slightly improve the certified accuracy, DRT could significantly boost the certified accuracy different radii.
Average Certified Radius, We report the Average Certified Radius (ACR) (Zhai et al. 2019 ACR
Sie. Σ
(r.)) R(x, y), where Swa refers to the test set and R(x, v) the certifed radius testing
https://gght thw.. com Hadi httaa///aammmcccchaaaaaaeeeaaaa
42

---

Published as a conference paper at ICLR 2022
Table 5: Certified accuracy of DRT-(P1, P2) under different radii r on MNIST dataset. Smoothing parameter o = 0.50. The grey rows present the performance of the proposed DRT approach. The brackets show the base models we use.
P5
P2
0.00
0.25
0.75
1.00
1.75
Cianssian Cahen et al 2019
99.0
97.7
96-4
94.7
90.0
83.0
68.2
43.5
SmoothAdd Salman 2015
98.6
98.0
97.0
95.4
93.0
87.7
80.2
66.3
(Caussaan)
99.0
97.7
90.5
45.3
0.2
2.0
99.1
98.4
97.2
95.2
92.6
86.5
74.3
54.1
5.0
99.1
98.6
97.1
95.5
92.6
86.2
74.0
54.3
92.1
0.5
5.0
99.0
98.2
97.3
95.1
91.6
84.8
73.7
52.4
10.0
99.1
98.1
97.1
95.0
91.8
85.7
73.3
51.4
95.2
92.2
54.4
0.1
98.8
98.0
96.8
94.7
91.5
86.5
75.5
59.1
DRT MME (Gaassian)
0.2
98.9
98.1
96.9
95.1
92.1
85.8
76.1
56.4
0.5
98.7
98.1
95.2
92.1
85.8
76.0
56.9
2.5
99.0
98.3
97.0
95.1
92.4
85.8
75.7
57.0
5.0
99.0
9%
96.8
95.0
91.9
85.5
74.4
54.6
10.0
99.0
98.2
96.9
95.1
91.9
85.5
74.6
51.5
98.7
95.1
91.7
39.8
80.0
5.0
98.5
97.7
96.5
94.99
91.9
85.9
766.
59.3
25.0
98.9
98.0
96.9
94.9
92.2
85.7
76.5
58.3
MME (SmonthAdr)
58.6
93.2
S5.1
67.5
0.5
98.4
97.8
97.0
95.5
92.7
87.7
80.9
67.9
0.1
1.0
98
97.9
97.0
95.5
92.9
88.
80.8
67.2
98.5
93.1
0.5
98.4
97.7
97.2
95.3
92.3
87.7
79.3
68.4
0.2
2.0
98.4
98.4
97.8
97.6
97.1
97.1
95.2
95.3
93.0
92.3
87.8
80.2
68.3
67.7
10.0
98.4
97.8
97.1
95.3
92,9
88.5
81.0
67.6
0.3
10.0
5.0
98.5
98.4
97.7
97.5
97.1
95.2
95.0
92.6
92.4
88.5
87.7
79.7
68.1
68.3
DRT MME (SmoothAdv)
0.5
5.0
2.0
98.5
98.4
97.5
97.3
96.6
96.9
94.6
94.3
91.6
92.0
87.5
86.7
80.1
79.5
68.6
67.8
0.5
97.7
96.8
95.5
92.5
89.6
84.1
76.7
66.3
97.9
92.6
89.7
0.1 95.4
93.3
91.2
88.1
83.8
76.8
68.3
59.9
0.2
95.5
93.7
90.9
87.7
82.0
75.7
68.7
59.6
95.0
93.3
82.6
2.5
94.6
92.9
90.1
86.3
81.6
76.0
69.6
62.5
5.0
94.3
93.1
90.0
86.1
81.9
76.3
70.0
63.6
10.0
94.9
93.4
87.3
83.2
65.9
80.0
87.7
75.0
70.5
50.5
5.0
88 5
85.1
81.0
76.8
71.4
67.4
60.6
$2.1
W.F. (Gaussian)
19.0
97.8
901.6
84.5
48.2
0.2
2.0
99.2
98.4
97.2
95.2
V2.5
86.2
74.3
53.5
5.0
99.1
98.6
97.
95.3
92.6
86.4
74.2
54.4
2.0
99.2
98.3
97.4
95.6
92.1
86.5
74.7
55.3
5.0
99.0
95.1
91
84.8
73.7
52.5
10.0
99.1
98.2
97.1
95.1
91.7
85.4
73.5
51.00
5.0
99.1
98.2
97.2
95.2
92.2
85.9
75.1
55.3
98.8
94.8
91.6
59.0
DRT WE (Gaussian)
0.2
98.8
98.1
97.0
95.0
92.1
86.0
75.7
56.8
10.0
0.5
98
98.1
96.9
95.2
92.2
86.0
76.2
57.0
2.5
98.1
92.4
56.3
5.0
99.0
98.1
96.9
95.0
91.8
85.5
74.5
55,0
10.0
99.0
98.1
96.9
95.1
91.9
85.7
74.3
54.4
2.5
98.7
97.9
96.7
95.1
91.8
86.2
75.5
60.1
80.0
5.0
98.4
97.8
96.8
95.0
91,9
86.2
75.6
60.2
25.0
99.0
9%
96.9
94.9
92.1
K5.9
76.7
5%.4
WE (SmmothAdv)
196.7
98.0
93.3
93.4
K8.2
67.9
0.5
98.4
97.88
97.0
95.55
V/2.7
87.8
80.6
68
0.1
1.0
98.5
97.9
97.0
95.5
93.1
85.0
81.2
67.7
5.0
98.5
98.2
97.0
95.4
93.3
88.5
81.4
68.6
98.4
97.7
97.2
95.4
92.3
87.6
79.7
6800
0.2
2.0
98.4
97.6
97.1
95.3
92.3
87.8
80.6
68.1
5.0
98.4
97.9
97.1
95.1
93,0
88.2
80.4
69 1
10.0
98.3
92.9
0.3
5.0
98.4
97.5
97.1
95.0
92.4
87.9
79.9
69.3
10.0
98.4
97.7
97.0
95.2
92.6
88.4
81.1
68.2
98.4
97.3
94.3
91.8
86.7
DRT WE (SmootlAAde)
5.0
98.4
97.5
96.9
94.7
92.0
87.7
79.7
67.7
0.5
97.8
96.8
95.4
92.3
89.7
84.1
77.0
65.9
1.0
1.0
97.9
96.6
95.6
92.7
89.8
84.4
77.4
66.2
95.3
93.5
91.2
88.7
83.8
76.8
68.9
60.1
0.2
95.4
93.8
91.9
88.1
K3.2
76.6
69.1
59.9
10.0
0.5
95.1
93.5
90.9
87.7
83.6
76.6
69.1
59.8
94.8
82.1
5.0
94.4
93.3
90.1
86.6
82,0
75.8
700
63.2
10.0
94.7
93.3
90.5
86.8
82.5
77.2
71.8
65.6
87.8
83.1
67.7
47.0
5.0
88.4
84.2
79.9
75.3
69.3
63.7
56.5
48.7
43

---

Published as a conference paper at ICLR 2022
Table 6: Certified accuracy of DRT-(P1, P2) under different radii r on MNIST dataset. Smoothing parameter 1.00. The grey rows present the performance of the proposed DRT approach. The brackets show the base models we use.
Radius r
P1
Pr
0.00
0,25
0.50
0.75
1.00
1.25
1.50
1.75
2.00
2.25
2.50
Gaussian (Coben al. 20191
96.5
91.1
87.0
80.2
71.
46.6
33.0
20.5
11.3
SmoothAdv Saman et at. 2019
95.3
93.5
89.3
85.6
80.4
72.8
63.9
54.6
43.2
34.3
24.0
MME (Gaussian)
96.4
94.8
73.5
61.0
48.8
34.7
23.4
12.7
2.0
96.0
93.9
90.1
86.3
80.7
73.2
63.0
52.0
38.9
26.9
15.6
5.0
95.8
94.1
90.0
86.6
80.4
72.9
62.4
51.3
40.0
27.8
16.5
85.8
80.0
72.7
62.9
52.0
39.8
28.5
17.6
DRT MME (Gaussian)
0.5
91.3
89.7
85.6
78.8
73.3
65.8
59.1
52.2
43.9
36.0
29.1
2.5
92.5
90.2
87.7
82.0
76.3
69.6
60.7
52.8
43.4
35.4
26.0
5.0
93.2
90.6
88.1
82.9
78.1
70.6
62.3
52.5
43.3
34.4
23.8
MME (SmoothAdv)
95.4
93.4
89.3
86.1
80.7
73.1
65.0
55.0
44.3
35.0
23.2
79.4
36.6
27.3
0.2
5.0
94.1
91.6
88.9
84.4
79.3
72.3
63.2
54.2
46.1
36.9
28.5
2.0
92.8
91.3
87.7
83.2
77.3
71.2
62.2
53.3
45.5
37.0
29.7
0.5
DRT MME (SmoothAdv)
5.0
92.5
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
82.2
76.5
35.2
29.2
5.0
87.6
83.3
78.8
73.1
67.4
61.8
56.2
50.5
44.9
38.4
32.8
10.0
20.0
82.7
79.6
75.3
72.0
67.9
63.3
58.6
51.1
46.6
40.3
34.7
WE (Gaussian)
91.3
87.7
49.0
35.2
23.7
12.9
2.0
95.9
93.9
90.2
86.3
80.7
73.2
63.2
51.9
38.6
27.0
15.5
0.5
95.9
94.1
$6.4
$0.4
73.1
62.3
51.7
39.8
27.5
16.4
DRT WE (Gaussian)
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
91.3
89.8
85.9
79.0
73.4
65.5
59.2
52.2
43.9
35.4
28.8
76.2
43.5
35.8
26.8
5.0
92.9
90.7
88.0
82.7
78.1
70.5
62.3
$2.6
43.1
34.5
24.4
WE (SmoothAdv)
95.2
93.4
89.4
S6.2
13.3
64.8
55.1
44.7
35.2
24.9
2.0
94.2
91.9
88866
84.5
79.6
72.5
63.7
53.9
44.9
36.4
27.3
5.0
94.2
91.6
88.9
84.4
79.3
72.5
63.3
$4.3
45.9
36.9
28.7
62.4
53.3
45_3
36.7
29.3
0.5
DRT WE (SmoothAdy)
5.0
92.5
91.2
88.0
83,4
78.5
71.1
62.3
53.7
45.3
37.8
29.5
92.1
90.0
86.4
81.4
76.3
69.7
61.1
54.0
46.4
38.4
31.0
1.0
89.1
86.5
82.5
76.7
70.5
63.0
54.8
48.4
41.5
35.3
29.1
87.9
83.4
78.8
73.0
67.5
61.6
56.2
50.4
44.8
38.5
32.7
63.4
46.7
40.2
34.7
1.00
1.0
Gouastan
HHS (Gauscine)
0.96
DRT MHE (Gausston)
WS (Ghunklan)
0.7
0.6
Cortifted
0.6
0.90
(Gausalan)
0.5
Causaian
ussian)
Certilied
0.4
0.83
DRT-NME (Gauesian)
0.4
DRT+MME (Coursian)
0.86
WE (Cauestan)
DRT+ [Gausslan)
WE (Gaussian)
DKT WE (Gaussian)
6.84
0.0
0.2
0.4
0.6
0.6
1.0
0.00 0.25
0.50 0.75 1.00 3.25 1.50
1.75 2.00
0.00
0.5
1.0
1.5
2.0 Radius
2.5
3.0
3.5
4.0
Radius
RRaiuss
0.25
(b) a 0.50
(c)
1.00
Figure 7: Certified accuracy for ML ensembles with Gaussian smoothed base models, under smooth- ing parameter a E {0.25, 0.50, 1.00} separately on MNIST.
1.0
Smoothue
Accurasy
0.9
0.8
MNE (SmosthAtv) We (Smaetadde (SmeothAke)
0.94
0.97
0.8
0.6
0.7
Certifeed
0.4
0.95
0.94
ORT+HMS (kmostiaa))
MNE (SoorhAdd
(smoohhady
0.6
MME (SmacthAdv
WE (mmeshheev
DRT-MME (Smsothh..r)
0.2
(SmsothAAd)
6.93
1.00
0.8.a
0.5
2.0
3.0
3.5
Radius
Radius
(a) = 0.25
(b) 0.50
(c)
1.00
Figure 8: Certified accuracy for ML ensembles with SmoothAdy base models, under smoothing parameter a E {0.25, 0.50, 1.00} separately MNIST.
44

---

Published as a conference paper at ICLR 2022
sample (I, y). We evaluate ACR of our DRT-trained ensemble trained with E {0.25, 0.5, 1.0) smoothing parameter and compare it with other baselines. Results are shown in T
We can clearly that DRT-trained ensemble could still achieve the highest ACR all the smoothing parameter settings. Especially on a 1.00, our improvement is significant.
Table Average Certified Radius (ACR) of DRT-trained ensemble trained with different smoothing parameter E {0.25, 0.50, 1.00] on MNIST dataset, compared with other baselines. The grey rows present the performance of the proposed DRT approach. The brackets shows the base models we use.
Radius
0.25
0.50
1.00
Gaussian (Cohen al. 2019)
0,912
1.565
1.633
SmoothAdv (Salman et al. 2019)
0,920
1.629
1.734
MACER (Zhai al. 20199
0.918
1,583
1.520
MME/ / WE (Gaussian)
0,915
1,585
1.669
DRT MME / WE (Gaussian)
0,923
1.637
1.745
MME/ / WE (SmoothAdv)
0.926
1.678
1.765
DRT MME / WE (SmoothAdv)
0.929
1.689
1.812
Effects of P1 and P2. We investigate the DRT hyper-parametert Pi and P2 corresponding to different smoothing parameter
(0.25, 0.5, 1.0). Here put the detailed results for various hyper- parameter settings in Tables to and bold the numbers with the highest certified accuracy on each radius r. From the experiments, the ensemble model's functionality: if we choose larger Pt, the model will achieve slightly lower certified accuracy on small radii, but higher certified accuracy on large radii. We also can not choose too large P1 on small a cases (c.g., σ = 0.25). Otherwise, model's 's functionality will collapse. Here we show DRT-based models' certified accuracy by applying different #1 Figure 9
find that the GD loss's weight PI have the major influence on
Alternatively, we find that the CM loss's weight P2 can also have positive influence on model's performance: the larger P22 we choose, the higher certified accuracy we could get. Choosing larger and larger P2 does not harm model's functionality too much, but the improvement on certified accuracy will become more and more marginal.
Efficiency Analysis. We regard the execution time per mini-batch our efficiency criterion. For MNIST with batch size equals to 256, DRT with the Gaussian smoothing base model only requires 1.04s to finish mini-batch training to achieve the comparable results the SmoothAdv 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 single NVIDIA GeForce GTX 1080 Ti GPU.
(SmoothAdk,
(SmeothAdr, P: -02)
0.9
DRT (SmsoothAdv, Ai =
Certriied Accuracy
DRT HIME [Sm.oohhAdr, 110)
6.8
Certifted
DRT MME (SmoothAdv, 0.00
(SmoothAdy, Ps 0.11
DRT (SmoothAdy,
DRT MME (SmoothAdv, 0.3)
0.6
(SmoothAdv, P1 0.55)
0.5
(b) 1.0
Figure 9: Effect of p1: Certified accuracy of DRT-based models with MME protocol trained by
different GD Loss's weight A on MNIST. Smoothing parameter o E (0.50, 1.00]. Training with large Pr will lead to lower certified accuracy on small radii but higher certified accuracy on large radii.
45

---

Published as a conference paper at ICLR 2022
Table 8: Certified accuracy of (RT-(P1, p2) under different radii r on CIFAR-I0 dataset. Smoothing parameter o 0.25. The grey rows present the performance of the proposed DRT approach. The brackets show the base models we use.
Radius
P1
P2
0.00
0.25
0.50
0.75
Gaussian (Cohen al. 2019)
78.9
64.4
47.4
30.6
SmoothAdv (Salman et al. 2019
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 (SmoothAdy)
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 (SmoothAdy)
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
F.2 CIFAR-10
Baseline Configuration. Following the literature (Salman et al.) 2019 Jeong & Shin 2020 Zhai et al. 2019). in each batch, each training sample is Gaussian augmented twice (augmenting more times yields negligible difference (Salman al. (2019) show). We choose Gaussian smoothing variance E {0.25, 0.5, 1.0} for training and evaluation for all methods. For SmoothAdy, we consider the attack be 10-step La PGD attack with perturbation scale ô 1.0 without pretraining and unlabelled data augmentation. We also reproduced the similar results mentioned in baseline
papers.
Training Details. First, we use 110 architecture and train each base model for 150 epochs. For the training optimizer, we use the SGD-momentum with the initial learning rate a 0.1. The learning rate is decayed for every 50-epochs with decay ratio finetune our model with small learning rate a for another 150 epochs. We also explore different DRT hyper-parameters Pl, P2 together with the initial learning rate a, and report the best certified accuracy on each radius among all the trained ensemble models.
0.1. Then, we use DRT to
Trend of Certified Accuracy with Perturbation Radius. We visualize the trend of certified accu- racy along with different perturbation radii on different smoothing parameters separately in Figure I0 and Figure II] For each radius r, present the best certified accuracy among all the trained models. We can see the similar trends: Applying either MMF or WE ensemble protocol will only give slight improvement while DRT help make this improvement significant.
Average Certified Radius. We report the Average Certified Radius (ACR) (Zhai et al. 2019] ACR Sucel (or R(x,2) 3), where StEst refers the test set and R(x,, y) the certifed radius testing sample (x, y). We evaluate ACR our DRT-trained ensemble trained with a e {0.25, 0.5, 1.0] smoothing parameter and compare it with other baselines. Results are shown in Table
Results shows that, DRT-trained ensemble has the highest ACR on almost all the settings. Especially on 1.00, improvement is significant.
Effects of pi and P2- We study the DRT hyper-parameter Pi and P2 corresponding to different smoothing parameters E (0.25, 0.5, 1.0) and put the detailed results in Tables 8 10 We bold the
46

---

Published as a conference paper at ICLR 2022
Table 9: Certified accuracy of DRT-(P1, p2) under different radii r on CIFAR-I0 dataset. Smoothing parameter o 0.50. The grey rows present the performance of the proposed DRT approach. The brackets show the base models we use.
Radius
P1
0.00
0.25
0.50
0.75
1.00
1.25
1.50
1.75
Gaussian CChhen 2019
68.2
57.1
44.9
33.7
23.1
16.3
10.0
5.4
SmoothAdy (Salman 2019
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
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
2.0
67.8
58.5
49.0
39.9
31.6
23.4
16.1
10.2
0.5
5.0
65.5
58.4
49.0
40.1
31.2
23.6
16.5
10.2
2.0
64.5
55.8
47.5
39.4
31.1
23.6
14.8
9.3
1.0
5.0
62.2
54.1
46.5
38.8
29.7
22.8
16.6
11.0
DRT + MME (Gaussian)
1.5
59.2
44.1
27.8
22.3
15.0
2.5
58.4
51.0
44.2
39.2
33.4
27.6
23.4
20.6
5.0
5.0
56.2
49.6
45.8
40.4
34.4
29.6
24.4
20.8
2.5
52.0
46.8
42.0
36.2
32.4
27.8
23.4
19.7
10.0
5,0
51.2
47.5
42.5
38.1
33.7
28.9
24.9
20.9
15.0
20.0
54.5
49.8
44.7
34,9
30.2
23.0
18.7
11.1
20.0
30.0
52.2
46.2
40.2
34.4
29.4
22.6
17.8
12.8
MME (SmoothAdy)
61.0
48.7
36.2
23.9
0.2
5.0
62.2
56.4
50.3
43.4
37.5
26.7
24.6
19.4
0.5
5.0
61.9
56.2
50.3
43.5
37.6
31.8
24.8
19.6
DRT MME (SmoothAdv)
1.0
5.0
56.4
52.6
48.2
44.4
39.6
35.8
30.4
23.6
1.5
5.0
56.0
50.8
47.2
44,2
39.8
35.0
29.4
24.0
WE (Gaussian)
69.4
59.7
47.5
38.4
29.2
19.7
13.3
7.5
69.7
50.8
40.2
30.8
22.4
15.9
10.0
0.2
68.0
59.9
50.1
40.8
30.1
22.1
15.4
9.7
2.0
67.8
58.5
49.2
39.8
31.7
23.5
16.2
10.4
0.5
5.0
65.5
58.4
49.1
40.3
31.3
24.2
16.4
10.3
2.0
64.6
55.9
47.5
39.6
31.0
24.0
14.8
9.4
1.0
5.0
62.3
$4.2
46.6
38.8
29.8
22.9
16.6
10.9
DRT + WE (Gaussian)
1.5
5.0
59.2
52.8
44.2
35.8
27.8
22.4
15.0
10.3
2.5
58.4
51.1
44.2
39.2
33.3
27.8
23.2
20.6
5.0
56.2
49.7
45.8
34.2
24.5
20.8
52.0
42.0
36.4
32.5
23.5
10.0
51.2
47.6
42.4
38.1
33.6
28.9
24.9
20.8
15.0
20.0
54.3
49.8
44.6
35.0
30.3
23.0
18.8
11.3
20.0
30.0
52.2
46.2
40.2
34,5
29.2
22.6
17.9
12.8
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
S0.3
43.4
37.5
26.9
24.7
19.3
0.5
61.9
50.2
43.4
37.9
25.0
DRT WE (SmoothAdv)
1.0
56.4
52.6
48.2
39.5
36.0
30.3
23.6
1.5
5.0
56.1
50.9
47.2
44.1
39.8
35.1
29.4
24.1
numbers with the highest certified accuracy each radius r. The results show similar conclusion to our understanding from MNIST.
efficiency criterion. For CIFAR-10 with batch size equals to 256, DRT with the Gaussian smoothing base model requires 3.82s to finish mini-batch training to achieve the competitive results to 10-step PGD attack based SmoothAdy method which requires 6.39s. All the models are trained in parallel on NVIDIA GeForce GTX 1080 Ti GPUs.
Efficiency Analysis. We also the execution time per mini-batch
F.3 IMAGENET
For ImageNet, we utilize ResNet-50 architecture and train each base model for 90 epochs using mGD-mmmentum optimizer. The initial learning rate a set to 0.1. During training, the learning rate is decayed for every 30-epochs with decay ratio 7 0.1. We tried different Gaussian smoothing parameter ø E {0.50, 1.00}, and consider the best dyper-parameter configuration for each a. Then, use DRT to finetune base models with the learning rate 5 10-3 for another 90 epochs. Due
47

---

Published as a conference paper at ICLR 2022
Table 10: DRT-(P1, p2) model's certified accuracy under different radii on CIFAR-IO dataset.
Smoothing parameter a = 1.00. The grey rows present the performance of the proposed DRT approach. The brackets show the base models we use.
Radius r
0.00
0.25
0.50
0.75
1.00
1.25
1.50
1.75
2,00
Gaussian (Chhen et al.
2019
48.9
42.7
35.4
28.7
22.8
18.3
13.6
10.5
7.3
Adv (Salman et al.
20T9
47.8
43.3
39.5
34.6
30.3
25.0
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
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
0.5
44.6
38.6
34.6
29.2
25.6
21.8
19.4
17.0
15.6
DRT + MME (Gaussian)
5.0
2.5
44.8
39.6
35.2
31.0
27.8
23.4
20.6
18.2
16.6
10.0
45.4
40.4
36.8
30.4
26.0
21.8
19.0
15.8
13.6
10.0
40.8
36.2
31.2
27.4
21.2
20.0
42.2
39.6
34.8
30.8
26.2
22.4
20.0
30.2
26.8
22.6
16.8
MME (SmoothAdv)
48.2
43.7
40.1
26.2
22.6
16.2
43.9
40.1
31.5
26.7
40.3
23.1
20.1
DRT MME (SmoothAdv)
30.0
23.8
20.1
47.8
43.4
39.5
35.4
31.6
26.7
23.1
20.4
18.1
WE (Gaussian)
50.4
44.1
37.5
15.9
49.5
37.8
31.8
25.6
22.5
48.2
42.5
30.4
26.1
22.1
12.6
0.5
44.6
38.6
34.7
29.1
25.8
21.8
19.6
17.1
15.6
DRT WE (Gaussian)
5.0
2.5
44.8
39.6
35.4
31.0
27.9
23.4
20.6
18.1
16.4
10.0
45.4
40.3
36.8
30.4
26.2
21.8
19.1
15.8
13.6
10.0
20.0
44.5
40.8
36,2
31.3
27.4
21.2
18.9
17.2
13.5
15.0
20.0
42.2
39.7
34.8
30.8
26.1
22.4
18.0
16.7
15.4
20.0
30.0
33.8
30.4
26.8
22.8
18.6
16.9
15.0
12.7
11.2
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.4
31.5
26.8
23.0
19.9
16.7
0.5
5.0
48.2
43.8
40.5
35.7
31.9
26.8
23.3
20.2
17.5
DRT (SmoothAdv)
1.0
5.0
46.2
43.4
40.6
37.0
34.2
30.1
26.8
23.9
20.3
1.5
5.0
47.8
43.4
39.6
35.4
31.4
26.7
23.0
20.4
18.1
Table 11: Average Certified Radius (ACR) of DRT-trained ensemble trained with different smoothing parameter a (0.25, 0.50, 1.00] on CIFAR- 10 dataset, compared with other baselines. The grey rows present the performance of the proposed DRT approach. The brackets shows the base models we use.
Radius r
= 0.25
= 0.50
1.00
Gaussian
0,484
0.595
0.559
SmoothAdy
0.539
0.662
0.730
MACER
0.556
0.726
0.792
MME/ / WE (Gaussian)
0.513
0.621
0.579
DRT MME / WE (Gaussian)
0.551
0.687
0,744
MME/ / WE (SmoothAdv)
0.542
0.692
0.689
DRT MME WE (SmoothAdv)
0.545
0.760
0.868
to the consideration of achieving high certified accuracy large radii, choose large DRT training hyper-parameter Pi and P2 in practice, which lead to relatively low benign accuracy.
G ABLATION STUDIES
G. THE EFFECTS OF GRADIENT DIVERSITY LOSS AND CONFIDENCE MARGIN LOSS
To explore the effects of individual Gradient Diversity and Confidence Margin Losses in DRT, set Pi or P2 to 0 and tune the other for evaluation on MNIST and CIFAR-10. The results are shown in
Table 12 and 13 We observe that both GD and CM losses have positive effects improving the
48

---

Published as a conference paper at ICLR 2022
0.8
0.7
Gasssion
Accurs
0.6
0.5
0.5
0.6
DAT- NHE (Gaussian)
WE (Gausslan)
HNE (Gaussian)
DR T- (Gauesban
Certifled Accurecy
0.4
DRT WE (Gaussian)
WE (Gaussian)
DAT+MME (Geumian)
(Gaussian)
0.4
(Gaussian]
0.2
MME usslan))
0.1
DRT (Gaussian)
(Gaussian)
0.1
8.0
0.2
0.4
0.6
0.8
1.0
88.00 0.25 0.50
1.00 Radius
1.50 3.75 2.00
0.0
0.0
0.5
1.0
1.5
2,0 Radius
2.5
3.0
3.5
4.0
Radus
(a)
0.25
(h) 0.50
(c) 1.00
Figure 10: Certified accuracy for ML ensembles with Gaussian smoothed base models, under smoothing parameter a {0.25, 0.50, 1.00} separately on CIFAR-10.
Smeothadv
Smoothadv
NIKE (Smsethttri
HHE (SmsothAdr)
will (sinethade
De (5meothaa)))
DRT MIKE [SmoothAdd)
(SmosthAdv) DRT (SmoothAdd)
Smoothldy
MME (SmoothAdv)
DAT-MMA MME (SoothhA)v)
mooohhhdv
DRT-WE (SmoothAdv)
68
A3di5
0.25
0.50
(c) 1.00
Figure 11: Certified accuracy for ML ensembles with SmoothAdy base models, under smoothing parameter a E {0.25, 0.50, 1.00] separately on CIFAR-10.
certified accuracy while GD plays a major role on larger radii. By combining these two regularization losses together in DRT, the ensemble model achieves the highest certified accuracy under all radii.
Table 12:
Certified accuracy achieved by training with GD Loss (GDL) or Confidence Margin Loss (CML.) only MNIST dataset.
Radius
0.25
0.50
0.75
1.00
1.50
1.75
2.25
2.50
MMH (Gaussian)
99.2
98.4
96.8
94.9
90.5
84.3
69.8
48.8
34.7
23.4
12.7
GDL + MME (Gaussian)
99.2
98.4
96.9
95.3
92.3
86.2
76.0
60.2
43.3
35.5
28.7
CML + MME (Gaussian)
99.3
98.4
97.0
95.0
90.8
84.0
71.1
50.0
36.7
24.5
13.7
DRT MME (Gaussian)
99.5
98.6
97.5
95.5
92.6
86.8
76.5
60.2
43.9
36.0
29.1
WiS (Gaussian)
99.2
98.4
96.9
94.9
90.6
84.5
70.4
49.0
35.2
23.7
12.9
GDL WE (Gaussian)
98.5
97.1
92.3
86.3
76.3
59.8
35.1
29.0
CML WE (Gaussian)
99.3
98.4
97.0
95.0
90.8
84,1
71.1
50.3
37.0
24.6
13.7
DRT WE (Gaussian)
99.5
98.6
97.4
95.6
92.6
86.7
76.7
60.2
43.9
35.8
29.0
G.2 CERTIFIED ROBUSTNESS OF SINGLE BASE MODEL WITHIN DRT-TRAINED ENSEMBLE
We also conduct ablation study on how the single base models' certified accuracy can be improved after applying DRT to the whole ensemble for both MNIST and CIFAR-10 datasets. Results are shown in in Table 14 and 15 We are surprised to find that the single base model within our DRT- trained ensemble are more robust compared to single base model within other baseline ensembles. Also, integrating them together could achieve higher robustness.
G.3 OPTIMIZING THE WEIGHTS OF DRT-TRAINED ENSEMBLE
While we adapt average weights in our WE ensemble protocol in our experiments, we are also interested in how tuning the optimal weights could further improve the certified accuracy of our DRT-trained ensemble. We conduct this ablation study on both MNIST and CIFAR- 10 datasets by grid-searching all the possible weights combination with step size as 0.1. Results are shown in Table 16 and[T] (AE here refers to the average ensemble protocol and WE the weighted ensemble protocol by adapting the tuned optimal weights)
49

---

Published as a conference paper at ICLR 2022
Table 13: Certified accuracy achieved by training with GD Loss (GDL) Confidence Margin Loss
(CML) only on 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)
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
CML MME (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
34.4
29.6
24.9
20.9
16.6
WF (Gaussian)
80.8
68.4
53.6
38.4
29.2
19.7
15.9
11.8
8.9
GDL WE (Gaussian)
81.0
69.1
55.6
41.8
30.6
25.2
20.2
16.9
14.9
CML + WE (Gaussian)
81.1
69.4
54.6
39.7
29.4
21.7
17.2
13.2
12.8
DRT WE (Gaussian)
81.5
70.4
57.9
44.0
34.2
29.6
24.9
20.8
16.4
Table 14: Certified accuracy of single base model within DRT-trained ensemble on 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
Single (Gaussian)
99.1
97.9
96.6
94.7
90.0
83.0
68.2
46.6
33.0
20.5
11.5
DRT Single (Gaussian)
99.0
98.6
97.2
95.4
92.0
85.6
74,9
59.8
43.4
35.2
28.6
DRT MME (Gaussian)
99.5
98.6
97.5
95.5
92.6
86.8
76.5
60.2
43.9
36.0
DRT WE (Gaussian)
99,5
98.6
97.4
95.6
92.6
86.7
76.7
60.2
43,9
35,8
29.0
Single (SmoothAds)
99.1
98.4
97.0
96.3
93.0
87.7
80.2
66.3
43.2
34.3
24.0
DRT Single (SmoothAdv)
99.2
98.4
97.6
96.6
92.9
88.
80.4
68.0
46.4
39,2
34.1
DRT + MME (SmoothAdv)
99.2
98.4
97.6
96.7
93.1
88.5
83.2
68.9
48.2
40.3
34,7
DRT + (SmoothAdv)
99.1
98.4
97.6
96.7
93.4
88.5
83.3
69.6
48.3
40.2
34.8
Table 15: Certified accuracy of single base model within DRT-trained ensemble on CIFAR- 10 dataset.
Radius
0.00
0.25
0.50
0.75
1.00
1.25
1.50
1.75
2.00
Single (Gaussian)
78.9
64.4
47.4
33.7
23.1
18.3
13.6
10.5
7.3
DRT Single (Gaussian)
81.4
69.8
56.2
42.5
33.6
27.6
24.2
20.4
15.4
DRT MME (Gaussian)
81.4
70.4
57.8
43.8
34.4
29.6
24.9
20.9
16.6
DRT WE (Gaussian)
81.5
70.4
57.9
44.0
34.2
29.6
24.9
20,8
16.4
Single (SmoothAdv)
68.9
61.0
54.4
45.7
34.8
28.5
21.9
18.2
13.7
DRT Single (SmoothAdv)
72.4
66.8
57.8
48.2
38.1
33.4
28.6
22.2
19.6
DRT + MME (SmoothAdv)
72.6
67.2
60.2
50.4
39.4
35.8
30.4
24.0
20.1
DRT + (SmoothAdv)
72.6
67.0
60.2
50.5
39.5
36.0
30.3
24.1
20.3
We can that, by learning the optimal weights, the certified accuracy could be only slightly improved compared to the average weights setting, which indicates that, average weights can good choice in practice.
Table 16: Comparison of the certified accuracy between Average Ensemble (AB) protocol and Weighted Ensemble (WE) protocol MNIST dataset. Cells with bold numbers indicate learning optimal weights could achieve higher certified accuracy on corresponding radius r.
Radius
0.00
0.25
0.50
0.75
1.00
1.25
1.50
1.75
2.00
2.25
2.50
DRT + AE (Gaussian)
99.3
98.6
97.4
95.6
92.6
86.7
76.7
60.2
43.9
35.8
29.0
DRT + WE (Gaussian)
99.5
98.6
97.6
95.6
92.7
86.8
76.7
60.3
44.0
36.0
29.3
DRT AE (SmoothAdv)
99.1
98.4
97.6
96.7
93.4
88.5
83,3
69.6
48.3
40.2
34,8
DRT + WH (SmoathAdv)
99.1
98.4
97.6
96.8
93.5
88.5
83.3
69.7
48.5
40.2
34.8
G.4 COMPARISON WITH OTHER GRADIENT DIVERSITY REGULARIZERS
We notice that of the certifiably robust ensemble field, there exist representatives of gradient diversity promoting regularizers: ADP (Pang et al. 2019) and GAL (Kariyappa & Qureshi 2019). They achieved notable improvements on empirical ensemble robustness. For an ensemble consisting of base models (Fi and input x and ground truth label the ADP regularizer is defined as
N
LADP(E, v) =a H(mcan ((fcc)(((f(=))))) + -llogg (ED)
Σ
50

---

Published as a conference paper at ICLR 2022
Table 17: Comparison of the certified accuracy between Average Ensemble (AB) protocol and Weighted Ensemble (WE) protocol on CIFAR-10 dataset. Cells with bold numbers indicate learning optimal weights could achieve higher certified accuracy on corresponding radius r.
Radius r
0.00
0.25
0.50
0.75
1.00
1.25
1.50
1.75
2.00
DRT AE (Gaussian)
81.5
70.4
57.9
44.0
34.2
29.6
24.9
20.8
16.4
DRT WE (Gaussian)
81.5
70.4
57.9
44.0
34.3
29.6
25.0
20,9
16.5
DRT + (SmoothAdv)
72.6
67.0
60.2
50.5
39.5
36.0
30.3
24.1
20.3
DRT (SmoothAdv)
50.5
39.5
30.3
24.1
20.4
Table 18:
Certified accuracy of (ADP, GAL., DRT)-based Gaussian smoothed ensemble under
different radii with WE protocol.
MNIST
0.00
0.25
0.50
0.75
1.00
1.25
1.50
1.75
2.00
2.25
2.50
ADP
99.5
98.2
97.2
95.2
92.2
85.8
73.4
53.2
36.9
24.7
13.3
GAL
99.5
98.3
97.2
95.1
92.4
86.1
73.2
54.4
36.2
24.7
13.9
DRT
99.5
98.6
97.4
95.6
92.6
86.7
76.7
60.2
43.9
35.8
29.0
CIFAR-10
0.00
0.25
0.50
0.75
1.00
1.25
1.50
1.75
2.00
ADP
83.0
68.0
S2.2
38.2
28.8
20.0
16.8
14.2
11.0
GAL
82.2
67.6
53.6
38.8
27.6
20.2
15.4
13.6
10.6
DRT
81.5
70.4
57.9
44.0
34.2
29.6
24.9
20.8
16.4
where H()) refers to the Shannon Entropy Loss function and ID the square of the spanned volume of base models' logit vectors.
GAL regularizer minimizes the cosine similarity value between base models' loss gradient vectors, which is defined as:
exp (cos(Vall, Vade,))
(a,L(x,)) = log
Σ
ISKGJN
Under the smoothed ensemble training setting, the final training loss is represented by
Larin (aiin(x,,))
Σ Lata( te v, [AADp( + e. LaAL (æ: + t,y))
iE[M]
where consider standard training loss (wt 5oy) of each base model F; to be the standard cross-entropy loss.
Table 18 shows the certified accuracy of (ADP, GAL, DRT) -trinedd ensemble under different radii with WE protocol on MNIST and CIFAR-10 dataset. We notice that DRT outperforms both ADP and GAL significantly in terms of the certified accuracy different datasets.
51


Reviews:
[{"review_id": "vzW5N9vhK9u", "reviewer": "Reviewer_AZhe", "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": "- The paper is clearly written and well-motivated. The motivation is theoretically supported, and the strong experimental results also confirm the effectiveness. I agree that exploring on the ensemble of smoothed classifiers is an important yet under-explored topic.\n- Although the paper motivates the method from Theorem 1, it was quite unclear to me when the paper proceeds from Theorem 1 to Ensemble-before-Smoothing (EBS): I can see that Theorem 1 holds only when all the base classifiers (\"before\" ensemble) are $\\beta$-smooth, but then why Theorem 2 shows the $\\beta$-smoothness of the classifier \"after\" ensemble? Does EBS guarantee that all the base classifiers before ensemble are $\\beta$-smooth? If not, how can one apply Theorem 1 to justify GD and CM losses?\n- I feel the paper could benefit from comparing Average Certified Radius (ACR) [Zhai et al., 2020] as well as the certified accuracies: overall, I could see that the proposed method improves certified accuracy, but generally the gains are not uniform (especially for the ImageNet results) so that the readers may be confused on interpreting them.\n- It would be helpful for the readers that the Table 1 and 2 could also present the single-model performance of DRT-trained models.\n- The paper should include a discussion about the computational costs of the proposed method - e.g., the increase in training time of DRT compared to the Gaussian training (or standard ensemble). Also, I would like to see the overheads in certification time, as the certification pipeline now includes an ensemble during smoothing.\n- I feel the results on ImageNet are relatively less significant, especially given the decrease in the clean accuracy of DRT+* models. The paper could include more discussion on it.", "summary_of_the_paper": "The paper proposes to train diverse classifiers to improve certified robustness of ensemble classifiers. More specifically, it proposes two regularization terms in training: (a) the Gradient Diversity (GD) loss, and (b) the Confidence Margin (CM) loss. This is motivated by a theoretical observation that one needs both (a) and (b) to achieve a robust ensemble model given that all the base classifiers are smooth. Experimental results on MNIST, CIFAR-10 and ImageNet show that the proposed training can consistently improve the certified accuracies of ensemble models compared to the ensemble of classifiers from the standard training. ", "summary_of_the_review": "Overall, I can see that the paper is clearly written and addresses an important research direction that explores a better ensemble scheme of smoothed classifiers. Although I feel a slight logical gap in Theorem 1 → EBS, the paper presents a novel and theoretical justification to motivate the new training method, and it is further supported with a strong empirical results.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "mpa_PM6tfDq", "reviewer": "Reviewer_f6eQ", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "### Strengths \n* The empirical results are strong, i.e., the proposed model outperforms baselines consistently.\n* The theoretical contributions appear sound and meaningful.\n* The paper is well-written and easy to follow.\n### Weaknesses\n* The authors only study a single setting of $N=3$. An interesting study would have been to see how increasing $N$ changes the certified robustness.\n* The authors do not make use of the fact that their theory allows to certify when the ensemble *cannot* be robust w.r.t. a sample.\n* The proposed method has the apparent drawback that the ensemble models cannot be trained in isolation.\n\n### Detailed comments\n* An interesting finding is the importance of gradient diversity for the ensemble robustness. This seems to align well with the fact that we favor diverse ensembles in practice. I wonder whether there is a deeper connection of gradient diversity for robustness to the diversity of the ensemble.\n* Out of curiosity, is there any theoretical indication that larger $N$ leads to more robustness? Intuitively, large $N$ should lead to a smoother ensemble function, but $N$ does not appear in the computation of the smoothness $\\beta$.\n* How are the $w_i$ optimized in the proposed approach?\n* An interesting aspect of the theoretical contribution is that Theorem 1 can also prove when a sample is *not* robust. It would have been interesting to show the share of *certifiably nonrobust* samples in addition to the certified accuracy in the figures and tables. This way we could also see how large the share of samples is for which we cannot certify (non-)robustness.", "summary_of_the_paper": "The authors present theoretical and empirical findings on how ensembles can improve certifiable robustness of classifiers. The authors show that increased robustness requires diverse gradients among the ensemble members (as well as large confidence margins). The authors incorporate these findings into two regularization terms for training and show that these lead to improved certifiable robustness on MNIST, CIFAR10, and ImageNet.", "summary_of_the_review": "The paper is well-written and easy to follow, and the theoretical and empirical contributions are interesting and appear meaningful. I would have liked to see different values of $N$ and a study of the *certifiable non-robustness* of the ensemble models. \n\nEdit: I have increased my score based on the authors' response.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "k2tQrGhd7a", "reviewer": "Reviewer_ug5z", "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": "The theoretical analysis in this paper is correct, although a bit difficult to follow due to the redundant and non-traditional notations. The experiment results are sufficient to support the claim of this paper.\n\nOne question I have is how the weights of ensembles could affect the results. I didn’t find any explicit values for these weights, which should be included in the experiment section as what are the values and how these are chosen.", "summary_of_the_paper": "This paper proposes a new analysis for randomized smoothing based certified robustness of ensemble models. The analysis shows that the robustness radius depends on the l2 norm of the weighted sum of the gradients of the confidence margin of base models. A training strategy is then proposed to regularize this term by increasing the divergence of gradient vectors.", "summary_of_the_review": "See comments above.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "iFb_mxGyV-S", "reviewer": "Reviewer_VR8o", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The ensemble model performs well in empirical defense, so its extension to provable robustness is essential. Some interesting insights are presented, but they also seem to be readily available from the empirical ensemble model defense. \n\nIn definition 1, To be consistent with randomized smoothing, should ${\\left\\|\\delta\\right\\|}_2 \\leqslant r$ be ${\\left\\|\\delta\\right\\|}_2 < r$? \n\nWhy is the empirical robust accuracy of DRT $(r=0)$ lower than the baseline on large-scale datasets?\n\nWhat is the motivation for Ensemble-before-Smoothing? Is it driven by the property of Theorem II or is it due to empirical observation? The EBS here seems trivial.\n\nI will consider raising my score based on the other reviewers' comments and the authors' responses.\n\n", "summary_of_the_paper": "The paper analyzed the certified robustness for ensemble ML models. It is proven that diversified gradient and large confidence margin are sufficient and necessary conditions for certifiably robust ensemble models under the model-smoothness assumption. The proposed Diversity Regularized Training (DRT) method performs better than current provable methods.\n\n", "summary_of_the_review": "The paper has a lot of proof, which is great, but there are some questions about the experimental results and motivation that need to be clarified.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "DidFq7BKfBu", "reviewer": "Reviewer_mt7k", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Strengths of the paper**\n- This is a rigorous and solid paper in which the practical approach is developed based on theoretical findings.\n- The writing and presentation are generally good and motivating.\n- Convincing experimental results.\n\n**Weaknesses of the paper**\n- The findings of the paper are not really new. The usefulness of gradient diversity in improving the robustness of an ensemble model and the capability of a large confident margin in enhancing the robustness are well-known. Furthermore, randomized smoothing has been proposed before. However, this paper is good in the sense of putting together them in the theory development of an ensemble approach.", "summary_of_the_paper": "This paper proposes using an ensemble model to improve certified robustness. Based on the developed theory, it proposes Diversity-Regularized Training (DRT), a lightweight regularization-based ensemble training approach which composes of two simple yet effective and general regularizers to promote the diversified gradients and large confidence margins respectively. The experiments were conducted to show the merit of the proposed approach.", "summary_of_the_review": "It would be great if the authors offers more discussion about the variation of the upper bounds in equations (4,5) if we vary the robust radius $r$. The current analysis is done with a fixed $r$.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes Diversity-Regularized Training (DRT), a new training method for an ensemble classifier to improve its certified robustness when randomized smoothing is applied. Specifically, it trains a set of base classifiers to diversify their input gradients while maximizing the confidence margin of each. The method is backed up with a theoretical observation on robustness of ensembles of smooth classifiers.

After the discussion phase, the reviewers unanimously ended up with supporting acceptance of this paper, and the authors were quite responsive to address the reviewers' concerns. Overall, the reviewers appreciated its strong empirical results with a theoretical support - AC also agrees on that, and thinks the paper presents a promising and under-explored direction to boost certified robustness of randomized smoothing.
Decision: Accept (Poster)