On The Existence of The Adversarial Bayes Classifier
Year: 2022

Abstract:
Adversarial robustness is a critical property in a variety of modern machine learning applications. While it has been the subject of several recent theoretical studies, many important questions related to adversarial robustness are still open. In this work, we study a fundamental question regarding Bayes optimality for adversarial robustness. We provide general sufficient conditions under which the existence of a Bayes optimal classifier can be guaranteed for adversarial robustness. Our results can provide a useful tool for a subsequent study of surrogate losses in adversarial robustness and their consistency properties.

heading: 1 Introduction
text: A key problem with using neural networks is their susceptibility to small perturbations: imperceptible changes to the input at test time may result in an incorrect classification by the network (Szegedy et al., 2013). A slightly perturbed picture of a dog could be misclassified as a hand-blower. The same phenomenon appears with other types of data such as biosequences, text, or speech. This problem has motivated a series of research publications studying the design of adversarially robust algorithms, both from an empirical and a theoretical perspective (Szegedy et al., 2013; Biggio et al., 2013; Madry et al., 2017; Schmidt et al., 2018; Athalye et al., 2018; Bubeck et al., 2018b; Montasser et al., 2019).
In the context of classification problems, instead of the standard zero-one loss, an adversarial zero-one loss has been adopted which penalizes a classifier not only if it misclassifies an input x but also if it does not maintain the correct x-label in a ϵ-neighborhood around x (Goodfellow et al., 2014; Madry et al., 2017; Tsipras et al., 2018; Carlini and Wagner, 2017). Since optimizing the adversarial zero-one loss is computationally intractable, a common approach for adversarial learning is to use a surrogate loss instead. However, optimizing a surrogate loss over a class of functions may not always lead to a minimizer of the true underlying loss over that class. In the case of the standard zero-one loss, there is a large body of literature identifying conditions under which surrogate losses are consistent, that is, minimizing them over the family of all measurable functions leads to minimizers of the true loss (Zhang, 2004; Bartlett et al., 2006; Steinwart, 2005; Lin, 2004). More precisely, as argued by Long and Servedio (2013), it is in fact H-consistency that is needed, which is consistency restricted to the hypothesis set under consideration. A surrogate loss may be consistent for the family of all measurable functions but not for the specific family of functions H, and a surrogate loss can be H-consistent for a particular family H, without being consistent for all measurable functions. When are adversarial surrogate losses H-consistent? This problem is already non-trivial for the standard zero-one loss: while there are well-known results for the consistency of losses for the zero-
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
one loss such as (Bartlett et al., 2006; Steinwart, 2005), these results do not hold for H-consistency. Existing theoretical results for H-consistency assume that the Bayes risk is zero (Long and Servedio, 2013; Zhang and Agarwal, 2020). A similar situation seems to hold for the more complex case of the adversarial loss. Recently, Awasthi et al. (2021) gave a detailed study of H-calibration and H-consistency of surrogates to the adversarial loss and also pointed out some technical issues with some H-consistency claims made in prior work (Bao et al., 2020). These authors presented a number of negative results for adversarial H-consistency and positive results for some surrogate losses which assume realizability. For these positive results, the zero Bayes adversarial loss seems necessary. In fact, the authors show empirically that without the realizability assumption, H-consistency does not hold for a variety of surrogate losses, even when they are H-calibrated. But when is the Bayes adversarial loss zero? Clearly, the adversarial risk can only be zero if it admits a minimizer, which we call the adversarial Bayes classifier. However, it is unclear under what conditions such a classifier exists. This is the primary theoretical question that we study in this work.
We now describe the challenges involved in finding minimizers of the adversarial zero-one loss. Most of the existing work on the study of Bayes optimal classifiers focuses on loss functions such as the zero-one loss that admit the pointwise optimality property (Steinwart, 2005; Steinwart et al., 2006). To illustrate this better, consider the case of binary classification where on a given input x, η(x) denotes the conditional class probability, that is, η(x) := P(y = 1 | x). In this case, it is well-known that the Bayes optimal classifier can be obtained by making optimal predictions per point in the domain: at a point x predict 1 if η(x) ≥ 12 , −1 otherwise. Similar to the notion of a Bayes optimal classifier, an adversarial Bayes optimal classifier is the one that minimizes the adversarial loss. However, an immediate obstacle is that the pointwise optimality property does not hold for adversarial losses.
As an example, consider the case of binary classification and perturbations measured in the ℓ2 norm. Then, for a given labeled point (x, y) and a perturbation radius ϵ, the adversarial zero-one loss of a classifier f is defined as maxx′ : ∥x′−x∥2≤ϵ 1(f(x
′) ̸= y). Thus, the loss at a point x cannot be measured simply by inspecting the prediction of the classifier at x. In other words, the construction of an adversarial Bayes optimal classifier necessarily involves arguing about the global patterns in the predictions of the classifier across the entire input domain. As a result, most of the technical tools developed for the study of Bayes optimal classifiers for traditional loss functions are not applicable to the analysis of adversarial loss functions, and new mathematical techniques are required.
The above discussion leads to our second motivation for studying the question of existence of the adversarial Bayes classifier. Insights regarding the structure of the adversarial Bayes optimal classifier could have algorithmic implications. For example, in the case of the standard zero-one loss, many popular learning algorithms seek to approximate the conditional probability of a class at a point because the conditional probability defines the Bayes optimal classifier in this case. Analogously, one could hope to develop new algorithmic techniques for adversarial learning with a better understanding of the properties of adversarial Bayes classifiers. In fact, two recent publications propose this approach (Yang et al., 2020; Bhattacharjee and Chaudhuri, 2020). Although their results do not rely on the existence of the adversarial Bayes classifier, they implicitly make this assumption to make their arguments clearer. Our work provides a rigorous basis for this premise.
A second related concept is certified robustness. A point x is certifiably robust for a classifier f and a perturbation radius ϵ if every perturbation of radius at most ϵ leaves the class of x unchanged. In this paper, we further study a property which we refer to as pseudo-certified robustness, which is necessary for certified robustness. We show that there always exists an adversarial Bayes classifier which satisfies the pseudo-certified robustness condition for a fixed radius at every point. However, a non-trivial classifier cannot be certifiably robust for a fixed radius at every point – specifically, a classifier is not certifiably robust at points within ϵ of the decision boundary. Furthermore, we argue that a classifier that is not pseudo-certifiably robust is typically not optimal. Lastly, Lewicka and Peres (2020) prove that for 2-norm perturbations, the boundary of a pseudo-certifiably robust set is differentiable and has Lipschitz normals.
The concept of certified robustness has algorithmic implications. Cohen et al. (2019) recently showed that after training a classifier, a process called randomized smoothing makes the classifier certifiably robust at a point x in the ℓ2 norm with a radius that depends on the point x. As the adversarial Bayes classifier is pseudo-certifiably robust but not certifiably robust with a fixed radius at every point, one could try to design algorithms which ensure pseudo-certifiable robustness during or after training. Recent works have explored constructing certificates of robustness as well (Raghunathan
et al., 2018; Weng et al., 2018; Zhang et al., 2018; Wong and Kolter, 2018). A better understanding of the adversarial Bayes classifier could help find additional learning algorithms. By studying the existence of the adversarial Bayes classifier, we take a first step towards this broader goal.
We now describe the organization of the paper. Section 2 summarizes related work and Section 3 presents the mathematical formulation of our problem. Section 4 discusses our main result and the proof. Next, Section 5 addresses the measurability issues relating to this problem. Section 6 demonstrates how our techniques might apply to other models of perturbations. Subsequently, in Appendix A, we prove the measurability results stated in Section 5 and, in Appendix B, we prove a variant of Prokhorov’s theorem that is essential for our proofs. Next, in Appendix C, we prove one of our key lemmas. Appendicies A, B and C present stand-alone results which do not depend on material elsewhere in the appendix. In Appendix D, we subsequently provide some background material for the results in Appendicies E-G. Next, we prove the rest of our key lemmas in Appendicies E and F. Lastly, Appendix G states and proves two generalizations of our main result.

heading: 2 Related Work
text: Existing theoretical work on adversarial robustness focuses on questions such as adversarial counterparts of VC-dimension and Rademacher complexity (Cullina et al., 2018; Khim and Loh, 2018; Yin et al., 2019; Awasthi et al., 2020), evidence of computational barriers (Bubeck et al., 2018b,a; Nakkiran, 2019; Degwekar et al., 2019) and statistical barriers towards ensuring low adversarial test error (Tsipras et al., 2018).
Cullina et al. (2018) formulate a notion of adversarial VC-dimension, aimed at capturing uniform convergence of robust empirical risk minimization. The authors show that, for linear models, adversarial VC-dimension coincides with the VC-dimension. However, in general, the two could be arbitrarily separate. In a similar vein, Khim and Loh (2018), Yin et al. (2019) and Awasthi et al. (2020) study the Rademacher complexity of adversarially robust losses for binary and multi-class classification. Schmidt et al. (2018) provide an instance of a learning problem where one can provably demonstrate a gap between the sample complexity of (standard) learning and adversarial learning.
Tsipras et al. (2018) points out a problem where any learning algorithm that achieves low (standard) test error must necessarily admit high adversarial test error, that is close to 1. This highlights a fundamental tension between ensuring low test error and low adversarial error. There are also studies of the conditions on the data distribution that lead to the presence of adversarial examples and the design of adversaries that can exploit them (Diochnos et al., 2018; Bartlett et al., 2021). The recent work of Montasser et al. (2019) shows that any function class with finite VC-dimension d can be adversarially robustly learned (in a PAC-style model) using exp(d) many samples.
Bubeck et al. (2018b,a) provide evidence of computational barriers in adversarial learning by constructing learning tasks that are easy in the PAC model, but that become intractable when adversarial robustness is required. Several recent publications have studied the question of characterizing the Bayes adversarial risk (Pydi and Jog, 2019; Bhagoji et al., 2019) for binary classification and relate it to the optimal transportation cost between the two class conditional distributions. While these studies aim to establish a lower bound on the Bayes adversarial risk, we study a more fundamental question of when the Bayes adversarial classifier exists. There have also been publications studying robustness beyond ℓp norm perturbations (Feige et al., 2015, 2018; Attias et al., 2018).
Finally, there are studies in the mathematical community of various properties regarding the direct sum of a set and an ϵ-ball, which we use to model adversarial perturbations. Similar, but not identical mathematical constructions have also appeared in the PDE literature. Cesaroni and Matteo (2017) and Cesaroni et al. (2018) consider perturbations to the measure-theoretic boundary of a set. However, the measure-theoretic boundary and the topological boundary behave quite differently. Chambolle et al. (2012) consider problems involving integrals of indicator functions of perturbed sets Aϵ divided by the size of the perturbation. Additionally, Bellettini (2004) and Chambolle et al. (2015) assume some set properties that are satisfied by sets perturbed by ℓp balls, and then use these to show regularity and the curvature of the boundary. Lastly, Bertsekas and Shreve (1996) study the universal σ-algebra in detail, however they did not show that the sets we use in this paper are universally measurable. We prove a new measurability result in Section 5.

heading: 3 Problem Setup
text: We study binary classification with class labels in {−1,+1}. We consider a probability distribution D over Rd × {−1,+1}. For convenience, we denote by η the conditional distribution, η(x) = D(Y = +1|x) for any x ∈ Rd, and by P the marginal, P(A) = D(A × {−1,+1}) for any measurable set A ⊆ Rd. Let f : Rd → R be a function whose sign defines a classifier. Then, for a perturbation set B, the adversarial loss of f is defined as
Rϵ(f) = E (x,y)∼D [ sup h∈B 1y sign(f(x+h))<0 ] where sign(z) = { +1 if z > 0 −1 otherwise .
The adversarial loss has been extensively studied in recent years (Montasser et al., 2019; Tsipras et al., 2018; Bubeck et al., 2018b; Khim and Loh, 2018; Yin et al., 2019), motivated by the empirical phenomenon of adversarial examples (Szegedy et al., 2013). In the rest of the paper, we will find it more convenient to work with an alternative set-based definition of classifiers (and adversarial losses), which we describe below. The function f induces two complementary sets A = {x : f(x) > 0} and AC = {x : f(x) ≤ 0}. Conversely, specifying the set A is equivalent to specifying a function f since we could choose f(x) = 1A(x). In the rest of the paper, we will specify the set of points A classified as +1 rather than the function f . The classification risk of a set A is then expressed as
R(A) = ∫ (1− η(x))1A(x) + η(x)1AC (x) dP. (1)
In the above formulation, it is easy to see that the Bayes optimal classifier is the set A = {x : η(x) > 1 2}. We now extend this viewpoint to adversarial losses. We assume that the adversary knows the classification set A and that the adversary seeks to perturb each point in Rd outside of A, via an additive perturbation in a set B. In typical applications, B is a ball in some norm, and in the rest of the paper we will assume that B = Bϵ(0) is a closed ball with radius ϵ centered at the origin. Next, we define Aϵ to be the set of points that can fall inside A after an additive perturbation of magnitude at most ϵ. Formally, Aϵ = {x ∈ Rd : ∃h ∈ Bϵ(0) for which x+ h ∈ A}. Therefore, we can define the adversarial risk as
Rϵ(A) = ∫ (1− η(x))1Aϵ(x) + η(x)1(AC)ϵ(x) dP. (2)
Pydi and Jog (2019); Bhagoji et al. (2019) also studied the adversarial Bayes classifiers using the ϵ operation. We will now re-write Aϵ in a form more amenable to analysis:
Aϵ = {x ∈ Rd : ∃h ∈ Bϵ(0)|x+ h ∈ A} = {x ∈ Rd : ∃h ∈ Bϵ(0) and a ∈ A|x+ h = a} = { x : ∃h ∈ Bϵ(0) and a ∈ A | a− h = x } = {a− h : a ∈ A,h ∈ Bϵ(0)} = A⊕Bϵ(0),
where the last equality follows from the symmetry of the ball Bϵ(0). From these relations, we can recover a more typical expression of the adversarial loss. Note that 1Aϵ(x) = 1A⊕Bϵ(0)(x) = sup
h∈Bϵ(0) 1A(x+ h), which implies
Rϵ(A) = ∫ (1− η(x)) sup
h∈Bϵ(0) 1A(x+ h) + η(x) sup h∈Bϵ(0) 1AC (x+ h) dP. (3)
The papers (Szegedy et al., 2013; Biggio et al., 2013; Madry et al., 2017) (and many others) use the multi-class version of this loss to define adversarial risk. More specifically, they evaluate the risk on the set A = {f(x) ≥ 0}, where f is a function in their model class. We define the adversarial Bayes risk Rϵ∗ as the infimum of (2) over all measurable sets, and we say that the set A is an adversarial Bayes classifier if Rϵ(A) = Rϵ∗. Note that the integral above is defined only if the sets Aϵ, (AC)ϵ are measurable. This consideration is nontrivial as there do exist measurable sets whose direct sum is not measurable, see (Erdös and Stone, 1970; Ciesielski et al., 2001/2002) for examples.
𝑨𝝐 𝑨 𝑨#𝝐
Figure 1: Sets Aϵ and A−ϵ
with B = B2ϵ (0), the closed ℓ2 ball.
To address this issue, in Section 5, we discuss a σ-algebra called the universal σ-algebra which is denoted U (Rd). Specifically, we show that if A ∈ U (Rd), then Aϵ ∈ U (Rd) as well. Thus, working in the universal σ-algebra U (Rd) allows us to define the integral in (2) and then optimize Rϵ over sets in U (Rd). In particular, throughout this paper, we adopt the convention that P is the completion of a Borel measure restricted to U (Rd). (We elaborate on this construction in Section 5.) We call a set universally measurable if it is in the universal σ-algebra U (Rd). We now introduce another important notation: we define A−ϵ : = ((AC)ϵ)C . The set A−ϵ contains the points that cannot be perturbed to fall outside of A. Figure 1 depicts the sets A,Aϵ and A−ϵ.

heading: 4 Main Results
text: In this section, we prove our main result establishing the existence of the optimal adversarial classifier. We first discuss challenges in establishing this theorem. In the case of the standard 0-1 loss, the risk is defined in (1) where the sets A and AC are disjoint. As a result, the integrand equals either η(x) or (1− η(x)) at each point. Thus the set for which 1− η(x) < η(x) minimizes R. In other words, the Bayes classifier minimizes the objective min(η(x), 1− η(x)) at each point. On the other hand, the same reasoning does not apply to the adversarial risk. The adversarial risk at a single point x depends on all the points in Bϵ(x). Hence, one cannot hope to find the adversarial Bayes classifier by studying the risk in a pointwise manner.
Next, we introduce the concepts of certifiable robustness and pseudo-certifiable robustness. Definition 1. Fix a perturbation radius ϵ. We say that a classifier A is certifiably robust at a point x with radius ϵ if either x ∈ A and Bϵ(x) ⊂ A, or x ∈ AC and Bϵ(x) ⊂ AC . We say that a classifier A is pseudo-certifiably robust at a point x with radius ϵ if either x ∈ A and there exists a ball Bϵ(y) with x ∈ Bϵ(y) and Bϵ(y) ⊂ A or x ∈ AC and there exists a ball Bϵ(y) with x ∈ Bϵ(y) and Bϵ(y) ⊂ AC . We say a classifier A is pseudo-certifiably robust if it is pseudo-certifiably robust with radius ϵ at every point.
In other words, a classifier is certifiably robust at a point x with radius ϵ if the entire ϵ-ball around x is classified the same as x, and a classifier is pseudo-certifiably robust at a point x with radius ϵ if some ball radius ϵ whose closure contains x is classified the same as x. Pseudo-certifiable robustness is a necessary condition for certifiable robustness.
We now discuss potential algorithmic applications of pseudo-certifiable robustness. To begin, we start by defining the set of points at which a classifier is not pseudo-certifiably robust. If we define
F (A) = {x ∈ A : every closed ϵ-ball containing x also intersects AC}. (4) Then, the set of points where a classifier is not pseudo-certifiably robust is F (A) ∪ F (AC).
In Appendix E, we show that if we “subtract" from a classifier the points at which it is not pseudo-certifiably robust, then we get a classifier with lower risk. Formally, we show that Rϵ(A−F (A)) ≤ Rϵ(A) and Rϵ(A∪F (AC) ≤ Rϵ(A) (Lemma 27). Furthermore, Lemma 27 suggests that near the adversarial Bayes classifier, these inequalities are typically strict. As illustrated in Figure 2, F (A), F (AC) are adjacent to the boundary ∂A. Furthermore, F (A) is not very "large" – F (A)−ϵ = ∅. These observations suggest that, typically, if A is not pseudo-certifiably robust, then there is another classifier with lower risk that can be found by making local changes to A.
We now state our main existence result.
Theorem 1. Let P be the completion of a Borel measure on B(Rd) restricted to U (Rd). Let Bϵ(0) be a ball for a norm for which the unit ball is strictly convex or a polytope. Define Aϵ = A⊕Bϵ(0). Then, there exists a minimizer of (2) when minimizing over U (Rd). Furthermore, this minimizer is pseudo-certifiably robust.
For perturbations in many common norms, such as the ℓ1, ℓ2, and ℓ∞ norms, the theorem provides a positive guarantee: for any distribution, the adversarial Bayes classifier exists. In fact, an even stronger result holds: if P is absolutely continuous with respect to the Lebesgue measure, we can show a statement analogous to every minimizing sequence of Rϵ has a convergent subsequence. We formally state and prove this stronger version of our theorem as Theorem 12 in Appendix G.
This result actually holds for all norms. However, the extension of one of our lemmas (Lemma 2) to all norms is not straightforward, and thus we are leaving this result to an extended version of the paper. We also expect an existence result for perturbations by open balls.
Next, we briefly discuss two ways in which our results relate to the consistency of adversarial losses. First, Awasthi et al. (2021) show that when H is the class of linear functions, if the surrogate risk RϵΨ of the adversarial surrogate loss Ψ is zero for a given distribution, then Ψ is H-consistent for that distribution. Furthermore, (Awasthi et al., 2021) give an example of a distribution for which the adversarial loss is nonzero and no continuous surrogate losses can be consistent. The existence of the adversarial Bayes classifier is required for this condition to hold. Next, a surrogate loss Ψ is consistent if a minimizing sequence of functions fi also minimizes 0-1 adversarial loss. However, it may be easier to study minimizing sequences of the Ψ loss when we have information about the adversarial Bayes classifier. Theorem 12 in the appendix lists a variety of conditions under which a minimizing sequence of the adversarial loss approaches an adversarial Bayes classifier in a meaningful sense. Thus, we can find conditions under which {x : fi(x) ≥ 0} approaches a set A. In other words: If Ψ is consistent and fi is a sequence that minimizes the adversarial ϕ loss, then fi ≥ 0 must approach an adversarial Bayes classifier in the sense described by Theorem 12.

heading: 4.1 Proof strategy
text: We first outline the main ideas behind the proof of Theorem 1, which is presented in the next subsection. The proof applies the direct method of the calculus of variations, with an additional step (2a below). Specifically, we apply the following procedure:
1) Choose a sequence of sets {An} ⊂ U (Rd) along which Rϵ(An) approaches its infimum; 2a) Using the sequence {An}, we find a decreasing minimizing sequence {Bn} with nice properties 2b) Extract a subsequence {Bnk} of {Bn} that is convergent in some topology; 3) Show that Rϵ is sequentially lower semi-continuous: for a convergent subsequence {An},
lim inf n→∞ Rϵ(An) ≥ Rϵ( lim n→∞ An).
Classically, the direct method of the calculus of variations consists of 1), 2b) and 3). In typical applications of the direct method, step 2) is almost immediate as it is achieved by working in the appropriate Sobolev space. However, showing step 3) is usually quite difficult. See Dacorogna (2008) for more on the direct method in PDEs. In contrast, in our scenario, the situation is the opposite: finding the right topology for step 2) is quite difficult but the lower semi-continuity is a direct implication of the dominated convergence theorem.
As described above, one of the main considerations in the proof of Theorem 1 is the convergence of set sequences. In order to apply the dominated convergence theorem, we need the indicator functions 1(An)ϵ ,1(ACn )ϵ to converge. With that in mind, we adopt the following standard settheoretic definitions for a sequence of sets {An}:
lim supAn= ⋂ N≥1 ⋃ n≥N An and lim inf An= ⋃ N≥1 ⋂ n≥N An.
See (Rockafellar and Wets, 1998) for further discussion of the intuition behind these definitions. As with lim sup and lim inf for a sequences of numbers, lim inf An ⊂ lim supAn or in other words 1lim inf An ≤ 1lim supAn . With the above definitions, the following holds:
lim inf n→∞ 1An = 1lim inf An and lim sup n→∞ 1An = 1lim supAn .
Specifically, these relations imply that the limit limn→∞ 1AndP exists a.e. if and only if the lim sup and the lim inf of the sequence {An} match up to sets of measure zero under P. We denote equality up to sets of measure zero by .=. In order to find a sequence for which lim inf An . = lim supAn, we first define the measures {Pn} by Pn(B) = P(An ∩ B). The hope is that if Pn converges to a measure Q, this would imply that lim inf An . = lim supAn.
To this end, we apply Prokhorov’s theorem to obtain a subsequence {Pnk} of {Pn} that converges to a measure Q in some sense. The notion of convergence for probability measures discussed in Prokhorov’s theorem is that of weak convergence. In order to extract a sequence An for which the lim inf and the lim sup match, we apply the following lemma to the sequence of measures Pnk . Lemma 1. Let {Pn},Q be measures on Rd. Assume that Pn weakly converges to Q with Pn given by Pn(B) = P(B ∩An) for a sequence of sets An. Then Q(B) = P(A ∩B) for a set A given by
A=̇ lim supAnj =̇ lim inf Anj ,
where {Anj} is some subsequence of An. Furthermore, 1Anj → 1A P-a.e.
The lemma above is proved in Appendix C. The next challenge is that lim inf Aϵn/ lim supA ϵ n do not necessarily equal Aϵ for some set A. However, finding a sequence satisfying this property is not too difficult if the sequence An is in fact decreasing, and Bϵ(0) is either strictly convex or a polytope.
Lemma 2. Let Bn be a decreasing sequence (Bn+1 ⊂ Bn). Let Aϵ = A ⊕ Bϵ(0), where Bϵ(0) is a strictly convex set or a polytope. Then, there exists another decreasing sequence Cn with Rϵ(Cn) ≤ Rϵ(Bn) for which ⋂∞ n=1 Cn is pseudo-certifiably robust at every point and satisfies
∞⋂ n=1 Cϵn = ( ∞⋂ n=1 Cn )ϵ , ∞⋂ n=1 C−ϵn = ( ∞⋂ n=1 Cn )−ϵ .
The lemma is proved in Appendix E. Note that for decreasing sequences of sets, lim inf Cn = lim supCn = ⋂ n≥1 Cn. Thus, using the sequence of sets given by Lemma 2, one can swap the order of the lim, ϵ, and −ϵ operations to conclude
lim inf Cϵn=(lim inf Cn) ϵ and lim inf C−ϵn =(lim inf Cn) −ϵ.
Finally, it remains to show that we can actually apply Lemma 2. This step requires proving that one can find a decreasing minimizing sequence Bn. Subsequently, the inequality Rϵ(Cn) ≤ Rϵ(Bn) of Lemma 2 implies that Cn must be a minimizing sequence when Bn is a minimizing sequence.
Lemma 3. Let An be a minimizing sequence of Rϵ for which lim inf Aϵn=̇ lim supAϵn and lim inf A−ϵn = lim supA −ϵ n . Then, there is a decreasing minimizing sequence Bn, i.e., Bn+1 ⊂ Bn.
We prove the above Lemma in Appendix F. Lemma 1 is used to satisfy the conditions of the lemma.

heading: 4.2 Formal Proof of Theorem 1
text: We now formally prove Theorem 1. We start by introducing three basic tools: weak convergence of probability measures, Prokhorov’s theorem, and inner regularity. We start with weak convergence.
Definition 2. A sequence of measures Qn converges weakly to a measure Q if for all continuous and bounded functions f , limn→+∞ ∫ fdQn = ∫ fdQ.
Given a sequence {Pn}, Prokohrov’s theorem allows one to extract a weakly convergent subsequence. Theorem 2 (Prokohrov’s Theorem). Consider Rd with the Borel σ-algebra B(Rd). A sequence of probability measures {Pn} on the B(Rd) admits a weakly convergent subsequence iff for all ϵ > 0, there exists a compact set K for which the condition Pn(Rd \K) < ϵ holds uniformly for all n.
If for the sequence {Pn}, for all ϵ > 0, there exists a compact set K for which Pn(Rd \ K) < ϵ uniformly for all n, then the sequence Pn is referred to as tight. However, as discussed in Section 3, the σ-algebra U (Rd) which we work with is larger than B(Rd), the σ-algebra present in Theorem 2. To address this technicality, we state a variant of Prokhorov’s Theorem which we prove in Appendix B.
Corollary 1 (Prokhorov’s Theorem). Let (Pn,Rd,U (Rd)) be a sequence of probability measure spaces for which each Pn is the completion of a Borel measure restricted to U (Rd). Then the sequence of measures {Pn} admits a weakly convergent subsequence iff the sequence is tight.
In order to demonstrate that Prokhorov’s theorem applies, we use the concept of inner regularity. Definition 3. Let P be a Borel measure on Rd or its completion. We say that P on Rd is inner regular if P(E) = sup{P(K) : K ⊂ E,K compact}.
The following Lemma states that all probability measures on Rd are inner regular. Lemma 4. Every Borel measure ν on Rd with ν(X) < ∞ is inner regular.
The above lemma is a consequence of Theorem 7.8 and Proposition 7.5 of Folland (1999) and further implies that the completion of every Borel measure on Rd restricted to U (Rd) is inner regular.
Proof of Theorem 1. Let An be universally measurable minimizing sequence. Consider two sequences of measures given by P1n(B) = P(Aϵn ∩ B) and P2n(B) = P(A−ϵn ∩ B). Since P is inner regular, by the comment after Lemma 4, both of these sequences are tight. Furthermore, each Pn is defined on the universal σ-algebra. Thus, we can apply Prokhorov’s Theorem in the form of Corollary 1 to extract weakly convergent subsequences of Pin. In fact, by diagonalization, we can choose the same subsequence for both measures. Specifically, using Prohkorov’s Theorem, we choose a weakly convergent subsequence {P1nk}. Note that the subsequence {P 2 nk } is also tight. This means that we can choose another weakly convergent subsequence {P2nkm }. Therefore both {P 1 nkm
} and {P2nkm} are weakly convergent.
To simplify notation, we drop the triple subscript and let An denote a sequence of sets for which P1n weakly converges to Q1 and P2n weakly converges to Q2. Next we use another diagonalization argument. By Lemma 1, we have
Q1(B) = P(C ∩B) with C=̇ lim supAϵnj =̇ lim inf A ϵ nj
for a subsequence Anj of {An}. Note that for any subsequence Anjk , it still holds that Q1(B) = P(C ∩B) with C=̇ lim supAϵnjk =̇ lim inf A ϵ njk . This statement holds because for any sequence of functions {fj} and any subsequence {fjk}, lim supk→∞ fjk ≤ lim supj→∞ fj and lim infk→∞ fjk ≥ lim infk→∞ fjk . Thus we can apply Lemma 1 to the sequence P2nj to extract a subsequence of indices {njk} for which
Q1(B) = P(C ∩B) and Q2(B) = P(D ∩B) with C=̇ lim supAϵnjk =̇ lim inf A ϵ njk and D=̇ lim supA−ϵnjk =̇ lim inf A −ϵ njk .
Note that Lemma 1 further implies that the convergence is P-a.e., not just weak convergence. Again, for clarity, we drop the triple subscript and refer to Anjk as An. Subsequently, Lemma 3 gives a decreasing minimizing sequence Bn. Next, Lemma 2 produces a decreasing sequence Cn for which
∞⋂ n=1 Cϵn = ( ∞⋂ n=1 Cn )ϵ and ∞⋂ n=1 C−ϵn = ( ∞⋂ n=1 Cn )−ϵ and Rϵ(Cn) ≤ Rϵ(Bn). Since Bn is a minimizing sequence, Cn must be a minimizing sequence as well. Now, pick A = ⋂∞ n=1 Cn. An application of the dominated convergence theorem then gives
inf S∈U (Rd) Rϵ(S) = lim n→∞ ∫ (1− η(x))1Cϵn + (1− η(x))1(C−ϵn )C
= ∫ lim
n→∞
( (1− η(x))1Cϵn + η(x)(1− 1C−ϵn ) ) dP
= ∫ (1− η(x))1⋂∞
n=1 C ϵ n + η(x)
( 1− 1⋂∞
n=1 C −ϵ n
) dP
= ∫ (1− η(x))1(⋂∞n=1 Cn)ϵ + η(x) ( 1− 1(⋂∞n=1 Cn)−ϵ ) dP
= ∫ (1− η(x))1Aϵ + η(x)1(A−ϵ)CdP = Rϵ(A).
Thus, we have found a minimizer of Rϵ. Lastly, by Lemma 2 A is pseudo-certifiably robust.

heading: 4.3 Proof Strategy for Lemma 2
text: In this section, we explain the intuition for the proof of Lemma 2. Appendix E presents the formal proofs. We begin by studying sets of the form Aϵ. From Aϵ = ⋃ a∈A Bϵ(a), one can show⋂
n≥1 A−ϵn = (⋂ n≥1 An )−ϵ (5)
for any sequence of sets {An}. We prove (5) formally in Appendix D. Thus, it remains to find a sequence Cn for which ⋂∞ n=1 C ϵ n = ( ⋂∞ n=1 Cn)
ϵ. With this observation in mind, we first study properties of sets of the form Aϵ. Notably, as Aϵ = ⋃ a∈A Bϵ(a), every point x ∈ Aϵ is contained in
some ball Bϵ(a) which is completely included in Aϵ. Thus, a necessary condition for ⋂∞ n=1 C ϵ n =
( ⋂∞
n=1 Cn) ϵ is that every point in ⋂∞ n=1 C ϵ n must be contained in some ball Bϵ(a) which is completely
included in ⋂∞
n=1 C ϵ n. In the proof of Lemma 2, we show this condition is also sufficient when one
chooses Cn = ((B−ϵn ) 2ϵ)−ϵ. We start by showing (A−ϵ)ϵ = A− F (A). Subsequently, applying (5),( ∞⋂
n=1
Cn
)ϵ = ( ∞⋂ n=1 (( B−ϵn )2ϵ)−ϵ)ϵ
= ( ∞⋂ n=1 (B−ϵn ) 2ϵ )−ϵϵ = ∞⋂ n=1 ( B−ϵn )2ϵ − F ( ∞⋂ n=1 ( B−ϵn )2ϵ)
and then one can argue that Cϵn = (B −ϵ n )
2ϵ. Lastly, we demonstrate that F ( ⋂∞
n=1 (B −ϵ n ) 2ϵ ) = ∅.

heading: 5 Addressing Measurability
text: As mentioned earlier, defining the adversarial loss requires integrating over Aϵ. However, one must ensure that Aϵ is measurable. Furthermore, in the proof of Lemma 2, we apply the ϵ,−ϵ operations multiple times in succession. In particular, we consider sets of the form ((A−ϵ)2ϵ)−ϵ. Hence we would like to work in a σ-algebra Σ for which if A ∈ Σ, Aϵ ∈ Σ as well. Below, we explain that a σ-algebra called the universal σ-algebra satisfies this property.
We follow the treatment of Nishiura (2010) for our definitions. Let B(Rd) be the Borel σ-algebra on Rd and let ν be a measure on this σ-algebra. We will denote the completion of the measure space (ν,Rd,B(Rd)) by (ν,Rd,Lν(Rd)) where Lν(Rd) is the σ-algebra of Lebesgue measurable sets. Let M (Rd) be the set of all σ-finite Borel measures on Rd. Then we define the universal σ-algebra as U (Rd) = ⋂ ν∈M (Rd) Lν(Rd). In other words, U (Rd) is the sets which are measurable under every complete σ-finite Borel measure. One can verify that an arbitrary intersection of σ-algebras is indeed a σ-algebra, so that U (Rd) is in fact a σ-algebra. For the universal σ-algebra, we have the following theorem proved in Appendix A:
Theorem 3. If A ∈ U (Rd), then Aϵ ∈ U (Rd) as well.
Specifically, Theorem 3 allows us to define the adversarial risk in Equation (2). Recall that for a probability measure Q, by definition U (Rd) ⊂ LQ(Rd). Therefore, if A ∈ U (Rd), then Aϵ is measurable with respect to (Q,Rd,LQ(Rd)). However, as this only holds for A ∈ U (Rd) and not all of LQ(Rd), throughout this paper, we implicitly assume that our measure space is (Q,Rd,U (Rd)). In other words, we assume that the probability measure P is the complete measure Q restricted to the σ-algebra U (Rd). As U (Rd) is closed under the ϵ,−ϵ operations, this convention allows us to mostly ignore measurability considerations.
Results similar to Theorem 3 appear in the literature, but are inadequate for our construction. For instance, Proposition 7.50 of Bertsekas and Shreve (1996) implies that if A is Borel measurable, then Aϵ is universally measurable. However, as discussed earlier in this section, this result does not suffice because we need to show that for a σ-algebra Σ, A ∈ Σ implies that Aϵ ∈ Σ as well.

heading: 6 Alternative Models of Perturbations
text: In this paper, we developed techniques for proving the existence of the adversarial Bayes classifier on Rd with additive perturbations. Our techniques could be applied to other natural models of perturbations. In Appendix G, we state a general theorem that summarizes the part of our theory that is applicable beyond additive perturbations. Below, we discuss three notable examples. Example 1 (Elementwise Scaling). For x ∈ Rd, we perturb each coordinate by multiplying it by a number in [1− ϵ, 1 + ϵ]. Thus, to perturb x, we multiply it elementwise by another vector in B∞ϵ (1).
(Engstrom et al., 2019) studied the following perturbation empirically in image classification tasks. Example 2 (Rotations). Let x ∈ Rd. We perturb x by multiplying it by a “small" rotation matrix R. We define our perturbation set this time as the set of matrices with
B = { R : sup
∥x∥2=1 x ·Rx ≥ 1− ϵ
} .
Our final example is inspired from applications in natural language processing (Ebrahimi et al., 2018). Example 3 (Discrete Perturbations). Let A be an alphabet. For an input string x, consider perturbations that replace a character of x at a given index with another character in A.
The above perturbation models have a lot in common with additive perturbations in Rd. All three are examples of semigroup actions, and in fact the first two are group actions. Furthermore, all three involve metric spaces. Lastly, denoting a perturbed set as Aϵ, we still have the containments( ∞⋃
i=1
Ai
)ϵ =
∞⋃ i=1 Aϵi and ( ∞⋂ i=1 Ai )ϵ ⊂ ∞⋂ i=1 Aϵi . (6)
Many aspects of the theory developed in this work are applicable in more general scenarios. In Appendix G.1, we prove the existence of the adversarial Bayes classifier for a simpler version of Example 3 using the techniques we developed in this paper. Proving the existence of the adversarial Bayes classifier for the other two examples remains an open problem.
Note that the proof of Theorem 1 only depends on Lemmas 1, 2, and 3, and not on the properties of Rd. Thus in order to generalize our main theorem, one needs to generalize the three lemmas. Lemma 3 follows from the containments in (6) and Lemma 1 can be extended to separable metric metric spaces. Thus it remains to generalize both the measurability considerations and Lemma 2 on a case-by-case basis. Regarding measurability, we prove a more general version of Theorem 3 in Appendix A (Theorem 4) which applies to perturbations given by a metric ball in a metric space. Lastly, our tools may be useful for proving Lemma 2 in other scenarios and we discuss in Appendix G.

heading: 7 Conclusion
text: We initiated the study of fundamental questions regarding the existence of adversarial Bayes optimal classifiers. We provided sufficient conditions that ensure the existence of such classifiers when perturbing by an ϵ-ball. More importantly, our work highlights the need for new tools to understand Bayes optimality under adversarial perturbations, as one cannot simply rely on constructing pointwise optimal classifiers. Our paper also introduces several theorems which could be useful tools in further theoretical work. Specifically, Appendices D and E study properties of adversarially perturbed sets, and Appendix A gives some conditions under which adversarially perturbed sets are universally measurable. Both of these results may be useful in other contexts.
Similar to the case of standard loss functions, the most interesting extension of our work is to formulate and study questions related to the consistency of surrogate loss functions for adversarial robustness. We hope that this line of study will lead to new practically useful surrogate losses for designing adversarially robust classifiers.

heading: Acknowledgements
text: This work was partly funded by NSF CCF-1535987 and NSF IIS-1618662. Special thanks to Professor James A. Morrow for some useful pointers on measurability.

Review summaries:
This paper establishes the existence of a binary classifier which minimizes the expected adversarial loss under a data and label distribution, which they call the adversarial Bayes classifier. The authors do so by constructing a sequence of classifiers which converges to the infimum risk, and then demonstrate that the risk is sequentially lower semi-continuous, which establishes the existence of a minimum. They also extend this result to some non-additive perturbations.

This paper studies a fundamental question regarding the adversarial Bayes classifier, i.e., does the optimal Bayes classifier exists and does it have any robustness guarantee. The contribution of this paper is theoretical: it proposes the concept of ‘pseudo-certifiable robustness’ and proves that the optimal Bayes classifier exists and satisfies the proposed ‘pseudo-certified robustness’. The proofs are mostly about real analysis and measure theory.