Towards Consistency in Adversarial Classification
Authors: Laurent Meunier
Raphael Ettedgui
Rafael Pinot
Yann Chevaleyre
Jamal Atif
Venue: NeurIPS 2022 Accept (2022)
Keywords: adversarial
consistency
calibration

Abstract: In this paper, we study the problem of consistency in the context of adversarial examples. Specifically, we tackle the following question: can surrogate losses still be used as a proxy for minimizing the $0/1$ loss in the presence of an adversary that alters the inputs at test-time? Different from the standard classification task, this question cannot be reduced to a point-wise minimization problem, and calibration needs not to be sufficient to ensure consistency. In this paper, we expose some pathological behaviors specific to the adversarial problem, and show that no convex surrogate loss can be consistent or calibrated in this context. It is therefore necessary to design another class of surrogate functions that can be used to solve the adversarial consistency issue. As a first step towards designing such a class, we identify sufficient and necessary conditions for a surrogate loss to be calibrated in both the adversarial and standard settings. Finally, we give some directions for building a class of losses that could be consistent in the adversarial framework.



Towards Consistency in Adversarial Classification
Laurent Meunier 1.2
Raphaël Ettedgui'
Rafael Pinot
Yann Chevaleyre'
Jamal Atif
Université Paris- Paris-Dauphine PSL Research University, CNRS, LAMSADE, Paris, France M AI Research, Paris, France
Boole Polytechnique Fédérale de Lausanne (EPFL), Switzerland
Abstract
In this paper, we study the problem of consistency in the context of adversarial examples. Specifically, we tackle the following question:
Can surrogate losses still be used as a proxy for minimizing the 0/1 loss in the presence of adversary that alters the inputs at test-time?
Different from the standard classification task, this question cannot be reduced a point-wise minimization problem, and calibration needs not to be sufficient to ensure consistency. In this paper, expose some pathological behaviors specific to the adversarial problem, and show that no convex surrogate loss can be consistent calibrated in this context. surrogate functions that can be used to solve the adversarial consistency issue. As first step towards designing such class, identify sufficient and necessary conditions for surrogate loss to be calibrated in both the adversarial and standard settings. Finally, we give some directions for building class of losses that could be consistent in the adversarial framework.
therefore necessary design another class of
1 Introduction
State-of-the of-tte-art machine learning classifiers are known be vulnerable adversarial example at- tacks [18 i.e., perturbation of the input data at test time that, while imperceptible, can significantly influence the classifier's ' output. This can have extreme consequences real-life scenarios such as autonomous cars [19] Therefore, it is necessary to design robust classifiers that present worst-case guarantees against a range of possible perturbations. To account for the possibility of adversary manipulating the inputs at test time, we need to revisit the standard risk minimization problem by penalizing any classification model that might change its decision when the point of interest is slightly changed. Essentially, this is done by replacing the standard (pointwise) 0/1 loss with an adversarial version that mimics its behavior locally but also penalizes any error in a given region around the point on which it is evaluated.
Yet, just like the 0/1 loss, its adversarial counterpart is convex, which renders the risk minimization difficult. To circumvent this limitation, we take inspiration from the standard learning theory approach which consists in solving a simpler optimization problem where the non-convex loss function replaced by convex surrogate. In general, the surrogate loss is chosen to have a property called consistency G. 17,, which essentially guarantees that any sequence of classifiers that minimizes the surrogate objective must also be sequence that minimizes the Bayes risk. In the context of standard classification, large family of convex losses, called classifier-onsiiste property. This class notoriously includes the hinge loss, the logistic loss and the square loss.
exhibits this
However, the adversarial version of these surrogate losses need not exhibit the same consistency properties with respect to the adversarial 0/1 loss. In fact, most existing results in the standard
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

framework rely on reduction of the global consisteney problem to point-wise problem, called calibration. However, this approach not feasible in the adversarial setting, because the new losses are by nature non-point-wise the optimum for given input may depend on yet a whole other set of inputs 3 Studying the concepts of calibration and consistency in an adversarial context remains an open and understudied issue. Furthermore, this is a complex and technical area of research, that requires a rigorous analysis, since small tweaks in definitions can quickly make results meaningless or inaccurate. This difficulty is illustrated in the literature, where articles published in high profile conferences tend to contradict or refute each other 1
Objective & Contributions. The objective of our work is to try and identify possible sources of confusion that may hinder the understanding of the concepts of calibration and consistency in the adversarial setting. In particular, we first come back in Section 2 on the problem of consistency and calibration in the standard setting and carefully define their adversarial counterpart. In doing so, we note that previous papers studying adversarial surrogate losses 4 1 3 did not use the same 0/1-loss as the one used in seminal papers on consistency 20
This difference might be erucial since it may lead to inaccurate results (see Section 5 We then study in Section B the problem of calibration in the adversarial setting and provide both necessary and sufficient conditions for a loss to be calibrated in this setting. It also worth noting that our results are easily extendable to H-calibration (see Appendix D. One on the main takeaway of our analysis is that no convex surrogate loss can be calibrated in the adversarial setting. We however characterize a set of non-convex loss functions, namely shifted odd functions that solve the calibration problem in the adversarial setting. Finally, we focus the problem of consistency in the adversarial setting in Section 4 Based on min-max arguments, we provide insights that might help paving a way to prove consistency of shifted odd functions in the adversarial setting. Specifically, we prove strong duality results for these losses and show tight links with the 0/1-loss. From these insights, we are able to provide a close but weaker property consistency.
2 Notions of Calibration and Consistency
Let us consider classification task with input space X' and output space y = (-1,+11 Let (X' d) be a proper Polish (i.e. completely separable) metric space representing the inputs space. For all x E X and 8 > 0, we denote (2)x) the closed ball of radius 5 and center x. We also assume that for all X and 8 0, (2) contains least two pointe] Let us also endow y with the trivial metric d' d'(v.'') 3/) = 1 y Then the space (X x V d a d') is proper Polish space. For any Polish space 2, we denote M (2) the Polish space of Borel probability measures on 2. We will denote F(2) the space of real valued Borel measurable functions on Z. Finally, we denote R == R U f00, +oo).
2.1 Notations and Preliminaries
The 0/1- 1ll-loss is both non-continuous and non-convex, and its direct minimization is difficult problem. The concepts of calibration and consistency aim at identifying the properties that a loss must satisfy in order to be good surrogate for the minimization of the 0/1 0/1-loss. In this section, we define these two concepts and explain the difference between them. First of all, we need to give a general definition of loss function.
Definition 2.1 (Loss function). A loss function is function L X x y x F(X) + RR such that ,(,r)) is measurable for all f E F(X)..
Note that this definition is not specific to the standard or adversarial case. In general, the loss at point (a, y) can either depend only on fxx). or on other points related to x (e.g. the set of points within distance E of z). We now recall the definition of the risk associated with a loss L and a distribution F..
Definition 2.2 (I-risk of a classifier). For a given loss function L,, and a Borel probability distribution P over X x y we define the risk of a classifier f associated with the loss L and distribution IP as
RI,((f) := -< [L y, f)l
We also define the optimal risk associated with the loss L as
Ri. == inf RI,((J)
fEF(X)
For instance, for any norm [1-1], (LL", |I-II) is Polish metrie space satisfying this property.

---

Essentially, the risk of a classifier is defined as the average loss over the distribution P. When the loss L is difficult to optimize practice (e.g when it non-convex or non-differentiable). it is often preferred to optimize a surrogate loss function instead. In the literature 2 surrogate losses has been studied as a consistency problem. be consistent if any minimizing sequence of classifiers for the risk associated with the surrogate loss also one for the risk associated with L. Formally, the notion of consistency as follows.
the notion of nutshell, surrogate loss is said to
Definition 2.3 (Consistency). Let L1 and Le be two loss functions. For a given MM x)), L2 is said to be consistent for P with respect to L1 for all sequences (fn)n E F((X)
Rta)((a) Rig. = RRn,,((n) - +Ri,
(1)
Furthermore, Le is said consistent with respect to a loss L1 the above holds for any distribution P.
Consistency is in general difficult problem to study because of its high dependency on the distribution at hand. Accordingly, several previous works 20
introduced a weaker notion to study pointwise version consistency. This simplified notion called calibration and corresponds to consistency when P is a combination of Dirac distributions. The main building block in the analysis of the calibration problem is the calibration function, defined as follows.
5 17
Definition 2.4 (Calibration function). Let L be loss function. The calibration function CL is
Cz f) == (z, 1, f) + (1 (),
for any v E [0, 11, x E X and f E F(t). We also define the optimal calibration finirrationfunncioon as (I, inf Cr. fEF(X)
Note that for any x E X and 7 E [0, 1], when P = n90 (2,+1) + (1 -1)6(=,-1)) we Cr, JJ Rf.,(f)) with The calibration function thus corresponds then to pointwise notion of the risk, evaluated at point æ. 1) corresponds in this case to the conditional probability of y = given r. We now define the calibration property of surrogate loss.
Definition 2.5 (Calibration). Let L1 and Lz be two loss functions. We say that L2 is calibrated with regards to L1 for every & <>0 0, 17 E [0, 1] and X, there exists 8 >> O such that for all E F(X),
Cz, C)- (x, S = (I, Ci, (x, S..
Furthermore, we say that L,2 uniformly calibrated with regards In for every > O, there exists 8 > O such that for all n E [0, 1}, E X and f E F(X) we have
Cr. (2, J) Ct (x. < 8 = (r, - Ci, (x, ()) SE.
Connection between calibration and consistency. It is always true that calibration is necessary condition for consistency. Yet there is no reason, in general, for the converse to be true. However, in the specific context usually studied in the literature (i.e., the standard classification with well-defined 0/1 1/l-lss)), the notions of consistency and calibration have been shown to be equivalent. 120 [7]. In the next section, we come back existing results regarding calibration and consistency this specific (standard) classification setting.
2.2 Existing Results in the Standard Classification Setting
Classification is standard task in machine learning that consists in finding classification function : X' + Y that maps an input x to a label y. In binary classification, h is often defined as the sign of a real valued function F(t). The loss usually used to characterize classification tasks corresponds to the accuracy of the classifier h. When h is defined as above, this loss is defined as follows.
Definition 2.6 (0/1 loss). Let E We define the 0/1 loss as follows
1o/1 y. f) = 1 y (x))
with a convention for the sign, egg. sign(0) = 1. We will denote Re(f) = (f), R$ R7 P C(x, f) == Clay (z. n, and C* 77 = Cin (x.
3

---

Note that this 0/1-loss is different from the one introduced by Bao et al. H Awasthi et al. BB: they used 1 yx s0 which usual 0/1 loss but unadapted consistency and calibrated study among them focus on the
(see Section 5 for details). Some of the most prominent works 20 6 17 concept of margin losses, as defined below.
Definition 2.7 (Margin loss). A loss Lo is said to be margin loss if there exists measurable function @ : - RR+ such that:
La (r, v. I) (()((t)
For simplicity, we will say that @ is a margin loss function and will denote Rg and C.. the risk associated with the margin loss 6. Notably, it has been demonstrated in several previous works (20 6 [ that, for margin loss Φ. we have always have (z, m7) infeeR nō((a) (1 ())(-a). This is in particular one of the main observation allowing to show the following strong result about the connection between consistency and calibration.
Theorem 2.1 (Zhang (20), Bartlett al. [6. Steinwart (7]. Let RR:R be a continuous
margin loss. Then the three following assertions are equivalent: (i) & is calibrated with regards to 10/1, (ii) & is uniformly calibrated lo/1, (iii) & is consistent with regards to lo/1-
Moreover. if é is convex and differentiable at 0, then @ is calibrated if and only o'(0) < O.
The Hinge loss @(t) max(1 t, 0) and the logistic loss o(t) log(1 + t are classical examples of convex consistent losses. Convexity is desirable property for faster optimization of the loss, but there exist other non-convex losses that are calibrated as the ramp loss (Ø(()
(max(1 - f, 0) max(-1 I, 0))) or the sigmoid loss (é(1) = (1 + e²)-1). These losses are plotted on the left in Figure ! In the next section, we present the adversarial classification setting for which Theorem 2.1 may not hold anymore.
The equivalence between calibration and consistency is a consequence from the fact that, over the large space of measurable functions, minimizing the loss pointwisely in the input by desintegrating with regards to x equivalent to minimize the whole risk over measurable functions. This result is very powerful and simplify the study of calibration in the standard setting.
Remark 1.
2.3 Calibration and Consistency in the Adversarial Setting.
We now consider the adversarial classification setting where an adversary tries manipulate the inputs at test time. Given E >> O, they can move each point x ~ I to another point x' which is at distance at most from + The goal of this adversary to maximize the 0/1 risk the shifted points from P. Formally, the loss associated to adversarial classification is defined as follows.
Definition 2.8 (Adversarial 0/1 loss). Let 2 We define the adversarial 0/1 1 loss of level as:
1o/1,c f.
sup [f
x'EB((#)
We will denote Re,((f) == Rinn, P(f), R = Riy,... Ce(2.n.f) = Clori (2, f) and Cz = Co (I, 1) for every P. x, and 1).
Specificity of the adversarial case The adversarial risk minimization problem is much more challenging than standard counterpart because an inner supremum is added to the optimization objective. With this inner supremum, it is no longer possible to reduce the distributional problem to pointwise minimization as it is usually done in the standard classification framework. notions of consistency and calibration are significantly different in the adversarial setting. This means that the results obtained the standard classification may no longer be valid in the adversarial setting (e.g., the calibration need not be sufficient for consistency), which makes the study of consistency much more complicated. As a first step towards analyzing the adversarial classification problem, we now adapt the notion of margin loss to the adversarial setting.
fact, the
Definition 2.9 (Adversarial margin loss). Let ó R + R,, be a margin loss and e 2 0. We define the adversarial loss of level associated with ò as:
sup ((v)(x')) (e( x'E
Note that after shifting to x', the point need not be in the support of IF anymore.

---

We say that o is adversarially calibrated (resp. uniformly calibrated, resp. consistent) at level e if oz calibrated (resp. uniformly calibrated, resp. consistent) wrt 10/1,c.
Note that first important sanity check to make is verify that 6g and lo/1.c are indeed measurable and well defined. The arguments are not trivial since uses advanced arguments from measure theory, but it is necessary establish measurability before going further on. Proposition 2.1 states the measurability of de and lo/1,s- We prove this result in Appendix B
Proposition 2.1. Let Φ R x y - R be measurable function and & 2 0. For every f E F(X), (a. > de (z. y. f) and (x. v) + 1o/1.e (z, y. f) are universally measurable.
Now that, proved that the adversarial setting is properly defined, the calibration functions for & and de are actually equal. This property might seem at first sight the adversarial risk is most of the time strictly larger than its standard counterpart. However, the calibration functions are only pointwise dependent, hence having the same prediction for any element of the ball (x) suffices to reach the optimal calibration Cz, 11).
make first observation:
Proposition 2.2. Let > O. Let @ be a continuous classification margin loss. For all x E X and 77 E [0, 1]. we have
C.. (I, ()) = inf nπb(a) + (1 (1)((-a)) C2(2,))
aER
The last equality also holds for the adversarial 0/1 loss.
The proof of this result is available in Appendix
3 Solving Adversarial Calibration
In this section, we study the calibration of adversarial margin losses with regard to the adversarial 0/1 loss. We first provide necessary and sufficient conditions under which margin losses are adversarially calibrated. We then show that wide range of surrogate losses that are calibrated in the standard setting are not calibrated in the adversarial setting. Finally we propose a class of losses that are calibrated in the adversarial setting, namely the shifted odd losses.
3.1 Necessary and Sufficient Conditions for Calibration
One of our main contributions is to find necessary and sufficient conditions for calibration in the adversarial setting. In a brief, we identify that for studying calibration is central to understand the case where there might be indecision for classifiers (i.e. n 1/2). Indeed, in this case, either labelling positively or negatively the input x would lead the same loss for x. Next result provides a necessary condition for calibration.
Theorem 3.1 (Necessary condition for Calibration). Let å be continuous margin loss and E > 0. If is adversarially calibrated at level e, then & is calibrated in the standard classification setting and 0 & argmin ((a) + a.).
We proof this theorem in Appendix D While the condition of calibration in the standard classification setting seems natural, we need to understand why 0 & argmin ((())) + (-)).. The intuition behind this result is that a sequence of functions simply converging towards 0 in the ball of radius around some r can take positive and negative values thus leading to suboptimal 0/1 adversarial risk. It turns out that, given an additional mild assumption, this condition is actually sufficient to ensure calibration.
Theorem 3.2 (Sufficient condition for Calibration). Let be a continuous margin loss and E >> 0. If é is decreasing and strictly decreasing in a neighbourhood of and calibrated in the standard setting and 0 & argmin }0(() + do( (0). then o adversarially uniformly calibrated at level e.
The proof of this thcorem is available in Appendix E
Remark 2 (Decreasing hypothesis). For the reciprocal, the additional assumption that & is decreasing and strictly decreasing a neighborhood of 0 is not restrictive for usual losses. In Theorem 2.1 this assumption is stated as necessary and sufficient condition for convex losses to be calibrated.
5

---

Hege Log stc
Logest: Sigmess Pamm
Simoodd
2.0
Bаmp 0/1 cus
1.5
1 1
1.5
1.0
1.0
Figure 1: On the left, illustration of common standardly calibrated losses. On the right plot of their symmetrized version. Here we notice that argmin, ((a) ((-a) for all these losses, Thus none of them are adversarially calibrated.
3.2 Negative results
Thanks to Theorem we can present two notable corollaries invalidating the use two important classes of surrogate losses in the standard setting. The first class of losses are convex margin losses. These losses are maybe the most widely used in modern day machine learning as they comprise the logistic loss the margin loss that are the building block of most classification algorithms. We illustrate such losses in Figure !1
Corollary 3.1. Let O. Then no convex margin loss can be adversarially calibrated at level E.
A convex loss satisfies (()) + { 2 <(0), hence 0 E argmin,eR Φ(a) + <(-a). From Theorem 3.1 we deduce the result. Then, Φ is not adversarially calibrated at level E. This result seems nounter-intuitive and highlights the difficulty of optimizing and understanding the adversarial risk. Since convex losses are not adversarially calibrated, one may hope to rely on famous non-convex losses such as sigmoid and ramp losses. But, unfortunately, such losses are not calibrated either as illusrtated in Figure
Corollary 3.2. Let >> Let X E R and th be lower-bounded odd function such that for all E TR, & > X. We define vi as ((a)= = X + v(a)) Then & is not adversarially calibrated at level e.
Indeed, (0(a) + (()))) X, that argmin OER }0(a) + (=)aaa))= RR. Thanks to Theorem 3.1 ó is not adversarially calibrated at level e.
3.3 Positive results
Theorem also gives sufficient conditions for to be adversarially calibrated. Leveraging this result, we devise a class of margin losses that are indeed calibrated in the adversarial settings. We call this class shifted odd losses, and we define it follows.
Definition 3.1 (Shifted odd losses). We say that & is a shifted odd margin loss if there exists À 2 0, O. and continuous lower bounded decreasing odd function va that strictly decreasing neighborhood of such that for all E IR, vb(a) Z -X and ((a)) = X + v0(a T).
The key difference between a standard odd margin loss and a shifted odd margin loss the variations of the function a + 3 (aaa)) + 35((aa). The primary difference is that, in the standard case the optima of this function are located at while they are located -oo and +0o in the adversarial setting. Let give some examples of margin shifted odd losses below.
Example (Shifted odd losses). For every e > O and every > 0, the shifted logistic loss, defined as follows, is adversarially calibrated at level e: o: + (1 exp (a 7)) This loss is plotted on left in Figure We also plotted on right Figure 2 a + =0(a) ( to justify that
& argmin ((()) + [)((-)). Also note that the shifted ramp loss also satisfies the same properties.
consequence of Theorem 3.2 that shifted odd losses are adversarially calibrated, as demonstrated in Proposition 3.1 stated below.

---

Sigmerd Loss Shitted Sigmold Loss
---
Sigmoid Loss
Shitted Sigmes Lo55
0.
0.
0.4
0.4
-300
-55
-50
-25
0.0
-50
-25
-50
-25
0.0
25
5.0
75
18.0
Figure 2: Illustration of a calibrated loss in the adversarial setting. The sigmoid loss satisfy the hypothesis for v. Its shifted version then calibrated for adversarial classification.
Proposition 3.1. Let be a shifted odd margin loss. For every > is adversarially calibrated at levels.
We proof this proposition in Appendix
4 Towards Adversarial Consistency
We focus our study now on the problem of adversarial consistency. In a first part, taking inspiration from Long and Servedio [1]. Awasthi al. (0), study the e-realisable case, i.e. the case where the adversarial risk at level & equals zero. In second part, we analyze the behavior a candidate class of losses, namely the 0/1-like margin losses.
4.1 The Realizable Case
The realizable case is important since there are no possible adversaries for the Bayes optimal classifier. Formally, this means that the adversarial risk equals O, stated in the following definition. Definition 4.1 (e-realisability). Let IP be a Borel probability distribution on X' y and e 2 0. We say that P is s-realisable if R O.
In the case of realizable probability distribution, calibrated (and consequently consistent) margin losses in the standard classification setting also calibrated and consistent in the adversarial case. Proposition 4.1. Let E > O. Let be an e-realisable distribution and be a calibrated margin loss in the standard setting. Then & is adversarially consistent level
We give a proof of this result in Appendix G The intuition behind this result that if a probability distribution is s s-realisable, the marginal distributions sufficiently separated, that there possible adversarial attacks, each point in the e-neighbourhood of the support of the distribution can be classified independently of each other.
4.2 Towards the General Case
In this section, we seek to pave the way towards proving the consistency of shifted odd losses. We will observe that their behavior is actually very similar to that of the 0/1 loss, which makes them good candidates to be consistent losses. this end, we first add an extra hypothesis to odd shifted losses in order to simplify our technical analysis.
Definition 4.2 (0/1-like margin losses). á a 0/1-like margin loss if there exists À 2 0, T 2 O, and continuous lower bounded strictly decreasing odd function & in a neighbourhood of 0 such that for all a E R. vaa) 2 -X and ő(a) = + v6 T) and
lim (() 1 and lim +(1) to+
Note here that the losses here are not necessarily shifted because 7 might equal 0, making this condition weaker. Consequently, we cannot hope that such losses consistent neither calibrated,

---

but they might help in finding the path towards consistency. Note also that if 6 is an odd or shifted odd loss, one can always find rescaling such that @ becomes a 0/ 1/1-like margin loss. Note also that such rescaling does neither change the notion of consistency and calibration for e nor for its rescaled version.
Based on min-max arguments, we provide below some results better characterizing 0/ 0/l-like margin loss functions in the adversarial setting. Let us first recall the notions of midpoint property and adversarial distributions set that will be useful from now on as well as an important existing result from Pydi and Jog [[6].
Definition 4.3. Let (Z, d) be a proper Polish metric space. We say that X' satisfy the midpoint property for all x1, X there exist E X such that d(x,x1) = d(x,x2) 2(21,22)
2
We recall also the set (IP) of adversarial distributions introduced in I3
Definition 4.4. Let P be Borel probability distribution and & >> O. We define the set of adversarial distributions (P) as:
(T)) = E EI 13 ((X x )))),
7 ((x, v), (z', (d',s/))-aa -ass 11 = IP, 112 = Q}
where I1; denotes the projection on the i-th component.
Note that in this definition, (z, y) denotes an input-label pair drawn from the original distribution and (x', v/) denotes the input-label pair from the perturbed distribution Q (after attack)
Theorem 4.1 (Pydi and Jog (16]). Let X be Polish space satisfying the midpoint property. Then
strong duality holds:
Rrp inf sup RQ(f)= sup QEA.(P) (EF(x)
inf Ro(f)
(EF(X) (EA.(P)
Moreover the supremum of the right-hand term is attained.
Note that in the original version of the theorem, Pydi and Jog [66 did not prove that the supremum is attained. We add proof of this in Appendix H
Connections between 0/1-like margin loss and 0/1 loss: min-max viewpoint. Thanks the the above concepts, we can now present some results identifying the similarity and the differences between the 0/1 loss and 0/1-like margin losses. We first show that for a given fixed probability distribution IP, the adversarial optimal risk associated with a 0/1-like margin loss and the 0/1 loss are equal. The proof of this result available in Appendix ![
Theorem 4.2. Let X be a Polish space satisfying the midpoint property. Let E 2 0, IP be a Borel probability distribution over X x Y and o be 0/ 1-lke margin loss. Then, we have:
R. F = Rr
In particular, we note that this property holds true for the standard risk. From this result, we can derive two interesting corollaries about 0/ llke margin losses. First, strong duality holds for the risk associated with Φ.
Corollary 4.1 (Strong duality for Φ). Let assume that X is a Polish space satisfying the midpoint property. Let e 2 0, P be a Borel probability distribution over X x y, and & be a 0/1-like margin loss. Then, we have;
inf JEF(X) QEA.(B)
sup Ro.elf) = sup inf Rg,e(f) (EA((P)FF(()
Moreover the supremum is atlained.
Note that there is reason that the infimum is attained. A second interesting corollary is the equality of the set of optimal attacks, i.e distributions of Ag (IP) that maximize the dual problem: an optimal attack for the 0/1 loss is also an optimal attack for 0/1-like margin, and vice versa.
Corollary 4.2 (Optimal attacks). Let assume that X' be a Polish space satisfying the midpoint property. Let e 2 O and To be Borel probability distribution over X' x Y. Then, an optimal attack Q+* of level e exists for both the 0/1 loss and 6. Moreover, for Q (PP). Q is an optimal attack for the loss á if and only if it is an optimal attack for the 0/1 loss.
The proof of these two corollaries is available in Appendix

---

A step towards consistency. From the previous results, we are able to prove a first result toward the demonstration of consistency. This result is much weaker than consistency result, but guarantees that if sequence minimizes the adversarial risk, then it minimizes the risk for optimal attacks. i.e. in a game where the attacker plays before the classifier. The proof of this result is in Appendix K
Proposition 4.2, Let us assume that X' be a Polish space satisfying the midpoint property. Let 2 0 and P be a Borel probability distribution over X x y. Let Q* be an optimal attack of level &. Let (Jn) be sequence of F(2) such that R. 17 (fn) + R. Then Re (fn) R
We hope this result and its proof may lead to a full proof of consistency. This result is significantly weaker than consistency stated in the following remark. In the proof of the previous results, we did not use the assumptions that losses are shifted. In our opinion, it is the key element that we miss and that need to to conclude on the consistency of this family of losses. The shift in the loss would force the classifier to goes to to0 on a E neighborhood support of the distribution of IP and then the risk would equal the adversarial 0/1-loss risk. However, we did not succeed in showing the appropriate result: we believe this question is complicated and is left as further work.
5 Related Work and Discussions
We now explain the differences between our approach and the one proposed by Bao et al. 4. Awasthi al. MB. The two main differences are the choice of the 0/1 loss and the studied notion of consistency and calibration.
Alternative 0/1 loss An alternative 0/1 loss would the following: I (=((x)) v) = 1y(e)) This loss penalizes indecision: i.e. predicting would lead a pointwise risk of for y = y --1 while the 0/1 loss 40/1 returns 1 for y 1 and 0 for y = -1. This definition was used by Bao et al. Awasthi et al. [ 3 to prove their calibration and consistency results. While Bartlett et al. 3 was not explicit on the choice for the 0/1 loss, Steinwart [07 explicitly mentions that the 0/1 loss not margin loss. The use of this loss is not suited for studying consistency and leads to inaccurate results as shown in the following counterexample. On X' = R, let P defined as
= 2 (6 + d==0,y=-1) and Φ IR- + R be a margin based loss. The ø-risk minimization problem writes inf,, } (Ø(a) + o(-a)). For any convex functional & the optimum is attained for 0. fn x 0 is minimizing sequence for the ø-risk. However Rtg (fa) = 1 for all n and
R 2- Then we deduce that no convex margin based loss is consistent wrt Lg. Consequently, the
0/1 loss to be used in adversarial consistency needs to be (0,1,=(11, y, supp''B, y otherwise the obtained results might be innacurate.
H-consistency and H-calibration Bao et al. 4. Awasthi et al. II 3 proposed to study H- calibration and H-consistency in the adversarial setting, i.e. calibration and consistency when minimizing sequences are in H. However, even in the standard classification setting, the link between both notions in this extended setting is not clear all since a pointwise minimization of the risk cannot be done. To our knowledge, there is only one research paper [I]] that focuses on this notion in standard setting. They do it in the restricted case of realisability, i.e. when the standard optimal risk associated with the 0/1 loss equals O. We believe that studying H-consistency and H-calibration in the adversarial setting a bit anticipated. For these reasons, we focus only on calibration and con- sistency on the space of measurable functions F(X'). However, note that many of our results can be adapted H-calibration: we propose, in Appendix conditions on classes H. so that Theorems and 3 still holds.
About the Adversarial Bayes Risk and Game Theory. A recent trend of work has focused on
analyzing the adversarial risk from multiple point of views. Bhagoji al. [X] as well as Pydi and Jog
[15 [6 showed that the adversarial optimal Bayes classifier can be written as optimal transport for a
well chosen cost. Another line of work [4
[K] 16 have focused on a game theoretic approach for
analyzing the adversarial risk having interest in the nature of equilibria between the classifier and the attacker. Recently, some researchers 2 TC proved encouraging results on the existence of an
optimal Bayes classifier in the adversarial setting under mild assumptions.

---

Conclusion and Perspectives
In this paper, we set some solid theoretical foundations for the study of adversarial consistency. We highlighted the importance of the definition of the 0/1 loss, well as the nuance between calibration and consistency that is specific to the adversarial setting. Furthermore, we solved the adversarial calibration problem, by giving necessary and sufficient condition for decreasing, continuous margin losses to be adversarially calibrated. Since this a necessary condition for consistency, an important consequence of this result is that no convex margin loss can be consistent. This rules most of the commonly used surrogates, and spurs the need for new families consistent, yet differentiable families of losses. We provide first insights into which losses may be consistent, by showing that translations odd loss functions are calibrated.
Nonetheless, we believe that our work could have a concrete practical impact in the near future, especially when considering adversarial training [122] When implementing this defense, we are essentially optimizing surrogate adversarial loss. As our results show, these losses are not consistent when chosen with standard consistency theory, which can lead to large optimality gap when using these techniques. We believe that using adversarially calibrated losses as the shifted odd losses could circumvent this problem, which would give important practical significance to our work.
Acknowledgement
Rafael is partly supported by an Ecocloud postdoctoral fellowship.
References
[1] Pranjal Awasthi, Natalic Frank, Anqi Mao, Mehryar Mohri, and Yutao Zhong. Calibration and consistency of adversarial surrogate losses. Advances in Neural Information Processing Systems, 34, 2021.
[2] Pranjal Awasthi, Natalie S Frank, and Mehryar Mohri. On the existence of the adversarial bayes classifier (extended version). arXiv preprint arXiv:21 2021.
[3] Pranjal Awasthi, Anqi Mao, Mehryar Mohri, and Yutao Zhong. finer calibration analysis for adversarial robustness. arXiv preprint arXiv:2/05.0/5500 2021.
[4] Han Bao, Clay Scott, and Masashi Sugiyama. Calibrated surrogate losses for adversarially robust classification. In Jacob Abernethy and Shivani Agarwal, editors, Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pages 408-451. PMLR, 09-12 Jul 2020. URL http::/ppocceddinnge mlr press/v125/ / bao20a. html
[5] Peter L Bartlett and Shahar Mendelson. Rademacher and gaussian complexitie: Risk bounds and structural results. Journal of Machine Learning Research, 3:463-482, 2002.
[6] Peter L Bartlett, Michael I Jordan, and Jon D McAuliffe. Convexity, classification, and risk bounds. Journal of the American Statistical Association, 101(473):138-156, 2006.
[7] Dimitir P Bertsekas and Steven Shreve. Stochastic optimal control: the discrete-time case. 2004.
[8] Arjun Nitin Bhagoji. Daniel Cullina, and Prateek Mittal. Lower bounds adversarial robustness from optimal transport. Advances in Neural Information Processing Systems, 32, 2019.
[9] Battista Biggio, Igino Corona, Davide Maiorea, Blaine Nelson, Nedim Šmdić Pavel Laskov, Giorgio Giacinto, and Fabio Roli. Evasion attacks against machine learning at test time. In Joint European conference on machine learning and knowledge discovery databases, pages 387-402. Springer, 2013.
[10] Leon Bungert, Nicolás Gareía Trillos, and Ryan Murray. The geometry adversarial training in binary classification. arXiv preprint arXiv:2111.1361,, 2021.
10

---

[11] Phil Long and Rocco Servedio. Consisteney versus realizable h-consistency for multiclass classification. In International Conference on Machine Learning, pages 801-809. PMLR. 2013.
[12] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference Learning Representations, 2018.
[13] Laurent Meunier, Meyer Scetbon, Rafael Pinot, Jamal Atif, and Yann Chevaleyre. Mixed nash equilibria in the adversarial examples game. In International Conference Machine Learning, pages 7677-7687. PMLR, 2021.
[14] Rafael Pinot, Raphael Ettedgui, Geovani Rizk, Yann Chevaleyre, and Jamal Atif. Randomization matters. how defend against strong adversarial attacks. International Conference on Machine Learning, 2020.
2020.
[15] Muni Sreenivas Pydi and Varun Jog, Adversarial risk via optimal transport and optimal couplings. In International Conference on Machine Learning. 2020.
[16] Muni Sreenivas Pydi and Varun Jog. The many faces of adversarial risk. Advances in Neural Information Processing Systems, 34, 2021.
[17] Ingo Steinwart. How compare different loss functions and their risks. Constructive Approxi- mation, 26(2):225-287, 2007.
[18] Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Good- fellow, and Rob Fergus. Intriguing properties of neural networks. In International Conference on Learning Representations, 2014.
[19] Deng Yao, Zheng Xi, Zhang Tianyi, Chen Chen, Lou Guannan, and Kim Miryung. An analysis of adversarial attacks and defenses on autonomous driving models. In 18th Annual IEEE International Conference Pervasive Computing and Communications. IEEE, 2020.
[20] Tong Zhang. Statistical behavior and consistency of classification methods based convex risk minimization. The Annals of Statistics, 32(1):56-8)) 2004.

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [No] The work brings theoretic insights on adversarial robustness. We believe there no potential social harm in our work.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set assumptions of all theoretical results? [Yes] Every result is stated with clear hypothesis.
(b) Did you include complete proofs of all theoretical results? [Yes] All proofs are in Appendix.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you eite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you't 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
12


Reviews:
[{"review_id": "xxnhvl0_yU-", "reviewer": "Reviewer_cdXZ", "summary": "The paper shows that the usual continous loss functions like hinge loss and logistic loss that are used to approximate the $0/1$-loss are not consistent nor calibrated for the adversarial $0/1$-loss.\n\nIt shows that a certain assymetry is necessary in order to have calibration and proposes shifted odd functions as candidates that are shown to fullfill them.\n\nFinally, difficulties with and potential pathways towards consistent losses for the adversarial setting are discussed and related with some interesting theoretical results.\n\nThe paper does not contain any experiments.", "questions": "The definition/interpretation of $\\eta$ should be clarified. In Definition 2.4, it is the conditional probability of the ground truth being $1$ for a given input $x$. While it is stated here that this is the meaning \"in this case\", it is not defined otherwise in the rest of the paper.\nIt seems like $\\eta$ is a function of $x$? If so, it would make things clearer if it was written as $\\eta(x)$ or $\\eta_x$. If it isn't, pleased clarify.\nSince the ground truth may not be constant in the $\\epsilon$-ball around a given $x$, it appears to be a problem that the statements and proofs for the adversarial settings seem to use one constant $\\eta$ over the ball. For example, in Appendix E in the equation of line 512, $\\eta$ appears outside of the supremum over $x'$.\n\n\nIn Definition 4.4, $x,x'$ and $y,y'$ should be defined more explictly. It would help to include an explanation of the definition, for which referring to \"[12] Meunier et al.: Mixed Nash Equilibria in the Adversarial Examples Game\" didn't help me either.\n\nIn l. 139, I think there is a sign error in the ramp loss, right?\n\nIn l. 354, is \"anticipated\" the correct word?\n\nA question about alternative losses: Would using logistic loss (KL-divergence) for evaluating adversarially robust models be an interesting metric that would lead to fewer problems since one does not need a surrogate to train it?\n\nA comment and potentially a discussion in the revision on the relation to the very recent \"Frank et al.: The Consistency of Adversarial Training for Binary Classification (https://arxiv.org/abs/2206.09099) \" which at first glance states some contradicting results would be very welcome.", "limitations": "The limitations of currently achievable results on consistency are described in detail.\n\nThe authors \"believe there is no potential social harm\" which is not a statement that is not obvious for any machine learning research, due to potential dual use and other general risks.\nHowever, there is nothing specific that needs to be mentioned for this paper, and I agree with the authors as in my opinion a work like this has non-negative expected social impacts.", "rating": 9, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is generally well written and presented.\n\nShowing that the standard losses for adversarial robustness training do not satisfy certain basic theoretical properties is an interesting and potentially important insight. The paper rigorously and comprehensively proofs these results.\n\nI checked the proofs up until Proposition 3.1 and they appear to be correct, with the only issue for me being the definition of $\\eta$, see below.\n\nFigure 1 is very helpful for understanding Proposition 3.1; more similar illustrations for the other results would be very beneficial for the paper, if possible.\n\nI think that the paper is a very interesting contribution to the field of adversarial robustness. \nThe paper is generally well written but some details are missing for me (also due to me not being very familiar with the literature on consistency); I hope for clarifications on the questions below, particularly on $\\eta$.\n\nWhile the results are interesting and partly surprising to me from the perspective of adversarial robustness, I cannot say much about the novelty in the context of consistency and calibration literature which this work builds upon.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "sEGtYy26vbo", "reviewer": "Reviewer_MTmv", "summary": "This paper studies the problem of consistency and calibration in the setting of classification with an adversary that perturbs the inputs during inference. The authors highlight the critical difference in the consistency and calibration between the standard setting and the adversarial setting. They show the widely used convex surrogate losses for 0-1 loss are no longer calibrated or consistent. They then provide detailed analyses to build the necessary and sufficient conditions for continuous loss functions to be calibrated in an adversarial setting. They further advance toward consistency in the adversarial setting by showing a weak result of consistency.", "questions": "Is it possible to analyze the level of “divergence” of widely used loss functions such as the logistic loss from the 0-1 loss? And perhaps provide some empirical results to validate it. Such analyses would be extremely helpful to motivate people to rethink the loss function for adversarial training and potentially provide new insights.", "limitations": "The limitations of this paper have been adequately discussed at the end of Section 4.2. ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The originality of the work is sufficient as the studies of calibration and consistency in adversarial settings for general functions are missing in the literature to the best of my knowledge. \n\nThe quality of the work is high as the authors provide detailed and solid analyses of calibration and consistency in the adversarial setting, including the difficulty and (potential) solutions to specific and general results.\n\nThe paper is well-organized and clarified, with sufficient background and preliminaries provided. I am not an expert in calibration and consistency but I was able to follow the analyses step by step.\n\nFinally, I believe the result is significant as the calibration and consistency in adversarial settings are important problems that are able to guide the training of adversarially robust classifiers. This paper is able to move one step toward this goal.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "JfyHlsAAkBc", "reviewer": "Reviewer_a53P", "summary": "This paper studies the consistency and calibration properties of adversarial losses. Specifically, it defines an adversarial loss as the highest loss in a $\\epsilon$-ball around data examples and find the sufficient and necessary conditions when an adversarial loss is adversarially calibrated. Furthermore, this paper also studies the consistency of adversarial loss. However, the obtained result in Prop 4.2 regarding the consistency seems weaker than expected.", "questions": "1) What are $x,x',y$ in the definition of $A_\\epsilon(\\mathbb{P})$?\n2) In Cor 4.2 and Prop 4.2, does $\\phi$ needs to be a 0/1 like loss?\n3) Why does not $\\epsilon$ exist in the sufficient conditions in Theorem 3.2? Does it mean that the conclusion holds for every $\\epsilon$?", "limitations": "This is a theoretically comprehensive study. However, it would be much better if the authors give hints of how the gained results can be exploited to benefit adversarial attack and defense.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "* Strengths:\n- This is a comprehensive study about the calibration and consistency property of loss functions in the context of adversary.\n- The paper is generally well-written and easy to follow.\n\n* Weakness:\n- The gained results seem to have less impact on practical problems of adversarial attack and defense.\n- There is no hint of how to utilize the gained results to improve adversarial robustness.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept