Year: 2021

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 L2-robustness on MNIST, CIFAR-10, and ImageNet datasets.

heading: 1 INTRODUCTION
text: Deep neural networks (DNN) have been widely applied in various applications, such as image classification (Krizhevsky, 2012; He et al., 2016), face recognition (Sun et al., 2014), and natural language processing (Vaswani et al., 2017; Devlin et 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 et al., 2020; Bulusu et al., 2020), and it has raised great concerns especially when DNNs are deployed in safety-critical applications such as autonomous driving and facial recognition.
To defend against such attacks, several empirical defenses have been proposed (Papernot et al., 2016b; Madry et al., 2018); however, many of them have been attacked again by strong adaptive attackers (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 ML models, so that no additional attack can break the model under certain adversarial constraints. For instance, randomized smoothing has been proposed as an effective defense providing certified robustness (Lecuyer et al., 2019; Cohen et al., 2019; Yang et al., 2020a). Among different certified robustness approaches (Weng et al., 2018; Xu et al., 2020; Li et al., 2020a), randomized smoothing provides a model-independent way to smooth a given ML model and achieves state-of-the-art certified robustness on large-scale datasets such as ImageNet.
Currently, all the existing certified defense approaches focus on the robustness of a single ML model. Given the observations that ensemble ML models are able to bring additional benefits in standard learning (Opitz & Maclin, 1999; Rokach, 2010), in this work we aim to ask: Can an ensemble ML model provide additional benefits in terms of the certified robustness compared with a single model? If so, what are the sufficient and necessary conditions to 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, a 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-10 (Table 2). Given such observations, next we aim to answer: How to improve the certified robustness of ensemble ML models? What types of conditions are required to improve the certified robustness for ML ensembles?
In particular, from the theoretical perspective, we analyze the standard Weighted Ensemble (WE) and Max-Margin Ensemble (MME) protocols, and prove the sufficient and necessary conditions for the certifiably robust ensemble models under model-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-before-Smoothing as the model smoothing strategy and prove the bounded model-smoothness with such strategy, which realizes our model-smoothness assumption.
Inspired by our theoretical analysis, we propose Diversity-Regularized Training (DRT), a lightweight regularization-based ensemble training approach. DRT is composed of two simple yet effective and general 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 augmentation (Cohen et al., 2019) and adversarial smoothed training (Salman et al., 2019), with negligible training time overhead while achieves significantly higher
certified robustness than state-of-the-art approaches consistently.
We conduct extensive experiments on a wide range of datasets including MNIST, CIFAR-10, and ImageNet. 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 to 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 under L2 radius 1.5, the DRT-trained 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 ML ensembles and propose an efficient training algorithm DRT to achieve the state-of-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 model-smoothness assumption. In particular, we prove that the diversified gradients and large confidence margins of base models are the sufficient and necessary conditions of certifiably robust ensembles. We also prove the bounded model-smoothness via proposed Ensemble-before-Smoothing strategy, which realizes our model-smoothness assumption. • 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, a
lightweight regularization-based training approach that can be easily combined with different training approaches and ensemble protocols with small training cost overhead. • We conduct extensive experiments to 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.
Related work. DNNs are known vulnerable to adversarial examples (Szegedy et al., 2013). To defend against such attacks, several empirical defenses have been proposed (Papernot et al.,
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 no certified robustness guarantee could be provided or enhanced; or certify the robustness for a standard weighted ensemble (Zhang et al., 2019; Liu et al., 2020) using either LP-based (Zhang et al., 2018) verification or 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, to our best knowledge, we propose the first training approach to boost the certified robustness of ensemble ML models.
Randomized smoothing (Lecuyer et al., 2019; Cohen et al., 2019) has been proposed to provide certified robustness for a single ML model. It achieved the state-of-the-art certified robustness on large-scale dataset such as ImageNet and CIFAR-10 under L2 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 et 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., 2019; Zhai et al., 2019), and denoising (Salman et al., 2020). In this paper, we compare and propose a suitable smoothing strategy to improve the certified robustness of ML ensembles.

heading: 2 CHARACTERIZING ML ENSEMBLE ROBUSTNESS
text: 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.

heading: 2.1 PRELIMINARIES
text: Notations. Throughout the paper, we consider the classification task with C classes. We first define the classification scoring function f : Rd → ∆C , which maps the input to a confidence vector, and f(x)i represents the confidence for the ith class. We mainly focus on the confidence after normalization, i.e., f(x) ∈ ∆C = {p ∈ RC≥0 : ‖p‖1 = 1} in the probability simplex. To characterize the confidence margin between two classes, we define fy1/y2(x) := f(x)y1 − f(x)y2 . The corresponding prediction F : Rd → [C] is defined by F (x) := arg maxi∈[C] f(x)i. We are also interested in the runner-up prediction F (2)(x) := arg maxi∈[C]:i 6=F (x) f(x)i.
r-Robustness. For brevity, we consider the model’s certified robustness, against the L2-bounded perturbations as defined below. Our analysis can be generalizable for L1 and L∞ perturbations, leveraging existing work (Li et al., 2019; Yang et al., 2020a; Levine & Feizi, 2021). Definition 1 (r-Robustness). For a prediction function F : Rd → [C] and input x0, if all instance x ∈ {x0 + δ : ‖δ‖2<r} satisfies F (x) = F (x0), we say model F is r-robust (at point x0).
Ensemble Protocols. An ensemble model contains N base models {Fi}Ni=1, where Fi(x) and F
(2) i (x) are their top and runner-up predictions for given input x 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}Ni=1, and the weight vector {wi}Ni=1 ∈ RN+ , the weighted ensembleMWE: Rd → [C] is defined by
MWE(x0) := arg max i∈[C] N∑ j=1 wjfj(x0)i. (1)
Definition 3 (Max-Margin Ensemble (MME)). Given N base models {Fi}Ni=1, for input x0, the max-margin ensemble modelMMME : Rd → [C] is defined by
MMME(x0) := Fc(x0) where c = arg max i∈[N ] ( fi(x0)Fi(x0) − fi(x0)F (2)i (x0) ) . (2)
The commonly-used WE (Zhang et al., 2019; Liu et al., 2020) sums up the weighted confidence of base models {Fi}Ni=1 with weight vector {wi}Ni=1, and predicts the class with the highest weighted confidence. The standard average ensemble can be viewed as a special case of WE (where all wi’s are equal). MME chooses the base model with the largest confidence margin between the top and the runner-up classes, which is a direct extension from max-margin training (Huang et al., 2008).
Randomized Smoothing. Randomized smoothing (Lecuyer et al., 2019; Cohen et al., 2019) provides certified robustness by constructing a smoothed model from a given model. Formally, let ε ∼ N (0, σ2Id) be a Gaussian random variable, for any given model F : Rd → [C] (can be an ensemble), we define smoothed confidence function gεF : Rd →∆C such that
gεF (x)j := E ε∼N (0,σ2Id) I[F (x+ ε) = j] = Pr ε∼N (0,σ2Id) (F (x+ ε) = j). (3)
Intuitively, gεF (x)j is the probability of base model F ’s prediction on the jth class given Gaussian smoothed input. The smoothed classifier GεF : Rd → [C] outputs the class with highest smoothed confidence: GεF (x) := arg maxj∈[C] g ε F (x)j . Let cA be the predicted class for input x0, i.e., cA := G ε F (x0). Cohen et al. show that G ε F is (σΦ
−1(gεF (x0)cA))-robust at input x0, i.e., the certified radius is σΦ−1(gεF (x0)cA) where Φ
−1 is the inverse cumulative distribution function of standard normal distribution. In practice, we will leverage the smoothing strategy together with Monte-Carlo sampling to certify ensemble robustness. More details can be found in Appendix A.

heading: 2.2 ROBUSTNESS CONDITIONS FOR GENERAL ENSEMBLE MODELS
text: We will first provide sufficient and necessary conditions for robust ensembles under the modelsmoothness assumption. Definition 4 (β-Smoothness). A differentiable function f : Rd 7→ RC is β-smooth, if for any x1, x2 ∈ Rd and any output dimension j ∈ [C], ‖∇x1f(x1)j−∇x2f(x2)j‖2 ‖x1−x2‖2 ≤ β.
The definition of β-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 β indicates smoother ones. When β = 0 the function/model is linear.
For Weighted Ensemble (WE), we have the following robustness conditions. Theorem 1 (Gradient and Confidence Margin Conditions for WE Robustness). Given input x0 ∈ Rd with ground-truth label y0 ∈ [C], andMWE as a WE defined over base models {Fi}Ni=1 with weights {wi}Ni=1.MWE(x0) = y0. All base models Fi’s are β-smooth.
• (Sufficient Condition) TheMWE is r-robust at point x0 if for any yi 6= y0,∥∥∥ N∑ j=1 wj∇xfy0/yij (x0) ∥∥∥ 2 ≤ 1 r N∑ j=1 wjf y0/yi j (x0)− βr N∑ j=1 wj , (4) • (Necessary Condition) IfMWE is r-robust at point x0, for any yi 6= y0,∥∥∥ N∑ j=1 wj∇xfy0/yij (x0) ∥∥∥ 2 ≤ 1 r N∑ j=1 wjf y0/yi j (x0) + βr N∑ j=1 wj . (5)
The proof follows from Taylor expansion at x0 and we leave the detailed proof in Appendix B.2. When it comes to Max-Margin Ensemble (MME), the derivation of robust conditions is more involved. In Theorem 3 (Appendix B.1.1) we derive the robustness conditions for MME composed of two base models. The robustness conditions have highly similar forms as those for WE in Theorem 1. Thus, for brevity, we focus on discussing Theorem 1 for WE hereinafter and similar conclusions can be drawn for MME (details are in Appendix B.1.1).
To analyze Theorem 1, we define Ensemble Robustness Indicator (ERI) as such:
Iyi := ∥∥∥ N∑
j=1
wj∇xfy0/yij (x0) ∥∥∥ 2 / ‖w‖1 − 1 r‖w‖1 N∑ j=1 wjf y0/yi j (x0). (6)
ERI appears in both sufficient (Equation (4)) and necessary (Equation (5)) conditions. In both conditions, smaller ERI means more certifiably robust ensemble. Note that we can analyze the
robustness under different attack radius r by directly varying r in Equations (4) and (5). When r becomes larger, the gap between the RHS of two inequalities (2βr ∑N j=1 wj) also becomes larger, and thus it becomes harder to determine robustness via Theorem 1. This is because the first-order condition implied by Theorem 1 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.
Diversified Gradients. The core of first term in ERI is the magnitude of the vector sum of gradients: ‖ ∑N j=1 wj∇xf y0/yi j (x0)‖2. According to the law of cosines: ‖a + b‖2 =√
‖a‖22 + ‖b‖22 + 2‖a‖2‖b‖2 cos〈a, 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 reducing 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. Large Confidence Margins. The core of second term in ERI is the confidence margin:∑N j=1 wjf y0/yi j (x0). Due to the negative sign of second term in ERI, we need to increase this term, i.e., we 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, we will directly regularize these two key factors to promote certified robustness of ensembles.
Impact of Model-Smoothness Bound β. From Theorem 1, we observe that: (1) if minyi 6=y0 Iyi ≤ −βr,MWE is guaranteed to be r-robust (sufficient condition); and (2) if minyi 6=y0 Iyi > βr,MWE cannot be r-robust (necessary condition). However, if minyi 6=y0 Iyi ∈ (−βr, βr], we only know MWE is possibly r-robust. As a result, the model-smoothness bound β decides the correlation strength between minyi 6=y0 Iyi and the robustness ofMWE: if β becomes larger, minyi 6=y0 Iyi is more likely to fall in (−βr, βr], inducing an undetermined robustness status from Theorem 1, vice versa. Specifically, when β = 0, i.e., all base models are linear, the gap is closed and we can always certify the robustness ofMWE via comparing minyi 6=y0 with 0. Similar observations can be drawn for MME. Therefore, to strengthen the correlation between Iyi and ensemble robustness, we would need model-smoothness bound β to be small.

heading: 2.3 ROBUSTNESS CONDITIONS FOR SMOOTHED ENSEMBLE MODELS
text: Typically neural networks are nonsmooth or admit only coarse smoothness bounds (Sinha et al., 2018), i.e., β is large. Therefore, applying Theorem 1 for normal nonsmooth models would lead to near-zero certified radius. Therefore, we propose soft smoothing to enforce the smoothness of base models. However, with the soft smoothed base models, directly applying Theorem 1 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-dimensional vectors via sampling, which requires linear number of samples with respect to input dimension (Mohapatra et al., 2020; Salman et al., 2019) and is thus too expensive in practice. To solve this issue, we then propose Ensemble-before-Smoothing 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 et al., 2020), which applies randomized smoothing over the confidence scores. Given base model’s confidence function f : Rd → ∆C (see Section 2.1), we define soft smoothed confidence by ḡεf : x 7→ Eεf(x+ ε). Note that soft smoothed confidence is different from smoothed confidence gεF 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 ḡεf .
Theorem 2 (Model-Smoothness Upper Bound for ḡεf ). Let ε ∼ N (0, σ2Id) be a Gaussian random variable, then the soft smoothed confidence function ḡεf is (2/σ 2)-smooth.
We defer the proof to Appendix B.4. The proof views the Gaussian smoothing as the Weierstrass transform (Weierstrass, 1885) of a function from Rd to [0, 1]C , leverages the symmetry property, and bounds the absolute value of diagonal elements of the Hessian matrix. Note that a Lipschitz constant√
2/(πσ2) is derived for smoothed confidence in previous work (Salman et al., 2019, Lemma 1),
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 {ḡεi (x0)}Ni=1 as base models’ confidence scores, and obtain soft ensemble ḠεMWE and Ḡ ε MMME respectively. Since each ḡεi is (2/σ 2)-smooth, take WE as an example, we can study the ensemble robustness with Theorem 1. We state the full statement in Corollary 2 (and in Corollary 3 for MME) in Appendix B.1.3. From the corollary, we observe that the corresponding ERI for the soft smoothed WE can be written as
Īyi := ∥∥∥Eε∇x N∑
j=1
wjf y0/yi j (x0 + ε) ∥∥∥ 2 / ‖w‖1 − 1 r‖w‖1 Eε N∑ j=1 wjf y0/yi j (x0 + ε). (7)
We have following observations: (1) unlike for standard models with unbounded β, for the smoothed ensemble models, this ERI (Equation (7)) would have guaranteed correlation with the model robustness since β = Θ(1/σ2) is bounded and can be controlled by tuning σ 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 x0 + ε instead of original input x0.
Towards Practical Certification. As outlined at the beginning of this subsection, even with smoothed base models, certifying robustness using Theorem 1 is practically difficult. Therefore, we introduce Ensemble-before-Smoothing strategy as below to construct GεMWE and G ε MMME as approximations of soft ensemble ḠεMWE and Ḡ ε MMME respectively. Definition 5 (Ensemble-before-Smoothing (EBS)). LetM be an ensemble model over base models {Fi}Ni=1 and ε be a random variable. The EBS strategy construct smoothed classifierGεM : Rd → [C] that picks the class with highest smoothed confidence ofM: GεM(x) := arg maxj∈[C] gεM(x)j .
HereM could be eitherMWE orMMME. EBS aims to approximate the soft smoothed ensemble. Formally, use WE as an example, we let fMWE := ∑N j=1 wjfj ‖w‖1 to be WE ensemble’s confidence, then
gεMWE(x)i = EεI[MWE(x + ε) = i] ≈ EεfMWE(x + ε)i = ∑N j=1 wj(ḡ ε fj
)i∑N j=1 wj = ḡεMWE(x)i (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 can leverage randomized smoothing based techniques to compute the robustness certification (see Proposition C.1 in Appendix C).

heading: 2.4 ADDITIONAL PROPERTIES OF ML ENSEMBLES
text: Comparison between Ensemble and Single-Model Robustness. In Appendix B.1, we show Corollary 1, a corollary of Theorem 1, 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 1 and Table 2), though without advanced training approaches such as DRT, the improvement of robustness brought by ensemble itself is marginal. In Appendix B.1, 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 a smoothed model is directly correlated with the probability of correct prediction under smoothed input (see Equation (11) 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 fi(x0 + ε)y0 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 DIVERSITY-REGULARIZED TRAINING Inspired by the above key factors in the sufficient and necessary conditions for the certifiably robust ensembles, we propose the Diversity-Regularized Training (DRT). In particular, let x0 be a training sample, DRT contains the following two regularization terms in the objective function to minimize:
• Gradient Diversity Loss (GD Loss): LGD(x0)ij = ∥∥∇xfy0/y(2)ii (x0)+∇xfy0/y(2)jj (x0)∥∥2. (9)
• Confidence Margin Loss (CM Loss): LCM(x0)ij = f y (2) i /y0 i (x0) + f y (2) j /y0 j (x0). (10)
In Equations (9) and (10), y0 is the ground-truth label of x0, and y (2) i (or y (2) j ) is the runner-up class of base model Fi (or Fj). Intuitively, for each model pair (Fi, Fj) where i, j ∈ [N ] and i 6= j, the GD loss promotes the diversity of gradients between the base model Fi and Fj . Note that the gradient computed here is actually the gradient difference between different labels. As our theorem reveals, it 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 base models’ gradient would hurt the model’s benign accuracy, and solely regularizing gradient diversity is hard to realize due to the boundedness of cosine similarity. The CM loss encourages the large margin between the true and runner-up classes for base models. Both regularization terms are directly motivated by theoretical analysis in Section 2.
For each input x0 with ground truth y0, we use x0 + ε with ε ∼ N (0, σ2Id) as training input for each base model (i.e., Gaussian augmentation). We call two base models ( Fi, Fj ) a valid model pair at (x0, y0) if both Fi(x0 + ε) and Fj(x0 + ε) equal to y0. For every valid model pair, we apply DRT: GD Loss and CM Loss with ρ1 and ρ2 as the weight hyperparameters as below.
Ltrain = ∑ i∈[N ] Lstd(x0 + ε, y0)i + ρ1 ∑
i,j∈[N ],i6=j (Fi, Fj) is valid
LGD(x0 + ε)ij + ρ2 ∑
i,j∈[N ],i6=j (Fi, Fj) is valid
LCM(x0 + ε)ij .
The standard training loss Lstd(x0 + ε, y0)i of each base model Fi 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 (x0 + ε) instead of x0 to 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 et al., 2019; Kariyappa & Qureshi, 2019; Yang et al., 2020b; 2021), or tries to only optimize the weights of Weighted Ensemble (Zhang et al., 2019; Liu et al., 2020). 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 Lp-bounded perturbations such as L1 and L∞ leveraging existing work (Li et al., 2019; Lecuyer et al., 2019; Yang et al., 2020a; Levine & Feizi, 2021).

heading: 4 EXPERIMENTAL EVALUATION
text: 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.

heading: 4.1 EXPERIMENTAL SETUP
text: Baselines. We consider the following state-of-the-art baselines for certified robustness: Gaussian smoothing (Cohen et al., 2019), SmoothAdv (Salman et al., 2019), MACER (Zhai et al., 2019), Stability (Li et 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, SmoothAdv, and MACER on all datasets, and in addition compare it with other baselines on MNIST and CIFAR-10 considering the training efficiency. There are other baselines, e.g., (Jeong & Shin, 2020). However, SmoothAdv performs consistently better across different datasets, so we mainly consider SmoothAdv as our strong baseline.
Models. For base models in our ensemble, we follow the configurations used in baselines: LeNet (LeCun et al., 1998), 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 3 to train the base models. We combine DRT with Gaussian smoothing and SmoothAdv (i.e., instantiating Lstd by either cross-entropy loss (Cohen et al., 2019; Yang et al., 2020a) or adversarial training loss (Salman et 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 ensembleM, using either WE or MME protocol (see Definitions 2 and 3). 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-Smoothing strategy to form a smoothed ensemble (see Definition 5). 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 2.
Evaluation Metric. We report the standard certified accuracy under different L2 radii r’s as our evaluation metric following existing work (Cohen et al., 2019; Yang et al., 2020b; Zhai et al., 2019; Jeong & Shin, 2020). More evaluation details are in Appendix F.

heading: 4.2 EXPERIMENTAL RESULTS
text: Here we consider ensemble models consisting of three base models. We show that 1) DRT-based ensembles outperform the SOTA baselines significantly especially under large perturbation radii; 2) smoothed ensembles are always more certifiably robust than each base model (Corollary 1 in Appendix B.1); 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 1, 2, 3 respectively. It is clear that though the certified accuracy of a single model can be improved by directly applying either MME or WE ensemble training (proved in Corollary 1), 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 1 shows).
From Tables 1 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 radii (over 8% for r = 2.50 on MNIST and 6% for r = 1.50 on CIFAR-10). We also demonstrate the scalability of DRT by training on ImageNet, and Table 3 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.
To evaluate the computational cost of DRT, we analyze the theoretical complexity in Appendix E and compare the efficiency of different methods in practice in Appendices F.1 and F.2. In particular, we show that DRT with Gaussian Smoothing base models even achieves around two times speedup compared with SmoothAdv with comparable or even higher certified robustness, since DRT does not require adversarial training. More discussions about hyper-parameters 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 different perturbation radii in Figure 3. For each radius r, we present the best certified accuracy among different smoothing parameters σ ∈ {0.25, 0.50, 1.00}. We notice that while simply applying MME or WE protocol could slightly improve the certified accuracy, DRT could significantly boost the certified accuracy under different radii. We also present the trends of different smoothing parameters separately in Appendix F which lead to similar conclusions.

heading: Effects of GD and CM Losses in DRT.
text: To explore the effects of individual Gradient Diversity and Confidence Margin Losses in DRT, we set ρ1 or ρ2 to 0 separately and tune the other for evaluation on MNIST and CIFAR-10. The full results are shown in Appendix G.1. We observe that both GD and CM losses have positive effects on improving the certified accuracy, and GD plays a major role on larger radii. By combining these two regularization losses as DRT does, the ensemble
model achieves the highest certified accuracy under all radii.

heading: 5 CONCLUSION
text: In this paper, we explored and characterized the robustness conditions for certifiably robust ensemble ML models theoretically, and proposed DRT for training a robust ensemble. Our analysis provided the justification of the regularization-based training approach DRT. Extensive experiments showed that DRT-enhanced ensembles achieve the highest certified robustness compared with existing baselines.
Ethics Statement. In this paper, we characterized the robustness conditions for certifying ML ensemble 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 ML ensemble. On the other hand, the trained ML 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 DRT-trained ensembles, and should not blindly rely on the ensembles when the attack can cause large deviations measured by L2 distance. As a 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, CIFAR10, and ImageNet datasets. Finally, we upload the source code as the supplementary material for reproducibility purpose.

heading: A BACKGROUND: RANDOMIZED SMOOTHING
text: Cohen et al. (Cohen et al., 2019) leverage Neyman-Pearson 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)). At point x0, let random variable ε ∼ N (0, σ2Id), a smoothed model GεF is r-robust where
r = σ
2
( Φ−1 (gεF (x0)cA)− Φ−1 (gεF (x0)cB ) ) , (11)
where cA = GεF (x0) and cB = G ε(2) F (x0) are the top and runner-up class respectively, and Φ −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): r = σΦ−1(gεF (x0)cA). Now we only need to figure out g ε F (x0)cA . 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 gεF (x0)cA = Prε∼N (0,σ2Id)(F (x0 + ε) = cA), we sample n Gaussian noises: ε1, ε2, . . . , εn ∼ N (0, σ2Id) and compute the empirical mean: ĝεF (x0)cA = 1n ∑n i=1 I[F (x0 + εi) = cA]. The binomial testing Clopper & Pearson (1934) then gives a high-confidence lower bound of gεF (x0)cA based on ĝεF (x0)cA . We follow the setting in the literature: sample n = 10
5 samples and set confidence level be 99.9% Cohen et al. (2019); Yang et al. (2020a); Zhai et al. (2019); Jeong & Shin (2020). More details are available in Appendix F. Note that F could be either single model or any ensemble models with Ensemble-before-Smoothing strategy.

heading: B DETAILED ANALYSIS AND PROOFS IN SECTION 2
text: In this appendix, we first show the omitted theoretical results in Section 2, which are the robustness conditions for Max-Margin Ensemble (MME) and the comparison between the robustness of ensemble model and single model. We then present all proofs for these theoretical results.

heading: B.1 DETAILED THEORETICAL RESULTS AND DISCUSSION
text: Here we present the theoretical results omitted from Section 2 along with some discussions.

heading: B.1.1 ROBUSTNESS CONDITION OF MME
text: For MME, we have the following robustness condition.
Theorem 3 (Gradient and Confidence Margin Condition for MME Robustness). Given input x0 ∈ Rd with ground-truth label y0 ∈ [C], and MMME as an MME defined over base models {F1, F2}. MMME(x0) = y0. Both F1 and F2 are β-smooth.
• (Sufficient Condition) If for any y1, y2 ∈ [C] such that y1 6= y0 and y2 6= y0,
‖∇xfy0/y11 (x0) +∇xf y0/y2 2 (x0)‖2 ≤
1 r (f y0/y1 1 (x0) + f y0/y2 2 (x0))− 2βr, (12)
thenMMME is r-robust at point x0.
• (Necessary Condition) Suppose for any x ∈ {x0 +δ : ||δ||2 ≤ r}, for any i ∈ {1, 2}, either Fi(x) = y0 or F (2) i (x) = y0. IfMMME is r-robust at point x0, then for any y1, y2 ∈ [C]
such that y1 6= y0 and y2 6= y0,
‖∇xfy0/y11 (x0) +∇xf y0/y2 2 (x0)‖2 ≤
1 r (f y0/y1 1 (x0) + f y0/y2 2 (x0)) + 2βr. (13)
Comparing with the robustness conditions of MME (Theorem 1), 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-smoothness bound β. A major distinction is that the condition for MME is limited to two base models. This is because the “maximum” operator in MME protocol poses difficulties for expressing the robust conditions in succinct 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 is proved in Appendix B.2.

heading: B.1.2 COMPARISON BETWEEN ENSEMBLE ROBUSTNESS AND SINGLE-MODEL ROBUSTNESS
text: To compare the robustness of ensemble models and single models, we have the following corollary that is extended from Theorem 1 and Theorem 3.
Corollary 1 (Comparison of Ensemble and Single-Model Robustness). Given an input x0 ∈ Rd with ground-truth label y0 ∈ [C]. Suppose we have two β-smooth base models {F1, F2}, which are both r-robust at point x0. For any ∆ ∈ [0, 1):
• (Weighted Ensemble) Define Weighted Ensemble MWE with base models {F1, F2}. Suppose MWE(x0) = y0. If for any label yi 6= y0, the base models’ smoothness β ≤ ∆ · min{fy0/yi1 (x0), f y0/yi 2 (x0)}/(c2r2), and the gradient cosine similarity
cos〈∇xfy0/yi1 (x0),∇xf y0/yi 2 (x0)〉 ≤ cos θ, then the MWE with weights {w1, w2} is at least R-robust at point x0 with
R = r · 1−∆ 1 + ∆ (1− CWE(1− cos θ))− 1/2 ,where (14)
CWE = min yi:yi 6=y0
2w1w2f y0/yi 1 (x0)f y0/yi 2 (x0)
(w1f y0/yi 1 (x0)+w2f y0/yi 2 (x0))
2 , c = max{ 1−∆1+∆ (1− CWE(1− cos θ)) −1/2 , 1}.
• (Max-Margin Ensemble) Define Max-Margin EnsembleMMME with the base models {F1, F2}. Suppose MMME(x0) = y0. If for any label y1 6= y0 and y2 6= y0, the base models’ smoothness β ≤ ∆ · min{fy0/y11 (x0), f y0/y2 2 (x0)}/(c2r2), and the gradient cosine similarity
cos〈∇xfy0/y11 (x0),∇xf y0/y2 2 (x0)〉 ≤ cos θ, then the MMME is at least R-robust at point x0 with
R = r · 1−∆ 1 + ∆ (1− CMME(1− cos θ))− 1/2 ,where (15)
CMME = miny1,y2: y1,y2 6=y0
2f y0/y1 1 (x0)f y0/y2 2 (x0)
(f y0/y1 1 (x0)+f y0/y2 2 (x0))
2 , c = max{ 1−∆1+∆ (1− CMME(1− cos θ)) −1/2 , 1}.
The proof is given in Appendix B.3.
Optimizing Weighted Ensemble. As we can observe from Corollary 1, we can adjust the weights {w1, w2} for Weighted Ensemble to change CWE and the certified robust radius (Equation (14)).
Then comes the problem of which set of weights can achieve the highest certified robust radius. Since larger CWE results in higher radius, we need to choose
(wOPT1 , w OPT 2 ) = arg max
w1,w2 min yi:yi 6=y0
2w1w2f y0/yi 1 (x0)f y0/yi 2 (x0)
(w1f y0/yi 1 (x0) + w2f y0/yi 2 (x0))
2 .
Since this quantity is scale-invariant, we can fix w1 and optimize over w2 to get the optimal weights. In particular, if there are only two classes, we have a closed-form solution
(wOPT1 , w OPT 2 ) = arg max
w1,w2
2w1w2f y0/y1 1 (x0)f y0/y1 2 (x0)
(w1f y0/y1 1 (x0) + w2f y0/y1 2 (x0)) 2
= {k · fy0/y12 (x0), k · f y0/y1 1 (x0) : k ∈ R+},
and corresponding CWE achieves the maximum 1/2.
For a special case—average weighted ensemble, we get the corresponding certified robust radius by setting w1 = w2 and plug the yielded
CWE = min yi:yi 6=y0
2f y0/yi 1 (x0)f y0/yi 2 (x0)
(f y0/yi 1 (x0) + f y0/yi 2 (x0))
2 ∈ (0, 1/2].
into Equation (14).
Comparison between ensemble and single-model robustness. The similar forms of R in the corollary allow us to discuss the Weighted Ensemble and Max-Margin Ensemble together. Specifically, we let C be either CWE or CMME, then
R = r · 1−∆ 1 + ∆ (1− C(1− cos θ))−1/2 .
Since when R > r, both ensembles have higher certified robustness than the base models, we solve this condition for cos θ:
R > r ⇐⇒ (
1−∆ 1 + ∆
)2 > 1− C(1− cos θ) ⇐⇒ cos θ ≤ 1− 4∆
C(1 + ∆)2 .
Notice that C ∈ (0, 1/2]. From this condition, we can easily observe that when the gradient cosine similarity is smaller, it 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 β, we can notice that ∆ could be close to zero. As a result, 1 − 4∆C(1+∆)2 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 methodology, we can further observe that larger number of 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 x0 ∈ Rd with ground-truth label y0 ∈ [C], suppose all base models {fi}N+Mi=1 are β-smooth. Suppose the Weighted EnsembleM1 of base models {fi}Ni=1 andM2 of base models {fi}N+Mi=N+1 are both r-robust according to the sufficient condition in Theorem 1, and for any yi 6= y0 the M1 and M2’s ensemble gradients ( ∑N j=1 wj∇xf y0/yi j (x0) and ∑N+M j=N+1 wj∇xf y0/yi j (x0)) are non-zero and not colinear, then the Weighted EnsembleM of {fi}N+Mi=1 is r′-robust for some r′ > r.
Proof of Proposition B.1. For any yi 6= y0, since bothM1 andM2 are r-robust according to the sufficient condition of Theorem 1, we have∥∥∥ N∑
j=1
wj∇xfy0/yij (x0) ∥∥∥
2 ≤ 1 r N∑ j=1 f y0/yi j (x0)− βr N∑ j=1 wj , (16)
∥∥∥ N+M∑ j=N+1 wj∇xfy0/yij (x0) ∥∥∥ 2 ≤ 1 r N+M∑ j=N+1 f y0/yi j (x0)− βr N+M∑ j=N+1 wj . (17)
Adding above two inequalties we get∥∥∥ N∑ j=1 wj∇xfy0/yij (x0) ∥∥∥ 2 + ∥∥∥ N+M∑ j=N+1 wj∇xfy0/yij (x0) ∥∥∥ 2 ≤ 1 r N+M∑ j=1 f y0/yi j (x0)− βr N+M∑ j=1 wj . (18) Since gradients of ensemble are not colinear and non-zero, from the triangle inequality,∥∥∥N+M∑
j=1
wj∇xfy0/yij (x0) ∥∥∥ 2 < ∥∥∥ N∑ j=1 wj∇xfy0/yij (x0) ∥∥∥ 2 + ∥∥∥ N+M∑ j=N+1 wj∇xfy0/yij (x0) ∥∥∥ 2 (19)
and thus ∥∥∥N+M∑ j=1 wj∇xfy0/yij (x0) ∥∥∥ 2 < 1 r N+M∑ j=1 f y0/yi j (x0)− βr N+M∑ j=1 wj , (20) which means we can increase r to r′ and still keep the inequality hold with “≤”, and in turn certify a larger radius r′ according to Theorem 1.
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.

heading: B.1.3 ROBUSTNESS CONDITIONS FOR SMOOTHED ENSEMBLE MODELS
text: Following the discussion in Section 2.3, for smoothed WE and MME, with the model-smoothness bound (Theorem 2), we can concretize the general robustness conditions in this way.
We define the soft smoothed confidence function ḡεf (x) := Eεf(x+ ε). This definition is also used in the literature (Salman et al., 2019; Zhai et al., 2019; Kumar et al., 2020). As a result, we revise the ensemble protocols of WE and MME by replacing the original confidences {fi(x0)}Ni=1 with these soft smoothed confidences {ḡεi (x0)}Ni=1. These protocols then choose the predicted class by treating these {ḡεi (x0)}Ni=1 as the base models’ confidence scores. In 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 2 (Gradient and Confidence Margin Conditions for Smoothed WE Robustness). Given input x0 ∈ Rd with ground-truth label y0 ∈ [C]. Let ε ∼ N (0, σ2Id) be a Gaussian random variable. Define soft smoothed confidence ḡεi (x) := Eεfi(x+ ε) for each base model Fi (1 ≤ i ≤ N ). The ḠεMWE is a WE defined over soft smoothed base models {ḡ ε i }Ni=1 with weights {wi}Ni=1. ḠεMWE(x0) = y0.
• (Sufficient Condition) The ḠεMWE is r-robust at point x0 if for any yi 6= y0,∥∥∥ N∑ j=1 wj∇x(ḡεj )y0/yi(x0) ∥∥∥ 2 ≤ 1 r N∑ j=1 wj(ḡ ε j ) y0/yi(x0)− 2r σ2 N∑ j=1 wj , (21)
• (Necessary Condition) If ḠεMWE is r-robust at point x0, for any yi 6= y0,∥∥∥ N∑ j=1 wj∇x(ḡεj )y0/yi(x0) ∥∥∥ 2 ≤ 1 r N∑ j=1 wj(ḡ ε j ) y0/yi(x0) + 2r σ2 N∑ j=1 wj . (22)
Corollary 3 (Gradient and Confidence Margin Condition for Smoothed MME Robustness). Given input x0 ∈ Rd with ground-truth label y0 ∈ [C]. Let ε ∼ N (0, σ2Id) be a Gaussian random variable. Define soft smoothed confidence ḡεi (x) := Eεfi(x + ε) for either base model F1 or F2. The ḠεMMME is a MME defined over soft smoothed base models {ḡ ε 1, ḡ ε 2}. ḠεMMME(x0) = y0.
• (Sufficient Condition) If for any y1, y2 ∈ [C] such that y1 6= y0 and y2 6= y0,
‖∇x(ḡε1)y0/y1(x0) +∇x(ḡε2)y0/y2(x0)‖2 ≤ 1
r ((ḡε1) y0/y1(x0) + (ḡ ε 2) y0/y2(x0))−
4r σ2 ,
(23) then ḠεMMME is r-robust at point x0.
• (Necessary Condition) Suppose for any x ∈ {x0 + δ : ||δ||2 ≤ r}, for any i ∈ {1, 2}, either GFi(x) = y0 or G (2) Fi
(x) = y0. If ḠεMMME is r-robust at point x0, then for any y1, y2 ∈ [C] such that y1 6= y0 and y2 6= y0,
‖∇x(ḡε1)y0/y1(x0) +∇x(ḡε2)y0/y2(x0)‖2 ≤ 1
r ((ḡε1) y0/y1(x0) + (ḡ ε 2) y0/y2(x0)) +
4r σ2 .
(24) Remark. The above two corollaries are extended from Theorem 1 and Theorem 3 respectively, and correspond to our discussion in Section 2.3. We defer the proofs to Appendix B.5. From these two corollaries, we can explicit see that the Ensemble-before-Smoothing (see Definition 5) provides smoothed classifiers ḠεMWE and Ḡ ε MMME with bounded model-smoothness; and we can see the correlation between the robustness conditions and gradient diversity/confidence margin for smoothed ensembles.

heading: B.2 PROOFS OF ROBUSTNESS CONDITIONS FOR GENERAL ENSEMBLE MODELS
text: This subsection contains the proofs of robustness conditions. First, we connect the prediction of ensemble models with the arithmetic relations of confidence scores of base models. This connection is straightforward to establish for Weighted Ensemble (shown in Proposition B.2), but nontrivial for Max-Margin Ensemble (shown in Theorem 4). Then, we prove the desired robustness conditions using Taylor expansion with Lagrange reminder. Proposition B.2 (Robustness Condition for WE). Consider an input x0 ∈ Rd with ground-truth label y0 ∈ [C], and an ensemble modelMWE constructed by base models {Fi}Ni=1 with weights {wi}Ni=1. SupposeMWE(x0) = y0. Then, the ensembleMWE is r-robust at point x0 if and only if for any x ∈ {x0 + δ : ‖δ‖2 ≤ r},
min yi∈[C]:yi 6=y0 N∑ j=1 wjf y0/yi j (x) ≥ 0. (25)
Proof of Proposition B.2. According the the definition of r-robust, we knowMWE is r-robust if and only if for any point x := x0 + δ where ‖δ‖2 ≤ r,MWE(x0 + δ) = y0, which means that for any other label yi 6= y0, the confidence score for label y0 is larger or equal than the confidence score for label yi. It means that
N∑ j=1 wjfj(x)y0 ≥ N∑ j=1 wjfj(x)yi
for any x ∈ {x0 + δ : ‖δ‖2 ≤ r}. Since this should hold for any yi 6= y0, we have the sufficient and necessary condition
min yi∈[C]:yi 6=y0 N∑ j=1 wjf y0/yi j (x) ≥ 0. (25)
Theorem 4 (Robustness Condition for MME). Consider an input x0 ∈ Rd with ground-truth label y0 ∈ [C]. LetMMME be an MME defined over base models {Fi}Ni=1. Suppose: (1)MMME(x0) = y0; (2) for any x ∈ {x0 + δ : ‖δ‖2 ≤ r}, given any base model i ∈ [N ], either Fi(x) = y0 or F (2)i (x) = y0. Then, the ensemble MMME is r-robust at point x0 if and only if for any x ∈ {x0 + δ : ‖δ‖2 ≤ r},
max i∈[N ] min yi∈[C]:yi 6=y0
f y0/yi i (x) ≥ max
i∈[N ] min y′i∈[C]:y′i 6=y0 f y′i/y0 i (x). (26)
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:
max i∈[N ] min yi∈[C]:yi 6=y0
f y0/yi i (x) + min
i∈[N ] min y′i∈[C]:y′i 6=y0 f y0/y
′ i
i (x) ≥ 0. (26)
Lemma B.1 (Sufficient Condition for MME). LetMMME be an MME defined over base models {Fi}Ni=1. For any input x0 ∈ Rd, the Max-Margin EnsembleMMME predictsMMME(x0) = y0 if
max i∈[N ] min yi∈[C]:yi 6=y0
f y0/yi i (x0) + min
i∈[N ] min y′i∈[C]:y′i 6=y0 f y0/y
′ i
i (x0) ≥ 0. (26)
Proof of Lemma B.1. For brevity, for i ∈ [N ], we denote yi := Fi(x0), y′i := F (2) i (x0) for each base model’s top class and runner-up class at point x0.
SupposeMMME(x0) 6= y0, then according to ensemble definition (see Definition 3), there exists c ∈ [N ], such thatMMME(x0) = Fc(x0) = yc, and
∀i ∈ [N ], i 6= c, fc(x0)yc/y ′ c > fi(x0) yi/y ′ i . (27)
Because yc 6= y0, we have fc(x0)y0 ≤ fc(x0)y′c , so that fc(x0) yc/y0 ≥ fc(x0)yc/y
′ c . Now consider
any model Fi where i ∈ [N ], we would like to show that there exists y∗ 6= y0, such that fi(x0)yi/y ′ i ≥ fi(x0) y0/y ∗ :
• If yi = y0, let y∗ := y′i, trivially fi(x0)yi/y ′ i = fi(x0) y0/y ∗ ;
• If yi 6= y0, and y′i 6= y0, we let y∗ := y′i, then fi(x0)yi/y ′ i = fi(x0) yi/y ∗ ≥ fi(x0)y0/y ∗ ;
• If yi 6= y0, but y′i = y0, we let y∗ := yi, then fi(x0)yi/y ′ i = fi(x0)
yi/y0 ≥ fi(x0)y0/yi = fi(x0) y0/y ∗ .
Combine the above findings with Equation 27, we have:
∀i ∈ [N ], i 6= c, ∃y∗c ∈ [C] and y∗c 6= y0, ∃y∗i ∈ [C] and y∗i 6= y0, fc(x0)y ∗ c/y0 > fi(x0) y0/y ∗ i .
Therefore, its negation
∃i ∈ [N ], i 6= c, ∀y∗c ∈ [C] and y∗c 6= y0, ∀y∗i ∈ [C] and y∗i 6= y0, fc(x0)y0/y ∗ c + fi(x0) y0/y ∗ i ≥ 0 (28) impliesM(x0) = y0. Since Equation (28) holds for any y∗c and y∗i , the equation is equivalent to
∃i ∈ [N ], i 6= c, min yc∈[C]:yc 6=y0 fc(x0) y0/yc(x0) + min y′i∈[C]:y′i 6=y0 fi(x0)
y0/y ′ i(x0) ≥ 0.
The existence qualifier over i can be replaced by maximum:
min yc∈[C]:yc 6=y0
fc(x0) y0/yc(x0) + max
i∈[N ] min y′i∈[C]:y′i 6=y0 fi(x0)
y0/y ′ i(x0) ≥ 0.
It is implied by
max i∈[N ] min yi∈[C]:yi 6=y0
f y0/yi i (x0) + min
i∈[N ] min y′i∈[C]:y′i 6=y0 f y0/y
′ i
i (x0) ≥ 0. (26)
Thus, Equation (26) is a sufficient condition forMMME(x0) = y0.
Lemma B.2 (Necessary Condition for MME). For any input x0 ∈ Rd, if for any base model i ∈ [N ], either Fi(x0) = y0 or F (2)i (x0) = y0, then Max-Margin EnsembleMMME predicting MMME(x0) = y0 implies
max i∈[N ] min yi∈[C]:yi 6=y0
f y0/yi i (x0) + min
i∈[N ] min y′i∈[C]:y′i 6=y0 f y0/y
′ i
i (x0) ≥ 0. (26)
Proof of Lemma B.2. Similar as before, for brevity, for i ∈ [N ], we denote yi := Fi(x0), y′i := F
(2) i (x0) for each base model’s top class and runner-up class at point x0.
Suppose Equation (26) is not satisfied, it means that
∃c ∈ [N ], ∃y∗c ∈ [C] and y∗c 6= y0, ∀i ∈ [N ], ∃y∗i ∈ [C] and y∗i 6= y0, f y∗c/y0 c (x0) > f y0/y ∗ i i (x0).
• If yc = y0, then f y∗c/y0 c (x0) ≤ 0, which implies that f y0/y ∗ i
i (x0) < 0, and hence Fi(x0) 6= y0. Moreover, we know that f yi/y ′ i i (x0) = f yi/y0 i (x0) ≥ f y∗i /y0 i (x0) > f y0/y ∗ c
c (x0) ≥ f y0/y ′ c c (x0) = f yc/y ′ c c (x0) soM(x0) 6= Fc(x0) = y0.
• If yc 6= y0, i.e., y′c = y0, then f yc/y0 c (x0) ≥ f y∗c/y0 c (x0) > f y0/y ∗ 1
i (x0). If Fi(x0) = y0, then f y0/y ∗ i i (x0) ≥ f y0/y ′ i i (x0) = f yi/y ′ i i (x0). Thus, f yc/y ′ c c (x0) = f yc/y0 c (x0) > f yi/y ′ i
i (x0). As the result,M(x0) = Fc(x0) 6= y0.
For both cases, we show thatMMME(x0) 6= y0, i.e., Equation (26) is a necessary condition for M(x0) = y0.
Proof of Theorem 4. Lemmas B.1 and B.2 are exactly the two directions (necessary and sufficient condition) ofMMME predicting label y0 at point x. Therefore, if the condition (Equation (26)) holds for any x ∈ {x0 + δ : ‖δ‖2 ≤ r}, the ensembleMMME is r-robust at point x0; 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 x0 ∈ Rd with ground-truth label y0 ∈ [C]. Suppose a model F satisfies F (x0) = y0. Then, the model F is r-robust at point x0 if and only if for any x ∈ {x0 + δ : ‖δ‖2 ≤ r},
min yi∈[C]:yi 6=y0
fy0/yi(x) ≥ 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 1 (Gradient and Confidence Margin Condition for WE Robustness). Given input x0 ∈ Rd with ground-truth label y0 ∈ [C], andMWE as a WE defined over base models {Fi}Ni=1 with weights {wi}Ni=1.MWE(x0) = y0. All base model Fi’s are β-smooth.
• (Sufficient Condition)MWE is r-robust at point x0 if for any yi 6= y0,∥∥∥ N∑ j=1 wj∇xfy0/yij (x0) ∥∥∥ 2 ≤ 1 r N∑ j=1 wjf y0/yi j (x0)− βr N∑ j=1 wj . (4)
• (Necessary Condition) IfMWE is r-robust at point x0, then for any yi 6= y0,∥∥∥ N∑ j=1 wj∇xfy0/yij (x0) ∥∥∥ 2 ≤ 1 r N∑ j=1 wjf y0/yi j (x0) + βr N∑ j=1 wj . (5)
Proof of Theorem 1. From Taylor expansion with Lagrange remainder and the β-smoothness assumption on the base models, we have N∑ j=1 wjf y0/yi j (x0)− r ∥∥∥ N∑ j=1 wj∇xfy0/yij (x0) ∥∥∥ 2 − 1 2 r2 N∑ j=1 (2βwj) ≤ min x:‖x−x0‖2≤r N∑ j=1 wjf y0/yi j (x)
≤ N∑ j=1 wjf y0/yi j (x0)− r ∥∥∥ N∑ j=1 wj∇xfy0/yij (x0) ∥∥∥ 2 + 1 2 r2 N∑ j=1 (2βwj),
(29)
where the term −1 2 r2 ∑N j=1(2βwj) and 1 2 r2 ∑N j=1(2βwj) are bounded from Lagrange remainder. Note that the difference fy0/yij is (2β)-smooth instead of β-smooth since it is the difference of two
β-smooth function, and thus ∑N j=1 wjf y0/yi j is ∑N j=1(2βwj)-smooth. From Proposition B.2, the
sufficient and necessary condition of WE’s r-robustness is ∑N j=1 wjf y0/yi j (x) ≥ 0 for any yi ∈ [C] such that yi 6= y0, and any x = x0 + δ where ‖δ‖2 ≤ r. Plugging this term into Equation (29) we get the theorem.
Theorem 3 (Gradient and Confidence Margin Condition for MME Robustness). Given input x0 ∈ Rd with ground-truth label y0 ∈ [C], and MMME as an MME defined over base models {F1, F2}. MMME(x0) = y0. Both F1 and F2 are β-smooth.
• (Sufficient Condition) If for any y1, y2 ∈ [C] such that y1 6= y0 and y2 6= y0,
‖∇xfy0/y11 (x0) +∇xf y0/y2 2 (x0)‖2 ≤
1 r (f y0/y1 1 (x0) + f y0/y2 2 (x0))− 2βr, (12)
thenMMME is r-robust at point x0.
• (Necessary Condition) Suppose for any x ∈ {x0 +δ : ||δ||2 ≤ r}, for any i ∈ {1, 2}, either Fi(x) = y0 or F (2) i (x) = y0. IfMMME is r-robust at point x0, then for any y1, y2 ∈ [C]
such that y1 6= y0 and y2 6= y0,
‖∇xfy0/y11 (x0) +∇xf y0/y2 2 (x0)‖2 ≤
1 r (f y0/y1 1 (x0) + f y0/y2 2 (x0)) + 2βr. (13)
Proof of Theorem 3. We prove the sufficient condition and necessary condition separately.
• (Sufficient Condition) From Lemma B.1, since there are only two base models, we can simplify the sufficient condition forMMME(x) = y0 as
min yi∈[C]:yi 6=y0
f y0/yi 1 (x) + min y′i∈[C]:y′i 6=y0 f y0/y
′ i
2 (x) ≥ 0.
In other words, for any y1 6= y0 and y2 6= y0,
f y0/y1 1 (x) + f y0/y2 2 (x) ≥ 0. (30)
With Taylor expansion and model-smoothness assumption, we have
min x:‖x−x0‖2≤r
f y0/y1 1 (x) + f y0/y2 2 (x)
≥fy0/y11 (x0) + f y0/y2 2 (x0)− r‖∇xf y0/y1 1 (x0) +∇xf y0/y2 2 (x0)‖2 −
1 2 · 4βr2.
Plugging this into Equation (30) yields the sufficient condition.
In the above equation, the term − 12 · 4βr 2 is bounded from Lagrange remainder. Here, the 4β term comes from the fact that fy0/y11 (x) + f y0/y2 2 (x) is (4β)-smooth since it is the sum of difference of β-smooth function.
• (Necessary Condition) From Lemma B.2, similarly, the necessary condition forMMME(x) = y0 is simplified to: for any y1 6= y0 and y2 6= y0,
f y0/y1 1 (x) + f y0/y2 2 (x) ≥ 0. (30)
Again, from Taylor expansion, we have
min x:‖x−x0‖2≤r
f y0/y1 1 (x) + f y0/y2 2 (x)
≤fy0/y11 (x0) + f y0/y2 2 (x0)− r‖∇xf y0/y1 1 (x0) +∇xf y0/y2 2 (x0)‖2 +
1 2 · 4βr2.
Plugging this into Equation (30) yields the necessary condition.
In the above equation, the term + 12 · 4βr 2 is bounded from Lagrange remainder. The 4β term appears because of the same reason as 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-Model Robustness). Given input x0 ∈ Rd with ground-truth label y0 ∈ [C]. Model F (x0) = y0, and it is β-smooth.
• (Sufficient Condition) If for any y1 ∈ [C] such that y1 6= y0,
‖∇xfy0/y1(x0)‖2 ≤ 1
r fy0/y1(x0)− βr, (31)
F is r-robust at point x0.
• (Necessary Condition) If F is r-robust at point x0, for any y1 ∈ [C] such that y1 6= y0,
‖∇xfy0/y1(x0)‖2 ≤ 1
r fy0/y1(x0) + βr. (32)
Proof of Proposition B.3. This proposition is apparent given the following inequality from Taylor expansion
fy0/y1(x0)−r‖∇xfy0/y1(x0)‖2−βr2 ≤ min x:‖x−x0‖2≤r fy0/y1(x) ≤ fy0/y1(x0)−r‖∇xfy0/y1(x0)‖2+βr2
and the sufficient and necessary robust condition in Fact B.1.

heading: B.3 PROOF OF ROBUSTNESS COMPARISON RESULTS BETWEEN ENSEMBLE MODELS AND SINGLE MODELS
text: Corollary 1 (Comparison of Ensemble and Single-Model Robustness). Given an input x0 ∈ Rd with ground-truth label y0 ∈ [C]. Suppose we have two β-smooth base models {F1, F2}, which are both r-robust at point x0. For any ∆ ∈ [0, 1):
• (Weighted Ensemble) Define Weighted Ensemble MWE with base models {F1, F2}. Suppose MWE(x0) = y0. If for any label yi 6= y0, the base models’ smoothness β ≤ ∆ · min{fy0/yi1 (x0), f y0/yi 2 (x0)}/(c2r2), and the gradient cosine similarity
cos〈∇xfy0/yi1 (x0),∇xf y0/yi 2 (x0)〉 ≤ cos θ, then the MWE with weights {w1, w2} is at least R-robust at point x0 with
R = r · 1−∆ 1 + ∆ (1− CWE(1− cos θ))− 1/2 ,where (14)
CWE = min yi:yi 6=y0
2w1w2f y0/yi 1 (x0)f y0/yi 2 (x0)
(w1f y0/yi 1 (x0)+w2f y0/yi 2 (x0))
2 , c = max{ 1−∆1+∆ (1− CWE(1− cos θ)) −1/2 , 1}.
• (Max-Margin Ensemble) Define Max-Margin EnsembleMMME with the base models {F1, F2}. Suppose MMME(x0) = y0. If for any label y1 6= y0 and y2 6= y0, the base models’ smoothness β ≤ ∆ · min{fy0/y11 (x0), f y0/y2 2 (x0)}/(c2r2), and the gradient cosine similarity
cos〈∇xfy0/y11 (x0),∇xf y0/y2 2 (x0)〉 ≤ cos θ, then the MMME is at least R-robust at point x0 with
R = r · 1−∆ 1 + ∆ (1− CMME(1− cos θ))− 1/2 ,where (15)
CMME = miny1,y2: y1,y2 6=y0
2f y0/y1 1 (x0)f y0/y2 2 (x0)
(f y0/y1 1 (x0)+f y0/y2 2 (x0))
2 , c = max{ 1−∆1+∆ (1− CMME(1− cos θ)) −1/2 , 1}.
Proof of Corollary 1. We first prove the theorem for Weighted Ensemble. For arbitrary yi 6= y0, we have
‖w1∇xfy0/yi1 (x0) + w2∇xf y0/yi 2 (x0)‖2
= √ w21‖∇xf y0/yi 1 (x0)‖22 + w22‖∇xf y0/yi 2 (x0)‖22 + 2w1w2〈∇xf y0/yi 1 (x0), f y0/yi 2 (x0)〉
≤ √ w21‖∇xf y0/yi 1 (x0)‖22 + w22‖∇xf y0/yi 2 (x0)‖22 + 2w1w2‖∇xf y0/yi 1 (x0)‖2‖∇xf y0/yi 2 (x0)‖2 cos θ
(i.) ≤ √ w21 ( 1
r f y0/yi 1 (x0) + βr
)2 + w22 ( 1
r f y0/yi 2 (x0) + βr
)2 + 2w1w2 ( 1
r f y0/yi 1 (x0) + βr
)( 1
r f y0/yi 2 (x0) + βr
) cos θ
= 1
r
√ w21 ( f y0/yi 1 (x0) + βr 2 )2 + w22 ( f y0/yi 2 (x0) + βr 2 )2 + 2w1w2 ( f y0/yi 1 (x0) + βr 2 )( f y0/yi 2 (x0) + βr 2 ) cos θ
(ii.) ≤ 1 r · ( 1 + ∆ c2 )√ w21f y0/yi 1 (x0) 2 + w22f y0/yi 2 (x0) 2 + 2w1w2f y0/yi 1 (x0)f y0/yi 2 (x0) cos θ
= 1 r · ( 1 + ∆ c2 )√( w1f y0/yi 1 (x0) + w2f y0/yi 2 (x0) )2 − 2(1− cos θ)w1fy0/yi1 (x0)w2f y0/yi 2 (x0)
(iii.) ≤ 1 r · ( 1 + ∆ c2 )√ 1− (1− cos θ)CWE ( w1f y0/yi 1 (x0) + w2f y0/yi 2 (x0) ) where (i.) follows from the necessary condition in Proposition B.3; (ii.) uses the condition on β; and (iii.) replaces 2w1w2f y0/yi 1 (x0)f y0/yi 2 (x0) leveraging CWE. Now, we define
K := 1−∆ 1 + ∆ (1− CWE(1− cos θ))− 1/2 .
All we need to do is to prove thatMWE is robust within radius Kr. To do so, from Equation (4), we upper bound ‖w1∇xfy0/yi1 (x0) + w2∇xf y0/yi 2 (x0)‖2 by 1Kr ( w1f y0/yi 1 (x0) + w2f y0/yi 2 (x0) ) −
βKr(w1 + w2):
‖w1∇xfy0/yi1 (x0) + w2∇xf y0/yi 2 (x0)‖2 ≤1 r · ( 1 + ∆ c2 )√ 1− (1− cos θ)CWE ( w1f y0/yi 1 (x0) + w2f y0/yi 2 (x0) ) ≤1 r (1 + ∆) √ 1− (1− cos θ)CWE ( w1f y0/yi 1 (x0) + w2f y0/yi 2 (x0)
) = 1
r · 1−∆
1−∆ 1+∆ (1− (1− cos θ)CWE)
−1/2
( w1f y0/yi 1 (x0) + w2f y0/yi 2 (x0) ) = 1
Kr (1−∆)
( w1f y0/yi 1 (x0) + w2f y0/yi 2 (x0) ) ≤ 1 Kr ( w1f y0/yi 1 (x0) + w2f y0/yi 2 (x0)−∆ min{f y0/yi 1 (x0), f y0/yi 2 (x0)}(w1 + w2) ) .
Notice that ∆ min{fy0/yi1 (x0), f y0/yi 2 (x0)} ≥ βc2r2 from β’s condition, so
‖w1∇xfy0/yi1 (x0) + w2∇xf y0/yi 2 (x0)‖2
≤ 1 Kr
( w1f y0/yi 1 (x0) + w2f y0/yi 2 (x0)− βc2r2(w1 + w2) ) = 1
Kr
( w1f y0/yi 1 (x0) + w2f y0/yi 2 (x0) ) − βKr(w1 + w2) · c2
K2
≤ 1 Kr
( w1f y0/yi 1 (x0) + w2f y0/yi 2 (x0) ) − βKr(w1 + w2).
From Equation (4), the theorem for Weighted Ensemble is proved.
Now we prove the theorem for Max-Margin Ensemble. Similarly, for any arbitrary y1, y2 such that y1 6= y0, y2 6= y0, we have
‖∇xfy0/y11 (x0) +∇xf y0/y2 2 (x0)‖2 ≤1 r · ( 1 + ∆ c2 )√ 1− (1− cos θ)CMME ( f y0/y1 1 (x0) + f y0/y2 2 (x0) ) .
Now we define K ′ :=
1−∆ 1 + ∆ (1− CMME(1− cos θ))− 1/2 .
Again, from β’s condition we have ∆ min{fy0/y11 (x0), f y0/y2 2 (x0)} ≥ βc2r2 and
‖∇xfy0/y11 (x0) +∇xf y0/y2 2 (x0)‖2 ≤
1
K ′r
( f y0/yi 1 (x0) + f y0/yi 2 (x0) ) − 2βK ′r.
From Equation (12), the ensemble is (K ′r)-robust at point x0, i.e., the theorem for Max-Margin Ensemble is proved.

heading: B.4 PROOFS OF MODEL-SMOOTHNESS BOUNDS FOR RANDOMIZED SMOOTHING
text: Theorem 2 (Model-Smoothness Upper Bound for ḡεf ). Let ε ∼ N (0, σ2Id) be a Gaussian random variable, then the soft smoothed confidence function ḡεf is (2/σ 2)-smooth.
Proof of Theorem 2. Recall that ḡεf (x)j = Eε∼N (0,σ2Id)f(x+ ε)j , where f(x+ ε)j is a function from Rd to {0, 1}. Therefore, to prove that gεM is (2/σ2)-smooth, we only need to show that for any function f : Rd → [0, 1], the function f̄ := f ∗ N (0, σ2Id) is (2/σ2)-smooth. According to (Salman et al., 2019, Lemma 1), we have
f̄(x) = 1
(2πσ2)d/2 ∫ Rd f(t) exp ( −‖x− t‖ 2 2 2σ2 ) dt, (33)
∇f̄(x) = 1 (2πσ2)d/2σ2 ∫ Rd f(t)(x− t) exp ( −‖x− t‖ 2 2 2σ2 ) dt. (34)
To show f̄ is (2/σ2)-smooth, we only need to show that ∇f̄ is (2/σ2)-Lipschitz. LetHf̄ (x) be the Hessian matrix of f̄ . Thus, we only need to show that for any unit vector u, |uTHf̄ (x)u| ≤ 2/σ2. By the isotropy of Hf̄ (x), it is sufficient to consider u = (1, 0, 0, . . . , 0)
T, where uTHf̄ (x)u = Hf̄ (x)11. Now we only need to bound the absolute value ofHf̄ (x)11:
|Hf̄ (x)11| = ∣∣∣ 1 (2πσ2)d/2σ2 ∫ Rd f(t) · ∂ ∂x1 (x− t) exp ( −‖x− t‖ 2 2 2σ2 ) dt ∣∣∣
= 1
(2πσ2)d/2σ2 ∣∣∣ ∫ Rd f(t) · ( 1− (x1 − t1) 2 σ2 ) exp ( −‖x− t‖ 2 2 2σ2 ) dt ∣∣∣
≤ 1 (2πσ2)d/2σ2 ∣∣∣ ∫ Rd exp ( −‖x− t‖ 2 2 2σ2 ) dt ∣∣∣
+ 1
(2πσ2)d/2σ2 ∣∣∣ ∫ Rd (x1 − t1)2 σ2 exp ( −‖x− t‖ 2 2 2σ2 ) dt ∣∣∣
= 1
σ2 + 1√ 2πσ2σ2
· 2 ∫ ∞
0
x2 σ2 exp
( − x 2
2σ2
) dx
= 1
σ2 +
√ 2
π · 1 σ2 ∫ ∞ 0 t2 exp(−t2/2)dt. (35)
Let Γ(·) be the Gamma function, we note that∫ ∞ 0 t2 exp(−t2/2)dt = ∫ ∞ 0 t exp(−t2/2)d(−t2/2) = √ 2 ∫ ∞ 0 √ t exp(−t)dt = √ 2Γ(3/2) = √ π/2,
and thus
|Hf̄ (x)11| ≤ 1
σ2 +
√ 2 π · 1 σ2 · √ π 2 = 2 σ2 , (36)
which concludes the proof.
Remark. The model-smoothness upper bound Theorem 2 is not limited to the ensemble model with Ensemble-before-Smoothing strategy. Indeed, for arbitrary classification models, since the confidence score is in range [0, 1], the theorem still holds. If the confidence score is bounded in [a, b], simple scaling yields the model-smoothness upper bound β = 2(b−a)σ2 . Proposition B.4 (Model-Smoothness Lower Bound for ḡεf ). There exists a smoothed confidence
function ḡεf that is β-smooth if and only if β ≥ (
1√ 2πeσ2
) .
Proof of Proposition B.4. We prove by construction. Consider the single dimensional input space R, and a model f that has confidence 1 if and only if input x ≥ 0. As a result,
gεf (x)y0 = 1√ 2πσ ∫ +∞ 0 exp ( − (t− x) 2 2σ2 ) dt = 1√ 2πσ ∫ +∞ −x exp ( − t 2 2σ2 ) dt.
Thus,
dgεf (x)y0 dx = 1√ 2πσ exp
( − x 2
2σ2
) and ∣∣∣dgεf (x)2y0 d2x ∣∣∣ = 1√ 2πσ2 · ∣∣∣x σ ∣∣∣ exp(− x2 2σ2 ) .
By symmetry, we study the function h(x) = x exp(−x2/2) for x ≥ 0. We have h′(x) = (1 − x) exp(−x2/2). Thus, h(x) obtains its maximum at x0 = 1: h(x0) = exp(−1/2), which implies that
max ∣∣∣dgεf (x)2y0
d2x ∣∣∣ = exp(−1/2)√ 2πσ2 = 1√ 2πeσ2
which implies β ≥ 1√ 2πeσ2 for this ḡεf per smoothness definition (Definition 4).

heading: B.5 PROOFS OF ROBUSTNESS CONDITIONS FOR SMOOTHED ENSEMBLE MODELS
text: Corollary 2 (Gradient and Confidence Margin Conditions for Smoothed WE Robustness). Given input x0 ∈ Rd with ground-truth label y0 ∈ [C]. Let ε ∼ N (0, σ2Id) be a Gaussian random variable. Define soft smoothed confidence ḡεi (x) := Eεfi(x+ ε) for each base model Fi (1 ≤ i ≤ N ). The ḠεMWE is a WE defined over soft smoothed base models {ḡ ε i }Ni=1 with weights {wi}Ni=1. ḠεMWE(x0) = y0.
• (Sufficient Condition) The ḠεMWE is r-robust at point x0 if for any yi 6= y0,∥∥∥ N∑ j=1 wj∇x(ḡεj )y0/yi(x0) ∥∥∥ 2 ≤ 1 r N∑ j=1 wj(ḡ ε j ) y0/yi(x0)− 2r σ2 N∑ j=1 wj , (21)
• (Necessary Condition) If ḠεMWE is r-robust at point x0, for any yi 6= y0,∥∥∥ N∑ j=1 wj∇x(ḡεj )y0/yi(x0) ∥∥∥ 2 ≤ 1 r N∑ j=1 wj(ḡ ε j ) y0/yi(x0) + 2r σ2 N∑ j=1 wj . (22)
Proof of Corollary 2. Since ḠεMWE is a WE defined over {ḡ ε i }Ni=1, we apply Theorem 1 directly for ḠεMWE . Notice that each ḡ ε i has model-smoothness bound β = 2/σ
2 from Theorem 2 and the corollary statement follows.
Corollary 3 (Gradient and Confidence Margin Condition for Smoothed MME Robustness). Given input x0 ∈ Rd with ground-truth label y0 ∈ [C]. Let ε ∼ N (0, σ2Id) be a Gaussian random variable. Define soft smoothed confidence ḡεi (x) := Eεfi(x + ε) for either base model F1 or F2. The ḠεMMME is a MME defined over soft smoothed base models {ḡ ε 1, ḡ ε 2}. ḠεMMME(x0) = y0.
• (Sufficient Condition) If for any y1, y2 ∈ [C] such that y1 6= y0 and y2 6= y0,
‖∇x(ḡε1)y0/y1(x0) +∇x(ḡε2)y0/y2(x0)‖2 ≤ 1
r ((ḡε1) y0/y1(x0) + (ḡ ε 2) y0/y2(x0))−
4r σ2 ,
(23) then ḠεMMME is r-robust at point x0.
• (Necessary Condition) Suppose for any x ∈ {x0 + δ : ||δ||2 ≤ r}, for any i ∈ {1, 2}, either GFi(x) = y0 or G (2) Fi
(x) = y0. If ḠεMMME is r-robust at point x0, then for any y1, y2 ∈ [C] such that y1 6= y0 and y2 6= y0,
‖∇x(ḡε1)y0/y1(x0) +∇x(ḡε2)y0/y2(x0)‖2 ≤ 1
r ((ḡε1) y0/y1(x0) + (ḡ ε 2) y0/y2(x0)) +
4r σ2 .
(24)
Proof of Corollary 3. Since ḠεMMME is constructed over confidences ḡ ε 1 and ḡ ε 2, we can directly apply Theorem 1. Again, with the model-smoothness bound β = 2/σ2 we can easily derive the corollary statement.

heading: C ANALYSIS OF ENSEMBLE SMOOTHING STRATEGIES
text: In main text we mainly use the adapted randomized model smoothing strategy which is named Ensemble-before-Smoothing (EBS). We also consider Ensemble-after-Smoothing (Ensemble-afterSmoothing). Through the following analysis, we will show Ensemble-before-Smoothing generally provides higher certified robust radius than Ensemble-after-Smoothing which justifies our choice of the strategy.
The Ensemble-before-Smoothing strategy is defined in Definition 5. The Ensemble-after-Smoothing strategy is defined as such. Definition 6 (Ensemble-after-Smoothing (EAS)). LetM be an ensemble model over base models {Fi}Ni=1. Let ε be a random variable. The EAS ensemble HεM : Rd 7→ [C] at input x0 ∈ Rd is defined as:
HεM(x0) := G ε Fc(x0) where c = arg max i∈[N ] gεFi(x0)GεFi (x0) . (37)
Here, c is the index of the smoothed base model selected. Remark. In EBS, we first construct a model ensembleM 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 ofM when the input follows distribution x0 + ε. In EAS, we use ε to construct smoothed classifiers for base models respectively. Then, for given input x0, the ensemble agrees on the base model which has the highest probability for its predicted class.

heading: C.1 CERTIFIED ROBUSTNESS
text: In this subsection, we characterize the certified robustness when using both strategies.
C.1.1 Ensemble-before-Smoothing
The following theorem gives an explicit method (first compute gεM(x0)GεM(x0) via sampling then compute r) to compute the certified robust radius r 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 Ensemble-before-Smoothing). Let GεM be an ensemble constructed by EBS strategy. The random variable ε ∼ N (0, σ2Id). Then the ensemble GεM is r-robust at point x0 where
r := σΦ−1 ( gεM(x0)GεM(x0) ) . (38)
Here, gεM(x0)j = Pr (M(x0 + ε) = j).
The proposition is a direct application of Lemma A.1.
C.1.2 Ensemble-after-Smoothing
The following theorem gives an explicit method to compute the certified robust radius r for EAS protocol. Theorem 5 (Certified robustness for Ensemble-after-Smoothing). Let HεM be an ensemble constructed by EAS strategy over base models {Fi}Ni=1. The random variable ∼ N (0, σ2Id). Let y0 = H ε M(x0). For each i ∈ [N ], define
ri :=  σΦ−1 ( gεFi(x0)GεFi (x0) ) , if GεFi(x0) = y0
−σΦ−1 ( gεFi(x0)GεFi (x0) ) . if GεFi(x0) 6= y0
Then the ensemble HεM is r-robust at point x0 where
r := maxi∈[N ] ri + mini∈[N ] ri
2 . (39)
Remark. The theorem appears to be a 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., ri’s are different), the r, certified robust radius for the ensemble, is strictly inferior to that of the best base model (i.e., max ri). Furthermore, if there exists a base model with wrong prediction (i.e., ri ≤ 0), the certified robust radius r is strictly smaller than half of the best base model.
Proof of Theorem 5. Without loss of generality, we assume r1 > r2 > · · · > rN . Let the perturbation added to x0 has L2 length δ.
When δ ≤ rN , since picking any model always gives the right prediction, the ensemble is robust. When rN < δ ≤ r1+rN2 , the highest robust radius with wrong prediction is δ − rN , and we can still guarantee that model F1 has robust radius at least r1 − δ from the smoothness of function x 7→ gεF1(x)GεF1 (x0) (Salman et al., 2019). Since r1− δ ≥ r1−rN 2 ≥ δ− rN , the ensemble will agree on F1 or other base model with correct prediction and still gives the right prediction.
When δ > r1+rN2 , suppose fN is a linear model and only predicts two labels (which achieves the tight robust radius bound according to Cohen et al. (2019)), then fN can have robust radius δ−rN for the wrong prediction. At the same time, for any other model Fi which is linear and predicts correctly, the robust radius is at most ri − δ. Since ri − δ < r1 − δ < r1−rN2 < δ − rN , 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 δ > r, there exist base models which lead the ensemble HεM(x0 + δe) to predict the label other than y0.

heading: C.2 COMPARISON OF TWO STRATEGIES
text: In this subsection, we compare the two ensemble strategies when the ensembles are constructed from two base models. Corollary 4 (Smoothing Strategy Comparison). GivenMMME, a Max-Margin Ensemble constructed from base models {fa, fb}. Let ε ∼ N (0, σ2Id). Let GεMMME be the EBS ensemble, and H ε MMME be the EAS ensemble. Suppose at point x0 with ground-truth label y0, GεFa(x0) = G ε Fb
(x0) = y0, gεFa(x0) > 0.5, g ε Fb (x0) > 0.5.
Let δ be their probability difference for class y0, i.e, δ := |gεFa(x0)y0 − g ε Fb (x0)y0 |,. Let pmin be the smaller probability for class y0 between them, i.e., pmin := min{gεFa(x0)y0 , g ε Fb
(x0)y0}. 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 ε
(MMME(x0 + ε) = y0 |Fa(x0 + ε) 6= Fb(x0 + ε) and (Fa(x0 + ε) = y0 orFb(x0 + ε) = y0)) ,
pab := Pr ε (Fa(x0 + ε) = Fb(x0 + ε) = y0) .
We have:
1. If p > 1/2 + (2 + 4(pmin − pab)/δ)−1, rG > rH .
2. If p ≤ 1/2, rH ≥ rG.
Here, rG is the certified robust radius of GεMMME computed from Equation (38); and rH is the certified robust radius of HεMMME computed from Equation (39).
Remark. Since p is the probability where the ensemble chooses the correct prediction between two base model predictions, with Max-Margin Ensemble, we think p > 1/2 with non-trivial margin.
The quantity pmin − pab 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 − pab)/δ)−1 ≈ 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. For convenience, define pa := gεFa(x0)y0 , pb := g ε Fb (x0)y0 , where pa = pb+δ and pmin = pb.
From Proposition C.1 and Theorem 5, we have
rG := σ
2 · 2Φ−1
( Pr (MMME(x0 + ) = y0) ) , rH := σ
2
( Φ−1(pa) + Φ −1(pb) ) .
Notice that Pr (MMME(x0 + ) = y0) = pab + p(pa + pb − 2pab), we can rewrite rG as
rG = σ
2 · 2Φ−1(pab + p(pa + pb − 2pab)).
1. When p > 1/2 + (2 + 4(pmin − pab)/δ)−1, since
p > 1
2 +
1
2 + 4(pmin−pab)δ =
1 2 +
δ 2δ + 4(pb − pab) = pa + pb + δ − 2pab 2(pa + pb − 2pab) = pa − pab pa + pb − 2pab ,
we have pab + p(pa + pb − 2pab) > pa. Therefore, rG > σΦ−1(pa). Whereas, rH ≤ σ/2 · 2Φ−1(pa) = σΦ −1(pa). So rG > rH .
2. When p ≤ 1/2,
pab + p(pa + pb − 2pab) ≤ pab + 1/2 · (pa + pb − 2pab) = (pa + pb)/2.
Therefore, rG ≤ σΦ−1((pa + pb)/2). Notice that Φ−1 is convex in [1/2,+∞), so Φ−1(pa) + Φ−1(pb) ≥ 2Φ−1((pa + pb)/2), i.e., rH ≥ rG.

heading: D ROBUSTNESS FOR SMOOTHED ML ENSEMBLE: STATISTICAL ROBUSTNESS PERSPECTIVE
text: In this appendix, we study the robustness of ensemble models from the statistical robustness perspective. This perspective is motivated from Lemma A.1, where the certified robust radius of a model smoothed with Gaussian distribution ε ∼ N (0, σ2Id) is directly proportional to the probability of the original (unsmoothed) model predicting the correct class under such noise.
We first define the notation of statistical robustness in Appendix D.1; 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 are also discussed; finally, we conduct extensive numerical experiments to verify all these findings in Appendix D.5.

heading: D.1 DEFINITIONS OF STATISTICAL ROBUSTNESS
text: Definition 7 ((ε, p)-Statistical Robust). Given a random variable ε and model F : Rd 7→ [C], at point x0 with ground truth label y0, we call F is (ε, p)-statistical robust if Prε(F (x0 +ε) = y0) ≥ p. Remark. Note that based on Lemma A.1, when ε ∼ N (0, σ2Id), if F is (ε, p)-statistical robust at point x0, the smoothed model GεF over F is (σΦ −1(p))-robust at point x0.
The following three definitions are used in the theorem statements in the following subsections. They can be viewed as the “confidence margins” under noised inputs x0 + ε for single model and ensemble respectively. Definition 8 ((ε, λ, p)-Single Confident). Given a classification model F . If at point x0 with groundtruth label y0 and the random variable ε, we have
Pr ε
( max
yj∈[C]:yj 6=y0 f(x0 + ε)yj ≤ λ(1− f(x0 + ε)y0)
) = 1− p,
we call F (ε, λ, p)-single confident at point x0. Definition 9 ((ε, λ, p)-WE Confident). LetMWE be a weighted ensemble defined over base models {Fi}Ni=1 with weights {wi}Ni=1. If at point x0 with ground-truth y0 and random variable ε, we have
Pr ε
( max
yj∈[C]:yj 6=y0 ( N∑ i=1 wifi(x0 + )yj ) ≤ λ N∑ i=1 wi (1− fi(x0 + )y0) ) = 1− p, (40)
we call weighted ensembleMWE (ε, λ, p)-WE confident at point x0. Definition 10 ((ε, λ, p)-MME Confident). LetMMME be a max-margin ensemble over {Fi}Ni=1. If at point x0 with ground-truth y0 and random variable ε, we have
Pr ε  ∧ i∈[N ] ( max yj∈[C]:yj 6=y0 fi(x0 + ε)yj ≤ λ(1− fi(x0 + ε)y0) ) = 1− p, (41) we call max-margin ensembleMMME (ε, λ, p)-MME confident at point x0.
Note that the confidence of every single model lies in the probability simplex, and λ reflects the confidence portion that a wrong prediction class can take beyond the true class (1− fi(x0 + ε)). To reduce ambiguity, we usualy use λ1 in WE Confident, λ2 in MME Confident, and λ3 in Single Confident. Note that given λ1 is the weighted average and λ2 the maximum over λ’s of all base models, under the same p, λ1/λ2 ≤ 1. Furthermore, under the same p, λ1/λ2 reflects the adversarial transferability (Papernot et al., 2016a) among base models: If the transferability is high, the confidence scores of base models are similar (λ’s are similar), and thus λ1 is large resulting in large λ1/λ2. On the other hand, when the transferability is low, the confidence scores are diverse (λ’s are diverse), and thus λ1 is small resulting in small λ1/λ2.
The following lemma is frequently used in our following proofs: Lemma D.1. Suppose the random variable X satisfies EX > 0, Var(X) <∞ and for any x ∈ R+, Pr(X ≥ EX + x) = Pr(X ≤ EX − x), then
Pr(X ≤ 0) ≤ Var(X) 2(EX)2 .
Proof of Lemma D.1. Apply Chebyshev’s inequality on 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.

heading: D.2 STATISTICAL CERTIFIED ROBUSTNESS GUARANTEES
text: The main results in this subsection are Theorem 6 and Theorem 7.

heading: D.2.1 CERTIFIED ROBUSTNESS FOR SINGLE MODEL
text: As the start point, we first show a direct proposition stating the certified robustness guarantee of the single model.
Proposition D.1 (Certified Robustness for Single Model). Let ε be a random variable. Let F be a classification model, which is (ε, λ3, p)-single confident. Let x0 ∈ Rd be the input with ground-truth y0 ∈ [C]. Suppose f(x0 + ε)y0 follows symmetric distribution with mean µ and variance s2, where µ > (1 + λ−13 ) −1. We have
Pr ε
(F (x0 + ε) = y0) ≥ 1− p− s2
2(µ− (1 + λ−13 )−1)2 .
Proof of Proposition D.1. We consider the distribution of quantity Y := f(x0 + ε)y0 − λ3(1 − f(x0 + ε)y0). Since the model F is (ε, λ3, p)-single confident, with probability 1 − p, Y ≤ f(x0 + ε)y0 −maxyj∈[C]:yj 6=y0 f(x0 + ε)yj . We note that since
EY = (1 + λ3)µ− λ3, Var(Y ) = (1 + λ3)2s2,
from Lemma D.1,
Pr(Y ≤ 0) ≤ s 2
2(µ− (1 + λ−13 )−1)2 .
Thus,
Pr(F (x0 + ε) = y0) = 1− Pr(F (x0 + ε) 6= y0) = 1− Pr ( f(x0 + ε)y0 − max
yj∈[C]:yj 6=y0 f(x0 + ε)yj < 0 ) ≥ 1− p− Pr(Y ≤ 0)
≥ 1− p− s 2
2(µ− (1 + λ−13 )−1)2 .

heading: D.2.2 CERTIFIED ROBUSTNESS FOR ENSEMBLES
text: Now we are ready to prove the certified robustness of the Weighted Ensemble and Max-Margin Ensemble (Theorems 6 and 7).
In the following text, we first define statistical margins for both WE and MME, and point out their connections to the notion of (ε, p)-Statistical 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 (X̂1; Statistical Margin for WEMWE). LetMWE be Weighted Ensemble defined over base models {Fi}Ni=1 with weights {wi}Ni=1. SupposeMWE is (ε, λ1, p)-WE-confident. We define random variable X̂1 which is depended by random variable ε:
X̂1( ) := (1 + λ1) N∑ j=1 wjfj(x0 + )y0 − λ1‖w‖1. (42)
Definition D.2 (X̂2; Statistical Margin for MMEMMME). LetMMME be Max-Margin Ensemble defined over base models {Fi}Ni=1. SupposeMMME is (ε, λ2, p)-MME-confident. We define random variable X̂2 which is depended by random variable ε:
X̂2( ) := (1 + λ2) ( max i∈[N ] fi(x0 + )y0 + min i∈[N ] fi(x0 + )y0 ) − 2λ2. (43)
We have the following observation:
Lemma D.2. For Weighted Ensemble,
Pr ε (MWE(x0 + ε) = y0) ≥ 1− p− Pr ε (X̂1(ε) < 0).

heading: For Max-Margin Ensemble,
text: Pr ε (MMME(x0 + ε) = y0) ≥ 1− p− Pr ε (X̂2(ε) < 0).
Proof of Lemma D.2. (1) For Weighted Ensemble, we define the random variable X1:
X1( ) := min yi∈[C]:yi 6=y0 N∑ j=1 wjf y0/yi j (x0 + ).
SinceMWE is (ε, λ1, p)-WE-confident, from Definition 9, with probability 1− p, we have
X1(ε) ≥ N∑ j=1 wj (fj(x0 + ε)y0 − λ2(1− fj(x0 + ε)y0))
= (1 + λ2) N∑ j=1 wjfj(x0 + ε)y0 − λ1‖w‖1 = X̂1(ε).
Therefore,
Pr ε (MWE(x0 + ε) = y0) = Pr ε (X1(ε) ≥ 0) ≥ 1− p− Pr ε (X̂2(ε) < 0).
(2) For Max-Margin Ensemble, we define the random variable X2:
X2( ) := max i∈[N ] min yi∈[C]:yi 6=y0
f y0/yi i (x0 + ) + min
i∈[N ] min yi∈[C]:yi 6=y0 f y0/yi i (x0 + ).
Similarly, sinceMMME is (ε, λ2, p)-MME-confident, from Definition 10, with probability 1− p, we have X2( ) ≥ max
i∈[N ] (fi(x0 + ε)y0 − λ2(1− fi(x0 + ε)y0)) + min i∈[N ] (fi(x0 + ε)y0 − λ2(1− fi(x0 + ε)y0))
= (1 + λ2) ( max i∈[N ] fi(x0 + )y0 + min i∈[N ] fi(x0 + )y0 ) − 2λ2 = X̂2(ε).
Moreover, from Lemma B.1, we know
Pr ε (M(x0 + ε) = y0) ≥ Pr ε (X2(ε) ≥ 0) ≥ 1− p− Pr ε (X̂2(ε) < 0).
As the result, to quantify the statistical robustness of two types of ensembles, we can analyze the distribution of statistical margins X̂1 and X̂2.
Lemma D.3 (Expectation and variance of X̂1 and X̂2). Let X̂1 and X̂2 be defined by Definition D.1 and Definition D.2 respectively. Assume {fi(x0+ε)y0}Ni=1 are i.i.d. and follow symmetric distribution with mean µ and variance s2. Define s2f = Var(mini∈[N ] fi(x0 + ε)y0). We have
E X̂1(ε) =(1 + λ1)‖w‖1µ− λ1‖w‖1, Var X̂1(ε) = (1 + λ1)2s2‖w‖22, E X̂2(ε) =2(1 + λ2)µ− 2λ2, Var X̂2(ε) ≤ 4(1 + λ2)2s2f .

heading: Proof of Lemma D.3.
text: EX̂1(ε) = (1 + λ1) N∑ j=1 Ewjfj(x0 + )y0 − λ1‖w‖1 = (1 + λ1)‖w‖1µ− λ1‖w‖1;
VarX̂1(ε) = (1 + λ1) 2 N∑ j=1 w2jVar(fj(x0 + )y0) = (1 + λ1) 2s2‖w‖22.
According to the symmetric distribution property of {fi(x0 + ε)y0}Ni=1, we have E X̂2(ε) = E(1 + λ2) (
max i∈[N ] fi(x0 + )y0 + min i∈[N ] fi(x0 + )y0
) − 2λ2
= 2(1 + λ2)µ− 2λ2.
Also, due the symmetry, we have
Var ( min i∈[N ] fi(x0 + ε)y0 ) = Var ( max i∈[N ] fi(x0 + ε)y0 ) = s2f .
As a result, Var X̂2(ε) ≤ (1 + λ2)2 · 4s2f .
From Lemma D.3, now with Lemma D.1, we are ready to derive the statistical robustness lower bound for WE and MME.
Theorem 6 (Certified Robustness for WE). Let ε be a random variable supported on Rd. LetMWE be a Weighted Ensemble defined over {Fi}Ni=1 with weights {wi}Ni=1. TheMWE is (ε, λ1, p)-WE confident. Let x0 ∈ Rd be the input with ground-truth label y0 ∈ [C]. Assume {fi(x0 + ε)y0}Ni=1, the confidence scores across base models for label y0, are i.i.d. and follow symmetric distribution with mean µ and variance s2, where µ > (1 + λ−11 ) −1. We have
Pr ε (MWE(x0 + ε) = y0) ≥ 1− p− ‖w‖22 ‖w‖21 · s 2 2 ( µ− ( 1 + λ−11 )−1)2 . (44) Theorem 7 (Certified Robustness for MME). Let ε be a random variable. LetMMME be a MaxMargin Ensemble defined over {Fi}Ni=1. TheMMME is (ε, λ2, p)-MME confident. Let x0 ∈ Rd be the input with ground-truth label y0 ∈ [C]. Assume {fi(x0 + ε)y0}Ni=1, the confidence scores across base models for label y0, are i.i.d. and follow symmetric distribution with mean µ where µ > (1 + λ−12 ) −1. Define s2f = Var(mini∈[N ] fi(x0 + ε)y0). We have
Pr ε
(MMME(x0 + ε) = y0) ≥ 1− p− s2f 2 ( µ− ( 1 + λ−12 )−1)2 . (45) Proof of Theorems 6 and 7. Combining Lemmas D.1 to D.3, we get the theorem.
Remark. Theorems 6 and 7 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̂1 is the weighted sum of several independent variables, we can further apply McDiarmid’s Inequality to get another bound
Pr ε
(MWE(x0 + ε) = y0) ≥ 1− p− exp ( −2‖w‖ 2 1
‖w‖22
( µ− ( 1 + λ−11 )−1)2) ,
which is tighter than Equation (44) when ‖w‖21/‖w‖22 is large. For average weighted ensemble, ‖w‖21/‖w‖22 = N . Thus, when N is large, this bound is tighter. Both theorems are applicable under the i.i.d. assumption of confidence scores. The another assumption µ > max{(1 + λ−11 )−1, (1 + λ −1 2 ) −1} insures that both ensembles have higher probability of predicting the true class rather than other classes, i.e., the ensembles have non-trivial clean accuracy.

heading: D.3 COMPARISON OF CERTIFIED ROBUSTNESS
text: We first show and prove an important lemma. Then, based on the lemma and Theorems 6 and 7, we derive the comparison corollary.
Lemma D.4. For µ, λ1, λ2, C > 0, when max{λ1/(1 + λ1), λ2/(1 + λ2)} < µ ≤ 1, and C < 1, we have
µ− (λ−12 + 1)−1
µ− (λ−11 + 1)−1 < C ⇐⇒ λ1 λ2 < λ−12
(( C−1 ( µ− λ2
1 + λ2
) + 1− µ )−1 − 1 ) . (46)

heading: Proof of Lemma D.4.
text: µ− (λ−12 + 1)−1 µ− (λ−11 + 1)−1 < C
⇐⇒ 1 λ−12 + 1 − C λ−11 + 1 > µ(1− C)
⇐⇒ λ1/λ2 λ−12 + λ1/λ2
< C−1
λ−12 + 1 − µ(C−1 − 1)
⇐⇒ λ1 λ2
( 1− µ+ C−1 ( µ− 1
λ−12 + 1
)) < λ−12 ( C−1 ( 1
λ−12 + 1 − µ
) + µ )
⇐⇒ λ1 λ2 < λ−12
C−1 (
1 λ−12 +1
− µ ) + µ
C−1 ( µ− 1
λ−12 +1
) + 1− µ
⇐⇒ λ1 λ2 < λ−12
(( C−1 ( µ− λ2
1 + λ2
) + 1− µ )−1 − 1 ) .
Now we can show and prove the comparison corollary.
Corollary 5 (Comparison of Certified Robustness). Let ε be a random variable supported on Rd. Over base models {Fi}Ni=1, letMMME be Max-Margin Ensemble, andMWE the Weighted Ensemble with weights {wi}Ni=1. Let x0 ∈ Rd be the input with ground-truth label y0 ∈ [C]. Assume {fi(x0 + ε)y0}Ni=1, the confidence scores across base models for label y0, are i.i.d, and follow symmetric distribution with mean µ and variance s2, where µ > max{(1 + λ−11 )−1, (1 + λ −1 2 ) −1}. Define s2f = Var(mini∈[N ] fi(x0 + ε)y0) and assume sf < s.
• When
λ1 λ2 < λ−12
(( s
sf
( µ− ( 1 + λ−12 )−1) + 1− µ )−1 − 1 ) , (47)
for any weights {wi}Ni=1,MWE has higher certified robustness thanMMME.
• When
λ1 λ2 > λ−12 ( s√ Nsf ( µ− ( 1 + λ−12 )−1) + 1− µ )−1 − 1  , (48) for any weights {wi}Ni=1,MMME has higher certified robustness thanMWE.
Here, the certified robustness is given by Theorems 6 and 7.
Proof of Corollary 5. (1) According to Lemma D.4, we have
λ1 λ2 < λ−12
(( s
sf
( µ− ( 1 + λ−12 )−1) + 1− µ )−1 − 1 )
=⇒µ− (λ −1 2 + 1) −1
µ− (λ−11 + 1)−1 < sf s
=⇒ √ ‖w‖22 ‖w‖21 µ− (λ−12 + 1)−1 µ− (λ−11 + 1)−1 < sf s
=⇒‖w‖ 2 2 ‖w‖21 · s 2 2 ( µ− ( 1 + λ−11 )−1)2 < s2f 2 ( µ− ( 1 + λ−12 )−1)2 . According to Theorems 6 and 7, we know the RHS in Equation (44) is larger than the RHS in Equation (45), i.e.,MWE has higher certified robustnesss thanMMME. (2) According to Lemma D.4, we have
λ1 λ2 > λ−12 ( s√ Nsf ( µ− ( 1 + λ−12 )−1) + 1− µ )−1 − 1  =⇒µ− (λ −1 2 + 1) −1
µ− (λ−11 + 1)−1 >
√ Nsf s
=⇒ √ ‖w‖22 ‖w‖21 µ− (λ−12 + 1)−1 µ− (λ−11 + 1)−1 > sf s
=⇒‖w‖ 2 2 ‖w‖21 · s 2 2 ( µ− ( 1 + λ−11 )−1)2 > s2f 2 ( µ− ( 1 + λ−12 )−1)2 . According to Theorems 6 and 7, we know the RHS in Equation (45) is larger than the RHS in Equation (44), i.e.,MMME has higher certified robustnesss thanMWE.
Remark. (1) Given that λ1/λ2 reflects the adversarial transferability among base models Appendix D.1, 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 λ1/λ2 lies in between RHS of Equation (47) and RHS of Equation (48), it is undetermined which ensemble protocol has higher robustness. Indeed, this uncertainty is caused by the adjustable weights {wi}Ni=1 of the Weighted Ensemble. If we only consider the average ensemble, then this gap is closed:
λ1 λ2 MMME more robust ≷ MWE more robust λ−12 ( s√ Nsf ( µ− ( 1 + λ−12 )−1) + 1− µ )−1 − 1  . (3) Note that we assume that sf < s, where s2 is the variance of single variable and s2f is the variance of minimum of N i.i.d. variables. For common symmetry distributions, along with the increase of N , sf shrinks in the order of O(1/NB) where B ∈ (0, 2]. Thus, as long as N is large, the assumption sf < s will always hold. An exception is that when these random variables follow the exponential distribution, where sf does not shrink along with the increase of N . However, since these random variables are confidence scores which are in [0, 1], they cannot obey exponential distribution.

heading: D.4 A CONCRETE CASE: UNIFORM DISTRIBUTION
text: As shown by Saremi & Srivastava (2020) (Remark 2.1), when the input dimension d is large, the Gaussian noise ε ∼ N (0, σ2Id) ≈ Unif(σ √ dSd−1), i.e., x0 + ε is highly uniformly distributed on
the (d− 1)-sphere centered at x0. Motivated by this, we study the case where the confidence scores {fi(x0 + ε)y0}Ni=1 are also uniformly distributed. Under this additional assumption, we can further make the certified robustness for the single model and both ensembles more concrete.

heading: D.4.1 CERTIFIED ROBUSTNESS FOR SINGLE MODEL
text: 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 is (ε, λ3, p)-single confident. Let x0 ∈ Rd be the input with ground-truth y0 ∈ [C]. Suppose f(x0 + ε)y0 is uniformly distributed in [a, b]. We have
Pr ε
(F (x0 + ε) = y0) ≥ 1− p− clip (
1/(1 + λ−13 )− a b− a
) ,
where clip(x) = max(min(x, 1), 0).
Proof of Proposition D.2. We consider the distribution of quantity Y := f(x0 + ε)y0 − λ3(1 − f(x0 + ε)y0). Since the model F is (ε, λ3, p)-single confident, with probability 1 − p, Y ≤ f(x0 + ε)y0 −maxyj∈[C]:yj 6=y0 f(x0 + ε)yj . At the same time, because f(x0 + )y0 follows the distribution U([a, b]),
Y = (1 + λ3)f(x0 + ε)y0 − λ3 follows the distribution U([(1 + λ3)a− λ3, (1 + λ3)b− λ3]). Therefore,
Pr(Y ≤ 0) = clip ( λ3 − (1 + λ3)a (1 + λ3)(b− a) ) .
As the result,
Pr ( f(x0 + ε)y0 − max
yj∈[C]:yj 6=y0 f(x0 + ε)yj ≤ 0
) ≤ p+ clip ( λ3 − (1 + λ3)a (1 + λ3)(b− a) ) ,
which is exactly Pr (F (x0 + ε) = y0) ≥ 1− p− clip ( λ3 − (1 + λ3)a (1 + λ3)(b− a) ) = 1− p− clip ( 1/(1 + λ−13 )− a b− a ) .

heading: D.4.2 CERTIFIED ROBUSTNESS FOR ENSEMBLES
text: Still, we define X̂1(ε) and X̂2(ε) according to Definitions D.1 and D.2. Under the uniform distribution assumption, we have the following lemma.
Lemma D.5 (Expectation and Variance of X̂1 and X̂2 under Uniform Distribution). Let X̂1 and X̂2 be defined by Definition D.1 and Definition D.2 respectively. Assume that under the distribution of ε, the base models’ confidence scores for true class {fi(x0 + ε)y0}Ni=1 are pairwise i.i.d and uniformly distributed in range [a, b]. We have
E X̂1(ε) = 1
2 (1 + λ1)‖w‖1(a+ b)− λ1‖w‖1, Var X̂1(ε) =
1
12 (1 + λ1)
2‖w‖22(b− a)2,
E X̂2(ε) = (1 + λ2)(a+ b)− 2λ2, Var X̂2(ε) ≤ (1 + λ2)2 4
N + 1
( 2
N + 2 − 1 N + 1
) (b− a)2.
Proof of Lemma D.5. We start from analyzing X̂1. From the definition
X̂1( ) := (1 + λ1) N∑ j=1 wjfj(x0 + )y0 − λ1‖w‖1 (42)
where {fi(x0 + )y0}Ni=1 are i.i.d. variables obeying uniform distribution U([a, b]),
E X̂1( ) = (1 + λ1)‖w‖1 a+ b
2 − λ1‖w‖1 =
1 2 (1 + λ1)‖w‖1(a+ b)− λ1‖w‖1,
Var X̂1( ) = (1 + λ1) 2 N∑ j=1 w2j 1 12 (b− a)2 = 1 12 (1 + λ1) 2‖w‖22(b− a)2.
Now analyze the expectation of X̂2. By the symmetry of uniform distribution, we know
E X̂2( ) = (1 + λ2) · 2E fi(x0 + )y0 − 2λ2 = (1 + λ2)(a+ b)− 2λ2.
To reason about the variance, we need the following fact:
Fact D.1. Let x1, x2, . . . , xn be uniformly distributed and independent random variables. Specifically, for each 1 ≤ i ≤ n, xi ∼ U([a, b]). Then we have
Var ( min
1≤i≤n xi
) = Var ( max
1≤i≤n xi
) = 1
n+ 1
( 2
n+ 2 − 1 n+ 1
) (b− a)2.
Observing that each i.i.d. fi(x0 + ε)y0 is exactly identical to xi in Fact D.1, we have
Var ( max i∈[N ] fi(x0 + )y0 + min i∈[N ] fi(x0 + )y0 ) ≤ 4 N + 1 ( 2 N + 2 − 1 N + 1 ) (b− a)2.
Therefore,
Var X̂2(ε) ≤ (1 + λ2)2 4
N + 1
( 2
N + 2 − 1 N + 1
) (b− a)2.
Proof of Fact D.1. From symmetry of uniform distribution, we know Var (min1≤i≤n xi) = Var (max1≤i≤n xi). So here we only consider Y := min1≤i≤n xi. Its CDF F and PDF f can be easily computed:
F (y) = 1−Pr (
min i
xi ≥ y ) = 1− ( b− y b− a )n , f(y) = F ′(y) = n (b− y)n−1 (b− a)n , where y ∈ [a, b].
Hence,
EY = ∫ b a yf(y)dy = y(b− y)n + (n+ 1)−1(b− y)n+1 (b− a)n ∣∣∣a b = a+ b− a n+ 1 ,
EY 2 = ∫ b a y2f(y)dy = ∫ b a ny2 (b− y)n−1 (b− a)n dy
= − ( b− y b− a )n y2 ∣∣∣b a + 2 ∫ b a ( b− y b− a )n ydy
= − ( b− y b− a )n y2 ∣∣∣b a + 2 n+ 1 ( − (b− y) n+1 (b− a)n y + ∫ (b− y)n+1 (b− a)n dy ) ∣∣∣b a
= − ( b− y b− a )n y2 ∣∣∣b a + 2 n+ 1 ( − (b− y) n+1 (b− a)n y − 1 n+ 2 (b− y)n+2 (b− a)n ) ∣∣∣b a
= a2 + 2 n+ 1 (b− a)a+ 2 (n+ 1)(n+ 2) (b− a)2.
As the result, VarY = EY 2 − (EY )2 = 1n+1 ( 2 n+2 − 1 n+1 ) (b− a)2.
Now, similarly, we use Lemma D.1 to derive the statistical robustness lower bound for WE and MME. We omit the proofs since they are direct applications of Lemma D.5, Lemma D.1, and Lemma D.2.
Theorem 8 (Certified Robustness for WE under Uniform Distribution). LetMWE be a Weighted Ensemble defined over {Fi}Ni=1 with weights {wi}Ni=1. Let x0 ∈ Rd be the input with ground-truth label y0 ∈ [C]. Let ε be a random variable supported on Rd. Under the distribution of ε, suppose {fi(x0 +ε)y0}Ni=1 are i.i.d. and uniformly distributed in [a, b]. TheMWE is (ε, λ1, p)-WE confident. Assume a+b2 >
1 1+λ−11 . We have
Pr ε
(MWE(x0 + ε) = y0) ≥ 1− p− dwK
2 1
12 ,
where dw = ‖w‖22 ‖w‖21 , K1 = b− a a+b 2 −
1 1+λ−11
. (49)
Theorem 9 (Certified Robustness for MME under Uniform Distribution). LetMMME be a MaxMargin Ensemble over {Fi}Ni=1. Let x0 ∈ Rd be the input with ground-truth label y0 ∈ [C]. Let ε be a random variable supported on Rd. Under the distribution of ε, suppose {fi(x0 + ε)y0}Ni=1 are i.i.d. and uniformly distributed in [a, b].MMME is (ε, λ2, p)-MME confident. Assume a+b2 >
1 1+λ−12 . We have
Pr ε
(MMME(x0 + ε) = y0) ≥ 1− p− cNK
2 2
4 ,
where cN = 2
N + 1
( 2
N + 2 − 1 N + 1
) , K2 = b− a a+b
2 − 1
1+λ−12
. (50)

heading: D.4.3 COMPARISON OF CERTIFIED ROBUSTNESS FOR ENSEMBLES
text: Now under the uniform distribution, we can also have the certified robustness comparison. Corollary 6 (Comparison of Certified Robustness under Uniform Distribution). Over base models {Fi}Ni=1, letMMME be Max-Margin Ensemble, andMWE the Weighted Ensemble with weights {wi}Ni=1. Let x0 ∈ Rd be the input with ground-truth label y0 ∈ [C]. Let ε be a random variable supported on Rd. Under the distribution of ε, suppose {fi(x0 + ε)y0}Ni=1 are i.i.d. and uniformly distributed with mean µ. SupposeMWE is (ε, λ1, p)-WE confident, andMMME is (ε, λ2, p)-MME confident. Assume µ > max { 1
1+λ−11 , 1 1+λ−12
} .
• When λ1 λ2 < λ−12 ((N + 1)√N + 2 6N ( µ− 1 1 + λ−12 ) + 1− µ )−1 − 1  , (51) MWE has higher certified robustness thanMMME.
• When λ1 λ2 > λ−12 (N + 1 N √ N + 2 6 ( µ− 1 1 + λ−12 ) + 1− µ )−1 − 1  , (52) MMME has higher certified robustness thanMWE.
• When
N > 6 ( 1− 1
µ(1 + λ−12 )
)−2 − 2, (53)
for any λ1,MMME has higher or equal certified robustness thanMWE.
Here, the certified robustness is given by Theorems 8 and 9.
Proof of Corollary 6. First, we notice that a uniform distribution with mean µ can be any distribution U([a, b]) where (a+ b)/2 = µ. We replace µ by (a+ b)/2. Then (1) and (2) follow from Lemma D.4 similar to the proof of Corollary 5.
(3) Since
N > 6 ( 1− 1
µ(1 + λ−12 )
)−2 − 2 =⇒ (√ N + 2
6
( µ− 1
1 + λ−12
) + 1− µ )−1 < 1
=⇒
( N + 1
N
√ N + 2
6
( µ− 1
1 + λ−12
) + 1− µ )−1 < 1,
the RHS of Equation (52) is smaller than 0. Thus, for any λ1, since λ1/λ2 > 0, the Equation (48) is satisfied. According to (2),MMME has higher certified robustnesss thanMWE.
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-Margin Ensemble than Weighted Ensemble. This is due to the more efficient variance reduction of Max-Margin Ensemble than Weighted Ensemble. As shown in Lemma D.5, the quantity VarX̂(ε)/(EX̂(ε))2 for Weighted Ensemble is Ω(1/N), while for Max-Margin Ensemble is O(1/N2). As the result, when N becomes larger, Max-Margin Ensemble has higher certified robustness.
We use uniform assumption here to give an illustration in a 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.

heading: D.5 NUMERICAL EXPERIMENTS
text: To validate and give more intuitive explanations for our theorems, we present some numerical experiments.

heading: D.5.1 ENSEMBLE COMPARISON FROM NUMERICAL SAMPLING
text: As discussed in Appendix D.1, λ1/λ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 λ1/λ2 (see the definitions of λ1 and λ2 in Definitions 9 and 10), and sampling the confidence scores {fi(x0 + ε)y0} and {maxj∈[C]:j 6=y0 fi(x0 + ε)j} under determined λ1 and λ2. For each level of λ1/λ2, with the samples, we compute the certified robust radius r using randomized smoothing (Lemma A.1) 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 λ1/λ2, Max-Margin Ensemble would gradually become more certifiably robust than Weighted Ensemble.
Figure 4 verifies the trends: with the increase of λ1/λ2, MME model tends to achieve higher certified radius than WE model. Moreover, we notice that under the same λ1/λ2, with the larger number of base models N , the MME tends to be relatively more certifiably robust compared with WE. This is because we sample the confidence score uniformly and under the uniform distribution, MME tends to be more certifiably robust than WE when the number of base models N becomes large, according to Corollary 6.
The concrete number settings of λ1, λ2, and the sampling interval of confidence scores are entailed in the caption of Figure 4.

heading: D.5.2 ENSEMBLE COMPARISON FROM CERTIFIED ROBUSTNESS PLOTTING
text: In Corollary 6, we derive the concrete certified robustness for both ensembles and the single model under i.i.d. and uniform distribution assumption. In fact, from the corollary, we can directly compute the certified robust radius without sampling, as long as we assume the added noise ε is Gaussian. In Figure 5, we plot out such certified robust radius for the single model, the WE, and the MME.
Concretely, in the figure, we assume that the true class confidence score for each base model is i.i.d. and uniformly distributed in [a, b]. The Weighted Ensemble is (ε, λ1, 0.01)-WE confident; the Max-Margin Ensemble is (ε, λ2, 0.01)-MME confident; and the single model is (ε, λ3, 0.01)-MME confident. We guarantee that λ1 ≤ λ3 ≤ λ2 to simulate the scenario that ensembles are based on the same set of base models to make a fair comparison. We directly apply the results from our analysis (Theorem 8, Theorem 9, Proposition D.2) to get the statistical robustness for single model and both ensembles. Then, we leverage Lemma A.1 to get the certified robust radius (with σ = 1.0, N = 100000 and failing probability α = 0.001 which are aligned with realistic setting). The x-axis 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 0 certified robustness mainly because our theoretical bounds for ensembles are not tight enough with the small N . Furthermore, we observe that the Max-Margin Ensemble gradually surpasses Weighted Ensemble when N is large, which conforms to our Corollary 6. Note that the left sub-figure has smaller transferability λ1/λ2 and the right subfigure has larger transferability λ1/λ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-Margin Ensemble.

heading: D.5.3 ENSEMBLE COMPARISON FROM REALISTIC DATA
text: We study the correlation between transferability λ1/λ2 and whether Weighted Ensemble or MaxMargin Ensemble is more certifiably robust using realistic data.
By varying the hyper-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 is more robust; for another half, MME is more robust. We collect 1, 000 test set samples in total. Then, for each test set sample, we compute the transferability λ1/λ2 and whether WE or MME has the higher certified robust radius. We remark that λ1 and λ2 are difficult to be practically estimated so we use the average confidence portion as the proxy:
• For WE,
λ1 = Eε maxyj∈[C]:yj 6=y0 ∑N i=1 wifi(x0 + ε)yj∑N
i=1 wi(1− fi(x0 + ε)y0) .
• For MME,
λ2 = Eε max i∈[N ] maxyj∈[C]:yj 6=y0 fi(x0 + ε)yj (1− fi(x0 + ε)y0) .
5 10 15 20 25 30 # of Base Models (N)
0.0
0.2
0.4
0.6
0.8
1.0
C er
tif ie
d R
ob us
tn es
s
Certified Robustness Comparison (a = 0.2, b = 0.3, 1 = 0.29, 2 = 0.31, 3 = 0.30)
WE MME Single Model
(a) [a, b] = [0.2, 0.3], λ1 = 0.29, λ2 = 0.31, λ3 = 0.30.
5 10 15 20 25 30 # of Base Models (N)
0.0
0.2
0.4
0.6
0.8
1.0
C er
tif ie
d R
ob us
tn es
s
Certified Robustness Comparison (a = 0.3, b = 0.4, 1 = 0.48, 2 = 0.50, 3 = 0.49)
WE MME Single Model
(b) [a, b] = [0.3, 0.4], λ1 = 0.48, λ2 = 0.50, λ3 = 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 is the certified robustness and the x-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 (ε, λ1, 0.01)-WE confident; the Max-Margin Ensemble (shown by green line) is (ε, λ2, 0.01)-MME confident; and the single model (shown by red line) is (ε, λ3, 0.01)-MME confident.
Figure 6: ROC curve of the I[MME has higher certified robustness] classification task with the threshold variable X .
Now we study the correlation between
X := λ1/λ2 − RHS of Equation (48) and Y := I[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 6. From the ROC curve, we find that X and Y are apparently positively correlated since AUC = 0.66 > 0.5, which again verifies Corollary 5. We remark that besides X , other factors such as non-symmetric or non-i.i.d. confidence score distribution may also play a 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 transferability is low; (2) If each fi(x0 + ε)y0 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.i.d. distribution of fi(x0 + ε)y0 or even more strict uniform distribution to 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
analysis can open an angle of theoretical analysis of ensembles and leave a more general analysis as the future work.

heading: E ANALYSIS OF ALTERNATIVE DESIGN OF DRT
text: In the main text, we design our DRT based on GD Loss
LGD(x0)ij = ∥∥∇xfy0/y(2)ii (x0) +∇xfy0/y(2)jj (x0)∥∥2 (9)
and CM Loss
LCM(x0)ij = f y (2) i /y0 i (x0) + f y (2) j /y0 j (x0). (10)
Following the convention, we apply Gaussian augmentation to train the models, i.e., replacing x0 by x0 + ε where ε ∼ N (0, σ2Id) in Equation (9) and Equation (10). We apply these two regularizers to every valid base model pair (Fi, Fj), where the valid pair means both base models predict the ground truth label y0: Fi(x0 + ε) = Fj(x0 + ε) = y0.
One may concern that in the worst case, there could be O(N2) valid pairs, i.e., O(N2) regularization terms in the training loss. However, we should notice that each base model Fi only appears in O(N) valid pairs. Therefore, when N is 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 1) is to use overall summation instead of pairwise summation, which directly correlates with Iyi (Equation (6)):
L′GD(x0) = ∥∥∥ N∑ i=1 ∇xf y0/y (2) i i (x0) ∥∥∥ 2 , (54)
L′CM(x0) = N∑ i=1 f y (2) i /y0 i (x0). (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 Fi to have the same runner-up prediction y (2) i as observed from both theorem and intuition (otherwise diversified gradients and confidence margins are for different and independent labels that are meaningless to jointly optimize). It is less likely to 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.

heading: F EXPERIMENT DETAILS
text: 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 et al., 2019): Adding the regularization term to maximize the certified radius R = σ2 (pA − pB) on training instances. (2) SmoothAdv (Salman et al., 2019) combines adversarial training with Gaussian augmentation. (3) MACER (Zhai et al., 2019) improves a single model’s certified robustness by adding regularization terms to minimize the Negative Log Likelihood (NLL) between smoothed classifier’s output gF (x) and label y, and maximize the certified radius R = σ2 (Φ
−1(gεF (x)y) − Φ−1(maxy′ 6=y gεF (x)y′)), where ε ∼ N (0, σ2Id) and gεF is as defined in Equation (3). (4) Stability (Li et al., 2019) maintains the stability of the smoothed classifier gF by minimizing the Rényi Divergence between gF (x) and gF (x + ε) where ε ∼ N (0, σ2Id). (5) SWEEN (Liu et al., 2020) builds smoothed Weighted Ensemble (WE), which is 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, we report the approximate certified
test accuracy (Cohen et al., 2019) sampled through the Monte Carlo procedure. For each sample, the robustness certification holds with probability at least 1− α. Following the literature, we choose α = 0.001, n0 = 100 for Monte Carlo sampling during prediction phase, and n = 105 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 we 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 et al., 2019).

heading: F.1 MNIST
text: 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 as Salman et al. (2019) show). We choose Gaussian smoothing variance σ ∈ {0.25, 0.5, 1.0} for training and evaluation for all methods. For SmoothAdv, we consider the attack to be 10-step L2 PGD attack with perturbation scale δ = 1.0 without pretraining and unlabelled data augmentation. We reproduced results similar to their paper by using their open-sourced code1.
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 α = 0.01. The learning rate is decayed for every 30 epochs with decay ratio γ = 0.1 and the batch size equals to 256. Then, we apply DRT to finetune our model with small learning rate α for another 90 epochs. We explore different DRT hyper-parameters ρ1, ρ2 together with the initial learning rate α, and report the best certified accuracy on each radius r among all the trained ensemble models.
Trend of Certified Accuracy with Perturbation Radius. We visualize the trend of certified accuracy along with different perturbation radii on different smoothing parameters separately in Figure 7 and Figure 8. 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 on different radii.
Average Certified Radius. We report the Average Certified Radius (ACR) (Zhai et al., 2019): ACR = 1|Stest| ∑ (x,y)∈Stest R(x, y), where Stest refers to the test set and R(x, y) the certifed radius on testing
1https://github.com/Hadisalman/smoothing-adversarial/
sample (x, y). We evaluate ACR of our DRT-trained ensemble trained with σ ∈ {0.25, 0.5, 1.0} smoothing parameter and compare it with other baselines. Results are shown in Table 7.
We can clearly see that our DRT-trained ensemble could still achieve the highest ACR on all the smoothing parameter settings. Especially on σ = 1.00, our improvement is significant.
Effects of ρ1 and ρ2. We investigate the DRT hyper-parameters ρ1 and ρ2 corresponding to different smoothing parameter σ ∈ {0.25, 0.5, 1.0}. Here we put the detailed results for various hyperparameter settings in Tables 4 to 6 and bold the numbers with the highest certified accuracy on each radius r. From the experiments, we find that the GD loss’s weight ρ1 can have the major influence on the ensemble model’s functionality: if we choose larger ρ1, 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 ρ1 on small σ cases (e.g., σ = 0.25). Otherwise, model’s functionality will collapse. Here we show DRT-based models’ certified accuracy by applying different ρ1 in Figure 9.
Alternatively, we find that the CM loss’s weight ρ2 can also have positive influence on model’s performance: the larger ρ2 we choose, the higher certified accuracy we could get. Choosing larger and larger ρ2 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 as our efficiency criterion. For MNIST with batch size equals to 256, DRT with the Gaussian smoothing base model only requires 1.04s to finish one mini-batch training to achieve the comparable results to 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 on single NVIDIA GeForce GTX 1080 Ti GPU.
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 as Salman et al. (2019) show). We choose Gaussian smoothing variance σ ∈ {0.25, 0.5, 1.0} for training and evaluation for all methods. For SmoothAdv, we consider the attack to be 10-step L2 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 ResNet-110 architecture and train each base model for 150 epochs. For the training optimizer, we use the SGD-momentum with the initial learning rate α = 0.1. The learning rate is decayed for every 50-epochs with decay ratio γ = 0.1. Then, we use DRT to finetune our model with small learning rate α for another 150 epochs. We also explore different DRT hyper-parameters ρ1, ρ2 together with the initial learning rate α, and report the best certified accuracy on each radius r among all the trained ensemble models.
Trend of Certified Accuracy with Perturbation Radius. We visualize the trend of certified accuracy along with different perturbation radii on different smoothing parameters separately in Figure 10 and Figure 11. For each radius r, we present the best certified accuracy among all the trained models. We can see the similar trends: Applying either MME or WE ensemble protocol will only give slight improvement while DRT can help make this improvement significant.
Average Certified Radius. We report the Average Certified Radius (ACR) (Zhai et al., 2019): ACR = 1|Stest| ∑ (x,y)∈Stest R(x, y), where Stest refers to the test set and R(x, y) the certifed radius on testing sample (x, y). We evaluate ACR of our DRT-trained ensemble trained with σ ∈ {0.25, 0.5, 1.0} smoothing parameter and compare it with other baselines. Results are shown in Table 11.
Results shows that, DRT-trained ensemble has the highest ACR on almost all the settings. Especially on σ = 1.00, our improvement is significant.
Effects of ρ1 and ρ2. We study the DRT hyper-parameter ρ1 and ρ2 corresponding to different smoothing parameters σ ∈ {0.25, 0.5, 1.0} and put the detailed results in Tables 8 to 10. We bold the
numbers with the highest certified accuracy on each radius r. The results show similar conclusion to our understanding from MNIST.
Efficiency Analysis. We also use the execution time per mini-batch as our efficiency criterion. For CIFAR-10 with batch size equals to 256, DRT with the Gaussian smoothing base model requires 3.82s to finish one mini-batch training to achieve the competitive results to 10-step PGD attack based SmoothAdv method which requires 6.39s. All the models are trained in parallel on 4 NVIDIA GeForce GTX 1080 Ti GPUs.
F.3 IMAGENET
For ImageNet, we utilize ResNet-50 architecture and train each base model for 90 epochs using SGD-momentum optimizer. The initial learning rate α is set to 0.1. During training, the learning rate is decayed for every 30-epochs with decay ratio γ = 0.1. We tried different Gaussian smoothing parameter σ ∈ {0.50, 1.00}, and consider the best hyper-parameter configuration for each σ. Then, we use DRT to finetune base models with the learning rate α = 5× 10−3 for another 90 epochs. Due
to the consideration of achieving high certified accuracy on large radii, we choose large DRT training hyper-parameter ρ1 and ρ2 in practice, which lead to relatively low benign accuracy.

heading: G ABLATION STUDIES

heading: G.1 THE EFFECTS OF GRADIENT DIVERSITY LOSS AND CONFIDENCE MARGIN LOSS
text: To explore the effects of individual Gradient Diversity and Confidence Margin Losses in DRT, we set ρ1 or ρ2 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 on improving the
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.

heading: G.2 CERTIFIED ROBUSTNESS OF SINGLE BASE MODEL WITHIN DRT-TRAINED ENSEMBLE
text: 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 DRTtrained ensemble are more robust compared to single base model within other baseline ensembles. Also, integrating them together could achieve higher robustness.

heading: G.3 OPTIMIZING THE WEIGHTS OF DRT-TRAINED ENSEMBLE
text: 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 17. (AE here refers to the average ensemble protocol and WE the weighted ensemble protocol by adapting the tuned optimal weights)
We can see 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 be a good choice in practice.

heading: G.4 COMPARISON WITH OTHER GRADIENT DIVERSITY REGULARIZERS
text: We notice that out of the certifiably robust ensemble field, there exist two 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}Ni=1 and input x and ground truth label y, the ADP regularizer is defined as
LADP(x, y) = α · N∑ i=1 H(mean({fi(x)})) + β · log(ED)
where H(·) refers to the Shannon Entropy Loss function and ED 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:
LGAL(x, y) = log  ∑ 1≤i<j≤N exp ( cos〈∇x`Fi ,∇x`Fj 〉 ) . Under the smoothed ensemble training setting, the final training loss is represented by
Ltrain(x, y) = ∑ i∈[N ] Lstd(x+ ε, y)i + {LADP(x+ ε, y) or LGAL(x+ ε, y)}
where we consider standard training loss Lstd(x0 + ε, y0)i of each base model Fi to be the standard cross-entropy loss.
Table 18 shows the certified accuracy of {ADP, GAL, DRT}-trained 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 on different datasets.

Review summaries:
Certified robustness approaches have been studied for single models based on interval propagation as well as randomized smoothing. The use of ensembles for empirical robustness has also been studied in the literature. This paper attempts to theoretically study the certifiable defense achieved by ensembles. The paper analyzes the standard Weighted Ensemble (WE) and MaxMargin Ensemble (MME) protocols, and proves the necessary and sufficient conditions for robustness under smoothness assumptions. The key idea is to show and utilize the diversification of gradients and large confidence margins. 

This paper studies the following problem: How to train a certifiably robust classifier with ensemble methods? The authors considered two types of ensembles: the weighted-average ensemble and large-margin ensemble. They first derived theoretically sufficient and necessary conditions for robustness under two types of ensembles, with the conclusion that large confidence margin and diversified gradients are two factors which contributes to the robustness of ensemble models. Diversity-regularized training, a method of designing loss functions for training ensemble models, is proposed motivated by their theoretical findings. They applied this methodology to randomized smoothing, performed extensive experiments and showed non-trivial improvement over single model methods.