Calibration and Consistency of Adversarial Surrogate Losses
Authors: Pranjal Awasthi
Natalie Frank
Anqi Mao
Mehryar Mohri
Yutao Zhong
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: Adversarial Robustness
Learning Theory
Consistency
Calibration
Statistical learning
Classification.

Abstract: Adversarial robustness is an increasingly critical property of classifiers in applications. The design of robust algorithms relies on surrogate losses since the optimization of the adversarial loss with most hypothesis sets is NP-hard. But, which surrogate losses should be used and when do they benefit from theoretical guarantees? We present an extensive study of this question, including a detailed analysis of the $\mathcal{H}$-calibration and $\mathcal{H}$-consistency of adversarial surrogate losses. We show that convex loss functions, or the supremum-based convex losses often used in applications, are not $\mathcal{H}$-calibrated for common hypothesis sets used in machine learning. We then give a characterization of $\mathcal{H}$-calibration and prove that some surrogate losses are indeed $\mathcal{H}$-calibrated for the adversarial zero-one loss, with common hypothesis sets. In particular, we fix some calibration results presented in prior work for a family of linear models and significantly generalize the results to the nonlinear hypothesis sets. Next, we show that $\mathcal{H}$-calibration is not sufficient to guarantee consistency and prove that, in the absence of any distributional assumption, no continuous surrogate loss is consistent in the adversarial setting. This, in particular, proves that a claim made in prior work is inaccurate. Next, we identify natural conditions under which some surrogate losses that we describe in detail are $\mathcal{H}$-consistent. We also report a series of empirical results which show that many $\mathcal{H}$-calibrated surrogate losses are indeed not $\mathcal{H}$-consistent, and validate our theoretical assumptions. Our adversarial $\mathcal{H}$-consistency results are novel, even for the case where $\mathcal{H}$ is the family of all measurable functions.

Calibration and Consistency of Adversarial Surrogate Losses
Pranjal Awasthi
Natalie S. Frank Courant Institute New York, NY 10012 nf 1 1211660@yu.eed
Anqi Mao Courant Institute New York, NY 10012
Google Research
New York, NY 10011
pranjalasasthi@@ooglee.co
aqmao@cima nyu edu
Mehryar Mohri
Yutao Zhong
Google Research Courant Institute New York, NY 10011
Courant Institute
New York, NY 10012 yutaoêcims nyu. edu
mohri@google.co com
Abstract
Adversarial robustness an increasingly critical property of classifiers in ap- plications. The design of robust algorithms relies surrogate losses since the optimization of the adversarial loss with most hypothesis sets is NP-hard. But, which surrogate losses should be used and when do they benefit from theoretical guarantees? We present an extensive study of this question, including a detailed analysis of the K-calibration and H-consistency of adversarial surrogate losses. We show that convex loss functions, or the supremum-base used in applications. are not H[-calibrated for common hypothesis sets used machine learning. We then give characterization of FC-calibration and prove that some surrogate losses are indeed H-calibraaedd for the adversarial zero-one loss, with common hypothesis sets. In particular, we fix some calibration results presented in prior work for family of linear models and significantly generalize the results to the nonlinear hypothesis sets. Next, we show that H-calibration is not sufficient to guarantee consistency and prove that, in the absence of any distri- butional assumption, setting. This, in particular, proves that a claim made in prior work is inaccurate. Next, we identify natural conditions under which some surrogate losses that we describe in detail are H-consistent.. We also report a series empirical results which show that many H-caalbraated surrogate losses indeed not HCCconsistent, and validate our theoretical assumptions. Our adversarial H-consistency results are novel, even for the case where H. is the family of all measurable functions.
convex losses often
continuous surrogate loss is consistent in the adversarial
1 Introduction
Complex multi-layer neural networks trained on large datasets have achieved a remarkable perfor- mance in several applications recent years, particular speech and visual recognition tasks (Sutskever et al., 2014; Krizhevsky et al., 2012). However, these rich models are susceptible to imperceptible perturbations (Szegedy et al., 2013). A complex neural network may, for example, misclassify a traffic sign, as result of minor variation, which may be the presence of small advertisement sticker on the sign. Such misclassifications can have dramatic consequences in practice, for example with self-driving cars. These concerns have motivated the study of adversarial robustness, that is the design of classifiers that are robust to small 4, norm input perturbations (Goodfellow et al., 2014; Madry et al., 2017: Tsipras et al., 2018; 8; Carlini and Wagner, 2017). The standard 0/1 loss is
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

then replaced with a more stringent adversarial loss, which requires predictor to correctly classify an input point x and also to maintain the same classification for all points at a small l, distance of But, can we devise efficient learning algorithms with theoretical guarantees for the adversarial loss?
Designing such robust algorithms requires resorting to appropriate surrogate losses since optimizing the adversarial loss is NP-hard for most hypothesis sets. A key property for surrogate adversarial losses is their consistency, that is, that exact or near optimal minimizers of the surrogate loss be also exact or near optimal minimizers of the original adversarial loss. The notion of consistency has been extensively studied in the case of the standard 0/1 loss or the multi-class setting (Zhang, 2004; Bartlett et al., 2006; Tewari and Bartlett, 2007; Steinwart, 2007). However, those results or proof techniques cannot be used to establish or characterize consistency in adversarial settings. This is because the adversarial loss of a predictor f at point x is inherently not just function of f(x) but also of its values around a neighhorhood of x. As we shall see, the study of consistency is significantly more complex in the adversarial setting, with subtleties that have in fact led to some inaccurate claims made in prior work that we discuss later.
Consistency requires property of the surrogate and the original losses to hold true for the family of all measurable functions. As argued by Long and Servedio (2013), the notion of H-consistency, which requires a similar property for the surrogate and original losses, but with the near or optimal minimizers considered on the restricted hypothesis set H. is more relevant and desirable property for learning. Long and Servedio (2013) gave examples of surrogate losses that are not H-coosistent when H is the class of all measurable functions but that satisfy a realizable JC-consistency condition when H. is the class of linear functions. More recently, Zhang and Agarwal (2020) studied the notion of improper realizable K-consistency of linear classes where the surrogate é can be optimized over a larger class, such as that of piecewise linear functions. Note that these studies only deal with the standard 0/1 classification loss. This motivates our main objective: an extensive study of the H-consistenccy of adversarial surrogate losses, which is critical to the design of robust algorithms with guarantees in this setting.
A more convenient notion in the study of H-consistencyy is that of F--aaiibaation which is a related notion that involves conditioning on the input point. JC-calibration often is a sufficient condition for K-consssstency in the standard classification settings (Steinwart, 2007). However, the adversarial loss presents new challenges and requires carefully distinguishing among these notions to avoid drawing false conclusions. As an example, the recent COLT 2020 paper of Bao et al. (2020) presents a study of K-calibration for the adversarial loss in the special case where H is the class of linear functions. However, several comments are due regarding that work. See a detailed discussion in Appendix B.
Our Contributions. We present more systematic study of the H-calibration and H-consistency including for the case where H = Hall of adversarial surrogate losses. In Section 4, we give a detailed analysis of the H--calibration properties of several natural surrogate losses. We present a series of new negative results showing that, under some general assumptions, convex loss functions and supremum- based convex losses, that are loss functions defined as the supremum over a ball of convex function. which are those commonly used in applications, are not K-calibrated for common hypothesis sets used in machine learning. Next, we give a characterization of calibration and prove that a family of proposed surrogates are H-calibrated, with common hypothesis sets. These fix previous calibration results presented for the family of linear models in (Bao et al., 2020) and significantly generalize the results to the nonlinear hypothesis sets. In Section 5, we study the K-consistency of surrogate loss functions. We prove that, in the absence of distributional assumptions, many surrogate losses shown to be H-calibrated in Section 4 are in fact not K-consisteni. This, in particular, proves that claim presented in COLT 2020 publication is inaccurate. Next, in contrast, we show that when the minimum of the surrogate loss is achieved within Hi, under some general conditions, the p-margin ramp loss (sce, for example, (Mohri et al., 2018)) is H-connsistett for H being the linear hypothesis set, or any nec-decegg and continuous based hypothesis set, including the ReL.Ubaaed hypothesis set. We then give similar K-consistency guarantees for supremum- based surrogate losses based on non-increasing auxiliary function, including the calibrated supremum-based p-margin ramp loss when H is any symmetric hypothesis set, e.g., the multi-layer neural networks. In Section 6, we further report series of empirical results on simulated data, which show that many K-calibrated surrogate losses are indeed not H-consistent, and justify our conditions for consistency. Overall, our results imply that the loss functions commonly used in practice for optimizing the adversarial loss are not FC-onsisttntt and that minimizing such losses may not lead to more favorable adversarial loss. This could be in fact the reason why the empirical results reported in the literature have not been
2

---

favorable. Instead, we suggest alternative surrogate losses that we prove are H-consistent and that can be useful the design of effective algorithms.
We give a detailed discussion of related work in Appendix A. We start with basic concepts of calibration and consistency (Section 2) and an introduction of robust classification (Section 3).
2 Preliminaries
We will denote vectors as lowercase bold letters (c.g. x). The d-dimensional (2-ball with radius r is denoted by (r):= {ze &d |2 S r). We denote by X the set of all possible examples. X is also sometimes referred to as the input space. The set of all possible labels is denoted by y. We will limit ourselves to the case of binary classification where y = +1). Let H be a family of functions from Rdd to R. Given a fixed but unknown distribution over X x y, the binary classification learning problem is then formulated as follows. The learner seeks to select predictor f ε H. with small generalization error with respect to the distribution P. The generalization error of a classifier f е H defined by Re, (f) E (x..))))llll -oooffff x. x)], where (o(f,x, y) (x) is the standard 0/1 loss. More generally, the E-risk of a classifier f for surrogate loss 8(f,x, y) is defined by
Re(
E (x.9)- (e(,x,)),
(I)
Moreover, the minimal (E, H.)-iskk which is also called the Bayes (e, H))-iskk, is defined by Ri fese fear Rf) In the standard classification setting, the goal of a consistency analysis is to determine whether the minimization of a surrogate loss & can lead to that of the binary loss generalization error. Similarly, in adversarially robust classification, the goal of a consistency analysis is determine the minimization of surrogate loss l yields that of the adversarial generalization error defined by Re, (f) = (x [L, (S, x, x)], where
(f,,,
sup 11 9x()))50
(2)
xxIx-x||s>
is the adversarial 0/1 loss. This motivates the definition of H-consistency. Definition 1 (FC-oonsistency), Given a hypothesis set H, we say that a loss function & H- consistent with respect to loss function &a, if the following holds:
Rí (fr) -Ri,,R RigH
O
(e) - -
O,
for all probability distributions and sequences of (JnJneN c H.
For distribution P over X x y with random variables X and Y, let npp - [0, 1] be a measurable
function such that, for any X E X, (x) -P(Y = 1 1 X x). By the property of conditional no where Ce(f. x) is the inner
expectation, we can rewrite (1) as Re(f)
E-risk defined as followed:
(4) Moreover, the minimal inner t-risk on H is denoted by Ci (x)x(xxn))== inf year (=(J,,,)) For a margin-based loss Φ. the generic conditional Φ-risk is (t, no(() + (1- (-) for any n E [0, 1] and ł IR (Bartlett et al., 2006). The notion of calibration for the inner risk is often powerful tool for the analysis of J--consistency (Steinwart, 2007).
V X, Vnj E [0, 1], c,(fx,,): mfx,x (1-m) -1).
Definition (H--Calibration.. [Definition 2.7 in (Steinwart, 2007)] Given a hypothesis set H, we say that a loss function & is H--alibrated with respect to loss function Eg if, for any >> 0, 7 [0. 1]. and x X, there exists 8 O such that for all f E H we have
Ce (f n) < C2 11 + 8 = (e,(f,)))) < C7n,00(x,,) +
(5)
Steinwart (2007) points out that é, is H-calibrated wrt E2, then K-consistency, that is condition (3), holds for any probability distribution verifying the additional condition of minimizability (Steinwart, 2007, Definition 2.4). Next, we introduce the notions of calibration function from (Steinwart, 2007).
Definition 3 (Calibration function). Given hypothesis set H. we define the calibration function Smax for a pair of losses (fz, E2) as follows: for all x X. n E [0, 1] and <> 0.
8max x, x, = inf (Ce, (f,x x, 11) - C7 ox n) Cr2, x, x.)) - 07, 20). 2e].
(6)
fex
3

---

X X-camissincy
3,00
Rilhaol
agn
Mimmzaoity
3P supported on
Figure 1: Illustaaioon of Hi-calibration and H--consistency. Left: HH-calibration, for any x e X, minimization of Ct2 (f,x) can lead that of C₁2 xf,x). Right: H-consistency, minimization of R2, (f) can lead to that of (f). HC-consistency reduces to H-calibrattion when the support of underlying distribution H--aliiration would imply HCconsistency.
the single point set {x] = X; Under the minimizability condition,
For any x X. 77 [0. 1] and e 0, the calibration function gives the maximal 8 satisfying the calibration condition (5), The following proposition is an important result from (Steinwart, 2007).
Proposition 4 (Lemma 2.9 in (Steinwart, 2007)). Given a hypothesis set H. loss & is H-ccalirrated with respect to & if and only if its calibration function maax satisfies Smax (e, x, n) > for all x X, r) [0, 1] and e O.
Since the concepts of calibration and consistency may not be familiar readers without an extensive background in this area, we further comment on these notions before presenting our main results. Informally, a loss function K-consistent if minimizing results a classifier whose generalization error is close to the minimal generalization error within K. Similarly, loss function is H-calibrated minimizing results in a classifier whose inner l2- 22-risk is close to the minimal inner & 22-risk within H. for each x X. H-calibration (5) is necessary condition for JC-consistency (3), but is not always sufficient, As an example, we show in Section 5.1 that H[-aalirateed surrogate losses proposed in (Bao et al., 2020) are not HC-consistent. For this reason, H--consistncyy that is consistency for particular hypothesis set H. is a difficult problem even in standard non-adversarial scenarios. When H is the family of all measurable functions, the notions of calibration and consistency with respect to the 0/1 loss have been widely studied in the literature to analyze the properties of margin-based losses (Zhang, 2004; Bartlett al., 2006). In this special case, calibration implies consistency. Steinwart (2007) further establishes a sufficient condition called minimizability under which H-calibration (5) implies H-consistency (3). Note that the minimizability condition holds in (Zhang, 2004; Bartlett et al.. 2006). However, it does not hold in general in the adversarial scenario and thus analyzing H-consistencyy becomes much harder. To the best of our knowledge, our work is the first to prove H-consistency results for general hypothesis sets H. including for the case where H = Hall. in the context of adversarial classification. We conclude this section with an illustration of the connection between the notations of calibration and consistency in Figure 1.
3 Adversarially Robust Classification
In adversarially robust classification, the loss at (x, 3) is measured in terms of the worst loss incurred over an adversarial perturbation of x within a ball of certain radius in norm. For simplicity. we will consider perturbations in the l2 norm || I." We will denote by the maximum magnitude of the allowed perturbations. Given 7 > O, data point (x,y). ) a function f H, and a margin-based loss di IR. + R,, we define the adversarial loss of f at (x, v)
H(,x x,)
sup x x+xx-XIsT
(uf(x)).
The above naturally motivates supremum- based surrogate losses that commonly used to optimize the adversarial 0/1 loss (Goodfellow et al., 2014; Madry et al., 2017; Shafahi et al., 2019; Wong et al.,
Our analysis the paper can extended directly to other perturbations such as 4 ball or Lx ball, and fact for any 4p norm for p [1, oo]. In particular, the proofs of our calibration and consistency results for general hypothesis sets (e.g.. Theorem 6, Theorem 7, Theorem 10, Theorem 16, Theorem 20, Theorem 23, Theorem 24) do not require the norm being la and work for other norms too.

---

2020). We say that surrogate loss x(f.x,) We say that the supremum- surrogate convex the function Φ in (7) is convex. When @ is non-increasing, the following equality holds (Yin et al., 2019):
x, y) is supremum-based if it is of the form defined in (7).
x x1 of p((x)
sup x sy
dvf((x))
inf
(8)
The adversarial 0/1 loss defined in (2) special case of (7), where the 0/1 loss, that is, ((f((x) (o(f.x,y) v) ux()==- Therefore, the adversarial 0/1 loss has the equivalent form
sup 11(())) (f.x xx|
inf v((x)so x/ipx-- Isy
This alternative equivalent form of adversarial 0/1 loss is more advantageous analyze than (2) and would be adopted in our proofs. Without loss of generality, let X (1) and Y (0, ) In this paper, we aim to characterize surrogate losses & satisfying HC-consistency (3) and H[-calibration (5) with 82 by and for the hypothesis sets H which are regular for adversarial calibration.
Definition 5 (Regularity for Adversarial Calibration). We say that hypothesis set H is regular for adversarial calibration if there exists a distinguishing x in X, that is if there exist f.g g H such that infix-xiis>> fx') 0 and sup/ix/xx<>> gx') O.
When studying FC-calibration of surrogate losses, suffices to study sets H that are regular for adversarial calibration not only because all common hypothesis sets admit the property, but also because of the following result. (See Appendix E. 1.1.1l1 for the proof.) We say that a hypothesis set H. is symmetric, if for any f E H, f is also in H.
Theorem 6. Let H[ be symmetric hypothesis set. If is not regular for adversarial calibration, then any surrogate loss f K-calibrated with respect to lx.
Moreover, specifically study the following hypothesis sets that are regular for adversarial
calibration: linear models: Him = {x + W x ||w|= =1), as in (Bao et al., 2020); generalized linear models: Hg tion; the family of all measurable functions: Hall and multi-layer neural networks: HNN b,)+ (b))+b))..)) b2)...- b,,) ||u|]] S 11, W, [byll B).
g(--xwx + |w| =,|==1 b) s G} where g is non-decreasing func-
{x + Pn Da(W,, "W.(==P((W)) (W where Pj is an activation function; In the special case of = (-) max(- 0). we denote the
(aPi(Wixc x
corresponding ReL.Ubbsed hypothesis see by Hretu {x (w- x), + |[ 1,10 G).
H-- FH-Calibratton
Calibration is condition that often guarantees consistency and is first step in analyzing surrogate losses. Thus, in this section, we first present a detailed study of the calibration properties of several loss functions. We first give a series of negative results showing that, under general assumptions, convex losses and supremum-based convex losses, which are typically used in practice for adversarial robustness, are not calibrated. We then complement these results with positive ones by identifying a family of losses that are indeed calibrated under certain general conditions.
4.1 Negative results: convex losses
We first study convex losses, which are often used for standard binary classification problems.
Theorem 7. Assume H. is such that there exists a distinguishing Xn E X and fo E H such that fo(xo)= O. If a margin-bause based loss d: R + R, is convex, then it is not H-calibrated with respect to by
In particular, the assumption holds when H is regular for adversarial calibration and contains By Theorem 7, we obtain the following corollary, which fixes the main negative result of Bao et al. (2020) and generalizes the result to nonlinear hypothesis sets. Note Hins HNN and Han satisfy there exists a distinguishing Xo X and fo e H such that fo(xo) 0. When g(->) + G 0 and g(7) G < 0, Hy also satisfies this assumption. Verifying this condition on H. is straightforward for G' sufficiently large.
5

---

Corollary 8. If a pargin-bbssed loss d: R R. is convex. then & is not K-calibrated with respect to for H[= Hiin Hg with non decresseg and continuous function g such that g(->) + G 0 and g(1) - G 0, Hreta with G 7, HNN, and Kall-
While convex surrogates are natural for the 0/1 loss, the current practice in designing practical algorithms for the adversarial loss involves using convex supremum-based surrogates (Madry et al., 2017; Wong et al., 2020; Shafahi et al., 2019). We next investigate such losses.
4.2 Negative results: supremum- based convex losses
We study losses of the type Φf ([f.xx.) y) supx-]|x-x((s: (xf(xx)), with é convex, which are often used in practice as surrogates for the adversarial 0/1 loss. The following theorems presents negative results for supremum-bane bassd convex surrogate losses for the common hypothesis sets H.
Theorem 9. Let & be a convex and non-increasing margin-based loss. Consider the surrogate loss defined by x(). = supx:[x-xlls> (xf(xx)). Then o is not K-calibrated with respect to fyp for K = -Hin Hyg with a non-decreasing and continuous function funcciion
such that 9(-7) + G 0 and
g(7) G G 0. and Hrelu with G.
Theorem 10. Ler H be hypothesis set containing O that is regular for adversarial calibration. Ifa margin-based loss & is convex and non-increasing, then the surrogate loss defined by Φ(f.x,)) supx:Ix-xII (yy((x (x))) is not K-calibrated with respect to E..
The theorems above provides evidence that the current practice of making networks adversarially robust via minimizing convex supremum-based surrogates may have serious deficiencies. This may also explain why in practice the adversarial accuracies that are achievable are much lower than the corresponding natural accuracies of the model (Madry et al., 2017). In general, optimizing non-calibrated or non- connosssitt surrogates could lead to undesirable solutions even under strong assumptions (such as the Bayes risk being zero). See Section where we empirically demonstrate this in a variety of settings. By Theorem 10 and the fact that HNNN and Hall both contain O and are regular for adversarial calibration, we can derive the following corollary.
Corollary 11. Let o be convex and non non-increasiin margin- margin-based loss. Consider the surrogate loss defined by o(f, x, y) = Ix- (x)(xx)). Then & is not K-calibrated with respect to ly, for H² HNN. and H = Hall-
The proofs of Theorem 7, Theorem 9 and Theorem 10 are included in Appendix E.2. The key in proving the above theorems is to analyze the calibration function (e, 17) as defined in (6) of 1, c 1 and distinguishing Xy X. Naturally, this requires us to understand losses (f, e,) at 17 2.
2
the inner risk Cf(f.x,)
x, 17) that in turn depends on the worst case perturbation of given data point according to f. Our key insight (Lemma 25) is that
77 can be characterized by two quantities M(f = infx: xx|ss>> f(x), Mff,xu, Xo, xuPx'//=ox'/1 fx'). Requiring Smax( (1. Xo. )) 0 corresponds to an appropriate convex function not achieving a minimum set that has global optimum, thereby reaching contradiction.
4.3
Positive results
In this section, we aim provide alternative losses which could be calibrated with respect to ey.
4.3.1
Characterization
In light of the above negative results, we need to consider non-convex surrogates. One possible candidate is the family of losses introduced by Bao et al. (2020) that satisfy the property that the generic conditional 6-risk Ct (t, 17) is quasi-concave in t E R for all 7 E [0, 1]. Theorem 12 below is a correction to the main positive result, Theorem 11 in (Bao et al., 2020), where we prove the theorem under the correct calibration definition.
Theorem 12. Let margin-based loss o be bounded, continuous, non-increasing, and satisfy the property that Cy (t, 1) is quaaiiiaaoonaaao quasi-concave in t & E for all r e [0, 1]. Assume that @(-t) > @(t) for any y < 1. Then è is Hino -calibrated with respect to l,, if and only if for any y t S 1,
o(t) o(-t).
(10)
6

---

The proof of Theorem 12 is included in Appendix E.4, where we make use of Lemma 27 and Lemma 28, which are powerful since they apply to any symmetric hypothesis sets, These lemmas would be used for proving more general positive results, as we will show later. Note Theorem 1 in (Bao et al., 2020) does not hold any more under the correct calibration Definition 2, since their
condition <(7) ((->)>> ((1) + ((-1) is much weaker than (10).
The following theorem extends the above show that under certain conditions, such surrogate losses are H-calibrated for the class of generalized linear models with respect to the adversarial 0/1 loss.
Theorem 13. Let g be a non-decreasing and continuous function such that g(1 + 7) < G and g(-1-7) > -G for some G 120 0. Let a margin-based loss & be bounded, continuous, non-increasing, and satisfy the property that Ct(t, is auasi-concave in t E R. for all n E [0.1]. Assume that ((g(-t) G) > (GG -((-t) and g(-t) + g(()== 2 0 for any 0 S t 1. Then 6 is -aacbaaidd with respect to e, if and only if for any 0 S t 1,
-====())==)()))) + G) and (006
(G- 9(-)) + +--(())()))))))))))))>>))))))))) -()
(((-)) (g(-t)- G),
where A(t) max.e 7)> and A(t) minge(-r.4 g(s +7).
See Appendix E.5 for the proof. The conditions in the theorem above are necessary and sufficient and thus characterize calibration for such surrogate losses. To interpret the conditions better, consider ReLU functions, In that case, the assumptions can be further simplified to get the following corollary.
Corollary 14. Assume that G > 1+%. Let margin- loss o be bounded, continuous, non- increasing, and satisfy the property that Co 1) is quasi-concave in R for all n e [0, 1]. Assume that ø( G) > (G)) Then o is callbbrade with respect to Ey if and only for any 0 < t s 1,
(GG) + O(-G) = A1 G) ((-L-G) and + (()))(--)) (G) + (-G)).
4.3.2 Calibration
To demonstrate the applicability of Theorem 13, we consider a specific surrogate loss namely the p-margin loss (t) := min 1I
p> O, which is a generalization of the ramp loss (see, (Mohri et al., 2018)). We also define its supremum- based counterpart as éf x, y) := supx:]xxx'(]ss (x)))))) Using Theorem 12, Theorem 13 and Corollary 14 in Section 4.3.1, we can conclude that the p-margin loss is calibrated under reasonable conditions for linear hypothesis sets and non-decreasing g-based hypothesis sets, since (t) is bounded, continuous, non-incre.sing, and satisfies C.2, (t, is quasi-concave in te TR. for all n e [0, This is stated formally below.
Theorem 15. The surrogate op is -illbcabbbrated with respect to by if and only if p y. Given a non-decreasing and continuous function g such that g(1+7) < G and g(-17)) > -G for some G 2 O. assume that g(t)+ 2 foor any 0 S &t& 1, then op is H. caalibratee with respect to b, if only if for any 0 S t 5 1, =))(GG(()))= where A(t) max 9() 7) and A(t) min g(s) g(s 7). Assume that G 1 1+ then @p is -allbbrcd with respect to e, if and only G 2 p>7
and min (A(t)) o (p(-A(t))} (G-
-
Recall that in Theorem 10 we ruled out the possibility of finding Halllbraated supremum- based convex surrogate losses with respect to the adversarial 0/1 loss. However, we show that the supremum-basee p-margin loss is indeed H-calibrated, where H is any symmetric hypothesis set.
Theorem 16. Let H be a symmetric hypothesis set, then o, is H-ccaiibrated with respect to Eyp
The proof of Theorem 16 is included in Appendix E.4. By Theorem 16 and the fact that Hins HNN and Hall are all symmetric, we derive the following.
Corollary 17. do is H-calibrated with respect to by, for H Him. HNN, and Kall-
The results of this section suggest that the p-margin loss and supremum-based p-margin loss may be good surrogates for the adversarial 0/1 loss. However, calibration, in general, is not equivalent to consistency, our eventual goal. In the next section, we study conditions under which we can expect these surrogates losses to be H--consistent well.
7

---

H--Consistency
In this section, we study the Jy-consistency of surrogate loss functions. The results of the previous section suggest that convex losses or supremum-based convex losses would not be H-consistent. However, HH-calibrated losses, such as the p-margin loss and supremum- an intriguing possibility. Bao et al. (2020) made a claim that since the losses they proposed are calibbatd they are also Hinn Consiieett
p-margin loss present
first present a result that implies this claim incorrect. In fact, our result stated below shows that without assumptions on the data distribution, no continuous margin based loss supremum-base baased continuous surrogate could be Hnnn-oonssttet,
5.1 Negative results
Theorem 18. No continuous margin- based loss function & is Hiaa-consisten with respect to lap Furthermore, for any continuous and con-increasing margin-base -aaeed loss Φ, surrogates of the form
o(fxx,)) = sup xxIxx-x11s>
(vf((x))
not Hinn -Conssitsttt with respect ly
The above theorem is proven in Appendix E.6. In particular, Theorem 18 contradicts the H-- consistency claim of Bao al. (2020) for their proposed losses when K is the family of linear functions. Furthermore, the theorem rules out K-coosistency of supremum supremum-based surrogates.
5.2 Positive results
In this section, investigate the nature of the assumptions the data distributions that may lead to K-consistency of surrogate losses. We take inspiration from the work of Long and Servedio (2013) and Zhang and Agarwal (2020) who study H-coosistency for the standard 0/1 1 loss. These studies establish consistency under realizability assumption on the data distribution stated below that requires the Bayes (C,, HO-risk to be zero.
Definition 19 (H-realizabiiltty). A distribution P over X is K-realizable if it labels points according to a deterministic model in H, i.e., if E H such that P(xxa)- (fgu( y) =.
As with H-realizability, we will assume that, under the data distribution, the Bayes (L,, H)-risk is zero. We show that the H-callibrated losses studied in previous sections are K-consistent under natural conditions along with the realizability assumption.
5.2.1 Non-supremum-basst based surrogates
Theorem 20. Let P be distribution over X x y and H a hypothesis set for which R2 0. Let Ø be wargin-based loss. If n O, there exists f E H Hau such that Ro( S R +1 +oo and & is H-calibrated with respect to Exp then for all <>> there exists 8 0 such that for all f e H,
Rf( + R. + = Re, < RT R2 +
For the family of linear models, some convex losses may also be -olnssstnttt verifying the conditions (1) = 0) Theorem 20. However, caalbbratd losses can #iim-consssten under more benign assumptions, where the realizability condition R2 = 0 can be further relaxed.
Theorem 21. Let P be a distribution over
Assume that there exists g" Hij such that Re, (g*) R2, Ka,"" Let & be a cargin-baseed loss. ffr 11 0, there exists f & Hii c Hall such that Ro Ro + 7 < +00 and @ is Hin HCin-caabbrated with respect ly, then for all there exists 8 0 such that for all f Hin we have
R&( +) Rd 6.96m +0 - Re, ( RR,,
RR2,,6.. Pia
The proofs of Theorem 20 and Theorem 21 are presented in Appendix E.7. Using Theorem 15 in Section 4.3.2 and theorems above, we immediately conclude that the calibrated p-margin loss consistent with respect to e, for all distributions that satisfy our realizability assumptions.

---

0.5
Ove
Oue
-1
0
Figure Left: Unit Circle with 1,000 and 2,000 samples. Right: Segment with 5,00 samples.
Theorem 22. p then 6p is Hiin--onsisiii -onnsiseett wrt lyy for all distributions such that there exists g" Hiin with Re, (g') N and there exists f Kiin such that Rv. (fr - Mann" If verifies the calibration condition Theorem 15, then @p is -oncsiiitt wrt for all distribution P over X x y that satisfies Ri,,,, = O and there exists f E eHg such that Rø, (f*)= (f)
R Ka If
G> 1+ and G p> Yi then Up is Hrelu -cnnsistent wrt Exy for all distribution P over X y that satisfies R2, Keati = and there exists f Hrelu such that Rv, (f*) R Kan""
5.2.2 Supremum-base surrogates
We can also extend the above to obtain --consisty of supremum- based convex surrogates. However need the stronger condition that R. is minimized exactly inside H..
Theorem 23. Given a distribution P over X x y and hypothesis set H such that Ri,, = O. Let Φ be non-increasing margin-buse based loss. If there exists f e H Han such that R&x R < +oo and Φ( {f, x,y) y) supx:|x-xxlss Φyy (x))) is K-calibrated with respect to ly then for all c there exists 8 0 such that for all f H we have
R (f( R
3,3 +
Re,(F) R 2e +
The proof of Theorem 23 is presented in Appendix E.7. Again, when combined with Theorem 16 in Section 4.3.2 conclude that the K-calibrated supremum-basse p-margin loss is also H-consistent with respect to by for all distributions that satisfy our realizability assumptions.
Theorem 24. Let H be symmetric hypothesis set, then dp is K-consistent with respect to e for all distributions P over x y that satisfy: Ri = 0 and there exists f e H such that Re, (f*) = R2, Kan < +00.
Experiments
Here, we present experiments on simulated data to support our theoretical findings. The goal is two-fold. First, we empirically demonstrate that indeed HC-calibrated surrogates in (Bao et al., 2020) may not be HC-consistent unless assumptions on the data distribution are made, even when H the class of linear functions. This is consistent with our negative result in Theorem 18 and provides an empirical counterexample to the claim made in (Bao al., 2020). Second, we study the necessity of the realizability assumptions we adopted in Section 5.2 to establish K-consistency of surrogates satisfying the conditions in Theorem 12.
We generate data points x E R² on the unit circle and consider H to be linear models Hiin- We denote f(x) w x. w (t))))))sin(t)) ,t f0, Hijn. All risks are approximated by their empirical counterparts computed over 10" i.i.d. samples. To demonstrate the need for some assumptions for H--consistnncy, we construct scenario we call the Unit Circle case. We consider four surrogates: Ohinge. Pramp. Psig and ólog defined in Appendix C.I. In general, we refer all of these surrogates as @sur. We generate data points x from the uniform distribution on the unit circle. Define x x = (cos(0); sin(())) 0 [0, 2nr. Set the label of point as follows: if 3
fe [ 3). then y -1 with probability á and 1 with probability 1,
4: if 0 E (0, Σ or ( (37 2x). v2 In this case, the Bayes (ly, Him)-rist is 2 then y = -1. Set
then y = 1; if 0 (T, 3x
R2 0.5000 0 and is achieved by wy, = (i)))))(n())) with 0 0. 0.7855. The results obtained by optimizing the different surrogate losses reported in Table ((a) and the plots for

---

Table I: (a) Unit Circle; (b) Segments.
Osur
R2, (f*)
Haa-CCa cal. -oons
Pluur
Re. (e_(5))
Re.... (f')
(iin-Cal [iL cons.
hingg
0.5257
0..1420
Phingo
0.0781
0.6907
1.3548
Oramp
0.5263
0.1288
Pramp
0.0781
0.3454
1.3548
Osig
0.5261
0.1320
0.0777
0.4247
1.3498
V
X
Plog
0.5258
(0.1414
X
X
0.0763
0.8078
1.3341
K
X
0.0111
0
X
X
8
22
0
0
(a)
(b)
1,000 samples and 2,000 samples are shown in Figure 2. Table ((a) shows that neither calibrated nor non-calibrated (convex) surrogates are -onsssttt with respect to & for this distribution. Figure 2 shows that the classifiers obtained by optimizing the four surrogates are almost the same but deviate a lot from the optimal Bayes classifier for ly This shows that indeed calibrated surrogates may not be consistent and contradicts Figure 12 of (Bao et al., 2020). The discrepancy results from an incorrect calculation of the adversarial Bayes risk in (Bao et al., 2020).
Next, we justify the realizability assumptions made in Section 5.2 for obtaining Hi-consisty of surrogate losses. To do so, we design scenario that we call the Segments case. Here, we consider six surrogates, the four studied above and two more surrogates Φ1 and Φ2 defined in Appendix C.I. The loss Φ1 a convex loss and Φ2 is the p-margin ramp loss for some p > 7. general, we refer to all of these surrogates as Osur- We show in Appendix C.2 that @hinge Plog and Φi are not Hinn- call-battbe while Pramps Osig and Φ2 are Hn Hin--alibbaan calibrated with respect to Ey.
Let 14 V 11-5 R22 and consider: IP 1) = P(Y = =1) = 2. and X Y = is the uniform distribution on the line segment =().2) E [0, 43 and X Y -1 is the uniform distribution on the line segment ((-5,=) = [=/,0] 0]} where & = 7 100
1-7 1+997 E (0. We choose
is easy to check that w achieves the Bayes (f,,, Hin -risk R2 = The results for the six different surrogate losses are indicated in Table 1(b) and the plot for 5,00 samples are shown in Figure 2. For Ohinge- Pramp: Psig and Glog. the Bayes (Ø -risk R HGn. # 0. Table 1(b) shows that they are not Hiin -onniisettt with respect to l For Φ1 and d22, the Bayes (deur. Hiin) Friskk R Kim = -.. Table 1(b) shows that Φ1 is not Hin consistent (recall that Φ1 is not calibrated) but Φ₂ is Hin coonsisent for this distribution. Hence, even when Kr, O, unless a condition is also imposed on 2g,, one cannot expect consistency, thereby justifying
= 0.1 and set w* = (1,0)
Sa
realizability as- sumption. Note that R2 Mh. R2 Nia = 0 is a special case verifying the conditions of Theorem 20 for = O. For this distri- bution, Gramp is not -oonsistet while Φ2 is Han -onsiiseet,, although both are Hin callibraedd We compare them in Figure 3, showing that minimizing -onsistttttt surrogate d2 minimizes the adversarial generalization error for large sample sizes but the same does not hold for non Hin- consistent surrogate Dramp-
10
150
700
750
Figure 3: Adv. true risk of con- sistent and calibrated inconsis- tent losses vs. sample size.
7 Conclusion
We presented a detailed study of calibration and consistency for adversarial robustness. These results can help guide the design of algorithms for learning robust predictors, an increasingly important problem in applications. Our theoretical results show in particular that many of the surrogate losses typically used in practice do not benefit from any guarantee. Our empirical results further illustrate that in the context of a general example. Our results also show that some of the calibration results presented in previous work do not bear any significance, since we prove that in fact they not guarantee consistency. Instead, we give a series of positive calibration and consistency results for several families of surrogate functions, under some realizability assumptions.
10

---

Acknowledgements
This work was partly funded by NSF CCF-1535987 and NSF IIS- 161662.
References
Attias, I., Kontorovich, A., and Mansour, Y. (2018). Improved generalization bounds for robust learning. arXiv preprint arXiv:8800002180.
Awasthi, P., Dutta, A., and Vijayaraghavan, A. (2019). On robustness to adversarial examples and polynomial optimization. In Advances in Neural Information Processing Systems, pages 13737-13747.
Awasthi, P., Frank, N., and Mohri, M. (2020), Adversarial learning guarantees for linear hypotheses and neural networks. In International Conference on Machine Learning, pages 431-441.
Bao, H., Scott, C., and Sugiyama, M. (2020). Calibrated surrogate losses for adversarially robust classification. In Conference on Learning Theory, pages 408-451.
Bao, H., Scott, C., and Sugiyama, M. (2021). Corrigendum to: Calibrated surrogate losses for adversarially robust classification. arXiv preprint arX14.2005.13748.
Bartlett, P. L., Bubeck, S., and Cherapanamjeri, Y. (2021). Adversarial examples in multi-layer random relu networks. arXiv preprint arXiv:2106. 12611.
Bartlett, P. L., Jordan, M. I., and McAuliffe, J. D. (2006). Convexity, classification, and risk bounds. Journal of the American Statistical Association, 108(473)
Boyd, S. P. and Vandenberghe, L. (2014). Convex Optimization. Cambridge University Press.
Bubeck, S., Lee, Y. T., Price, E., and Razenshteyn, I. (2018a). Adversarial examples from crypto- graphic pseudo-random generators. arXiv preprint 1rXiv:1811.0641
Bubeck, S., Price. E., and Razenshteyn, (2018b). Adversarial examples from computational
constraints. arXiv preprint arXiv:1805.
Carlini, N. and Wagner, D. (2017). Towards evaluating the robustness of neural networks. In IEEE Symposium on Security and Privacy (SP), pages 39-57.
Carmon, Y., Raghunathan, A., Schmidt, L., Liang, P., and Duchi, C. (2019). Unlabeled data improves adversarial robustness, arXiv preprint arXiv: 1et..
Cullina, D., Bhagoji, A. N., and Mittal, P. (2018). PAC-learning in the presence of evasion adversaries. arXiv preprint 1tf6::8800.4444
Diakonikolas, I., Kane, D. M., and Manurangsi, P. (2020). The complexity adversarially robust proper learning of halfspaces with agnostic noise. arXiv preprint arXiv:2007.15200
Feige, U., Mansour, Y., and Schapire, R. (2015). Learning and inference in the presence of corrupted inputs. In Conference on Learning Theory, pages 637-657.
Feige, U., Mansour, Y., and Schapire, R. E. (2018). Robust inference for multiclass classification. In Algorithmic Learning Theory, pages 368-386.
Gao, W. and Zhou, Z.-H. (2015). On the consistency of auc pairwise optimization. In Twenty-Fourth International Joint Conference on Artificial Intelligence.
Goodfellow, J., Shlens, J., and Szegedy, C. (2014), Explaining and harnessing adversarial examples. arXiv preprini 1412.524
Khim, J. and Loh, P.L. (2018). Adversarial risk bounds for binary classification via function transformation. arXiv preprint arXiv:1810.0955
Krizhevsky, A., Sutskever, I., and Hinton, G. (2012). Imagenet classification with deep convolu- tional neural networks. In Advances in Neural Information Processing Systems, pages 1097-1105.

---

Long, P. and Servedio, R. (2013). Consistency versus realizable H-consistency for multiclass classification. In International Conference on Machine Learning, pages 801-809.
Madry, A., Makelov, A., Schmidt, L.,, Tsipras, D., and Vladu, A. (2017), Towards deep learning models resistant adversarial attacks. arXiv preprini arXiv:/706.06083
Mohri, M., Rostamizadeh, A., and Talwalkar, A. (2018). Foundations of Machine Learning. MIT Press, second edition.
Montasser, O., Hanneke, S., and Srebro, N. (2019). Ve classes are adversarially robustly learnable, but only improperly. arXiv preprint 1rXiiv:9002.0 1902.0421..
Montasser, O., Hanneke, S., and Srebro, N. (2020). Reducing adversarially robust learning to non-robust pac learning. arXiv preprint wrXiv:2010.12033
Shafahi, A., Najibi, M., Ghiasi, M. A., Xu, Z., Dickerson, J., Studer, C., Davis, L. S., Taylor, G., and Goldstein, T. (2019). Adversarial training for free! Advances in Neural Information Processing Systems, pages 3353-3364
Steinwart, I. (2007). How to compare different loss functions and their risks. Constructive Approxi- mation, 26(2):225-25 2877
Sutskever, I., Vinyals, O., and Le, Q. V. (2014). Sequence to sequence learning with neural networks. In Advances Neural Information Processing Systems, pages 3104-3112.
Szegedy, C., Zaremba, W., Sutskever, I., Bruna, J., Erhan, D.,, Goodfellow. I., and Fergus, R. (2013). Intriguing properties of neural networks. arXiv preprint arXiv: 131.61931,.6699
Tewari, A. and Bartlett, P. L. (2007). On the consistency of multiclass classification methods. Journal of Machine Learning Research, 8(36); 1007-
Tsipras, D., Santurkar, S., Engstrom, L., Turner, A., and Madry, A. (2018). Robustness may be at odds with accuracy. arXiv preprint arXiv: 12051120...
Uematsu, K. and Lee, Y. (2011). On theoretically optimal ranking functions in bipartite ranking. Department of Statistics, The Ohio State University, Tech. Rep, 863.
Wong, E., Rice, L., and Kolter, J. Z. (2020). Fast is better than free: Revisiting adversarial training. arXiv preprint arXiv:2001 .03994.
Yin, D., Ramchandran, K., and Bartlett, P. L. (2019). Rademacher complexity for adversarially robust generalization. In International Conference of Machine Learning, pages 7085-7094.
Zhang, H., Yu, Y., Jiao, J., Xing, E. P., Ghaoui, L. E., and Jordan, M. I. (2019). Theoretically principled trade-off between robustness and accuracy. arXiv preprint arXiv:1901.0853
Zhang, M. and Agarwal, S. (2020). Bayes consistency vs. h-consistency: The interplay between surrogate loss functions and the scoring function class. In Advances in Neural Information Processing Systems, pages 16927-16936.
Zhang, T. (2004). Statistical behavior and consistency of classification methods based on convex risk minimization. The Annals of Statistics, 32(1) (2(1):56885 85.
12


Reviews:
[{"review_id": "m4X_TIODJpK", "reviewer": "Reviewer_vHnZ", "summary": "This paper provides an extensive analysis of the satisfiability of H-calibration and H-consistency for surrogate losses in binary classification, where the evaluation metric is not the standard 0-1 loss but the adversarial 0-1 loss. The adversarial 0-1 loss is a pointwise loss defined on an input x by calculating the supremum of the 0-1 loss value of a point that can perturb around x within a ball of a pre-specified radius. This paper reveals a negative result showing that many surrogate losses are not H-consistent, especially the convex losses.  This paper also reveals a positive result of a certain class of non-convex losses that can be H-consistent under some assumptions. Synthetic experiments were also provided to justify the relevance of theoretical findings.", "questions": "", "limitations": "", "rating": 9, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Although this paper looks theoretically heavy and dense at glance, I found that reading this paper was a very enjoyable experience. The paper is very well-written. The authors did a very good job to provide motivation and intuitive explanations for most theoretical results presented in this paper. I appreciate the fact that both margin-based losses and their supremum version are both studied. Also, the hypothesis class considered in this paper goes beyond a simple linear model. Furthermore, it resolves some issues of recent work. Overall, I found the theoretical results of this paper are highly significant and definitely help to improve our understanding of a surrogate loss behavior in adversarially robust classification. Thus, I vote for a strong acceptance for this paper.\n\nWeaknesses:\n1. Perhaps more illustration at the beginning of the paper can improve the readability for readers who are not familiar with adversarial surrogate losses, margin losses, a regularity condition for $\\mathcal{H}$. Due to space limitations, I understand that doing all this can be quite challenging but it may still be worth considering.\n2. One may criticize that the result is limited to the binary classification case, but I think the result only on the binary classification is already sufficient.\n3. Some parts of the paper may not be self-contained enough since many contents are deferred to Appendix (deferring the proof is perfectly acceptable in my opinion). But for example, in experiments, my impression is that it is necessary to write down a loss function form (provided in Appendix C.1).\n\nQuestions:\n1. It is very insightful that H-calibration does not imply H-consistency. Nevertheless, in the setting of adversarial classification considered here, can we say that H-calibration is a \"necessary\" condition for H-consistency? I believe so but it was not stated clearly in the paper in my understanding or perhaps I missed it. If so, then the notion of H-calibration is still very useful to filter out some surrogate losses without checking the H-consistency condition.\n2. Is there any existing results of Fisher consistency in the context of adversarial classification before this paper? If not, do I understand correctly that when we use $\\mathcal{H}_{\\textrm{all}}$, we are considering a notion of standard Fisher consistency (i.e., infinite sample consistency) and this paper is the first to prove such results?\n3. I am a bit confused around Lines 156--160. it is said that studying regular $mathcal{H}$ is enough because Theorem 6, which is specific for symmetric hypothesis set, states that \"if $\\mathcal{H}$ is NOT regular, then any surrogate loss is $\\mathcal{H}$-calibrated. My understanding is that for non-regular set, it causes the definition of $\\mathcal{H}$-calibration to be useless, however, since $\\mathcal{H}$-calibration is not equivalent to $\\mathcal{H}$-consistency, wouldn't this mean they might be worth considering?\n4. How strong the requirement that $\\mathcal{H}$ is symmetric is? Is this the case for most hypothesis classes we can think of? \n5. Is there other settings that H-calibration does not imply H-consistency other than adversarially robust classification? If I understood correctly, I guess this setting is not the first work that has this phenomenon. Thus, it could be useful to discuss this phenomenon a little bit more to suggest that it is not special only for adversarially robust classification (if space allows). To my knowledge, if I understand correctly, I am aware that in AUC-optimization, calibration also does not imply consistency in the all measurable function cases [1][2]. \n6. Does a relaxed assumption to obtain H-calibration that does not require the Bayes $(\\ell_0, \\mathcal{H})$-risk to be zero in Theorem 21--23  equivalent to saying that the model misspecification does not occur (i.e., it is well-specified)?\n7. Do the presented numbers in Table 1 sufficient to tell that surrogate risks of all candidate losses were successfully minimized? If not, is there a way to do that (maybe it is difficult...)? \n8. Is it straightforward to extend this framework to the multiclass case? \n\n[1] Uematsu and Lee, On Theoretically Optimal Ranking Functions in Bipartite Ranking, JASA, 2016\n\n[2] Gao and Zhou, On the consistency of AUC pairwise optimization, IJCAI, 2015 (Lemma 3).\n\nMinor comments:\n1. The use of \\citep and \\citet are mixed in a strange way. I am not sure if this was intentional. For example, I think Line 72, many parts in Appendix B, Line 79, 122, 132, 133, 162, 237, 342, 345, 364, 365 should be \\citet in my understanding.\n\nUpdate: I have read other reviews and authors' feedback. I believe this paper did a great job and therefore my score remains unchanged (strong accept).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The discussion was adequate.", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10 hours"}, "extra_text": {}}, {"review_id": "NlL4jybSQEy", "reviewer": "Reviewer_ks5M", "summary": "The authors provide an extensive characterization of calibration and consistency for surrogates to the l2 robust 0-1 loss, along the lines of what Bartlett et al. and Steinwart provided for the standard 0-1 loss.  They demonstrate that convex losses and supremum-based convex losses are not calibrated, and further that calibration is in general not sufficient to guarantee consistency.  This corrects a previous incorrect assertion made by Bao et al. in a COLT 2020 paper.  They provide experiments which corroborate their results. ", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The results in this paper are, to my knowledge, significant.  Consistency and calibration of convex surrogates to the standard 0-1 loss is by now a classical topic with over a decade of serious research in the area.  Given the numerous questions about the existence of adversarially robust classifiers in complicated hypothesis classes, the study of calibration and consistency in this setting is important.  Although Bao et al. (2020) analyzed consistency and calibration of surrogates to the l2 robust 0-1 loss, the authors demonstrate that they made serious errors throughout their work, thus this work helps address a significant problem with previous work.  They also provide a number of significant extensions of the (incorrect) work of Bao et al, providing analysis of how the calibration and consistency results differ when using linear/relu hypothesis classes as well as the classes of neural networks and all measurable functions.  \n\nI found the exposition clean and friendly to read in the main section, which was impressive given the large number of results presented in the paper.  (I did not have time to read the proof details in the appendix.)  I don't have any significant issues with the paper, but below are a few minor points that I think could help improve the paper.\n\n(1) Figure 1 is unreadable.  Even zooming to maximum on computer, it wasn't possible to see what was happening.  Please re-make the figure and give a more descriptive caption.\n\n(2) A figure for the Segments experiment, showing what the distribution looks like, would be helpful.\n\n(3) For experiments, it wasn't clear to me how the authors calculated the minimizer of the robust 0-1 loss for different settings; is there an exact formula that is possible from using the constructed distribution?  If not, how?\n\n(4) Further discussion on the computational tradeoffs of adversarial consistency would improve the paper.  The results suggest that in order for consistency to hold in this setting, one must use non-convex surrogates, leaving open the question of how to minimize such surrogates, even in the linear hypothesis setting.  Recent work has shown that in the non-robust linear hypothesis setting, minimizers of convex surrogates have sub-optimal performance for learning linear classifiers in the non-realizable setting, while minimizing nonconvex surrogates with gradient descent leads to nearly-optimal guarantees [1'].  Likewise, the current state-of-the-art algorithms for learning robust linear classifiers in the non-realizable setting are based on a supremum-based *non*-convex surrogate in the language of the paper, i.e. adversarial training on a non-convex sigmoidal loss, with convex surrogates having less strong guarantees (although with no lower bounds proving a separation) [2'].  It would be worth commenting on these two works, e.g. around lines 189-191. \n\n\n[1'] Non-Convex SGD Learns Halfspaces with Adversarial Label Noise. Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, Nikos Zarifis. NeurIPS 2020\n\n[2'] Provable Robustness of Adversarial Training for Learning Halfspaces with Noise. Difan Zou, Spencer Frei, Quanquan Gu.  ICML 2021\n\n** Post rebuttal **\n\nI'm happy with the author response and am sticking with my strong recommendation for acceptance. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Adequately addressed", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "Gs7BvaokSH6", "reviewer": "Reviewer_mcZd", "summary": "This paper provides a detailed analysis on the H-calibration and H-consistency of adversarial surrogate losses. \n\nIt shows that some common used losses for adversarial training are not H-calibrated.  \n\nSome theoretical results on the characterization of H-calibration are established.  The paper also proves that some surrogate losses are indeed H-calibrated.\n\nSome additional theoretical results on H-consistency are established too.\n\n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "1. This paper contains too many theorems, definitions, propositions, and corollaries. It is very difficult to track the main ideas, especially for those who are not familiar with this area.\n\n2. There is a key reference Bao et al. (2020). It seems that this paper is questioning that many results in Bao et al. (2020) are wrong results. Is it possible to make a summary what results in Bao et al. (2020) are not correct and how to correct them?\n\n3. There is a gap between the theory and the practice. Can you provide some numerical analysis on some benchmark datasets by using the proposed H-consistency losses? It would be interesting to see the benefit over the commonly uses loss functions.\n\n4. The perturbation ball is fixed to be the $\\ell_2$ ball. Can the analysis be extended to other perturbation such as the $\\ell_\\infty$ ball?   \n\n5. For the proofs of these theorems, is there any novel techniques beyond the current references? \n\n6. Is it straightforward to extent the current analysis from binary classification to multiple-class classification?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "95MHEK6Vmxd", "reviewer": "Reviewer_yRf4", "summary": "This paper focuses on the H-calibration and H-consistency of loss functions in terms of adversarial robustness. The authors claim that the reason for the difficulty in achieving the adversarial robustness is related to the current convex surrogate losses. Theoretically, they showed the limitation of H-calibration of convex loss functions and surrogate loss functions. Furthermore, they rejected the result from previous studies which provides the relationship between H-calibration and H-consistency, and found a condition that the relationship working correctly. They proposed a non-convex loss function to satisfy H-calibration and experimentally showed the advantages of the proposed loss.", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength.\n* Well-written theorems and their assumptions.\n* New proposed surrogate loss.\n\nWeakness.\n* A more generalized analysis is needed: The authors use l2 norm for adversarial perturbations. How about l1 norm or l_inf norm?\n* A question on the writing: Why Theorem 9 and Corollary 11 are disparted not as in Section 4.1?\n* The generalization of proposed \\rho-margin loss: The reasonable inspiration of proposing \\rho-margin loss is not clear. How about other non-convex surrogate losses?\n* Explanations on experiment details: In table 1, why the results on \\phi_1 and \\phi_2 are missing? Do the results are consistent with other perturbation extent \\gamma? The theoretical proof of the optimal value in the unit circle experiment (\\theta=0.7855) is missing.\n* Lack of experiments: This paper suggests a new loss, however, the advantage of the suggested loss is not strongly supported due to the lack of experiments. Zhang et al. [1] similarly proposed a new loss and provided the proof of the calibration of the proposed loss, then included the extensive experiments on MNIST and CIFAR10. If there are more experiments on bigger data, the claims in the paper becomes more convincing.\n\nI would be happy to raise my score if the authors could address the weakness.\n\n[1] Zhang, H., Yu, Y., Jiao, J., Xing, E., El Ghaoui, L., & Jordan, M. (2019, May). Theoretically principled trade-off between robustness and accuracy. In International Conference on Machine Learning (pp. 7472-7482). PMLR.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Refer to the main review.", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: I agree with the reviewers that this paper makes substantive contributions to understanding the role of surrogate losses in adversarial learning. To make the paper more accessible, I encourage the authors to make the exposition (at least the first few sections) more friendly to readers who don’t have an extensive background in learning theory.
Decision: Accept (Spotlight)