The Adversarial Consistency of Surrogate Risks for Binary Classification
Authors: Natalie Frank
Jonathan Niles-Weed
Venue: NeurIPS 2023 poster (2023)
Keywords: Adversarial learning
surrogate risks
optimal transport
TL;DR: We prove necessary and sufficient conditions for the statistical consistency of surrogate risks in the adversarial setting

Abstract: We study the consistency of surrogate risks for robust binary classification.
	It is common to learn robust classifiers by adversarial training, which seeks to minimize the expected $0$-$1$ loss when each example can be maliciously corrupted within a small ball.
	We give a simple and complete characterization of the set of surrogate loss functions that are \emph{consistent}, i.e., that can replace the $0$-$1$ loss without affecting the minimizing sequences of the original adversarial risk, for any data distribution.
	We also prove a quantitative version of adversarial consistency for the $\rho$-margin loss.
	Our results reveal that the class of adversarially consistent surrogates is substantially smaller than in the standard setting, where many common surrogates are known to be consistent.

The Adversarial Consistency of Surrogate Risks for Binary Classification
Natalie S. Frank Courant Institute New York University
Jonathan Niles-
Courant Institute New York University New York, NY 10012 j jnw@cims nyu. edu
New York, NY 10012 nf 1066@6yn..eeee edu
Abstract
We study the consistency of surrogate risks for robust binary classification. It is common to learn robust classifiers by adversarial training, which seeks to minimize the expected 0-1 loss when each example can be maliciously corrupted within a small ball. We give simple and complete characterization of the set of surrogate loss functions that are consistent, i.e., that can replace the 1 loss without affecting the minimizing sequences of the original adversarial risk, for any data distribution. We also prove a quantitative version of adversarial consistency for the p-margin loss. Our results reveal that the class of adversarially consistent surrogates is substantially smaller than in the standard setting, where many common surrogates are known be consistent.
Introduction
central issue in the study of neural is their susceptibility adversarial perturbations- perturbations imperceptible to the human eye can cause a neural net to misclassify an image (Szegedy al. 2013 Biggio al.] 2013]. The same phenomenon appears in other types of data such as speech and text. As deep nets are used in applications such as self-driving cars and medical imaging
Paschali al. 2018 Li al. 202T]. training classifiers robust to adversarial perturbations
central question in machine learning.
The foundational theory of surrogates for classication in well understood. In the standard classification setting, one seeks to minimize the classification risk-the proportion of incorrectly classified data. Since minimizing the classification risk is typically computationally intractable (Ben-David al.) 2003). a common approach is to instead minimize a better-behaved alternative called the surrogate risk. However, risk. If for every data distribution, a sequence of functions minimizing the surrogate also minimizes the classification risk, the surrogate risk called consistent. Many classic papers study the consistency of surrogate risks in the standard classification setting [Bartlett et al. 2006 Lin 2004
must verify that classifiers with low surrogate risk also achieve low classification
Steinwart
2007 Philip M. Long 2013 Mingyuan Zhang 2020).
Unlike the standard case, however, little known about the consistency of surrogate risks in the context of adversarial training, which involves risks that compute the supremum of a surrogate loss function over an e-ball. Though this question has been partially studied in the literature [Awasthi] al. 2021a Meunier al. 2022), general theory is lacking. Existing results reveal, however, that the situation is substantially different from the standard case: for instance, [Meunier et al. 2022 show that conver surrogate be adversarially consistent. To our knowledge, adversarially consistent risks are known.
In this work, give a complete characterization of adversarial consistency for surrogate losses.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Our Contributions:
In Section 4 we give surprisingly simple necessary and sufficient condition for adversarial consistency:
Informal Theorem. Under reasonable assumptions on the surrogate loss Ø. the supremum-
based ø-risk is adversarially consistent if and only if 6(a)/2 p(=a)/2 < (0))
In particular, this result proves consistency for any loss function that is not midpoint convex at the origin.
In Section[5] we specialize the case of the p-margin loss, where obtain quantitative proof of adversarial consistency by explicitly bounding the excess adversarial risk.
To the best of the authors' knowledge, this paper is the first to prove that a loss-based learning procedure is consistent for a wide range of distributions in the adversarial setting. As mentioned above, the p-margin loss (p(a) = minn( [1, max(1 a/p, 0)) satisfies the conditions of Informal Theorem above, as does the shifted sigmoid loss (a 1/((1 + exp(a - 7)) with t > 0, which confirms conjecture of Meunier et al. [2022). By contrast, all convex losses satisfy inf @(a) +
(())/2+((-a)/? d(-a)/2 =
(0). and are therefore not adversarially consistent.
In addition to consistency, one would hope to obtain a quantitative comparison between the adversarial surrogate risk and the adversarial classification risk. Our bound in Section 5 shows that the excess error of the adversarial p-margin loss is a linear upper bound on the adversarial classification error, which implies that minimizing the adversarial p-margin loss is an effective procedure for minimizing the adversarial classification error. Extending the bound in Section 5 to further losses remains an open question.
Related Works
Many previous works have studied the consistency of surrogate risks [Bartlett et al. 2006 Lin 2004
Steinwart 2007
Philip M. Long 2013 Mingyuan Zhang. 2020]. The classic papers by [Bartlett et al. 2004 Zhang 2004] explore the consistency of surrogate risks over all measurable functions.
2006
The works [Philip M. Long 2013 Mingyuan Zhang 2020 Awasthi al. 2022
study H-consisteney, generalizes some of
which is consistency restricted to smaller set of functions. Steinwart 2007
these results into a framework referred as calibration. Awasthi et al. [202aa] Bao et al. (202T).
Awasthi et al. [202]c), Meunier et al. [2022] then use this framework to analyze the calibration of adversarial surrogate losses. Furthermore Meunier et al.] [2022] relate calibration to consistency
for adversarial losses in certain cases they show that no convex loss is adversarially consistent.
They also conjecture that a class of surrogate losses called the odd shifted losses are adversarially consistent, Meunier et al. [2022) also show that in a restricted setting, surrogates are consistent for 'optimal attacks'. The proof of our result formalizes this intuition. Simultaneous work [Mao et al.. 2023] shows that the p-margin loss is adversarially H-consistent for typical function classes. Lastly, Bhattacharjee and Chaudhuri 2020 2021] use a different set of techniques to study the consistency of non--nnaannn ponmmeaamctiic methods adversarial scenarios.
Our results rely on recent works establishing the properties of minimizers to surrogate adversarial
risks. (Aasthi et al.] 2021b Pydi and Jog, 2021 |Bungert et al.) 2021] all proved the existence
of minimizers to the adversarial risk and [Pydi and Jog 2021 I] proved a minimax theorem for the
zero-one loss. Building on the work of (Pydi and Jog] 2021]. Frank and Niles Weed [0233 later
proved similar existence and minimax statements for arbitrary surrogate losses. [Tillos et al. [022
2023) extend some of these results to the multiclass case. Lastly, [Trillos and Murray 2020 study further properties of the minimizers to the adversarial classification loss.
3 Problem Setup
This section contains the necessary background for our results. Section 3.1 gives precise definitions
for the main concepts, and Section 3.2 describes the minimax theorems that are at the heart of our proof.
2

---

3.1 Surrogate Risks
This paper studies binary classification on R Explicitly, labels are {-1,+1} and the data is distributed according distribution D on the set Rd {-1,+1}. The measures Pi, Po define the relative probabilities of finding points with given label in region of Rd. Formally, define measures on Rdd by
(1(4) D(A (+1)), = D(A {-1)).
The classification risk R(f) is then the probability of misclassifying a point under D:
R(f) 100) 1(0)2odPP.
(1)
The surrogate to R
( (())PP + M(-[)dPo-
R₂()) -
(2)
classifier can be obtained by minimizing either R or R& over the set all measurable functions. point x is then classified according to sign f. There are many possible choices for di dytypiiclly one chooses a loss that is easy to optimize. In this paper, we assume that non-increasing, non-negative, continuous, and lima x(a)
Assumption 1.
Most surrogate losses in machine learning satisfy this assumption. Leaning algorithms typically optimize the risk in 2 using an iterative procedure, which produces a sequence of functions that minimizes Rg. We call R2 consistent risk and ø consistent loss if for all distributions, every minimizing sequence of Rs is also minimizing sequence of R Alternatively, the risks R. Rs can be expressed in terms of the quantities Po + P1 and 1j = d /d. For all ry E [0, 1]. define
Cln, a)) 11 (1-1) 1020 C*(1) inf a),
(3)
C, no(a) (1 7){(-))))))))))))))))))
(2(1) inf Co a:)
(4)
For more on the definitions of R. Rø, C, Cg. see (Bartlett al. 2006) or Sections 3.1 and 3.2 of Frank and Weed 2023 Using these definitions, RT) C()(x), dx) and
Ro(f) = fo()(x),
(5)
This alternative view of the risks R and Rs provides 'pointwise' criterion for consistency- if the function f(x) minimizes ()()))),)) -) at each point, then it also minimizes Rg. However, minimizers to (n.-) over R do not always exist- consider for instance 7) for the exponential loss ((a) e a In general, for minimizers of Cv -) to exist, one must work over the extended real numbers F = R U {-oc, +oo}. The following proposition proved in Appendix immples that "pointwise" considerations also extends minimizing sequences of functions.
Proposition 1. The following equivalent:
1) & is consistent
2) Every minimizing sequence of Co -) is also a minimizing sequence of C(n,))
3) Every R-valued minimizer of Ry is minimizer R
This result is well-known in prior literature; in particular the equivalence between 2) and 3) is closely related to the equivalence between calibration and consistency in the non-adversarial setting [Steinwart] 2007). Most importantly, the equivalence between [] and 3n) reduces studying minimizing sequences of functionals to studying minimizers of functions. We will show that the equivalence
In context of standard (non adversarial) learning. the concept we defined as consistency often referred to as calibration, see for instance [Bartlett et al. 20066 Steinwart 2007). We opt for the term 'consistency" as the prior works (Aaathh et al. 2021 Meunier et al. 2022 use calibration to refer to a different but related concept in the adversarial setting.
3

---

between 1 and 2) has an analog in the adversarial scenario, but the equivalence between I and 3)
does not.
In the adversarial classification setting, every z-value is perturbed by malicious adversary before undergoing classification by f- We assume that these perturbations bounded by in some norm Il- and furthermore, the adversary knows both our classifier f and the true label of the point x. In other words, f misclassifies (x, v) when there is point x' E (x) for which f(x) = 1 for y = +1 and 1 f(x)0 = for y -1. Conveniently, this criterion can expressed in terms of suprema. For any function we define
(x) sup g(x + h) [|bllsc
A point with label +1 is misclassified when S, (1))))) 1 and point with label - is misclassified when S. (>0))(x = Hence the expected fraction of errors under the adversarial attack is
R ()) ] (. + St (L
(6)
which is called the adversarial classification risk 2 computationally intractable so instead one minimizes surrogate of the form
Again, optimizing the empirical version of (6
R2 - Sc fdP
S.(60 (o(oo-f)dPP
Due to the supremum in this expression, refer such risk supremum-bassed surrogate. We define adversarial consistency as
Definition 1. The risk Ry is adversarially consistent for every data distribution, every sequence I which minimizes Rt over all Borel measurable functions also minimizes Rt. We say that the loss is adversarially consistent the risk R, adversarially consistent.
Many convex and non-convex losses are consistent standard classification (Bartlett al., 2006 Zhang 2004 Steinwart 2007 Reid and Williamson 2009 Lin 2004). By contrast, adversarial con- sistency often fails. For instance, Meunier et al. [022 show that convex losses are not adversarially consistent. Furthermore, their example shows that the equivalence between D and 3) in Proposition ] does not hold the adversarial context. Thus, to understand adversarial consistency, does not suffice to compare minimizers of R% and R To illustrate this distinction, show the following result, adapted from [Meunier et al. 2022).
Proposition 2. Assume that inf, s(a)/2 dl (02 =00). Then & is not adversarially consistent.
Proof. Let Po Pı be the the uniform distribution the ball (n) and let 2R. Let Φ be a loss function for which inf, ((a)/221 o(-a)/2 = (1/2)) = 6(0). Notice that inf, R (f) 2 inf, R(J)) and infy (f) 2 inf Rf) Since IP. = P,, the optimal non-adversarial risk is inf, R(()) = 1/2. Moreover, as (1(122) = <00), the optimal non-adversarial surrogate risk is inf, (f) = (1/(1)) = 6(0). Thus, for the function f 0, R (f*) = inf R(f) = 1/2
and 125(()) =inf, (f) = o(0). Therefore f" minimizes both Rt and Rt. Now consider the
sequence of functions
=
(x) 1-1
x
Because 2R, every point in the support of the distribution can be perturbed to every other point. Thus (, o fa) (x) = 6(11/n) and S. -f)) = *(-1/n). However, S. (.(1))) = and (1()) 1. Therefore, R (f.) o( 1/nn) while R (f.) 1 for all n. As is continuous, limn ((, (0). Thus fa is a minimizing sequence of R3 but not of R Φ is not adversarially consistent.
'Defining this integral requires some care because for Borel function S.(g) may not be measurable; see Section 3.3 and Appendix A of (Frank and Niles-Weed 2023 for details.

---

This example shows that if (J o()). then Φ is not adversarially consistent. The main result of this paper is that this is the only obstruction to adversarial consisteney: & is adversarially consistent if and only if (1/2) (0)).
We begin by showing that this condition suffices for consistency in the non-adversarial setting. Surprisingly, despite the wealth of work on this topic, this condition does not appear to known.
Proposition 3. If (1/2) 6(0), then is consistent.
See Appendix foor proof.
Again, some losses that satisfy this property are the p-margin loss Φa(a) = min(1 max a/p, and the the shifted sigmoid loss proposed by Meunier al. 2022 <(a) = 1/(1 exp(a 7)).
T > O. (In fact, one can show that the class of shifted odd losses proposed by Meunier et al. [2022]
satisfy (2 < (0).)
Notice that all convex losses satisfy (1/2) 6(0):
C3(1/2) inl a
(d(a) + (0(-)) (0))
The opposite inequality follows from the observation that (1/122 - (1/2,,0) 6(0). In contrast, recall that convex loss á with ø' 00) < 0 is consistent Bartlett et al. 2006].
As conjectured by prior work Bao et al. [2021), J, Meunier al. 2002)) the fundamental reason losses with (1/2) < (0) are ad adversarially consistent is that minimizers of (I) :) are uniformly bounded away from O for all ry:
Lemma 1, The loss & satisfies (1(1/2 < 6(0) iff there is an a > 0 for which any minimizer of of Co(),)) satisfies la] 2 a.
See C for proof. Concretely, one can show that for the p-margin loss oy. minimizer of Co (7) :) must satisfy |a*1 2 Similarly, minimizer o² of Co, (1, -) of the shifted sigmoid loss or = (1 + exp(a- - T)), >> is always either -oo or +o0. In 4 we use this property to show that minimizing sequences of R2, must be uniformly bounded away from zero, thus ruling the counterexample presented in Proposition 2
3.2 Minimax Theorems for Adversarial Risks
We study the consistency of o by by comparing minimizing sequences of Rt with those of R In the next section, in order to compare these minimizing sequences, we will attempt to re-write the adversarial loss in 'pointwise' manner similar to Proposition In order achieve this representation of the adversarial loss, we apply minimax and complimentary slackness theorems from [Pydi and Frank and Niles- Weed 2023).
Jog 2021
Before presenting these results, we introduce the 3o- Sc-Wasserstein metric from optimal transport.
For two finite probability measures Q, Q' satisfying Q(R)) QR()"), let 11(Q Q') be the set of couplings between Q and Q':
I Q/) = (r measure on Rd x Rd with (A x Rd)) Q(4), (TR x A) = (A))
The distance between Q' and Q in the Wasserstein co-metric W is defined as
Woo (Q, Q') = inf ess sup ||x yl| ( (x,y)>>
The Woo distance in fact metric on the space of measures. We denote the oo- bo-Wasserstein ball around a measure Q by
B
(Q': O Borel, W. V <
Informally, the measure Q' is in 0 (Q) if perturbing points by at most under the measure Q can produce Q As result, Wasserstein co-balls are fairly useful for modeling adversarial attacks. Specifically, one can show:
5

---

Lemma 2. For any function 9 and measures Q Q with W (Q', Q S the inequality f (e(g)d gdll'' holds.
See Appendix D for proof.
Minimax theorems from prior work use this framework to introduce dual problems to the adversarial classification risks (6 and Let Pb P1 be finite Borel measures and define
RCP. P() = f
d(P
(8)
d(TP' P1)
where C* is defined by (3. The next theorem states that maximizing R over Wo balls is in fact dual problem minimizing R
Theorem 1. Let R be defined by (8)
inf R-valued
R=
sup Fy (Pa) P (Pi)
R(F
(9)
and furthermore equality is attained for some Borel measurable j and Pl, Po with Woo (Po: Po) Se and W PI),
The first to show such theorem was Pydi and Jog 2021 In comparison to their Theorem 8. Theorem removes the assumption that 1o, 11 are absolutely continuous with respect to Lebesgue measure and shows that the minimizer in fact Borel. We prove this theorem in Appendix Frank and Niles- Weed 2023] prove similar statement for the surrogate risk R This time, the dual objective is
(P P() - f
dIP
d(P' + F())
(10)
d(P) +P)
with O defined by 4
Theorem 2. Assume that Assumption
7 holds, and define Rsg by (T). Then
inf Borel I R-valued
R& = sup (P% P1)
(11)
P,EB, (Po) P(BB((P)) (Pr)
and furthermore equality in the dual problem is attained for some P1, P2 with Woc (PG, and (P1, P1) S.c.
Frank and Niles- Weed
2023 proved this statement in Theorem 6 but with the infimum taken
R-valued functions. To extend the result to RR-valued functions as in Theorem 2 we show that
inl, /orel, Revalued (t,()) infy Borelf R-valued R (J) Appendix B
Adversarially Consistent Losses
This section contains our main results on adversarial consistency. In light of Proposition task to show that loss satisfying (1/2)) < ((0) adversarially consistent.
2 our main
At high level, we will show that every minimizing sequence of Rt must also minimize R However, directly analyzing minimizing sequences (fa) of It, and R is challenging due the supremums in the definitions of the adversarial risks. We therefore develop alternate characterizations of minimizing sequences to both functionals, based on complimentary slackness conditions derived from the convex duality results of Section 3.2. However, unlike standard complementary slackness conditions well known from convex optimization, these theorems allow us to characterize minimizing sequences as well as minimizers.
4.1 Approximate Complimentary Slackness
We first state this slackness result for the surrogate case, due to Frank and Niles- Weed 2023 Lemmas
16 and 26] and Theorem 2

---

Proposition 4. Let PT) be any maximizers of Rs over (P,)) Define F = Fo + Pi. 17" dPt/dF' If fo is minimizing sequence for Ry then the following hold:
lim / n-000
Cola" Fn) = { (3(1))
(12)
lim m / Sc( fn)
/ fn fn
Se( 10000100000 100 = (13)
lim n-+00
Proof. Let Ry be the minimal value of R% and choose a d Then for sufficiently large N. n 2 N implies that (fx) S R2 + Lemma 2 and the definition of C% in (4) further imply that
R2 + / Se fn)dF
(o(do-f))dP, 2 f fndPt f 00 fn- 2 R (14)
As -. - C )dl,, this relation immediately implies 12
Next, Lemmal again implies that
f 6 fn)dP1
/ 1o and f 0 2 / f0o- 1po-frdPp (15)
while 14)
implies that
R - 1 SadFy 10 1oor++000--iii - < 0.
Therefore, subtracting I o fndPi + 1000-fnie from
14 results in
(f (. k.)
IndPi) 00oond
+ (/ (/S.(0o- fa)dPo f -ndTi
8
20. 0. (16)
Again, implies that the quantities on parentheses are both positive which implies (3)
Proposition 4 shows that minimizing sequences of R, satisfy two properties: 1) The sequence {fr
must minimize the standard ø-risk R. with measures P PP in place of Po, PP 2) At the limit, the measures 1P are best adversarial attacks on & o fr, ó o -nn In fact, one can show that {fr} minimizing sequence of R2, if and only if it satisfies these properties. Crucially, very similar characterization holds for minimizers of the adversarial classification loss. We state and prove the only if' direction of this characterization in Proposition [
Proposition 5. Let fn. be a sequence and let 12 IP; be measures in B (P.). Define F = 12 + Pi. 17" /dP" If the following two conditions hold:
lim / C(n', fT))PP - ('))))d
(17)
lim / (,(1,,50)PP f 1 so = 0, n n
(c(( - / I = 0, (18)
lim
n
then In is minimizing sequence of R
Proof. Equation 17 implies that the limit lim fn)d"" exists. Thus 17 and 18 imply
that
lim (fx))) lim / (011) / (.(1,,20)dPo 100
lim / 1 + n lim / [((n = -' c'(r))pp=PPPP R(PP).P1) n
/ 1 10.2
Therefore, Strong duality (Theorem
I then implics that sup R(PPY IP()) inf R RC)
lim (fa)
P,E (Po) P(E8?"(P))
Borel
B valued
and therefore, Sn is minimizing sequence.

---

We end this section by comparing the different criteria for consistency presented in Proposition| 1 with Propositions and [ Together, Propositions I and [ will allow us compare minimizing sequences
of RC to those of St by showing that any sequence satisfying 122 (13) must also satisfy (17)- (8)
This statement is the analog to 2) of Proposition [ Indeed, because Cø(n", f.)) C2 ) 12 is
actually equivalent to Co (17" fn) - (7 in L' (FP)) However, the extra criterion (18) implies
an additional constraint the structure of the minimizing sequence. This additional constraint is the reason 3) of Proposition is false in the adversarial setting. In the restricted situation where R = R.
Meunier al. (2022) show that (12) implies (Proposition 4.2). However, this observation does
not suffice to conclude consistency.
4.2 Adversarial Consistency
We are now in position to prove consistency. Before presenting the full proof, we pause to discuss the overall strategy. Consistency will follow from three considerations. First, every minimizing
sequence of Ht, satisfies conditions [22 and (3). Second, conditions (12 and 13 imply the very
similar conditions (17) and (8). Finally, any function sequence satisfying and (18 must be
minimizing sequence to R The first and last steps are the content of Propositions and 5
so
remains to justify the middle step.
Verifying that (2) implics (17) is straightforward. The relation [12p actually states that f, minimizes the standard surrogate risk with respect to the distribution given by Pú. 121 Therefore (22 implies
so long as Φ is consistent.
The main difficulty is verifying (18). due to the discontinuity of la<o. 1.20 at O. Due to this discontinuity, one cannot directly argue that (13) implies (18): simplify the discussion, assume that Φ is strictly decreasing on a neighborhood of the origin, in which case 1,<00 = =(())=)(()) and
1020 200)- Recall that according (13), in the limit n - 0o, 0r PP are the strongest attack in _ (1P)) x B (PP)), or informally, (, fx) (x) approaches o( (x') for optimal perturbation w.h.p., with a similar condition for & o - -nn However, due to the discontinuity of
(0)-a)2d(0) (0),, if fn (x') + 0 as > 20, this relation does not imply that 1 (.. fa)))=0000
approaches do f.. (x))20-
Lemma I says that (1/2) < (0), minimizers of Co .) are uniformly bounded away from This fact suggests that minimizing sequences will also be bounded away from the origin, which will allow us to avoid the discontinuity there. Concretely, we show:
Lemma Let (1/2) < (()). Then there is 8 > 0 and a > O with Φ(c) < ((0) for which a E [-c, c] implies Cn ax) 2 C2(n) + ô, uniformly in n. Furthermore, for this value of c, i > then d(a)) < o(c).
We prove this lemma in Appendix C Because Co(n", Cz(1") in L' (IF). Lemma 3 implies that
lim (Pa E c-c,c) n-
(19)
This relation the key fact that allows us to show that (()) is essential for this step of the argument.
13 implies 18 The condition C1 <
Lastly, Lemma implies that I' S. (1,,,0)dP; 2 1 dP and thus to validate (18), it suffices to verify the opposite inequality in the limit n + cc.
Lemma 4. Let fn be sequence of functions and let F. E (Po), Pi E (%) (P1). The equation
lim / S.(Ln,5o)dP; liminf n-0 / [Ir.SodPy
(20)
implies the first relation of 18 and
/ |
lim
(,( I limint
(21)
n n-
implies the second relation of 188)
See Appendix F for proof. These considerations suffice to prove the main result of this paper:
8

---

Theorem 3. The loss & is adversarially consistent if and only if C < 6(0).
Proof. The 'nly if' portion of the statement is Proposition 2
To show the 'if" statement, recall the standard analysis fact: lim, an iff for all subsequences {anz) J. there is further subsequence Ongz for which limn- anys = a. This result implies that to prove Rt is consistent, it suffices to show that every minimizing sequence fa of Rg has subsequence fny that minimizes R
Let fn be a minimizing sequence of R. For convenience, pick a subsequence fny for which the limits lim f (c(1 <o)dPPo <o, limj-too f (e (,,22))dP 20) both exist. For notational clarity, we drop the subscript and denote this sequence as fu.
By Proposition 4 the equations 122 and (3) hold. We will argue that fn in fact minimizing sequence of 1t by verifying the conditions of Proposition
First, the relation (12) states that the sequence fn minimizes the standard ø-riskk for the distribution given by Fi and I... As the loss & is consistent by Proposition 3 the sequence fn must minimize the standard classification risk for the distribution 12 Pi. This statement implies (17). Next we will argue that (18) holds.
Let c, 5 be as in Lemma Because Co(n", C)("") implies that Co ;(nn",n) fn) converges
to (3n"") in I.A. However, I,- convergence implies convergence measure (see for instance Proposition 2.29 of [Folland ). and therefore limm-+oc P (C > Cg(n") + 6) = 0. Lemma then implies that for 0,1
lim (fa E (-c,,c) = 0.
(22)
Next, because is non-increasing, f < 0 implies Φ(f) 2 (0) and thus 1 I 1 100 Furthermore, as the function a +> 1a20 is monotone and upper semi-comtinuous,
f (c1
/ Sc (c(1pop.200))d S / 15,6000)2200))
(23)
Let % be coupling between P. and P for which ess sup ||--X/ y S Then the measure %
supported on A, = ((x,y): ||--|| S <). Furthermore, as (1bof 2 fo (x') everywhere
on A., the relation (00 > do (x') actually holds a.c. Therefore, ((3) actually implies
that (. o (x) - 0 (x') converges in me-muaurre to In particular, since ((c) < ((0).
lim, 71 (o) ((f))(xx))(((((()))))) 2 <(0) - -(()) = 0 and thus lim, (S fn)(x) Therefore.
((0) noo fx(xx) < o(c))
liminf IP, (S. fn) (x) 2 o(0)) = lim (S. 20) o()))
n-
n
lim (0 o fa (x') z x(c)) inf fx(x') o(c)) n-
R-550
This calculation implics
11.,60//000222000000 / < lim
lim inf /
/ 1000 S lim inf n-occ
f 1/,SaPPP (24)
liminf
The last inequality follows because Lemma states that implies d(a) < ((()) and therefore I (olc2 & 50 Equation 22 then implies
/ 10000 < lim / 1 lim inf n-000
/ 11.5-odP3
lim inf
limmin
(25)
n0
n2400
Recall that the sequence fn was chosen that the limit lim J (c(L exists. Combining this fact with (3). (24). and (55 results in
5.(1 (1 < liminf / 11.5-odPi
/ 1
lim sup nt nx
lim inf n-
(26)
The first relation of 18 then follows from
26 together with Lemma

---

A similar argument implies the second relation of (T8). Because 1/20 = =1-/20 S 1 1-50, the same chain of inequalities as
and (25) implies that
/ (. I lim sup
/ 1 1-1-5- PP = lim inf n=+00
/ 1 In22
lim sup n-+00
Sc(1 (o) - lim n
10+000
As c > 0, it follows that Sup f ( 5.,1) S lim liminf,-- 7 S sn Once again, the
second expression of (18) follows from this relation and Lemma
5
Quantitative Bounds for the p-Margin Loss
As discussed in the introduction, statistical consistency is not the only property one would want from surrogate. Hopefully, minimizing a surrogate will also efficiently minimize the classification loss. Bartlett et al. 2006]. Steinwart (2007] Reid and Williamson 2009] prove bounds of the form R(F) R. S Go( (T)() R for function Go and R. inf, R(f). , R inf (f) The function Go is an upper bound on the rate of convergence of the classification risk in terms of the rate of convergence of the surrogate risk. One would hope that G& is not logarithmic, as such a bound could imply that reducing R( by quantity A could require an exponential change of e in R (f) Rg... Bartlett et al. (2006) compute such Ge for several popular losses in the standard classification setting. For example, they show the bounds (0)
R.
for the hinge loss
σ(a) = (1 - a)++ and (f) = v for the squared hinge loss d(a) = (1 a On can prove an analogous bound for the p-margin loss in the adversarial setting:
Theorem 4. Let do = min(1, max(1 a/p,0)) be the p-margin loss, R inf, Rf),), and
Ry (,) = =iff R,,, (f). Then
R² - R. S 10, B
Notice that this theorem immediately implics that the p-margin loss is in fact adversarially consistent. The proof below is completely independent of the argument in Section
Proof. Notice that for the the optimal adversarial classification risk Rs However, since (p(a) 2 Lago and Φp(-a) 2 1a>0 for any a, one can conclude that Rs (f) S R% (f). Therefore,
p p-margin loss, C%2, = C and therefore, the optimal op- R 2,.. equals
RC) - R. = (f) - Re S R (f) R
This bound implies that reducing the excess adversarial p-margin loss by A also reduces upper bound on the excess adversarial classification loss by A. Thus, one would expect that minimizing the adversarial p-margin risk would be an effective procedure for minimizing the adversarial classification risk.
Extending Theorem to other losses remains open problem. In the non-adversarial scenario, many prior works develop techniques for computing such bounds. These include the v V-transform of (Bartlett al. 2006). calibration analysis in [Steinwart 2007), and special techniques for proper
losses in [Reid and Williamson 2009]
Contemporary work MMo et al. 2023 derives an H-consistency surrogate risk bound for variant of the adversarial p-margin loss.
Conclusion
In conclusion, proved that the adversarial training procedure is consistent for perturbations in an e-ball an only if (1/2)) < (0)). The technique that proved consistency extends to perturbation sets which satisfy existence and minimax theorems analogous to Theorems [ and 2 Furthermore, we showed quantitative excess risk bound for the adversarial p-margin loss. Finding such bounds for other losses remains an open problem. We hope that insights consistency and the structure of adversarial learning will lead to the design of better adversarial learning algorithmss
10

---

Acknowledgments and Disclosure of Funding
Natalic Frank was supported in part by the Research Training Group in Modeling and Simulation funded by the National Science Foundation via grant RTG/DMS 1646339. Jonathan Niles- Weed was supported in part by Sloan Research Fellowship.
References
Awasthi, N. Frank, A. Mao, M. Mohri, and Y. Zhong. Calibration and consistency of adversarial surrogate losses. Neurlps, 2021a.
P. Awasthi, N. S. Frank, and M. Mohri. On the existence of the adversarial bayes classifier (extended version). arxiv, 2021b.
Awasthi, A. Mao, M. Mohri, and Zhong. A finer calibration analysis for adversarial robustness. arxiv, 2021c.
P. Awasthi, A. Mao, M. Mohri, and Y. Zhong. H-consistency bounds for surrogate loss minimizers. In Proceedings of the 39th International Conference on Machine Learning. PMLR, 2022.
H. Bao, C. Scott, and M. Sugiyama. Calibrated surrogate losses for adversarially robust classification. arxiv, 2021.
L. Bartlett, M. Jordan, and J. D. McAuliffe. Convexity, classification, and risk bounds. Journal of the American Statistical Association, 101(473), 2006.
S. Ben-David, N. Eiron, and P. M. Long. On the difficulty of approximately maximizing agreements. Journal of Computer System Sciences, 2003.
R. Bhattacharjee and K. Chaudhuri. When are non-parametric methods robust? PMLR, 2020.
R. Bhattacharjec and K. Chaudhuri. Consistent non-parametric methods for maximizing robustness. Neurlps, 2021.
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 machine learning and knowledge discovery in databases, pages 387-402. Springer, 2013.
L. Bungert, N. G. Trillos, and R. Murray. The geometry of adversarial training in binary classification. arxiv, 2021.
G. B. Folland. Real analysis: modern techniques and their applications, volume 40. John Wiley & Sons, 1999.
N. S. Frank and J. Niles-Weed. Existence and minimax theorems for adversarial surrogate risks in binary classification. arXiv,, 2023.
Y. Li, X. Xu, J. Xiao, S. Li, and T. Shen. Adaptive square attack: Fooling autonomous cars with adversarial traffic signs. IEEE Internet of Things Journal, 8(8), 2021.
Y. Lin. A note margin-bass based loss functions in classification. Statistics & Probability Letters, 68 (1):73-82, 2004.
A. Mao, M. Mohri, and Y. Zhong. Cross-entropy loss functions: Theoretical analysis and applications, 2023.
L. Meunier, R. Ettedgui, R. Pinot, Chevaleyre, and J. Atif. Towards consistency in adversarial classification. arXiv, 2022.
S. A. Mingyuan Zhang. Consistency vs. h-consistency: The interplay between surrogate loss functions and the scoring function class. Neurlps, 2020.
M. Paschali, S. Conjeti, Navarro, and Navab. Generalizability vs. robustness: Adversarial examples for medical imaging, Springer, 2018.

---

R. A. S. Philip M. Long. Consistency versus realizable h-consisteney for multiclass classification. ICML, 2013.
M. S. Pydi and V. Jog. The many faces of adversarial risk. Neural Information Processing Systems, 2021.
M. D. Reid and R. C. Williamson. Surrogate regret bounds for proper losses. In Proceedings of the 26th Annual International Conference on Machine Learning, New York, NY, USA, 2009. Association for Computing Machinery.
I. Steinwart. How to compare different loss functions and their risks. Constructive Approximation. 2007.
C. Szegedy, W. Zaremba, I. Sutskever, J. Bruna, D. Erhan, I. Goodfellow, and R. Fergus. Intriguing properties of neural networks. arXiv preprint arXiv: 13 12.61999, 2013.
N. G. Trillos and R. Murray. Adversarial classification: Necessary conditions and geometric flows. arxiv, 2020.
N. G. Trillos, M. Jacobs, and J. Kim. The multimarginal optimal transport formulation of adversarial multiclass classification. arXiv, 2022.
N. G. Trillos, M. Jacobs, and J. Kim. On the existence of solutions to adversarial training in multiclass classification, 2023.
T. Zhang. Statistical behavior and consistency of classification methods based on convex risk minimization. The Annals of Statistics, 2004.
12


Reviews:
[{"review_id": "0PhDsh8L1U", "reviewer": "Reviewer_PJjd", "summary": "this paper tackles the problem of consistency in adversarial classification. Consistent losses are losses whose minimization lead to the minimization of the 0/1 loss. Although consistent losses are known for a long time in standard classification, they were not known in the adversarial setting. This paper show a simple necessary and sufficient condition for a loss to be adversarially consistent. ", "questions": "1. It seems like thm1 is already known. In particular, points (1) and (2) boil down to the equivalence between calibration and consistency in the non adversarial setting, isn’t it right ?\n\n2. In Proposition 4: aren’t \\mathbb{P}*_0 and \\mathbb{P}*_1 maximizers of \\bar{R}_\\phi instead of \\bar{R} ? I don’t see the logic here.\nMake explicit that there exists a pair \\mathbb{P}*_0 and \\mathbb{P}*_1 maximizing both \\bar{R} and \\bar{R}_\\phi. I also don't see how it is related to the reference [Frank and Niles-Weed]. Please make this clearer.\n\n", "limitations": "limitations have been addressed.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "The existence of consistent losses in adversarial classification is a very important problem, and this paper solves it in some way.\nUp to section 3, the paper is very well written and easy to understand.\nAlso, section 5 provides very useful bounds on margin losses, which are the counterpart of what was published in the non-adversarial setting by Bartlett, Zhang, and others.\n", "weaknesses": "section 4 is much harder to understand. For example, to understand propositions in that section, reading [Frank and Niles-Weed] helps a lot. In my opinion, authors should work on improving the clarity of this section.\n\ndetails:\n- Proposition 2, Line 139: a unit ball is of radius 1. But here, radius is R=epsilon/2\n- Proposition 3, Line 211: recall that the inequality holds thanks to assumption 1, to make things clearer.\n- Why put the proof of proposition 2 in the paper ? The proof is exactly the same as Meunier’s proof of the same result. Removing the proof would release space to improve clarity of section 4.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "   Weaknesses:\n\n - We will look for ways to clarify Section 4 by adding additional context for the main Propositions. Regarding  Proposition 2, the statement is of course crucial for our main theorem, and this example is both simple and illuminating.\n    \n -  Your comments on lines 139, 211: we have incorporated your feedback.\n\n\n    \n   Questions:\n\n    \n 1. Yes you are right. We included a proof of this result only because we couldn't find it stated in this precise form in prior work. We will clarify that proposition 1 is already known and add a citation to results on calibration.\n\n    \n 2. Yes, that was a typo, thank you for finding this mistake! To clarify, $\\mathbb P_0^*$ and $\\mathbb P_1^*$ are maximizers of $\\bar R_\\phi$, and we do not need to assume that they are maximizers of $\\bar R$.\n\n    \n\n\n  Relation to the reference [Frank and Niles-Weed]:\n    \n Lemma 16 of [Frank and Niles-Weed] proves an approximate complementary slackness condition for a convex relaxation to $R_\\phi^\\epsilon$ which they call $\\Theta$. Later, in Lemma 26, they prove that minimizing the convex relaxation $\\Theta$ is equivalent to minimizing $R_\\phi^\\epsilon$. Combining the approximate complimentary slackness result (Lemma 16 of [Frank Niles-Weed]) together with the equivalence of minimizing $\\Theta$ and $R_\\phi^\\epsilon$ (Lemma 26 of [Frank Niles-Weed]) results in Proposition 4 of our paper.\n  We will clarify this in our revised version.\n\n  To avoid confusion, we will include a self-contained proof of this result in our appendix.\n"}, {"review_id": "GP5cFqddQM", "reviewer": "Reviewer_epdC", "summary": "The paper analyzes the consistency of surrogate losses in the case where there is an adversary that perturbs the sample data. Unlike in empirical risk minimization, where many convex surrogate losses have been proven to be consistent, the authors show that no convex surrogate losses are adversarially consistent. The authors provide a theoretical analysis to back up the claim. In addition, the authors design a non-convex surrogate loss that is adversarially consistent.", "questions": "Please answer my concerns in the previous section.\n", "limitations": "No concern.\n", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "- The paper presents an important analysis of the consistency of surrogate losses under adversarial examples setting. \n- The authors provide a thorough theoretical analysis of the property of surrogate losses under adversarial examples setting.\n- The authors propose a surrogate loss that is adversarially consistent.", "weaknesses": "- The presentation of the paper is a bit hard to parse. For example, some of the notations are used before they are defined, like in the last few paragraphs of the introduction.\n- To improve the clarity of the presentations, I suggest the authors incorporate some figures to illustrate the difference of consistency property in adversarial vs regular cases.\n- It will be good to also show the benefit of the adversarially consistent surrogate loss empirically. It could be experiments on real-world data or even some synthetic data to demonstrate the effect of having adversarially consistent surrogate loss in practice", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "- We apologize we forgot to define $\\tau$ towards the end of the introduction. In the shifted sigmoid loss, the constant $\\tau$ is any positive number.\n    The remaining notation in this paragraph seems to be properly defined, but in our revision we will try to clarify this part of the paper further.\n\n\n - Thank you for the suggestion to include figures. Space permitting, we will include several simple examples in the revised version to illustrate the main concepts.\n\n - Yes, running an experiment on MNIST comparing different losses would definitely be interesting. To limit the scope of this paper, we focus on theoretical aspects of adversarial learning and leave experiments for future work.\n    \n"}, {"review_id": "g6hMYoMKLM", "reviewer": "Reviewer_6vgU", "summary": "The paper provides a sufficient and necessary condition for surrogate loss to be adversarial consistency, and provide $\\rho$-margin loss that satisfies the proposed condition so that it can replace 0-1 loss.", "questions": "In the paper, the author also presents another shifted sigmoid loss that satisfies the consistency property. I wonder if the author can shed any light on the performance of such loss function used in adversarial training on some simple dataset like MNIST.", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Understanding the consistency of loss in the adversarial setting is a rather ongoing topic and hasn’t been addressed yet. The paper studies the consistency of surrogate loss for robust binary classification and presents some examples of loss function that satisfies the calibration condition, which has a good contribution to the community. Past work shows no convex loss (which people often use in practice) is adversarially consistent. This paper further provides sufficient and necessary conditions regarding what kind of surrogate loss is adversarially consistent. The presentation is clear and easy to follow.", "weaknesses": "It shouldn’t be surprising that $\\rho$-margin loss can be a good surrogate loss for adversarial training, as when $\\rho$ is extremely small the loss is approximately 0-1 loss. Yet such loss is non-differentiable and therefore hard to use in practice. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "- Somewhat surprisingly, there are surrogate losses very close to the $0$-$1$ loss that are not adversarially consistent. Let $\\psi(\\alpha)=1/(1+\\exp(\\alpha))$) be the sigmoid loss and define $\\phi_K(\\alpha)=\\psi(K\\alpha)$. Notice that for large $K$, $\\phi_K$ is also a close approximation  to the 0-1 loss. However, our results imply that $\\phi_K$ is not adversarially consistent.\n    This example illustrates that the consistency of the $\\rho$ margin loss does not follow merely from the fact that it approximates the $0$-$1$ loss well.\n\n- Yes, running an experiment on MNIST comparing different losses would definitely be interesting. To limit the scope of this paper, we focus on theoretical aspects of adversarial learning and leave experiments for future work.\n"}, {"review_id": "oBysBvgFJF", "reviewer": "Reviewer_QDX6", "summary": "This paper proves the necessary and sufficient condition for a loss function to be adversarially consistent.\nIn the previous literature, either adversarial consistency for restricted hypothesis spaces or negative results for adversarial consistency has been known.\nThis paper follows this research line to provide a general condition to characterize loss functions.\nThe condition only requires $C\\_\\\\phi^\\*(1/2) < \\\\phi(0)$, which is quite simple to check.\nThis even holds for nonconvex loss functions.\nThe proof technique relies on the strong duality and complementary slackness results between adversarial surrogate loss minimization and the optimal coupling between benign and adversarial distributions.", "questions": "- (Comment) In the introduction, you may consider emphasizing the main result shown in this paper is related to consistency for all measurable functions, not $\\\\mathcal{H}$-consistency, to clarify how the result differs from the previous works.\n- (Question) Regarding Proposition 2: The counterexample $\\\\mathbb{P}\\_0 = \\\\mathbb{P}\\_1$ seems very malicious and rarely happens in practice. Are there any other counterexamples for which the corresponding loss function is not adversarially consistent?\n- (Comment) In the definition of $W\\_\\\\infty$, it is better to explain what $(x,y) \\\\sim \\\\gamma$ does mean.\n- (Typo) In l.233 \"fo\" -> \"of\"\n- (Typo) In l.260 $R$ -> $R^\\\\epsilon$\n- (Comment) In l.275, it seems better to discuss the existence of the coupling $\\\\gamma\\_i$.\n- (Comment) In l.307, I don't think Theorem 4 immediately implies adversarial consistency because it is unclear whether the inequality is tight for any distributions.", "limitations": "The authors mention the limitations in conclusion: The extension of the convergence rate for general loss functions is left open.\n\nThis is theoretical work, and potential negative societal concerns are not applicable.", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Very general condition to characterize adversarially consistent losses: Unlike previous results of adversarial $\\\\mathcal{H}$-consistency (Awasthi et al. (2021)) and negative results for adversarial consistency (Meunier et al. (2022)), this work contributes to show the necessary and sufficient condition for a loss function to be adversarially consistent. This is a new insight into the community and may help design loss functions in adversarial training.\n- The condition applies even to nonconvex losses: Traditionally, the theory of calibrated losses mainly concerns convex losses, such as Bartlett et al. (2006) because their proof technique essentially relies on the first-order optimality condition when characterizing loss minimizers. This is a transparent proof technique yet excludes nonconvex losses. In contrast, the proof technique of this paper first translates the optimality of the adversarial loss into the optimal coupling (Propositions 4 and 5) and then deals with the standard consistency analysis for the adversarial distribution $\\\\mathbb{P}^\\*$ (by leveraging Lemma 1).", "weaknesses": "Overall, I do not see any concerns about this paper.\nThere are a few minor comments and questions, which are mentioned in the following \"Questions.\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "- Thank you for catching those typos. We have corrected them in our paper.\n\n    \n- Regarding proposition 2: Yes you are correct that the counter example $\\mathbb P_0=\\mathbb P_1$ is particularly malicious. We are currently writing a follow-up paper that identifies all the counterexamples to consistency for $\\phi$ satisfying $C_\\phi^*(1/2)=\\phi(0)$.\n\n    \n- About Theorem 4 and consistency: Let $f_n$ be a minimizing sequence of $R_{\\phi_\\rho}^\\epsilon$: then $\\lim_{n\\to \\infty} R_{\\phi_\\rho}^\\epsilon(f_n)=R^\\epsilon_{\\phi_\\rho,*}$. \n   \nThe inequality in Theorem 4 immediately implies that $\\lim_{n\\to \\infty} R^\\epsilon(f_n)=R^\\epsilon_*$, so $f_n$ is a minimizing sequence for the adversarial classification risk. Thus the $\\rho$-margin loss is consistent. "}]

Author rebuttal:

Meta-review: ## Summary

This paper studies consistency in adversarial classification. Specifically, they are concerned with losses that are good surrogates for the 0/1 loss (minimizing one leads to minimizing the other). In contrast to non-robust ML, such losses were not known for adversarial robustness before this paper. As one of the main results, the paper shows necessary and sufficient conditions for a loss function to be adversarially consistent. The reviewers found this to be novel, building on several prior works. One of the new contributions is that the authors' results apply to non-convex loss functions. One of the techniques in the paper translates the optimality of the adversarial loss into the optimal coupling and then uses a adversarial consistency analysis. The reviewers (after sufficient discussion) found the theoretical analysis to be correct and clear, and the reviewers also found the results overall to be compelling.

The reason the recommendation is not higher is simply that there was not enough support from the reviewers about the impact/originality/difficulty of the work. It seems like a solid contribution to the field.

## Improvements

There were no major concerns with the paper. However, there were several suggestions for improvements for the final version of the paper. For example:
- clarify that proposition 1 is already known
- fix several typos
- improve the introductions and add more definitions of notation
- add expository figures to illustrate the key ideas and concepts
- include some experiments to demonstrate the results (e.g., on synthetic toy examples)
Decision: Accept (poster)