The Many Faces of Adversarial Risk
Authors: Muni Sreenivas Pydi
Varun Jog
Venue: NeurIPS 2021 Poster (2021)
Keywords: Adversarial risk
robustness
optimal transport
game theory
Nash equilibrium
2-alternating capacities
Strassen's theorem
measurable selection theorem
Wasserstein distance
robust statistics

Abstract: Adversarial risk quantifies the performance of classifiers on adversarially perturbed data. Numerous definitions of adversarial risk---not all mathematically rigorous and differing subtly in the details---have appeared in the literature. In this paper, we revisit these definitions, make them rigorous, and critically examine their similarities and differences. Our technical tools derive from optimal transport, robust statistics, functional analysis, and game theory. Our contributions include the following: generalizing Strassen’s theorem to the unbalanced optimal transport setting with applications to adversarial classification with unequal priors; showing an equivalence between adversarial robustness and robust hypothesis testing with $\infty$-Wasserstein uncertainty sets; proving the existence of a pure Nash equilibrium in the two-player game between the adversary and the algorithm; and characterizing adversarial risk by the minimum Bayes error between distributions belonging to the $\infty$-Wasserstein uncertainty sets. Our results generalize and deepen recently discovered connections between optimal transport and adversarial robustness and reveal new connections to Choquet capacities and game theory.

The Many Faces of Adversarial Risk
Muni Sreenivas Pydi University Wisconsin Madison Madison, Wisconsin, USA pydi@wisc.edu
Varun Jog University of Cambridge Cambridge, UK vj2700cam.ac. uk
Abstract
Adversarial risk quantifies the performance of classifiers adversarially perturbed data. Numerous definitions of adversarial risk-not not all mathematically rigorous and differing subtly in the details- appeared in the literature. In this paper, visit these definitions, make them rigorous, and critically examine their similarities and differences. Our technical tools derive from optimal transport, robust statisties, functional analysis, and game theory. Our contributions include the following: generalizing Strassen's 's theorem to the unbalanced optimal transport setting with ap- plications to ad adversarial classification with unequal priors; showing an equivalence between adversarial robustness and robust hypothesis testing with oo- Wasserstein uncertainty sets; proving the existence of a pure Nash equilibrium in the two- -wo-player game between the adversary and the algorithm; and characterizing adversarial risk by the minimum Bayes error between pair of distributions belonging to the oo- Wasserstein uncertainty sets. Our results generalize and deepen recently discovered connections between optimal transport and ad adversarial robustness and reveal new connections to Choquet capacities and game theory.
Introduction
Neural networks are known be vulnerable adversarial attacks, which are imperceptible per- Developing algorithms resistant to such
turbations to input data that maximize loss [38]
15
5
attacks has received considerable attention in recent years
28
20), motivated by safety-critical
applications such as autonomous driving [18 27 medical imaging
17
22
and law 22
A classification algorithm with high accuracy (low risk) in the absence of adversary may have poor accuracy (high risk) when an adversary is present. Thus, a modified notion known as adversarial risk used to quantify the adversarial robustness of algorithms. Algorithms that minimize adversarial risk
are deemed robust. Procedures for finding them have been effective in practice (4 41 28 spurring numerous theoretical investigations into adversarial risk and its minimizers.
There is no universally agreed upon definition of adversarial risk. Even the simplest setting of binary classification in IR with an & adversary admits various definitions involving set expansions 16), transport maps [29], Markov kernels [I], and couplings (26). These works broadly interpret adversarial risk measure of robustness small perturbations, but their definitions differ in subtle details such as the class of adversaries and algorithms considered, budget constraints placed on the adversary, assumptions the loss function, and the geometry of decision boundaries.
Optimal adversarial risk most commonly defined as the minimax risk under adversarial contam- ination 24 33 Other notable characterizations include an optimal transport cost between data
generating distributions in [30 IO, II the optimal value of distributionally robust optimization
problem 36 35 40) and the value of two-player zero-sum game [26]] 29
The diversity of definitions for adversarial risk makes challenging compare approaches. Moreover, not all approaches are rigorous. For instance, the classes of adversarial strategies and classifier
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

algorithms are often unclear, and issues of measurability are ignored. Although this may be harmless for applied research, it has led to incorrect proofs and insufficient assumptions in some theoretical works; mathematically rigorous foundation for adversarial risk is essential for future research.
In this paper, examine various notions of adversarial risk for binary classification in a non- parametric setting, where the decision boundary (or decision region) of a classifier is an arbitrary subset of the input space. We present rigorous definitions of adversarial risk and identify conditions under which these definitions are equivalent. We consider the general setting of Polish spaces (complete, separable metric spaces), and present stronger results for the Euclidean space (R") Our contributions are as follows:
We examine the definition of adversarial risk based on set expansions. For Polish spaces, we observe that adversarial risk is not Borel measurable, and hence, not well-defined when the decision region is an arbitrary set. We show that the problem can be resolved by considering a Polish space equipped with the universal completion of the Borel o-algebra and restricting the decision regions to Borel sets. For the Euclidean space with the Lebesgue o-algebra, we show that adversarial risk is well-defined for any Lebesgue measurable decision region. Our key lemma (Lemma 4.3) shows that the Lebesgue o-algebra is preferred over the Borel o-algebra because set expansions are Lebesgue measurable but not necessarily Borel measurable. These results are contained in Section
We show that the definition of adversarial risk using set expansions is identical to a notion of risk that appears in robust hypothesis testing with co- so-Wasserstein uncertainty sets. We prove this result in Polish spaces using the theory of measurable selections M [3). In Rd we able to use the powerful theory of Choquet capacities M7] (in particular, Huber and Strassen's ' 2-alternating capacities [19] to establish results of a similar nature. These results are contained in Scction
We consider the binary classification setup with unequal priors and show (under suitable assumptions) that the optimal adversarial risk from the above definitions is characterized by unbalanced optimal transport cost between fata-generating distributions. For both Polish spaces and IRd, the main tool we use is Theorem 6. in which we generalize a classical result of Strassen excess-cost optimal transport 37 42 from probability measures to finite measures with possibly unequal mass. This generalizes results of [31] 2 on binary classification, which were only for equal priors. These results are contained in Section 6
We consider the setup of a zero-sum game between the adversary and the algorithm. We show that the value of this game (adversarial risk) is equal to the minimum Bayes error between a pair of distributions belonging to the co- -a-Sasserttein uncertainty sets centered around true data-generating distributions. We prove the existence of a pure Nash equilibrium in this game for Id and for Polish spaces with midpoint property. This extends/strengthens the results of [26] 22 3 to non-maramct classifiers. These results are contained in Section 7
The paper is organized as follows: In Section 2 we present preliminary definitions from optimal transport and metric space topology. In Section we discuss various definitions of adversarial risk and present more related work. Sections 4 5 and contaii our main contributions summarized above. We conclude the paper in Section and discuss future research directions.
We emphasize that rectifying measure theoretic issues with existing formulations of adversarial risk is one of our contributions, but not the main focus of our paper. We start our presentation with fixing measurability and well-definedness (in Section 4 because otherwise present our main results in the subsequent sections, namely: relation to robust hypothesis testing and Choquet capacities in section 5 generalizing the results of [2] 30 in section, 6 proving minimax
will not be able rigorously
theorems and existence of Nash equilibria and extending the results of 26 29 in section 7
Notation:
Throughout the paper, we use X' to denote Polish space (a complete, separable metric space) with metric d and Borel o-algebra B(2)). For x E X' and r 2 0, let (x) denote the closed ball of radius r centered z. We use P(2') and MXX) to denote the space of probability measures and finite measures defined on the measure space (2,, ((X)), respectively. Let B(X') denote the universal completion of (()). Let P(X) and ((X) denote the space of probability measures and finite measures defined the complete measure space (X, B(X)). For μl, M(x),, say dominates μ if u(A) < v(A) for all A B(X) and write μ 3 V. When X is RRd, use L(X²) to
2

---

denote the Lebesgue o-algebra and À to denote the d-dimensional Lebesgue measure. Note that [(x) = ( for = Rd. For a positive integer ni we use [nx] to denote the finite set (1....,7) ]
2
Preliminaries
2.1 Metric Space Topology
We introduce three different notions of set expansions. For 2 0 and A E B(X), the e-Minkowski expansion of given by A := Uae (o) The e-closed expansion of A is defined as A {o E X' ddx A) $ e}. where d(æ, A) = infard d(zz, a). The é-open expansion of A is defined as A == fr E X d(x, A) < e}. We use the notation A to denote ((A9))). Similarly, A = ((A)))))) For example, consider the set
(0. 1] the space (X, d) (R. 1)) and <> O. Then A 0 = (-c, 1-,,,++e, c]. A [-c, + c| and A (-c, +c). For any A E ((X)), A is closed and A open. Hence, A", A ( Moreover, A C A A However, A the may not be in (X)) (see Appendix for an example). In general, the Minkowski sum of two Borel sets need not be Borel 13 and that of two Lebesgue measurable sets need not be Lebesgue measurable [34
2.2 Optimal Transport
Let p. U E P(()). A coupling between J4 and y joint probability measure π E P((x2) with marginals μ and v. The set (),, S (2 denotes the set of all couplings between j and v. The optimal transport cost between and y under a cost function X' x X - oc) is defined as Volu, inf inf(e))( Sxa c(2,,')ddr x')d( x'). For positive integer p, the p- p-Wasserstein distance between y and is defined as, v) (Tx v)) The xo- W-Wsssesstiin metric is defined as (w, = limp- (p,,, v). It can also be expressed in the following ways:
(w,
inf sup d(x, 2') inf O: x(A) S AAAAAAA B(X)) aEll(w)) (a,w')
(I)
Given a μ E P(X) and measurable function f: + X. the forh-forward of p by f is defined as probability measure f&u P(X) given by fay (A)) for all A E B(X).
3 Adversarial Risk: Definitions and Related Work
We consider binary classification setting on feature space X. Let Po- Pi E P(X) be the data- generating distributions for labels 0 and 1, respectively. Let the prior probabilities for labels 0 and 1 be the ratio T : where we assume > I without loss of generality. For a space of classifiers parametrized by E W and loss function é (X x )) x W + [0. oo). the adversarial risk of classifier w E W under an adversarial budget of E 2 is defined as 24,33).
Rape (f, w) E(zw)
E((2', v). w) sup
d(z,)")se
If the loss function E(. w) is measurable, upper semi-continuous and bounded above for all W, 26 show that R, (E, w) is well-defined. But in general, it may not be so. A case of special interest the 0-1 loss function with non-parametric classifiers of the form fa(x) = 1(r E A) where A E B()). In this case, fo/1((x, v), A) = 1(x E A, = 0} + ffx E A = 1}. Hence,
T
Red(fo/1, A) T
Po
sup d(z,"")se
1f E A}}
T 1 E,
sup d(
11xx E A9)
T
T'+ TT (A
+ T pi ((A9)
A problem with the formulation in equation is the ambiguity over the measurability of the sets - and (4 Even when A E (())). is not guaranteed that A (Ar)0r E B(X) (see Appendix for example). Hence, (eo//1 A) is not well-defined for all A E B(X)). is shown in [1 that Rope (fo/1, A) is well-defined when A is either closed open, but its validity beyond that is unknown.
3

---

A simple fix to this measurability problem is to use closed set expansion instead of the Minkowski set expansion, as done [25]. This leads the following formulation.
T T T+ Po(A5) + T+1 P1 PI((A)))
Re Re(lo/1.
(4)
The above definition is well-defined for any A E B())) because A and (A9)² are both closed and hence, measurable. However, under the above definition, a point such that xx, x') > c. For example, when = (0, 1), we have A = [-c,c] and an adversary may transport 8 0 x' -c violating the budget constraint at z.
A may be perturbed to x' A
Remark 1. The formulations in equations 2) (3) and (4) can give a strictly positive adversarial risk even for "perfect" (i.e. Bayes optimal) classifier. This is consistent with the literature on adversarial examples where even a perfect classifier is forced to make errors in the presence of evasion attacks. These formulations of adversarial risk correspond to "constant-in-the-be
risk of 16 and "corrupteddinstance" risk in [9] 255. Here, an adversarial risk of zero is only possible if the supports of Po and P1 are non-overlapping and separated by least 2e. This is not the case with other formulations of ad adversarial risk such as "exact-in bhal" risk [16). ppredittion-change risk and "crror-region" risk g 225] We focus on the coorrppeediinttacee family of risks in this work.
Another approach to defining adversarial risk is by explicitly defining the class of adversaries of budget e as measurable transport maps f X - that push-forward the true data distribution such that no point is transported by more than a distance of e; i.e., d(x, (xx) S The transport map-based adversarial risk (29] is formally defined as follows:
T
Ry. (fo/1: A)
sup f (e
T Toppo Soppo (A) + T 1 ((19))
(5)
Yet another definition uses the robust hypothesis testing framework with W uncertainty sets. In this approach, an adversary perturbs the true distribution p; to corrupted distribution pf such that (Po p/) S c. From ( this is equivalent to the existence of coupling ग E I[ p.) such that ess sup((,"") d(x, x') S The adversarial risk with such an adversary is given by
T
1 T ((A9))
Rr. (Co/1, Wa (p)( (Po.)))
sup
T 1
(b(A)
(6)
Clearly, Ry, (fa/1: A) I Rr, (fo/1. A). but conditions for equality were not studied in prior work. Moreover, their relation to set expansion-based definitions in 3 and 4 was also unknown.
Next we discuss some characterizations of optimal adversarial risk, defined as Ra. (EB()) Ree (lo/1,
[30) 2]. it is shown that R = _ (e(Po.P) P1)] for equal priors (==1) 1), where De is an optimal transport cost defined as follows.
Definition (D. cost). Let μ, v E P(X). Let e 2 0. Let c. X² + {0, 1] be such that ce cz ((x,x') X x X: d(x, x') > 26). Then for n,v P(X) and 2 0, De(u, D) Te, (1,
For e = 0, D. reduces to the total variation distance. While Do is a metric on P(X), D. (for > 0) neither a metric nor a pseudometric [T].
Other formulations of optimal adversarial risk are inspired from game theory 29 26 3) Con-
sider game between two players: (1) The adversary whose action space is pairs of distribu- tions P6- Pi E P(X), and (2) The algorithm whose action space is the space of decision re- gions of the form A E B(X)}. For T > 0, define B(x') P(X'= x P(X') + [0, 1] as, ((A, = T (AA( + ((A)). The payoff when the algorithm plays first is given by inf (EBA) supw (po.%)) W (se r(A, p()),, and this quantity is interpreted as the optimal adversarial risk in this setup.
4 Well-Definedness of Adversarial Risk
As stated Section 3 Rape (fo/1, A) may not be well-defined for some decision regions A E ((x) because of the non-measurability of the sets A and (A9)8e, Specifically, we have the following lemma

---

Table 1: Summary of the adversarial risk definitions presented in Section Riper Re. RG, and Rr, denote adversarial risk defined using Minkowski set expansions, closed set expansions, transport maps and oc- xc-Wasserstein metric respectively.
Risk
Adversary's s action
Perturbation
d(x,x') S c?
Well-defined?
R4, Yes, for Lebesgue A Polish X': Yes, for Borel A
Rage
E A x' A
Random
Yes, Var
R.
x A + E A
Random
No
Yes, for measurable A
RF.
4 x' f((x)
Deterministic
Yes, Vz
Yes, for measurable f.
Pi 71
Almost surely yes,
Rr.
Random
Yes
(pi, E
Lemma 4.1. For any 0, there exists A e B(X) such that A & B(x).
In this section, we lay down the conditions under which the ambiguity can be resolved. We begin by presenting Lemma that shows that 4 is an analytic set (i.e. continuous image of Borel set) whenever A is Borel. It is known that an analytic sets are universally measurable, i.c. they belong in B(X), the universal completion of the Borel o-algebra (A)), and are measurable with respect to any finite measure defined on the complete measure space, (x, B())).
Lemma 4.2. Let A E ( Then, A [ is an analytic set. Consequently, A E B(X).
By virtue of the previous lemma, have the following.
Theorem 4.1. Let Po: Pi E P(X)) Then for any A E B(X), Rge Reo(fo/1, A) is well-defined.
For the special case of X' Idd, we can further strengthen Theorem 4.1 to include all Lebesgue measurable sets C(X) instead of just Borel sets ((X). For this, we use the concept of porous sets. Definition 2 (Porous set). A set E' C X' is said to be porous if there exists
(0, 1) and ro such that for every r E (0, ru] and every E X, there is an x' E X such that Bar (x') S (x)
Porous sets are a subclass of nowhere dense sets. Importantly, A(E) 0 for any porous set E C Rd 47]. By the following lemma, the set difference between the closed/open set expansions porous.
Lemma 4.3. Let (X' d) (R.", || II) and A E L(X). Then F A*)) is porous.
Lemma 4.3 plays a crucial role in proving that T E L(²') whenever A E L(X). We recall that A is the Minkowski sum of A with the closed e-ball. In general, the Minkowski sum of two Lebesgue measurable sets is not always Lebesgue measurable [44 So the fact that one of them a closed ball in case of A (rr is important. In the following theorem, we use Lemma 4.3 to prove the measurability of A and in turn prove that Ra (f0/1, A) is well-defined for any A ((X).
Theorem 4.2. Let (X (Rd .I [I). Let Po, Pı P(X) and let 2 0. Then for any A L(X), Rac(fo/1 A) is well-defined. If, in addition, Po and p1 are absolutely continuous with respect to the Lebesgue measure, then (40/,, A) = R2 (fo/1, A).
5 Equivalence with oc- -a-asseesttinn Robustness
In this section, we show the conditions under which Ri (byy1, A) is equivalent other notions of adversarial risk based on transport maps and W robustness.
5.1 W Robustness in Polish Spaces via Measurable Selections
We begin by presenting a lemma that links the measure of e-Minkowsi set expansion to the worst case measure over Wo probability ball radius e.
Lemma 5.1. Let μ E P(X) and A B()). Then supw (nad) (/ (A) = p(A*)). Moreover, the supremum the previous equation is achieved by n² E P(2)) that induced from μ via measurable transport map ő X + X (i.c. μ² = dzu) satisfying d(z, o(x)) S e for all X.
5

---

Table 2: Eqvivalences among adversarial risk formulations. Re R.), Ry, (A) and Rr, (A) denote adversarial risk for 0-1 loss function (fo/1) 1) for a binary classifier with decision region A (i.e. fA (x) = 1 E A}), defined using Minkowski set expansions, closed set expansions, transport maps and oc- Wasseessttnn metric respectively. (X)) and (()) denote the Borel and Lebesgue o-algebras. (X, (x)) denotes the universal completion of the Borel measure space, (x, B())).
Equivalences in Adversarial Risk
Conditions
Raee (A) = Rr. (A)
Rº: A E C(X) or (X, (())): A A B(X)
Røe (A) Rr, (A) RF,(A)
(x, B(X)): A ((X)
Rac (A) Rr. (A) RE (A) (A)
Rd. A E L(X) and po.P1 have densities
crucial step in the proof of Lemma 5.1 is finding measurable transport map & such that Ø (A) A and d(x, d(x)) S e for all æ E X. In the following theorem, we use Lemma 5.1 to establish the equivalence between three different notions of adversarial risk introduced in section 3
Theorem 5.1. Let Po.Pr
P(X) and A B(X). Then Rge(fn/1; A) Rf, Rr, (f0/1, A). In addition, the supremum over fo and fi in Rr, (f0/1, A) is attained. Similarly, the supremum over p/ and pl in Rr, (fo/1, A) is attained.
5.2 W Robustness in d via 2-Alternating Capacities
In this subsection, establish connection between adversarial risk and Choquet capacities in Ied. This connection allows us to extend Theorem 5.1 from Borel sets to the broader class of Lebesgue measurable sets. We will again use this connection for proving minimax theorems and existence of Nash equilibria in Section 7.1 We begin with the following definitions.
Definition 3 (Capacity). A set function v B(X))
[0. 1] is a capacity if it satisfies the following conditions: (1) ( = 0 and v(X)) = 1: (2) For A, E B(x)) A C = =
v(A) S v(B); (3)
A, 1 A = v(An) f v(A); and (4) Fa J F. F, closed = v(Fx) 4 vFF).
Definition 4 (2-Alternating Capacity). A capacity v defined on the measure space ((x)( is
called 2-alternating if (AAU v(A B) I v(A) + vBB for all A, B e B(X).
For any compact set of probability measures E _ P(X),, the upper probability v(A) suppes ((A) is a capacity [19. The upper probability of e-neighborhoods of μ E P(X' defined using either the total variation metric or the eevy-Prokhorov metric can shown to be 2-alternating capacity [19] The following lemma shows that A - μ( (A#*) is 2-alternating capacity under some conditions.
Lemma 5.2. Let (X, dd (Rd ||. II) Let E P(x) and let 2 0. Define a set function on X such that for any A E ((X), e( A) == nu(A +h Then u is 2-alternating capacity.
Now we relate the capacity defined in Lemma 5.2 to the Wo metric. Since the e-neighborhood of a E P(X) in Wo metric is a compact set of probability measures (46), the upper probability over this W e-ball is capacity. The following lemma shows that it is 2-alternating capacity, and identifies it with the capacity defined in Lemma (52
Lemma 5.3. Let (X,d) (u n (((A) (*) Moreover, the supremum in the previous equation is attained.
(Rd, - II). Let μ E P(X). Then for any A E L(X),
Lemma 5.3 plays similar role to Lemma 5.1 in proving the following equivalence between adversar- ial robustness and W robustness.
Theorem 5.2. Let (X, d) (Rd, II II). Let Po E P(Xx) and let < 2 0. Then for any A E L(X'), Rac Rfp/Lo/11 - A) Rr. (fo/1: A). and the supremum over P6 and p in Rr, (fo/1, A) is attained.
The proof follows by converting the expression for Rr. into one for Rg. using Lemma 5.3 Unlike Theorem 5.1 Theorem 5.2 does not show the equivalence of Rg, (fo/1. with the other definitions under the relaxed assumption of A E L(X). This because Lemma 5.3 does not provide a push- forward map é such that μ² din with 4² attaining the supremum over the W.c ball.

---

Optimal Adversarial Risk via Generalized Strassen's 's Theorem
In section 5 we analyzed adversarial risk for a specific decision region A B()). In this section, we analyze infimum of adversarial risk over all possible decision regions; i.e., the optimal adversarial risk. We show that optimal adversarial risk in binary classification with unequal priors is characterized by an unbalanced optimal transport cost between tett-geenrating distributions. Our main technical lemma generalizes Strassen's 's theorem to unbalanced optimal transport. We present this result in and present our characterization of optimal adversarial risk in subsection
subsection and
6.1 Unbalanced Optimal Transport & Generalized Strassen's 's Theorem
Recall from Section that the optimal transport cost D, characterizes the optimal adversarial risk in binary classification for equal priors. The following result gives an alternative characterization of D.- Proposition 6.1 (Strassen's theorem). [Corollary 1.28 in 42 Let U. P(X). Let 2 0. Then
sup p(A) - ( (422) (e(,,)). AEB(X)
is special case of Seriooooviic--Rbbistteee duality 42) applied to {0. 1 J-valued cost functions. We now generalize this result to measures with unequal masses. We begin with some definitions that generalize the concepts we introduced in subsection 2.2
Proposition 6.1
Let uu M(X) be such that (x()) S (((). A coupling between μ and is
E MMX?)
such that for any A E (()), T (A x X) = (((A) and (X x A) $ (AA). The set [[,, v) is defined be the set of all couplings between μ and For cost function e X²2 [0, 00), the optimal transport cost between 1l and y under e is defined as Te(p, v) = -infxel(p,,)) Sx c(x, ('r,,")dd( (Ir, x²).
Theorem 6.1 (Generalized Strassen's 's theorem). Let μz, V E MM(X) be such that 0 < M = (x()) < v(X). L >> O. Define C. X22 + {0, 1} ce c2 2¹) 1 ((,,x') E X22 :2:d(xxx) x') 2c}. Then
sup ((A) (A²2) Te, (1, M AEB(X)
inf VEP(X) SW/M
De (e/M,,
Moreover, the infimum on the right hand side is attained. (Equivalently, there is a coupling æ E [(p, v/) that attains the unbalanced optimal transport cost Te, (H,,
Our proof of Theorem 6.1 leverages strong duality in linear programming. We first establish (8) for discrete measures on finite support. We then apply the discrete result sequence of measures supported on countable dense subset of the Polish space X. Using the tightness of finite measures on X. construct an optimal coupling that achieves the cost Te, (μ, v) in (8). We then show that the constructed coupling satisfies (8). This proof strategy is adapted from the works of [2] and [3
6.2 Optimal Adversarial Risk for Unequal Priors
Generalized Strassen's theorem involves closed set expansions. The following lemma allows switch to Minkowski set expansions.
Lemma 6.1. Let v E M(X) and e 0. Then SUPAEB(X) m(A) v(A2t)
(еg ((AAr)= ((A Moreover, the supremum in the right hand side of the above equality can be replaced by a supremum over closed sets.
Using the above lemma and the generalized Strassen's theorem, we show the following result optimal adversarial risk for unequal priors, generalizing the result of []
Theorem 6.2. Let po: P1 E P(X) and let 2 Then,
inf Rge(Ln/1. = T+1 --1 AEB(X)
1-
inf (EP(
De(g.P1)
Moreover, the infimum on the left hand side can be replaced by an infimum over closed sets.
The proof follows by using Lemma 6. to convert the expression with Minkowski expansion to one with closed expansions, followed by an application of Theorem 6. arrive at the final optimal
transport-based expression. Theorem 6.2 extends the result of [3] in two ways: (1) the infimum is
7

---

Theorem 7.2 (D, shortest Drv between W balls). Let (X, d) have the midpoint property. Let Dry (p' v'). Moreover, the taken over all sets for which Rge ( is well-defined. instead of restricting to closed sets, and (2) the priors on both labels can be unequal. We also note that for (2, (IR*) |), holds with the infimum on the left hand side taken over all E ((
Minimax Theorems and Nash Equilibria
In this section, we revisit the zero-sum game between the adversary and the algorithm introduced in section 3 Recall that for A E (A)) and po- p/1 E P((X), the payoff function is given by
T
r(A, Po. pi) = T Pb(A) + T P1 ((A9))
(10)
The max-min inequality gives us
sup Ws= (e AEA
inf r(A, 1o.1/% S
inf AEB(X) W (p.. (p
sup
(A:
(11)
If the inequality in 11 is equality, we say that the game has zero duality gap, and admits a value equal to either expression in (IT). Then there is no advantage to player making the first move. Our minimax theorems establish such equality. If in addition having an equality in (TT), there exist Po E (2))) that achieve the supremum on the left-hand side and A E B(X) that achieves the infimum on the right-hand side, we say that ((P6: pi), AA) is pure Nash equilibrium of the game.
In Section 7.1 we prove the minimax theorem and the existence of pure Nash equilibrium in IR using the theory of 2-alternating capacities [19] and the relation to adversarial risk from Section 5.2 Section 7.2 extends these results to more general Polish spaces with "midpoint property."
7.1 Minimax Theorem in RRd via 2- Aleernnaiing Capacities
The following theorem proves the minimax equality and the existence of Nash equilibrium for the adversarial robustness game in Idd
Theorem 7.1 (Minimax theorem in R.), Let (X, = (R* , || II). Let Po. E P(X) and let 2 0.
Define in (T). Then,
inf inf r r(A, AEC(X) W (Po.6)).. (p Wo (...oo..).Waalppppp AEC(X)
sup
sup
r r(A.Ph-Pi) (12)
Moreover, there exist Pū pi E P(2') and A E L(X) that achieve the supremum and infimum on the left and right hand sides of the above equation.
Crucial to the proof of Theorem 7. is Lemma 5.2 which shows that the set-valued maps A + Po(A ABe) and A + (() are 2-alternating capacities. The same proof technique is not applicable in general Polish spaces because the map A ((#))) is not a capacity for a general (()). This is because A @ is not measurable for all A E B(A))
7.2 Minimax Theorem Polish Spaces via Optimal Transport
We now extend the minimax theorem from Rd to general Polish spaces with the following property. Definition (Midpoint property). A metric space (X, d) is said to have the midpoint property if for every 1 I2 X, there exists X' such that, d(z x)) d(x, 22) d(z),,2)) 2/2
Any normed vector space with distance defined as d(z, x²) = || - x'1 satisfies the midpoint property. An example of metric space without this property the discrete metric space where d(æ,2') 1(x # x'} The midpoint property plays a crucial role in proving the following theorem, which shows that the D. transport cost between two distributions is the shortest total variation distance between their c-neighborhoods in W metric. A similar result was also presented in [II]
V.V E ((X) and let 0. Then D De v) wnf infimum over Drv in the above equation is attained.
The following theorem uses Theorem 7.2 to prove the minimax equality and the existence Nash equilibrium for any Polish space with the midpoint property for the case of equal priors.

---

Theorem 7.3 (Minimax theorem for equal priors), Let (X, d) have the midpoint property. Let
Po,P1 E P(2) and let 2 0. Define r as in (TO) with T = 1. Then
sup (c..p..))....llle (P Dise AEB(Z)
inf r(A.
inf AE W (po.p)). W (pi.s))
sup
r(A, pí). (13)
Moreover, there exist po: P(2)) that achieve the supremum the left hand side.
Proof. For μ E P(X), let W B(u) denote the set of all μ E P(X) such that Wod (H, Se
inf sup AEB(2) N6 EW ((EWB()) BEEW B(p1)
r(A.Pó.Pi) = inf AEB(X)
Rr. (f0/1, A) ( inf
Roo/1o A) (2)
Dr(Po.Pi)
AEB(2)
sup inf r(A, (A.PP))))) W/E ((po) pi EW B(s))
(112)
sup
1 11 Drv (p- p1)]
1
1
inf 16 N/E B(pa) pi EW B(pr)
Drv (P6-11)
AEB(X)
ew ((po)
2
eW B(p))
where (i) follows from Theorem 5.1 (ii) from Theorem 6.2 and (iei) again from Theorem 6.2 with
O. The expressions on the right extremes of the above equations are equal by Theorem 7.2 The
existence of P/. pT ((X) follows Theorem 7.2
To prove the minimax theorem for unequal priors, we need the following generalization of Theo- rem 7.2 to finite measures of unequal mass.
Lemma 7.1. Let po. P1 E P(X) and let 0. Then for T 2 1, inf
De(..1)) = (EP(X))TTM W (g.r)) W, (w
inf
inf
Div
inf W. (po. W.WW (n o (EP())
inf Drv(d'
(14)
Now, we prove the minimax equality for unequal priors. Theorem 7.4 (Minimax theorem for unequal priors). Let (X, d) have the midpoint property. Let Po.Pr P1 E P(X) and let For T 0, define as in (IO). Then
sup Woo (po. W (( AEBlx)
inf r( (A. p/)
inf AEB(X) W (P.
sup
r(A,p'.Pp). (15)
The proof uses: (1) the characterization of inf-sup payoff in terms of unbalanced optimal transport using Theorem 5.T] (2) Lemma 7.1 and (3) the minimax equality of Theorem 7.3 for equal priors.
Remark 2. Unlike Theorem 7.1 Theorems 7.3 and 7.4 do not guarantee the existence of optimal decision region 4". While Theorem 7.3 guarantees the existence of worst-case pair of perturbed distributions p př. Theorem 7.4 does not do Nevertheless, approximate pure Nash equilibrium exists all the cases. This is in sharp contrast with the non-existence of Nash equilibrium proven in
29 (which considers a different notion of adversarial perturbations).
Remark 3. recent work (26) shows the existence of mixed Nash equilibrium for randomized classifiers parametrized by points Polish space (see also [29 3). Fan's minimax theorem used in this result is inapplicable in our setting of non-parametric. decision region-based classifiers. Instead, we applied the theory of Choquet capacities (in Rd) and generalized Strassen's 's duality theorem (in
Polish spaces), which is novel to the best of our knowledge.
8 Discussion
We examined different notions of adversarial risk in a binary classification setting with 0-1 loss function and laid down the conditions under which these definitions are equivalent. By verifying the
conditions in Sections 4 and 5 researchers may use different definitions interchangeably. Several definitions have also been proposed for adversarial risk under general loss functions [31 26 using analogous constructions like transport maps, couplings and suprema over e-neighborhoods. Extending equivalence results to general loss functions is left for future work.

---

A
Drv
Do
Pu
W Wa Aol Se
War Se
D.
Drv pi)
We Watt wile
c
Drv
Drv
D.
P
70
2 T
WalPees se
War 16)
q TTo
Wallg.0'
Ty
inf PoN
P.(a.P)
inf (5 Kalon')
Drvld c
inf Waeten We of W 27%
T> 1: T+I
T=
Figure 1: Illustration of various equivalent formulations of the optimal adversarial risk. The equalities summarize the results of Section and Section 7 For equal priors (T = 1), A and denote two ways of obtaining the optimal adversarial risk, R& 1) A which denotes the D. cost between the true label distributions po and p1. and 2) B which denotes the shortest total variation distance
between oc- Wasserstein balls of radius e around and P1- For unequal priors (7 > 1). C D and
E denote three equivalent ways of obtaining Rige. The black dotted balls denote co- Wasserstein balls and the blue dashed balls denote sets defined using stochastic domination. The order in which
the types of balls appear around po is reversed between and
E
We analyzed optimal adversarial risk for -orrmmaamttricc) decision region-based classifiers. Using formulation of optimal transport between finite measures of unequal mass, we extended the optimal transport based characterization Strassen's 's theorem. This may find applications in the study of excess cost optimal transport [45] 44]. recent work (39 obtains a different characterization of optimal adversarial risk using optimal transport on the product space X' x ) where y is the label space. Further, they show the evolution of the optimal classifier A" as grows, terms of a mean curvature flow. This raises an interesting question on the evolution of the optimal adversarial distributions Po p E P(X) with e.
adversarial risk of 30 to unequal priors by generalizing
We proved a minimax theorem for adversarial robustness game and the existence a Nash equilibrium. constructed the worst-case pair of distributions Po: P P(2)) in terms true data distributions and showed that their total variation distance gives the optimal adversarial risk. Identifying worst case distributions could lead to a new approach to developing robust algorithms.
We used Choquet capacities for results in gd and measurable selections in Polish spaces. Specifically, showed that the measure of e-Minkowski expansion is 2-alternating capacity. This connection could help generalize our results to total variation and Prokhorov distance based contaminations.
Limitations: We largely focused on the binary classification setup with 0-1 loss function. While may be possible extend our results on measurability and relation oo- Wasserstein distributional robustness to more general loss functions and a multi-class setup, it is unclear how our results on generalized Strassen's theorem and Nash equilibria can be extended further. Our results on various equivalent formulations of optimal adversarial risk are specific to adversarial perturbations (or equivalently, oc- Wasserssnn distributional perturbations). and did not investigate more general perturbation models.
10

---

References
[1] D. Bertsekas and S. E. Shreve. Stochastic optimal control: the discrete-time case, volume 5. Athena Scientific, 1996.
[2] A.N. Bhagoji, D. Cullina, and Mittal. Lower bounds on adversarial robustness from optimal transport. In Advances in Neural Information Processing Systems, pages 7496-7508, 2019.
[3] A.J. Bose, G. Gidel, H. Berrard, A. Cianflone, P. Vincent, S. Lacoste-Julien, and W.I. Hamilton. Adversarial example games. Advances in Neural Information Processing Systems, 2020.
[4] S.R. Bulò, B. Biggio, Pillai, M. Pelillo, and F. Roli. Randomized prediction games for adversarial machine learning. IEEE Transactions on Neural Nenworks and Learning Systems, 28(11):2466-247 2016.
[5] N. Carlini and D. Wagner. Towards evaluating the robustness of neural networks. In IEEE Symposium on Security and Privacy, pages 39-57. IEEE, 2017.
[6] I. Chalkidis and D. Kampas. Deep learning in law: Early adaptation and legal word embeddings trained on large corpora. Artificial Intelligence and Law, 27(2):171-198, 2019.
[7] G. Choquet. Theory of capacities. In Annales de l'institul Fourier, volume 5, pages 131-295, 1954.
[8] J.M. Cohen, E. Rosenfeld, and J. Z. Kolter. Certified adversarial robustness via randomized smoothing. In International Conference Machine Learning, 2019.
[9] D. I. Diochnos, Mahloujifar, and M. Mahmoody, Adversarial risk and robustness: General definitions and implications for the uniform distribution. Advances in Neural Information Processing Systems, 31:10359-10368 2018.
[10] E. Dohmatob. Generalized no free lunch theorem for adversarial robustness. In International Conference on Machine Learning, pages 1646-1654. PMLR, 2019.
[11] E. Dohmatob. Universal lower-bounds on classification error under adversarial attacks and random corruption. arXiv preprint arXiv:2006.0m 09989, 2020.
[12] R.M. Dudley. Distances of probability measures and random variables. In Selected Works of RM Dudley, pages 28-37. Springer, 2010.
[13] Erdós and A. Stone. On the sum of two Borel sets. Proceedings of the American Mathematical Society, 25(2):304-3066 1970.
[14] R. Gardner. The Krunn-Minkowssi inequality. Bulletin of the American Mathematical Society, 39(3):355 405, 2002.
[15] I. J. Goodfellow, J. Shlens, and C. Szegedy. Explaining and harnessing adversarial examples. International Conference on Learning Representations, 2015.
[16] P. Gourdeau, V. Kanade, M. Kwiatkowska, and J. Worrell. On the hardness of robust classifica- tion. In Advances in Neural Information Processing Systems, volume 32, 2019.
[17] H. Greenspan, B. van Ginneken, and R. M. Summers. Guest editorial deep learning in medical imaging: Overview and future promise of exciting new technique. IEEE Transactions Medical Imaging, 15(5):1153-113 153-1153199 1159, 2016.
[18] S. Grigorescu, B. Trasnea, T. Cocias, and G. Macesanu. A survey of deep learning techniques for autonomous driving. Journal of Field Robotics, 37(3):362 -3-66336--386, 2020.
[19] P.J. Huber and V. Strassen. Minimax tests and the Neyman-PParsae lemma for capacities. The Annals of Statistics, pages 251-263, 1973.
[20] A. Jalal, A. Ilyas, C. Daskalakis, and A.G. Dimakis. The robust manifold defense: Adversarial training using generative models. arXiv preprint arXiv:1712.09196 2017.
11

---

[21] R.S.S. Kumar, D.R. O'Brien, K. Albert, and S. Vilojen. Law and adversarial machine learning. NeurIPS Workshop on Security in Machine Learning, 2018.
[22] Z. Liu, J. Zhang, V. Jog, P. Loh, and A.B. McMillan. Robustifying deep networks for image segmentation. arXiv preprint arXiv: 00656, 2019.
[23] X. Ma, Y. Niu, L. Gu, Y. Wang, Y. Zhao, J. Bailey, and F. Lu. Understanding adversarial attacks on deep learning based medical image analysis systems. Pattern Recognition, 110:107332, 2021.
[24] A. Madry, A. Makelov, L. Schmidt, D. Tsipras, and A. Vladu. Towards deep learning models resistant to adversarial attacks. International Conference on Learning Representations, 2018.
[25] S. Mahloujifar, D. I. Diochnos, and M. Mahmoody. The curse of concentration in robust learning: Evasion and poisoning attacks from concentration of measure. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 4536-4543, 2019.
[26] L. Meunier, M. Scetbon, Pinot, Atif, and Y. Chevaleyre. Mixed Nash equilibria in the adversarial examples game. International Conference on Machine Learning, 2021.
[27] K. Muhammad, A. Ullah, Lloret, Del Ser, and V.H.C. de Albuquerque. Deep learning for safe autonomous driving: Current challenges and future directions. IEEE Transactions on Intelligent Transportation Systems, 2020.
[28] N. Papernot, P. McDaniel, X. Wu, S. Jha, and A. Swami. Distillation as a defense to adversarial perturbations against deep neural networks. In 2016 IEEE Symposium on Security and Privacy, pages 582-597. IEEE, 2016.
[29] R. Pinot, R. Ettedgui, G. Rizk, Y. Chevaleyre, and J. Atif. Randomization matters. how to defend against strong adversarial attacks. In International Conference on Machine Learning, pages 7717-7727. PMLR, 2020.
[30] M. Pydi and V. Jog. Adversarial risk via optimal transport and optimal couplings. In International Conference Machine Learning, pages 7814-7823, PMLR, 2020.
[31] M. S. Pydi and V. Jog. Adversarial risk via optimal transport and optimal couplings. IEEE Transactions on Information Theory, 67(9):6031-600 6052, 2021.
[32] G. Schay, Nearest random variables with given distributions. The Annals of Probability, pages 163-166, 1974.
[33] U. Shaham, Y. Yamada, and S. Negahban. Understanding adversarial training: Increasing local stability of supervised models through robust optimization. Neurocomputing, 307:195-200 2018.
[34] W. Sierpiński. Sur la question de la mesurabilité de la base de M. Hamel. Fundamenta Mathematicae, 101):105-111, 1920.
[35] A. Sinha, H. Namkoong, and J. C. Duchi. Certifying some distributional robustness with principled adversarial training. In International Conference on Learning Representations, 2017.
[36] M. Staib and S. Jegelka. Distributionally robust deep learning as a generalization of adversarial training. In NeurIPS workshop on Machine Learning and Computer Security, 2017.
[37] V. Strassen. The existence of probability measures with given marginals. The Annals of Mathematical Statistics, 36(2):423 439,, 1965.
[38] C. Szegedy, W. Zaremba, I. Sutskever, J. Bruna. D. Erhan, I. Goodfellow, and R. Fergus. Intriguing properties of neural networks. International Conference on Learning Representations, 2014.
[39] N.G. Trillos and R. Murray. Adversarial classification: Necessary conditions and geometric flows. arXiv preprint 20X1v20011.10977, 2020.
12

---

[40] Z. Tu, J. Zhang, and D. Tao. Theoretical analysis of adversarial learning: A minimax approach. In Advances in Neural Information Processing Systems, volume 32, 2019.
[41] Uesato, B. Oadonoghue, P. Kohli, and A. Oord. Adversarial risk and the dangers evaluating against weak attacks. In International Conference Machine Learning, pages 5025-5034. PMLR, 2018.
[42] C. Villani. Topics in Optimal Transportation. American Mathematical Society, 2003.
[43] D. H. Wagner. Survey of measurable selection theorems. SIAM Journal on Control and Optimization, 15(5)855--903, 1977.
[44] L. Yu. Asymptotics for strassen's 's optimal transport problem. arXiv preprint arXiv: 2019.
[45] L. Yu and V. Tan. Asymptotic coupling and its applications in information theory. IEEE Trunsactions on Information Theory, 1313)413, 2018.
[46] M.C. Yue, D. Kuhn, and W. Wiesemann. On linear optimization over Wasserstein balls. Mathematical Programming, pages 1-16, 2021.
[47] I.. Zajfček. On a-porous in abstract spaces. In Abstract and Applied Analysis, volume 2005, pages 509-534. Hindawi, 2005.
13


Reviews:
[{"review_id": "ifDjGh3O_P5", "reviewer": "Reviewer_pEiS", "summary": "The paper discusses different definitions of adversarial risk that have been used in various papers throughout the years, where, by using tools from optimal transport theory, robust statistics, functional analysis, and game theory, these definitions are viewed under a different lens, and in several ways new connections (and separations) between some of these definitions are established. \n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper first gathers and discusses different notions of adversarial risk and then takes a unified approach on looking at these definitions in different settings. Though I have to admit that I have not carefully looked into the proofs, I think that for the largest part the paper is ok and provides the reader with new insights connecting different definitions of adversarial risk. Having said that, there are some claims in the related literature that are a little bit confusing to the reader and indeed not all the definitions are discussed. \n\nSection 3 is very important as the authors discuss 4 different definitions of adversarial risk. However, the way some definitions are presented is confusing for the reader. \n- For example, the authors claim that the formulation of adversarial risk studied in [9, 16] is a special case of the approach followed in [25, 34]. This is only partially true as [9] and [16] spend a significant amount explaining the differences between different definitions and in particular those that are used in [25] and [34]. So, while the papers [9] and [16] indeed discuss, among other things, a special case of the definitions used in [25] and [34], they nevertheless take a different route and explain that when misclassification is the goal for the generation of adversarial examples, then the definitions used in [25] and [34] may in turn compute completely wrong values. As an extreme case, for example, when PAC learning Boolean functions, it is often-times the case that we learn the target function completely. Then, in such situations [9] and [16] claim that indeed the learnt model is infinitely robust since it cannot be fooled by any adversarial example. However, both [25] and [34] can somehow claim that they can find adversarial examples in these situations, by making the model flip the prediction label. However, when the ground truth also changes, then there is no misclassification -- which is really the whole point behind adversarial examples. This is also true in equations (2) and (3) in this paper where we can see that the adversarial risk would be positive, even if the model was entirely correct against a ground function that does the labeling. \n- And to go one step further, equation (3) in the current paper still makes this assumption, and I do not believe it is even studied in [26] which is cited as the paper where this definition has its origin. [26] uses the same definition of \"error-region adversarial risk\" that is used in [9] (or what is called \"exact in the ball adversarial risk\" in [16]).\n\nThe above points need to be clarified so that everything is crystal clear to the reader. The current paper studies variations of adversarial risk that follow along the lines of \"corrupted-inputs adversarial risk\" [9] or \"constant in the ball adversarial risk\" [16]. Such versions of risk are indeed special cases of [25] and [34]. But in general, and that is the main point of [9] and [16], these definitions do not compute, adversarial examples -- again, assuming that misclassification is the goal of an adversarial example, and I believe we all agree that this is indeed the goal.\n\nHence, as far as I understand, the current paper indeed tries to formulate variations of the \"corrupted-inputs / constant in the ball\" adversarial risk. This has indeed its own merit, but the presentation in section 3 needs to be more careful and really explain things in a better way. The current paper does not touch upon the different definitions that are out there -- in fact, in some situations I believe that the presentation is entirely misleading. \n\nGetting along I must admit that I really appreciate all the effort and the work that the authors have done and indeed I find the different connections that are established, to be interesting. The authors try to be clear and make interesting comments on their results. Nevertheless, it is also a little bit unclear to me up to what point we can accept some of the consequences, in general, as this assumption of maintaining the ground-truth label in some region around a sampled point does not necessarily hold.\n\n*Post-rebuttal:*\n\nThank you for the response to all the reviews. I am looking forward to seeing the improvements that have been suggested on clarifications by myself as well as from the other reviewers. Assuming these clarifications will be seen in the final manuscript, I am increasing my score from 5 to 6. Thank you for a very interesting paper!", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I am happy with the discussion that the authors have done in the paper.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "UwnLl1z0SB", "reviewer": "Reviewer_nVTq", "summary": "The paper focuses on formalizing the definition of \"adversarial risk\" which is risk under test-time perturbation attacks. The focus is on subtle measure theoretic issues that arise when the distributions are continuous. ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Several definitions are given for adversarial risk in the literature. Most are not formal, and some are formal. The paper’s starting point is the formal ones. Yet, it revisits those definitions in the general case where distributions are not discrete, and hence subtle points arise about measurability of events and in particular whether or not certain probabilities associated with adversarial risk are always well defined. In particular, it is argued that some definitions use a union of Minkowski balls, which in general is not a measurable set. Other subtle points arise depending on what measure is used (e.g., Lebesgue or not). The paper also gives conditions under which: (1) various definitions become equivalent, (2) certain objects of interest exist and are characterized by intuitive formulations (e.g., optimal classifier under attack and Nash equilibrium in adversary’s game against algorithm designers).\n\nAs far as I understand, these points only arise when we pay attention to subtle aspects of formalism in a measure theoretic sense for general measures. So, this makes the work quite theoretical, as “in practice” (e.g., when we deal with *algorithmic* attacks and distributions), everything is discrete and none of the issues studied here arise. So, I don’t think the paper has a “practical” effect, as basically all the definitions that paper revisits are fine in the discrete setting and all the subtle points the paper mentions only show up when we go beyond the discrete case and start to care about measurability of sets in the continuous regime. \n\n\nIn fact, typically, by just assuming the space to be Polish these issues go away (e.g., see the last paragraph of page 11 here http://cgm.cs.mcgill.ca/~breed/conc/Talagrand.pdf) but evidently, in the context of adversarial risk and optimal adversarial strategies certain issues still exist, and the paper shows how to resolve them by carefully finding sufficient conditions. \n\nThe writing is very clear and precise and readable, and that is a big plus for a paper that has such a goal of formalizing notions.\n\nOverall, I think the paper fills a gap in an important direction, even though this gap is purely theoretical and has no immediate impact on the “practical” side. Still it is important to have a general and precise theory for this phenomenon, and that could be important to practice also in the long run. Considering the quality and clarity of the writing and its content, I think the paper will be useful for the program and recommend acceptance.\n\nComments:\n\nWhat is the main reason for focusing on binary classification? Any major limitations for larger label sets?\n\nThe term “decision region” is used in line 46 which is not clear. It is clarified later in line 109, but it is confusing the first time around.\n\nThe paper’s formulation of adversarial risk does not pay any attention to whether or not the perturbed point is in fact misclassified. Of course, if the perturbed point is “close” to the original point to the degree that the “truth” does not change, this would happen and this is how adversarial examples are perceived (“imperceptible” changes in a setting where humans are the judge for true labels). The issue is discussed here:\nhttp://proceedings.mlr.press/v89/suggala19a/suggala19a.pdf\nand the cited paper [9]. This aspect does not negatively affect this paper, becaue the paper's focus is mostly on \"welldefinedness of events\", yet it would be good to know how this can fit into this paper’s formal studies.\n\nThe letter “T” is used for both the probability weight and the transportation notation.\n\nLine 156 : “It generalizes a similar result of [32] for closed and open sets. ” What is the key new insight? In general, it would be good to point out the new part of the generalized arguments.\n\nLine 290: “Our minimax theorems establish such an equality.”\nBut in the cited paper [31] the authors say \"Then we demonstrate, in Section 4, the non-existence of a Nash equilibrium in the deterministic setting of this game\".\nHow is their result compatible with yours? Please clarify.\n\nLine 362: “transport characterization adversarial risk” I think you need to add “of” after “characterization”\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper is mainly theoretical and the long term impacts are positive.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "9"}, "extra_text": {}}, {"review_id": "SUSPoY3abq5", "reviewer": "Reviewer_9nkD", "summary": "This paper formalizes different definitions of adversarial risk for binary classification and studies the equivalence between those definitions. Moreover, the authors analyze optimal adversarial risk through the lens of optimal transport, which leads to the existence of a Nash equilibrium of the adversarial robustness game. The contribution of this paper is theoretical.", "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": "\n**Originality**\n\nThis paper is original and novel as far as I can see. It seems that one of the closest work to this paper is *M. S. Pydi and V. Jog. Adversarial risk via optimal transport and optimal couplings.* The authors discuss their advances from this one. \n\n**Quality**\n\nI did not notice wrong statements in the main paper. However, I only read the proofs in the main paper. \n\nMy questions are the following.\n\n1.\tThis paper defines the adversarial risk as various set functions, i.e., loss function w.r.t. the decision region $A$. However, it is more general to define the adversarial risk w.r.t. the model $f$ itself.  For example, given the input space $\\mathcal{X}$, output space $\\mathcal{Y}$, the data generating distribution $p\\in \\mathcal{P}({\\mathcal{X}\\times \\mathcal{Y}})$, and a cost function $c: \\mathcal{Y} \\times \\mathcal{Y} \\to [0,+\\infty)$, the adversarial loss function can be modeled by $$R(f)=\\int \\sup_{x'\\in B_\\epsilon(x)} c(f(x'),y)\\ \\ \\mathrm{d}p(x,y).$$\nFor binary classification, any function $f:\\mathcal{X}\\to \\mathbb{R}$ defines a decision region by $A=f^{-1}((0, +\\infty))$. By defining $c(\\cdot,\\cdot)$ to be the $\\ell_{0/1}$ loss based on the decision region, it seems that it recovers the $R_{\\oplus \\epsilon}$ loss. Moreover, the above $R(f)$ can be applied to other settings, e.g., multi-class classification and regression.\n    \n    Denoting $\\ell^\\epsilon(x, y)=\\sup_{x'\\in B_\\epsilon(x)} c(f(x'),y)$, to study the well-definedness for $R(f)$, it becomes to study the measurability of $\\ell^\\epsilon$ and the integrability of $\\ell^\\epsilon$ w.r.t. the data generating measure $p$. Therefore, does studying the well-definedness of $R(f)$ give the well-definedness of the set-based risk function? Moreover, what are the benefits of studying the set-based risks over the function based risk $R(f)$?\n\n2. For Theorem 6.1, it is mentioned that the infimum on the right hand side is attained. I'm curious that is the supremum on the left hand side attained? It seems that it leads to whether the optimal $A$ in Theorem 6.2 is attained. \n3. For non-theory people, the contribution of this paper may be limited. For example, an empirical person may think that the measurability is never a problem in real-world machine learning. Since NeurIPS is a big conference where attenders have diverse background, is there any point of this paper that may intrigue an empirical person?\n\n**Clarity**\n\nThis paper is rigorous and well-written as far I see. \n\n**Significance**\n\nIt is important in the sense that this paper rigorously defines several adversarial risk functions, filling the gap of previous work and building the ground for future work.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors discuss some of the limitations of their results in section 8. Comparing to the condition of Lebesgue measurable, I'm more curious about the case of general loss functions. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "A5_Vg0FM--h", "reviewer": "Reviewer_A5zG", "summary": "This paper provides a lot of theoretical insights to connect the different definitions of adversarial risk. It also discusses some other properties such as well-definedness and minimax theorem.", "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: this paper utilizes a lot of different mathematical tools and provides rigorous analysis. Such an analysis is complicated and is novel based on my knowledge.\n\nQuality, clarity and significance: my biggest concern is that the paper piles up a lot of different definitions and mathematical symbols, which may prevent readers from related areas to understand it (e.g. people who work on empirical study of adversarial training).  The authors are strongly encouraged to reorganize this paper and simplify some notations so that it has a more clear structure and is easier to understand.  Two examples:\n\n(1) Although this paper uses the definition of adversarial risk in [9], the definition in [9] is self is much easier than the one in this paper to understand. Please consider use simple definitions first (even informal), and try to provide their more formal definitions later. \n\n(2) The four contributions listed in Section 1 need to have a clear connection with the following five sections in this paper. I would suggest to first write down the corresponding sections when listing the contributions, and recall the readers about the this when starting each section.\n\nThe authors also need to emphasize the significance of this paper, e.g. provide some concrete easy-to-understand example where some definitions of adversarial risk may fail while others work well, and provide some experiments (or even simple simulation) to help illustration. It is hard to justify the significance of this paper from its current writing. \n \nA minor issue:\nA missing related reference: Xu, Q., Bello, K., & Honorio, J. (2020). A Le Cam Type Bound for Adversarial Learning and Applications. arXiv preprint arXiv:2007.00289.\n\n====================================================\n\nAfter author feedback:\n\nThe authors provided useful materials for the readability based on my major concern. Raised my score from 5 to 6.\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No social impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "7y-ksMYQD8D", "reviewer": "Reviewer_YZqf", "summary": "The paper extends previous works of the study of the adversarial risk. The authors interest in the well definition of the adversarial risk. They then show a minimax theorem on the game between the classifier and the adversary.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall I enjoyed reading the paper. The paper brings insights on Adversarial risks extending previous results from the literature. The paper is well written and easy to follow. The current trend of theoretical papers on adversarial attacks can be only beneficial for the understanding of the topic. I tried to make a thorough reading of the proofs, but I still might have missed some points. I would like to discuss the following points with the authors:\n\n- On the definition of the adversarial risk. I believe it is provable that $A^{\\oplus\\epsilon}$ is  analytic (cf 1 for more details) and hence universally measurable. Idea: write $1_{x\\in A^{\\oplus\\epsilon}}$ as $\\sup_{a\\in A} 1_{x\\in\\bar{B}_\\epsilon(a)}$. Then you can use the results from Bertsekas and Shreve (2004), Prop 7.39 and Corollary 7.42.1. Maybe the authors can use these ideas to prove a more general result. I think all further results can be extended to all Borel sets instead that only $G_\\delta$ and $F_\\sigma$ sets. I am happy to discuss more about this during the rebuttal phase. I might be mistaken, but I think it worth discussing. It would simplify some results in the paper I’d say.\n\n- The authors said they prove the existence of Pure Nash equilibria. Although the classifier is deterministic, the attacker is still « randomized ». Maybe they should mention that the equilibria are hybrid. This result seems right and reasonable.\n\n- I would also suggest the authors to give some more intuition to the different notions of risks the authors introduced. For instance, draw some figures to explain it. It would be more readable for non advertised readers\n\n- Finally, although I enjoyed reading the paper, I also find that the paper lacks a bit of novelty with regards to existing literature (Pydi et al., Dohmatob, Bhagoji et al.). These papers have proved the majority of the results exposed in the paper ($W_\\infty$, $c_\\epsilon$ costs,etc.). The authors managed to treat unbalanced probabilities. This is my major concern about accepting/rejecting the paper. I am willing to discuss with the authors and the other reviewers on this.\n\nFor now, I rate this paper as borderline,  but I am willing to change my rating if the authors explain to me more clearly the novelties of their paper. Moreover, I hope authors can get rid of their hypothesis on $F_\\sigma$ and $G_\\delta$.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The understanding of Adversarial robustness is a very important topic. It can impact positively the safety of autonomous ML systems.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: All the reviewers agreed that this paper provides important contributions in the area of robust learning. I recommend to the authors to incorporate all the comments made by the reviewers in the updated version of the paper. The reviews have indeed brought many important points.
Decision: Accept (Poster)