On the Role of Randomization in Adversarially Robust Classification
Authors: Lucas Gnecco Heredia
Muni Sreenivas Pydi
Laurent Meunier
benjamin negrevergne
Yann Chevaleyre
Venue: NeurIPS 2023 spotlight (2023)
Keywords: adversarial attacks
robustness
adversarial
attacks
deep learning
randomization
randomized ensembles
TL;DR: We study the conditions under which randomized classifiers offer improvements for adversarial robustness. We show that for any binary randomized classifiers, there exists a deterministic one that is at least as robust.

Abstract: Deep neural networks are known to be vulnerable to small adversarial perturbations in test data. To defend against adversarial attacks, probabilistic classifiers have been proposed as an alternative to deterministic ones. However, literature has conflicting findings on the effectiveness of probabilistic classifiers in comparison to deterministic ones. In this paper, we clarify the role of randomization in building adversarially robust classifiers.
Given a base hypothesis set of deterministic classifiers, we show the conditions under which a randomized ensemble outperforms the hypothesis set in adversarial risk, extending previous results.
Additionally, we show that for any probabilistic binary classifier (including randomized ensembles), there exists a deterministic classifier that outperforms it. Finally, we give an explicit description of the deterministic hypothesis set that contains such a deterministic classifier for many types of commonly used probabilistic classifiers, *i.e.* randomized ensembles and parametric/input noise injection.

On the Role of Randomization in Adversarially Robust Classification
Lucas Gnecco Heredia Muni Sreenivas Pydi' Laurent Meunier
Benjamin Negrevergne' Yann Chevaleyre'
CNRS, LAMSADE, Université Paris Dauphine PSL 2 Payflows
-lucas.gnecco--eer seeeecoo-errdiaammiee pddihhhu pal.ee psl. negrevergne, nennijiiinnngeeeegeeee..... Laurent@payflows..s
(benjamin. amin
yann che ammaade. dauphine fr
Abstract
Deep neural networks are known to be vulnerable to small adversarial perturbations in test data. To defend against adversarial attacks, probabilistic classifiers have been proposed as an alternative to deterministic ones. However, literature has conflicting findings the effectiveness of probabilistic classifiers in comparison to determinis- tic ones. In this paper, we clarify the role of randomization building adversarially robust classifiers. Given a base hypothesis set of deterministic classifiers, we show the conditions under which a randomized ensemble outperforms the hypothesis set in adversarial risk, extending previous results. Additionally, we show that for any probabilistic binary classifier (including randomized ensembles), there exists a deterministic classifier that outperforms it. Finally, give an explicit description of the deterministic hypothesis set that contains such deterministic classifier for many types of commonly used probabilistic classifiers, i.e. randomized ensembles and parametric/input noise injection.
1 Introduction
Modern machine learning algorithms such as neural networks are highly sensitive to small, impercep- tible adversarial perturbations of inputs [3, 43]. In the last decade, there has been back-and-forth in research progress between developing increasingly potent attacks [5, 10, 19, 25] and the creation of practical defense mechanisms through empirical design [8, 30. 32]. In particular, probabilis- tic classifiers (also called stochastic classifiers or randomized classifiers) have been widely used to build strong defenses which can be roughly categorized into two groups: noise injection tech- niques [14, 28, 34, 37, 47, 48] and randomized ensembles 38]. The first group includes methods that add noise at inference, usually to the input [22, 48), an intermediate layer activation [22, 47, 51] or the weights of parametric model [22] like neural network. Most of this work is experimental, with some theoretical papers that try to justify the use of such methods [37]. The second group, inspired by game theory, create mixed strategy over base classifiers finite mixture [31, 38). The argument behind this kind of models is that it becomes harder for an attacker to fool multiple models at the same time [12, 36).
Intuitively, the greater flexibility of probabilistic classifiers implies that they should outperform their deterministic counterparts in adversarially robust classification. For instance, one of the earliest works using randomization to improve robustness to adversarial attacks [48] claims that "randomization at inference time makes the network much more robust to adversarial images". Dhillon et al. [14] propose pruning method that "is stochastic and has more freedom to deceive the adversary".
"Corresponding author
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Similarly, Panousis et al. [34] claim that for their method, "the stochastic nature of the proposed activation significantly contributes to the robustness of the model".
Lending support to the intuition that probabilistic classifiers are better than their deterministic counterparts, Pinot et al. [38] prove the non-existence of a Nash equilibrium in the zero-sum game between an adversary and a classifier when both use deterministic strategies. Moreover, they show that a randomized ensemble outperforms any deterministic classifier under a regularized adversary. Meunier et al. [31] shows that a mixed Nash equilibrium does exist in the adversarial game when the classifier is allowed to use randomized strategies, making a strong case for probabílistic classifiers.
In contrast to the above results advocating for probabilistic classifiers, Pydi and Jog [40] use an equivalence between adversarial risk minimization and certain optimal transport problem between data generating distributions to show that in the case of binary classification there exists an approxi- mate pure Nash equilibrium in the adversarial game, showing that there always exists sequence of deterministic classifiers that are optimal for adversarial risk minimization. Trillos et al. [45] extend their results to multiclass classification using multimarginal optimal transport formulation. More recently, Awasthi et al. [1. 2] prove the existence of a deterministic classifier that attains the optimal value for adversarial risk under mild assumptions. Trillos et al. [44] extends to the multiclass setting.
How does reconcile these apparently confficting theoretical findings machine learning practitioner? First, it is important to note that the above theoretical results are valid when considering large hypothesis sets, like that of all possible measurable classifiers. In practice, one works with more limited hypotheses sets such as the space of linear classifiers or the space of classifiers that can be learned by an T--layered deep neural network, for which the above theoretical results do not directly apply. Second, the task of training a robust probabilistic classifier is non-trivial [12, 39J. Even the task of efficiently attacking probabilistic classifier is not straightforward [6. 12, 13, 36]. Hence, it is important to understand the precise role of randomization in adversarial robustness and the conditions under which probabilistic classifiers offer a discernible advantage over deterministic classifiers. In this work, we address this issue by making the following contributions.
From deterministic to probabilistic classifiers: Given a base hypothesis set (BHS) Hi of deterministic classifiers, we prove the necessary and sufficient conditions for a probabilistic classifier built from Hs to strictly outperform the best classifier in Hs in adversarial risk. A quantity that plays a crucial role in our analysis is the expected matching penny gap wherein there exist classifiers that are vulnerable to adversarial perturbation at a point, but not all at the same time. These results are contained in Section 3.
From probabilistic to deterministic classifiers: a probabilistic classifier h, we show that there always exists a deterministic classifier belonging to "threshold" hypothesis set (THS) that is built from h in straightforward way. We then apply our results to common families of probabilistic classifiers, leading to two important conclusions: 1) For every randomized ensemble classifier [13, 38]. there exists a deterministic weighted ensemble [17, 52] with better adversarial risk. 2) For every input noise injection classifier [22, 37, 39], there exists deterministic classifier that is slight generalization of randomized smoothing classifier 18, 26) with better adversarial risk. These results are contained in Section 4.
In the binary classification setting, given
Families of classifiers for which randomization does not help: Given BHS Hs. show the conditions under which randomizing over classifiers in Hs does not help to improve adversarial risk. Specifically, if the decision regions of Hr are closed under union and intersection, our results imply that randomized ensembles built using Hi offer no advantage over the deterministic classifiers in Hp. These results are contained in Section 5.
Notation: We use 1{C} to denote an indicator function which takes value if the proposition C is true, and 0 otherwise. For an input space X C Rd, we use (xX) to denote some o-algebra over X' that makes (X, (XX)) a measurable space. If not specified, (XX)) will be the Borel o-algebra, which is generated by the open sets of X. We use P(2') to denote the set of probability measures over the measure space (X, (.))). For a positive integer K, we use [K] to denote the range (1...., K). For vector E RK we denote u, the ith component of u.

---

2 Preliminaries
2.1 Adversarially Robust Classification
We consider classification setting with input space X _ IK and finite label space The space X' is equipped with some norm ||-I], which is commonly set to be the lg or &oo norms. Let p E P(X x)) denote the data distribution, which can be factored as p(z, y) u(y),y()), where P())) denotes the marginal probability distribution of over y and py E P(2) denotes the conditional probability distribution of the data over X' given class y.
deterministic classifier is a function h : X + y that maps each x E X to a fixed label in y. The 0-1 loss of h on point (ar, v) E X is given by, (0x h) 11 [h(x)) # v)-
X - P()") that maps each x E X' to a probability distribution over V. To label E X' with h. one samples random label from the distribution h(x) E P()). In practice, if y consists of K classes, P())) is identifiable with the K --simplex A K that consist of vectors u E RK such that Ei=1 u. = 1. Therefore. one can think of h(x) as probability vector for every æ.
probabilistic classifier
function
The 0-1 loss of h on (x, y) E &''x v/yiin is given by, ((x h) = Eg-n(z) + v}1 = 1 1- -h(()y- Note that g0r1 ((x, y), h) E [0, is a generalization of the classical 0-1 loss for deterministic classifiers, which can only take values in {0,
Given x. E X, we consider a data perturbing adversary of budget e 2 that can transport æ to x' E B, (z) {a' E X d(x, S E), where (x) is the closed ball of radius e around The adversarial risk of a probabilistic classifier h is defined as follows.
R. (h)
E you
(b)] = E
E
sup (xE
( (((z,,)) v).
(I)
you zoppy
The adversarial risk of deterministic classifier f is defined analogously, replacing h by / in (l).
2.2 Threat model
We consider a white-box threat model, in which the adversary has complete access to the classifier proposed by the defender. theory, we are assuming that the adversary is able to attain (or approximate to any precision) the inner supremum in (1). In practice, if the classifier is differentiable, supremun
the adversary will have full access to the gradients (and any derivative of any order), and will have full knowledge of the classifier, including its architecture and any preprocessing used. The adversary can also query the classifier as many times as needed. The only limitation for the adversary regards the sources of randomness. In particular, when the proposed classifier is probabilistic and an inference pass is done by sampling a label from h(r), the adversary does not know and cannot manipulate the randomness behind this sampling.
is worth noting that other works have considered similar inference processes, in which the label of point is obtained by sampling procedure [29]. The underlying question is similar to ours: does randomness improve adversarial robustness?. They propose a threat model in which an attacker can perform N independent attempts with the goal of producing at least misclassification which becomes easier if the predicted probability for the correct class is less than 1. In this paper, however, are interested in the expected accuracy of classifier from theoretical point of view, which in practice translates to the probability of error, or the long term average performance or the classifier.
Our formulation of adversarial risk in (1) corresponds to the "cconstantinn-the-oee "corrupeed-istancee instancee"""" risk in [15]. Under this formulation, as pointed out in [40], an adversarial risk of 0 is only possible is the supports of the class-conditions distributions Py are non-overlapping and separated by at least 2e. This is not the case with other formulations of risk introduced in [15, 20]. We focus the former in this work.
risk in [20] the
'The measurability the 0-1 loss under attack (inner part of (1)) is non-tric non-trivial and depends on various factors like the type of ball considered for the supremum (closed or open) [44], and the underlying olalgebra [1. 40]. In Section 2.3 and Appendix A we will clarify the assumptions that ensure the well dellneeeiss of the adversarial risk in our setting.
3

---

2.3 Probabilistic Classifiers Built from a Base Hypothesis Set
In this paper, we study probabilistic classifiers that are constructed from base hypothesis set (BHS) of (possibly infinitely many) deterministic classifiers, denoted by Hs. We use the name mixtures [38] for these type of classifiers. In the following, we show that many of the probabilistic classifiers that are commonly used in practice fall under this framework.
Let Hi be BHS of deterministic classifiers from X' to Y/ which we assume is identifiable with a Borel subset of some R². Let μ E P(H,) be a probability measure over the measure space (He, (HH)), where a (HH)) denotes the Borel o-algebra on Hé. One can construct probabílistic classifier hy X + P())), built from Ho. that maps I E X' to probability distribution μlx E P()), where Ms (y) = Ph~y (h(x) = y). We now instantiate Hd and μ P(Hs) for two main types of probabilistic classifiers that are commonly used in practice: randomized ensembles and noise injection classifiers.
For a randomized ensemble classifier (REC), μ E (Ms) c P(Hb) where Par (Ha) is the set of all discrete measures on Hi supported on a finite set of M deterministic classifiers, {/1,.... hyy) ].
In this case, (x) takes the value hm) (x) with probability Pm ju(hm)) for m E [M]. where
Eme[M] Pm 1. RECs were introduced in [38] and play the role of mixed strategies in the adversarial robustness game. They are simple randomization scheme when a finite number of classifiers are at hand, and both training and attacking them represent a challenge [12, 13].
For weight-noise injection classifier (WNC), Ho { E W) where hww is deterministic classifier with parameter w. In this case, μ is taken to be a probability distribution over W with the understanding that each E W is associated with unique h. H4. For example, Hd can be the set of all neural network classifiers with weights in the set W C R². Any probability distribution on the space of weights W results in probabilistic classifier h Alternatively, Hs can be generated by injecting noise 2 sampled from a distribution j to the weights wp of a fixed classifier hwg- In this case, the probabilistic classifier h, maps x E X' a probability distribution Ma P())) where Men (v) = P=-n (Anoo+ (x) = y). Weight noise injection has been explicitly used in [22], but there many other approaches that implicitly define probability distribution over the parameters of model [14, 35] and sample one or more at inference.
For input-noise injection classifier (INC), Hos = [h, 17 E X} where -x) ho + 17) for fixed deterministic classifier hg. In this case, μ is taken to be probability distribution over (which is unrelated to the data generating distribution), and h2 maps
X to probability distribution Meg E P)))), where (4= (v) = IP Pr (h(r + n) = y). Injecting noise to the input has been used for decades as regularization method [4, 21]. INCs are studied in [22, 37, 39] defense against adversarial attacks, and are closely related to randomized smoothing classifiers [8, 26].
Remark 1 (Measurability). To ensure the well-definedess of the adversarial risk, we need to ensure that the 0-1 loss under attack (inner part of (1)) is measurable. The 0-1 loss for fixed class y E y can now be seen as a function from the product space X' x Hs to {0, 1}:
fax h) = e ((x, h) = 1 (M(x) + y)
(2)
For distribution μ E P(Hs) and the associated probabilistic classifier hy, we can rewrite the 0-1 loss of h, at x as
f. f(,h)dd((h)
((. ((.)),,)) = E (1()() # wإl
Jn.
Note that if f is Borel measurable in X' x Ho. then by Fubini-Tonelli's Theorem, Theeree,, the 0-1 loss as a function of x with an integral over Hs shown in (3) is Borel measurable. By [16, Appendix A, Theorem 27], the 0-1 loss under attack is then universally measurable and therefore the adversarial risk, which requires the integral over X of the loss under attack, is well-defined over this universal o-algebra [44, Definition 2.7]. Recent work by Trillos et al. [44] have also shown the existence of Borel measurable solutions for the closed ball formulation of adversarial risk.
In this work, we assume that the function f in (2) is Borel measurable in X' x H, for every y, so that (1) is well-defined. This assumption is already satisfied in the settings that are of interest for our work. As an example, it holds when the classifiers at hand are neural networks with continuous activation functions. More details on Appendix A. For a deeper study on the measurability and well-definedness of the adversarial risk in different threat models and settings, see [1. 16, 40, 44].

---

3 From Deterministic to Probabilistic Classifiers
Let Hs be a class of deterministic classifiers. In this section, we compare the robustness of proba- bilistic classifiers built upon Hd with the robustness of the class H,, itself. Note that if we consider the trivial mixtures μ on for h E Hs. we obtain the original classifiers in Ha. so it is always true that (HH,)) R2 (h,,) I infRER, (h)... We are interested in the situations in which this gap is striet, meaning that mixtures strictly outperform the base classifiers. With this in mind, we introduce the notion of Matching Penny Gup to quantify the improvement of probabilistic classifiers
over deterministic ones.
Theoretical Results on Robustness of Probabilistic Classifiers. We begin by presenting theorem which shows that the adversarial risk of a probabilistic classifier is at most the average of the adversarial risk of the deterministic classifiers constituting it. The proof of this result will be first step towards understanding the conditions that favor the mixture classifier.
Theorem 3.1. For a probabilistic classifier hy : X + P(Y) constructed from BHS Hi using any E (HH)), we have R. (b,.) S Es-z [R.(h)]
A natural follow-up question is to ask what conditions guarantee a strictly better performance of a probabilistic classifier. We know that this gap can be strict, as can be seen in toy examples like the one shown in Figure 1b where Hy the set of all linear classifiers, and there exist two distinct classifiers f1, fe both attaining the minimum adversarial risk among all classifiers in Hg. Any non-degenerate mixture of fi, f2 attains a strictly better adversarial risk, demonstrating strict advantage for probabilistic classifiers.
From the proof of Theorem 3.1 it is clear that strict gap in performance between probabilistic and deterministic classifiers is only possible when the following strict inequality holds for a non- non-vanishing probability mass over (x, v))
sup E [1(h(x') + E'EB, (a)) hopp
E sup 1(h(z') * v\ hmw
(4)
(')
The above condition holds at (x, y) if there exists subset of vulnerable classifiers Heb C Ho with p(Hoo) > any of which can be foreed to individually misclassify the point (z,y) v) by an adversary using (possibly different) perturbations x', E (z) for h E Hub. but cannot be forced to misclassify all at the same time using the same perturbation x' E B, (x). Such a configuration is reminiscent of the game of matching pennies [18, 46] (see Appendix B). If H4 is in a matching penny configuration at (I. y). a mixed strategy for classification (i.e. a mixture of Ha) achieves a decisive advantage over any pure strategy (i.e. any deterministic base classifier) because the adversary can only force a misclassification on a subset of all vulnerable classifiers. Such a configuration was first noted in [12] in the context of improved adversarial attacks on RECs, and also in [13] for computing the adversarial risk of RECs of size M = 2. Figure 1 illustrates such a condition on an example REC of size M = 2 over single point (Figure la), and over a simple discrete distribution (Figure lb). We formalize this intuition with the definition below.
Definition (Matching penny gap). The matching penny gap of a data point (x, y) E (X' x y) with respect to probabilistic classifier hy constructed from Hd using μ E P(H)) is defined as,
Th (x, v) ((Hos 9)) - max (I, u):
(5)
where Hus(I, y) S Hi denotes the vulnerable subset and m.ma (I, y) the maximal simultaneous vulnerability of base classifiers Ho, defined below.
Hoblz, y) (h E Ho : 3ayh E Bz(z) such that h(ahh) F y),
Dx0b v) (H' C Hss : 3x' E (x(x) such that Vh E H', h((x)) + yh.
1 max (x, v) sup
((H').
If Th, (x.y) > we say that h in matching penny configuration at (xr, v)-
For example, in Figure la, The (Zo. yo) = max( min(p(fi). (((2) where Hss (f1, f2). The subset Hos(z,y) y) contains all classifiers that can be individually fooled by an
5

---

optimal attacker. The collection of subsets Deeb (2, y) contains all subsets 't' of classifiers that can be simultaneously fooled. Then, y= y) the maximum mass of classifiers that can be fooled simultaneously. Thus, Th, (r. y) measures the gap between the mass of classifiers that are individually vulnerable and the maximum mass classifiers that can fooled with only one perturbation.
f1
22
J3
f2
V.A
f1(2)
fa(2) =1
(a) A matching penny configuration at with two deterministic classifiers and f2 with fi (xx)= f2(20) = yo- top-left colored region, fi (a) o yo. and on the bottom-right colored region fz (1) * (vulnerability regions). Both fi, can be made to incur loss of at B. (zu) by separate perturba- tions, but not with the same perturba- tion.
f - f2(a)
(b) Binary classification example with discrete data distri- bution 18(z = 21, 1) - 36(z 2y, y = 0). No linear classifier can attain adversarial risk better than (attained by both and f2). Any REC with u(fi) i 1-#(f2) E (0, 1) achieves strictly better risk. REC with ((fi) f(ffa) = 1/2 optimal with risk 1. See Appendix C.4 for details.
Figure Toy examples demonstrating a strict gap in adversarial risk between deterministic and probabilistic classifiers (RECs).
The following theorem strengthens Theorem 3.1 by showing that R. (h) is a strictly convex function if and only if there is a non-zero expected matching penny gap.
Theorem 3.2. For a probabilistic classifier h : + P(Y) constructed from a BHS Hl using any P(Ho),
Rh(h,)
[Re(h)]
E (a.u)~p
[Th, (a. y)].
hmp
Proof sketch. By interchanging expectations over h a and (x, v) ~ p and using the fact that supweB,(a) (u) 1(h(x') # y} = and only if h E Hos(x, v), we first show the following.
E
[h)]
E (#.6)~p
[n( y))]
Arguing from the definition of mm (x, y). we then show that sup En ([(x') max (x. y). Taking expectation with respect to (xx, y) ~ we get,
R. = E [ max vl. (..)))~
(8)
Combining (8) and (7) yields (6).
The following corollary shows that lower bound on the expected matching penny gap is both necessary and sufficient for mixture to strictly outperform any deterministic classifier in Ha- Corollary 3.1. For j P(Hs), R. (hw) < inf R.(h) if and only if the following condition holds.
E [Th, (x. > E [R.)) - inf (h) hmp
(9)
(m.y)mp
hEMo
Additionally, inf in((E)) Re (hy) inlnem, R. (h) if and only if there exists n P(Hss) for which (9) holds.

---

Remark 2 (Multiple optimal classifiers in matching penny configuration), For finite He, the assump- tion (9) of Corollary 3.1 holds whenever there exist two distinct optimal classifiers hi h E H, with positive expected matching penny gap. In such case, the RHS of (9) is zero for any μ that is mixture hi, hz. This is indeed the case in Figure 1b. More generally, assumption (9) holds if there is a subset of classifiers in matching penny configuration that are "near optimal" on average. More details in Appendix C.3.
The following example depicts the scenario of Remark 2 in the extreme case in which there exist infinitely many distinct optimal classifiers in matching penny configuration, leading to the maximum possible advantage of using probabilistic classifiers.
Example 1 (Maximum expected matching penny gap of 1). Consider discrete data distribution 80 = 0,y = 1) and a BHS composed of infinitely many linear classifiers, Hi, {h: h(x)) = 1( x < |1.1]//l |||l
}} where || ||2 is the Euclidean norm. Observe that every classifier in Hs is vulnerable at (æt, v) - (0, 1) and so R. (h) = for all h E Ho. However, no pair is simultaneously vulnerable. Hence, Th, (z, v) = 1 for any distribution
P(H,) that is continuous over the entire support Ho- By Theorem 3.2 we get that R. (h2)) 0 for any such μr. Therefore, any such hy outperforms every h E Hé. and we have details on Appendix C.I.
( R. (h,, < infREи. (h)
More
Remark 3 (Probabilistic classifiers with zero matching penny gap are not useful). Suppose the expected matching penny gap ((s.)))>((Th,, (a,y)] y)] is zero for some μí E P(Hs). Then the left hand side of (9) is zero, whereas the right-hand side Enwyy [R. (h)] - infRem, (h) is always non-negative. Hence, (9) does not hold and so R. (h,-) 2 inf (h). Therefore, any such probabilistic classifier underperforms the best deterministic classifier in the base set Ho.
The following example illustrates scenario described in Remark 3, where we examine classifiers with decision boundaries that are parallel sets [23].
Example (Minimum expected matching penny gap of 0 / Parallel decision boundaries). Fix any binary classifier h X -> {0, }} with non-empty decision region A, = {x E X' h(x)) =1] C X S Rd. Let Hi be composed of all classifiers whose decision regions are r-parallll sets of A,, detined as A = Ap + (0) where @ denotes the Minkowski sum, i.e., Hi = (h Br 2 0 s.t. A% {ar X' h(x)= = 1}}. Because of the parallel decision boundaries, whenever two classifiers in Hi, are vulnerable, they are simultaneously vulnerable, and never exhibit matching penny configuration. Therefore, E(z.a)) Mh, (I, y)] 0 for any μ E P(Hs). More details on Appendix C.2.
Application to RECs and Links with [13]. In the case of RECs where μ Eme(M] Pm pno i.e., h is a mixture of M deterministic classifiers in Hs = (hm) [meM)) we can instantiate Theorem 3.2 as follows. As the family Deeb (2, y) is finite, the supremum p (x, (x,y) y) is always attained by some subset of simultaneously vulnerable classifiers Hore" (I. y). We can then write:
R. (b,,)
Σ Pm (h) Pm mE(M)]
E (a..))<p
1hh E Hus(z, \ H (z. v)
(10)
Alternatively, we can use (8) to write Rh, = =meln))=Eme( Pm B(a,)) 1 (mm E Hmo (z, y)}- At each (x,y). v), testing whether hm E Hme= (x,y) reduces to solving combinatorial optimization problem, as noted in [13]. Any (I, falls into one of finitely many configurations, depending on which subset of classifiers are vulnerable or simultaneously vulnerable at (a, y). Dbouk and Shanbhag [13] use this to derive upper and lower bounds on R. (h,)). Specifically. [13, Proposition
1] is equivalent to (8) for the special case of RECs. Also, [13, Theorem 1] can be proved as an application of Theorem 3.2 to RECs with M = 2. To establish the link, one must note that [( (2r, y)] )((((x,)) v) R)) where R X' y indicates the set of all points where hi, hy are in matching penny configuration.
4 From Probabilistic to Deterministic Classifiers
In this section, we prove that for any probabilistic binary classifier h, there exists a deterministic classifier h in a "threshold" hypothesis set Hr(h) with at least the same adversarial risk. In
7

---

Section 4.1 we present the main theorem and in Section 4.2 we apply the theorem to various classes of probabilistic classifiers.
4.1 Reducing a Probabilistic Classifier to Deterministic One Through Threshold Classifiers
In the case of binary classification, i.e. y = {0, 1} any distribution v E P(Y) is uniquely determined by scalar a pyy = 1) [0. function h : X + [0, 1]. where h(x) v 1 E [o, 1]. Accordingly, ((2, 0), h) = h(x) and e011 ((x, 1), h)
Hence, any probabilistic binary classifier is identified with
h(x)).
Given a probabilistic binary classifier h X > [0, 1] and a threshold a E [o, 1]. the a-threshold classifier ht X' {0,1} is defined as h² (z) (((()) > a), and the threshold hypothesis set (THS) of is given by (h) = {1a Jae In Theorem 4.1 we show that there exists ha. E Hr(h) such that R. (1(*)) S R. (h). The following lemma plays a crucial role in proving Theorem 4.1.
Lemma 4.1. Let h - (0, 1] be any measurable function. For any > (>,2), the following inequality holds, and it becomes an equality if h continuous or takes finitely many values:
I sup (E)
h(zz)) x +a3²
sup 1(b(r') > a} x' (t),(()
(11)
Note that Lemma 4.1 a generalization of the layer-cake representation of h(r) given by.
h(z) = J. (h(x)) adda L. 1(b(x) 2 aa
Theorem 4.1. Let h : X + [0, 1J be any probabilistic binary classifier. Let ha be the a-threshold classifier. Then the following equation holds:
R. (h) 2 =f [_ 2 inf R. (h").
(12)
a
Further, if h is either continuous or takes finitely many values, the first inequality in (12) becomes an equality.
Note that h takes finitely many values in the case of RECs, and h is continuous in the case of INCs
and WNCs whenever the noise distribution admits density. Hence, R. (h) Jo' R. (h in all these cases.
Remark 4. Theorem 4.1 says that in the binary case (K = 2), one is able to consider complex enough hypotheses sets that contain the Hr)h), then randomization is not necessary because there is a deterministic classifier with equal or better adversarial risk.
It was very recently shown with a toy example [45, Section 5.2] that Theorem 4. 1 does not hold in the multi-class case K > This example shows that even when the family of probabilistic classifiers considered is very general (all Borel measurable functions), simple data distributions can create situation in which the optimal classifier probabilistic, and there is no optimal deterministic classifier. In other words, there is a strict gap in adversarial risk between the best deterministic classifier and the best probabilistic one.
4.2 Applications: Connections to Weighted Ensembles and Randomized Smoothing
In this section, we apply Theorem 4.1 to probabilistic classifiers presented in Section 2.3.
RECs. When f Emelar Pmon... and
1), the REC h, be written h (2r) DM Pm Let introduce the constant classifier ho ho(xr) K
for all x, and po ha (z) = 1|>K= hm (x) > a} = 1 P hm (x) > 0}. This shows that ha is weighted ensemble, such as those that the boosting algorithm can learn [17].
Then
Further, REC h built with M base binary classifiers can take at most p S 2M distinet values, corresponding to all possible partial sums of the weights Pm. Let 0 ri < ... S Tp 1 be
8

---

the possible values. Then, for any E (11))) h² = h3. Applying Theorem 4.1 yields,
R. (h) = -[0 R. = E) r+t
p-1
Re Re(h")da - ( ri)
(13)
Equation (13) shows that the THS (h) )ne) Joe is composed of at most p S 2 distinet classifiers, each of which is in turn a weighted ensemble. In case of uniform weights i.e. Pm 1 there are only M distinct weighted ensembles in (k).).
INCs. Let hy base classifier h, defined in Section 2.3. The probabilistic classifier h, is defined as (x) Py-a(h(æ + 11) = 1). Thus, the a-threshold classifier takes a similar form to the well-known classifier obtained by randomized smoothing.
+ {0.1} be the deterministic binary classifiers created from a
ho (x) IP =))===) 1y-ay
(14)
Randomized smoothing was first introduced in [26] and refined in [8. 27, 42] as way to create classifiers that are certifiably robust. Given a deterministic classifier / : X' + y and noise
distribution μ E PP))), the smoothed model will output prediction according to the following rule:
h = argmax Pro (h(r + 1)) = -) = 1 {1 (Pr~a (h(x + n) = } yEy
(15)
In other words, Equation (14) generalizes the randomized smoothing classifier in the binary case by replacing the 1 threshold by a. Theorem 4.1 then states that for any INC, there exists a deterministic randomized smoothing classifier with threshold that is at least robust.
Families of Binary Classifiers for Which Randomization Does not Help
In Sections and 4, we discussed two types of hypothesis sets for binary classification: 1) base set Hs from which probabilistic classifier is built using some μ E PPHss), and 2) threshold set Hr(h) which is built from a base probabilistic classifier h. Recapitulating this two-step process, one may define the completion of a base set Hs of binary classifiers w.r.t. a set of probability distributions M S P(H)) as, (M(M) = Mu (bw)) Observe that Ho S (P()))))). In the following theorem, we show that if Hs HMM,), then probabilistic binary classifiers built from Hi using any y M do not offer robustness gains compared the deterministic classifiers in Hs.
Theorem 5.1. If Ho Ho(M) and Ōū E M for all h E Ho. then inf R. (h) in Re (hy).
=
Proof.
inf (.
(h) = inf inf R.(h) JEM (rr
< inf R. (b,,) WEM
S inf R. (h), NE
(16)
where the first inequality follows from Theorem and the second by considering μ = 8, for any h E Hs. The desired conclusion follows by observing that the first and last terms in (16) are identical from the assumption H,, = (M).
trivial example where the assumptions of Theorem 5.1 hold when H, is the set of all measurable
functions : X' - {0. 1}. Such a Hr, is commonly used in the study of optimal adversarial risk [2, 40]. In the following corollary, case of RECs built using Hr that satisfy "closure" property.
show that the assumptions of Theorem 5.1 also hold in the
Corollary 5.1. Let Hr be any family of deterministic binary classifiers. Let M = PM (Hi) C P(H))) be the subset of probability measures H4 defining RECs as in Section 2.3. Let A (1) h Ho) }. If A is closed under union and intersection, then
inf (e = inf heWo
R. (h,).
μεP (Hs)

---

the existence of binary deterministic classifier attaining the minimum adversarial risk over the space of all Lebeggue measurable classifiers in Rd. Awasthi et al. |2, Theorem 1] prove similar result over the space of universally measurable classifiers in Rd. For both these families the assumptions of Theorem 5.1 hold for M = P(H)), and so probabilistic classifiers offer no additional advantage over deterministic ones. Further, suppose H is a finite subset of classifiers achieving optimal adversarial risk. Then by Theorem 3.2, for any μ E P(H"), the expected matching penny gap for h, must be zero, otherwise we could strictly improve the adversarial risk by considering the mixture built using μ. In other words, any pair of optimally robust binary deterministic classifiers in the settings of [2, 40] can only be in a matching penny configuration on a null subset E C X x V. Remark 5 (Implications on the optimal adversarial classifier). Pydi and Jog [40. Theorem 8] show
Conclusion and Future Work
In this paper, we have studied the robustness improvements brought by randomization. First, we studied the situation in which one expands base family of classifiers by considering probability distributions over it. We showed that under some conditions on the data distribution and the configu- ration of the base classifiers, such a probabilistic expansion could offer gains in adversarial robustness (See Corollary 3.1), characterized by the matching penny gap. These results generalize previous work that focused on RECs [13]. Next, we showed that for any binary probabilistic classifier, there is always another deterministic extension with classifiers of comparable or better robustness. This result linked with the existence results in [2, 40]. As a direct consequence of this result, we show that in the binary setting, deterministic weighted ensembles are at least as robust as randomized ensembles and randomized smoothing is at least as robust as noise injection.
There are many avenues for future research.
Improving the Matching Penny Gap. An interesting direction would be finding tighter bounds on the matching penny gap for particular and widely used probabilistic classifiers like RECs, INCs and WNCs. It would be interesting to establish the conditions under which each method can offer robustness gains, and to quantify those gains in terms of parameters such as the strength of the noise injected or the number of classifiers in the REC.
Studying the Threshold Hypothesis Sets. We have seen in Section 4.2 that different probabilistic classifiers induce different THS. In particular, we showed the THS corresponding to RECs and INCs. would be useful to formally describe the THS induced by other popular families of probabilistic classifiers in the literature. It would also be useful to quantify the complexity gap between the initial Hs and the THS to understand the risk-complexity trade-off we would have to incur.
Multiclass Setting. The toy example in [45, Section 5.2] shows that randomization might be necessary in the multi-class setting, as it is no longer true that there is always a deterministic optimal classifier, even when considering very general families of deterministic classifiers like all measurable functions. A natural road for future work to further characterize the situations in which probabilistic classifiers strictly outperform deterministic ones in the multi-class setting.
Training algorithms for diverse ensembles and RECs. There numerous works based on the idea of training diverse classifiers that are not simultaneously vulnerable to create robust ensembles [11,24, 33, 49,149,000 Most of these approaches try induce orthogonality in decision boundaries so that gradient- attacks do not transfer between models. This intuition is validated by Corollary 3.1, since such diversification would tend to increase the matching penny gap. It should be noted that ensembles and RECs have different inference procedures. and attacking them represents different optimization problems. One avenue of research would be make the link between the matching penny gap and the diversity more formal. In addition, designing training algorithms explicitly optimizing the matching penny gap would be valuable, particularly because existing training algorithms for RECs [31, 38] have been shown to be inadequate [12].
7 Acknowledgements
This work was funded by the French National Research Agency (DELCO ANR- 19-119--22-0011))
10

---

References
[1] Pranjal Awasthi, Natalie Frank, and Mehryar Mohri. On the existence of the adversarial bayes classifier. Advances in Neural Information Processing Systems, 34:2978-2990 2021.
[2] Pranjal Awasthi, Natalie S Frank, and Mehryar Mohri. On the existence of the adversarial bayes classifier (extended version). arXiv preprint arXiv:2112.01194, 2021.
[3] Battista Biggio, Igino Corona, Davide Maiorca, Blaine Nelson, Nedim Šmdić, Pavel Laskov, Giorgio Giacinto, and Fabio Roli. Evasion attacks against machine learning at test time. In Joint European conference on machine learning and knowledge discovery in databases, pages 387-402. Springer, 2013.
[4] Chris M Bishop. Training with noise equivalent tikhonov regularization, Neural computa- tion, 7(1):108-1 16,, 1995.
[5] Nicholas Carlini and David Wagner. Adversarial examples are not easily detected: Bypassing ten detection methods. Proceedings of the 10th ACM workshop on artificial intelligence and security, pages 3-14, 2017.
[6] Nicholas Carlini, Anish Athalye, Nicolas Papernot, Wieland Brendel, Jonas Rauber, Dimitris Tsipras, Ian Goodfellow, Aleksander Madry, and Alexey Kurakin. On evaluating adversarial robustness. arXiv preprint arXiv: 1902.06705, 2019.
[7] D Charalambos and Border Aliprantis. Infinite Dimensional Analysis: A Hitchhiker's Guide. Springer-Veree Verlag Berlin and Heidelberg GmbH & Company KG, 2006.
[8] Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. In International Conference on Machine Learning, pages 1310-1320. PMLR, 2019.
[9] Yves Crama and Peter I. Hammer. Boolean functions: Theory, algorithms, and applications. Cambridge University Press, 2011.
[10] Francesco Croce and Matthias Hein. Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attacks. In International conference on machine learning, pages 2206-2216. PMLR, 2020.
[11] Ali Dabouei, Sobhan Soleymani, Fariborz Taherkhani, Jeremy Dawson, and Nasser M Nasrabadi. Exploiting joint robustness to adversarial perturbations. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 1122-1131, 2020.
[12] Hassan Dbouk and Naresh Shanbhag. Adversarial vulnerability of randomized ensembles. In International Conference Machine Learning, pages 4890-4917. PMLR, 2022.
[13] Hassan Dbouk and Naresh Shanbhag. On the robustness of randomized ensembles to adversarial perturbations. In International Conference on Machine Learning, pages 7303-7328. PMLR, 2023.
[14] Guneet S. Dhillon, Kamyar Azizzadenesheli, Zachary C. Lipton, Jeremy Bernstein, Jean Kossaifi, Aran Khanna, and Animashree Anandkumar. Stochastic activation pruning for robust adversarial defense. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30- May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018. URL htttss:/oppnrte
[15) Dimitrios Diochnos, Saeed Mahloujifar, and Mohammad Mahmoody. Adversarial risk and robustness: General definitions and implications for the uniform distribution. Advances in Neural Information Processing Systems, 31, 2018.
[16] Natalie S Frank and Jonathan Niles- Weed. Existence and minimax theorems for adversarial surrogate risks in binary classification. arXiv preprint arXiv:2206.090: 09098, 2022.
[17] Yoav Freund, Robert Schapire, and Naoki Abe. A short introduction to boosting. Journal- Japanese Society For Artificial Intelligence, 147711-780):1612. 1999.
[18] Drew Fudenberg and Jean Tirole. Game theory. MIT press, 1991.

---

[19] Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and hamnessing adver- sarial examples. In Yoshua Bengio and Yann LeCun, editors, 3rd International Conference on Learning Representations, ICIR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015. BtRlhttt:///axii www.aawwww.w...aaaa.....eeooooee //s///b///// ha////as///11...... 1tt.//112...2...
[20] Pascale Gourdeau, Varun Kanade, Marta Kwiatkowska, and James Worrell. On the hardness of robust classification. The Journal of Machine Learning Research, 22(1):1251111254, 2021.
[21] Yves Grandvalet, Stéphane Canu, and Stéphane Boucheron. Noise injection: Theoretical prospects. Neural Compulation, 955):0033-1100 1997.
[22] Zhezhi He, Adnan Siraj Rakin, and Deliang Fan. Parametric noise injection: Trainable random- ness to improve deep neural network robustness against adversarial attack. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pullern Recognition, pages 588-597, 2019.
[23] Varun Jog. Reverse euclidean and gaussian isoperimetric inequalities for parallel sets with applications. IEEE Transactions on Information Theory, 67(10))6368-6383, 2021.
[24] Sanjay Kariyappa and Moinuddin K. Qureshi. Improving adversarial robustness of ensembles with diversity training. CoRR, /etp//901.0998// 2019. URL http:://rxiii /ttp//aavv..rraa////0a/a 09981.
[25] Alexey Kurakin, Ian Goodfellow, and Samy Bengio. Adversarial machine learning at scale. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017. URL httpp://opperrevie.. www..eeeeooommmddddd/da//aea.00
[26] Mathias Lecuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified robustness to adversarial examples with differential privacy. In 2019 IEEE Symposium on Security and Privacy (SP), pages 656-672. IEEE, 2019.
[27] Bai Li, Changyou Chen, Wenlin Wang, and Lawrence Carin, Certified adversarial robustness with additive noise. Advances in neural information processing systems, 32, 2019.
[28] Xuanqing Liu, Minhao Cheng, Huan Zhang, and Cho-Jui Hsich. Towards robust neural networks via random self-ensemble. In Proceedings of the European Conference on Computer Vision (ECCV), pages 369-385, 2018
[29] Keane Lucas, Matthew Jagielski, Florian Tramèr, Lujo Bauer, and Nicholas Carlini. Ran- domness in ml defenses helps persistent attackers and hinders evaluators. arXiv preprint arXiv:2302.13466 2023.
[30] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018. URL https: / net/ forum?id=xJzIBfZM
[31] Laurent Meunier, Meyer Scetbon, Rafael Pinot, Jamal Atif, and Yann Chevaleyre. Mixed nash equilibria in the adversarial examples game. In International Conference on Machine Learning, pages 7677-7687. PMLR, 2021.
[32] Seyed-Mohsen Moosavi-Dezfooli, Alhussein Fawzi, Jonathan Uesato, and Pascal Frossard. Robustness via curvature regularization, and vice versa. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 9088, 2019.
[33] Tianyu Pang, Kun Xu, Chao Du, Ning Chen, and Jun Zhu. Improving adversarial robustness via promoting ensemble diversity. In International Conference Machine Learning, pages 4970. PMLR, 2019.
[34] Konstantinos Panousis, Sotirios Chatzis, Antonios Alexos, and Sergios Theodoridis. Local competition and stochasticity for adversarial robustness in deep learning. International Conference Artificial Intelligence and Statistics, pages 3862-3870. PMLR, 2021.
12

---

[35] Konstantinos P Panousis, Sotirios Chatzis, and Sergios Theodoridis. Stochastic local winner- takes-all networks enable profound adversarial robustness. arXiv preprint arXiv:2112.02671, 2021.
[36] Juan C Perdomo and Yaron Singer. Robust attacks against multiple classifiers. arXiv preprint arXiv: 1906,02066,6 16, 2019.
[37] Rafael Pinot, Laurent Meunier, Alexandre Araujo, Hisashi Kashima, Florian Yger, Cédric Gouy- Pailler, and Jamal Atif. Theoretical evidence for adversarial robustness through randomization. Advances Neural Information Processing Systems, 32, 2019.
[38] 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, pages 7717-7727. PMLR, 2020.
[39] Rafael Pinot, Laurent Meunier, Florian Yger, Cédric Gouy-Pailler, Yann Chevaleyre. and Jamal Atif. On the robustness of randomized classifiers to adversarial examples. Machine Learning, 111(9):3425-3444 3457, 2022.
[40] Muni Sreenivas Pydi and Varun Jog. The many faces of adversarial risk: An expanded study. IEEE Transactions on Information Theory, pages 1-1, 2023. doi: 10. 00011099/7112223333332111
[41] Andrew Ross, Weiwei Pan, Leo Celi, and Finale Doshi Velez. Ensembles of locally independent prediction models. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 5527-5536, 2020.
[42] Hadi Salman, Jerry Li, Ilya Razenshteyn, Pengchuan Zhang, Huan Zhang, Sebastien Bubeck, and Greg Yang. Provably robust deep learning via adversarially trained smoothed classifiers. Advances Neural Information Processing Systems, 32, 2019.
[43] Christian Szegedy, Wojciech Zaremba, llya Sutskever, Joan Bruna, Dumitru Erhan, Ian J. Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In Yoshua Bengio and Yann LeCun, editors, 2nd International Conference on Learning Representations, ICLR 2014, Bansf, AB, Canada, April 14-16, 2014, Conference Track Proceedings, 2014. URL http://arxiv. .rgg hbsp///s/111111 6199.
[44] Nicolas Garcia Trillos, Matt Jacobs, and Jakwang Kim. On the existence of solutions to adversarial training in multiclass classification. arXiv preprint arXiv:2305.00075. 2023.
[45] Nicolás Garcia Trillos, Matt Jacobs, and Jakwang Kim. The multimarginal optimal transport formulation of adversarial multiclass classification. Journal of Machine Learning Research, 24 145):1-56, 2023.
[46] John Von Neumann. On the theory of games of strategy. Contributions to the Theory of Games, 4:13-42, 1959.
[47] Bao Wang, Zuoqiang Shi, and Stanley Osher. Resnets ensemble via the feynman-kat formalism improve natural and robust accuracies. Advances Neural Information Processing Systems, 32, 2019.
[48] Cihang Xie, Jianyu Wang. Zhishuai Zhang, Zhou Ren, and Alan Yuille. Mitigating adversarial effects through randomization. arXiv preprint 1711v:1711.0099) 2017.
[49] 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:5505-5515, 2020.
[50] 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, 14:17642-17655 2021.
13

---

[51] Tianyuan Yu, Yongxin Yang, Da Li. Timothy Hospedales, and Tao Xiang, Simple and effective stochastic neural networks. In Proceedings of the AAAI Conference on Artificial Intelliencee pages 3252-3260, 2021.
[52] 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 of Proceedings of Machine Learning Research, pages 26669-26692. PMLR, 17-23 Jul 2022.
14

---

Supplementary Material
Appendix A Measurability of the e0-1 under attack
In this section, we will go the conditions that ensure the well-definedness of the adversarial risk defined in (1), We will show that the assumptions we make are verified in the settings that are of interest to work. We highlight that the main purpose of this paper is not to deeply study the existence of measurable solutions to the adversarial problem, as was done in previous work [1, 40, 44]. In this work, we allow ourselves to add hypothesis on the input space A' and the families of classifiers Hy that we consider, as long as they are valid in practice.
A.1 Discussion
Recall that in our setting we have the following. The input space X' is some subset (almost always bounded or even compact) of R y [K] and P(Y) = = On the other hand, for all the applications of interest to work, we consider base hypothesis sets Ho that either finite or discrete (for randomized ensembles), or identifiable with subsets some IP (for weight and input noise injection). For all these sets, assume the usual topology and the Borel o-algebra that is generated by the open sets. We further assume that X' and Hs are Borel spaces, which is not restrictive. It allows, for example, any open closed set of R". which already encompasses all practical applications of interest. This hypothesis makes it simpler to work on the product measure space X' x Ho.
In the adversarial attacks literature, the question of measurability is always with respect to [2, 40]. For a deterministic classifier h X' y [K] to be measurable, the sets h ( must be measurable. In other words, each classifier / creates a K K-partition of X into measurable subsets (1) A (K). This immediately translates into the (0-
function of æ, being measurable, because (-1 ((- y). (() = fi E X h(x) + y} = X' \ h- (t). In other words, assuming classifiers measurable functions translates into measurability of the 0-1 loss, so the arguments in previous work [1, 16, 40] can be used to justify that the adversarial risk is well-defined.
We introduce new component, the BHS Hr. and we now compute integrals over it. For this reason, we now consider more general functions of the form f : X' x Ho -> (0. 1). fxx,
(h(x) # y} (1(x)) + y} becomes the same
and study their measurability. one fixes h, the function fd (x) 0-1 loss considered earlier, so assuming every h is measurable function translates into the fact that is measurable w.r.t. x for every fixed h. The new part we have to deal with is the measurability of f w.r.t h for every fixed rr
As first example, let us consider the case of linear classifiers. In this case, classifier h can be represented as a K x matrix A with the classification rule h(x)) argmax, (Ax),. meaning classifies x using the with higher score. In this case, can directly see the measurability of in each component (fth and fz) by looking at the pre-images of 1, which are the sets that induce an error (recall y fixed). For fh, the pre-image the set of a E X such that h(x) + y. This can be seen as the complement of the set X,, in which predicts
(f*)- {x X h(x) + y} f- E X h(x) y] = X
The set X,, is described by K 1 linear equations using the rows aj of the matrix A that defines the linear classifier h, follows
X, = (x EX of a. Vj *
This is the finite intersection of hyperplanes, thh is measurable on X' for any h linear classifier.
Borel measurable, and therefore the function
For the measurability of f", have to consider the set Hy of classifiers that produce prediction of y for fixed x. Let us recall that each classifier is represented by matrix A R Kxd then
Hg (h Ho Mxx) v) (A e R K xd
a
a.
Vj + y4
Hy a convex cone, because if A, B E Hy, then for a positive a, a.A H, and A + E Hy. This set is therefore measurable, and conclude that gr is measurable for every x.
15

---

When considering neural networks with weights parametrized by we can think of them as non- linear functions plus last linear layer as the one described earlier. Then, if the non-linear function is continuous w.r.t both and w, the function we are considering is again measurable w.r.t to and w.
In summary, all the situations that are of interest a product space R x Rr, and it has good properties when seen as functions of x or h separately (measurable, continuous or differentiable). These separately measurable functions [7, Definition 4.47] might not be jointly measurable, i.e. measurable on the product space, which is one condition that would grant us the dell-definedes of (1). Nevertheless, we can make use of the stronger properties these functions have and assume they are Carathéodory functions [7, Definition 4.50J. This will imply the joint measurability of f. For completeness, we rewrite the results from [7]:
work verify that the function f is defined over
Definition 2 (Carahéodory function [7. Definition 4.50)), Let (S, Σ) be a measurable space, and let X and Y be topological spaces. Let By be the Borel o-algebra on Y. A function f SS X is a Carathéodory function if:
For each E X, the function === S + Y is B
* For each s S, the function f = f(s .) : X + Y is continuous.
As we have seen, the functions f : X' H4. R consider be assumed to be Carthéodory functions, as they are in general differentiable or continuous in both components. Even going away from practice, in theoretical works it is usual to consider classifiers h X - A as Borel measurable functions from X, and adding the assumption of continuity w.r.t h for every fixed æ it not restrictive (for example neural networks with continuous activation functions [31]).
Lemma A.1 (Carahéodory functions are jointly measurable [7, Lemma 4.51J). Let (S. Σ) be a mea- surable space, X separable metrizable space, and Y a metrizable space. Then every Carathéodory function f S x X + Y is jointly measurable
A.2 Conclusion
If we assume the hypotheses of Lemma A.I, that is
1. We assume that for every component y. the function f X' x Hd + {0, defined as f(x, h) = 11((())++()))))))())(()) # y} is a Carathéodory functioon,, which translates in our case into:
Each h Hs, h measurable function on X' (very common assumption). f(x,1) h) is continuous (not
For each x, the function fz Hr {0, 1). f²
unrealistic, satisfied by neural networks with continuous activation functions)
2. The input space X is a measurable space (satisfied by hypothesis, X C R2d some Borel set).
3. The base hypothesis set Hg is a separable metrizable space (valid when Hs is a Borel subset of TRP).
4. The output space {0, 1} is a metrizable space (satisfied).
then, by Lemma 1, the function f is jointly measurable.
By Fubini- Tonell'ssssl'''s Theorem, the function x - JHs f(x, h)dp(h) is mcasurable on X. Then, following the same arguments as in [1, 16), the loss under attack can be defined and measurable over the universal o-algebra (x') on X. Then, considering ((2'), the adversarial risk is well-defined as it is an integral over X' using the completions of the class conditioned measures Py over U(X)) (see (I)).
Appendix B On the name Matching penny gap
In the original matching penny game between player (attacker) and player (defender), each player has penny coin and has to secretly position its penny in either heads or tails. Then, both coins are simultaneously revealed and the outcome of the game is decided as follows: attacker wins both pennies match. If they do not match, then def endender wins. This situation can be represented using the following matrix (attacker wants to maximize), where heads and tails have been replaced by fi and fe for reasons that will be explained later:
16

---

Attacker
Defender
fi
f2
f1
0
f2
0
1
This game has no Pure Nash Equilibrium. has, however, a mixed Nash equilibrium which consist of the strategies (2 2) for both players [18]. In the context of the matching pennies game, this can be seen as the strategy in which players toss the coin obtain either heads or tails uniformly at random (assuming the coins are fair) instead of choosing can be sure that, on average over multiple realizations of the game, they will win half of the times each. The fact that it is Nash Equilibrium means that, if one player deviated from this strategy, the other player could find way to win more than half the times. To see this, imagine that the def enderder player plays heads with probability 2 5. Then, if attacker knew this, he could play the strategy always heads. Then, from all the realizations of the game, with probability 2 + 6 the coins would be both on the same side (heads), meaning attacker would win of the times, gaining 8 w.r.t the equilibrium strategy.
of the sides. Using this strategy, each player
The parallel with work can be simply explained follows (see Figure 2): Take point (on, yo) and two classifiers /2 that correctly classify z0- Suppose that both fi and f2 are vulnerable at æo. which is represented by the colored areas Figure 2. However, add the key assumption that they cannot be attacked at the same time, which is represented by the fact that the colored areas do not intersect inside the e-ball around To. That is, even though an optimal attacker can fool each
fi
TD
f2
Figure 2: Example of classifiers a matching penny configuration around point zo-
classifier individually, there is point in the allowed perturbation region (xo) in which both simultancously fooled.
Consider now that the defender is using a randomized ensemble that picks either fi or f2 at random for inference. This was introduced in [38] with the name mixtures of classifiers, related to mixed strategies in the context of game theory. In such setting, the optimal attacker that faces such mixture now matching pennies game situation. At each inference pass, the attacker must choose which classifier to attack in order to craft the adversarial example x', and if the chosen classifier matches with the one the defender used, then the attacker wins. they do not match, the prediction made by the defender will be correct and the attacker would have lost. This is exactly the game of matching pennies!
What is particularly worse for defender is that, in the traditional formulation of adversarial attacks, the attacker is given the chance play second and therefore can adapt to the classifier. In other words, attacker can craft its perturbation for the particular classifier proposed by defender, while defender has to propose a classifier that should be robust to every conceivable attack. This means that if defender uses f1 or f2 individually, then attacker would be able to craft an attack that induces an error. In this situation, and inspired by the game of matching pennies, defender can turn these two strategies, that have 0 robust accuracy by randomizing over fi and f2. Recall that attacker is optimal for any fixed classifier, but it has no control over randomness, which means that when faced against
their own, into strategy that guarantees
an expected accuracy of 2
17

---

mixture of fi and f2, attacker can compute any perturbation ó from them, but he has no knowledge of which classifier will be used for each independent inference pass. This can be interpreted as follows: for a given inference run, there is a chance of that the perturbation proposed by attacker indeed an adversarial attack and induces an error.
Notice that if we increase the number of choices (classifiers) in matching pennies' configuration to M > 2. the game becomes harder for the attacker. Indeed, for every possible choice of classifier at each inference pass, there is one out of M choices that lead to successful attack (attacking the one that was sampled for the inference pass), and M that lead to a correct classification. An extreme example of such benefit to the defender is shown in Example 1.
Appendix C Details on the examples and remarks
C.1 Example 1: Maximum mathing penny gap
Note that for this example, each classifier w satisfies that w x = O, and therefore 1( x < 1) = which means that all predict the correct label for the clean input x. Now we want to see that every w is vulnerable at æ.
We can rewrite this norm dual norm ||w||2 = w 2. Moreover, this supremum is attained by some 2w. so for each we get zn of norm 1, such that w Zm
Recall that we defined Hy as the space of linear classifiers w such that ||l||2 1
W
C Zm
(x, 1)
Figure 3: Visualization of Example 1. Best viewed in color. Here w is of the linear classifiers considered in H4. For the budget 6, there is exactly one point e 2w of intersection between the c-ball around (xr, 1) and the hyperplane defined by the equation w x wTx x: 2 are classified as This includes this half-space. That is why e zu is the only adversarial attack that can fool w, and it cannot fool any other w/ # w.
All the points in the half-space 2n, and this is the only point in the c-ball that belongs
Now, for each w E Hi, consider the adversarial example e 2w. It is valid adversarial ex- meaning that the classifier predicts 1(w" (E zw) < 1} 0, the wrong class. The next step is guarantee that this perturbation is unique for each w, which holds because we are using the Euclidean norm.
ample because it has norm e, and w (e 2n))
Having that Zu fools w and only w, over Hg. Let us compute the sets Hos 1) and mm penny gap for this example.
consider for simplicity μ the uniform distribution
(x. 1) = 0 to be able to compute the matching
As we just saw, every w is itself vulnerable. This means that Hns(x, 1) Hs. and therefore u(Hus(I, 1)) = 1.
18

---

Given the unicity of 2w, we know that no two classifiers can be fooled by the same perturbation. Therefore the family of simultaneously vulnerable classifiers only contains singletons {w). As (((w)) = 0 for every w, taking the supremum gives y= (z, 1) 0.
Finally, expected the matching penny gap for this example with only one point
Ah 1)] Th, (z, 1) = (o, 1)) م max (z, 1) 1- 2.y
E
In other words, the mixture in this example has the best adversarial risk possible, even though is built from classifiers with the worst adversarial risk possible individually.
C.2 Example 2: Minimum mathing penny gap Parallel sets
To simplify the example, consider the compact set A {0} R. Then, the family of all parallel classifiers h, = A < (0) are the classifiers of the form (x) = 11 fa E (-r,r)) for orr >
Recall that a matching penny configuration arises when 1) both classifiers are vulnerable, but 2) not simultaneously. That is, each one of them must be vulnerable, no allowed perturbation can induce error on both at the same time. We will see that this cannot happen with this family of classifiers that are "parallel".
W.l.o.g, take any point x > O and suppose it is of class is 0. Take any two classifiers hy hy with r1 T2 and fix the attacker budget is, the attacker must be able to move æ inside (-r, with its budget of e. This also holds for hy
Note that hr, is vulnerable at x an only if x e S r1- That
Note that to satisfy the condition that both classifiers vulnerable, we must ensure that and x c S r2- However, any x that satisfies x c S T1 immediately satisfies x - c S r2. as both classifiers. In conclusion, they
T1 72, meaning that the same perturbation induces cannot be both individually vulnerable without being simultancously vulnerable at x.
A'a
AT
h1
hg
f2
(a) Example of parallel classifiers in R
(b) Example of parallel classifiers in IR2
For the case of general parallel sets A", A"a A",, note that r r2 then A Th Assuming that the classifiers predict if the point is inside the set A", then the condition both classifiers are vulnerable means that point of class 0 is at distance of most from both A A²= However, for any given being e-close to Ar implies that x is e-close to A"2, so any adversarial example of 4 will be also adversarial for A In conclusion. they can never in a matching penny configuration.
C.3 Multiple optimal classifiers in matching penny configuration
In this section, we are going to explain in more detail Remark 2, First, we rewrite Equation (9) which states the condition under which mixture outperforms the individual classifiers composing it:
E
[Th (xx,
E (h)) inf Rh(
(m.y)~p
kmp
hERs
For simplicity, assume Ho consist of two different classifiers hy, h2 with the same adversarial risk and with strictly positive matching penny gap. i.c. E(ax) [Tr (z, y)] > for some
19

---

== (j(h1), p(h2)). Then the REC h that consists of these two classifiers will outperform each one of them. This is because the LHS of equation (9) is positive, while the RHS is exactly 0 because both classifiers have the same risk, so their average risk is equal to the best risk among them. If we add the assumption that b1 and h2 were optimal deterministic classifiers from larger family He. we would have created a mixture that outperforms all classifiers in it.
If now we try soften the assumptions on h1, f2, and say that they have very similar adversarial risks, ie. R. (h2) = Re (h1) + 5 for some small 6, then the RHS of (9) is no longer 0 but g. In this case, for condition (9) to hold we need the matching penny gap to be not only strictly positive, but greater than 1
The important intuition is that mixing classifiers that have very different adversarial risks is not ideal, as one will then need much greater expected matching penny gap order actually outperform the best individual classifier. Another interesting intuition is that one can create a good mixture from very bad classifiers, as was seen in Example where individual classifiers had adversarial risk of (the worst possible), but mixing them resulted in an adversarial risk of 0 (the best possible). Even if Example is merely toy example, it highlights the intuition that it is possible for many non-robust classifiers to gain robustness mixture if they interact nicely between them and the dataset (have high expected matching penny gap).
C.4 Example with linear classifiers: Mixtures can improve robustness (Figure 1b)
33
+
fi(x) =1
fe(1) =1
f(()= 0 fa(z)
Figure 5: The mixture of fi and f2 with uniform weights has lower adversarial risk than any linear classifier, motivating the use of mixtures as robust alternative.
C.4.1 Detailed description of the example
Here is the exact description of the example that was introduced in Figure 1b. We will use
colors to simplify the distinction between points. The points have the following coordinates:
sn = (0, 1).42 22 = (-2.7, 1,),,33 = (2.7, 1.1), x4 = (0. 2). For this extended analysis, it will be
casier to work with classes in {-1, 1). so we have labels yı = 1 and y2 ys = y4 -1. We set == 1.
Let f = b) be generic linear classifier in IR, where of the hyperplane and b is the bias term. The classification is done using the rule sign(f(=)) =
(w1, W2) is the normal vector
sign(w" x + b). in standard binary classification with labels {-1,
In this setting, point (x,y) v) E R² x (-1,1} is correctly classified y f(x) > 0. Moreover, for linear classifiers, the optimal adversarial perturbation is known and robustness at point can be easily studied. Note that given perturbation 8, we can check if it induces a misclassification by simply computing y
fz (z= + 6). We can say f is robust at (z, y) if, for every perturbation of norm at most
20

---

we have that f((x + 6) > 0. This can be developed to get
y f(x + 0) 0 v(w" (or +0) 20
y(w x + + +y 00
(17)
y(w" x + b) > y u
For f to be robust at (z, y). Equation (17) must hold for all 6, in particular for the quantity maximizing Inserting this worst perturbation, we obtain simple
the RHS. This happens for 8 - - condition for robustness the linear case:
[
y( x b) ||
(18)
Without loss of generality, can use these inequalities to show that no linear classifier can be robust at 01, 22 and 24 at the same time. Indeed, being robust at each point gives the following inequalities:
assume w has norm the last equation further simplifies. We
W2 + b
b > 1- 02
T2 2.7w1 1.1w2 - b>1
b < 2.7w1 1.1
(24)
2w² - b>b
b < 2002 -
Using the inequalities for 2 and 24, get the condition w2 T2 gives that 2.7w, 0.1w; > 2. Together with the bound W2. get the bound wi These two bounds make it impossible for w to have norm 1, contradicting our hypothesis. An analogous reasoning shows that linear classifier can be robust Ii, 2g and 244 at the same time.
Using the incqualities for æ1 and
Knowing that a linear classifier can't be robust at Ø 22 and 24 simultaneously. we can further ask what is the best adversarial risk one get. One can casily check that it is possible to be robust on any of the pairs (æ1, 22), (I2, F4) or (1,22)) At each time, robustness on the two selected points comes at the expense of non-robustness robust at the pair (I22, T4), because being non-robust at 21 implies a risk of 1 2. way higher than the risk of one would have to pay for being non-robust at or I4. With this being said, the other two solutions are optimal in terms of adversarial risk for linear classifiers, with an adversarial risk of 1 Nevertheless, for building robust mixture, only one of them will be useful.
the third point. This fact discards the strategy of being
C.4.2 Matching pennies situation.
In order to show that the matching pennies situation exist 2', the simplest thing is to propose two linear classifiers for which it happens. We propose the following linear classifiers:
f1 (w1, b1) with wi = (0.825, 0.565132728) and bı 0.536876091.
f2 (W2, b2) with w2 0.825, 0.565132728) and b2 0.536876091.
Using Equation (18) one can check that these classifiers match the situation that is illustrated in Figure 5, Lee. they are both robust 1T, they are robust at 23 and 2i respectively, they are non-robust at va but they can't be attacked on the same region, their intersections with the 1-ball around .a are disjoint (gray circular sectors Figure 5). Let us denote the REC Si and f2 with probabilities (2:4 2)
C.4.3 Adversarial risk calculation for the mixture of fi and fz.
For T2, Ji is not robust, meaning its adversarial 0-1 loss on D2 is 1. On the other hand, f2 is robust on T2, perturbation of norm at most will make it predict the wrong class. For these reasons, the adversarial 0-1 loss on 22 for h is J. The same goes for Ø3, and therefore they each add I T to the
total adversarial risk (mass of each point times the 0-1 loss).
At the point Zig, given the matching pennies situation, the adversarial 0-1 for is 3. for a total adversarial risk of 12. As both fi and f2 are robust on T1, the adversarial risk on 0y is O, and we can conclude that the total adversarial risk of h is 3 = 1 12
1
4. which is less than the optimal adversarial
risk when considering linear classifiers only, that is 3
21

---

C.5 On the toy example in Trillos et al. [45, Section 5.2]
The example shown in Trillos al. [45, Section 5.2] involves three points of different classes. We are interested in Case 4-(1). in which each pair of points can be merged into one by the adversary, but the three cannot be merged because their three e-balls have an empty intersection, as depicted in Figure 6. For simplicity, we assume each point has probability w, of which satisfies the condition w1 < w2 + w/ on Case (i) in [45].
373
31
Figure 6: Toy example in Trillos et al. [45, Section 5.2], Case 4-(i). Best viewed in color.
Authors show that in this case, the optimal attack consist on distributing the mass of the original points into the neighbors in such way that, for each of the barycenters Fig. the mass coming from each of the original points I; and ž is the same. In our simplified example, this means that each original point sends 6 of its mass to each neighboring barycenter, as depicted in Figure 7a. When it comes an optimal classifier, the one presented Figure 7b is optimal and coincides with the one described in the original work of [45]. This classifier predicts the original class for each a; inside the part of the ball (x;) that is not intersecting any of the other balls. For each intersection B, (Z2z n B, ( the classifier predicts class and & with probability å each, and the third class i with probability O. This classifier achieves adversarial risk of 2. because at any point of the new adversarial distribution that is supported on {T12, T13, F23) this classifier has probability } of predicting the correct class.
203
13
323
271
6
(a) Optimal attack.
(b) Optimal classifier.
Figure 7: Solution for toy example in Trillos al. [45, Section 5.2], Case 4-(i). Best viewed in color.
From the perspective of our work, it is interesting that the optimal probabilistic classifier shown in Figure can be built as a uniform REC of deterministic classifiers fiyk that predict in B, (x.). j in (xy) \ B, (xx, and & in B, (xx) (B,x)) U B, (x,)) (see Figure 8). Each feyk has standard accuracy of and adversarial accuracy of & (risk of against optimal attack. like the constant
22

---

classifiers, because it can only be robust at one point at most. They are optimal when restricting to deterministic classifiers. Additionally, the uniform mixture of these classifiers coincides with the classifier presented in Figure 7b, which has standard accuracy of 1, and adversarial accuracy of with respect to the deterministic fizk.
meaning an increase in performance of
T1
T2
T1
T2
(a) Deterministic classifier f1z3
(b) Deterministic classifier fea1
Figure 8: Examples of deterministic classifiers that allow the construction of the optimal classifier as a REC
One can compute the matching penny gap of this mixture of classifiers in this dataset as follows: at each original point 24, there are only two classifiers that are robust (fijk and fakz), which means (H,,s(z; i)) = -/2 On the other hand. single perturbation will not fool all the four vulnerable models. Starting from I;, the attacker might move this point towards Iy or Tt- Any of these perturbations will fool three of the six classifiers. For example, the attack - F12 will fool the subset {f213, f231, f321). while the other three classifiers will correctly predict the class conclusion, mmax (zi, EhB 3. We conclude that at each point, the matching penny gap is exactly -- 8. for total expected matching penny gap of (recall every point had the same mass). The average risk is L. and the risk of the mixture be found using Equation (6) from Theorem 3.2 as 2z
Z12. In
Appendix D Proofs
Theorem 3.1. For a probabilistic classifier h : X - P(Y) constructed from a BHS Hi using any μ E P(Ho), we have (h,) < Enwy (h)].
Proof. For any E P(H)), we have the following.
R. Rh,) = E
sup (x)
( hp)
E
sup
E (1((x²') + y}l
(a.y)-up
(a.a)) m
('EB,()) hmp
E
1(h(z') + v\ (a)
sup
( m
houp
= E
E
sup ('E
1(h(z') # v\
2
hem
(x.y)<p
= E ham
[h)]
Taking infimum with respect to on both sides of the above inequality, we get the following.
inf (EP(H))
Re <
inf
E [R)]
(19)
(EP(H)) haup
23

---

For any h Ho. we may choose the Dirac measure that assigns probability to in order to obtain inf, (EP(HH) Reau (h)] I En-ua [R)] (h). Taking infimum over Hr, we get the following.
E [R) - inf (h).). (EP(Ha) houp
inf
(20)
NEH,
The remaining assertion of the theorem follows by combining (19) with (20).
Theorem 3.2. For a probabilistic classifier h : : - P(Y) constructed from a BHS Hi using any P(H)),
R. (bw)
E [Re(h)] hmw
I (a.y)mp
Thy (z, y)].
(6)
Proof.
Observe that for any h E Ho, sup 1(4(2) + y) =1 if and only if la E Heblo, v). Hence,
sup 1(h(x') # y}
= EE
[1 E Hoola, w)Hl = (Hooll (x,))
hawp (x)
hwwp
Taking expectation on both sides with respect to (z,, y) ~ P. we get
E
(u(Hos(D,,
E
E
sup (x)
1 (1((')) + v}
= E
[R)),
(21)
(r.
(x.y) Arups
hmne
where the second equality follows from switching the order of the two preceding expectations. For any x' (x),),
E [1((=') + v}1 w(th Ho h(2') # 3}) S 1 (x, y), hmw
where the above inequality holds because the i measure of any subset of Ho that is simultaneously vulnerable at some x' E B, (I:) is at most max (x., v)- Taking supremum over all x' E BB(x)) in the above incquality, we get the following.
sup E (1(((>)) vll < max (I, w) x'EB, hop
We will now show that the above inequality also holds in the other direction.
Let (H*)es k=1 be sequence of sets, H* (ar,(ar,)) y), such that limg ((H)) maa (ar, v)- For each H² we have by definition of Sanb(I, y) that there exists some x² B, (x) such that all
classifiers h H are fooled by zt In other words, the total mass of classifiers that fooled by x² greater or equal to ((H))) This gives
sup E [1(h(x') + > E [1(h(=*) + y}} 2 ((H²)) x'EB,(x) hmp
hwp
This is true for every k. so taking k: + oa we get that sup=')B.(z) EAny [1 (h(x') # v}1 2 limp- = (x, (r,y).
Taking expectation on both sides with respect to (z, ~ P. we get
R. = E
sup E [1fh(T') + y}ll (')
E (w.))~p
I max
(22)
(x.g)<p
Combining (22) and (21) yields (6).
"We can swap expectations by Fubeli-Tonelli's Tonelli's theorem because the function sup, B L(A(x') + y} is universally measurable if h is measurable (See [16, 40J) and both measure spaces X' x 3, Hd are assumed o-iinite We also assume the measurability w.r.t h. See Appendix A for details.

---

Corollary 3.1. For μl P(H)), Re(hy/) < infREm, (h) if and only if the following condition holds.
E
Th (2, v)
E
(h))
inf Re(h)
(9)
(m.y)~p
hmp
hEMo
Additionally, uePHH)) (h,), inlnez, R.c (l)) if and only if there exists p P(Hs) for which (9) holds.
Proof. Suppose (9) holds for some jl' E P(H)). Then,
inf R. (bp) R. (hw:) MEP(Ha)
E [R)]
Th (Ir 8)]
han
(x.yimp
< inf Re(h)
E hERb (a.0)~p
[T (x,, y)]
E (0.3))~
[mb (x, v)l
inf Re(h),
NER,
where the first equality follows from Theorem 3.2 and the second inequality follows from the assumption in (9). Suppose (9) does not hold for yí' P(Hss). Then,
R. (h,r) = E [h)]
E (x.w)~<p
[m (I,
kmw
> inf R. (h(
E
(h (x,
Thh (x, y)]
hEHA
(R.y)~p
(2.8)mup
inf R,
NEHo
Suppose (9) does not hold for any o² E P(Hs), then taking infimum with respect to μl E P(Hs) in the above inequality, get (EP(H))) Rhw/)) infnER, R.(h).
Lemma 4.1. Let h X' + (0, 1] be any measurable function. For any > (>, 2), the following inequality holds, and it becomes equality if h is continuous takes finitely many values:
"{ sup h(x²) > a 2 ('),(())
sup 1(h(a') > a) rEE,(())
(11)
Proof. As both functions only take the values and 1, it suffices show that if the RHS equal to 1, then so is the LHS. Suppose supweeB,Ce (w) [h((z) > a} 1. As the function (h(x') > a}
takes only a finite number of values, this implies that there exists some x² E B, (z) such that 1[((x=) > a} = This means that h(x*) > a, and therefore sup,'en, h(r') > a. This makes the LHS equal to
If we further assume that h is continuous or takes a finite number of values, then if the LHS is equal to one,
Theorem 4.1. Let h + |0, 1] be any probabilistic binary classifier. Let htt be the a-threshold classifier. Then the following equation holds:
R. 2 L. R. 2 inf R.(h"))
(12)
Further, if h is either continuous or takes finitely many values, the first inequality in (12) becomes an equality.
Proof. We begin the proof by rewriting the adversarial risk of terms of the adversarial risk for each class. To alleviate notation, we denote p0-1 ((z, v). h) = sup e0- ((2'((, y), h). Recall
from Equation (1) that
(h) = =v(0) R (h) + v(1) R,
(23)
25

---

Let us now develop the terms R²(h), For any
>E {>, we obtain the following:
(h)
= E
[ec ((z,)),
P~pa
E s~pp
((z, h) > alda
(24)
E [1(4] ((x, v) h) > a}} da mopp
In the last equation, were able to interchange the two integrals using Tomnelli's theorem. Indeed, the function (z, a) + [(20-1 ((x, y). h) > a) is Lebesgue measurable in X' x if (-- ((,,0), h) is Lebesgue measurable, which is the case [40, Theorem 1].
The next step to use Lemma 4.1 to interchange the supremum operator and the indicator function. This will make the adversarial risk of the h appear. For 0 and replacing the operator > by >, we obtain the following:
[
(h)
E z~p0
((x,0),,) at] da (1,
E
sup (a)
1(h(x') a} da
(25)
0 p-
(h")dd
Now we do a similar development for = and replacing the operator > by 2 to obtain:
(h)
1(1 h(x')= 2 a} da (
sup
2oup1
sup
1(1 - h(x')) da
8-911
E'E (m)
sup x'E,(()) (4)
1-1 > 1 a} do
(26)
1 1 h (x)) da
sup
x'EB, (a)
(1) htt da
E J0 Topp1
sup ('EB,( (m)
R. (h1 yd
(h")du
In the last equation, the change of variable = 1 allows us to complete the calculations and obtain the desired result. Putting everything together, we obtain the following result about the original probabilistic classifier h:
R. (h) 2 S (()) + ((L)R! ( = J. (h(())d
(27)
In particular, Equation (27) implies that (h) 2 min, R. (h meaning that for any h probabilistic
binary classifier, there is always deterministic a-threshold classifier with better equal adversarial risk.
Corollary 5.1. Let Hs be any family of deterministic binary classifiers. Let M PM (Ha) C P(Hs) be the subset of probability measures over Hs defining RECs as in Section 2.3. Let A (h-1(1) h E Ho.. If A is closed under union and intersection, then
inf (h) = inf R. (h,). heWo
μεP
26

---

Proof. Theorem 4.1 1 applied to RECs (see Section 4.2) tells us that Ho(Pas (Ha)) is the set of all
weighted ensembles built from Hs. It is clear that for any E Hy. òn E Par (Hs)) so Ho. S (P M (H6)). Let us now show the other inclusion.
Take any E Pas(Ho) and consider any weighted ensemble ho over Hy the form hº (x)
1[ Am a}} with Pm (b(mm)) Define the function g" {0, 13M 10, 1] as
( = 1===1mmm > a Then, hat can be written as gd (x) has (2)). Be- any monotone
cause the Pm are positive, the function g" is a monotone boolean function.
boolean function, g" can be written as disjunctive normal form (DNF) without negations [9]. Thus, the set AgNS {o E X' he (x) = 1} is a union of intersections over the sets A ....... AM where A (1). Because A is closed under union and intersection, AENS A. which means that ha E Hd. Thus, HPMPM (H6)) _ Ho.
As all the hypothesis of Theorem 5.1 are met, conclude that infREH, Re(h)
( (M,) (h,).
27


Reviews:
[{"review_id": "nYqNKLxHFL", "reviewer": "Reviewer_TdsR", "summary": "The paper addresses the theoretical problem of how randomization affects adversarial robustness. It establishes a condition that is both necessary and sufficient for enhancing the robustness of probabilistic models. Furthermore, it proves that in binary classification, a deterministic model can always achieve at least the same level of robustness. The paper also discusses the crucial condition for the effectiveness of randomization. Although the assumptions are strict, the theories in this work can serve as a foundation to further investigate adversarial robustness in probabilistic classifiers.", "questions": "N.A.", "limitations": "See weakness", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well-written and well-organized.\n2. The paper works on an interesting theoretical problem of the effect of using randomization on adversarial robustness. The theoretical result gives a promising hint to better understand the randomization methods.", "weaknesses": "1. The theories and proofs in this work heavily rely on binary classifiers with a misleading title. This restricts the practical application of these theories in real randomization scenarios.\n2. The work presented lacks in applying and evaluating the theory, even in binary cases. It does not explore the potential of the proposed theory to improve randomization or identify scenarios where a deterministic classifier is possible. For instance, can we find or estimate better deterministic models corresponding to baseline probabilistic classifiers? How can we apply the theories to enhance adversarial robustness? Including quantitative evaluations would significantly improve the quality of the work.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review. We agree with you in that a very interesting path for future work is the practical implementation of this theory. We are very interested in exploring how we can actually boost adversarial robustness, either by considering the right probabilistic classifiers (that maximize the *matching penny gap*), or by better understanding the threshold step used in Section 4 for binary classifiers. We believe that this theory should definitely give intuitions on practical actions towards implementable robust classifiers. \n\nBelow, we adress some of your remarks in more detail.\n\n\n1. Section 3 does not assume binary classification, it also works in multiclass. It is Section 4 which is restricted to binary classification.\n\n2. We provide theoretical evidence that we can indeed estimate the better deterministic models by training weighted ensembles and randomized smoothing classifiers in opposition to randomized ensembles and any kind of noise injection classifiers, which are abundant in the literature.\n\n3. The question of enhancing adversarial robustness is very interesting, and the theory we have developed can motivate new methods that rely on diversity promotion. It should also motivate the crafting of more powerful attacks that can adapt to the mixture scenario, i.e. attacks that maximize the mass of simultaneously attacked classifiers.\n"}, {"review_id": "S5TJiLU8up", "reviewer": "Reviewer_gWM1", "summary": "This paper provides an analysis of the role of randomization in developing adversarially robust classifiers. It explores the conditions under which randomized ensembles outperform deterministic classifiers regarding adversarial risk. The study also highlights the existence of deterministic classifiers that is at least the same adversarial risk as the probabilistic model, where the authors also connect the theory to weighted ensembles and randomized smoothing. Overall, the paper offers valuable insights into randomization for building robust classifiers in adversarial settings. ", "questions": "1. In adversarial literature, we might consider the attackers can submit malicious input multiple times, where one misclassification is considered a \"success attack.\" I believe the probabilistic model might be more likely to be broken. What happens to the current theorem if considering such an attacking scenario? I found a recent work [1] which is considering this issue. \n\n2. This paper considers a BHS composed of infinitely many linear classifiers. How does the theorem change if BHS is composed of non-linear classifiers? \n\n3. The paper mainly discussed robustness. How does the clean performance change of building a probabilistic model from deterministic models and back?\n\n[1] Lucas et al. Randomness in ML Defenses Helps Persistent Attackers and Hinders Evaluators. https://arxiv.org/pdf/2302.13464.pdf", "limitations": "The authors are suggested to include a paragraph discussing the limitations of the paper. ", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well-written, ensuring clarity and ease of understanding for readers.\n\n2. The paper offers a foundational understanding of the significance of randomization in building robust models. Especially, I find constructing a probabilistic model from a deterministic model and back particularly interesting. \n\n3. The paper includes an insightful analysis of existing methods (e.g., randomized smoothing ), showcasing their effectiveness. ", "weaknesses": "1. While the theoretical analysis presented in this paper is intriguing, it leaves me questioning its practical implications in constructing robust classifiers. Specifically, I am concerned about how these theoretical findings translate into practical strategies for building classifiers that perform effectively in real-world scenarios. For example, Theorem 4, in its current form, only addresses the binary case, limiting its applicability. I think the authors can add more discussion on how to guide the future empirical robust model design. \n\n2. The authors show there exists \"a probabilistic classifier that is at least as robust as the best deterministic classifier.\" However, I think it is more important to guide future research to find such a better probabilistic classifier in a principled way.\n\n3. Minor: It is recommended to explain the term \"Borel σ-algebra.\" \n4. Minor: Moving the fig1 to near page 4 is better. \n\nAs I am not an expert in theoretical research, evaluating the novelty and contribution is hard for me. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank you for your review. We are very happy to know that you find that our work offers a foundational understanding of the significance of randomization in building robust models. Furthermore, we also agree with you in that this theoretical contribution should be followed by practical ones. Particularly, we are very eager to work on practical algorithms to optimize the *matching penny gap* of a set of classifiers. Below we address your remarks and questions.\n\n> In adversarial literature, we might consider the attackers can submit malicious input multiple times, where one misclassification is considered a \"success attack.\"\n\nThank you for the interesting reference. We found out that it shares some ideas with our work. More precisely, their conclusion seems to agree with our conclusion in Section 4, where taking out the noise of a probabilistic classifier could give a potentially better deterministic one. However, they conclude this under a threat model that is particularly pessimistic for randomized models.\n\nWith the definitions we use for probabilistic classifiers, at any point $(x, y)$ we have that $\\mathbf{h}(x)_y$, the $y-$th component of $\\mathbf{h}(x)$, is the probability that we predict the correct label for $x$. In general, these probabilities will lie between 0 and 1, without being exactly 0 or 1, which means that simply making $n$ inferences on the same point, without even computing an attack, will decrease the chance of correctly predicting $n$ times in a row. Under this threat model, the performance of a probabilistic classifier will degrade as $n$ gets bigger.\n\nConsider a point $(x, y)$ and $M$ classifiers that are in a *matching penny* configuration, that is, **they are all individually vulnerable, but no attack can fool two classifiers simultaneously**. Recall that this is the scenario in which a mixture of classifiers provides the greatest gains in robustness w.r.t the original $M$ models considered. All of the $M$ original models have 0 accuracy on $(x,y)$ (under attack). However, using the mixture of the $M$ models gives an expected accuracy of $\\frac{M-1}{M}$ because no matter which classifiers the attacker chooses, there is a probability of $\\frac{M-1}{M}$ that we use another model to predict. This represents a gain of $\\frac{M-1}{M}$ in expected accuracy. Now, under the threat model with $n$ inference passes, this gain passes from $\\frac{M-1}{M}$ to $(\\frac{M-1}{M})^n$, which will decrease rapidly as $n$ increases. As an example, if $M=5$ and $n=5$, the gain passes from $0.8$ to $0.32$. If $n=10$, then it is only $0.107$.\n\nOn the other side of the spectrum, adding $n$ is also detrimental for those cases in which considering a mixture actually *added a vulnerability*. Just as the gains of the mixture become less important, also the new vulnerabilities become more critical. To see this, imagine the situation in which at a point $(x, y)$ there are $M-1$ models that are robust, and only 1 classifier that is vulnerable. An optimal attacker will attack this single model, as it is the only vulnerable one. In our setting, the best model had an accuracy of 1 at the point, and the mixture had an expected accuracy of $\\frac{M-1}{M}$, meaning the mixture introduced a loss in performance of $\\frac{1}{M}$ at the point. Now if we introduce $n$ and the attacker proposes the same attack, the mixture will have an expected accuracy of $(\\frac{M-1}{M})^n$, meaning the vulnerability introduced by the mixture is now $1 - (\\frac{M-1}{M})^n$, which tends to 1 as $n$ gets bigger.\n\nIn conclusion, our results show that mixing can be beneficial in certain cases, but if one considers this new, more pessimistic threat model parametrized by $n$, the gains provided by mixtures decrease, and the vulnerabilities introduced increase, making it harder for the mixture to bring any improvement w.r.t the original deterministic classifiers.\n\n> How does the clean performance change of building a probabilistic model from deterministic models and back?\n\nThe clean risk of a mixture equals the average risk of the base classifiers. There is no gain nor loss of accuracy when considering mixtures. This can be seen in the following equation:\n\n$$\\\\mathcal{R}(\\\\mathbf{h}_{\\\\mu}) = \\\\mathbb{E}\\_{x, y \\\\sim \\\\rho} \\\\left[ \\\\mathbb{E}\\_{h \\\\sim \\\\mu} \\\\left[ \\\\mathcal{1}\\\\{h(x) \\\\ne y \\\\} \\\\right] \\\\right] =  \\\\mathbb{E}\\_{h \\\\sim \\\\mu} \\\\left[ \\\\mathbb{E}\\_{x, y \\\\sim \\\\rho} \\\\left[ \\\\mathcal{1}\\\\{h(x) \\\\ne y \\\\} \\\\right] \\\\right] =  \\\\mathbb{E}\\_{h \\\\sim \\\\mu} \\\\left[ \\\\mathcal{R}(h) \\\\right] $$\n\nThe average risk is lower bounded by the lowest risk achievable in $\\mathcal{H}_b$. This means that mixing does not offer any gain in standard risk, which is in contrast with what is shown in Section 3, where we study the conditions under which mixing does improve adversarial risk.\n\nWhen it comes to Theorem 4.1, the proof can be replicated with equality, meaning that for a binary probabilistic classifier $\\mathbf{h}: \\mathcal{X} \\to \\left[0, 1 \\right]$, it holds that $\\mathcal{R}(\\mathbf{h}) = \\int_0^1 \\mathcal{R}(h^{\\alpha}) d\\alpha \\ge \\inf_{\\alpha} \\mathcal{R}(h^{\\alpha})$. So we can say that inside the same family of $\\alpha$-threshold classifiers, there exists one with better standard risk than the original probabilistic classifier.\n\n> How does the theorem change if BHS is composed of non-linear classifiers?\n\nWe do not consider linear classifiers only, apart from certain examples, like Example 1 or Figure 1. The results that we prove hold for non-linear classifiers too. We agree we need to add some explicit assumption on the family of classifiers $\\mathcal{H}_b$, but by no means is this family restricted to linear classifiers. Our work covers many practical scenarios of interest, like neural networks with continuous activations and many other parametric families of hypothesis.\n\n[1] Lucas et al. Randomness in ML Defenses Helps Persistent Attackers and Hinders Evaluators."}, {"review_id": "imuKZ2fCdg", "reviewer": "Reviewer_Tq42", "summary": "Several proposed adversarial defenses involve randomized classifiers. Prior theoretical work analyzes both the randomized and non-randomized cases. This paper answers: 1) When does randomization 'help' in adversarial classification? 2) When does it suffice to consider deterministic classifiers?\n\nThe authors start by describing three common paradigms ( randomized ensemble classifier (REC), weight-noise injection classifier (WNC), input-noise injection classifier (INC)) for constructing randomized classifiers. Subsequently, the authors give a condition describing when randomized classifier over a hypothesis set $\\mathcal H_b$ will outperform deterministic classifiers. Next, the authors show that one can always threshhold a binary randomized classifier to get a better performing deterministic classifier. Lastly, the authors show that if $\\cH_b$ is all measurable sets, then randomization over $\\cH_b$ does not improve the adversarial risk.", "questions": "- line 108: The Borel sigma algebra is defined in terms of the open sets on a topological space. How are you defining the topology on the set $\\mathcal H_b$? It seems that in the REC, ENC, INC paradigms, there is a \"continuous\" map from $\\mathbb R^d$ to $\\mathcal H_b$. Perhaps you could use this map. \n- Can you explain the name \"penny matching gap\"?\n- In section 4.1, I would expect that one can always take the threshhold $\\alpha=1/2$. Why is this not the case?\n", "limitations": "Some of the results only hold in the binary case. The paper discusses this limitation", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "- The paper answers and important question in the field of adversarial learning: when does randomization help with adversarial classification?\n- Proofs seem simple and clear", "weaknesses": "The exposition is not great. Here are some specific issues.\n0. Please state your threat model. Your adversary has access to the randomized classifier, but does not know which random function the learner uses every time a point is classified.  \n1. Equation 1:  $\\mathcal R_\\epsilon ^y$ is not defined before equation (1)\nNote that you also need to explain that $\\sup_{x'\\in B_\\e(x)} \\ell^{0-1}((x',y),h)$ is measureable. See appendix A of the following reference for this result:\nExistence and minimax theorems for adversarial surrogate risks in binary classification. N. S. Frank, J. Niles-Weed.\n2. Foot note 1: I understand how such a proof would go, but I would expect to see a proof with a maximizing sequence rather than a maximizer in the supplementary material\n3. I couldn't understand the argument in line 191-192\n4. lines 203-204: I couldn't understand the sentence. \"More generally, assumption...\"\n5. I had a hard time understanding the parallel decision boundaries discussion in example 2\n6. line 276: I think an REC built from 2 base classifiers takes on continuously many values. Can you better explain 276-278?\n7. The supplementary material is quite disorganized", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for all the effort you put in reviewing our work and pointing out relevant references. We appreciate that you find that our paper \"answers an important question in the field of adversarial learning\". We will put all out effort in clarifying the exposition of the paper to make it clearer and avoid confusion. Below are some comments addressing your suggestions and questions. Also, as your remarks and questions were very important and numerous, we will be answering some of them in an official comment to this rebuttal if we are allowed.\n\n> Please state your threat model\n\nWe will add in Section 2 the details about our threat model, in which, as you state, the adversary has full access to the models (parameters, gradients, number of models, etc.), but no control nor access over the randomness used by the defender to choose which model to use for each inference pass. That is, we are in a white-box threat model without access nor control over the random number generators.\n\n> line 108: About the Borel sigma algebra over $\\mathcal{H}_b$\n\nIn all our particular use cases, the space $\\mathcal{H}_b$ is either finite or identifiable to some usual subset of $\\mathbb{R}^d$. In the case of INC, $\\mathcal{H}_b$ is identifiable with the input space $\\mathcal{X} \\subset \\mathbb{R}^d$. For WNC, when classifiers are parametrized over some $\\mathbb{R}^p$ (neural networks, linear classifiers), this is also the case. So in any of these cases, the topology considered is the usual topology and the Borel $\\sigma$-algebra is defined accordingly.\n\nIn Remark 4 we consider a setting closer to [1, 2, 3], where $\\mathcal{H}_b$ is much more complex. However, this remark holds when one takes any finite number of optimal classifiers, so even if the family $\\mathcal{H}^*$ of optimal classifiers is complicated, we can simply take any pair of them ($\\mathcal{H}_b$ finite, with two elements) and say that their matching penny gap must be zero.\n\nWe thank you for pointing out the need for clarification. We will make it clear in Section 2 that, for this work, $\\mathcal{H}_b$ will always be either finite or directly identifiable with some subset of $\\mathbb{R}^p$. Furthermore, we will also reformulate Remark 4 accordingly.\n\n> Note that you also need to explain that $\\sup_{x' \\in B_{\\epsilon}(x) } \\ell^{0 -1}((x', y), h)$ is measureable\n\nWe totally agree that the measurability of the 0-1 loss under attack is non-trivial, and it is important to discuss it. Your remark sparked an important discussion within the team that led to the following conclusions:\n\nTo ensure measurability, we add the assumption that for every $y$, the evaluation function $f : \\mathcal{X} \\times \\mathcal{H}_b \\to \\mathbb{R}$ defined as $f(x, h) = h(x)_y$ (the $y$-th component of $h(x)$ seen as a vector function) is Borel measurable in $\\mathcal{X} \\times \\mathcal{H}_b$. This might not be true in general (see this thread https://mathoverflow.net/a/28114), but it holds in our setting. What we mean is that in practice, $f$ takes a simpler form, like $f(x, w) = (w^T x)\\_y$ in the case of linear classifiers, or $f\\_{w}(x)\\_y$ in the case of parametrized neural networks. In all these settings, the function $f$ can be assumed to be well-behaved function from $\\mathbb{R}^d \\\\times \\mathbb{R}^p$ to $\\\\mathbb{R}^K$ that satisfies the measurability condition.\n\nAssuming that for every $y$, the mapping $(x, h) \\to h(x)\\_y$ is Borel measurable, we can then write the expected 0-1 loss as\n\n$$\\\\ell^{0 -1}((\\\\cdot, y),\\\\mathbf{h}\\_{\\\\mu}) = \\\\mathbb{E}\\_{h \\\\sim \\\\mu} \\\\left[ \\\\mathcal{1}\\\\{h(x) \\\\ne y \\\\} \\\\right] = \\\\mathbb{E}\\_{h \\\\sim \\\\mu} \\\\left[ 1 -h(x)\\_y \\\\right] = \\\\int_{\\\\mathcal{H}\\_b} 1 -h(x)\\_y d\\\\mu(h)$$\n\nand by Fubini-Tonnelli's Theorem, this function will be Borel measurable in $\\mathcal{X}$.\n\nThe final step would be to apply [1, Appendix A, Theorem 27] to prove that the loss under attack is universally measurable, and that the adversarial risk is well-defined in the universal $\\sigma$-algebra.\n\n> Proof with a maximizing sequence\n\nWe will add this proof in the supplementary material. We will also modify the definitions in page 5 accordingly. In particular, we will define $\\\\mu^{max}(x, y) = \\\\sup\\_{\\\\mathcal{H}' \\\\in \\\\mathcal{H}\\_{svb}} \\\\mu(\\\\mathcal{H}')$ instead of using the $argmax$, which somehow assumes the existence of such $\\mathcal{H}^{max}\\_{svb}$ (and $x^{max}$ in the proof).\n\n> I couldn't understand the argument in line 191-192\n\nThe main intuition is that the optimal attack for a mixture of models, i.e. in which the defender randomly samples a model at inference, consists exactly on crafting an attack that simultaneously attacks as many classifiers as possible. This lines however will be modified according to the last answer.\n\n> Can you explain the name \"penny matching gap\"?\n\nPlease refer to the global response.\n\n[1] Existence and minimax theorems for adversarial surrogate risks in binary classification\n\n[2] The Many Faces of Adversarial Risk\n\n[3] On the Existence of the Adversarial Bayes Classifier (Extended Version)\n\n[4] Randomization matters. How to defend against strong adversarial attacks\n\n[5] Adversarial Risk via Optimal Transport and Optimal Couplings"}, {"review_id": "ILjBtZaeOd", "reviewer": "Reviewer_ZKUe", "summary": "The paper investigates randomized classifiers and their robustness against adversarial examples. The authors' contributions can be found along three different axes. First, the authors give the necessary and sufficient conditions so that from a set of deterministic classifiers one can build a randomized classifier that outperforms the best deterministic classifier from the original set (w.r.t. adversarial risk). In sequence the authors present some results in the opposite direction in the binary classification case; e.g., for every randomized ensemble classifier there exists a deterministic weighted ensemble with better adversarial risk. Finally, the authors identify the conditions under which randomization can provably help on a deterministic base hypothesis set. \n\nAfter rebuttal: Upgraded my score from \"Weak Accept\" to \"Accept\".", "questions": "Q1. In lines 144-146 it is stated \"Consequently, we get that there always exists a probabilistic classifier that is at least as good as the best deterministic classifier in the BHS $\\mathcal{H}_b$.\" Can you please explain why and how this follows from the previous sentence?\n\nQ2. In lines 210-211 we have \"Observe that every classifier in $H_b$ is vulnerable at $(x,y) = (0,1)$ and so $R_{\\epsilon}(h) = 1$ for all $h\\in H_b$\". I am not sure I follow; since $x = 0$, then $w^T x = 0$ and therefore 1{$w^Tx < 1$} should return 1, which is really the label $y$. Can you explain? ", "limitations": "I think the paper is ok in this regard, especially in the light of the clear ideas for future work that one can pursue and are listed in Section 6.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Some of the ideas of the paper are building on ideas and findings of prior work by Dbouk and Shanbhag; namely, the observation that a randomized classifier can achieve a decisive advantage over any deterministic classifier, because the adversary can only force a misclassification on a subset of all vulnerable classifiers, where \"vulnerable\" means classifiers that can be fooled with perturbations of certain magnitude. This observation and the continuation of the work is interesting and the paper is well-written for the largest part, though, near the end I found it more dense than what I would have preferred it to be. I expect this paper to influence to some extent the work that will be done on the robustness of randomized classifiers in the near future. Overall an interesting paper with interesting findings, though, for completeness, I would like to see the authors add some information in the supplementary material even for simple claims; e.g., clearly write down the calculations for Figure 1b, or clarify other small remarks that they have here and there. I also like Section 6; the conclusion that the authors have written -- a clear summary of their contributions and a summary of ideas related to their work that can be explored as future work.", "weaknesses": "Figure 1 appears 2 pages after it is first mentioned. One page difference is ok, but two pages is strange.\n\nThe authors assume that the label y does not change within the perturbation budget $\\epsilon$ around $x$. While this is a reasonable assumption, and in fact it is the prevailing assumption in adversarial robustness, nevertheless, it is not the only assumption one can make. Clarifying this and citing any of the following two papers (or both?) so that someone can find more information about the topic, I believe can be important and potentially also motivate further avenues for randomized classification. The two papers are:\n\n[M1] Adversarial Risk and Robustness: General Definitions and Implications for the Uniform Distribution\nhttps://proceedings.neurips.cc/paper_files/paper/2018/file/3483e5ec0489e5c394b028ec4e81f3e1-Paper.pdf\n\n[M2] On the Hardness of Robust Classification\nhttps://www.jmlr.org/papers/volume22/20-285/20-285.pdf\n\nLine 102: Write down explicitly the adversarial risk of a deterministic classifier in the appendix, if it does not fit in the main part of the paper, so that there is no ambiguity.\n\nI think the \"Matching Penny\" notions are not clearly defined in the paper. It is apparent that some of the ideas have appeared in prior work but the authors spend nearly no time explaining the original ideas and the original context.  I believe this should change.  In particular, the authors cite two books in lines 168-170 without saying much more; the reader may have no idea about these books and this line of work.\n\nIt is quite unfortunate that Definition 1 splits between pages because the notation is a bit overloaded and it is clarified on the following page.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful review and pointing out relevant references. We are very pleased to know you found our work \"interesting and well-written for the largest part\". We also share the expectation that our contribution will \"influence to some extent the work that will be done on the robustness of randomized classifiers in the near future\". Below we answer your questions and concerns.\n\n> The authors assume that the label $y$ does not change within the perturbation budget $\\epsilon$ around $x$\n\nYes, we indeed work on the *corrupted-instance* setting according to [1] (*constant-in-the-ball* [2]), as opposed to the *error region* or *prediction change* formulations [1]. As discussed in [1, 2], this definition can be problematic because even the true concept class can have positive and even constant adversarial risk. However, we consider the *corrupted-instance* setting because it is commonly studied in adversarial examples literature [3, 4, 5] and in the work that is closely related to ours, like [6, 7].\n\nWe will include in the paper a comment mentioning the different notions of adversarial risk and clearly clarify that our work corresponds to the *corrupted-instance* setting.\n\n> I think the \"Matching Penny\" notions are not clearly defined in the paper\n\nPlease refer to the Global response.\n\n> In lines 144-146 it is stated \"Consequently, we get that there always exists a probabilistic classifier that is at least as good as the best deterministic classifier in the BHS $\\mathcal{H}_b$.\" Can you please explain why and how this follows from the previous sentence?\n\nWe thank you for pointing out this sentence, as we agree it needs to be rephrased to really transmit the correct message. There is a simpler argument to support this remark, which is expressed in the proof of Theorem 3.1 in the Supplementary Material, lines 482-486. The idea is that the original deterministic classifiers $h \\in \\mathcal{H}\\_b$ can be seen as probabilistic classifiers by considering $\\mathbf{h}\\_{\\mu}$ with $\\mu = \\delta\\_{h}$, the Dirac measure over $h$. This being said, one can take infimum over all probabilistic classifiers over $\\mathcal{H}_b$, and obtain that for any $h' \\in \\mathcal{H}_b$ the following holds:\n\n$$\\inf\\_{\\mu \\in \\mathcal{P}(\\mathcal{H}_b)} \\mathcal{R}\\_{\\epsilon}(\\mathbf{h}\\_{\\mu}) \\le \\mathcal{R}\\_{\\epsilon}(\\mathbf{h}\\_{\\delta\\_{h'}}) = \\mathcal{R}\\_{\\epsilon}(h')$$\n\n\n> In lines 210-211 ... [About Example 1]\n\nAs you state, each classifier $w$ satisfies that $w^Tx = 0$, and therefore $\\mathcal{1}\\\\{w^Tx < 1\\\\} = 1$, which means that all $w$ predict the correct label for the *clean* input $x$. Now we want to see that every $w$ is vulnerable at $x$.\n\nRecall that we defined $\\mathcal{H}\\_b$ as the space of linear classifiers $w$ such that $\\left\\lVert w \\right\\rVert\\_{\\star} = \\frac{1}{\\epsilon}$. In our case, $\\mathcal{X} = \\mathbb{R}^d$ with (usually) an $L_p$ norm $\\left\\lVert \\cdot \\right\\rVert$, so we can rewrite the dual norm as $\\left\\lVert w \\right\\rVert_{\\star} = \\sup\\_{\\left\\lVert z \\right\\rVert=1} \\{ w^Tz \\}$. Moreover, this supremum is attained by some $z_w$, so for each $w$ we get $z_w$ of norm 1, such that $w^T z_w = \\frac{1}{\\epsilon}$.\n\nNow, for each $w \\in \\mathcal{H}_b$, consider the adversarial example $\\epsilon \\cdot z_w$. It is a valid adversarial example because it has norm $\\epsilon$, and $w^T (\\epsilon \\cdot z_w )= \\epsilon \\cdot \\frac{1}{\\epsilon} = 1$, meaning that the classifier predicts $\\mathcal{1}\\\\{w^T (\\epsilon \\cdot z_w) < 1\\\\} = 0$, the wrong class. The next step is to guarantee that this perturbation is unique for each $w$, and your question made us realize that we need to add an extra assumption for this: we need to work with the $L_2$ norm so that $z_w$ is the only vector attaining the supremum on the dual norm.\n\nHaving that $\\epsilon \\cdot z_w$ fools $w$ and *only* $w$, we can consider for simplicity $\\mu$ the uniform distribution over $\\mathcal{H}_b$. Let us compute the sets $\\mathcal{H}\\_{vb}$ and $\\mathcal{H}^{max}\\_{svb}$ to be able to compute the *matching penny gap* for this example.\n\nAs we just saw, every $w$ is itself vulnerable. This means that $\\mathcal{H}\\_{vb} = \\mathcal{H}\\_{b}$, and therefore $\\mu(\\mathcal{H}\\_{vb}) = 1$.\n\nGiven the unicity of $z_w$, we know that no two classifiers can be fooled by the same perturbation. Therefore the family of simultaneously vulnerable classifiers only contains singletons $\\{w\\}$. As $\\mu(\\{w\\}) = 0$ for every $w$, taking the supremum gives $\\mu(\\mathcal{H}^{max}_{svb}) = 0$.\n\nFinally, the matching penny gap is $\\pi_{\\mathbf{h}\\_{\\mu}}(x,y) = \\mu(\\mathcal{H}\\_{vb}) - \\mu(\\mathcal{H}^{max}\\_{svb}) = 1$. In other words, the mixture in this example has the best adversarial risk possible, even though it is built from classifiers with the worst adversarial risk possible individually.\n\nWe will add the complete explanation on the Supplementary material, and add to the main paper that the example works for the $L_2$ norm.\n\n[1] Adversarial Risk and Robustness: General Definitions and Implications for the Uniform Distribution\n\n[2] On the Hardness of Robust Classification\n\n[3] Towards Deep Learning Models Resistant to Adversarial Attacks\n\n[4] The Limitations of Deep Learning in Adversarial Settings\n\n[5] The Many Faces of Adversarial Risk\n\n[6] Adversarial Vulnerability of Randomized Ensembles\n\n[7] Mixed Nash Equilibria in the Adversarial Examples Game"}]

Author rebuttal:
We thank all the reviewers for their very valuable comments and questions. Many of them also pointed out interesting references that sparked interesting discussions within the team. We are glad that multiple reviewers found that our work tackles an interesting question related to adversarial robustness, and that it should contribute to future work on the use of randomized classifiers for adversarial robustness. Below we address comments that were raised by multiple reviewers

> About the term *matching penny gap*

We agree that it would be better to add a more complete explanation on what the term means and why it is relevant to our analysis. Below is a more in depth explanation that we would like to include in the Supplementary material, and a summary of it if possible in the main paper, Section 3 with the introduction of the matching penny gap.

Recall that in the original matching penny game between player 1 (attacker) and player 2 (defense), each player has a penny coin and has to secretly position its penny in either heads or tails. Then, both coins are simultaneously revealed and the outcome of the game is decided as follows: attacker wins if both pennies match. If they do not match, then defender wins.

The parallel with our work can be simply explained as follows: Take a point $(x, y)$ and two classifiers $tails, heads$ that correctly classify $x$. Suppose that both $tails$ and $heads$ are vulnerable at $x$ for some given threat model, but add the key assumption that they cannot be attacked at the same time (Figure 1.a). That is, even though an optimal attacker can fool each classifier individually, there is no point in the allowed perturbation region $B\_{\epsilon}(x)$ in which both are simultaneously fooled. Consider that the defender is using a randomized ensemble that picks either $tails$ or $heads$ at random for inference. This was introduced in [1] with the name *mixtures of classifiers*, related to mixed strategies in the context of game theory. In such setting, the optimal attacker that faces such mixture is now in a matching pennies game situation. At each inference pass, the attacker must choose which classifier to attack in order to craft the adversarial example $x'$, and if the chosen classifier matches with the one the defender used, then the attacker wins. If they do not match, the prediction made by the defender will be correct and the attacker would have lost.

Notice that if we increase the number of choices (classifiers) in matching pennies configuration to $M>2$, the game becomes harder for the attacker. Indeed, for every possible choice the defender can make, there is one out of $M$ choices that lead to a successful attack, and $M-1$ that lead to a correct classification. An extreme example of such benefit to the defender is shown in Example 1.

> Completeness of the supplementary material

We agree that adding deeper explanations of examples and the calculations of Figure 1 would increase the overall quality and completeness of the paper. We are going to add these detailed explanations and calculations, as well as the modified proof of Theorem 3.2 with a maximizing sequence. We will also add the comment related to the measurability of the 0-1 loss under attack. Other things we will add :

- Motivation of the name *matching penny gap*
- Adversarial risk for deterministic classifiers (line 102) as ZKUe suggests.

> Figure placement

We will do our best to ensure Figure 1 appears closer to the relevant section.

***

**Supplementary pdf**

In the supplementary PDF page we added three plots that show how the adversarial risk of the deterministic classifiers $h^{\alpha}$ behaves w.r.t $\alpha$, and compare it with the adversarial risk of the base probabilistic classifier $\mathbf{h}$. These plots show that, following Theorem 4.1, there is always some $\alpha$ such that $h^{\alpha}$ performs better that $\mathbf{h}$. The dataset used was CIFAR-10, where classes were grouped into `animal` and `vehicle` to create a binary classification task, creating a 60%-40% class distribution.


[1] Randomization matters. How to defend against strong adversarial attacks

Meta-review: ## Overview

This is a theory paper studying randomness and adversarial robustness. One of the main results is a condition for improving robustness in a randomized defender setting. As a consequence, the authors show that deterministic models can be at least as robust as randomized models for binary classification. The authors study multiple approaches to constructing robust randomized classifiers, e.g., randomized ensemble classifier (REC), weight-noise injection classifier (WNC), input-noise injection classifier (INC). The authors analyze these approaches in the context of their performance relative to the best deterministic classifier, deriving a number of new results.

On the positive side, the reviewers found the results to be interesting, novel, and insightful. The theoretical results are also motivated by common approaches in practice, leading to potential future empirical impact. Given that the authors provide new results on basic, fundamental questions, there is likely be a broad scope for future work inspired by this paper.

On the negative side, there are some serious concerns around the exposition and clarity of the writing (see below in the improvements section).

The authors and reviewers had a very fruitful discussions. In particular, several very technical questions and suggestions were raised by the reviewers. The authors have taken these into consideration, and I believe they will improve the final version of the paper. The discussion and clarifications also led to a number of score increases, speaking to the impact and correctness of the paper.

## Improvements:

It would be good to continue improving the final version of the paper by including (either in the main paper or appendix) more exposition around the main results in the paper.  For example, in the recent comments, there a number of improvements that should be included in the final version of the paper (e.g., the name matching penny gap and adversarial risk for deterministic classifiers). Please also add examples/calculations relating to Figure 1 and any clarifications around the theorem statements and proofs. Similarly, it is quite important to be clear about the attack model: access to the parameters, gradients, but not the defender randomness.
Decision: Accept (spotlight)