On the Existence of The Adversarial Bayes Classifier
Authors: Pranjal Awasthi
Natalie Frank
Mehryar Mohri
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: Adversarial Learning
Learning Theory
Consistency
Calibration
Bayes classifiers

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.

On The Existence of The Adversarial Bayes Classifier
Pranjal Awasthi Google Research New York, NY 10011, USA
Natalie S. Frank Courant Institute New York, NY 10012 10666006...eeem edu
pranjallwwathhigooggleccc
Mehryar Mohri
Google Research & Courant Institute New York, NY 10011, USA
mohri@google.com
Abstract
Adversarial robustness is critical property in variety of modern machine learning applications. While it has been the subject of several recent theoretical studies, many important questions related to adversarial robustness 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 useful tool for a subsequent study of surrogate losses in adversarial robustness and their consistency properties.
Introduction
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 al., 2013). slightly perturbed picture of dog could be misclassified phenomenon appears with other types of data such as biosequences, text, or speech. This problem has motivated 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 al., 2017; Schmidt et al., 2018; Athalye et al., 2018; Bubeck al., 201 0018b; Montasser et al., 2019).
The same
In the context classification problems, instead of the standard zero-one loss, an adversarial zero-one only if it misclassifies input but also if it
loss has been adopted which penalizes classifier does not maintain the correct z-label a e-neighborhood around x (Goodfellow et al., 2014; Madry al., 2017; Tsipras et al., 2018; Carlini and Wagner, 2017). Since optimizing the adversarial zero-one loss is computationally intractable, common approach for adversarial learning is to use a surrogate loss instead. However, optimizing surrogate loss over class of functions may not always lead to minimizer of the true underlying loss over that class. In the case of the standard zero-one loss, there is large body of literature identifying conditions under which surrogate losses consistent, that is. minimizing them over the family of all measurable functions leads to minimizers of the true loss (Zhang, 2004; Bartlett 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 surrogate loss can be H-consistent for a particular family H. without being consistent for all measurable functions.
When are adversarial surrogate losses H--consittntt? This problem is already non-trivial for the standard zero-one loss: while there are well-known results for the consistency losses for the zero-
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

one loss such as (Bartlett et al., 2006; Steinwart, 2005), these results do not hold for H-consisteney. Existing theoretical results for H-consistency assume that the Bayes risk 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 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-coosistenccy 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, N-coosistency 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 minimizer, which we call the adversarial Bayes classifter. 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 al., 2006). To illustrate this better, consider the case of binary classification where on a given input 2; 77(z) denotes the conditional class probability, that is, .7(x) = Py 1 æ)). In this case, is well-known that the Bayes optimal classifier can be obtained by making optimal predictions per point in the domain: at a point z predict 1 if n(z)= 2 }. -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 l norm. Then, for given labeled point (ar, y) and perturbation radius e, the adversarial zero-one loss of a classifier f is defined as maxx': ||a"- 1 (f(')) & y). Thus, the loss at a point x cannot be measured simply by inspecting the prediction of the classifier at æ. 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 approximate the conditional probability of 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; Bhattccarree 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.
second related concept is certified robustness. A point x is certifiably robust for a classifier f and a perturbation radius e 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 sscudo-certified robustness condition for 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-certifiabe Peres (2020) prove that for 2-norm perturbations, the boundary of pseudo-certifably robust set is differentiable and has Lipschitz normals.
robust is typically not optimal. Lastly, Lewicka and
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 & in the & 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 seeudo-certifialle robustness during or after training. Recent works have explored constructing certificates of robustness as well (Raghunathan
2

---

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 first step towards this broader goal.
We now describe the organization of the paper. Section 2 summarizes related work and Section presents the mathematical formulation of our problem. Section 4 discusses our main result and the proof. Next, Section addresses the measurability issues relating to this problem. Section 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 's theorem that is essential for our proofs. Next, in Appendix C, we prove one of our key lemmas. Appendicies A, and 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 Lastly, Appendix G states and proves two generalizations of our main result.
2 Related Work
Existing theoretical work on adversarial robustness focuses on questions such as adversarial coun- terparts of VC-dimension and Rademacher complexity (Cullina 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 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 PAC-style model) using exp(d) many samples.
Bubeck et al. (201 8b,a) provide evidence of computational barriers in adversarial learning by con- structing 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 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 lp 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 set and an e-ball, which we use model adversarial perturbations. Similar, but not identical mathematical constructions have also appeared in the PDE literature. Cesaroni and Mattco (2017) and Cesaroni al. (2018) consider perturbations the measure-theoretic boundary of a set. However, the measure-theoree 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 l, balls, and then use these to show regularity and the curvature of the boundary. Lastly, Bertsekas and Shreve (1996) study the universal olalgebra in detail, however they did not show that the sets we use this paper are universally measurable, We prove new measurability result in Section 5.
3

---

3 Problem Setup
We study binary classification with class labels in {-1, +1}. We consider probability distribution D over IRd x {-1,+1 For convenience, we denote by the conditional distribution, ry(x) D(Y = + +Ixx) for any x E IR and by I' the marginal, P(A) = (A x {-1,+1) +13) for any measurable set S Rd. Let f: Rd R be function whose sign defines a classifier. Then, for perturbation set B. the adversarial loss of f is defined as
+1 if = where sign(=)= 1-1 otherwise
(E)
E sup 1 (lg)((((+b))))< (a.y)~
heB
The adversarial loss has been extensively studied in recent years (Montasser et al., 2019; Tsipras 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 classifiers (and adversarial losses),
which we describe below. The function induces two complementary sets A (x: [(x 0} and
AC [x: ((x S 0}. Conversely, specifying the set equivalent to specifying a function
since we could choose [(x) 1 (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 set A is then expressed as
R(A) f (1- (1- (1-m(x))(A(x)) + ( (x) dP.
(1)
In the above formulation, it is easy to see that the Bayes optimal classifier the set A= (x: r7(x)) > }) 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 a ball some norm, and in the rest of the paper we will assume that B = (0) is a closed ball with radius e centered at the origin. Next, points that can fall inside A after an additive perturbation of magnitude
we define A to be the most e. Formally, A fx Rd 3h (0) for which + A}. Therefore. we can define the adversarial risk as
Rs (A(A) = / (1- (xx)) + ((xx) dP.
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 analysis:
(x Rdd 3h (, and A|x h a} - x = aa- a B.) A (0), A {x E Rd: 3h (, h A}
xx: The E (0) and A
where the last equality follows from the symmetry of the ball (0). From these relations, we can recover a more typical expression of the adversarial loss. Note that 1xx(x) ABB,(o) (x) sup SuP 1x(x + h), which implies
|(L (1-n(x) sup LA(x + h) + n(x) sup bEB,(O)
R
1 4 h) dP.
he
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 define adversarial risk. More specifically, they evaluate the risk the set A = [f(x) 2 0}. where f is function in their model class.
We define the adversarial Bayes risk RE as the infimum of (2) over all measurable sets, and we say that the set A is an adversarial Bayes classifier (A) that the integral above is defined only if the sets AS, are measurable. This con- sideration nontrivial as there do exist measurable sets whose direct sum is not mea- surable, (Erdös and Stone, 1970; Ciesielski et al., 2001/2002) for examples.
R. Note

---

To address this issue, in Section 5, we discuss a o-algebra called the universal o-algebra which denoted V (Rd). Specifically, we show that if A V (RR), then A E V (R.)) as well. Thus, working in the universal o-algebra V/ (RR) allows to define the integral in (2) and then optimize Rt over sets in V (R4). In particular, throughout this paper, we adopt the convention that the completion of Borel
A
A
A-
measure restricted to 2 (IR"). (We claborate on this construction in
Section 5.) We call a set universally measurable if is in the universal o-algebra V (..
Figure 1: Sets A and A- with B (²) the closed &g ball.
We now introduce another important notation: we define A= ((A The set A contains the points that cannot be perturbed to fall outside of A. Figure depicts the sets A, A' and S..
4
Main Results
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 (I) where the sets A and A are disjoint. As a result, the integrand equals either 17(x) or
- ())) each point. Thus the set for which 7)(x) n7(x) minimizes R. In other words, the Bayes classifier minimizes the objective min(1((x), 1 - ) at each point.
On the other hand, the same reasoning does not apply to the adversarial risk. The adversarial risk at single point depends on all the points in (x) Hence, 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 perturbation radius e. We say that a classifier
certifiably robust at point
with radius c if either x E A and (x) C A, or x E A and (x(x) C A We say that a classifier A is pseudo-certifiably robust at a point x with radius if either x E A and there exists a ball (y) with x E (y) and (y) C A or x E AC and there exists a ball (.(y) with x E B.(y) and B (y) C. AC. We say classifier A is pscudo-certifably robust if it is pseudo robust with radius e at every point.
In other words, classifier is certifiably robust at point x with radius if the entire e-ball around x classified the same as x. and classifier pseudo-certifiably robust at a point x with radius e some ball radius whose closure contains x is classified the same as x. Pscudo-certifiable robustness 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 which a classifier is not pseudo-certifaat robust. If we define
F(A) fx E A every closed c-ball containing also intersects A²).
(4)
Then, the set of points where classifier is not pseudo-certifiably robust is F(A) U F(A)) In Appendix E. we show that we "subtract" from a classifier the points at which it is not ceuudo-certfiablly robust, then we get a classi- fier with lower risk. Formally, we show that R (A- F(A)) < R (A) and Re (A U F(AC) < Re (A) (Lemma 27). Furthermore, Lemma 27 suggests that near the adversarial Bayes classifier, these incqualities are typically strict. As illus- trated in Figure 2, F F are adjacent to the boundary OA. Furthermore, F(A) is not very "large" " - F(A) = 0. These observations sug- gest that, typically, if A is not seeudo-certifiable robust, then there is another classifier with lower risk that can be found by making local changes to A.
F(AS)
F(A)
Figure 2: The figure illustrates a set A with the sets F(A) and F(AC) roughly indicated. For a point E F(A), every closed e-ball containing a also intersects AC while for a E F(A every closed e-ball containing also intersects A.
We now state main existence result.
5

---

Theorem 1. Let P be the completion of a Borel measure on B(B²) restricted to V (R*). Let (0) be a ball for norm for which the unit ball is strictly convex polytope. Define A = A + (0). Then, there exists minimizer of (2) when mininizing over V (IR"). Furthermore, this minimizer is pseudo-certifabby robust.
For perturbations in many common norms, such as the L 6,, and &oo norms, the theorem provides positive guarantee: for any distribution, the adversarial Bayes classifier exists. In fact, an even stronger result holds: if IP is absolutely continuous with respect to the Lebesgue measure, we can show 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 Re of the adversarial surrogate loss & is zero for a given distribution, then H-consistent for that distribution. Furthermore, (Awasthi et al., 2021) give an example of distribution for which the adversarial loss is nonzero and no continuous surrogate losses can be consistent. The existence the adversarial Bayes classifier is required for this condition to hold. Next, surrogate loss V is consistent a minimizing sequence of functions ft also minimizes 0-1 I adversarial loss. However, it may be easier to study minimizing sequences of the V 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 Thus, we can find conditions under which {x: fx() 2 0} approaches a set A. In other words: If y consistent and a sequence that minimizes the adversarial loss, then Si must approach an adversarial Bayes classifier in the sense described by Theorem 12.
adversarial Bayes classifier in meaningful sense.
4.1 Proof strategy
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} c. 2 (R²) along which R (A,)) approaches its infimum;
2a) Using the sequence }, we find decreasing minimizing sequence {B,, with nice properties
2b) Extract subsequence (Bn,} } of {Bx} that is convergent in some topology;
3) Show that R is sequentially lower semi-continuous: for a convergent subsequence (An}: }.
lim inf R (A,,) 2 R lim A,). n-+00
-00000
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 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 direct implication of the dominated convergence theorem.
As described above, one of the main considerations in the proof of Theorem is the convergence of set sequences. In order to apply the dominated convergence theorem, we need the indicator functions 1(A,,)' ((g)) to converge. With that in mind, we adopt the following standard set- theoretic definitions for sequence of sets {An):
limsup An N U An and lim inf A, N21
U n A.. N21
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 A,, C limsup, A, or in other words lim inf A., < Im sup A.- With the above definitions, the following holds:
lim inf 1
Lim inf A, and sup 1 AA, = Lim sup A.
700
n 20

---

Specifically, these relations imply that the limit lim,-+00 LA, dIP exists a.e. if and only if the lip and the lim inf of the sequence {A,] match up to sets of measure zero under P. We denote equality up to sets of measure 7ero by =. In order to find a sequence for which lim inf A, = lim sup An. we first define the measures (Pn). by IP, (B) = P(A,, n B). The hope is that if P,, converges to measure Q this would imply that lim inf A, = lim A,.
To this end, we apply Prokhorov's theorem obtain subsequence (..,,) of [PP.] 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 sequence A, for which the lim inf and the lim sup match, we apply the following lemma to the sequence of measures Fng.
J. Q be measures on R... Assume that P,, weakly converges to Q with P, given Lemma 1. Let [PPn,
by (B) = P(B n An) for a sequence of sets An. Then Q(B) P(An B) for a set A given by
A liimssu An, -lim inf Ang
where (Any) } is some subsequence of An. Furthermore, 1 An, - A P-a.e
The lemma above is proved in Appendix C. The next challenge is that lim inf A lim sup AS, do necessarily equal A for some set A. However, finding a sequence satisfying this property is not too difficult if the sequence A, is in fact decreasing, and B (0) is either strictly convex or a polytope.
Lemma 2. Let Bn be decreasing sequence (Ba+1 C Bn). Let A A B.( where (0 is strictly convex set or polytope. Then, there exists another decreasing sequence Cn with R (Cn) S R (Bn) for which m==1 On pseudo-certifiably robust at every point and satisfies
20
C
n
Cn
C
n
Cn
The lemma is proved in Appendix E. Note that for decreasing sequences of sets, inf Cn limsup Cn = O221 On. Thus, using the sequence of sets given by Lemma 2, one can swap the order of the lim, 5, and operations to conclude
lim inf C = (lim inf C,) and lim inf C (lim inf CT
Finally, it remains to show that we can actually apply Lemma This step requires proving that one can find a decreasing minimizing sequence B, Subsequently, the inequality R (C..) S. R (B,) of Lemma 2 implies that On must be a minimizing sequence when B,, a minimizing sequence.
Lemma 3. Let An be minimizing sequence of R for which lim inf AS lim sup A and lim inf A = lim sup A,S. Then, there is a decreasing minimizing sequence B,, i.e. Bu+1 C. B
We prove the above Lemma in Appendix F. Lemma is used to satisfy the conditions of the lemma.
4.2 Formal Proof Theorem
We now formally prove Theorem 1. We start by introducing three basic tools: weak convergence of probability measures, Prokhorov's 's theorem, and inner regularity. We start with weak convergence. Definition 2. sequence of measures Qn converges weakly to a measure Q for all continuous and bounded functions f, lim,->+oo J fdQ,. = J fdQ.
Given a sequence [.,,). Prokohrov's 's theorem allows one to extract a weakly convergent subsequence.
Theorem 2 (Prokohrov's Theorem). Consider Rdd with the Borel a-algebra B(Rd). A sequence of probability measures {P.} on the (( admits a weakly convergent subsequence for all > 0, there exists a compuct set K for which the condition P,, (Rd K) < holds uniformly for all n.
for the sequence [Pr]. for e > 0, there exists a compact set K for which P. (RR K) < uniformly for all n, then the sequence P,, is referred to as tight. However, discussed in Section 3, the r-algebra 2/ (Rd) which we work with is larger than (RR)),, the o-algebra present Theorem 2. To address this technicality, state variant of Prokhorov's 's Theorem which prove in Appendix B.
7

---

(R be a sequence of probability measure Corollary 1 (Prokhorov's Theorem). Let (P,, R,, R
spaces for which each n,, is the completion of a Borel measure restricted to W (RR). Then the sequence of measures 3 admits a weakly convergent subsequence iff the sequence is tight.
In order demonstrate that Prokhorov's theorem applies, Definition 3. Let P be Borel measure on Rd or its completion. We say that P on IR is inner regular iFIP(E) (u){ K C E, K compact).
the concept of inner regularity.
The following Lemma states that all probability measures on Rd are inner regular. Lemma 4. Every Borel measure v on R with vXX < oo 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 V/ (RR") is inner regular.
Proof of Theorem I. Let An be universally measurable minimizing sequence. Consider two se- quences of measures given by PA (B) P(A,, n B) and P (B) = P(A B). Since IP is inner regular, by the comment after Lemma 4, both of these sequences are tight. Furthermore, each P,, defined on the universal o-algebra. Thus, can apply Prokhorov's Theorem in the form of Corollary to extract weakly convergent subsequences of IP; In fact, by diagonalization, we can choose the same subsequence for both measures. Specifically, using Prohkorov's Theorem, choose a weakly convergent subsequence (PL n. J. Note that the subsequence {IP nu } is also tight. This means that we can choose another weakly convergent subsequence {I22 nu... }. Therefore both {P m } and
{IP2 (IP....) are weakly convergent.
To simplify notation, we drop the triple subscript and let An denote sequence of sets for which PA weakly converges Q' and TP? weakly converges to Q Next we use another diagonalization argument. By Lemma 1, we have
Q (B) PCCnB) with C= C-lim lim A - lim inf As,
for a subsequence An, of {An}. Note that for any subsequence Ani, it still holds that
Q²( = IP(C n B) with C=mim sup Ah,, = lim inf Anyy
This statement holds because for any sequence of functions {ff} and any subsequence {fj, }. lim -oo fy. S lim limsup; fj and lim inf fis 2 lim inf fja- Thus we can apply Lemma to the sequence n, to extract subsequence of indices {nz, } for which
@ (B) PP B) and QB = P(D B)
with C= lim sup A = lim inf A and D= lim sup A, = lim inf Anj.
Note that Lemma further implies that the convergence is P-a.e., not just weak convergence. Again, for clarity, we drop the triple subscript and refer Anj, as A,, Subsequently, Lemma gives decreasing minimizing sequence B,, Next, Lemma 2 produces decreasing sequence C, for which
Do
20
oc and n
xC
N
CH
n
Cn
n
C
and R (C,) < Rd (B,). Since Bn is minimizing sequence, Cn must be minimizing sequence as well. Now, pick A = n Cn. An application of the dominated convergence theorem then gives
f (1 (11-nxx)) m(x)) + (1- (1-n(x))4(cc577
inf (S) lim Se (Rd)
n-on
lim ((1 (1-7(x))11e ()(x)) + (x)) 1 dp
n(x)) c₁ + (xx) (1 1 1 Cn c..)) )TP
(1 - n(x)) (n= c.)² + n(x) (1 1 [ Cz) ))
/ ((x)) nxx) (A- godf (A).
8

---

Thus, we have found minimizer of R Lastly, by Lemma 2 A is pseudo-certifably robust.
4.3 Proof Strategy for Lemma 2
In this section, we explain the intuition for the proof of Lemma 2. Appendix presents the formal proofs. We begin by studying sets of the form A From A UnEa B.(a), one can show
(N Am n21
A
(5)
12
any sequence of sets {.a}. We prove (5) formally Appendix D. Thus, it remains to find sequence Cn for which On= C% (N==1 C.) With this observation in mind, we first study properties of sets of the form A Notably, A UaEA (a(a), every point A is contained in some ball (a) which is completely included in A Thus, a necessary condition for O C = (Na=1 Cn) is that every point in N== Cü must be contained in some ball B, (a) which is completely included in N Cū In the proof of Lemma 2, show this condition is also sufficient when one We start by showing (A ()= = A - F(A). Subsequently, applying (5),
chooses C₂ (Bxz)
2
n
00
n Cn
((
00
0 B 9
(2
[B,
n=1
h==
and then one can argue that C (2, Lastly, we demonstrate that F(N (B,r)²²)
Addressing Measurability
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 s, operations multiple times in succession. would like to work in a olalgebra Σ for which if A E Σ, A E E as well. Below, we explain that o-algebra called the universal a-algebra satisfies this property.
particular, we consider sets of the form ((A ((A-))²))- Hence we
We follow the treatment of Nishiura (2010) for our definitions. Let ((R))) be the Borel o-algebra on Rd and let v be a measure on this olalgebra. We will denote the completion of the measure space (v, Rd B(RR)) by (V, R. Ly (R where (Rd)) ) is the o-algebra of Lebesgue measurable sets. Let Al (Rd) be the set of all o-finite Borel measures on Rdd Then we define the universal o-algebra as V (Rd) = Nwe (R (R.)). In other words, V/ (RR) is the sets which are measurable under every complete o- o-finit Borel measure. One can verify that an arbitrary intersection of o-algebras is indeed alalgebra, so that 2 (Fd) is in fact o-algebra. For the universal o-algebra, we have the following theorem proved in Appendix A:
Theorem 3. If E W (Rd), then A e V (R2) as well.
Specifically, Theorem 3 allows us to define the adversarial risk in Equation (2). Recall that for
probability measure Q, by definition W (Rd) c LQ(R).. Therefore, if A E W/ (Rd), then A is measurable with respect to (Q, Rdd Lq (R))). However, as this only holds for A E W [Rd) and not all of (RC),, throughout this paper, we implicitly assume that our measure space is Rd 2 ()d)). In other words, we assume that the probability measure IP is the complete measure Q restricted to the o-algebra 2/ (Rd). , As % (Rd)) is closed under the 5, -e operations, this convention allows us to mostly ignore measurability considerations.
Results similar to Theorem 3 appear 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 this section, this result does not suffice because need to show that for o-algebra Σ, A Σ implics that A Σ as well.

---

6 Alternative Models of Perturbations
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 general theorem that summarizes the part of our theory that is applicable beyond additive perturbations. Below, we discuss three notable examples.
Example (Elementwise Scaling). For x E Rd, we perturb each coordinate by multiplying it by number in e, 1+ Thus, to perturb x, 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 E Rdd We perturb x by multiplying it by a "small" rotation matrix R. We define perturbation this time the set of matrices with
B R:
sup |||||==
Rx 1x
Our final example is inspired from applications in natural language processing (Ebrahimi al., 2018). Example 3 (Discrete Perturbations). Let A be alphabet. For an input string æ, consider perturba- tions that replace character of al a given index with another character in A.
The above perturbation models have lot in common with additive perturbations in R. 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 A", we still have the containments
(UA))
U
oC and (
A
4
OC
AS
(6)
Many aspects of the theory developed in this work applicable in more general scenarios. In Appendix G.I, we prove the existence of the adversarial Bayes classifier for a simpler version of Example 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 only depends on Lemmas 1, 2, and 3, and not on the properties of Rdd Thus in order to generalize our main theorem, one needs generalize the three lemmas. Lemma 3 follows from the containments in (6) and Lemma I can be extended to separable metric metric spaces. Thus it remains to generalize both the measurability considerations and Lemma on case-by-case basis. Regarding measurability, we prove 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.
7 Conclusion
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 e-ball. More importantly. our work highlights the need for new tools to understand Bayes optimality under adversarial perturbations, 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 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 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.
10

---

Acknowledgements
This work was partly funded by NSF CCF-1535987 and NSF I1S-1618662. Special thanks to Professor James A. Morrow for some useful pointers on measurability.
References
A. Athalye, N. Carlini, and D. Wagner. Obfuscated gradients give false sense of security; Circum- venting defenses to adversarial examples. arXiv preprint arXiv:1802. 00420, 2018.
1. Attias, A. Kontorovich, and Y. Mansour. Improved generalization bounds for robust learning. arXiv preprint arXiv:1810.021800 2018.
Awasthi, Frank, and M. Mohri. Adversarial learning guarantees for linear hypotheses and neural networks. arXiv preprint arXiv:2004. 13617, 2020.
P. Awasthi, N. Frank, A. Mao, M. Mohri, and Y. Zhong. Calibration and consistency of adversarial surrogate losses. NeurIPS, 2021.
H. Bao, C. Scott, and M. Sugiyama. Calibrated surrogate losses adversarially robust classification. arXiv preprint arXiv:2005. 13748, 2020.
P. L. Bartlett, M. I. Jordan, and J. D. McAuliffe. Convexity, classification, and risk bounds. Journal of the American Statistical Association, 101(473), 2006.
L.. Bartlett, S. Bubeck, and Cherapanamjeri. Adversarial examples in multi-layer random relu networks. CoRR, 2021.
G. Bellettini. Anisotropic and crystalline mean curvature flow. MSRI publications, 2004.
D. P. Bertsekas and S. E. Shreve. Stochastic Optimal Control: The Discrete-Time Case. Athena Scientific, 1996.
A. N. Bhagoji, D. Cullina, and P. Mittal. Lower bounds on adversarial robustness from optimal transport. In Advances in Neural Information Processing Systems, pages 7498-7510, 2019.
R. Bhattacharjee and K. Chaudhuri. When are non-parametric methods robust? ICML, 2020.
B. Biggio, I. Corona, D. Maiorca, B. Nelson, N. Šmdić, P. Laskov, G. Giacinto, and F. 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.
P. Billingsley. Convergence of Probability Measures. Wiley Series in Probability and Statistics. Wiley, 2nd edition, 1999. ISBN 0-471-19745-9,
S. Bubeck, Y. T. Lee, E. Price, and Razenshteyn. Adversarial examples from cryptographic pseudo-random generators. arXiv preprint / 2018a.
S. Bubeck, E. Price, and Razenshteyn. Adversarial examples from computational constraints. arXiv preprint arviv: 1805. 10204, 2018b.
N. Carlini and D. Wagner. Towards evaluating the robustness neural networks. In 2017 ieee symposium security and privacy (sp). pages 39-57. IEEE, 2017.
A. Cesaroni and N. Mattco. Isoperimetric problems for nonlocal perimeter of minkowski type. arXiv preprint arXiv: 17090052944 2017.
A. Cesaroni, D. Serena, and Matteo. Minimizers for nonlocal perimeters of minkowski type. SpringerLink, 2018
A. Chambolle, M. Morini, and M. Ponsiglione. A non-local mean curvature flow and its semi-implicit time-discrete approximation. SIAM Journal on Mathematical Analysis, 2012.
A. Chambolle, M. Morini, and M. Ponsiglione. Nonlocal curvature flows. Archive for Rational Mechanics and Analysis,
2015.

---

K. Ciesielski, H. Fejzić, and C. Freiling, Measure zero sets with non- mon-uaasueeble sum. Real Analysis Exchange, 2001/2002.
M. Cohen, E. Rosenfeld, and J. Z. Kolter. Certified adversarial robustness via randomized smoothing. CoRR, 2019.
D. Cullina, A. N. Bhagoji, and P. Mittal. Pac-learning in the presence of evasion ad versaaries. arXiv preprint arXiv: 01471, 2018
B. Dacorogna. Direct Methods in the Calculus of Variations. Springer, 2008
A. Degwekar, P. Nakkiran, and V. Vaikuntanathan. Computational limitations in robust classification and win-win results. In Proceedings of the Thirty-Second Conference on Learning Theory, pages 994-1022 2019.
D. Diochnos, S. Mahloujifar, and M. Mahmoody, Adversarial risk and robustness: General definitions and implications for the uniform distribution. In Advances in Neural Information Processing Systems, pages 10359-10368. 2018
Ebrahimi, A. Rao. D. Lowd, and D. Dou. HotFlip: White-box adversarial examples for text classification. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers). Association for Computational Linguistics, jul 2018.
L. Engstrom, B. Tran, D. Tsipras, L. Schmidt, and A. Madry. Exploring the landscape of spatial robustness. In International Conference on Machine Learning, pages 1802-1811. PMLR, 2019.
P. Erdös and A. H. Stone. On the sum of two borel sets. Proceedings of the American Mathematical Society, 1970.
U. Feige, Y. Mansour, and R. Schapire. Learning and inference in the presence of corrupted inputs. In Conference on Learning Theory, pages 637-657, 2015.
U. Feige, Y. Mansour, and R. E. Schapire. Robust inference for multiclass classification. In Algorithmic Learning Theory, pages 368-386, 2018.
G. B. Folland. Real analysis: modern techniques and their applications, volume 40. John Wiley & Sons, 1999.
I. J. Goodfellow, Shlens, and C. Szegedy. Explaining and harnessing adversarial examples. arXiv preprint arXiv: /4f.. 1412.6572, 2014.
J. Khim and P.-L. Loh. Adversarial risk bounds via function transformation. arXiv preprint arXiv: 1810.09599, 2018.
M. Lewicka and Y. Peres. Which domains have two-sided supporting unit spheres at every boundary point? Expositiones Mathematicae, 38(4):548 558,, 2020.
Y. Lin. A note margin-based based loss functions in classification. Statistics & Probability Letters, 68 (1):73-82, 2004. ISSN 0167-7152.
Long and R. Servedio. Consistency versus realizable H-consistency for multiclass classification. In International Conference on Machine Learning, pages
2013.
A. Madry, A. Makelov, L. Schmidt, D. Tsipras, and A. Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint 1rXiv:7706.06083 2017.
O. Montasser, Hanneke, and N. Srebro. VC classes are adversarially robustly learnable, but only improperly. arXiv preprint
2019.
P. Nakkiran. Adversarial robustness may be at odds with simplicity. arXiv preprint arXiv:1901.005: 2019.
Nishiura. Absolute Measurable Spaces. Cambridge University Press, 2010.
M. S. Pydi and V. Jog. Adversarial risk via optimal transport and optimal couplings. arXiv preprint arXiv:1912.02294, 2019.
12

---

A. Raghunathan, J. Steinhardt, and P. Liang. Semidefinite relaxations for certifying robustness to adversarial examples. NeurIPS, 2018. URL http://arxix.... orgoo//////oo httpg//bs//1......///////a/ 01057.
R. Rockafellar. Convex Analysis. Princeton University Press, 2015.
R. T. Rockafellar and R. Wets. Variational Analysis. Springer, 1998.
L. Schmidt, S. Santurkar, D. Tsipras, K. Talwar, and A. Madry. Adversarially robust generalization requires data. In Advances in Neural Information Processing Systems, pages 5014-5024 2018.
P. Stein. A note on the volume of a simplex. The American Mathematical Monthly, 1966.
I. Steinwart. Consistency of support vector machines and other regularized kernel classifiers. IEEE transactions on information theory, 51(1):128-142 2005.
I. Steinwart, D. Hush, and C. Scovel. Function classes that approximate the bayes risk. In International Conference Computational Learning Theory, pages 79-93. Springer, 2006.
C. Szegedy, W. Zaremba, I. Sutskever, J. Bruna, D. Erhan, I. Goodfellow, and R. Fergus. Intriguing properties of neural networks. arXiv preprint arXiv: 13,66999, 2013.
D. Tsipras, S. Santurkar, L. Engstrom, A. Turner, and A. Madry. Robustness may be at odds with accuracy, 2018
Weng, H. Zhang, Chen, Song, C.-J. Hsieh, Daniel, D. Boning, and Dhillon. Towards fast computation of certified robustness for ReLU networks. In Proceedings of the 35th International Conference on Machine Learning, Proceedings Machine Learning Research. PMLR, 2018.
E. Wong and J. Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In Proceedings of the 35th International Conference Machine Learning. 2018.
Y.-Y. Yang, C. Rashtchian, Y. Wang, and K. Chaudhuri. Robustness for non-parametric classification: generic attack and defense. mlr, 2020.
D. Yin, K. Ramchandran, and Bartlett. Rademacher complexity for adversarially robust generalization. In Proceedings of ICML, pages 7085-7094, 2019.
L. Zajiček. Porosity and o-porosity. Real Analysis Exchange, 13(2):314-355 1987.
H. Zhang, T. Weng, P. Chen, C. Hsieh, and L. Daniel. Efficient neural network robustness certification with general activation functions. NeurIPS, 2018.
M. Zhang and S. Agarwal. Bayes consistency vs. h-consistency: The interplay between surrogate loss functions and the scoring function class. In Advances in Neural Information Processing Systems, 2020.
T. Zhang. Statistical behavior and consistency of classification methods based on convex risk minimization. The Annals for Statistics, 32, 2004.
13


Reviews:
[{"review_id": "cuG1PrcTDR", "reviewer": "Reviewer_j1GR", "summary": "The paper proves the existence of universally measurable classifiers minimizing the adversarial risk for strictly convex set of perturbations. This is the first result of this kind in adversarial literature.", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I would like to highlight how nice it is to see theoretical papers in the field of adversarial attacks. I really believe this kind of paper can improve the research in the field and helps understanding the very nature of this phenomenon. The paper is very technical. I acknowledge I have a good background in measure theory which helped me understand better the paper. Yet, this paper needs to be somekind of simplified if the authors would like it to have an impact broader than people mastering measure theory and having interest in adversarial machine learning. I am fine with the current version, but it is rather a suggestion. \n\nI must admit I read the proofs but I did not check them carefully. From what I read, I am confident in the results. In the meantime of the review it is complicated to have a thorough reading of the paper and the proofs for such a technical paper. That said, I still have some comments about your work:\n\n- The supplementary material is very difficult to read. I suggest the authors to write a linear appendix. Going up and down to check proofs is not very comfortable.\n- Measurability of the adversarial risk was treated in this paper [1] using the same concepts of universal measurability.\n- I am not sur  the risk $R^\\epsilon(f)$ defined L138 actually corresponds to the risk $R^\\epsilon(A)$. I think the \"right\" loss should be $1_{ysign(f(x))\\leq 0}$. but I might be mistaken\n- The paper is motivated by calibration/consistency and provable robustness. I am not sure to see the direct link. Can the authors elaborate a bit on that?\n\n[1] Mixed Nash Equilibria in the Adversarial Examples Game. Laurent Meunier, Meyer Scetbon, Rafael Pinot, Jamal Atif, Yann Chevaleyre. ICML2021.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Understanding theoretically adversarial examples can help building more robust networks.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "IzF7GOlC1g", "reviewer": "Reviewer_o7af", "summary": "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. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Originality**\n\nThe concept of ‘pseudo-certified robustness’ is new to me. In addition, by formalizing the adversarial risk as a function of sets and thus transforming the original problem to a real analysis problem, the proof techniques seem to be not very common in the adversarial machine learning literatures. \n\n**Quality**\n\nThe paper is rigorous and mostly well-written. Reading through the main paper, I did not notice wrong statements assuming all the lemmas are correct. The contents in appendix are quite overwhelming, for which I only had a skim.\n\nI do not have any major criticisms for this paper, but I do have some suggestions. I think some of the considerations may be too mathematical and far away from the area of machine learning. These pure mathematical considerations complicate the proofs and theorems, while has no real meaning to machine learning. \n\nFor example, the measurability issue of $A\\oplus \\overline{B_\\epsilon(0)}$. Even though there exists extreme cases where the direct sum of two measurable sets is not measurable, I do not think that can be a real problem for machine learning models. The authors put quite an effort to establish the ‘universal $\\sigma$-algebra’, but the measurability issue can be worked around effortlessly by being a little bit more ‘machine learning’. I am not suggesting being less rigorous but being a bit more practical.\n\nConcretely, $A\\oplus \\overline{B_\\epsilon(0)}$ is open, thus measurable, if $A$ is open. Moreover, $A\\oplus \\overline{B_\\epsilon(0)}$ is measurable if $A$ is closed (See Lemma 3.1 in [1]). This kind of $A$ (i.e., being either an open set or a closed set) should cover most of, if not every, realistic cases I think. For example, $A=\\\\{x:f(x) > 0 \\\\}=f^{-1}((0, +\\infty))$ is open whenever the model $f$ is continuous, which covers many common models, e.g., SVM, neural networks with any continuous activation like ReLU and Sigmoid. Moreover, I think there should be weaker conditions for $A\\oplus \\overline{B_\\epsilon(0)}$ being measurable to hold. \n\nThe bottom-line: the results are interesting, but I believe there are simpler ways to deliver the same message without sacrificing rigorousness.\n\nQuestion: Theorem 1 proves that the minimizer of adversarial risk exists and is pseudo-certifiably robust. However, it seems that pseudo-certified robustness alone cannot guarantee a low adversarial risk. What other conditions do we need to guarantee pseudo-certified robustness imply low adversarial risk? More generally, it would be interesting to see more investigations about the pseudo-certified robustness.\n\n**Clarity**\n\nThe paper is well-written in my opinion. \nMinor things: line 193 typo (is is is). In Lemma 4 $X$ should be $\\mathbb{R}^d$? Some equations are too wide (e.g. line 318, 329)\n\n**Significance**\n\nI think the results of this paper is novel, fundamental and important.\n\n[1] Adversarial risk via optimal transport and optimal couplings. Muni Sreenivas Pydi and Varun Jog.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The main result (theorem 1) requires a strictly convex norm which excludes two common norms, $\\ell_1$ and $\\ell_\\infty$. The authors discuss this limitation in appendix.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "IIYZAXx2QJL", "reviewer": "Reviewer_UUgs", "summary": "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I am somewhat unfamiliar with the prior work in this area of adversarial learning theory, so I cannot comment much on the originality of the work. Since this seemed to be a point of concern in previous submissions, I will defer to the other reviewers' opinion in this area. However, one point in the introduction about previous work is a bit misleading: in lines 82-84, the authors write that\n\n> a process called randomized smoothing makes the classifier certifiably robust in the `$\\ell_2$ norm with high probability. Notably, randomized smoothing is applied after training. A better understanding of the adversarial Bayes classifier could help find other such procedures.\n\nThis seems to indicate that prior work has not incorporated certified robustness *during* training, but many papers have explored this idea [1-4, among others]. It would be good to clarify this.\n\nThe exposition is good throughout the paper. All the math appears to be sound, although I did not carefully check every proof.\n\nThe results seem useful for adversarial learning theory, although again I am not sure exactly how novel they are. I think the authors could do a bit more to flesh out the implications of the work. While the introduction and conclusion refer to giving insight into the consistency of adversarial losses, they are mostly vague. Are there implications of the Bayes optimal classifier being pseudo-certifiably robust? In Appendix B, the authors argue that removing the non-pseudo-certifiably robust region of a classifier generally reduces the loss and that \"one could try and device algorithms to take advantage of this property.\" Moving and adding statements like this to the conclusion or introduction could give some more intuition about why and how the results are significant.\n\nOverall, the paper is well-written and sound; I would vote to accept it if the above concerns are addressed and barring serious concerns from the other reviewers. \n\n*A typo*: in Definition 1, I believe the last line should read \"A is pseudo-certifiably robust *if it is* pseudo-certifiably robust\", not \"is is is\".\n\n[1] Weng et al. Towards fast computation of certified robustness for ReLU networks. ICML 2018.\n\n[2] Wong and Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. ICML 2018.\n\n[3] Zhang et al. Efficient neural network robustness certification with general activation functions. NeurIPS 2018.\n\n[4] Raghunathan et al. Semidefinite relaxations for certifying robustness to adversarial examples. NeurIPS 2018.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors state that \"our work is theoretical in nature and we do not anticipate any immediate negative societal impact\"; I agree with this assessment.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies a variety of theoretical questions regarding the Bayes optimal classifier and associated robustness guarantees. This is an important topic, adding to the growing discussion around theoretical tools for robustness-related questions. The reviewers found the theoretical results to be substantial, using novel arguments in linear algebra and measure theory. The reviewers also believe that the results are interesting, well-motivated, and technically sound. Therefore, I recommend accepting this paper.

In the reviews, there were two main concerns that the authors should address for the final version of the paper: (1) certain relevant references were missing and should be discussed, and (2) there was a strong suggestion to improve the readability of the supplemental results and proofs in the paper. I agree that both of these should be addressed, and that writing a good theory paper can be challenging but is ultimately a good service to the community. Specifically, for (1), I think the authors can also be clearer in the paper about the relationship with prior work, focusing more on the theoretical comparison between the prior results in some of the references and the present results (e.g., a proper technical overview may be a good way to address both points and set up the exposition for the appendix and proofs). 
Decision: Accept (Spotlight)