On the Robustness of Randomized Ensembles to Adversarial Perturbations
Authors: Hassan Dbouk
Naresh Shanbhag
Venue: Submitted to ICLR 2023 (2023)
Keywords: adversarial robustness
efficient inference
randomized ensembles
boosting

Abstract: Randomized ensemble classifiers (RECs), where one classifier is randomly selected during inference, have emerged as an attractive alternative to traditional ensembling methods for realizing adversarially robust classifiers with limited compute requirements. However, recent works have shown that existing methods for constructing RECs are more vulnerable than initially claimed, casting major doubts on their efficacy and prompting fundamental questions such as: "When are RECs useful?", "What are their limits?", and "How do we train them?". In this work, we first demystify RECs as we derive fundamental results regarding their theoretical limits, necessary and sufficient conditions for them to be useful, and more. Leveraging this new understanding, we propose a new boosting
algorithm (BARRE) for training robust RECs, and empirically demonstrate its effectiveness at defending against strong $\ell_\infty$ norm-bounded adversaries across various network architectures and datasets. Our code is submitted as part of the supplementary material, and will be publicly released on GitHub

Under review as a conference paper at ICLR 2023
ON THE ROBUSTNESS OF RANDOMIZED ENSEMBLES TO ADVERSARIAL PERTURBATIONS
A Anonymous authors
Paper under double-blind review
ABSTRACT
Randomized ensemble classifiers (RECs), where one classifier is randomly se- lected during inference, have emerged as attractive alternative to traditional en- sembling methods for realizing adversarially robust classifiers with limited com- pute requirements. However, recent works have shown that existing methods for constructing RECs are more vulnerable than initially claimed, casting major doubts on their efficacy and gromplingfunddamennn fundamental questions such as: "When are RECs useful?" "What are their limits?", and "How do we train them?". In this work, we first demystify RECs as we derive fundamental results regarding their theoretical limits, necessary and sufficient conditions for them to be useful, and more. Leveraging this new understanding, we propose new boosting algorithm (BARRE) for training robust RECs, and empirically demonstrate its effectiveness at defending against strong Lo norm-bounded adversaries across various network architectures and datasets. Our code is submitted as part of the supplementary material, and will be publicly released on GütHub.
INTRODUCTION
Defending deep networks against adversarial perturbations (Szegedy et al., 2013; Biggio et al., 2013;
Goodfellow et al., 2014) remains a difficult task. Several proposed defenses (Papernot et al., 2016; Pang et al., 2019; Yang et al., 2019; Sen et al., 2019; Pinot et al., 2020) have been subsequently "broken" by stronger adversaries (Carlini & Wagner, 2017; Athalye et al., 2018; Tramèr et al., 2020; Dbouk & Shanbhag, 2022), whereas strong defenses (Cisse et al., 2017; Tramer et al., 2018; Cohen et al., 2019), such as adversarial training (AT) (Goodfellow et al., 2014; Zhang et al., 2019; Madry al., 2018), achieve unsatisfactory levels of robustness!
A popular belief in the adversarial community is that single model defenses, e.g., AT, lack the ca- pacity to defend against all possible perturbations, and that constructing ensemble of diverse, often smaller, models should be more cost-effective (Pang et al., 2019; Kariyappa & Qureshi, 2019; Pinot al., 2020; Yang et al., 2020b; 2021; Abernethy al., 2021; Zhang al., 2022). Indeed, recent deterministic robust ensemble methods, such as MRBoost (Zhang et al., 2022), have been successful at achieving higher robustness compared AT baselines using the same network archi- tecture, at the expense of 4x more compute (see Fig. 1). In fact, Fig indicates that one can simply adversarially training larger deep nets that can match the robustness and compute requirements of MRBoost models, rendering of-th- art boosting techniques obsolete for designing classifiers that are both robust and efficient.
In contrast, randomized ensembles, where one classifier is randomly selected during inference, offer a unique way of ensembling that can operate with limited compute resources. However, the recent work of Dbouk & Shanbhag (2022) has cast major concerns regarding their efficacy, they success- fully compromised the tfate-of-the-ar randomized defense Pinot et al. (2020) by large margins using their proposed ARC adversary. Furthermore, there is an apparent lack of proper theory on the robustness of randomized ensembles, as fundamental questions such as: "when does randomization help?" or "how to find the optimal sampling probability?" remain unanswered.
Contributions. In this work, we first provide a theoretical framework for analyzing the adversarial robustness of randomized ensmeble classifiers (RECs). Our theoretical results enable us to better
when compared to the high clean accuracy achieved in aov-adversarial setting

---

Under review as a conference paper at ICLR 2023
Robust Accuracy [%)
52
goal
networks:
ResNet-20
MobileNetV1
ResNet-18
48
4x less FLOPs
methods:
44
4.5% 19bustuut--aaa accuracy
Adv. Training
MRBoost
BARRE (Proposed)
40
102
10a
MFLOPs
Figure 1: The efficacy of employing randomized ensembles (*) for achieving robust and efficient inference compared to AT (+) and deterministic ensembling MRBoost (+) CIFAR-10. Robustness measured using the standard &o norm-bounde adversary with radius $/255.
understand randomized ensembles, revealing interesting and useful answers regarding their limits, necessary and sufficient conditions for them to be useful, and efficient methods for finding the op- timal sampling probability. Next, guided by our threoretical results, we propose BARRE, new boosting algorithm for training robust randomized ensemble classifiers achieving state-of-the-art ro- bustness. We validate the effectiveness of BARRE via comprehensive experiments across multiple network architectures and datasets, thereby demonstrating that RECs can achieve similar robustness to AT and MRBoost, at a fruction of the computational cost (see Fig. 1).
2 BACKGROUND AND RELATED WORK
Adversarial Robustness. Deep neural networks are known to be vulnerable to adversarial perturba- tions (Szegedy et al., 2013; Biggio al., 2013). an attempt to robustify deep nets, several defense methods have been proposed (Katz et al., 2017; Madry et al., 2018; Cisse et al., 2017; Zhang et al., 2019; Yang et al., 2020b; Zhang et al., 2022: Tjeng et al., 2018; Xiao al., 2018; Raghunathan al., 2018; Yang et al., 2020a). While some cauristic-based empirical defenses have later been broken by better adversaries (Carlini & Wagner, 2017; Athalye al., 2018; Tramèr al., 2020), strong de- fenses, such as adversarial training (AT) (Goodfellow al., 2014; Madry et al., 2018; Zhang al., 2019), remain unbroken but achieve unsatisfactory levels of robustness.
Ensemble Defenses. Building on the massive success of classic ensemble methods in machine learning (Breiman, 1996; Freund & Schapire, 1997; Dictterich, 2000), robust ensemble methods (Kariyappa & Qureshi, 2019; Pang al., 2019; Sen et al., 2019; Yang al., 2020b; 2021; Aber- nethy et al., 2021; Zhang et al., 2022) have emerged as a natural solution to compensate for the un- satisfactory performance of existing single-me model defenses, such AT. Earlier works (Kariyappa & Qureshi, 2019; Pang et al., 2019; Sen et al., 2019) relied on heuristic-based techniques for inducing diversity within the ensembles, and have been subsequently shown be weak (Tramèr al., 2020; Athalye et al., 2018). Recent methods, such as RobBoost (Abernethy et al., 2021) and MR Boost (Zhang et al., 2022), formulate the design of robust ensembles from margin boosting perspective, achieving state-of tfate--f-the-art robustness for deterministic ensemble methods. This achievement comes massive (4 5x) increase compute requirements, as each inference requires executing all members of the ensemble, deeming them unsuitable for safety-critiaal edge applications (Guo al., 2020; Sehwag et al., 2020; Dbouk Shanbhag. 2021). Randomized ensembles (Pinot et al., 2020), where one classifier is chosen randomly during inference, offer more compute-efficient alternative. However, their ability to defend against strong adversaries remains unclear (Dbouk Shanbhag, 2022: Zhang et al., 2022). In this work, show that randomized ensemble classifiers be ef- fective at defending against adversarial perturbations, and propose a boosting algorithm for training such ensembles, thereby achieving high levels of robustness with limited compute requirements.
2

---

Under review as a conference paper at ICLR 2023
Randomized Defenses. A randomized defense, where the defender adopts a random strategy for classification, is intuitive: if the defender does not know what is the exact policy used for a certain input, then expects that the adversary will struggle average to fool such a defense. Theoret- ically, Bayesian Neural Nets (BNNs) (Neal, 2012) have been shown to be robust (in the large data limit) to gradient-based attacks (Carbone et al., 2020), whereas Pinot et al. (2020) has shown that a randomized ensemble classifier (REC) with higher robustness exists for every deterministic clas- sifier. However, realizing strong and practical randomized defenses remains elusive as BNNs are too computationally prohibitive and existing methods (Xie et al., 2018; Dhillon et al., 2018; Yang et al., 2019) often end up being compromised by adaptive attacks (Athalye et al., 2018: Tramer et al., 2020). Even BAT, the proposed method of Pinot et al. (2020) for robust RECs, was recently broken by Zhang et al. (2022); Dbouk Shanbhag (2022). contrast, our work first demystifies randomized ensembles as we derive fundamental results regarding the limit of RECs, necessary and sufficient conditions for them to be useful, and efficient methods for finding the optimal sampling probability. Empirically, our proposed boosting algorithm (BARRE) successfully train robust RECs, achieving state-of of-the-art robustmess for RECs.
PRELIMINARIES & PROBLEM SETUP
Notation. Let F [M] be collection of M arbitrary C-ary classifiers fi Rd [C]- soft classifier, denoted by f Rd - RCC, can be used to construct hard classifier f(x) arg max [x()),. where [v]c = ue- We use the notation f(-10) to represent parametric clas- sifiers where f fixed mapping and 0
represents the learnable parameters. Let AM (v E [0,1] Σ v; = 1} be the probability simplex of dimension M - 1. Given probability vector a E Aw, we construct randomized ensemble classifier (REC) fa such that (x = (x) with probability ag, In contrast, traditional ensembling methods construct a deterministic ensemble classifier (DEC) using the soft classifiers follows?: f(x) arg max [E fi(x)) Denote
z = (x, y) E Fd x [C] as feature-label pair that follows some unknown distribution D. Let S c Rd be a closed and bounded set representing the attacker's 's perturbation set. A typical choice of S in the adversarial community is the lp ball of radius c: (c = 16 E Rdd
-100pp S c). For a classifier
fi F and data-point adversarial perturbations to fi at z.
(x, y), define (z) 1ō E S fi(x 5) # y) to be the set of valid
Definition 1. For any (potentially random) classifier f. define the adversarial risk ry.
(ff) = EZ-D
max B, [f 5) vH BES
The adversarial risk measures the robustness of f on average in the presence of an adversary (at- tacker) restricted to the set S. For the special case of S {0}. the adversarial risk reduces to the standard risk of f:
To( = EZ-D E, 1 (f(x) + u)ll -P サッ}
(2)
The more commonly reported robust accuracy of f. i.c., accuracy against adversarially perturbed inputs, can be directly computed from rff). The same can be said for the clean accuracy and 170 (f).
When working with an REC fa. the adversarial risk can be expressed as:
M
mffa = nn(a== = EZWD
max ÓES
a.1lf(x + 8) + 1
(3)
1=1
where we use the notation r7(cx) whenever the collection F fixed. Let (e: MMM C 10,1)M be the
standard basis vectors of R M then we employ the notation nffx) = n(fe.) = (c:) = n/
4 THE ADVERSARIAL RISK OF A RANDOMIZED ENSEMBLE CLASSIFIER
In this section, we develop our main theoretical findings regarding the adversarial robustness of any randomized ensemble classifier. Detailed proofs of all statements and theorems can be found in Appendix B.
the normalizing constant 1. does not affect the classifier output
3

---

Under review as a conference paper at ICLR 2023
f
shaded regions are misclassified
decomposition =1 C2 93 U G4 Ug
Ss
F4
maxr 6, a) max dz. 22 ag. 0z. BES
Ss
perturbation set 5
0 1 0 0
captured by configuration
1
G2
1
fz
f2
Figure 2: Illustration of the equivalence in (6) using example of three classifiers in R The shaded areas represent regions in the attacker-restricted input space where each classifier makes an error. All classifiers correctly classify x. The set U uniquely captures the interaction between and f1. /2, & /3 inside S.
4.1 PROPERTIES OF
We start with the following statement:
perturbbatnn set C Rd, and data distribution D, the adver- sarial risk 7) is piece-wise linear convex function Ya AMs. Specifically, 3K N configurations Us C {0, 1 vk E [K] and p.m.f. p E Âς such (hat:
Proposition 1. For any F= { 1
K
maa)=
Σ
max Deli
{u (uTa))
(4)
Before we explain the intuition behind Proposition 1, we first make the following observations:
Generality. Proposition makes no assumptions about the classifiers F, i.e., applies even the enigmatic deep nets. While the majority theoretical results in the literature have been restricted l bp-bounded adversaries. Proposition 1 holds for any closed and bounded perturbation set S. This is crucial, as real-world attacks are often not restricted to E, balls around the input (Liu et al., 2018; Duan et al., 2020). This generality is further inherited by all of our results, as they build on Proposition 1.
Analytic Form. Proposition allows to re- write the adversarial risk in (3) using the analytic form in (4), which is much simpler to analyze and work with. In fact, the analytic form in (4) enables us to derive our main theoretical results Sections 4.2 & 4.3, which include tight fundamental bounds on 77.
Optimal Sampling. The convexity of implics that any local minimum a also global min- imum. The probability simplex is closed convex set, thus global minimum, which need not be unique, is always achievable. Since piece-wise linear, then there always exists a finite set of candidate solutions for a". For M < 3, efficiently enumerate all candidates in Section 4.2, eliminating the need for any sophisticated search method. For larger M however, enumeration be- comes intractable. In Section 4.4, construct optimal algorithm for finding a by leveraging the classic sub-gradient method (Shor, 2012) for optimizing sub-differentiable functions.
Intuition. Consider data-point E T [C), then for any 5 S and AM have the per sample risk:
M r (z, 6, = Σ a. [f 6)
+ +) = =
(5)
where u E {0, 1] such that u, and only if adversarial to fi at z. Since u is independent of a. thus obtain many-to-one mapping from d E S to {0, (0.1) 11M Therefore, for any a and z, we can always decompose the perturbation set S, i.e., S = 91 U U Gn. into n < 2 u, for some binary vector u, independent of a. Let be the collection these vectors, then we can write:
subsets, such that: Vg E GG (z, d, a)
= (= {uy}y
r Ō max max (z, (2) max (axx((z,,,a)) dEC,U..UG, RES
max {u [Ta}] uell
(6)
JE(n DEC;
4

---

Under review as a conference paper at ICLR 2023
configuration 1
configuration 2
configuration 3
configuration 4
configuration 5
f2
fi
f
2
G2
92
f
fi
x
x
x
x
x
fz
G+
F1
fz
fz
1
1 [o]
Hil-i-10. U3 [10|
-ool
U4
-19--10 10]
Us
Figure 3: Enumeration of all K 5 unique configurations with two classifiers and data-point around set S. Note that since a 2 Vi, the vector redundant in Ui for ht [4]. which
explains why K = and not more.
The main idea behind the equivalence in (6) that we can represent any configuration of classifiers, data-p data-point point and perturbation set using unique set of binary vectors U. For example, Fig. pictorially depicts this equivalence using a case of M = 3 classifiers in R2 with = B2(c). This equivalence the key behind Proposition since the point-wise max term in (6) is piece- siiee linear and con- vex Vo E AM- Finally, Proposition holds due to the pigeon-hole principle and the linearity of expectation.
4.2 SPECIAL CASE OF TWo CLASSIFIERS
With two classifiers only, we can leverage the analytic form of in (4) and enumerate all possi- ble classifiers/data-poin configurations around S by enumerating all configurations U4g S {0, 1) Specifically, Fig. 3 visualizes all K 5 such unique configurations, which allows us to write Va A2:
n(ax= Pı max 02) p2 1 Pa + P4 + .0
where p E As is the p.m.f. of "binning" any data-point z into any of the five configurations, under the data distribution
D. Using (7), we obtain the following result:
Theorem 1. For any two classifiers fi and f2 with individual adversarial risks Tn and n2, respec- tively, subject to a perturbation set S C Idd and data distribution D, if:
P E(ZERi) > Im 72l
(8)
where:
R1= x [C]: + (2)) + 0, ( =0) o)
(9)
then the optimal sampling probability a = 1/2 2/2 uniquely minimizes Tπ(()) resulting in m(a²) = 2 (nh + 122 ( - R1)). Otherwise, a E (21 minimizes n)(x), where e,s are the standard basis vectors of R
Theorem 1 provides us with complete description of how randomized ensembles operate when M = 2. We discuss its implications below:
Interpretation. Theorem states that randomization is guaranteed to help when the condition in (8) is satisfied, i.e., when the probability of data-points (IP E R2}) for which it is possible to find adversarial perturbations that can fool f1 fz but not both (see configuration 1 in Fig. 3), greater than the absolute difference (nn m2)) of the individual classifiers' adversarial risks. Consequently, if the adversarial risks of the classifiers are heavily skewed, i.e., In 7/2 is large, then randomization is less likely to help, since condition (8) becomes harder to satisfy. This, fact, the case for BAT defense (Pinot et al.. 2020) since it generates two classifiers with 7/1 < 1 and 7/2 1. Theorem indicates that adversarial defenses should strive to achieve 7/1 As 7/2 for randomization to be effective. In practice, it is very difficult to make P E R2} very large compared 7h and 1)2 due to transferability adversarial perturbations.
Optimality Condition. In fact, the condition in (8) is actually a necessary and sufficient condition for n(a") < min(m (7, 72). That is, a randomized ensemble of fi and fa is guaranteed to achieve smaller adversarial risk than either fi of f2 if and only if (8) holds. This also implies that it is
5

---

Under review as a conference paper at ICLR 2023
impossible to have nontrivial' unique global minimizer other than a = 1/2] which provides further theoretical justification for why the BAT defense in (Pinot et al., 2020) does not work, where a" = [0.9 0.1] was claimed to be a unique optimum (obtained via sweeping a).
Simplified Search. Theorem I eliminates the need for sweeping a to find the optimal sampling probability a' when working with M 2 classifiers as done in (Pinot et al., 2020; Dbouk & Shanbhag. 2022). We only need to evaluate 7/ (D/2 1/2l") and check if is smaller than min(m1 (2)
to choose optimal sampling probability. In Appendix C.I, we extend this result for M 3. Interestingly, Vorobeychik Li (2014) derive a similar result for M = 2 for a different problem of an adversary attempting reverse engineer the defender's classifier via queries.
Theoretical Limit. From Theorem 1, we can directly obtain a light bound on the adversarial risk:
Corollary 1. For any two classifiers fi and fz with individual adversarial risks ih and Tp,, respec- lively, perturbation set S, and duta distribution D:
min n)(x) = -7(x')== min 2 oE
max m2) min(n, m2)
(10)
In other words, it is impossible for REC with M = 2 classifiers to achieve risk smaller than the RHS in (10). In the next section, we derive a more general version of this bound for arbitrary M.
4.3 TIGHT FUNDAMENTAL BOUNDS
A fundamental question remains to be answered: given ensemble F of M classifiers with adver- sarial risks "n..... YM,, what is the tightest bound we can provide for the adversarial risk 77(x) of a randomized ensemble constructed from F? The following theorem answers this question:
Theorem 2. For perturbation set S, data distribution DD and collection of M classifiers F with individual adversarial risks Th (i [M] such that O < in S ... S AM S 1, we have Va E AM:
min kE[M]
1 {
S n)(a= S JM
(11)
Both bounds are tight in the sense that if all that is known about the setup F, D, and S { then there exist no tighter bounds. Furthermore, the upper bound is always met if a eM, and the lower bound (if achievable) can be met if 1 o...... 0) where m arg min %o
Upper bound: The upper bound in (11) holds due the convexity of n (Proposition and the fact AM = H M1), where H(x)) is the convex hull of the set of points X.
Implications of upper bound: Intuitively, we expect that a randomized ensemble cannot be worse than the worst performing member (in this case fM). A direct implication of this is that if all the members have similar robustness 7) = n7 Vi, then randomized ensembling is guaranteed to either improve or achieve the same robustness. In contrast, deterministic ensemble methods that average logits (Zhang et al., 2022; Abernethy et al., 2021; Kariyappa & Qureshi, 2019) do not even satisfy this upper bound (see Appendix C.2). In other words, there are no worst-case performance guarantees with deterministic ensembling, even all the classifiers are robust.
Lower bound: The main idea behind the proof of the lower bound in (11) is to show that Vo E Ami
M
7(a)= 2
Σ 1=1
- (n=
max (az)) h((x))
2 min h((a) = h((²)= 7/m aE
(12)
JED....,a)
where 7/0 0, m arg min (=/x)) and h can be interpreted as the adversarial risk of an REC constructed from an optimal set of classifiers F with the same individual risks as F. We make the following observations:
Implications of lower bound: The lower bound in (11) provides us with a fundamental limit on the adversarial risk of RECs viz., it is impossible for any REC constructed from M classifiers with
that is different than e eg

---

Under review as a conference paper at ICLR 2023
sorted risks } 1 achieve adversarial risk smaller than c
[M]]
[m//k] mm/mm. This
limit not always achievable and generalizes the one (10) which holds for M = 2. Theorem
states that if the limit is achievable then the corresponding optimal sampling probability a'
[ 0... oj². Note that this does not imply that the optimal sampling probability is always
equiprobable sampling VFF
Additionally, the lower bound in (11) provides guidelines for robustifying individual classifiers in order for randomized ensembling enhance the overall adversarial risk. Given classifiers /1,-.. J' obtained via any sequential ensemble training algorithm, a good rule of thumb for the classifier obtained via the training iteration + 1 is have:
1
Mm S 7m++1 S
(1+=) Tmm m
(13)
Note that only for 1 does (13) become a necessary condition: If 172 27/, then fi will always achieve better risk than an REC of f1 and f2. If a training method generates classifiers fi,-., s'M with risks: !/1 and 7; Vi (2...., M), i.e., only the first classifier is somewhat robust and the remaining M - 1 classifiers are compromised (such as BAT), the lower bound in (11) reduces to:
1
n(a) 2 min Th M
(14)
implying the necessary condition M [nj '1 for RECs constructed from F to achieve better risk than /1- Note: the fact that this condition violated by (Pinot et al., 2020) hints to the existence of strong attacks that can break it (Zhang et al., 2022; Dbouk & Shanbhag, 2022).
4.4 OPTIMAL SAMPLING
In this section, we leverage Proposition to extend the results in Section 4.2 to provide a theoreti- cally optimal and efficient solution for computing the optimal sampling probability (OSP) algorithm (Algorithm 1) for M > 3.
In practice we do not know the true data distribution D. Instead, we are provided a training set Zi, .... Zn. assumed to be sampled i.i.d. from D. Given the training set, and fixed collection of classifiers F, we wish to find the optimal sampling probability:
M
Σ a +0) + mn vi))
a' = arg min f(a) = arg min - aEAM
arg max BES
(15)
aEdM n
Note that the empirical adversarial risk v is also piece-wise linear and convex in a, and hence all our theoretical results apply naturally. In order to numerically solve (15), we first require access to an adversarial attack oracle (attack) for RECs that solves VS, and a::
attack (F,S, arg
a, ( + 8) +
(16)
ÓES
Using the oracle attack, Algorithm updates its solution iteratively given the adversarial error-rate of each classifier over the training set. The projection operator II in Line (15) of Algorithm (2013) provide simple and
ensures that the solution is valid p.m.f.. Wang & Carreira- exact method for computing IT Finally, we state the following result on the optimality of OSP:
Theorem 3. The OSP algorithm output oer satisfies:
(I -
111 aa
Ma² T 2t=1
2-
0 ri((T) -i((a))
0
(17)
2a DuEi11 1-1
for all initial conditions ()) E AM. a O, where a global minimum.
Theorem 3 follows from direct application of the classic convergence result of the projected sub- gradient method for constrained convex minimization (Shor (2012)). The optimality of OSP relies on the existence of attack oracle for (16) which may not always exist. However, attack algorithms

---

Under review as a conference paper at ICLR 2023
such ARC (Dbouk & Shanbhag (2022)) were found to yield good results in the common setting of differentiable classifiers and Eo eerssttriteed adversaries.
Algorithm 1 The Optimal Sampling Probubility (OSP) Al-
Algorithm 2 The Boosting Algorithm for Robust Randomized En- sembles (BARRE)
gorithm for Randomized Ensembles
Input:
classifiers F (f perturbation set S, 1: Input: Number of classifiers M. perturbation set S. training set
tack algorithm attack, training set [2, initial step-
(2,)5-1 learning tale p. mini-batch size number epochs E,
size a > 0, and number iterations 21.
OSP frequency E... OSP number of iterations T.
2: Output: optimal sampling probability a'.
2: Output: Robust randomized ensemble classifier (F,ox)
3: initialize a1)) Asr. Thest
initialize 9. B.
4: te we find that (1
performs well
for E (1, M do
5: for (1...., T
Om <- mm F [
#1
6: 2- 0.0c 4
c E (1...,, E]
7:
mn for j (1, [l....n) do
for mini batch {2,]1' do
8:
8; + attack
compute vD [B] 6, + attack (F,
update 6., SGD:
9:
Wi [M]: 36 + 9e + (f(xx + 6,) As))
end for
11:
- ..8
sub gradient of (
p
Vo. (i(xs 5y 8m))))))))
n! -a (0
B Am1
if ify(0 S Thex then fest +- Tees x/0
10: end for
14:
/o projection-upaat step
11: Is update a every Es epochs
15:
(((4)) Ha (a(0 o(g)
12: if mod E, = then (3)
17: return a (!w)
end for
13:
end for
14:
end for
15: return F.a
5 A ROBUST BOOSTING ALGORITHM FOR RANDOMIZED ENSEMBLES
Inspired by BAT (Pinot et al., 2020) and MRBoost (Zhang et al., 2022), we leverage our results in Section 4 and propose BARRE: unified Boosting Algorithm for Robust Randomized Ensembles described in Algorithm 2. Given a dataset {z, 1 and an REC attack algorithm attack, BARRE iteratively trains a set of parametric classifiers f-)00). .... (-10ss) such that the adversarial risk of the corresponding REC is minimized. The first iteration of BARRE reduces to standard AT (Madry et al., 2018). Doing so typically guarantees that the first classifier achieves the lowest adversarial risk and r7(x*) S 1), i.e., Theorem ensures the REC is no worse than single model AT.
In each iteration m 2 2, BARRE initializes the m-th classifier J [(-10m) with On 0m- The train- ing procedure alternates between updating the parameters Om via SGD using adversarial samples of the current REC and solving for the optimal sampling probability a E Am, via OSP. Including f(100.) in the attack (Line (8)) is crucial, it ensures that the robustness of f- not com- pletely compromised, thereby improving the bounds in Theorem 2. Note that for iterations m < 3, we replace the OSP procedure in Line (12) with a simplified search over a finite set of candidate solutions (see Section 4.2 and Appendix C.I).
5.1 EXPERIMENTAL RESULTS
In this section, we validate the effectiveness of BARRE in constructing robust RECs.
Setup. Per standard practice, we focus on defending against fxr norm-bounded adversaries. We re- port results for three network architectures with different complexities: ResNet-20 (He al., 2016), MobileNetV1 (Howard et al., 2017), and ResNet- 18, across CIFAR-10 and CIFAR-100 datasets (Krizhevsky et al., 2009). Computational complexity measured via the number of floating- point operations (FLOPs) required per inference. To ensure a fair comparison across different baselines, we use the same hyper--aramene parameter settings detailed in Appendix D.I.
Attack Algorithm. For all our robust evaluations, will adopt the ofate-of-the-art ARC algorithm (Dbouk & Shanbhag, 2022) which can be used for both RECs and single models. Specifically, we shall use a slightly modified version that achieves better results in the equiprobable sampling setting (see Appendix D.3). For training with BARRE, we adopt adaptive PGD (Zhang et al., 2022) for better generalization performance (see Appendix D.4).
Benefit of Randomization. Table 1 demonstrates that BARRE can successfully construct RECs that achieve competitive robustness (within 0.5%) compared to MRBoost-triined deterministic
8

---

Under review as a conference paper at ICLR 2023
Table 1: Comparison between BARRE and MRBoost across different network architectures and ensemble sizes on CIFAR-10. Robust accuracy is measured against an &oo norm-bounded adversary using ARC with $/255.
M
M
Network
Method
Aax
Auh
F1.0Ps
Aus
Axb
FL.O%s
Aua
Anb
FLOPss
Aax
Aub
F1.0Ps
MRBoost
75.22
11.68
162 M
76.13
16.09
243 M
76.96
16.31
324
ResNet-20
73.18
41.99
81 M
BARRE
T4.63
44.38
81 M
75.35
45.41
81 M
75.95
46.44
81 M
MobileNetV1
MRBoost BARRE
79.01
46.22
312 M
80.19
48.58
624 M
79.79
49.39
936 M
80.14
49.36
1.2 B
79.58
48.32
312 M
79.53
48.75
312 M
79.54
49.38
312 M
ResNet-18
MRBoost
BARRE
80.96
48.7
1.1
82.66
83.90
50.72
50.51
2.2
1.1
83.40
85.07
51.57
52.15
3.3
R
83.54
85.07
52.13
52,15
4,4
1.1 B
ensembles, across three different network architectures CIFAR-10. The benefit of randomization can be seen for MM 2 2, as we obtain massive 4x savings in compute requirements. Note that both methods have the same* memory footprint. These observations further corroborated by CIFAR- 100 experiments in Appendix D.5.
Table 2: Comparison between BARRE and other methods at constructing robust randomized en- semble classifiers across various network architectures and datasets. Robust accuracy is measured against an Lo corm-bounded adversary using ARC with 8/255.
CIFAR-10
CIFAR-100
Network
FLOPs
Method
Size
Ana [%]
Anb [%]
Am [%)]
Anb [%]
AT
M
73.18
41.99
38.34
17.69
ResNet-20
81 M
IAT
M =
73.90
45.77
38.57
19.65
MRBoast
M
75.89
46.66
41.69
21.04
BARRE
M 5
76.28
47.35
41.86
21.11
AT
M
79.01
46.22
51.87
23.45
IAT
M = 5
78.89
49.57
51.41
25.74
MobileNetV1
312 M
MRBoost!
M =
76.70
48.05
50.14
24.76
MRBoost
M
78.65
48.91
52.96
25.95
BARRE
M 5
79.55
49.91
52.95
27.53
AT
M
80.96
48.72
58.85
24.15
IAT
M 1
80.99
51.43
54.30
26.73
ResNet-18
1.1
MRBos
M =
83.13
51.82
51.06
24.04
MRBoost
M 83.13
51.82
52.04
25.65
BARRE
M 83.54
52.13
541.63
26.93
result obtained ussuming equiprobable sumpling insteud of using OSP
BARRE vs. Other Methods. Due to the lack of dedicated randomized ensemble defenses, we es- tablish baselines by constructing RECs from both MRBoost and independently adversarially trained (IAT) models. We use OSP (Algorithm 1) to find the optimal sampling probability for each REC. All RECs share the same first classifier fi. which is adversarially trained. Doing ensures a fair com- parison, and guarantees all the methods cannot be worse than AT. Table 2 provides strong evidence that BARRE outperforms both IAT and MRBoost for both CIFAR-10 10 and CIFAR- 100 datasets. In- terestingly, we find that MRBoost ensembles can be quite ill-suited for RECs. This can be seen for MobileNetV1, where the optimal sampling probability obtained a (0.25 0.25 0.25 0.25 0] iee, the REC completely disregards the last classifier. In contrast, BARRE-trained RECs utilize all members the ensemble.
CONCLUSION
We have demonstrated both theoretically and empirically that robust randomized ensemble classi- fiers (RECs) realizable. Theoretically, derive the robustness limits of RECs, necessary and sufficient conditions for them to be useful, and efficient methods for finding the optimal sampling probability. Empirically, propose BARRE, a boosting algorithm for constructing robust RECs and demonstrate its effectiveness at defending against strong fox norm-bounded adversaries.
iignoring the negligihle memory overhead of storing

---

Under review as a conference paper at ICLR 2023
REFERENCES
Jacob Abernethy, Pranjal Awasthi, and Satyen Kale. A multiclass boosting framework for achieving fast and provable adversarial robustness. arXiv preprint arXiv:2103.01276. 2021.
Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give a false sense se- curity: Circumventing defenses to adversarial examples. In International Conference on Machine Learning, pp. 274-283. PMLR, 2018.
Battista Biggio, Igino Corona, Davide Maiorca, Blaine Nelson, Nedim Smdić, Pavel Laskov, Gior- gio Giacinto, and Fabio Roli. Evasion attacks against machine learning at test time. Joint European conference machine learning and knowledge discovery in datahases, pp. 387-402. Springer, 2013.
Stephen Boyd, Stephen P Boyd, and Lieven Vandenberghe. Convex optimization. Cambridge uni- versity press, 2004.
Leo Breiman. Bagging predictors. Machine learning, 24(2):123-140, 1996.
Ginevra Carbone, Matthew Wicker, Luca Laurenti, Andrea Patane, Luca Bortolussi, and Guido Sanguinetti. Robustness of bayesian neural networks gradient-based attacks. Advances in Neural Information Processing Systems, 5602-15311, 2020.
Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In 2017 ieee symposium on security and privacy (sp). pp. 59. IEEE, 2017.
Moustapha Cisse, Piotr Bojanowski, Edouard Grave, Yann Dauphin, and Nicolas Usunier. Parseval networks: Improving robustness to adversarial examples. In International Conference on Machine Learning, pp. 854 863. PMLR, 2017.
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. International Conference on Machine Learning, pp. 1310-1320 PMLR, 2019.
Hassan Dbouk and Naresh Shanbhag- Generalized depthwise-separable convolutions for adversar- ially robust and efficient neural networks. Advances in Neural Information Processing Systems, 34, 2021.
Hassan Dbouk and Naresh Shanbhag. Adversarial vulnerability of randomized ensembles. In Inter- national Conference Machine Learning, pp. 4890-4917. PMLR, 2022.
Guneet Dhillon, Kamyar Azizzadenesheli, Zachary C Lipton, Jeremy Bernstein, Jean Kossaifi, Aran Khanna, and Animashree Anandkumar. Stochastic activation pruning for robust adversarial defense. In International Conference on Learning Representations, 2018
Thomas G Dietterich. Ensemble methods in machine learning. In International workshop on multi- ple classifier systems, pp. 1-15. Springer, 2000.
Ranjie Duan, Xingjun Ma. Yisen Wang, James Bailey, A Kai Qin, and Yun Yang. Adversarial camouflage: Hiding physical-worf world attacks with natural styles. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 1000-1008, 2020.
Yoav Freund and Robert E Schapire. A decision-theoreticc generalization on-line learning and an application to boosting. Journal of computer and system sciences, 55(1): 199-199, 1997.
Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. arXiv preprint arXiv: 14,,6577,, 2014.
Minghao Guo, Yuzhe Yang, Rui Xu, Ziwei Liu, and Dahua Lin. When NAS meets robustness: In search of robust architectures against adversarial attacks. In Proceedings of the IEFF/CVF Conference on Computer Vision and Pattern Recognition, pp. 631-640, 2020.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp- 770-778, 2016.
10

---

Under review as a conference paper at ICLR 2023
Andrew G Howard, Menglong Zhu, Bo Chen, Dmitry Kalenichenko, Weijun Wang, Tobias Weyand, Marco Andreetto, and Hartwig Adam. Mobilenets: Efficient convolutional neural networks for mobile vision applications. arXiv preprint arXiv: 170.00770 2017.
Sanjay Kariyappa and Moinuddin K Qureshi. Improving adversarial robustness of ensembles with diversity training. arXiv preprint atXiv:/901.09900000 2019.
Guy Katz, Clark Barrett, David L Dill, Kyle Julian, and Mykel Kochenderfer. Reluplex: An efficient SMT solver for verifying deep neural networks. In International conference on computer aided verification, pp. 97-117. Springer, 2017.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. Technical report, Citeseer, 2009.
Xin Liu, Huanrui Yang. Ziwei Liu, Linghao Song, Hai Li, and Yiran Chen. Dpatch: An adversarial patch attack on object detectors. arXiv preprint arXiv: 02w.9,2299.2.. 2018.
Aleksander Madry, Alcksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. To- wards deep learning models resistant adversarial attacks. In International Conference Learn- ing Representations, 2018. URL ht tps / openreview net/ / forum 2id
Radford M Neal. Bayesian learning for neural networks, volume 118. Springer Science & Business Media, 2012.
Tianyu Pang, Kun Xu, Chao Du, Ning Chen, and Jun Zhu. Improving adversarial robustness via promoting ensemble diversity. International Conference on Machine Learning, pp. 4970--9779 PMLR, 2019.
Nicolas Papernot, Patrick McDaniel, Xi Wu, Somesh Jha, and Ananthram Swami. Distillation defense to adversarial perturbations against deep neural networks. In 2016 IEEE symposium on security and privacy (SP), pp. 582-597. IEEE, 2016.
Rafael Pinot, Raphael Ettedgui, Geovani Rizk, Yann Chevaleyre, and Jamal Atif. Randomization matters how to defend against strong adversarial attacks. In International Conference on Machine Learning, pp. 7717-7727. PMLR, 2020.
Aditi Raghunathan, Jacob Steinhardt, and Percy Liang. Certified defenses against adversarial exam- ples. In International Conference on Learning Representations, 2018.
Leslie Rice, Eric Wong, and Zico Kolter. Overfitting in adversarially robust deep learning. In International Conference Machine Learning, pp. 8093-8104, PMLR, 2020.
Vikash Sehwag, Shiqi Wang, Prateek Mittal, and Suman Jana. HYDRA: Pruning adversarially robust neural networks. Advances in Neural Information Processing Systems (NewrIPS), 7, 2020.
Sanchari Sen, Balaraman Ravindran, and Anand Raghunathan. EMPIR: Ensembles of mixed preci- sion deep networks for increased robustness against adversarial attacks. In International Confer- ence on Learning Representations, 2019.
Naum Zuselevich Shor. Minimization methods for nin-differentiublee funntioon volume 3. Springer Science & Business Media, 2012.
Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. arXiv preprint arXiv:1312.6199 2013.
Vincent Tjeng, Kai Y Xiao, and Russ Tedrake. Evaluating robustness of neural networks with mixed integer programming. In International Conference Learning Representations, 2018.
Florian Tramèr, Nicholas Carlini, Wieland Brendel, and Aleksander Madry. On adaptive attacks to adversarial example defenses. Advances in Neural Information Processing Systems, 33, 2020.
Florian Tramèr, Alexey Kurakin, Nicolas Papernot, Ian Goodfellow, Dan Boneh, and Patrick McDaniel. Ensemble adversarial training: Attacks and defenses. In International Confer- ence on Learning Representations, 2018. URL https:/ //ppnrevee/eeeeiiii.... net forum?id-
rkZvSe-RZ.
11

---

Under review as a conference paper at ICLR 2023
Yevgeniy Vorobeychik and Bo Li. Optimal randomized classification in adversarial settings. In AAMAS, pp. 485 4985-99,,00 2014.
Weiran Wang and Miguel A Carreira-Perpinte Projection onto the probability simplex: An efficient algorithm with simple proof, and application. arXiv preprint vrXiv:1309.15411 2013.
Kai Y Xiao, Vincent Tjeng, Nur Muhammad Mahi Shafiullah, and Aleksander Madry. Training for faster adversarial robustness verification via inducing ReLU stability. In International Conference on Learning Representations, 2018.
Cihang Xie, Jianyu Wang. Zhishuai Zhang, Zhou Ren, and Alan Yuille. Mitigating adversarial effects through randomization. In International Conference Learning Representations, 2018.
Greg Yang, Tony Duan, J Edward Hu, Hadi Salman, Ilya Razenshteyn, and Jerry Li. Randomized smoothing of all shapes and sizes. In International Conference on Machine Learning, pp. 10693- 10705. PMLR, 2020a.
Huanrui Yang. Jingyang Zhang, Hongliang Dong, Nathan Inkawhich, Andrew Gardner, Andrew Touchet, Wesley Wilkes, Heath Berry, and Hai Li. DVERGE: Diversifying vulnerabilities for enhanced robust generation of ensembles. Advances in Neural Information Processing Systems, 33, 2020b.
Yuzhe Yang, Guo Zhang, Dina Katabi, and Zhi Xu. Me-net: Towards effective adversarial robust- ness with matrix estimation. In International Conference on Machine Learning, pp. 7025-7034. PMLR, 2019.
Zhuolin Yang, Linyi Li, Xiaojun Xu, Shiliang Zuo, Qian Chen, Pan Zhou, Benjamin Rubinstein, Ce Zhang, and Bo Li. TRS: Transferability reduced ensemble via promoting gradient diversity and model smoothness. Advances Neural Information Processing Systems, 34, 2021.
Dinghuai Zhang, Hongyang Zhang, Aaron Courville, Yoshua Bengio, Pradeep Ravikumar, and Arun Sai Suggala. Building robust ensembles via margin boosting. In Proceedings of the 39th International Conference on Machine Learning, volume 162, pp. 26669-2888 26692. PMLR, 17-23 Jul 2022.
Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric Xing, Laurent El Ghaoui, and Michael Jordan. Theoretically principled trade-off between robustness and accuracy. In International Conference on Machine Learning. pp. 7472-7482. PMLR, 2019.
12

---

Under review as a conference paper at ICLR 2023
A THEORETICAL RATIONALE FOR BARRE
In this section, we expand on Section 5.1 and provide a more detailed rationale behind the steps in BARRE.
Given a dataset {z:}/=1 and an REC attack algorithm attack, BARRE iteratively trains a set of parametric classifiers f(-101), a(-(0ar) in a boosting fashion. Note that the optimality of OSP (Theorem 3) implies that a BARRE-trained REC is guaranteed to achieve better or the same perfor- mance than the BEST performing member of the ensemble. This explains the choice of boosting for BARRE, since the first iteration reduces to standard AT, the most effective method to date for generating robust classifiers. Thus, BARRE trained RECs are guaranteed to perform better than AT.
In each iteration m 2 2, BARRE initializes the m-th classifier f(-10m) with 8n 0m-1. The train- ing procedure alternates between updating the parameters on. via SGD using adversarial samples of the current REC and solving for the optimal sampling probability ing f-))0m.) in the attack (Line (8)) is crucial, as it ensures that the robustness of f(-10m. is not completely compromised, thereby improving the bounds in Theorem 2.
E Am via OSP. Includ-
Furthermore, the rationale behind the sequence of steps in BARRE can be better understood using Theorem (for the case of = 2). Theorem states that the optimal REC adversarial risk would be ni(a)) 1/ (m + 172 P [z E R1}) (assuming (8) is met), therefore it is equally important to minimize both 17's and maximize IP {z E R1}. BARRE does so by initially adversarially training a robust classifier fi (minimizing 7)), then training f2 (initialized from fi to minimizes 7/2) the
adversarial examples of the REC of fi and f2. Doing so increases P (z E R1} while maintaining m2 low possible.
13

---

Under review as a conference paper at ICLR 2023
B OMITTED PROOFS AND DERIVATIONS
B. PROOF OF PROPOSITION
We provide the proof of Proposition (restated below):
Proposition (Restated). For any F {ff perturbation set S C. RR, and data distribution D, the adversarial risk 1) is piece-wise linear convex function Vo E Aas- Specifically, 3K E N configurations Ug {0. 1] M Ak E [K] and p.m.f. p E AK such that:
K
7(x) = Σ
Pk max {u aTa)
(18)
uEll;
Proof. Consider having one data-point z E Rdd [C], then for any d E and a E AM we have:
M
r rz,,6, = Σ a ff 6) + マ = =
(19)
where u E {0, 13 such that u, if and only if ô is adversarial f; at z. Since is independent of a, we thus obtain many-to-one mapping from 6 E S to E 10.1)M Therefore, for any a and z, we can always decompose the perturbation uy for some binary vector uj independent of a. Let = {u;}y=1 the collection of these vectors, then we can write:
S, i.e. S 91 U ... Gn. into S 2M
subsets, such that: Vộ E : (z, 6, a))
maxr (z, dES
r max max (2, max {uTa) JE BEG;
(20)
SEGIU...G,
The vectors (u, define unique classifier and data-point configuration that is independent of the sampling probability. The function max8 r' is thus convex and piece-wise linear in a.
Partitioning the data-point space R C Hd [C] into K subsets R R2 U... UR such that all the data-points Z E R2 share the same set "configuration" Un. we obtain:
M
n(a)= EIND
a (f 8) + 4
Pz(z) max r (z, 8, a) dz BES
ZER
(z(z)
max (z, 6, a) dz dES
ZER
k=1
(21)
pz(z).
mmx (u aa)a) dz uEEliz
k=1
ZER
K
Σ
max {u Tuaa. netk
a) ZER
Pz(z) dz
kml
Σ
Pk max (u (uTa)) wells
where the total size of the partition K is finite (exponential in the size M) and p AR such that Pk = P (z E R4}. Finally. is convex and piece-wise linear in a since the summation of convex and picce-wise linear functions also convex and piece-wise linear.
B.2 PROOF OF THEOREM 1
First, state and prove this useful lemma:
14

---

Under review as a conference paper at ICLR 2023
Lemma 1. Let h IR -> IR be convex piece-wise linear, hence sub-differentiable, function of the form:
h(z) max + by, a2z b2) + azI + b3
(22)
such that 01 < 02. We wish to minimize h over I E [c,d] where S y S d, and y is the intersection
point ha=b1.
at a1aa
Then, the optimal value x² that minimizes
h(x)) (22), given by
1/ x²
if d3 E (-02, -11)
C, if a3 2 01
d, if a3 S -02
Note: only in the first case is the solution unique.
Proof. From constrained convex optimization (Boyd et al. (2004); Shor (2012)), we know that x" is the minimizer of h over [c, d] if there exists sub sub-gradient g ah(x*) such that:
(x x-)=x) 2 0 Vx E [c,d]
(23)
For * y, is differentiable with Vh = 03 a1 (if z y) or Vh a3 + 02 (if y), and for I the sub-differential is given by ah(y) = {a3 + 3an + (1 (11--)00 3)a2 3 [].
If a3 E (-a2, -a1), then 33 E [0. 1] such that d3 3aj + 3)02 0, and thus E @h(y). which is sufficient condition for global minimization, thus x = y. Furthermore, x is unique, since Vr * y. we will have Vh a1 + 03 < (if x < y) or Vh 02 + 0s > 0 (if y) which in both cases implies V2 # Er E [c. d] such that Vh(z) - < 0.
If ag (-02, -Q1), then either ag 2 d1 or a3 < -2. 03 2 -1,, then al + 0g Vh(c) 2 0, which implies that: (01 + +a) (a)
c) 2 0 Va E [c, d]. hence x² Otherwise if S - a2, then 02 + 03 = Vh(d) & 0, which implies that: (02 + 03) d) 2 Vo E [c, hence d.
We now provide the proof of Theorem (restated below):
Theorem (Restated). For any two classifiers f1 and f2 with individual adversarial risks 1n and mp respectively, subject to perturbation set S C Rd and data distribution D, if:
P P E R1 >
1mh - 72l
(24)
where:
R1 = f x [C]: S1(2) + (2(z) & 2, ( =
(25)
then the optimum sampling probability ax = (1/2, 1/2) uniquely minimizes n)(a) resulting in n(a")= (m + 7 ( R1)). Otherwise, a" E e2 minimizes 1)(x), where e,8 the standard basis vectors of R22
Proof. We know that, for M = 2, the adversarial risk y can be re-written Va Ag:
()x))= P1 max (2) + P2 P3 an + p4 02 + P5
(26)
where Pk
P (z E R₂ and the regions { partition the input space Rd [C] follows:
R1 = {z E Ed x
+ R₂ = {z E k x
+ S1) S2(z)) Ø
R3 = {z E E 0
(27)
R4 {z E Rd x
R₂+ {z E _d
= S2())= =
Using 01 - 02 a, we have Ya E [0, 1]:
n (aa. - a) )) h(aa P1 max 1 a} + (ps -P1) + P2 + P1
(28)
where we wish to find a* E [0. 1] that minimizes h(a).. Applying Lemma 1 with:
a1 = P1,
b -
Pl. a2 = Pl. 62 = 0, 03 = p3 P4. by = P2 + P4
(29)
and utilizing ? e7 pı + P2 Ps and 1/2 m)(22) = P1 + P2 p4. yields the main result.
n
15

---

Under review as a conference paper at ICLR 2023
B.3 PROOF OF COROLLARY
We provide the proof of Corollary 1 (restated below):
Corollary. For any two classifiers fi and fz with individual adversarial risks th and n2, respec- lively, perturbation set S, and data distribution D:
min n)(x)= = =n((a)) min { max (m. 12), min(n, n2n oE
(30)
Proof. From Theorem have that:
π(a") min
(mh + 1/2 P (z E R1}). min(m, nal 2
(31)
Using the tight upper bound on P (z E R1} I min 72), we obtain the main result.
B.4 PROOF OF THEOREM? 2
B.4.1 USEFUL LEMMAS
We first state and prove a few useful lemmas that are vital for proving Theorem 2. While some lem- mas trivial and have been proven elsewhere, nonetheless state their proofs for completeness.
Lemma 2. Let h R + I be a convex function, and H()) C R be the convex hull of X (x1,... xa) where { E R", then there exists X. X such that:
h(u) h((xm)
(32)
UEH(X)
Proof. Let u be any arbitrary vector in H()), that is Eax Ad:
a,3;
(33)
Let m [d] such that h(xm) 2 h(x;) Vi E [d]. From the convexity of h, we upper bound h(n) as follows:
d
d
h(u) = h Σ axx,
S
agh(x,)= < Σ ash((m)) = h(Xm)
Σ aj
h(xm)
(34)
1=1
Thus, (32) holds for any u E H(()).
Lemma (Redistribution Lemma). Vp, such that S SSP 2 5 999. Vo E AM, and VI, J C [M] such that I & I $ I we have:
p max + max(az) 2p max (as) + (q max(a;} +p- max {ax} EEI
(35)
JEJ
tEzuy
jEJ
kEING
Proof.
p max(aa) + max(a;} = p ai + a.
IEI JEJ
p. (ar + +a--) (g p) ag*
@ p.
max fai) min ( a3.) (g p) ag- iEZUJ
(36)
(6) max {a; (q - p) a-- +
2p.
max fas} kEZnTT
(ETUT
p max iEIUJ
{a:} (q p) max +
max {ax} kEInT
iEJ
where (a) holds because the maximum over I U J is either a,- or dj., and (b) holds since the smallest of the two maximizers cannot be smaller than the maximizer of the smaller set I INJ. n
16

---

Under review as a conference paper at ICLR 2023
Lemma 4. Let {fi)/=1
1 be arbitrary collection of C-ary classifiers with individual adversarial
risks Ti such that < 1n S ... T1M $ 1. For ant data distribution 'D and perturbation set S we
have Vo A
n(a) 2 Σ
(n: 17-1))
max
{ay)
(37)
jE(S...df)
where 7io =
Proof. From Proposition we know that 3F E N. Ak. and Us s {0, 1)M Ak [K] such that:
K Σ
max {u (uTaa)
(38)
ueli,
A=1
Let L* S [M] represent the set of classifier indices i1, ..., in that are active in the configuration Us. that is:
m E Lx
- Iv E Ua such that Um = 1
(39)
We then lower bound follows:
( Σ
Pk max {u a})
Σ
Pk max (as) (ax)
(40)
uell,
iELe
The bound trivially holds, since the of positive numbers is always larger than any summand. is noteworthy to point out that the RHS quantity (ax) can be interpreted as the adversarial risk of an auxiliary classifiers J' with same individual risks {nr such that for any E R2 [C]. the classifiers have no common adversarial perturbations, i.e.:
n S((2) =0
(41)
and:
= (/.)))
Σ kiiECa
pk = p==n(c;;) 17/
(42)
Assume that the conditions of Lemma 3 are met by two terms in 1/', i.c., 3kg 22 [K] such that Lxy & Liz & Lix, and Pk, S Pkay then we can apply the bound in Lemma and obtain:
((())) -
E
Pk max {ai)) = iELt
Pki
max {a;} + pko iEDe,
max {a:}
2 phl
max {ait + (pkz -Pk)) max {aj} ph.
max {ay} keLL naag
(43)
iE iEcx, Uling
jEENg
= (a)
Σ
Pk max tEC.
fm-mmxx(or {as)
where 1a"(x) is the modified ensemble adversarial risk. The application Lemma can un- derstood as way to "re-distribute" the classifiers' adversarial vulnerabilities while preserving the adversarial risk identities Vi [M]:
7 = (e:) = Σ p (e,))
(44)
kiECC
The main idea of this proof is keep applying Lemma 3 the modified ensemble adversarial risks (if possible) to obtain better lower bound. The process stops when the conditions are no longer met, and we obtain adversarial risk h(a:)
2.22(a)
Σ
9k max {agb
(45)
JEJ,
17

---

Under review as a conference paper at ICLR 2023
Without loss of generality, will assume that (Te) distinct and Os + O. Furthermore, since the conditions of Lemma 3 cannot be met by any two sets in {Jk}. we must have (up to a re-ordering of the indices):
Jr. C JL-1 c... C (M)
(46)
We now make the following observations:
1. Due to (46), we have that L S M and for all i E (M), 3m, E [L] such that:
7 =
Σ ANE
qk
(47)
2. Since {n.} are sorted, we get that m,+1 m, + 1 if < 7h41 m4+1 m, otherwise
3. Ji [M] since 7n
4. For any consecutive Ta and Jk-1, we can always find 1 indices from [M] such that Ts Jk+1 U (ōi..... }. The indices i1, in are consecutive, share the same
my (i.e., T7; the same for all / [ni),, and also satisfy:
min (4] max (5) + [E(n]
(48)
JEJN+1
We first prove the lemma for the special case of distinct risks, i.e. < 1/41 Vi.
Special Case. The risks are distinct, then we must have L M, with every two consecutive sets Ts and Je+1 differing by one index. Therefore we have Te = Je+1 U {k} and JM41 Furthermore, we will get 7/- - 7ji-1 = Vi [M] with rjo = 0. Thus we can write:
Ø.
M
M
((a)) = Σ
max JEJL
{ast
Σ 1=1
(1: Th-1) max {as}
(49)
JE(D....Mf)
General Case. For the general case we will have L < M distinct risks n7, .... < Th and repeated risks, where
1. Thus have Qk 7/s TR Vk: E [T.), and 1/o ?/o 0 by definition. Using observations and 4, we have that Te (u....,, for some index ug E [M] with i 1. Thus we have Mk+1 Uy equal to ThK Let { be the M - L index sets missing from {i E [M] {i.... M M) then we have:
0 be the number of of consecutive repeated risks
h(a))
9h max {ay}
JEJ.
(Mia The)
max je be(u.... M) {a²})
(50)
M-4
(0
(Nicms The)
{aj})
Σ
max {ast
max
jet jelme...,ds)
jE3,
kml
k=1
(1) m--1) max
{ag}
jE( jE(l....Mr)
where (a) holds due to the fact 17, 7/--1 = 0 for all the merged M L terms.
Lemma 5. Given sequence {r.) such that 0 = < S S TM S 1, the vector
a 0 0] E AM a solution to the following minimization problem:
M
min h(a) min aE
Σ i=1
(7a
7-1))
jE jE(t...M)) {az}
max
7/m
(51)
aεAM
m
where Tim
T4 Vi [M]
18

---

Under review as a conference paper at ICLR 2023
Proof. We know that h is piece-wiss wise linear convex function closed and convex set, which implies the existence global minimizer.
Define the mapping AM - [0, 1]M such that Vi [M]:
((aa)= jE(S....M)
{az} max
{az}
(52)
je(+4....M)
We can re-write the function h via simple re-arrangement to obtain:
Σ 7/' ( max JEft....My fazt
M
M
h(a))=
max
{ast)
Σ
Tt gi(a) = =7- g(a)
(53)
JE(++I...,
Define the decomposition over the probability simplex: Av Vn E [M!], ,2, f2,..., iM such that Yo E A we have:
M U A U U... U.. AM Mt
where
M
04 2 0k2 04i 2 ... aiu
(54)
other words, A is the set of all probability vectors that share the same sorting indices. Since we have M! ways to arrange M numbers, the size of the decomposition will be M!. We now make the following observations:
1. Vn, Aßr is convex set. quick proof: Let B Air. then 3ü, i2, 2,,,.. iM such that dig >
Z Oigg and 3i 2 ... 2 Bisr- VX E [0,1] we have q λo + (1 A)B E AM, since
Σ q: Σ da; + (1 2)3; = 1 and q: 2 0. We also have 4I E [M 1|:
qu: λo (1 -)B8 2 Aas4. + (1 A) qu+1
(55)
2. Vn, 3." = .p.,....PP!!! C Br such that Air H(P"), where H(x is the convex hull of the set of points X. quick proof: : Let is be sorted indices associated with an arbitrary subset Air. Construct the M probability vectors follows: Wk [M]] ph,
if j E {i1, .... ig else k/k: 1, and Pk.n ... 2 Ples
Př. = 0. It is easy to verify that P Ah. since E,Ph,
Since Aii convex (Claim 1), we thus have that H(P")) An M. What left show that A $
H(PP".. which can be established if we show that Vo E An M. =x E AM such that a = Σx AsPk.
We shall prove by construction, specifically define:
A ks (ate aiies) 2
(56)
This induces a valid convex coefficient vector X, since Ee d Σ (at, -0 En ai 1. It is also easy to verify that ai; Σx AsPR, for all indices is [M]. since:
M
M
(ais -0 + M
AAPE,
M - (aiw- -aix) ... (an aiiz1) = (57)
M
by construction of X and pr.
Vn, the function g is linear over a E Aii, quick proof: Define the maximum index s(a, i)
arg m {a,}- By definition, E A% implies that s(i) s(a, is independent of Therefore Vi E [M] we have (a))) aa((i) asti+1) with the slight abuse of notation am+1 0.
Therefore " (-1, 0, 0, 13
MxM such that g(a) G for all a A
Combining observations 1,2&3, we can re-write the original optimization problem as follows:
min h(a)= = aEAM
min u....u
7 g(a)
min RE[M]
min oEAR kt
> s(a))
7 T
min M
min (EE((P))
(58)
min RE[M]
min pEP"
7 TGPP
min xE[M]]
Y g(p))
19

---

Under review as a conference paper at ICLR 2023
where (a) holds because the minimum of linear function over the convex hull of set of points X' is obtained at one of the points in X.
Thus, to solve the original optimization problem, we only need to evaluate M!! linear functions with M vectors each, and pick the one that achieves the smallest value. Finally, we will now show that the search space be significantly reduced from M! M to M possible solutions.
Let A' be an arbitrary subset of AM whose associated sorted indices are Et. #2,..., TMy- and p"
{pk l are the associated extreme points. We first note that, Vk [M], g(p)) [0 10...
0]
with o ma ... {8. is the non-zero index. Therefore, we have that Vn, k:
TE K
h(p*) 7 g(p))
(59)
Equation (59) reveals that, amongst all vectors P with fixed k. the smallest error is always achieved by the subset n whose associated ji index is the smallest, since the robust errors are always assumed to be sorted. Furthermore, the smallest value that jă can achieve is k, since it is the largest index amongst k arbitrary indices from [M]. Therefore, let AM be the subset whose sorting indices are
in k, i.e. a AM implies an 2 ... 2 aM- For this subset, we will always have f max [1, }} = lc which implies that An E [M!] and Ak E [M]:
h(p)) = TE
2
= h(pk)
(60)
k
k
where p._ = [t ... & 0.... 0] Combining (58)&(60) we obtain:
min 1(())= = min > 9(p)) = min
7
7k-
(61)
oEAM
kE[M]
kE[M]
k
k-
which can be achieved using a" = k ... k- 0 0.. T
1
L
B.4.2 MAIN PROOF
We now restate and prove Theorem 2:
Theorem (Restated). For a perturbation set S, data distribution D, and collection of M classifiers
F with individual adversarial risks Tp (i E [M] such that 0 Th I ... S 17M S 1, we have Va E AM:
min [Tk (s((a kE[M]
{ TM
(62)
Both bounds are tight the sense that if all that is known about the setup F, D, and { then there exist no lighter bounds. Furthermore, the upper bound is always met if a eM, and the lower bound (if achievable) can be met i f====p -
where m = arg min l
Proof. We first prove the upper bound and then the lower bound.
Upper bound: From Proposition 1, we have that 1) is convex in E AM. Using AM H (fe),..., )w and applying Lemma 2, we get Va Am:
<7(x) < max 17(x)) = max T7(e,) 17M dEAM
(63)
This establishes the upper bound in (62). The bound is tight, since ()(r 7/M is achievable.
Lower bound: From Lemmas 4&5, we establish Va E Aas, the following result:
n(a)=
(n: (n--)-1) max je(t...,M (a;}) h((a))
min h((a) hh(a") m
Th
(64)
aEAM
where m arg min ( and a (62).
1 m
0 ... 0] This establishes the lower bound in
m
The bound is tight, since for fixed 0 < 17 S
I 7MM < 1, we can construct S, and D such that n(a)) = h(x)) and vi [M] :((e)) -h(e,) 1/s shown next.
20

---

Under review as a conference paper at ICLR 2023
Let S C R be any closed and bounded set containing at least M distinct vectors {6,}ح- S
S. Let D be any valid distribution over R Rd x [C] such that Vi E [M] (z E Ti} = ni
f TM+1] = 1, and Ø To C Ti T2 S ... S TM S TM+1 C R. Finally, we construct
classifiers fi (Vi [M] to satisfy the following assignment Vz TM+1:
y y xy
if (x, T
7) =y vo V { & fi(x 6.) =
(65)
otherwise
i.e., the i-th classifier decision fi(x + 6) is incorrect only if and z Tr. Given the above construction, we establish
ENND 17(a)
max BES
Σ
a, (fi(x 5) + v/
M
P=(z)-
max BES
0 [fi(x + 6) tul) dz
2ETM++
i=1
M
M
0 [fi(x + 0) (0))1) m) dz
(=(z).
max BES
ZETAATIL
k=
1=1
(66)
M
Pz(z)-
{ast dz (E
max
ZETAATE-1
M
max (as)) / (E(
TeTTa-1 (=(2)
M
(1: m-11)
(ay} h((x))
jE(k....d)
where: (a) holds because P E Tar+1] 1; (b) holds because we can partition TM into M + sets: T (T2 (.)U...(TMT:: TM). and because the max term is 0 Vz TMs+1 Tar: (c) holds by construction of F and S, and (d) holds since f/2 TP {z E Ti) and Ti C Ti+1-
B.5 PROOF OF THEOREM 3
First, we state the classic result on the convergence of the projected sub-gradient method for convex minimization (Shor (2012)):
Lemma 6 (Projected Sub-gradient Method). Let Rdd RR. be convex and sub-differentiable function. Let C C RRd be a convex set. For iterations / = 1,.., T, define the projected sub- sub-gradient method:
(t+1) IIe (x(()) (1)
(67)
(t+1) min best
(1) I1 h(x (xx(1)))
(68)
where at = f/r some positive a > O, x (2) E C is an arbitrary initial guess, tiee = lx(x and
g(t) E (h(x(()) is sub- gradient of h at x(1), Let bes designate the best iteration index thus far.
Then, if h has norm-boo non--ounded sub sub-gradiee gradients: |gg S G for all g (Oh(x) and x E C, we have:
(1)
G2 Gl at
(t) best
h2
0
(69)
2 2 ak
1-000
where:
h" = h(x')xxx-=))))))"())) min l(()
(70)
XEC
We then prove Theorem 3 (restated below) via direct application of Lemma 6:
21

---

Under review as a conference paper at ICLR 2023
Theorem (Restated), The OSP algorithm outpur oer satisfies:
0 S (j((r)))))) - -f((a))=== < |a aa 11 + Ma² -1
t-
0
(71)
2a Σi=1 t-
T-000
for any initial condition (1) E A. a > O, where o² is a global minimum.
Proof. The ensemble empirical adversarial risk i is convex and sub-differentiable (Proposition 1), being minimized over convex set A At each iteration / in OSP, the vector g obtained at line (12)
is norm-bounded with G VM, the vector g is also sub-gradient of f at o therefore Lemma applies.
22

---

Under review as a conference paper at ICLR 2023
C ADDITIONAL THEORETICAL RESULTS
C.1 SPECIAL CASE OF THREE CLASSIFIESS
In this section, we derive a simplified search strategy for finding the optimal sampling probability for the special case of M 3, akin to Section 4.2. Similar to (7), we can enumerate all possible classifiers/datz-ponnt configurations around S, which allows us to write Voe E A3:
a)())= P1 max 02, a23
P2 maxfa1 + a2, 0z3 + P3 max(a2 + a3, a1} + Pt maxfa1 + as, 02)
(72)
+ Ps max(a1, 02) + Ps max 0.s) + P7 max 0ss
ps 01 Pg 02 + P1o a3 + P11 1 P12
where p E A12. Using (72), we obtain the following result:
Theorem 4. Define A Ag to the set of the following vectors:
1/2
1/2
A
0
1/2
1/2
(73)
L/22
11/2
L//2
Then for any three classifiers S1, J2. and f3, perturbation set S C RRd, and data distribution D, have:
min naa)) = min 7)(x)
(74)
aEAs
The set A is optimal, in the sense that there exist no smaller set A' such that (74) holds.
Theorem 4 simplifies the search for the optimal sampling probability significantly, as it sufficient evaluate 7 exactly 10 different candidate solutions, captured by A. and pick the best performing one. Theorem 4 also guarantees that the search procedure is efficient, since every candidate solution A needs be evaluated.
Proof. We shall the same technique used in the proof of Lemma 5. We can decompose As into 6 such subsets AJ..., AS such that each subset contains vectors that share the same sorting indices. These subsets convex, and they can be represented as the convex hull of three vectors. Due to the symmetry of the problem, we shall focus on one subset A
H ({ (1,0,0) 1/2 (4/3, 1/3, 1/a) where Va E A we have: aj 2 a2 2 ag. Notice that for any a E AJ, all the terms in (72) become linear in a, except for the term max(ag +03, Therefore, we can further decompose Ag into two convex subsets Ag and A such that:
A (a E A on 2 02 + 03)
A (a D on S 02 03)
(75)
and 1j linear over both subsets (but not their union).
Claim: we have:
A H ((11,000) ((144,00),(/)422220 (127///)))
(76)
A/2 = H (f(122 1/)1 //2, 1/,0), 112,
Since both A and 1.2 are convex, is enough to show that:
411 1.1 C H (((10,0)) 12.2 1/211/1/// 1/0
(77)
A12 C 7l {{(1))) (1/2,1/2,1)))
(1/2,12200 ./2. .12, 1/41)/////
for (76) hold. For all A 1.1 define:
X1 01 02 03 2 0,
Xa = 2 (02 0a) 20 & A3 40g
(78)
23

---

Under review as a conference paper at ICLR 2023
Then always have:
[222 1/2
1/2
0
X2
X1
(79)
[0]
1/4
where it is easy to verify that a + X A3 the following:
1. The same can be shown for any Ag 1.2 using
A = 2 (a2 - 03) 2 0,
= 4- (al a2) 2 0, & A3 = 3- (a2 + a. - a 2 0 (80)
which establishes the claim in (76).
Using (76) and the linearity of yy on each subset, we can write:
min n(a)) min
min (EED)"
nTa),, min n(a)
a
(81)
1/22 1/2
1/2 1/4
1/3
min
17
.7
"
1/3
1/4
1/a
Finally, repeating this procedure for the remainder sets A Ag establishes (74). show that the set A is minimal, we provide 10 constructions of using the p vector in (72) such that the 7th
vector a A is unique (amongst A) global optimum 7 characterized by the 7th p vector (listed below):
P1
00000000
22 00
11
1 1000000!000
P2
2 2 00
0000000
P3
22 000
0000
0000 00 2
P4
00000
1 0000
P5
(82)
1 000000
100000101000 000
P6
2
00
00 2
1
1
000000
P7
P8
000
00
00000
2
2
Po
0
00
0000000
1000000000000
C.2 WORST CASE PERFORMANCE OF DETERMINISTIC ENSEMBLES
In Section 4.3, we showed via Theorem 2 that the adversarial risk of any randomized ensemble classifier is upper bounded by the worst performing classifier in the ensemble F. In this section, we will show that the same cannot be said regarding deterministic ensemble classifiers. That is, there exist an ensemble F, data distribution D, and perturbation set S such that:
n(f))
> max (ff))
(83)
M
24

---

Under review as a conference paper at ICLR 2023
where f is the deterministic ensemble classifier constructed via the rule:
f(x) arg eE[C]
Σ fx(x)
(84)
Consider the following setup:
1. two binary classifiers in R2:
{1 if if x 20
f(()) = 2 otherwise
(85)
which can be obtained from the "soft" classifiers:
f((x)
w
(86)
w
using fi(x) = arg (1,2 where = [1 11] and W2 = [1 - 1]
2. a Ber(p) data distribution ID over two data-points IR² x [2]:
( 2 .1) (1) and Z2 = (x2, U2) = (1-2] .1)
Z1 = (x1,
(87)
3. the & norm-bounded perturbation set S {ō || S c) for some 0 1/V2.
We first note that for binary linear classifiers and 22-nrrm bounded adversaries, we have that:
the shortest distance between a point and the decision boundary of linear classifier / with weight w and bias is:
w x + bl
(88)
w|
if f(x) # then the optimal adversarial perturbation is given by:
8 = -igg (w x x b)
ew
(89)
[w]
We can now evaluate the adversarial risks of each classifier:
max 1 {wi (x2 6) < <0]) [|61|5
[w]] (x: 5) < 01 + (1 11-p) p)
= max [|
(90)
=p. (1
V2e 0)) + (1- (1 0}) 1
where we use 1/v2. Due to symmetry, also get 1/2 p.
The average ensemble classifier f constructed from fi and f2 is defined via the rule:
[1 if f 2 0
f(xx
22 otherwise
(91)
whose adversarial risk can be computed as follows:
p. max 1 [ + 61) < <0} + (1 -1-p)) p) max 1 {x2,1 + + <0 < <0})
(92)
= (1 + p) (1 < = =
which is strictly greater than max(p. 1 1-p] Vp E (0, 1). Therefore, we have constructed an example where deterministic ensembling always worse than using any of the individual classifiers, which proves that deterministic ensemble classifiers do not satisfy the upper bound.
25

---

Under review as a conference paper at ICLR 2023
D ADDITIONAL EXPERIMENTS AND COMPARISONS
D.1 EXPERIMENTAL SETUP
In this section, we describe the complete experimental setup used for our experiments.
Training. All models are trained for 100 epochs via SGD with a batch size of 256 and 0.1 initial learning rate, decayed by 0.1 first at the 50th epoch and twice at the 75th epoch. We employ the recently proposed margin-maximizing cross-entropy (MCE) loss from Zhang et al. (2022) with 0.9 momentum and a weight decay factor of x 10 10-4. We use 10 attack iterations during training with c 8/255 and step size = 2/235. For IAT, each classifier is indepdenelty trained from different random initialization, using standard PGD adversary. For MRBoost, we use their public implementation from GitHub to reproduce all their results. For BARRE, (APGD) adversary (discussed in detail in Section D.4) as our training attack algorithm. We apply OSP for T. 10 iterations every E.- 10 epochs.
adaptive PGD)
To avoid catastrophic overfitting (Rice et al., 2020), we always save the best performing checkpoint during training. Since all the ensemble methods considered reduce to adversarial training for the first iteration, we use shared adversarially trained first classifier. Doing so ensures fair com- parison between different ensemble methods. For both CIFAR-10, and CIFAR-100 datasets, we adopt standard data augmentation (random crops and flips). Per standard practice, we apply input normalization as part of the model, so that the adversary operates on physical images x [0, 1]d.
Evaluation. For all our robust evaluations, we will adopt the state-of-the-ard ARC algorithm (Dbouk & Shanbhag, 2022) which can be used for both RECs and single models. Specifically, we use 20 8/255 and approximation parameter G = 2. Following
iterations of ARC, with attack strength the recommendations of Dbouk & Shanbhag (2022), we use a step size of 2/255 when evaluating single models (M 1) and step size of 8/255 when evaluating RECs (M 2 2).
D.2 INDIVIDUAL MODEL ROBUSTNESS
In Tables 3&4, we provide the clean and robust accuracies of all the individual classifiers constructed via the different ensemble methods on CIFAR-10 and CIFAR-100, respectively. Robust accuracy is measured using ARC.
As expected, only ensembles produced via IAT consist of classifiers achieving near-identical robust and natural accuracies. In contrast, ensembles produced via MRBosst or BARRE witness degra- dation in individual classifier robust accuracy the ensemble size grows. However, since MRBoost was not initially designed for randomized ensemble classifiers, this degradation in robust accuracy for MobileNetV1 in both Tables 3&4. This explains why, for such en-
can be rather severe sembles, the optimal sampling probability obtained for the constructed REC completely disregards the last classifier as highlighted in Section 5.1.
Table 3: Natural and robust accuracies of the individual classifiers of all ensembles methods trained on CIFAR-10 (from Table 2). Robust accuracy measured against an for norm-bounded adversary using ARC with 8/255.
fi
f2
fa
fa
fo
Network
Method
Ami
Amb
Ana
Arb
Ans
Arah
Aesi
Anah
Ama
Anbh
IAT
73.42
41.94
74.44
42.25
74.27
42.06
74.17
42.14
ResNet-20
MRBoost
73.18
41.99
76.00
41.42
76.59
39. 60
77.25
38.38
76.43
36.62
BARRE
76.08
41.18
77.40
39.87
77.12
39.07
77.60
37.01
IAT MRBoost
79.17
46.21
79.05
46.60 60.60
78.44
46.11
78.76
46.74
MobileNetV1
79.01
46.22
80.11
44.52
77.55
42.03
77.94
39.36
68.89
33.40
BARRE
80.15
44.56
79.43
42.67
79.56
39.65
79.60
38.28
IAT
80.64
48.23
81.24
48.83
81.13
48.70
ResNet-18
MRBoost
80.96
48.72
84.01
47.56
83.67
45.72
83.88
43.38
BARRE
84.35
46.48
$4.89
45.86
83.88
43.09
26

---

Under review as a conference paper at ICLR 2023
Table Natural and robust accuracies of the individual classifiers all ensembles methods trained on CIFAR-100 100 (from Table 2). Robust accuracy is measured against an &oo norm-bounded adversary using ARC with $/255.
NETWORK
METHOD
Auu
Awb
Aus
Awb
Ana
Aub
Ani
Aub
Auu
Anbb
IAT MRBoOST
38.40
17.89
39.13
17.63
38.36
18.
RESNET-20
38.34
17.69
41.69
17.29
42.69
17.67
42.92
17.44
42.83
16.11
BARRE
41.57
18.22
42.96
17.24
42.69
17.14
43.72
16.30
IAT MRBOOST BARRE
51.46
23.01
50.61
23.00
51.21
23.40
51.89
23.56
MOBILENETVI
51.87
23.45
53.96
22,65 22.63
53.45
20,48
02.55
19.90
38,88
11.34
52.75
22.90
53.61
21.21
54.31
18.67
51.99
18.02
IAT MR BROOS
53.85
24.17
54.80
24.30
64.71
24.50
RESNET-18
53.85
24.15
54.78
22.28
47.49
16.28
48.13
15.98
BARRE
55.21
22.26
55.69
21.05
53.73
17.99
D.3 ATTACKS FOR RANDOMIZED ENSEMBLES
Given a data-point (x, y) and potentially random classifier f. the goal of adversary is to find an adversarial perturbation that maximizes the single-point expected adversarial risk:
8 arg max rzz, 8) = arg max E, [1 1f(x + 6) + v}1 S:
arg max P (/(x + + y
(93)
Se
5: 5
where we adopt the Ep norm-bounded adversary for the remainder of this section.
Projected gradient descent (PGD) (Madry et al., 2018) is perhaps the most popular attack algorithm for solving (93) for the case of differentiable deterministic classifiers. Specifically, given a surro- gate loss function such as the cross-entropy loss, PGD finds an adversarial iteratively the following:
((k) TT. (8(k-1) + mpp (Vxl (xx+8(111))
8lk (
(94)
where up is the lp steepest direction projection operator, and 11 is the projection operator on the 4p ball of radius c.
In order to adapt PGD for evaluating randomized ensemble classifiers, Pinot al. (2020) first pro- posed adaptive PGD (APGD-L) using the expectation-ove orpettatioooverrtaaffommaaiooo (EOT) method (Athalye
Table 5: Comparing the success of different attack algorithms fooling various RECs using foe norm-bounded attacks with 8/255 on CIFAR-10. All the RECs are constructed with equiprohable sampling.
Network
Method
APGD-L
APGD-S
ARC
ARC-R
IAT
49.31
49.34
46.73
45.77
ResNet-20
MRBoost
49.65
49.61
47.74
46.66
BARRE
49.79
49.75
48.05
47.35
IAT
52.94
52.91
50.68
49.57
MobileNetV1
MRBoost
51.19
51.02
49.37
48.05
BARRE
52.16
51.94
51.16
49.91
IAT
54.50
54.49
52.42
51.43
ResNet-18
MRBoost
54.51
54.23
53.19
51.82
BARRE
54.52
54.07
53.62
52.13
27

---

Under review as a conference paper at ICLR 2023
Train with
/
78
Robust Accuracy [%)
Natural Accuracy [%]
M Mmmamm
40
74-
38
72-
70
68
20 40
60
80 100
20 40
60
80
100
Training Epochs
Training Epochs
Figure 4: The robust (left) and natural (right) accuracies of an REC of two ResNet-20's trained on CIFAR-10 using BARRE vs. the training epochs of the second classifier f2, where the first classifier fi is pre-adversarially trained. Robust and natural accuracies reported the test set, using foo norm-bounded adversaries with ARC and $/255.
al., 2018), which uses (94) with the expected loss function as follows:
(bk) mH (5lh-1) + 1/p VxB 1 (f (x x -
(95)
Note that the discrete nature of randomized ensembles allows for an exact computation of the ex- pectation in (95).
Recently, Zhang et al. (2022) proposed stronger version of adaptive PGD, where the expectation is taken at the softmax level (APGD-S). Using APGD-S, Zhang et al. (2022) were able compromise the BAT defense. Independently, Dbouk & Shanbhag (2022) studied the effectiveness of FOT- based adaptive attacks for evaluating the robustness of RECs, and concluded that such methods are fundamentally ill-suited for the task. Instead, they proposed the ARC attack (Algorithm 2 of (Dbouk & Shanbhag. 2022)), which relied on iteratively updating the perturbation based on estimating the direction towards the decision boundary of each classifier and using an adaptive step size method.
In this section, we propose a small modification to ARC (ARC-R) that proves to be quite more effec- tive in the equiprobable setting. Specifically, instead of looping over the classifiers in a deterministic fashion based on the order the sampling probability vector, we propose using a randomized order loop. This ensures that ARC is never biased towards certain classifiers. In fact, Table 5 demon- strates that ARC-R better than APGD-L (Pinot et al., 2020), APGD-S Zhang et al. (2022), and ARC (Dbouk & Shanbhag, 2022) evaluating the robustness of RECs CIFAR-IO, constructed with equiprobable sampling across various network architectures and ensemble training methods. Hence, we shall adopt this version of ARC for all our experiments.
D.4 ARC vs. ADAPTIVE PGD FOR BARRE
As highlighted in Section 5.1, we find that ARC, despite being the strongest adversary, leads to poor performance when adopted as the training attack in BARRE. In this section, we investigate this phenomenon, as we study the performance of BARRE using two different attacks during training, APGD (Zhang et al., 2022) and ARC (Dbouk & Shanbhag, 2022). Specifically, on CIFAR- using the ResNet-20 architecture. Both RECs share the same first classifier fi, which is adversarially trained using standard PGD. The second classifier f2 is trained via either APGD or ARC.
train two RECs
Figure 4 plots the evolution of both robust and clean accuracies of the two RECs across the 100 training epochs of f2, measured on the test set. Note that in both RECs, the robust accuracy is eval- uated via the stronger ARC adversary. When evaluated on clean images, we find that BARRE with
28

---

Under review as a conference paper at ICLR 2023
ARC leads to significantly more accurate RECs when compared BARRE with APGD. However, this comes at the expense of robust accuracy, as the REC obtained via BARRE with ARC is much more vulnerable than the APGD counterpart. We hypothesize that the adversarial samples generated via ARC during training do not generalize well to the test set. This explains why we observe that the REC obtained via BARRE with ARC achieves much higher robust accuracies the training Thus, for better gencralization performance, we shall adopt adaptive PGD during training in all our experiments.
D.5 ADDITIONAL RESULTS
In this section, complete the CIFAR-10 results reported in Table for showcasing the bene- fit randomization. Specifically, Table 6 provides further evidence that BARRE can train RECs of competitive robustness compared MRBoost-trained deterministic ensembles, while requiring significantly less compute.
Table 6: Comparison between BARRE and MRBoost across different network architectures and ensemble sizes CIFAR-100. Robust accuracy measured against foo norm-bounded adversary using ARC with $/255.
M
M
M
Network
Method
Aax
And
FLOPS
Ara
Alph
FLOPS
Aru
Anb
FLOPs
Aaz
Aui
FLOPS
ResNet-20
MRBoost
BARRE
38.34
17.69
39.95
19.13
81 M
40.96
19.85
81 M
41.40
43.62
21.36
21.41
81 M
NobileNetVV
MRBoost BARRE
51.87
23.45
312
54.41
25.73
624 M
51.91
26.63
936 M
55.03
26.97
1.2.B
52:31
24.96
312 M
52.74
25.75
312 M
53.14
27.12
312
ResNet-18
MRBoost BARRE
53.85
24.15
1.1
54.53
55.83
25.99
25.37
2.2
1.1
55.39
64.92
26.09
26.76
1.1 B
B
51.63
55.80
26.30
26.90
1.1 B
B
29


Reviews:
[{"review_id": "zykqbBll3c", "reviewer": "Reviewer_3zJ9", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper studies the limits of the adversarial robustness that can be obtained by combining $M$ different classifiers into one randomized classifier that at inference time, chooses one of the elements with certain probability. Some intermediate lower and upper bounds are presented that illustrate the main intuition behind the results. The main theorem is Theorem 2 which basically states that the randomized classifier in the worst case is as accurate as its worst component (trivial) and in the best case it can improve the robustness by a $1/M$ factor in the case where all classifiers have the same robustness (this is the interesting bound, and the result is stated in the more general case where each classifier might have a different robustness). Two algorithms are provided: the first obtains the best sampling probaility vector (assuming an oracle that obtains optimal adversarial perturbations) and the second is a boosting algorithm to obtain good classifiers to create the ensemble. In practical experiments it is shown that the second algorithm can lead to increased robustness against the state-of-the art ARC attack which was shown to break previous randomized ensemble defenses.\n\n**After Rebuttal**\nThe authors have addressed some of my concerns. Despite not addressing the missing confidence intervals in the experiments, I am inclined to increase my score because of the following:\n\n1. The method studied is interesting and significant, as there hasn't been an improvement in robust accuracy metrics from the single model paradigm in the last years. I believe most improvements have been on the training speed department rather than the robust accuracy metric. As such, exploring alternative paradigms like the randomized ensemble classifier studied here is one promising way forward.\n2. A good amount of contributions are theoretical, and they provide guidance on how to develop better algorithms for building RECs. As such, I think it is possible to give the authors a pass regarding the fact that the improvements over the baseline are small and lack the confidence intervals. Focusing only on the experimental part would dismiss the interesting theoretical results which could be used or improved upon by others. Of course, after reflecting on the results presented, they appear quite intuitive, however, i think it is a stretch to call them 'trivial' as other reviewers have dismissed. To support such a statement they should have provided a simplified proof or argument, which I believe is not the case.\n3. I disagree that not enjoying certain properties of BNNs would be a reason to dismiss researching RECs. Both are methods with pros and cons, and the goal of this paper as I understood was to advance the algorithmic and theoretical framework of RECs, rather than claim they are superior to BNNs in all aspects.\n4. There are some concerns that this method is not suitable for some applications (like certain medical tasks). However, applications of ML have vastly different specifications and its hard to develop a one-size-fits-all method.\n\nIn the end, raising my score will not help much as there is still a big disagreement with two other reviewers. It would be most helpful if they re-evaluate their score after the author's rebuttal, and express if some of their concerns have been addressed.", "summary_of_the_review": "Upper and lower bounds for the robustness of ensemble classifiers are presented. The results are quite interesting and their presentation is clear despite being highly technical. The theory leads to the design of principled algorithms that are evaluated against strong baselines, showing promise for improvement. Overall the paper seems to make significant contributions. However two big issues remain: (1) lack of discussion regarding prior results in the context of (non-adversarial) accuracy of ensembles and (2) computation of confidence intervals for the numbers presented in the tables. These two last points prevent me from confidently recommending acceptance but I would increase my score if they are addressed.", "strength_and_weaknesses": "The main strength of this paper are the interesting theoretical bounds on the performance of randomized classifiers. This is important as the paradigm of training a single robust classifier appears to have hit a limit in terms of robustness, and the obtained lower bounds from Theorem 2 indicate that randomizing the classifier could lead to potentially big improvements. Of course, the lower bounds are only achieved when the classifiers at hand have the nice \"incoherence\" property where they don't share \"vulnerable regions\" where all are simultaneously mistaken by an adversary. The paper does a good job of presenting the case of two classifiers where the results are pretty straightforward and easy to understand, before presenting Theorem 2, which is the statement in full generality.\n\nThe math appears to be correct (I have checked some of the results in detail) and all the statements are clear, as well as the flow of the proofs is well organised. This is in contrast with the awful quality of the maths/proofs from average ICML/NeurIPS/ICLR submission, so this deserves a special mention. I would say however that some proofs are a bit more difficult than needed, for example in the proof of Lemma 5 in page 18, the items (1) and (2) are trivial. (1) simply follows from the fact that the sets are intersection of half-spaces and (2) follows from the well known equivalence between Vertex and Hyperplane descriptions of convex polytopes, see for example https://link.springer.com/content/pdf/bbm:978-0-387-46112-0/1.pdf\n\nThe theoretical results are not left without application, as they are used to define the algorithms 1 and 2, which builds a randomized classifier in stages, by adding robust classifiers while simultaneouly optimizing the sampling probabilities of the ensemble. Overall the theory justifies the design of the algorithm which is ideal.\n\nThe main weakness I see (unfortunately) is the empirical evaluation. Now, I think the settings studied are extensive, but the fact that there is randomness involved in the algorithm (through the use of SGD) means that one should provide some assessment of the confidence about the numbers stated in Table 1 and 2. The authors only provide a single number and it might be the case that the improvements are due to randomness. Hopefully this can be resolved simply by running multiple seeds and computing some confidence intervals. That would greatly improve the paper.\n\nFinally another weakness is that the authors do not make an effort of presenting related results. I believe this topic should have been studied before at least in the context of clean accuracy (no adversary). The authors should comment on the relation to the papers:\n1. https://aamas.csc.liv.ac.uk/Proceedings/aamas2014/aamas/p485.pdf\n2. https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3156487/\n3. https://www.cs.waikato.ac.nz/~ml/publications/2002/bounds.pdf\n4. https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=7044723\n\nand cite them, as it seems they study a similar question (possibly in the non-adversarial setting). ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "yZ95dDWLIm", "reviewer": "Reviewer_5kPi", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In this work, the authors analyze randomized ensembles through a theoretical perspective. A randomized ensemble classifier (REC) is an ensemble of classifiers where predictions are made using only one of the constituent models selected at random. The authors analyze this set up in an adversarial scenario and show a series of elementary facts about them including bounds on the worst-case risk of the REC and from these facts show how to set the probability that any one classifier is taken from the ensemble as the model from which a prediction is made. The primary motivations for this set up are claimed to be (1) greater computational complexity compared to ensembles (2) greater adversarial robustness compared to both ensembles and single models. ", "summary_of_the_review": "Overall, I found the theory presented to be simplistic bordering on trivial. The claims are also incorrect in places (see the example in weaknesses).  The experimental analysis does not really report error bars which is also a red flag. Overall I think the work needs some further developments to be impactful.", "strength_and_weaknesses": "Strengths:\n\nThe authors provide promising empirical evidence that an REC can be made from an ensemble of classifiers such that one gets performance gains over the naive ensembling approach that would be typically taken.\n\nWeaknesses: \n\nThere are a couple of non-trivial drawbacks to this method that are not discussed. For the first contribution (having better computational complexity) the authors leave undiscussed the cost of this computational complexity. In particular, when using an REC one forfeits the uncertainty properties of an ensemble classifier (or Bayesian NN) which have been shown in many instances to help adversarial robustness and to aid in safety analysis. It feels like this is an important drawback: the computational gain here is not for free, you are sacrificing uncertainty. And this needs to be at the very least discussed if not empirically analyzed. \n\nThe theoretical results themselves are also simplistic, bordering on trivial. I do note here that I am not an expert on RECs, so perhaps reviewers with more experience in these models will find these results more interesting than I. In addition to being very simplistic the claims about some of the theorems are not correct. Most glaring to me is the statement that \"there are no worst-case performance guarantees with deterministic ensembling, even if all the classifiers are robust.\" This statement is either unqualified and therefore misleading or simply  incorrect. A deterministic ensemble (or BNN) is a single classifier: a model average. Therefore, they _do_ fit into Theorem 2 as there is only one model under consideration in these cases and therefore only one $\\eta$ (risk value) and therefore they do have the same guarantees. Thus the statement regarding Theorem 2 is incorrect. This also points to the fact that Theorem 2 is bordering on trivial because it can be said of any classifier and is not unique to RECs. \n\nFinally, the results, while they do show a slight increase in performance, do not include any error bars. This seems a large omission given that the performance gains are ~1% in many cases and this is a randomized method so not reporting the variance is a red flag. \n\nMinor note:  I find the placement of the related works to be a bit jarring. If it could be placed in before the problem statement that might help the flow of the paper. But this is stylistic.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "bM79tDbcPZ7", "reviewer": "Reviewer_BAMT", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper considers the problem of adversarial robustness. For this problem the paper investigates the usefulness of randomized ensemble classifiers (REC) where one classifier is randomly selected from the ensemble during inference.  The main motivation behind considering RECs over deterministic ensembles is that the former has much smaller inference time than the latter. \n\nThe paper makes two main contributions. The first contribution, which is on the theory front, involves careful characterization of the adversarial risk of RECs. In particular, the authors obtain reasonably tight upper and lower bounds for the adversarial risk of RECs that depend on the adversarial risks of the component classifiers in the ensemble. Based on these bounds, the authors provide some useful insights on how to design RECs with good adversarial risk guarantees. The second contribution is to provide a boosting style algorithm (BARRE) for constructing robust RECs that can tolerate adversarial attacks. The algorithm is mostly inspired by a recently proposed robust boosting technique called MRBoost.", "summary_of_the_review": "The clarity and presentation in the paper are good. The theoretical results are interesting and novel. But their usefulness is a little bit unclear. The empirical results look weak. Moreover, the proposed algorithm looks identical to MRBoost, except for a minor step which involves setting the weights of the component classifiers in the ensemble. Given this, I'm a little bit inclined towards rejecting the paper. But I'm happy to upgrade my score if the authors address my concerns.", "strength_and_weaknesses": "Strengths:\n  *  Randomized ensembling is an interesting defense strategy that is under-explored in the literature. While there are some works that provide algorithms for building robust RECs, they are easily broken by adaptive defenses. So there is a need for better randomized ensembling strategies. The paper takes a step towards solving this problem. The theoretical results provided in the paper on bounding the adversarial risk of RECs, are novel and interesting. However, it is not immediately clear how the insights gained from these theoretical results can be used to develop a good algorithm (more on this below).\n  *  The paper is easy to read. The clarity and presentation is good. The proofs are elementary and easy to follow.\n\nWeaknesses:\n  *  Motivation: \n      - The authors motivate the paper by saying that randomized ensembles can be computationally more efficient than deterministic ensembles. But there is a drawback of randomized ensembles that hasn't been brought up in the paper. In many application domains (e.g., healthcare), it is important to have deterministic predictions (otherwise it is hard to trust and understand these complex models). By moving to randomized ensembles, we lose this property. Can the authors provide some concrete use cases for randomized ensembles?\n      -  Low compute resource devices also tend to have low memory. But RECs have high memory requirement ( same as deterministic ensembles). Given this, and the fact that deterministic ensembling techniques (like MRBoost) have better performance than BARRE, it is not entirely clear what the practical applications of RECs could be.  \n\n\n  * Empirical results:  \n     - the empirical results look weak. For example, in table 1, MRBoost has better performance than BARRE both in terms of robust and standard accuracy. This seems to be in contrast with the message one gets by reading the theory section in the paper. For example in page 6 (in paragraph titled \"implications of upper bound\"), it is mentioned that deterministic ensembles have much worse performance in the worst-case. Why is there this mismatch between theory and experiments? \n         - under what circumstances are deterministic ensembles better than RECs and vice-versa? \n\n * BARRE: \n    - the algorithm looks almost identical to MRBoost, except for line 12 in Algorithm 2. In BARRE, the weights for each component classifier in the ensemble are recomputed after every boosting iteration. Whereas in MRBoost, all the component classifiers are given equal weights. Given this, why can't we simply add step 12 to MRBoost and get a randomized classifier out of it? How would the resulting algorithm compare with BARRE?\n    - What is the computational overhead of BARRE over MRBoost?  It looks like computing weights (line 12) can be expensive, especially for large M.\n    - In the introduction the authors claim that BARRE is based on the theoretical results in the paper (page 2). But I don't see any connection between the two. In particular, I don't see how the theoretical results in sections 3.2, 3.3 are used to derive this algorithm.  \n\n *  Theoretical Results: \n    -  A number of insights on how to obtain robust RECs have been provided in the discussion after theoretical results. Can these insights be used to derive a better algorithm than BARRE?\n\n * Minor comments:\n    -  a more detailed explanation on why K=5 in section 3.2 would be helpful to the readers\n    - ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "VALBXqwmZyP", "reviewer": "Reviewer_tU9P", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper considers randomised ensemble classifiers (RECs) and study the problem of how to assign the probabilities to select each classifier to improve the adversarial robustness of the REC. The authors first show that minimising the adversarial risk is equivalent to minimising a piecewise linear function with linear constraints. Then, by relying on the convexity of the problem, they develop algorithms to solve the resulting optimisation problem first in the case of 2 classifiers and then they consider the general case.  Experimental analysis on CIFAR-10 and CIFAR-100 compare the proposed method with state-of-the-art approaches.", "summary_of_the_review": "The paper studies an important problem and presents an interesting new perspective that makes possible to use of tools from convex optimisation. However, experimental results do not seem to present a substantial improvement compared to state-of-the-art. ", "strength_and_weaknesses": "Strength:\n\n-Paper is well written\n\n-The authors formally show that picking the optimal sampling probabilities for different classifiers is equivalent to optimising a piece-wise linear convex function over a convex set. This enables them to use tools from convex optimisation to solve this problem. I find this observation and the resulting algorithms interesting.\n\n\nWeaknesses:\n\n-Experimental results should be improved/clarified: \n\na) Table 1 and 2 report different trends in the comparison with MRBoost. In fact, while in table 1 MRBoost almost always obtains better accuracy and robustness compared to BARRE (the method presented by the authors), the trend is reversed in Table 2. This is particularly confusing for the ResNEt-18 M=4 example, where while BARRE has same values in both Table 1 and 2, for MRBoost these are different.\n\nb) Please, report computational times. Also, it would be interesting to also consider larger values of M.\n\nc) FLOPs in Table 1 is not defined\n \n\n-Theorem 1 guarantees that to improve the empirical risk of the ensemble compared to that of the individual classifiers, region $\\mathcal{R}_1$ should contain large probability mass wrt the input distribution. However, a discussion on how often this condition is verified in practice is missing. Intuitively, I believe that, due to the transferability of adversarial examples, such region will not be large in general. Nevertheless, a possibly interesting direction could be to train the individual classifiers in the ensemble with different adversarial training techniques in order to enforce that $\\mathcal{R}_1$ is large, while keeping each classifier accurate and robust to a particular class of attacks.\n\n-The fact that randomized classifiers can improve the adversarial robustness wrt the individual classifiers is well known. Therefore, also considering the above comments on the experiments, the results of the paper feel a bit incremental.\n\n-Finally, the comparison with the literature completely misses Bayesian ensembles, which have been already shown to be robust to adversarial examples, see e.g. [1]. \n\n\n[1]: Carbone, Ginevra, et al. \"Robustness of bayesian neural networks to gradient-based attacks.\" Advances in Neural Information Processing Systems 33 (2020): 15602-15613.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject