Calibration and Consistency of Adversarial Surrogate Losses
Year: 2022

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 H-calibration and H-consistency of adversarial surrogate losses. We show that convex loss functions, or the supremum-based convex losses often used in applications, are not H-calibrated for common hypothesis sets used in machine learning. We then give a characterization of H-calibration and prove that some surrogate losses are indeed 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 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 H-consistent. We also report a series of empirical results which show that many H-calibrated surrogate losses are indeed not H-consistent, 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.

heading: 1 Introduction
text: Complex multi-layer neural networks trained on large datasets have achieved a remarkable performance in several applications in recent years, in particular in 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 a result of a minor variation, which may be the presence of a 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 `p norm input perturbations (Goodfellow et al., 2014; Madry et al., 2017; Tsipras et al., 2018; Carlini and Wagner, 2017). The standard 0/1 loss is
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
then replaced with a more stringent adversarial loss, which requires a predictor to correctly classify an input point x and also to maintain the same classification for all points at a small `p distance of x. 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 a function of f(x) but also of its values around a neighborhood 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 a 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 a more relevant and desirable property for learning. Long and Servedio (2013) gave examples of surrogate losses that are not H-consistent when H is the class of all measurable functions but that satisfy a realizable H-consistency condition when H is the class of linear functions. More recently, Zhang and Agarwal (2020) studied the notion of improper realizable H-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-consistency 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-consistency is that of H-calibration, which is a related notion that involves conditioning on the input point. H-calibration often is a sufficient condition for H-consistency 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 H-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 a 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 supremumbased convex losses, that are loss functions defined as the supremum over a ball of a convex function, which are those commonly used in applications, are not H-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 H-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 H-consistent. This, in particular, proves that a claim presented in a COLT 2020 publication is inaccurate. Next, in contrast, we show that when the minimum of the surrogate loss is achieved within H, under some general conditions, the ρ-margin ramp loss (see, for example, (Mohri et al., 2018)) is H-consistent for H being the linear hypothesis set, or any non-decreasing and continuous g-based hypothesis set, including the ReLU-based hypothesis set. We then give similar H-consistency guarantees for supremum-based surrogate losses based on a non-increasing auxiliary function, including the calibrated supremum-based ρ-margin ramp loss when H is any symmetric hypothesis set, e.g., the multi-layer neural networks. In Section 6, we further report a series of empirical results on simulated data, which show that many H-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 H-consistent and that minimizing such losses may not lead to a more favorable adversarial loss. This could be in fact the reason why the empirical results reported in the literature have not been
favorable. Instead, we suggest alternative surrogate losses that we prove are H-consistent and that can be useful to 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).

heading: 2 Preliminaries
text: We will denote vectors as lowercase bold letters (e.g. x). The d-dimensional l2-ball with radius r is denoted by Bd2(r)∶= {z ∈ Rd ∣ ∥z∥2 ≤ 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,+1}. Let H be a family of functions from Rd to R. Given a fixed but unknown distribution P over X×Y, the binary classification learning problem is then formulated as follows. The learner seeks to select a predictor f ∈ H with small generalization error with respect to the distribution P. The generalization error of a classifier f ∈H is defined byR`0(f) = E(x,y)∼P[`0(f,x, y)], where `0(f,x, y) = 1yf(x)≤0 is the standard 0/1 loss. More generally, the `-risk of a classifier f for a surrogate loss `(f,x, y) is defined by
R`(f) = E (x,y)∼P [`(f,x, y)]. (1)
Moreover, the minimal (`, H)-risk, which is also called the Bayes (`, H)-risk, is defined byR∗`,H = inff∈HR`(f). 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 to determine if the minimization of a surrogate loss ` yields that of the adversarial generalization error defined by R`γ (f) = E(x,y)∼P[`γ(f,x, y)], where
`γ(f,x, y)∶= sup x′∶∥x−x′∥≤γ 1yf(x′)≤0 (2)
is the adversarial 0/1 loss. This motivates the definition of H-consistency. Definition 1 (H-Consistency). Given a hypothesis set H, we say that a loss function `1 is Hconsistent with respect to a loss function `2, if the following holds:
R`1(fn) −R∗`1,H n→+∞ÐÐÐ→ 0 Ô⇒ R`2(fn) −R∗`2,H n→+∞ÐÐÐ→ 0, (3) for all probability distributions and sequences of {fn}n∈N ⊂H.
For a distribution P over X × Y with random variables X and Y , let ηP∶X→ [0,1] be a measurable function such that, for any x ∈ X, ηP(x) = P(Y = 1 ∣ X = x). By the property of conditional expectation, we can rewrite (1) as R`(f) = EX[C`(f,x, ηP(x))], where C`(f,x, η) is the inner `-risk defined as followed:
∀x ∈ X,∀η ∈ [0,1], C`(f,x, η)∶= η`(f,x,+1) + (1 − η)`(f,x,−1). (4) Moreover, the minimal inner `-risk on H is denoted by C∗`,H(x, η)∶= inff∈H C`(f,x, η). For a margin-based loss φ, the generic conditional φ-risk is C̄φ(t, η)∶= ηφ(t) + (1 − η)φ(−t) for any η ∈ [0,1] and t ∈ R (Bartlett et al., 2006). The notion of calibration for the inner risk is often a powerful tool for the analysis of H-consistency (Steinwart, 2007). Definition 2 (H-Calibration). [Definition 2.7 in (Steinwart, 2007)] Given a hypothesis set H, we say that a loss function `1 is H-calibrated with respect to a loss function `2 if, for any > 0, η ∈ [0,1], and x ∈ X, there exists δ > 0 such that for all f ∈H we have
C`1(f,x, η) < C∗`1,H(x, η) + δ Ô⇒ C`2(f,x, η) < C ∗ `2,H(x, η) + . (5)
Steinwart (2007) points out that if `1 is H-calibrated wrt `2, then H-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 a hypothesis set H, we define the calibration function δmax for a pair of losses (`1, `2) as follows: for all x ∈ X, η ∈ [0,1] and > 0,
δmax( ,x, η) = inf f∈H {C`1(f,x, η) − C∗`1,H(x, η) ∣ C`2(f,x, η) − C ∗ `2,H(x, η) ≥ } . (6)
For any x ∈ X, η ∈ [0,1] and > 0, the calibration function gives the maximal δ 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 `1 is H-calibrated with respect to `2 if and only if its calibration function δmax satisfies δmax( ,x, η) > 0 for all x ∈ X, η ∈ [0,1] and > 0.
Since the concepts of calibration and consistency may not be familiar to readers without an extensive background in this area, we further comment on these notions before presenting our main results. Informally, a loss function is H-consistent if minimizing it results in a classifier whose generalization error is close to the minimal generalization error within H. Similarly, a loss function is H-calibrated if minimizing it results in a classifier whose inner `2-risk is close to the minimal inner `2-risk within H for each x ∈ X. H-calibration (5) is a necessary condition for H-consistency (3), but is not always sufficient. As an example, we show in Section 5.1 that H-calibrated surrogate losses proposed in (Bao et al., 2020) are not H-consistent. For this reason, H-consistency, that is consistency for a 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 et 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-consistency 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.

heading: 3 Adversarially Robust Classification
text: In adversarially robust classification, the loss at (x, y) is measured in terms of the worst loss incurred over an adversarial perturbation of x within a ball of a certain radius in a norm. For simplicity, we will consider perturbations in the l2 norm ∥ ⋅ ∥.1 We will denote by γ the maximum magnitude of the allowed perturbations. Given γ > 0, a data point (x, y), a function f ∈H, and a margin-based loss φ∶R→ R+, we define the adversarial loss of f at (x, y) as
φ̃(f,x, y) = sup x′∶∥x−x′∥≤γ
φ(yf(x′)). (7)
The above naturally motivates supremum-based surrogate losses that are commonly used to optimize the adversarial 0/1 loss (Goodfellow et al., 2014; Madry et al., 2017; Shafahi et al., 2019; Wong et al.,
1Our analysis in the paper can be extended directly to other perturbations such as the l1 ball or l∞ ball, and in fact for any lp norm for p ∈ [1,∞]. 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 l2 and work for other norms too.
2020). We say that a surrogate loss φ̃(f,x, y) is supremum-based if it is of the form defined in (7). We say that the supremum-based surrogate is convex if the function φ in (7) is convex. When φ is non-increasing, the following equality holds (Yin et al., 2019):
sup x′∶∥x−x′∥≤γ φ(yf(x′)) = φ( inf x′∶∥x−x′∥≤γ yf(x′)). (8)
The adversarial 0/1 loss defined in (2) is a special case of (7), where φ is the 0/1 loss, that is, φ(yf(x)) = `0(f,x, y) = 1yf(x)≤0. Therefore, the adversarial 0/1 loss has the equivalent form
`γ(f,x, y) = sup x′∶∥x−x′∥≤γ 1yf(x′)≤0 = 1 inf x′ ∶∥x−x′∥≤γ yf(x′)≤0. (9)
This alternative equivalent form of adversarial 0/1 loss is more advantageous to analyze than (2) and would be adopted in our proofs. Without loss of generality, let X = Bd2(1) and γ ∈ (0,1). In this paper, we aim to characterize surrogate losses `1 satisfying H-consistency (3) and H-calibration (5) with `2 = `γ and for the hypothesis sets H which are regular for adversarial calibration. Definition 5 (Regularity for Adversarial Calibration). We say that a hypothesis set H is regular for adversarial calibration if there exists a distinguishing x in X, that is if there exist f, g ∈H such that inf∥x′−x∥≤γ f(x′) > 0 and sup∥x′−x∥≤γ g(x′) < 0.
When studying H-calibration of surrogate losses, it 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 for the proof.) We say that a hypothesis set H is symmetric, if for any f ∈H, −f is also in H. Theorem 6. Let H be a symmetric hypothesis set. If H is not regular for adversarial calibration, then any surrogate loss ` is H-calibrated with respect to `γ .
Moreover, we specifically study the following hypothesis sets that are regular for adversarial calibration: linear models: Hlin = {x→w ⋅ x ∣ ∥w∥ = 1}, as in (Bao et al., 2020); generalized linear models: Hg = {x→ g(w ⋅ x) + b ∣ ∥w∥ = 1, ∣b∣ ≤ G} where g is a non-decreasing function; the family of all measurable functions: Hall; and multi-layer neural networks: HNN = {x→ u ⋅ ρn(Wn(⋯ρ2(W2ρ1(W1x + b1) + b2)⋯) + bn) ∣ ∥u∥1 ≤ Λ, ∥Wj∥ ≤W, ∥bj∥1 ≤ B}, where ρj is an activation function; In the special case of g = (⋅)+ = max(⋅,0), we denote the corresponding ReLU-based hypothesis set by Hrelu = {x→ (w ⋅ x)+ + b ∣ ∥w∥ = 1, ∣b∣ ≤ G}.
4 H-Calibration
Calibration is a condition that often guarantees consistency and is a 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.

heading: 4.1 Negative results: convex losses
text: 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 x0 ∈ X and f0 ∈ H such that f0(x0) = 0. If a margin-based loss φ∶R→ R+ is convex, then it is not H-calibrated with respect to `γ .

heading: In particular, the assumption holds when H is regular for adversarial calibration and contains 0. By
text: 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 Hlin, HNN and Hall all satisfy there exists a distinguishing x0 ∈ X and f0 ∈ H such that f0(x0) = 0. When g(−γ) +G > 0 and g(γ) −G < 0, Hg also satisfies this assumption. Verifying this condition on Hg is straightforward for G sufficiently large.
Corollary 8. If a margin-based loss φ∶R→ R+ is convex, then φ is not H-calibrated with respect to `γ , for H =Hlin, Hg with a non-decreasing and continuous function g such that g(−γ) +G > 0 and g(γ) −G < 0, Hrelu with G > γ, HNN, and Hall.
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.

heading: 4.2 Negative results: supremum-based convex losses
text: We study losses of the type φ̃(f,x, y) = supx′∶∥x−x′∥≤γ φ(yf(x′)), with φ convex, which are often used in practice as surrogates for the adversarial 0/1 loss. The following theorems presents negative results for supremum-based 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 φ̃(f,x, y) = supx′∶∥x−x′∥≤γ φ(yf(x′)). Then φ̃ is not H-calibrated with respect to `γ , for H = Hlin, Hg with a non-decreasing and continuous function g such that g(−γ) +G > 0 and g(γ) −G < 0, and Hrelu with G > γ. Theorem 10. Let H be a hypothesis set containing 0 that is regular for adversarial calibration. If a margin-based loss φ is convex and non-increasing, then the surrogate loss defined by φ̃(f,x, y) = supx′∶∥x−x′∥≤γ φ(yf(x′)) is not H-calibrated with respect to `γ .
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-consistent surrogates could lead to undesirable solutions even under strong assumptions (such as the Bayes risk being zero). See Section 6, where we empirically demonstrate this in a variety of settings. By Theorem 10 and the fact that HNN and Hall both contain 0 and are regular for adversarial calibration, we can derive the following corollary. Corollary 11. Let φ be a convex and non-increasing margin-based loss. Consider the surrogate loss defined by φ̃(f,x, y) = supx′∶∥x−x′∥≤γ φ(yf(x′)). Then φ̃ is not H-calibrated with respect to `γ , 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 δmax( ,x, η) as defined in (6) of losses (`, `γ) at η = 12 , = 1 2
and distinguishing x0 ∈ X. Naturally, this requires us to understand the inner risk C`(f,x, η) that in turn depends on the worst case perturbation of a given data point according to `. Our key insight (Lemma 25) is that δmax( ,x0, η) can be characterized by two quantities M(f,x0, γ) = infx′∶∥x0−x′∥≤γ f(x′), M(f,x0, γ) = supx′∶∥x0−x′∥≤γ f(x
′). Requiring δmax( 12 ,x0, 1 2 ) > 0 corresponds to an appropriate convex function not achieving a minimum in a set that has global optimum, thereby reaching a contradiction.

heading: 4.3 Positive results
text: In this section, we aim to provide alternative losses which could be calibrated with respect to `γ .

heading: 4.3.1 Characterization
text: 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 φ-risk C̄φ(t, η) is quasi-concave in t ∈ R for all η ∈ [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 a margin-based loss φ be bounded, continuous, non-increasing, and satisfy the property that C̄φ(t, η) is quasi-concave in t ∈ R for all η ∈ [0,1]. Assume that φ(−t) > φ(t) for any γ < t ≤ 1. Then φ is Hlin-calibrated with respect to `γ if and only if for any γ < t ≤ 1,
φ(γ) + φ(−γ) > φ(t) + φ(−t) . (10)
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 11 in (Bao et al., 2020) does not hold any more under the correct calibration Definition 2, since their condition φ(γ) + φ(−γ) > φ(1) + φ(−1) is much weaker than (10). The following theorem extends the above to 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 + γ) < G and g(−1 − γ) > −G for some G ≥ 0. Let a margin-based loss φ be bounded, continuous, non-increasing, and satisfy the property that C̄φ(t, η) is quasi-concave in t ∈ R for all η ∈ [0,1]. Assume that φ(g(−t) −G) > φ(G − g(−t)) and g(−t) + g(t) ≥ 0 for any 0 ≤ t ≤ 1. Then φ is Hg-calibrated with respect to `γ if and only if for any 0 ≤ t ≤ 1,
φ(G − g(−t)) + φ(g(−t) −G) = φ(g(t) +G) + φ(−g(t) −G) and min{φ(A(t)) + φ(−A(t)), φ(A(t)) + φ(−A(t))} > φ(G − g(−t)) + φ(g(−t) −G),
where A(t) = maxs∈[−t,t] g(s) − g(s − γ) and A(t) = mins∈[−t,t] g(s) − g(s + γ).
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 a margin-based loss φ be bounded, continuous, nonincreasing, and satisfy the property that C̄φ(t, η) is quasi-concave in t ∈ R for all η ∈ [0,1]. Assume that φ(−G) > φ(G). Then φ is Hrelu-calibrated with respect to `γ if and only if for any 0 ≤ t ≤ 1,
φ(G) + φ(−G) = φ(t +G) + φ(−t −G) and φ(γ) + φ(−γ) > φ(G) + φ(−G).

heading: 4.3.2 Calibration
text: To demonstrate the applicability of Theorem 13, we consider a specific surrogate loss namely the ρ-margin loss φρ(t) ∶= min{1,max{0,1 − tρ}}, ρ > 0, 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′∶∥x−x′∥≤γ φρ(yf(x′)). Using Theorem 12, Theorem 13 and Corollary 14 in Section 4.3.1, we can conclude that the ρ-margin loss is calibrated under reasonable conditions for linear hypothesis sets and non-decreasing g-based hypothesis sets, since φρ(t) is bounded, continuous, non-increasing, and satisfies C̄φρ(t, η) is quasi-concave in t ∈ R for all η ∈ [0,1]. This is stated formally below. Theorem 15. The surrogate φρ is Hlin-calibrated with respect to `γ if and only if ρ > γ. Given a non-decreasing and continuous function g such that g(1+γ) < G and g(−1−γ) > −G for someG ≥ 0, assume that g(−t)+g(t) ≥ 0 for any 0 ≤ t ≤ 1, then φρ is Hg-calibrated with respect to `γ if and only if for any 0 ≤ t ≤ 1, φρ(G−g(−t)) = φρ(g(t)+G) and min{φρ(A(t)), φρ(−A(t))} > φρ(G−g(−t)), where A(t) = maxs∈[−t,t] g(s) − g(s − γ) and A(t) = mins∈[−t,t] g(s) − g(s + γ). Assume that G > 1 + γ, then φρ is Hrelu-calibrated with respect to `γ if and only if G ≥ ρ > γ.
Recall that in Theorem 10 we ruled out the possibility of finding H-calibrated supremum-based convex surrogate losses with respect to the adversarial 0/1 loss. However, we show that the supremum-based ρ-margin loss is indeed H-calibrated, where H is any symmetric hypothesis set.
Theorem 16. Let H be a symmetric hypothesis set, then φ̃ρ is H-calibrated with respect to `γ .
The proof of Theorem 16 is included in Appendix E.4. By Theorem 16 and the fact that Hlin, HNN and Hall are all symmetric, we derive the following.
Corollary 17. φ̃ρ is H-calibrated with respect to `γ , for H =Hlin, HNN, and Hall.
The results of this section suggest that the ρ-margin loss and supremum-based ρ-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 as well.
5 H-Consistency
In this section, we study the H-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, H-calibrated losses, such as the ρ-margin loss and supremum-based ρ-margin loss present an intriguing possibility. Bao et al. (2020) made a claim that since the losses they proposed are Hlin-calibrated they are also Hlin-consistent. We first present a result that implies this claim is incorrect. In fact, our result stated below shows that without assumptions on the data distribution, no continuous margin based loss or a supremum-based continuous surrogate could be Hlin-consistent.

heading: 5.1 Negative results
text: Theorem 18. No continuous margin-based loss function φ is Hlin-consistent with respect to `γ . Furthermore, for any continuous and non-increasing margin-based loss φ, surrogates of the form
φ̃(f,x, y) = sup x′∶∥x−x′∥≤γ
φ(yf(x′))
are not Hlin-consistent with respect to `γ .
The above theorem is proven in Appendix E.6. In particular, Theorem 18 contradicts the Hconsistency claim of Bao et al. (2020) for their proposed losses when H is the family of linear functions. Furthermore, the theorem rules out H-consistency of supremum-based surrogates.

heading: 5.2 Positive results
text: In this section, we investigate the nature of the assumptions on the data distributions that may lead to H-consistency of surrogate losses. We take inspiration from the work of Long and Servedio (2013) and Zhang and Agarwal (2020) who study H-consistency for the standard 0/1 loss. These studies establish consistency under a realizability assumption on the data distribution stated below that requires the Bayes (`0, H)-risk to be zero. Definition 19 (H-realizability). A distribution P over X × Y is H-realizable if it labels points according to a deterministic model in H, i.e., if ∃f ∈H such that P(x,y)∼P(sgn(f(x)) = y) = 1.
As with H-realizability, we will assume that, under the data distribution, the Bayes (`γ , H)-risk is zero. We show that the H-calibrated losses studied in previous sections are H-consistent under natural conditions along with the realizability assumption.

heading: 5.2.1 Non-supremum-based surrogates
text: Theorem 20. Let P be a distribution over X × Y and H a hypothesis set for whichR∗`γ ,H = 0. Let φ be a margin-based loss. If for η ≥ 0, there exists f∗ ∈H ⊂Hall such thatRφ(f∗) ≤R∗φ,Hall+η < +∞ and φ is H-calibrated with respect to `γ , then for all > 0 there exists δ > 0 such that for all f ∈H,
Rφ(f) + η <R∗φ,H + δ Ô⇒ R`γ (f) <R∗`γ ,H + .
For the family of linear models, some convex losses may also be Hlin-consistent verifying the conditions (η = 0) in Theorem 20. However, Hlin-calibrated losses can be Hlin-consistent under more benign assumptions, where the realizability conditionR∗`γ ,Hlin = 0 can be further relaxed. Theorem 21. Let P be a distribution over X × Y. Assume that there exists g∗ ∈ Hlin such that R`γ (g∗) = R∗`γ ,Hall . Let φ be a margin-based loss. If for η ≥ 0, there exists f
∗ ∈Hlin ⊂Hall such thatRφ(f∗) ≤R∗φ,Hall + η < +∞ and φ is Hlin-calibrated with respect to `γ , then for all > 0 there exists δ > 0 such that for all f ∈Hlin we have
Rφ(f) + η <R∗φ,Hlin + δ Ô⇒ R`γ (f) <R ∗ `γ ,Hlin + .
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 ρ-margin loss is consistent with respect to `γ for all distributions that satisfy our realizability assumptions.
Theorem 22. If ρ > γ, then φρ is Hlin-consistent wrt `γ for all distributions such that there exists g∗ ∈ Hlin with R`γ (g∗) = R∗`γ ,Hall and there exists f
∗ ∈ Hlin such that Rφρ(f∗) = R∗φρ,Hall . If g verifies the calibration condition in Theorem 15, then φρ is Hg-consistent wrt `γ for all distribution P over X ×Y that satisfiesR∗`γ ,Hg = 0 and there exists f
∗ ∈Hg such thatRφρ(f∗) =R∗φρ,Hall . If G > 1 + γ and G ≥ ρ > γ, then φρ is Hrelu-consistent wrt `γ for all distribution P over X × Y that satisfiesR∗`γ ,Hrelu = 0 and there exists f ∗ ∈Hrelu such thatRφρ(f∗) =R∗φρ,Hall .

heading: 5.2.2 Supremum-based surrogates
text: We can also extend the above to obtain H-consistency of supremum-based convex surrogates. However we need the stronger condition thatRφ is minimized exactly inside H. Theorem 23. Given a distribution P over X×Y and a hypothesis set H such thatR∗`γ ,H = 0. Let φ be a non-increasing margin-based loss. If there exists f∗ ∈H ⊂Hall such thatRφ(f∗) =R∗φ,Hall < +∞ and φ̃(f,x, y) = supx′∶∥x−x′∥≤γ φ(yf(x′)) is H-calibrated with respect to `γ , then for all > 0 there exists δ > 0 such that for all f ∈H we have
Rφ̃(f) <R ∗ φ̃,H + δ Ô⇒ R`γ (f) <R∗`γ ,H + .
The proof of Theorem 23 is presented in Appendix E.7. Again, when combined with Theorem 16 in Section 4.3.2 we conclude that the H-calibrated supremum-based ρ-margin loss is also H-consistent with respect to `γ for all distributions that satisfy our realizability assumptions.
Theorem 24. Let H be a symmetric hypothesis set, then φ̃ρ is H-consistent with respect to `γ for all distributions P over X × Y that satisfy: R∗`γ ,H = 0 and there exists f
∗ ∈ H such that Rφρ(f∗) =R∗φρ,Hall < +∞.

heading: 6 Experiments
text: Here, we present experiments on simulated data to support our theoretical findings. The goal is two-fold. First, we empirically demonstrate that indeed H-calibrated surrogates in (Bao et al., 2020) may not be H-consistent unless assumptions on the data distribution are made, even when H is 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 et al., 2020). Second, we study the necessity of the realizability assumptions we adopted in Section 5.2 to establish H-consistency of surrogates satisfying the conditions in Theorem 12.
We generate data points x ∈ R2 on the unit circle and consider H to be linear models Hlin. We denote f(x) = w ⋅ x, w = (cos(t), sin(t))⊺, t ∈ [0,2π), f ∈ Hlin. All risks are approximated by their empirical counterparts computed over 107 i.i.d. samples. To demonstrate the need for some assumptions for H-consistency, we construct a scenario we call the Unit Circle case. We consider four surrogates: φhinge, φramp, φsig and φlog defined in Appendix C.1. 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 as x = (cos(θ), sin(θ))⊺, θ ∈ [0,2π). Set the label of a point x as follows: if θ ∈ (π
2 , π), then y = −1 with probability 3 4 and y = 1 with probability 1 4 ; if θ ∈ (0, π 2 ) or ( 3π 2 ,2π),
then y = 1; if θ ∈ (π, 3π 2 ), then y = −1. Set γ =
√ 2
2 . In this case, the Bayes (`γ , Hlin)-risk is
R∗`γ ,Hlin ≈ 0.5000 ≠ 0 and is achieved by w`γ = (cos(θ), sin(θ)) ⊺ with θ ≈ 0.7855. The results obtained by optimizing the different surrogate losses are reported in Table 1(a) and the plots for
1,000 samples and 2,000 samples are shown in Figure 2. Table 1(a) shows that neither calibrated nor non-calibrated (convex) surrogates are Hlin-consistent 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 `γ . 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 H-consistency of surrogate losses. To do so, we design a 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.1. The loss φ1 is a convex loss and φ2 is the ρ-margin ramp loss for some ρ > γ. In general, we refer to all of these surrogates as φsur. We show in Appendix C.2 that φhinge, φlog and φ1 are not Hlin-calibrated while φramp, φsig and φ2 are Hlin-calibrated with respect to `γ . Let Iγ̂ = √ 1 − γ̂2 and consider: P(Y = 1) = P(Y = −1) = 1 2
, and X ∣ Y = 1 is the uniform distribution on the line segment {(γ̂, z) ∣ z ∈ [0, Iγ̂]} and X ∣ Y = −1 is the uniform distribution on the line segment {(−γ̂, z) ∣ z ∈ [−Iγ̂ ,0]} where γ̂ = γ + 1−γ100 = 1+99γ 100
, γ ∈ (0,1). We choose γ = 0.1 and set w∗ = (1,0)⊺. It is easy to check that w∗ achieves the Bayes (`γ , Hlin)-risk R∗`γ ,Hlin = 0. 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 φhinge, φramp, φsig and φlog, the Bayes (φsur, Hlin)-risk R∗φsur,Hlin ≠ 0. Table 1(b) shows that they are not Hlin-consistent with respect to `γ .
For φ1 and φ2, the Bayes (φsur, Hlin)-riskR∗φsur,Hlin = 0. Table 1(b) shows that φ1 is not Hlin-consistent (recall that φ1 is not calibrated) but φ2 is Hlin-consistent for this distribution. Hence, even when R∗`γ ,Hlin = 0, unless a condition is also imposed onR ∗ φsur,Hlin
, one cannot expect consistency, thereby justifying our realizability assumption. Note that R∗φsur,Hlin = R ∗ `γ ,Hlin
= 0 is a special case verifying the conditions of Theorem 20 for η = 0. For this distribution, φramp is not Hlin-consistent while φ2 is Hlin-consistent, although both are Hlin-calibrated. We compare them in Figure 3, showing that minimizing Hlin-consistent surrogate φ2 minimizes
the adversarial generalization error for large sample sizes but the same does not hold for non Hlinconsistent surrogate φramp.

heading: 7 Conclusion
text: 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 do not guarantee consistency. Instead, we give a series of positive calibration and consistency results for several families of surrogate functions, under some realizability assumptions.

heading: Acknowledgements
text: This work was partly funded by NSF CCF-1535987 and NSF IIS-1618662.

Review summaries:
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. 

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.

This paper provides a detailed analysis on the H-calibration and H-consistency of adversarial surrogate losses.   It shows that some common used losses for adversarial training are not H-calibrated.    Some theoretical results on the characterization of H-calibration are established.  The paper also proves that some surrogate losses are indeed H-calibrated.  Some additional theoretical results on H-consistency are established too.  

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.