Realizable $H$-Consistent and Bayes-Consistent Loss Functions for Learning to Defer
Authors: Anqi Mao
Mehryar Mohri
Yutao Zhong
Venue: NeurIPS 2024 poster (2024)
Keywords: learning to defer
consistency
realizable H-consistency
learning theory
Primary area: learning_theory

Abstract: We present a comprehensive study of surrogate loss functions for learning to defer. We introduce a broad family of surrogate losses, parameterized by a non-increasing function $\Psi$, and establish their realizable $H$-consistency under mild conditions. For cost functions based on classification error, we further show that these losses admit $H$-consistency bounds when the hypothesis set is symmetric and complete, a property satisfied by common neural network and linear function hypothesis sets. Our results also resolve an open question raised in previous work [Mozannar et al., 2023] by proving the realizable $H$-consistency and Bayes-consistency of a specific surrogate loss. Furthermore, we identify choices of $\Psi$ that lead to $H$-consistent surrogate losses for *any general cost function*, thus achieving Bayes-consistency, realizable $H$-consistency, and $H$-consistency bounds *simultaneously*. We also investigate the relationship between $H$-consistency bounds and realizable $H$-consistency in learning to defer, highlighting key differences from standard classification. Finally, we empirically evaluate our proposed surrogate losses and compare them with existing baselines.

Realizable H-Connsitentt and Bayes-Consistent Loss Functions for Learning to Defer
Anqi Mao Courant Institute New York, NY 10012 aqmao@cims.co .yy..n.eee. edu
Mehryar Mohri Google Research & CIMS New York, NY 10011 mohri@google.com
Yutao Zhong
Courant Institute
New York, NY 10012 yutaoucims nyu edu
Abstract
We present comprehensive study of surrogate loss functions for learning defer. We introduce a broad family of surrogate losses, parameterized by a non-increasing function V and establish their realizable HC-consistency under mild conditions. For cost functions based on classification error, we further show that these loss functions admit K-consistency bounds when the hypothesis set is symmetric and complete, a property satisfied by common neural network and linear function hypothesis sets. Our results also resolve an open question raised in previous work [Mozannar et al., 2023] by proving the realizable JCCconnsstynccy and Bayes-consistent specific surrogate loss. Furthermore. we identify choices of v that lead H--conistentt surrogate losses for any general cost function, thus achieving Bayes- consistency, realizable H-cooniitenncy, and H-consistenccy bounds simultaneously. We also investigate the relationship between H--consistency bounds and realizable H--conistencyy learning to defer, highlighting key differences from standard classification. Finally, we empirically evaluate our proposed surrogate losses and compare them with existing baselines.
of
Introduction
In many practical scenarios, combining expert insights with established models can yield significant enhancements. These experts can be human domain specialists or more complex, albeit resource- intensive, models. For example, modern language and dialogue models are prone to producing hallucinations or inaccurate information. The quality of their responses can be significantly enhanced by delegating uncertain predictions more specialized or advanced pre-trained models. This problem is particularly crucial for large language models (LLMs), as noted in [Wei et al., 2022, Bubeck et al., 2023]. The same principle applies to other generative systems, like those for images or videos, and to learning models in diverse applications such as image classification, annotation, and speech recognition. Thus, the task of learning to defer (L2D) with experts has become increasingly critical across a wide array of applications.
Directly optimizing the deferral loss function, which is the target loss in L2D, is computationally intractable for many choices of the hypothesis set. Therefore, a common approach is to optimize surrogate loss that facilitates the optimization of the deferral loss function. Recent work in L2D has proposed several surrogate losses [Mozannar and Sontag, 2020, Verma and Nalisnick, 2022, Mozannar et al., 2023, Mao et al., 2024a] and studied their consistency guarantees, including Bayes-consistency, realizable K-consistency, and K--consistnncy bounds (see definitions in Section 3.2). In particular, Mozannar and Sontag [2020] proposed the first Bayes-consistent surrogate loss by generalizing the cross-entropy loss for L2D. Verma and Nalisnick [2022] proposed alternative Bayes-consistent surrogate loss by generalizing the one-versus-all loss for L2D. Mozannar et al. [2023] showed that these surrogate losses are not realizable HC-consistent. They proposed alternative surrogate loss
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

that is realizable JC-oonsistnt, but they were unable to prove or disprove whether the proposed surrogate loss is Bayes-consistent. All the surrogate losses mentioned above and their consistency guarantees hold only for cost functions based on classification error. Mao et al. [2024a] generalized the surrogate loss in [Mozannar and Sontag, 2020] to incorporate general cost functions and any multi-class surrogate losses. They provided H-coosistency bounds for the novel family of surrogate losses, offering a stronger guarantee than Bayes-consisteney.
However, none of these surrogate losses satisfies all these guarantees simultancously. In particular, a recent AISTATS notable award paper by Mozannar al. [2023] left open the problem of finding surrogate losses that are both coyessccosistent and realizable HC-consistent when the cost function for the expert is its classification error. The problem becomes even more challenging when considering more general and realistic cost functions.
We present a comprehensive analysis of surrogate loss functions for L.2.. Our contributions address the limitations of previous approaches and provide a unified framework for designing surrogate losses with strong theoretical guarantees. In Section 4, we first introduce a broad family of surrogate losses for L2D, derived from first principles (Section 4.1). This family is parameterized by a non-increasing function Vr, which provides some flexibility in tailoring the loss function specific requirements. We establish that under mild conditions on V these surrogate losses achieve realizable HH-consistency, a key guarantee for many applications (Section 4.2).
Next, for cost functions based on classification error, we further establish that our surrogate loss func- tions admit HH-consistency bounds when the hypothesis set is symmetric and complete (Section 4.3). This result holds for commonly used neural network and linear function hypothesis sets, further strengthening the applicability of our results. Additionally, our results resolve an open question raised by Mozannar et al. [2023] by proving the realizable H--consistency and Bayes-consistency of their proposed surrogate loss, which the authors had left as an open question (Section 4.4).
In Section 4.3, we further identify specific choices of V, such as the one corresponding to the mean absolute error loss, that lead to H-consistent surrogate losses for any general cost function. These loss functions are adapted to general cost functions and benefit from canesscconistency (Section 4.4), realizable CC-coniis,,ncy, and H-coosistency bounds simultaneously.
In Section 5, we also study the relationship between K-consistency bounds and realizable H- consistency in the context of L,D,, highlighting key distinctions from the standard classification setting. Finally, we further report the results of experiments with our new surrogate losses and their comparison with the baselines in different settings (Section 6).
We discuss the related work in Section 2 and then begin with the preliminaries in Section 3.
2 Related work
The approach of single-stage learning to defer, where a predictor and a deferral function are trained together, was pioneered by Cortes, DeSalvo, and Mohri [2016a,b, 2023] and further developed in subsequent studies on abstention, where the cost is constant [Charoenphakdee et al., 2021, Cao et al., 2022, Li et al., 2023, Cheng et al., 2023, Mao et al., 2024c.b, Mohri et al., 2024] and on deferral, where the cost can vary depending on the instance and the label [Mozannar and Sontag, 2020, Verma and Nalisnick, 2022, Mozannar et al., 2023, Verma al., 2023, Cao al., 2023, Mao et al., 2023a, 2024a]. In this approach, the deferral function determines whether to defer to an expert for each input. This approach has been shown to be superior to confidence-bused approaches, where the decision to abstain or defer is based solely on the magnitude of the predictor's 's value [Chow, 1957, 1970, Bartlett and Wegkamp, 2008 Yuan and Wegkamp, 2010, 2011, Ramaswamy et al., 2018, Ni et al., 2019, Jitkrittum al., 2023]: and to selective classification approaches, where the selection rate is fixed and a cost function modeled by an expert cannot be taken into account [EI- Yaniy et al., 2010, El-Yami -a-ya and Wiener, 2012, Wiener and El-yaniv, 2011 1, 2012, 2015, Geifman and El-yaniv, 2017, 2019, Acar et al., 2020, Gangrade et al., 2021, Zaoui et al., 2020, Jiang et al., 2020, Shah et al., 2022].
Madras et al. [2018] initiated the learning to defer (L2D) problem scenario, which integrates human expert decisions into the cost function. This approach has been further explored in subsequent studies [Raghu et al., 2019, Wilder et al., 2021, Pradier et al., 2021]. Mozannar and Sontag [2020] introduced the first Bayes-consistent surrogate loss for I.2D, which was further refined in [Raman and Yee, 2021, Liu et al., 2022]. Verma and Nalisnick [2022] proposed alternative Bayss-consistent surrogate loss,
2

---

the one-versus-all loss, which was later examined within a broader family of loss functions [Charusaie al., 2022]. Cao et al. [2023] proposed an asymmetric softmax function, which can induce valid probability estimator for learning to defer. Mozannar et al. [2023] showed that the surrogate losses in [Mozannar and Sontag, 2020, Verma and Nalisnick, 2022] are not realizable H-consistent. They proposed an alternative surrogate loss that is realizable HH-consistent, but they were unable to prove or disprove whether the proposed surrogate loss is Bayes-consistent. All the surrogate losses mentioned above and their consistency guarantees hold only for cost functions based on classification error. Mao et al. [2024a] generalized the surrogate loss in [Mozannar and Sontag, 2020] to incorporate general cost functions and any multi-class surrogate losses. They provided H-coosiisenccy bounds for the novel family of surrogate losses, offering a stronger guarantee than Bayes-consistency.
Additional studies have focused on post-hoc methods, with Okati et al. [2021] suggesting an alternative optimization technique between the predictor and rejector, and Narasimhan et al. [2022] offering corrections for underfitting surrogate losses [Liu et al., 2024], and Charusaie and Samadi [2024] providing unifying post-processing framework for multi-ohjective L.2D based on generalization of the Neyman-Pearson Lemma [Neyman and Pearson, 1933]. The L2D framework thereof have found applications in diverse scenarios, spanning regression, reinforcement learning, and human-in-the-loop systems, among others [De et al., 2020, 2021, Straitouri et al., 2021, 1, Zhao et al., 2021, Joshi et al., 2021, Gao et al., 2021, Mozannar et al.. 2022, Hemmer et al., 2023, Chen et al., 2024, Palomba et al., 2024]. More recently, the problem of learning defer with multiple experts has been analyzed in several publications [Hemmer et al., 2022, Keswani et al., 2021, Kerrigan et al., 2021, Straitouri et al., 2022, Benz and Rodriguez, 2022, Verma et al., 2023, Mao et al., 2023a, 2024a.g. Tailor et al., 2024]. Meanwhile, Mao et al. [2023a] also proposed a two-stage learning to defer framework. They introduced two-stage surrogate losses that are both Bayes-consistent and realizable H-conssstentt with constant costs. However, realizable J-cconiity does not hold for cost functions based on classification error. As with [Mozannar and Sontag, 2020, Verma and Nalisnick, 2022, Mozannar et al., 2023], our work focuses on the single-stage and single-expert setting, and we plan to explore similar approach in a multi-expert/woo-ttage setting in the future.
variations
3 Preliminaries
We start with the definitions and notations used in the learning-to- -t-eerr scenario considered in this paper. We will then introduce consistency guarantees, including Bayes consistency. Realizable HC-consistency, and K-cconsisenncy bounds. Finally, we will review existing consistent surrogate losses for L2D.
3.1 Learning to defer: problem setup
Let X be input space and y [n] (1...., n) be the label space in the standard multi-class classification setting. We study the learning to defer (L.D) scenario, where a learner can either predict a label from or defer to an expert.
To model this, we introduce an augmented label space y = (1..... n. + 1 corresponds to deferral. An expert is fixed predictor g: x y R. The goal of L2D to select predictor out of a hypothesis set H of functions mapping from X x to with small expected deferral loss. Let h(x) denote the prediction of h on input x E X, defined as h(x) argmax,eey h(x,z) y), that is the label in the augmented label space y with the highest score, with arbitrary but fixed deterministic strategy for breaking ties. Then, the deferral loss function
1}, where the label
Laer is defined as follows:
V(, v) x Laer(h, x. y) = In(z)ay + c(x, y) In()==++1
where c(x,y) is the the cost of deferring on input x with true label y. If the deferral option is selected, that is h(x)= + 1, the deferral cost c(x, y) is incurred. Otherwise, the prediction of h. is within the standard label space, h(z) [m]. and the loss incurred coincides with the standard zero-one classification loss, In(=)=y*
The choice of the cost function c is flexible. For example, the cost can be defined as the expert's s classification enror: v(r.y)= lg(=))ay as in previous work [Mozannar and Sontag, 2020, Verma and Nalisnick, 2022, Mozannar al., 2023]. Here, g(x) argmax g(x, y) is the prediction made by
3

---

the expert g. More generally, it can incorporate the inference cost for the expert [Mao et al., 2024a]: <(x,y y) al g(w)+y + 3, with a, 5 O. We assume, without loss of generality, that the cost bounded by I: 0 c(x,g) $ which can be achieved through normalization in practice.
3.2 Consistency guarantees
Directly optimizing the deferral loss function, which is the target loss in L2D, is generally computa- tionally intractable for complex hypothesis sets H. Therefore, common approach is to optimize a surrogate loss that facilitates the optimization of the deferral loss function. A natural learning guarantee for such surrogate losses is Bayes-consistency [Zhang, 2004a, Bartlett et al., 2006, Zhang, 2004b, Tewari and Bartlett, 2007, Steinwart, 2007]:
Definition 3.1 (Bayes-consistney)) A surrogate loss L is Bayes- Bayss-consistent with respect to Laef, minimizing the surrogate loss over the family of all measurable functions leads to the minimization of the deferral loss:
lim (hh))) Ei (Hal)) =0 n10+000
lim ELue (hn) Ei (Han) 0. n-++00
Here, given a distribution over X x and loss function L:H x X y TR we denote by & (h) the generalization error of a hypothesis h H. (L(h) (2 (.,, v)), and by (T() the best-in-class generalization error, & (TC) = infnem (h). Bayes-consistengs assumes that the optimization occurs over the family of all measurable functions, Hall However, in practice, the hypothesis set of interest is typically restricted one, such as family of neural networks. Therefore, a
learning guarantee, such as K-consistency bounds [Awasthi et al., 2022a,b] (see also [Awasthi et al., 2021 a,b, 2023, 2024, Mao et al., 2023b.e,f, Zheng et al., 2023, Mao et al., 2023c,d, 20,4h,e,d,f, Cortes et al., 2024]) and realizable H-consistency [Long and Servedio, 2013, Zhang and Agarwal, 2020], is more informative and relevant. Realizable H-consistency, defined as follows, requires that minimizer of the surrogate loss over the given hypothesis set also minimizes the target loss, provided that the underlying distribution is realizable.
Definition 3.2 (Realizable -f-connistencc). A surrogate loss is realizable HC-consistent with respect Ldef, if for any distribution over which there exists a predictor h* e H achieving zero deferral loss, EL (h*) = O, minimizing the surrogate loss also leads to zero-error solution:
h argmin (h) ELA (h) heM
Note that realizable K-connsstenccy does not imply Bayes- Bayes-consistency, even if we set H Kall in Definition 3.2, since Bayes-consistency requires that the relationship holds for all distributions, not just realizable ones. H-consistenccy bounds, Given a hypothesis set H. a surrogate loss L admits an H-consistency bound, if for some non- decreasing concave function R:R, R, with I(0)= 0, bound of the following form holds for any hypothesis h e HC and any distribution:
the other hand, always imply Bayes-consistengy
E (h) - Eia (H) + Ma (H) s (n) (9)) + (H)),
(1)
where ML M)( is the mininizability gap, defined as the difference between the best-in-class generaliza- tion error and the expected pointwise infimum loss: Mr (H) = & (3t) - Ee iinfserr [Lih,L(h,,,)) x, 3)]] The minimizability gap can be upper-bounded by the approximation eгror and vanishes when H- Han [Awasthi et al., 20.2a,b]. Thus, an --consistency bound implies Bayes-consistency The relationship between the two prppothssi--depndeee learning guarantees -eaaaizes-rralizallle H-consistency and H-consistency bounds-depends on the target loss adopted in the specific learning scenario. In Section 5, will demonstrate that in the standard multi-class classification setting, H-consistency bound is a stronger notion than realizable H-consistency. However, in I.2D, these guarantees do not imply one another.
3.3 Existing surrogate losses
Here, we will review several consistent surrogate losses used in L2D. For convenience, we use ((x,y) lg(m)ey denote the cost when it specifically represents the expert's classification error, and use c(z, y) when it represents general cost function.

---

Mozannar and Sontag [2020] proposed the first Bayes-consister surrogate loss by generalizing the cross-entropy loss for L2D, with cost functions based on classification error, which is defined
Eyee ch(x..rr) (1-7(z)))) )
((r.)))
I(an+1)
LcB x, log
log
Ever ey ch(
Verma and Nalisnick [2022] proposed alternative one-vs-all surrogates loss with cost functions based on expert's 's classification error, that is Bayes-consistent as well:
Lova (h, x,) = - (h(x,)))))))))))))))))))))))(()) Σ *(-h(z,))) (1- (() Mtt 1))] v'ey
y'+y
where & is a strictly proper binary composite loss [Reid and Williamson, 2010], such as the logistic loss t + log(11 e- Lcg and LOvA not realizable H-cconsistent. Instead, Mozannar al. [2023]
proposed the following loss function that is realizable H-consistent when H is closed under scaling:
Ma.y) + (1-7(x ((fx,y))e ye) Eyer chaas)
(hs xz g) -2
However, they were unable prove or disprove whether the surrogate loss Lns Bayes-consistent.
All the surrogate losses mentioned above and their consistency guarantees hold only for cost functions based on the classification error: a(2, y) [g(x)=g- Mao et al. [2024a] generalized the surrogate loss LCE to incorporate general cost functions and any multi-class surrogate losses:
Lgeneral (h, x, y) ( x, + (1 c(2, ()) x, n,
Here, is a Bayes-consisten surrogate loss for the multi-class zero-one loss over the augmented label set y. In particular, & can be chosen as a comp-sum loss [Mao et al., 2023f], for example, the generalized cross entropy loss (see Section 4.1). As shown by Mao et al. [2024a], Lgeneral benefits from H-coosistency bounds, which implies Bayes-consistency.
Novel surrogate losses
In this section, introduce new family of surrogate losses for L.2D that benefit from Bayes- consistency, realizable K-consistency and H--consistency bounds, starting from first principles.
4.1 Derivation from first principles
Observe that for any y1 X y, have In(=)=++1 1n(x) h())=n+1+ since h(x) implies h(z) y. Thus, using additionally In(z)e[u] l(())=++1 the deferral loss can be rewritten as follows for all (x,y) v) e X y:
= 4n(z))yy (n + c(x, ())
= !M))+ (n()ene1 + c(x, y) h(x)+ h(()===1 (h(o)ay-h(z))mn)) + c( , (n( (1- In(2)an=1)
=c(x,y) (1 c(x; 1 h()))
Next, we will derive the new surrogate losses for L2D by replacing the indicator functions in (2) with smooth loss functions. The first indicator function Is()ey is just the multi-class zero-one loss. Thus, natural choice is to replace with surrogate loss in standard multi-class classification. We will specifically consider the family of comp-sum losses [Mao et al., 2023f], defined as follows for any (h, y) e H. X y:
((z.w)
Ecomp 2h, v
Eyrgeh ch((.rr)
where v: [0.1] + R. (+00} is non-increasing function. For example, by taking (t() - log(t), (1 -1-+ with g 1), 1 obtain the logistic loss [Verhulst, 1838, 1845, Berkson, 1944,
5

---

Table 1: A new family of surrogate losses LRL2D for L2D.
(())
LRL2D
h(xa)) (eamw)) b(ana)) (
-Iog(t)
-c(x, 3)
log
(1 cx b)) log
} (9)
dx.yy)
-
e ch(z.)))
(--(Iry))
te
Ey chiarvy
9
Eveo cA(
1-1
dx, v)
cx 1))
EyeT
1951], the generalized cross entropy loss [Zhang and Sabuneu, 2018], and the mean absolute enror loss [Ghosh et al., 2017], respectively:
M(z,))
Logistic loss:
loo (h, -log
y'ey De ch(a-r)))
eh(()))))
787
Generalized cross entropy loss:
(h,
Eggey ch(wwrr)
Mean absolute error loss:
Emae (h,
Σ Ever Eyegeh(arr)) ch(xaar))
For any (h,,0, 2r y) e H. X x y. the confidence margin Ph (n( y) defined by Phi (2, y) = h(r, max, yeH,y'y h(z,3') Thus, the second indicator function [n(=))ynn(()))nt can be expressed as follows in terms of the confidence margin:
1 h(())))A(())=m=11 = (M(=.))smax,45.v (aa yon Ma./))
Note that the first indicator function can also be written in terms of margin: In(x)ev = pn(()))s
Unlike the first indicator function, which presses h(r,y) y) to be the largest score among y, that is the margin Ps (x. y) be positive, the second indicator function only enforces h(z, y) or h(x,n+ be the largest score among y, that is the maximum of two margins, max(Pn (x,y): PPh (I, n 1)}, to be positive. This condition
be further strengthened by requiring the sum of two margins, Pa (x. 3) + pk (x, + 1), to be positive. In view of this observation, we adopt the following modified comp-sum surrogate loss for the second indicator function:
Teomp (,)
Eyegehhass
where y: [B is a non-increasing function. In other words, Foomp replaces the term c/2,,) in the softmax function in leomp with the sum e( (zxm++1),, The effect is to encourage the sum the two margins, Ph (z( y) + Pa (x, n + 1). to be positive, rather than just the single margin Ps (x, v). Following this principle. derive the following expression for new family of surrogate losses, LRL2D, dubbed realizable L2D:
LRLaD 2r, 3) c(x, koom (h, x, v) (1 c(z, 3)) (omp (h,
For the choices of V(() log((), (1-(9) with g (0, and 1 I, we obtain the new surrogate losses for L.2D in Table 1. In the next sections, will prove both realizable K-consistency guarantees and HF-consistency bounds for this family of surrogate losses, which imply their excess error bounds and cayesteonsistency well.
4.2 Realizable F(-cnssistnncy
Here, we show that LRL2D realizable H-consistent with respect to Laef. We say that a hypothesis set DC is closed under scaling if, h e F[ ah H for any E R.

---

Theorem 4.1. Assume that 3 is closed under scaling. Suppose that V is non-inoneenn non-increasing, ((3) > 0 and lim (t) = 0. Then, the surrogate loss LRL2D is realizable HC-consistntt with respect to Ldef-
The proof. detailed in Appendix A, begins by establishing upper bound on the deferral loss in terms of the comp-sum loss: Ldef
LRL.D Letting h be the minimizer of LIL2D and a be any real
V v(+)
number, we then show that LLa (h) s ( ELauan (ah"). The generalization error is then split by
conditioning on whether h² (Ir) is the deferral class (n 1) or not. Finally, we demonstrate that each conditional term converges to zero as a tends to +00, and apply the monotone convergence theorem to complete the proof.
4.3 H-Connsisenccy bounds
Here, we show that LRL2D admits an H--consistnncy bound with respect to Ldefs which im- plies its Bayss-consistency as well. We say that a hypothesis set is symmetric if there exists family F of functions f mapping from X to R such that {[h(z, 1), .......,ha, ,,,,,, E EF), for any x é X. We say that a hypothesis set H is com- plete if for any (Ir X y, the set of scores generated by it spans across the real numbers: (M(x,y) y) h e H} = R. Common neural network and linear function hypothesis sets are all symmet- ric and complete. We first consider the case where the cost is expert's classification error.
1)]: h JC
fI........... (.) fn+1
Theorem 4.2. Assume that H is symmetric and complete and that cxx y) = 1g(())y Then, for all h H. and any distribution, the following K-consistency bound holds:
ELOo (h) ELent (3C) Ma (JC) T(ELataD (h) ELaxaD (H) MLnian (3():
where (()) = 28 when (t) = - log(() and [(t) = /2(n + 1)9t when (t) [ 19) with 10.
The proof, detailed in Appendix B.3 and B.4, establishes strong consistency guarantees for our new surrogate loss LRL2D (Theorem 4.2). We first introduce ymax argmax p(x, y). the label with the highest conditional probability. We then show that for any hypothesis h and input x. if Vmax is not the predicted label hmax, the conditional error of h is lower bounded by modified hypothesis (obtained by swapping the scores of ymax and hmax)) Next, for hypotheses where ymaa hmax. we lower bound their conditional regret in terms the conditional regret of the deferral loss using new hypothesis hy. This proof is novel and significantly different from existing approaches for establishing H-coonistenccy bounds in either the standard or deferral settings [Mao et al., 2023f, 2024a].
The next result further shows that when (1) =1 1-1,, our surrogate losses benefit from K-consistency bounds for any general cost function.
Theorem 4.3. Assume that H is symmetric and complete. Suppose that Tt =1 Then, for all he E H and any distribution, the following H-consistency bounds hold:
ELi (h) ELio (IC) + ML... (3() S (n + (n( (h)- ELLraD (H() + MLnian (3()).
The proof is included in Appendix B.2. Theorem 4.2 provides stronger consistency guarantees for our new surrogate loss LRL.2 with (() = 11 since it holds for any general cost function. The proof idea is similar that of Theorem 4.2, albeit with more cases analyze due the general cost function. This occurs when lower bounding the conditional regret of a hypothesis ht which satisfies Ymax hmax. in terms of the conditional regret of the deferral loss by introducing new hypothesis 1بh The additional cases necessitate a more stringent condition for the guarantee, such that the functions (t) log(t) and (t) (1 10-t% t²) do not apply.
4.4 Excess error bounds and Bayes-consistency
For the family of all measurable functions H. Halt. the minimizability gaps vanish. In this case, Theorems 4.2 and 4.3 imply the following excess error bounds and Bayes-consistency guarantees. Corollary 4.4. Suppose that c(x. y) Lg(e)+y> For all h E Han and any distribution, the following excess error bounds hold:
ELSe (h) ELast (Hal) S I'EERILD (h) ELRLOD (Han)))
7

---

Table 2: Consistency properties of existing surrogate losses and ours in the case of c( y) 1100=1g00 (z))=y
Surrogate losses
Realizable H-consistency
Bayes-consistency
H-consistency hounds
LCE
no no no LRL2D with (t) (1 e (0
yes
yes yes yes yes (proved by us)
LovA
yes yes
Legneral
Las (LRIED with (()) = (=t))=log())) -lo(()))
yes
yes (proved by us)
yes
yes
yes
LRLED with 1 (t) 1-t
yes
yes
yes 1)st when (t)
where [tt) = 2t when (t) - log(t) and 2 (0,1). Furthermore, the surrogate loss LRL.2 is Bayes-consistent with respect Låef in these cases.
( [() with
Corollary 4.5. Suppose that (+) = 1 For all h Hall and any distribution, the following excess ervor bounds hold:
LLai (h) - ELaes (Han s (n+ 1)(ELaun (h) ELREAD (Han))
Furthermore, the surrogate loss LRL2D Bayes-consistert with respect Ldef in this case.
Therefore, Theorem 4.1 and Corollary 4.4 show that LRlaD is both realizable H[coonsistent and Bayes-consistent with respect to Ldef- This solves the open problem raised by Mozannar et al. [2023].
In particular, for cost functions based on classification error, c(r,v) = <(#)+yy our surrogate loss LRL2D with (t) log(()) coincides with the surrogate loss LRS in [Mozannar et al., 2023], modulo a constant. This affirmatively answers the question of whether their surrogate loss is payes-consistent when c(2, y) = -g(=) However, their surrogate loss cannot be shown to be Bayes- covessconssstent for
a general cost function. In contrast, our surrogate losses LRL2D with (t) = 1 t are adaptable to general cost functions and benefit from both H--consistency bounds and realizable HC-oosssstnccy guarantees. We also provide a more general family of comp-sum loss functions with (t) = (1 19) that benefit from both H-consistency bounds and realizable K-coosistency when c(2,, y) 1g())=g)
4.5 Summary
Here, we summarize the consistency properties of existing surrogate losses and ours. As mentioned earlier, most surrogate losses proposed in previous work, except for Lggneral, analyzed under the condition c(x, 3) = =yy This naturally leads to a summary of these surrogate losses this context, presented in Table 1. Additionally, we provide analyses and the consistency properties of our surrogate loss, LRL2D. with general cost functions.
More specifically, our surrogate losses LRL2D satisfying Theorem 4.1 perform better in realizable scenarios than the surrogate losses LçF, LOVA. and Lgeneral from prior work, as ours are realizable H(- consistent while theirs are not. This will be illustrated by our experiment results in the realizable case (Figure la). Our surrogate losses LRL2D satisfying Theorem 4.2 and Corollary 4.4 are comparable to the surrogate losses in prior work in non-realizable scenarios when the cost is the expert's classification error, as all of them are Bayes-consistent and supported by H-consistency bounds. This is demonstrated by our experiment in the non-realizable case with the cost function being the expert's classification error (Table 3). Our surrogate losses LRL2D satisfying Theorem 4.3 and Corollary 4.5 superior to the surrogate loss LRs in non-realizable scenarios with general cost functions, are supported by H-consistency bounds and coysssccnn while theirs are not. This is evidenced by experiment in the non-realizable case with general cost functions (Figure 1b).
5 Relationship between H-consistency bounds and realizable K-consistency
Here, we discuss the relationship between H-cconsisenccy bounds and realizable K-consistency. First, realizable H-coosistencyy does not imply H--consistnncy bounds, since H-coosistency bounds require that the relationship holds for all distributions. not just realizable ones. Moreover, H--consistnncy bounds provide non-asymptotic guarantees, while realizable HH-consistnncy provides only asymptotic guarantees. Second, K-consistency bounds imply realizable H-cconissency in the standard multi-class classification setting. This is because minimizability gaps vanish under the realizable assumption in standard case. In particular, for comp-sum losses, the following holds (see Appendix C for proof).
8

---

Table 3: Comparison of system aceuracy, accepted accuracy and coverage; mean standard deviation over three runs. Realizable L2D outperforms or is comparable to baselines in all the settings.
Method
Dataset
System Accuracy
Accepted Accuracy
Coverage
Mozannar and Sontag [2020] (Lce)
91.60 a: 0.15
94.61 1: 0.67
44.55 = 1.68
Verma and Nalisnick [2022] (Lova)
92.18 = 0.10
95.43 = 0.36
58,56
Mozannar al. [2023] (LRs)
91.83 0.63
95.37 0.72
54.78 = 3.70
HateSpeech
Mao al. [2024a] (L-generat)
92.05 0.04
96.28 0.35
=
Realizable L.2D ( 0.7)
92.20 0.54
96.06 = 0.39
57.85 0.76
Realizable L2D (LRL2D.9
91.97 0.29
96.57 a: 0.69
53.25
Mozannar and Sontag [2020] (LCE)
66.33 0.47
73.65 + 1.83
55.17
Verma and Nalisnick [2022] (Lova)
66.33 1.31
71.03 a 5.10
53.33 =: 4.73
Mozannar al. [2023] (LRs)
66.00 2.27
+ 63.20
69.50 10.8
COMPASS
Mao et al. [2024a] (Lggeerra)
66.67 0.62
76.25 +: 2.42
48.33 5.33
Realizable L2D (LR122, 0.7)
66.17 2.01
69.33 + 3.03
55.67 5.99
Realizable 1.21 (LRL2D.9- 11
66.83 0.85
69.02 + 2.42
54.83 = 0.62
Mozannar and Sontag [2020] (LOR)
96.27 0.51
98.77 = 0.71
64.33 = 6.13
Verma and Nalisnick [2022] (Lova)
96.25 0.45
98.74 a: 0.54
67.88 = 6.16
Mozannar et al. [2023] (Lns)
96.63 0.18
98.23 + 0.78
66.63 = 1.80 1.80
CIFAR-IOH
Mao et al. [2024a] (L (Lgeneraa)
96.75 0.55
98.65 + 0.80
65.68 = 3.36
Realizable L2D (LaL2D, 0.7))
96.80 0.25
98.37 = 0.20
76.77 = 3.63
Realizable L2D (LRL2D,
96.57 0.05
98.34 + 0.24
77.37 2.43
Theorem 5.1. Assume that there exists zero error solution he S.. with Eta 1 (h*) 0 and H. is closed under scaling, Assume that lim (t) = 0. Then, the minimizability gap of comp-sun sum loss feomp vanishes: Mi (3)) =
However, in the deferral setting, this relationship no longer holds: H-consistency bounds cannot imply realizable K-coonsstencyy In particular, Mao et al. [2023f] showed that LCE benefits from K- consistency bounds, while Mozannar et al. [2023] showed that it is not realizable JCCconsistent. The loss function in [Madras al., 2018] not Bayes-consiste and thus does not have HC-consistency bound guarantees, but is actually realizable J[-consistent [Mozannar et al., 2023].
Experiments
In this section, we empirically evaluate our proposed surrogate losses and compare them with existing baselines.
Experimental settings. We follow the setting of Mozannar et al. [2023] and conduct experiments on synthetic dataset: Mixture-of-Gaussian [Mozannar et al., 2023], and three real-world datasets: CIFAR- 10H [Battleday et al., 2020). HateSpeech [Davidson et al., 2017], and COMPASS [Dressel and Farid, 2018]. For these three datasets, we adopt the same model class as that in [Mozannar et al., 2023, Table 1]. Each dataset is randomly split into 70%. 10%, and 20% for training, validation, and testing, respectively. For the Eexture-of-Gaussian [Mozannar et al., 2023, Section 7.2]. which is realizable by linear functions: there exists a linear hypothesis h* e H achieving zero deferral loss, EL... (h*) =0.
we adopt the exact realizable setting from
As with [Mozannar et al., 2023], we choose the cost function to be the expert's classification error: (xxyy) lg(z)=g) We compare our surrogate four baselines as described in Section 3.3: the cross-entropy surrogate LCF from [Mozannar and Sontag, 2020], the one-vs-all surrogate Lova from [Mozannar and Sontag, 2020], the realizable surrogate Lns from [Mozannar al., 2023), and the general surrogate Lgeneral from [Mao et al., 2024a]. For LOvA, we choose + as the logistic loss, following [Verma and Nalisnick, 2022]. For Lgeneral, we choose as the generalized cross entropy loss with = 0.7, following [Mao et al., 2024a]. For our Realizable L2D surrogate LRL2D, we consider two choices: É as the generalized cross entropy loss with q 0.7, following [Zhang and Sabuncu, 2018, Mao et al., 2024a], and é as the mean absolute eтror loss (g 1). Among these, LCE. Lova and Lgeneral are cayes-consistent but not realizable H-connsisentt; LRS, LRL2D with q = 0.7 LRL2D with = are both Sayes-consisten and realizable HC-consistent, shown in Sections 4.2 and 4.4. Note that in this case, LRS is special case of LRL.n when chosen as / llg( We use the same optimizer, learning rate, and number of epochs chosen in [Mozannar et al., 2023]. and we select the model that achieves the highest system accuracy, that is average [1 Laer (h, 2,, y)), on validation set.
0.7 and

---

0.98
0.92
System Accuracy
0.96
System Accuracy
0.91
0.94
0.90
0.92
Ler
Lowk
0.88
Lignnaaal
0.88
Lis
Lauzo,
0.7
LuzzD: q
0.86
9=1
Ligneral
500
1000
1500 2000 2500 3000 3500 4000
0.65
0.70
0.75
0.80
0.85
Training sample size
Coverage
(a) Comparison of system accuracy versus training sam- (b) Comparison of system accuracy versus coverage on ple size on realizable synthetic dataset.
the HateSpeech dataset with general cost functions.
Figure 1: Results for the realizable case and the non-realizable case with general cost functions.
Evaluation. For the three real-world datasets. we report the system accuracy, that is average value of - [a-Laor z, z, y)] on the test data. For completeness, we also include the accepted accuracy, that is the average value of [](())ey h(=))[mn]] This metric considers only incorrect predictions (h(z) + y) and measures the fraction of those where the system's 's output (h(x)) falls within the valid range of possible outputs ([n.). We also report the coverage, that is the average value of [Inc=)e[=]] on the test set, the fraction of test instances where the system's 's prediction falls within the valid range ([nJ). For each metric, we average results over three runs and report the mean accuracy along with the standard deviation for both our proposed methods and the baseline approaches. For the realizable Mixture-of -ff-asssi,ss,, we plot the system accuracy of various methods on a held-out test dataset consisting of 5,000 points as we increase the size of the training data.
Results. Table 3 shows that for the real-world datasets, LRL2D with q= 0.7, and LRL2D with q = either outperform or are comparable the best baseline in terms of system accuracy each dataset. This performance is supported by our JCcoosiitencyy bounds and Bayes-consistenge results for our Realizable L2D surrogate with respect the deferral loss Ldefs as shown in Sections 4.3 and 4.4. Table 3 also shows that LRL2D achieves reasonable coverage and acceptable accuracy. The system accuracy, coverage, and standard deviations of the baselines match those in [Mozannar et al., 2023]. Moreover, LRs. LBL2D with g 0.7, and LRLDD with 1 perform differently across various datasets: LRL2D with q = 0.7 outperforms the others on HateSpeech and CIFAR- 10H, while LRL2D with q 1 outperforms the others on COMPASS. Note that in this case, LRS is a special case of LRL2D when y chosen as log(t). These results show that Realizable L2D can benefit from the flexibility in the choice of VT.
Figure Ia shows system accuracy versus training samples the realizable Mixture-of of-Gaussianss distribution. Our surrogate loss LRL2D with q= 0.7 and 1 are realizable H-cconsistent, while LCE, LOVA and Lgeneral are not. This verifies our theory.
Figure 1b shows system accuracy versus coverage on the HateSpeech dataset by varying 3 in the general cost functions c(x. v) Lg(x)ay B. As 3 increases, deferral algorithms yield solutions with higher coverage and decreased system accuracy. This is because 3 controls the trade-off between expert's 's inference cost and accuracy. LRL2D with q = performs comparably to the surrogate loss Lgeneral, as both are supported by K-conssitency bounds and Bayes-consistency with general cost functions. Our surrogate loss LRL2D with outperforms Lns because the latter does not benefit from Bayes-consistency with general cost functions.
7 Conclusion
We introduced broad family of surrogate losses and algorithms for learning defer, parameterized by non- non-increassng function. We established their realizable HC-consistency properties under mild conditions and proved that several of these surrogate losses benefit from H--consistnncy bounds for cost functions based on classification error and general cost functions, which also imply their cayes-consistency. This research not only resolves an open question posed previous work but also lays the groundwork for comparing various consistency notions in learning to defer and standard classification. Looking forward, our approach offers promising avenue for analyzing multi-expert and two-stage settings.
10

---

References
D. A. E. Acar, A. Gangrade, and V. Saligrama. Budget learning via bracketing. In International Conference on Artificial Intelligence and Statistics, pages 4109-4119, 2020.
P. Awasthi, N. Frank, A. Mao, M. Mohri, and Y. Zhong. Calibration and consistency of adversarial surrogate losses. Advances Neural Information Processing Systems, pages 9804-9815, 202
Awasthi, A. Mao, M. Mohri, and Zhong. A finer calibration analysis for adversarial robustness. arXiv preprint wwXiv:2105.0/555 2021
P. Awasthi, A. Mao, M. Mohri, and Y. Zhong. J[-consistnney bounds for surrogate loss minimizers. In International Conference on Machine Learning. 2022a.
Awasthi, A. Mao, M. Mohri, and Y. Zhong. Multi-class H-consistency bounds. In Advances in neural information processing systems, 2022b.
Awasthi, A. Mao, M. Mohri, and Y. Zhong. Theoretically grounded loss functions and algorithms for adversarial robustness. In International Conference on Artificial Intelligence and Statistics, pages 10077-10094, 2023.
Awasthi, A. Mao, M. Mohri, and Y. Zhong. DC-programming for neural network optimizations. Journal of Global Optimization, 2024.
P. L. Bartlett and M. H. Wegkamp. Classification with reject option using hinge loss. Journal of Machine Learning Research, 98), 2008.
L. Bartlett, M. Jordan, and J. D. McAuliffe. Convexity, classification, and risk bounds. Journal of the American Statistical Association, 101(473):138-156 2006.
R. M. Battleday, J. C. Peterson, and T. L. Griffith.. Capturing human categorization of natural images by combining deep networks and cognitive models. Nature communications, 11(1):5418, 2020.
N. C. Benz and M. G. Rodriguez. Counterfactual inference of second opinions. In Uncertainty in Artificial Intelligence, pages 453-463, 2022.
J. Berkson. Application of the logistic function to bio-assay. Journal of the American Statistical Association, 39:357-333 335, 1944.
Berkson. Why prefer logits probits. Biometrics, 7(4):327-332) 1951.
S. Bubeck, V. Chandrasekaran, R. Eldan, J. Gehrke, E. Horvitz, E. Kamar, Lee, Y. T. Lee, Y. Li, S. Lundberg, et al. Sparks of artificial general intelligence: Early experiments with gpt-4, arXiv preprint arXiv:2303. 120.12222...1....... 2023.
Y. Cao, T. Cai, L. Feng, L. Gu, Gu, B. An, G. Niu, and M. Sugiyama. Generalizing consistent multi-class classification with rejection to be compatible with arbitrary losses. In Advances in neural information processing systems, 2022.
Y. Cao, H. Mozannar, L. Feng, H. Wei, and B. An. In defense of softmax parametrization for calibrated and consistent learning to defer. In Advances in Neural Information Processing Systems, 2023.
N. Charoenphakdee, Z. Cui. Y. Zhang, and M. Sugiyama. Classification with rejection based on cost-sensitive classification. International Conference on Machine Learning, pages 1507-1517, 2021.
M.-A. Charusaie and S. Samadi. A unifying post processin framework for multi-objective learn-to- defer problems. arXiv preprint arXiv:2407.12211 12710, 2024.
M.-A. Charusaie, Mozannar, D. Sontag, and S. Samadi. Sample efficient learning of predictors that complement humans. In International Conference on Machine Learning, pages 2972-3005 2022.
G. Chen, Li, C. Sun, and H. Wang. Learning to make adherence-aware advice, In International Conference Learning Representations, 2024.

---

X. Cheng, Y. Cao, H. Wang. H. Wei, B. An, and L. Feng. Regression with cost-based rejection. In Advances in Neural Information Processing Systems, 2023.
C. Chow. An optimum character recognition system using decision function. IEEE C., 1957.
C. Chow. On optimum recognition error and reject tradeoff. IEEE Transactions on information theory, 16(1):411444 1970.
C. Cortes, G. DeSalvo, and M. Mohri. Learning with rejection. International Conference on Algorithmic Learning Theory, pages 67-82, 2016a.
C. Cortes, DeSalvo, and M. Mohri. Boosting with abstention. In Advances Neural Information Processing Systems, pages 1660-1668, 2016b.
C. Cortes, G. DeSalvo, and M. Mohri. Theory and algorithms for learning with rejection in binary classification. Annals of Mathematics and Artificial Intelligence, pages 1-39, 2023.
C. Cortes, A. Mao, C. Mohri, M. Mohri, and Y. Zhong. Cardinality-aware set prediction and top-k classification. In Advances in neural information processing systems, 2024.
T. Davidson, D. Warmsley, M. Macy, and I. Weber. Automated hate speech detection and the problem of offensive language. Proceedings of the international AAAI conference on web and social media, volume 11, pages 312-515,20 2017.
A. De, P. Koley, N. Ganguly, and M. Gomez Modriz-od Regression under human assistance. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 261 16200, 2020.
A. De. N. Okati, A. Zarezade, and M. G. Rodriguez. Classification under human assistance. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 5905-5913, 2021.
J. Dressel and H. Farid. The accuracy, fairnsss, and limits of predicting recidivism. Science advances, 4(1 :1):eaa05580, 2018.
R. El- Yaniv and Wiener. Active learning via perfect selective classification. Journal of Machine Learning Research, 13(2), 2012.
R. El-Yaniv al. On the foundations of noise-free selective classification. Journal of Machine Learning Research, 11(5), 2010.
A. Gangrade, A. Kag, and V. Saligrama. Selective classification via one-sided prediction. In International Conference on Artificial Intelligence and Statistics, pages 2179-2187, 2021.
R. Gao, M. Saar- bacchssechan,,, M. De-Arteaga, L. Han, M. K. Lee, and M. Lease Human-ai collabora- tion with bandit feedback. arXiv preprint arXiv:2105. 20.21005511144. 2021.
Y. Geifmann and R. Yaniv. Selective classification for deep neural networks. In Advances in neural information processing systems, 2017.
Y. Geifiman and El-Yaniv. Selectivenet: A deep neural network with an integrated reject option. In International conference on machine learning, pages 2151-2159, 2019.
A. Ghosh, H. Kumar, and P. S. Sastry. Robust loss functions under label noise for deep neural networks. In Proceedings of the AAAI conference on artificial intelligence, 2017.
P. Hemmer, S. Schellhammer, M. Vössing, J. Jakubik, and G. Satzger. Forming effective human-ai teams: Building machine learning models that complement the capabilities of multiple experts. arXiv preprint wxXiv:2006.07948, 2022.
Hemmer, I.. Thede, M. Vössing, J. Jakubik, and N. Kühl. Learning defer with limited expert predictions. arXiv preprint arXiv:2304.073306 2023.
W. Jiang, Y. Zhao, and Z. Wang. Risk-controlled selective prediction for regression deep neural network models, In 2020 International Joint Conference on Neural Networks (IJCNN) pages 1-8, 2020.
12

---

W. Jitkrittum, N. Gupta, A. K. Menon, H. Narasimhan, A. Rawat, and S. Kumar. When does confidence-based cascade deferral suffice? In Advances in Neural Information Processing Systems, 2023.
S. Joshi, S. Parbhoo, and F. Doshi- Velez. Pre-emptive leaming-to-defer for sequential medical Decision-making under uncertainty. arXiv preprint arXiv:2109.06311, 2021.
G. Kerrigan, P. Smyth, and M. Steyvers. Combining human predictions with model probabilities via confusion matrices and calibration. Advances Neural Information Processing Systems, 34: 4421-4434, 2021.
V. Keswani, M. Lease, and K. Kenthapadi. Towards unbiased and accurate deferral to multiple experts. In Proceedings of the 2021 AAAI/ACM Conference on AI, Ethics, and Society, pages 154-165, 2021.
X. Li, S. Liu, C. Sun, and H. Wang. When no-rejection learning is optimal for regression with rejection. arXiv preprint arXiv:2307.02932, 2023.
J. Liu, B. Gallego, and S. Barbieri. Incorporating uncertainty in learning to defer algorithms for safe computer-aided diagnosis. Scientific reports, 12(1):1762, 2022.
S. Liu, Y. Cao, Q. Zhang, L. Feng, and B. An. Mitigating underfitting in learning to defer with consistent losses. In International Conference on Artificial Intelligence and Statistics, pages 4816-4824 2024.
P. Long and R. Servedio. Consistency versus realizable H-consistency for multiclass classification. In International Conference on Machine Learning, pages 801-809, 2013.
D. Madras, E. Creager, T. Pitassi, and R. Zemel. Learning adversarially fair and transferable representations. arXiv preprint arXiv: 1et.:0882.0.30 2018.
A. Mao, C. Mohri, M. Mohri, and Y. Zhong. Two-stage learning to defer with multiple experts. In Advances in neural information processing systems, 2023a.
A. Mao, M. Mohri, and Y. Zhong. H-consistency bounds: Characterization and extensions. In Advances in Neural Information Processing Systems, 2023b.
A. Mao, M. Mohri, and Y. Zhong. H-consistency bounds for pairwise misranking loss surrogates, In International conference on Machine learning, 2023c.
A. Mao, M. Mohri, and Y. Zhong. Ranking with abstention. In ICML 2023 Workshop The Many Facets of Preference-Bast Based Learning, 2023d.
A. Mao, M. Mohri, and Y. Zhong. Structured prediction with stronger consistency guarantees. In Advances in Neural Information Processing Systems, 2023e.
A. Mao, M. Mohri, and Y. Zhong. Cross-entropy loss functions: Theoretical analysis and applications. In International Conference on Machine Learning, 2023f.
A. Mao, M. Mohri, and Y. Zhong, Principled approaches for learning defer with multiple experts. In International Symposium on Artificial Intelligence and Mathematics, 2024a.
A. Mao, M. Mohri, and Y. Zhong. Predictor-rejector multi-class abstention:
Theoretical analysis and algorithms. In International Conference on Algorithmic Learning Theory, pages 822-867, 2024b.
A. Mao, M. Mohri, and Y. Zhong. Theoretically grounded loss functions and algorithms for score- based multi-class abstention. In International Conference Artificial Intelligence and Statistics, pages 4753-4761, 2024c.
A. Mao, M. Mohri, and Y. Zhong. Enhanced H-ccosistenccy bounds. arXiv preprint ar arXiv:2407. 13722, 2024d.
A. Mao, M. Mohri, and Zhong. H-consistency guarantees for regression. International Conference Machine Learning, pages 14737734737, 2024c.
13

---

A. Mao, M. Mohri, and Y. Zhong. Multi-label learning with stronger consistency guarantees. In Advances in neural information processing systems, 2024f.
A. Mao, M. Mohri, and Y. Zhong. Regression with multi-expert deferral. In International Conference on Machine Learning, pages 34738-34759, 2024g.
A. Mao, M. Mohri, and Zhong. A universal growth rate for learning with smooth surrogate losses. In Advances in neural information processing systems, 2024h.
C. Mohri, D. Andor, E. Choi, M. Collins, A. Mao, and Y. Zhong. Learning to reject with fixed predictor: Application to decontextualization. In International Conference on Learning Representations, 2024.
M. Mohri, A. Rostamizadeh, and A. Talwalkar, Foundations of Machine Learning. MIT Press, second edition, 2018
H. Mozannar and D. Sontag, Consistent estimators for learning to defer to an expert. In International Conference on Machine Learning, pages 7076-7087, 2020.
H. Mozannar, A. Satyanarayan, and D. Sontag. Teaching humans when to defer to a classifier via exemplars. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 5323-5331, 2022.
H. Mozannar, H. Lang, D. Wei, P. Sattigeri, S. Das, and D. Sontag. Who should predict? exact algorithms for learning to defer to humans. International Conference on Artificial Intelligence and Statistics, pages 10520-10545 2023.
H. Narasimhan, W. Jitkrittum, A. K. Menon, A. S. Rawat, and Kumar. Post-hoc estimators for learning to defer to an expert. In Advances in Neural Information Processing Systems, pages 29292-29304, 2022.
J. Neyman and E. S. Pearson. Ix. on the problem of the most efficient tests of statistical hypotheses. Philosophical Transactions of the Royal Society of London. Series A, Containing Papers of Mathematical or Physical Character, 231 23166944706)229-3337 1933.
C. Ni, N. Charoenphakdee, J. Honda, and M. Sugiyama. On the calibration of multiclass classification with rejection. In Advances in Neural Information Processing Systems, pages 2582-2592, 2019.
N. Okati, A. De, and M. Rodriguez. Differentiable learning under triage. Advances in Neural Information Processing Systems, 34:9140-9151 2021. 2021.
F. Palomba, A. Pugnana, J. M. Alvarez, and S. Ruggieri. A causal framework for evaluating deferring systems. arXiv preprint arXiv:2405. 2400:22255./992... 2024.
M. F. Pradier, J. Zazo, S. Parbhoo, R. H. Perlis, M. Zazzi, and F. Doshi-Veled Preferential mixture- of-experts: Interpretable models that rely on human expertise as much as possible. AMIA Summits on Translational Science Proceedings, 2021:525, 2021.
M. Raghu, K. Blumer, G. Corrado, J. Kleinberg, Z. Obermeyer, and Mullainathan. The algorithmic automation problem: Prediction, triage, and human effort. arXiv preprint arXiv:1903.1 12220, 2019.
N. Raman and M. Yee. Improving learning-to-defer to-defer algorithms through fine-tuning. arXiv preprint arXiv:2112.10768 2021.
H. G. Ramaswamy, A. Tewari, and S. Agarwal. Consistent algorithms for multiclass classification with an abstain option. Electronic Journal of Statistics, 12(1):530-554, 2018
M. D. Reid and R. C. Williamson. Composite binary losses. The Journal of Machine Learning Research, 11:2877-2422, 2010.
A. Shah, Y. Bu, J. K. Lee, S. Das, R. Panda, P. Sattigeri, and G. W. Worelll. Selective regression under fairness criteria. In International Conference on Machine Learning, pages 10598-19615, 2022.
14

---

I. Steinwart, How to compare different loss functions and their risks. Constructive Approximation. 26(2):225-287, 2007.
E. Straitouri, A. Singla, V. B. Meresht, and M. Rodriguz. Reinforcement learning under algorithmic triage. arXiv preprint arXiv:2109. 1910001....,,. 2021.
E. Straitouri, L. Wang, N. Okati, and M. G. Rodriguez. Provably improving expert predictions with conformal prediction. arXiv preprint arXiv:2201.12006, 2022.
D. Tailor, A. Patra, R. Verma, P. Manggala, and E. Nalisnick. Learning to defer to a population: A meta-learning approach. In International Conference on Artificial Intelligence and Statistics, pages 3475-3483, 2024.
A. Tewari and P. L. Bartlett. On the consistency of multiclass classification methods. Journal of Machine Learning Research, 1006 2007.
F. Verhulst. Notice sur loi que la population suit dans son accroissement. Correspondance mathématique el physique, 10:113 121, 1838.
P. F. Verhulst. Recherches mathématiques sur la loi d' d'accroissement de la population. Nouveaux Mémoires l'Académie Royale des Sciences et Belles-Lettre de Bruxelles, 18:1-42, 1845.
R. Verma and E. Nalisnick. Calibrated learning to defer with one-vs-all classifiers. In International Conference Machine Learning, pages 22184 22202, 2022.
R. Verma, D. Barrejón, and E. Nalisnick. Learning defer to multiple experts: Consistent surrogate losses, confidence calibration, and conformal ensembles. In International Conference on Artificial Intelligence and Statistics, pages 11415-11434 2023.
J. Wei, Y. Tay, R. Bommasani, C. Raffel, B. Zoph, Borgeaud, D. Yogatama. M. Bosma, D. Zhou, D. Metzler, E. H. Chi, T. Hashimoto, O. Vinyals, P. Liang, J. Dean, and W. Fedus. Emergent abilities of large language models. CoRR, abs/2206.07682. 2022.
Y. Wiener and R. El-Yaniv. Agnostic selective classification. In Advances in neural information processing systems, 2011.
Y. Wiener and R. Ylniv.. Pointwise tracking the optimal regression function. Advances in Neural Information Processing Systems, 25, 2012.
Y. Wiener and R. Yl-ian.v. Agnostic pointwise-competiiie selective classification. Journal of Artificial Intelligence Research, 52:171-201, 2015.
B. Wilder, E. Horvitz, and E. Kamar. Learning to complement humans. In International Joint Conferences on Artificial Intelligence, pages 1526-1522 1533, 2021.
M. Yuan and M. Wegkamp. Classification methods with reject option based on convex risk minimiza- tion. Journal of Machine Learning Research, 11(1), 2010.
M. Yuan and M. Wegkamp. SVMs with reject option. Bernoulli, 2011.
A. Zaoui, C. Denis, and M. Hebiri. Regression with reject option and application to knn. In Advances in Neural Information Processing Systems, pages
2020.
M. Zhang and S. Agarwal. Bayes consistency vs. H-consistency: The interplay between surrogate loss functions and the scoring function class. In Advances in Neural Information Processing Systems, 2020.
T. Zhang. Statistical behavior and consistency of classification methods based on convex risk minimization. The Annals of Statistics, 32(1):56 2004a.
T. Zhang. Statistical analysis of some multi-category large margin classification methods. Journal of Machine Learning Research, 5(Oct): 1225 1251, 2004b.
Zhang and M. Sabuncu. Generalized eross entropy loss for training deep neural networks with noisy labels. In Advances in neural information processing systems, 2018.
15

---

J. Zhao, M. Agrawal, P. Razavi, and D. Sontag, Directing human attention in event localization for clinical timeline creation. In Machine Learning for Healthcare Conference, pages 80-102, 2021.
C. Zheng, G. Wu, F. Bao, Y. Cao, C. Li, and J. Zhu, Revisiting discriminative vs. generative classifier:: Theory and implications. In International Conference on Machine Learning, pages 42420-42477, 2023.
16

---

Contents of Appendix
Proof of realizable JC-consistnnyy
18
B Proof of K-consistency bounds
19
B.1 Auxiliary lemma
19
B.2 v(t) = 1- t
20
B.3 ((() = log(()
23
B.4 V(() (1 (1-19)
26
Proof of Theorem 5.1
28
D Future work
28
17

---

A Proof of realizable H-consistency
Theorem 4.1. Assume that H is closed under scaling. Suppose that v is non-inee com-increasing ( > 0
and lim (t) 0. Then, the surrogate loss LRL2D is realizable HCconsistentt with respect to Ldef-
Proof. We first prove that for every (h, x. y) H x Xxx y, the following inequality holds:
LRL2D (h, v.
de (h, 1,)
V/
We will analyze by case.
1. Case If hf)) E [m]] (deferral does not occur):
(a) (n()++y 1, then we must have
c(x,y)
1
Last (h, = Ever eh(xz,)
$
2'
Egeey el((e)))))))))))
1
2
LRL2D(h, 2, v) 2 c(x,,)) 4
+ +(1 (1-c(z,)))
c(x,,))
2 4
Laef (h, (1, x,
2
3
(b) 1n(x)) = 0, then we must have
LRI.2D (0t,2(44,20 vr v) 2 0 Laer(h, v,)).
2. Case II: hf:) n (deferral occurs): then we must have
Laer = =
Eyegeh(orr)
= = LR,) 2cl,,,))))))))))))) c(
2 1
Laer 2,)).
2
3
This concludes that 2h, s LRLap(ha..)) Next, prove that LRL2D is realizable HC- ((3)
consistent under the assumptions. Consider distribution and an expert under which there exists zero eтror solution h" H with EL (h*) = O. Let be the minimizer of the surrogate loss: h argminkeи ELRLDD (h). Let be any real number. Then, the following inequality holds:
1 EL (h)
ELaat (h) s
(Laef S ((2) LRL2D)
(23))
1
LL (ah")
(h argmin ELRDOD (h) and HC is closed under scaling)
1 (3)
[[LRIan(ah" x. v) (x) = + ()P(h" =+
ve ((2)
B[LRLaD(ah" x,,) h (x) [n]]I((h (x))
For the first term conditional on h' (æ) = + 1, we must have h² (x, n + 1) > max h² (x, y) and cxx,y) y) 0 since the data is realizable. Therefore,
lim B[LRLeD(ah" 2x,9) h" (x) n 1))(("(x))= =n+))
eah' (a.1) eah (2,1+1)
lim
T
1h* = (x)=++))
a0++00
Ever (x,
B[O hh (x) = P)p(P" (x) = (lim-1 V(() 0 and monotone convergence theorem)
0.
18

---

For the second term conditional on h2(x) é [nz], we must have h" (x.3) > max /eD.'y h(2, v)) since the data is realizable. Therefore,
lim B[ xx, (m) a++000
(ab"()y)))
lim E c(x.V)
a00+000
Σ Egeey cah")
(a.)) (z,a1))
+ ((1-c(18)))
[h( e [n] P(h P(h e
Eyregeah
E[O h² (z) [n]]][(h' (x) [n]) (lim--1 (()) 0 and monotone convergence theorem)
= 0.
Combining the two analyses, we conclude that ELrer (h) and thus Lre2D is realizable H--conistent with respect to Ldef-
B Proof of H-consistency bounds
Before delving into the proof, we first establish some essential notation and definitions. Let represent a deferral surrogate loss and H denote hypothesis set. We define the conditional error as EL (h, x) and the conditional regret as Ae,,oe (h, e, 2), (TC, We proceed present general theorem demonstrating that, to establish H--oonistenccy bounds (1) with concave function T, it suffices to lower bound the conditional regret of the surrogate loss by that of the deferral loss, using the same function r.
x,,,,, v) the best-in-class conditional error as ej (H, x) = inf CL (h,
Theorem B.1. If the following holds for all E H and x E X, for some concave function r:
Al (h, ((AeL,,((h;;))
then, for all hypotheses h e H and for any distribution,
ELaer (h) - Eieer (H() Ma (I() (h) M)))
Proof. We can express the expectations of the conditional regrets for Laet and as follows:
F Cr m)] E (h) Eiaet (H) + Mi (H)
E[ m) (h) E[(H) + ML()).
Then, by using (4) and taking the expectation, we obtain:
ELam (h) Eige (IC) ML (7() E[ A ( [h,
$ E (TT
(Eq. (4))
<I El (E
(concavity of of
= =((E)(h) (H) ML())).
Thus, the proof is complete.
Next, to prove H-consistency bounds using Theorem B.I, we will characterize the conditional regret of the deferral loss Laet in the following section.
B.1 Auxiliary lemma
To simplify the presentation, we introduce the following notation. For any y, define p(æ, y) P(Y X x) as the conditional probability that Y y given X x. For brevity, we will omit the dependency on in our notation. We denote by hy l((x,)) v) for any y E We also denote by Py p(z, 3) and q, p(x, ()((2,)) y) for any y y, and Pn-1 Evey p(z, (1 (1- c(z,))).
19

---

Ph(a)
h(z) [n]
Note that p( (1 c(x,))) = Py 9y. Vy E y. Let ph = Ph(w) =
Let and hmax = argmax hy. Note that both ymax and Amax are in the label
Pr+11 = 1.
Vmax = argmax
space y, while h(x:) is in the augmented lahel space y. We characterize the conditional regret of the deferral loss Lee as follows.
Lemma B.2. Assume that H. is symmetric and complete. Then, the conditional regret of the deferral loss Ldef can be expressed as follows: ACLaa, (h, max (Pymae Pn=1] } Pn-
Proof. We can write the conditional enror of the deferral loss as follows:
C (h)
Σ (h,,
wey
Σ (((x.v) (nc) ((W))))) Σ p(r,,))(zz yEy
yEy
- Pa()) (1-P)t)) [M())([] (1-Pa+))
1-Phh Ph.
Since H. is symmetric and complete, for any e X, (h(x):he =y. Then, the best-in-class conditional error of Ldef can be expressed follows:
Cian (H, = inf Claer (h, hell
(5)
Therefore, AC (h, (h,
CLaa (h, x) CLas (H, maxx Pn+1 } Ph-
Next, will present the proof's separately in the following sections, by lower bounding the condi- tional regret of the surrogate loss by that of the deferral loss Ldef using Lemma B.2.
B.2 v (1) =1)==1tt
Theorem B.3, Assume that K. is symmetric and complete. Then, for all h H and any distribution, the following H-consistency bound holds:
ELaot (h) ELaor (3() Mener (H) nl (ELRIAD (h) ELRIZD (H) MLRLAD (H().
Proof. We can write the conditional error of the surrogate loss as follows:
CLRLDD (h)
Σ ((,, (2 LALAD x,))
yey
(((w))
ch((,.)) c((an-)))
p(x, (((z,))((E5)) y
Σ
Σ p(z, (((z,))(-c((..)))) vey
+
Eye ch((
chvv
Epy - (n)
1- chvv elints
Σ yey
qu
Exerye elair
Every
Every elto
vey
By Lemma B.2, the conditional regret of the deferral loss can be expressed as
AC 96 (h, x) = max Priaae Pn+1] } - Ph-
Next, we will show that the conditional regret of the surrogate loss can be lower bounded as follows:
1
ALLM (h, CLnxan (h) ei (H) n (AC (h)
(6)
20

---

We first prove that for any hypothesis h and E X. if Umax hmax, then the conditional error of
himas
y Vmax
be lower bounded by that of ht which satisfies that (x,
hymaa
y hmax
Indeed,
hy
otherwise.
6 emmmx + eltns
CLaLaD (h) CLauan (h) 9ymar
1
) (Pymar 4ymax
Σ Evegehe
Σ Eyeg
@Mlimax
e.hmma + elant
+ qivaax
Exeey ehly
+ (Phmaa 9lrmax
Eyeey elyy
Mo elun
(Pyaaxx Vyaann
Σ Eyer ehi
Eveer E.u
A
Aluma + elhmnz
(Phrnox [lmmax
Qlimax
Eveey ehv
Eyeey cha
(Pymax
Phomaa (eh
120.
Eyer ehv
Therefore, we only need to lower bound the conditional regret of hypothesis h satisfying V/max hmax- Next, will analyze case by case. Note that when (Pymax Pu+t1 (Hyymax -hxt1) > 0, have A ACLan (h, = max (amaxe Pn-1)
O.
1. Case I: If P Pymax
Pn+1 and y - hn+1 O: we define new hypothesis h such log( Ano (1) that () = log( cllamax h(x,,))
y= Vmax
== n 1 where A 2 2 O. Then, we can otherwise.
lower bound the conditional regret of LRL2D by using AC (1, CLaLAD (h) CnuaD (li,) for any Breaxx 14 0:
A AC De 2h,
sup
(CLRCAD (11) RiRc (Nin))
umma + clinte Eyegy' e'v env
sup e KVaaa 2012
Jymax 1
Evege env
(Dymar -9mmax)
e'lv' + Elhan
Σ
(py qv) 1
Evege"""
bnai +
)
elber + hibaa
Qyanax
1-
Ever Ena
(Pymes Wymea)
Eyeef cha
eliv + euuman -11)
Σ
(py -yr))r)
Eyegge e/v
(Aymns (enrss + e ) (Pat1 Pymmxx + Myaas (cf - e Mnni))
Evey ehv
sup
e 2ade Bans
-Puimx Pmt1))
(I = Ammax achieves the maximum)
Eyegers
(Pymax Pr+1)
(by the assumption 1pp11 2 Nymas -lipmax (by the assumption Pyiaxe 2 Pn+1 and hymax hx+1 S 0)
1
(ACL (h,
71
21

---

2. Case II: If Mmax PA++1 0 and yyax - hnt1 2 O: we define a new hypothesis hy such that Sog(e"nus
log( e
p2)
y = ymax
(x,
log( e.lomass 11)
y = n where 1 2 ps O. Then, we can lower bound
1((,,))
otherwise.
the conditional regret of LRL2D by using AC AC or (h, CLRLAD (h) CiaLZ (n)) for any e 2 22
A ALLLLDD, (h,
sup chn+12000
(CLaCaD (h)
CiRLDD (hw))
e Mmmaa
Aymar + Eltunl
sup cAn112220
Qyanax
1-
Eyegyetyy
(Dymex
Vymas 1
Eyeeyj enu
envv + elaan
Σ
(py Yor)
Evey eh
y'ey.yy* ymax Ymnax
Mass
Anis + Abbmax
9ymmx
1
Σ Eyeg enrs
(P Dsmmax)
Eyegg
eno + e elumaxx + Eyegg ehlo (Bymar (ehmus - (uvmaa
Σ
(Pys (ot)
V/EM y'maxx
Vonax
(pn+1 Pymaae gymaz (e"smax f e
sup
Σ Eyer chty ehnt12u20
(Pu-1 Pumax) Eyegehr
(μ = Anrr achieves the maximum)
(par1 Penaas)
(by the assumption hi My 1nx
71 +
1
(e
(by the assumption Pn-t Pymas and hymax hnot 2 20)
This proves the inequality (6). By Theorem B.I, we complete the proof.
22

---

B.3 llgg))
Theorem B.4. Assume that 3 is symmetric and complete. Assume that c(z y) [(()))) Then, for all h e H and any distribution, the following H-consisteney bound holds:
ELact (h) ELaes (H) + Miaar (3() s 2/ ELarnD (h) ELRLAD (3() + MLRLLD (3().
Proof. We can write the conditional error of the surrogate loss as follows:
CLaaaD (h,
Σ (r, v) (4,,2))(4
yey
e (xx.))
((x.)) + c(ann)))
Σ yey
p(= v)((r.)) log
Σ ((xx,)(1- yey
Evey ch((z.9))
Eyeyy ch(aie))
Nv
chv + chauri
=- Σ qy log
Σ (Py 93) log yey
Eyeey en
Every en
By Lemma B.2, the conditional regret of the deferral loss can be expressed as
ACLaar (h,,)) = max (Pymax Pn+1) - Ph-
Next, we will show that the conditional regret of the surrogate loss can be lower bounded as follows:
ACLRLED. (h,, CLRIAD (h) Cinnan (HF) ((h,,,,((h,,
We first consider the case where g(x) # Vmaxx Otherwise, it would be straightforward to see that the bound holds. In the case where g(x) # Ymax, we have Qymax Pmmas We first prove that for any hypothesis and x e X, Umax 1maxx then the conditional error can be lower bounded by that
Ymax
of h, which satisfies that T(x,8)) = hygmax hmax Indeed,
bly otherwise.
eLuaa (h) CL (h)
vmaux
Ummax + ehint
--Qymase log
(Punaux
Oxtmax log
Eyeej ellvr
Σ Eyegge elty
Ahann + chaon
log
(Phras -huaa log
Evey en:v"
E Eveyy chvv
e Nhhmax
Ahmma eftnes
+ Ogmmar log
(Pymax Yymaxx log
Eyeyy envy
Eyegge enl
vvmax
E pomax + elhin
Qlrmax log
(Phnax -bmmax log
Eyery eh-yr
E Eyegg cliy
Armax efbnr evvax + elhnia
(Aymax
Dtemax
log
(Pyiaex Qyaax Phinx + Abmox log
e Asmac
Armax
elinss
(Pyans Phimas
log
Bumax
ghunes
2 0.
Therefore, we only need to lower bound the conditional regret of hypothesis h satisfying Vmax Rmaax-
Since c(x, y) g())))) we have Pymox 2 Pn+1 Pε(x)) Note that when (P Pn+11 (h
hnt1) 0, have AC (h, max m Pymar pn-1) -Pp
When hymas hh O, we define
log hnrl + 11)
y = Vmax
a new hypothesis h, such that (z,
log Jumax - -1)
y n
where eavmaux - chiil otherwise.
h(x,,)
23

---

S S e"vanux, Then, we can lower bound the conditional regret of LRL2D by using AC (( (h, CLRIND (h) -e CLana ( for any envaax @0 μs vmax:
AC ALLLLDD Dr (+)
(CLaZaD (1)) - CiRaD (Rx))
sup ymax fire Ymaa -e h
Chumas
A cnnne
sup e/Simax 2/12 fimac - mes
Mmmas log
Eveeg clto
(Pymax Mmaa log
E Eyeey eha
enlyr + Elhanl
Σ
(Py - ( log
Σ Eyege enter
e/ +ymax
enee + 1 Σ Cyegehhv
Anuss e/"mmsx
+ Jymae log
+ (Pymax Aymmx) log
E Eyegehe
ene + vuuma - pii
+
Σ
(Dy - 2o log
E Eyrege
y/H,, Fymax
Anta + # Elymax
(py - 9o )og env + chuman 1 chlv' elenne
sup emmmx 21120" Vinax -e Anol
Yymax log
Σ
y y.sf
Anoi + 4 pomax
@ - H elhnes
sup "mmax 2/22 Smax hahill
Aymax log
(Dy - 4o log
y/e +uwaa
Amuu claur
S f2 clh
Buil +
Mamax f
sup Syaax fur Ymax hart
9ymax
log
(Put1 (P
9ymma )) log
elinss
By differentiating with respect to μ4, obtain that
f1 Vymoce Nymax
(pn=1 - (Pymmer 9ymmax h
9ymax
(pu+1 (Pymas 9ymaxe
achieves the maximum. Plugging it into the expression, have
(h, Asmax + An-i
Tylaax
2 Aymax log ehomax [qrmax + (put1 (Pymar Pymax
hehswox + e Mrerl [ (put1 (Pymax Lismace ))
(po+1 (Pymax Bylmase )) log
elenrs Dymmax + (pus1 (Pyiaax
4yanax
This can be further lower bounded by taking the minimum over h H. where the minimum is attained when Am Ansl Therefore,
A 1e
20p
Uymax log
Ayana + (Pr+1 (Pynex
U Myuaan
(pnrr (Pymax Aeranx ))
+ (put1 - (Pymax Dymaxx log
Aymas (prol (p (Prmax Aeanss

---

By applying Pinsker's s inequality [Mohri et al., 2018, Proposition E.7], we obtain
AC LLLIL de (h,
Igymae
Pu+1
(myma
Jymase
Aomax
1
Pu++ (Pymax lymax
2 Voanx Pn+11
(Priaax Iylanax
2
Myaaax Pn+1
(Pyanax Yymax )
(Pymaxx Pu+11)
Aymac + *pr+1 (Prmaxe Aihmax
2 (Pymax Pn++1
(gymax + Pn+11 (Pymax 9ymmax
S 1)
2
2 (AC xh,
(by the assumption Pymar 2 Pr++1 and hymaa S hn++1)
This proves the inequality (7). In the case where g(x) Mmnxx we have pn-1 Pymas: By Lemma B.2, the conditional regret of the deferral loss can be expressed as or = pu+1 Ph- h(x))) n 1, then we have A ACLa.r. (h, O. Otherwise, when h(a:) n 1, we can proceed in the similar
log( e + +H)
y=h(x)
way as above, by defining a new hypothesis h2 such that h y)
log( ( 11)
y=n+l.
h(r,z)
otherwise
Then, can lower bound the conditional regret of LRL2D by using A ALLLLDD. o6 (h,, x) CLELLD (h)
ex Lgaan (hp), by applying the same derivation as above, modulo replacing Umax with h(x). This leads to the inequality (7) as well. By Theorem B.I, we complete the proof.
25

---

B.4 (t)) = (1 (((--t))
Theorem B.S. Assume that K. is symmetric and complete. Assume that c(., v) g(())+ Then, for all E H and any distribution, the following H-consistency bound holds:
ELeat (h) ELeat (3)) MLeat (H) & 2 1) (LLaLaD (h) ELRLDD (H) M MLRCED (H)).
Proof. We can write the conditional enror of the surrogate loss as follows:
CLULDD (h,
Σ yey
p(2, (1,,,
1
Σ p( p(C,))c(o,,)
el(2,0)
Eye chilrss)
9 ye
(ch(ar)) ch(znnt1) ))
E wey
p(x, v) (1
Eyege elg
chyy Exegee
+ 1 - Ep,, - (a) (0)11
e + clinss Eveey eh>"" ))
Σ 4v yey
yey
By Lemma B.2, the conditional regret the deferral loss can be expressed as
ACt (h,, = max (Pymax P Ph-
Next, we will show that the conditional regret of the surrogate loss can be lower bounded as follows:
ALLR (h, CLRIAN (h) CiRLaD (F() 2 2(n 1)9 (A (h,
(8)
We first consider the case where g(x) Vmaxx- Otherwise, it would be straightforward to that the bound holds. In the case where g(x) # Ymax, we have Jymax = Pymax We first prove that for any hypothesis h and e X, if Vmax hmax then the conditional error of can be lower bounded by that
hhmax
y = Vmaxx
of Tr which satisfies that T(x,y))=
Nygaax
= Amax Indeed,
ht
otherwise.
q( CLLLLD (h) CLaZaD (h))
e Ummax
Iymoox
Σ Egegehe eha
(Prwax
Evereh e'v
Mimux chrill
+ Thraax
Exeey Ehhy
(pirmace Alrmae
1 Eveey ehter
hhmma + chuurl
81
Qytaax
Σ Eyer chv
(Primxx Iitanax
Eyger ellv
Ummax
@l + eltnns
Thiaax
-
Σ Eyeg chv
(Phnmxx Alrmao
Eveg chvv
[11-
e Uuman
Mlimax
(Aumas Drrasse
Ey Eyeger chu
Eneege chvv
Mumma + elinn
Noans + cllnne Evey e
+ (Pymaa Dymaax Pheaas
+ Dreann
Eyeey eltv
{(111
Aumax + cnnsss
(1-
hhmar + etaes
')]
(Pyaex Pirmmna
E eyy
Eyegge ehtvr
O.
26

---

Therefore, we only need to lower bound the conditional regret of hypothesis h satisfying Vmnxx hmaxx
Since c(2,y) y) g()))y we have Pymax Pn+1 Pe(x)) Note that when (Pymax Pu+ 1) yyym
hn+1) > we have AL (ch,,
maxx(Pymax Pn+1] Ph
O. When hymax hnt1 S O,
log( e +
y Imax
define new hypothesis hn such that (x,
log ("usmax
11)
-n+1. where elumaxx
h(r,y)
otherwise.
Buii S euumax, Then, we can lower bound the conditional regret of hypothesis h by using CLRLDD (h) Cr CaaaD (I1,) for any e e nn ju eumaa:
A ALRLLDD (1,
A ALLILDD (h,,))
sup
(elazaD (h) CRina (hw))
yymax 2222 P P
)) (Prnma Tmamas )11 (1- Avmmr eltrros
1
sup q e 2u1e Vemax elinl
1
Σ Eyregeh
Σ Eye c
ch chhnre
Σ
(Py 900)
Eyegett elu
Eyeey ehlo 1)
emmos + H
Ants e Eyeey
(Pymas yymnx
4immax
Eyregebr ehlu
(Py (or) (0r)
ehe el - 11
Σ
Eyegyh chv
y/EMl y'my..e=ymax yymax
1)+
(py - qv 1w 1-
E Eyrogeeh )
1
2
sup c Vaans zuze Manas hill
gymar -
Egrgchrr
Σ yeEyy a/mmxmax
q
Mmas t
)
99
Uimaxx
1
Ey Eyeey ehao
Σ
(py- 1
Evey ehe Ao Euart p S chvimux)
E
yeey. +ymax
1 supp
ehimaxx
) + (pu+1 (Pymax Iymax )) 1(11
ehniz
Jymar
Egereee
19) Evegeh
q
Vvaas zuzze" "uuzee"unaae Vanas Anll
Moss + pe Eyeey ehas
1) (pn-1
(P 9 )) eArsmnn -M
-ymmax
Eveey en'o'
By differentiating with respect to /4, we obtain that
p (pr+1 (Pyans Vyanas) F Avman (gymaax + Ani2
(ggmax) (pr+1 (Prman 4ymax q-r
achieves the maximum. Plugging it into the expression, we have
Ae (h,
Nymace
Anns
-9mmax
Σ Eyregeh
(pr+1 (Pymax Yymax)
Σ Tyyeehho
17
Mamax + tefnns [Prrll (Pranx Ayaanee
9 ymaas
Σ Eyege e/vo Domax (pn-1 (Pymox Aoman )) x
))
[e eltniaa Myans
(pr-1 (Pumes 4xmmax) ))
Exeyy e
Aomor + (prot - (Pymer Aymae
27

---

This can be further lower bounded by taking the minimum over / é H, where the minimum is attained when en e e for all y Therefore,
l-v Aymar (pn-1 (Pymaee Aymave
1-9
Pn++ Pylmxx
DE (1, 2 (n+ 1)9
2
2
(minimum attained when eh ehumar = ehv, Vy E e)
(Pymax -Pu+1) )²
2n + 1)8
(ymax (pr+1 (Pyamax +Iymaxx )) 1 and by analyzing the Taylor expansion)
2(n 1)9 (AC (k,
(Pymax 2 Pr+1 and Hymax $ hn+1)
This proves the inequality (8). the case where g(x) Ymnax- we have Pn-1 = Pymax" By Lemma B.2, the conditional regret of the deferral loss be expressed AC (h, n+ 1, then we have A ACtan. oe (h, x) = O. Otherwise, when h(x) # n 1, we can proceed in the similar
Pu+1 Ph- If h(x)) log(c
y= h(2)
way as above, by defining a new hypothesis hy such that (,, y)
log( (og(eeh 11) y ==n+l.
h(x,z)
otherwise
Then, we can lower bound the conditional regret of LRE2D by using A ACtaLaD et Eggan (hp)). by applying the same derivation as above, modulo replacing y/axx with h(r). This leads to the inequality (8) as well. By Theorem B.1, we complete the proof.
2 CL (h)
C Proof of Theorem 5.1
Theorem 5.1. Assume that there exists zero error solution h² H. with Etg (h²) = 0 and H. is closed under scaling. Assume that limn--1 (L) = 0. Then, the minimizability gap of comp-sum loss leomp vanishes: Miwoan (3) =
Proof. By definition and the Lebesgue dominated convergence theorem, we have
@ah (x,))
(z.0)
] 1
Me (I() S Elcomp (HI) S lim
T Every eat' (1:00))))))))
a-+400
This completes the proof.
D
Future work
While we presented comprehensive study of surrogate loss functions for learning to defer, our work focused on the standard single-expert and single-stage setting, aligning with previous work [Mozannar al., 2023]. However, an interesting direction is to extend our approach multi-expert [Verma et al., 2023] and two-stage settings [Mao et al., 2023a], which we have left for future work.
28

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
See Section 1.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
See Appendix D.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]

---

Justification:
See Section 4, Section 5, Appendix A, Appendix B and Appendix C.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: YYs]
Justification: See Section 6.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
30

---

Answer: [Yes]
Justification:
See Section
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.. cc/
http://oeeeamiiiiinniiooo onnooicy)))) for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: / //nips. wttpccccppppccccctt.ct..cc.cccct /
/Codeeeooiimsseeeeee cesssubmisiiioiioe wswinnolll onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
See Section
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: See Table 3.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
31

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
show in tables or
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: For each model training, we use an Nvidia A100 GPU.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: htt///eurrippcccoo httpp////ccpppptttt.ccciiiieeeed
Answer: [Yes]
Justification:
The authors have reviewed the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
The machine learning community has started to address the fairness implica- tions of involving downstream decision-maker This represents broader impact for any learning to defer (L.2D) methods.
Justification:
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
32

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: See Section 6.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name the license (c.g.. CC-BY 4.0) should be included for each asset. For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
33

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA].
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
34


Reviews:
[{"review_id": "QWq5wYUKTG", "reviewer": "Reviewer_Nrap", "summary": "This paper proposes considers the setting of learning to defer: a machine learning system can choose to either classify an instance or defer the decision to an expert which incurs a variable cost. The objective is to minimize the deferral loss of the system. To solve this problem, prior work has proposed surrogate losses with certain theoretical guarantees with respect to the original deferral loss. This work proposes the first surrogate loss RL2D that is realizable H-consistent, satisfies an H-consistency bound and thus is bayes consistent. This resolves an open problem proposed from prior work. Empirically, the authors showcase that the proposed surrogate exceeds or matches prior surrogates on three different datasets.", "questions": "- In which settings is the new proposed surrogate better than prior work?\n\n- How do the theoretical properties manifest in practice?\n\n\nFollow-up after author response:\n- the authors have done a good job answering the concerns, I believe this paper merits acceptance but I will maintain my original score as I am unsure about the level of impact of the paper.", "limitations": "Yes they have.", "rating": 6, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "Originality: The surrogate loss proposed in the work is novel as well as the proof technique for the theoretical properties. The derivation of the surrogate loss is different from prior work, however, it is not clear how the technique can be generalized to other settings.\n\nQuality: I have verified a good portion of the theoretical derivations and they seem sound. The experimental setup follows similar protocol to prior work and is sound. The paper is very strong theoretically.\n\nClarity: very well written, clearly stating contributions of prior work and setting the stage for readers unfamiliar with the setting and the literature. Derivation and theoretical properties very well stated and easy to follow along.\n\nSignificance: The paper settles an open problem from prior work at AISTATS and in turns I believe concludes (barring any breakthroughs) a line of work on deriving surrogate losses for learning to defer. I think this is important because now the community can focus on other settings and other considerations beyond theoretical consistency properties. However, I don't think the paper has a lot to offer in terms of techniques/methods for the community beyond the learning to defer problem as the derivation rely on some algebra of the deferral loss. Therefore, I don't expect this to be widely read by the community, but will be instead read in great detail by the community working on learning to defer and related problems.", "weaknesses": "There are no weaknesses with regard to the theory in this paper beyond the generalizability of the approach taken to related problem settings.\n\nHowever, the experimental setting is quite limited in terms of showcasing the behavior empirically of the newly proposed method. For the use of the surrogate in practice, it is not clear in which scenarios (if any) is the surrogate superior to prior work.\n\nMoreover, it is not clear how do the theoretical properties help in practice.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your appreciation of our work. We will take your suggestions into account when preparing the final version. Below please find responses to specific questions.\n\n**Weaknesses:**\n\n**1. There are no weaknesses with regard to the theory in this paper beyond the generalizability of the approach taken to related problem settings.**\n\n**Response:** Thank you for appreciating our theoretical contributions. While the proof techniques and methods may not extend directly to other settings beyond L2D, we believe our work connecting realizable $H$-consistency, $H$-consistency bounds, and Bayes-consistency could provide valuable insights into these consistency notions in other learning settings. In particular, these connections, along with our approach of constructively replacing indicator functions with smooth loss functions in the novel derivation of new surrogate losses from first principles, could help design loss functions that benefit from strong consistency guarantees in various scenarios.\n\n**2. However, the experimental setting is quite limited in terms of showcasing the behavior empirically of the newly proposed method.**\n\n**Response:** Thank you for the feedback. We have included two additional experiments in the global response: the realizable case and the non-realizable case with general cost functions. In the realizable case, the additional experimental result (Figure 1) shows that our surrogate loss $\\mathsf L_{\\mathrm{RL2D}}$ with $q = 0.7$ and $q = 1$ are realizable $H$-consistent, while $\\mathsf L_{\\mathrm{CE}}$, $\\mathsf L_{\\mathrm{OVA}}$ and $\\mathsf L_{\\mathrm{general}}$ are not. This validates our theory.\n\nIn the non-realizable case with general cost functions, the additional experimental result (Figure 2) shows that our surrogate loss $\\mathsf{L}_ {\\mathrm{RL2D}}$ with $q = 1$ performs comparably to the surrogate loss $\\mathsf{L}_ {\\mathrm{general}}$, as both are supported by $H$-consistency bounds and Bayes-consistency with general cost functions. Our surrogate loss $\\mathsf{L}_ {\\mathrm{RL2D}}$ with $q = 1$ outperforms $\\mathsf{L}_ {\\mathrm{RS}}$ because the latter does not benefit from Bayes-consistency with general cost functions.\n\n**Questions:**\n\n**1. In which settings is the new proposed surrogate better than prior work?**\n\n**Weakness: For the use of the surrogate in practice, it is not clear in which scenarios (if any) is the surrogate superior to prior work.**\n\n**Response:** Our surrogate losses $\\mathsf{L}_ {\\mathrm{RL2D}}$ satisfying Theorem 4.1 perform better in realizable scenarios than the surrogate losses $\\mathsf{L}_ {\\mathrm{CE}}$, $\\mathsf{L}_ {\\mathrm{OVA}}$, and $\\mathsf{L}_ {\\mathrm{general}}$ from prior work, as ours are realizable $H$-consistent while theirs are not. This is illustrated by our experiment in the realizable case (Figure 1 in the global response).\n\nOur surrogate losses $\\mathsf{L}_ {\\mathrm{RL2D}}$ satisfying Theorem 4.2 and Corollary 4.4 are comparable to the surrogate losses in prior work in non-realizable scenarios when the cost is the expert's classification error, as all of them are Bayes-consistent and supported by $H$-consistency bounds. This is demonstrated by our experiment in the non-realizable case with the cost function being the expert's classification error (Table 2 in the submission).\n\nOur surrogate losses $\\mathsf{L}_ {\\mathrm{RL2D}}$ satisfying Theorem 4.3 and Corollary 4.5 are superior to the surrogate loss $\\mathsf{L}_ {\\mathrm{RS}}$ in non-realizable scenarios with general cost functions, as ours are supported by $H$-consistency bounds and Bayes-consistency while theirs are not. This is evidenced by our experiment in the non-realizable case with general cost functions (Figure 2 in the global response).\n\n**2. How do the theoretical properties manifest in practice?**\n\n**Weakness: Moreover, it is not clear how do the theoretical properties help in practice.**\n\n**Response:** The additional experimental result (Figure 1 in the global response) in the realizable scenario demonstrates that our realizable $H$-consistent surrogate loss $\\mathsf{L}_ {\\mathrm{RL2D}}$ with $q = 0.7$ and $q = 1$ outperforms $\\mathsf{L}_ {\\mathrm{CE}}$, $\\mathsf{L}_ {\\mathrm{OVA}}$, and $\\mathsf{L}_ {\\mathrm{general}}$, which are not realizable $H$-consistent. Realizable $H$-consistency is beneficial in practice since realizable scenarios are common, particularly in the current use of neural networks in applications. Furthermore, the simultaneous $H$-consistency properties of our surrogate losses support their use in non-realizable scenarios, as they share the same Bayes-consistency properties with existing surrogate losses and are expected to perform comparably. The additional experimental result (Figure 2 in the global response) in the non-realizable scenario with general cost functions shows that our surrogate loss $\\mathsf{L}_ {\\mathrm{RL2D}}$ with $q = 1$ performs comparably to the surrogate loss $\\mathsf{L}_ {\\mathrm{general}}$, as both are supported by H-consistency bounds and Bayes-consistency with general cost functions. Our surrogate loss $\\mathsf{L}_ {\\mathrm{RL2D}}$ with $q = 1$ outperforms $\\mathsf{L}_ {\\mathrm{RS}}$ because the latter does not benefit from Bayes-consistency with general cost functions. These experimental results align with and further validate our theory.", "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": "", "extra_scores": {}}, {"review_id": "0tUCIi7vk5", "reviewer": "Reviewer_kR4F", "summary": "The authors provide a framework of surrogate loss functions for learning to defer under the multi-class classification problem. By examining the deferral loss function and choosing different surrogates for the indicator functions, the authors provide a novel class of surrogate loss functions for learning to defer and prove the realizable $\\mathcal{H}$-consistency and $\\mathcal{H}$-consistency for some cases. The authors also verify their proposed loss with numerical results.", "questions": "1. The major concern of mine is that the training under the proposed loss function requires the full responses of the expert to the entire training dataset, which is undesirable for the L2D problem. Previous surrogate loss functions (nominated in Section 3.3) only require $c(x, y)$ if the model chooses to defer. The learning to defer problem is proposed to ease the pain of consulting experts, while I think the loss function proposed works against that principle. Is it possible to mitigate the training cost of the model?\n2. All the remaining questions are addressed in the Weakness part and do not matter unless the first question is addressed.", "limitations": "NA", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The analysis is novel and provides new insights for learning to defer literature;\n2. The paper addresses the problem of achieving $\\mathcal{H}$-consistency and realizable $\\mathcal{H}$-consistency simultaneously.", "weaknesses": "1. (Major) The proposed loss is not practical in many critical settings when the cost to consult an expert is high; Both terms of the derived loss function contain the exact value of $c(x, y)$ while knowing $c(x, y)$ itself needs consulting the expert if $c(x, y)$ is related to the expert's response. Thus, training a model using the proposed surrogate loss requires querying not only the true label but also the expert's response to every single sample, which is somewhat against the motivation of deriving the problem of learning to defer. See the derivation of equation (2). (Addressed, improve my rating to 6)\n2. (Minor) Some of the results are restricted to the case $c(x,y) = 1_{g(x) \\neq y}$, which is limited compared to the vast problem settings of learning to defer;\n3. (Minor) The presentation is a little confusing: there are three consistencies (Bayes consistency, $\\mathcal{H}$- consistency, and realizable $\\mathcal{H}$-consistency), while their relationships should be formally summarized into some propositions; the existing surrogate loss functions' consistencies should also be summarized into one table with indicator \"yes\", \"no\", or \"not proved\" for each consistency.\n4. (Moderate) The numerical experiments don't specify the expert algorithm; the experiments are also very restricted to the case of $c(x,y) = 1_{g(x) \\neq y}$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful comments. We have carefully addressed all the questions raised. Please find our responses below.\n\n**Weakness 1: The proposed loss is not practical ... the derivation of equation (2).**\n\n**Question 1. The major concern ... mitigate the training cost of the model?**\n\n**Response:** Let us begin by addressing a misconception: all previous surrogate loss functions, including those in Section 3.3, require knowing the costs $c(x, y)$ for all training points. This is essential to select an effective predictor that minimizes the need to consult experts during inference. The same requirement applies also to the original deferral loss itself (whose direct minimization is intractable).\n\nFurthermore, Eq. (2) is just an equivalent form of the original deferral loss, which helps derive new surrogate loss functions from first principles. \n\nThe goal of the L2D framework is to suitably decide whether to predict a label or defer to an expert at *inference time*. During inference, it is only necessary to compute the output of the selected expert.\n\nLearning a good deferral solution requires training a predictor with an augmented label corresponding to the deferral options using the training data. Thus, the full responses of the experts are required during training to train the predictor effectively.\n\nOur work is fully consistent with the L2D framework and does not violate its principle.\n\nNow, it's certainly possible to explore alternative solutions to mitigate training costs:\n\n- Using Precomputed Costs: Instead of relying on instance-specific costs, one could use a general precomputed cost, such as the average error of an expert. This simplifies training but might lead to a less optimal deferral solution compared to using instance-dependent costs.\n\n- Learning to Predict Costs: Another approach is to train a model $f$ for each expert to predict the costs $c(x, y)$. While pre-training is also needed here, it might be possible to use a smaller training set. This approach introduces trade-offs worth investigating, depending on the desired level of cost estimation accuracy.\n\n- Partial Cost Computation: A third option involves using only a fraction of the costs during training and leveraging techniques like importance weighting to estimate the costs for instances where they weren't computed.\n\n**Weakness 2. (Minor) Some of the results are restricted to the case $c(x, y) = 1_{g(x) \\neq y}$ ... settings of learning to defer.**\n\n**Response:** The case $c(x, y) = 1_{\\mathsf{g}(x) \\neq y}$ has been adopted in previous fundamental work on L2D [Mozannar and Sontag, 2020; Verma and Nalisnick, 2022], including the recent study on realizable $H$-consistency by Mozannar et al. (2023). The surrogate losses $\\mathsf{L}_ {\\mathrm{CE}}$, $\\mathsf{L}_ {\\mathrm{OVA}}$, and $\\mathsf{L}_ {\\mathrm{RS}}$ in Section 3.3 are all proposed in this context. \n\nOur work introduces a new family of surrogate losses parameterized by a function $\\Phi$ that can achieve Bayes-consistency, realizable $H$-consistency, and $H$-consistency bounds simultaneously, both in the case of $c(x, y) = 1_{\\mathsf{g}(x) \\neq y}$ and for general cost functions with appropriate choices of $\\Phi$. Our work also highlights that consistency guarantees can differ between the standard case of $c(x, y) = 1_{\\mathsf{g}(x) \\neq y}$ and cases involving general cost functions for surrogate loss functions in L2D, a distinction not pointed out in previous studies. Additionally, we resolve an open question raised in previous work [Mozannar et al., 2023] by proving the realizable $H$-consistency and Bayes-consistency of a specific surrogate loss in the case $c(x, y) = 1_{\\mathsf{g}(x) \\neq y}$.\n\n**Weakness 3. (Minor) The presentation is a little confusing ... for each consistency.**\n\n**Response:** Thank you for the suggestions. We will clarify the relationships between the three consistency notions in the propositions and include tables summarizing the properties of existing surrogate losses by using an additional page in the final version. Below is a table of the consistency properties of existing surrogate losses and ours in the case of $c(x, y) = 1_{\\mathsf{g}(x) \\neq y}$.\n\n| Surrogate losses| Realizable $H$-consistency| Bayes-consistency| $H$-consistency bounds|\n|-|-|-|-|\n| $\\mathsf{L_{\\mathrm{CE}}}$|no|yes|yes|\n| $\\mathsf{L_{\\mathrm{OvA}}}$|no|yes|yes|\n| $\\mathsf{L_{\\mathrm{general}}}$|no|yes|yes|\n| $\\mathsf{L_{\\mathrm{RS}}}$ ($\\mathsf{L}_{\\mathrm{RL2D}}$ with $\\Psi(t) = -\\log(t)$)|yes|yes (proved by us)|yes (proved by us)|\n| $\\mathsf{L}_{\\mathrm{RL2D}}$ with $\\Psi(t) = \\frac{1}{q} \\left(1 - t^q\\right), q \\in (0, 1)$|yes|yes|yes|\n| $\\mathsf{L}_{\\mathrm{RL2D}}$ with $\\Psi(t) = 1 - t$|yes|yes|yes|\n\n**Weakness 4. (Moderate) The numerical experiments don't specify the expert ... of $c(x, y) = 1_{g(x) \\neq y}$.**\n\n**Response:** We follow the setting of Mozannar et al. [2023] and adopt the same expert algorithm as in [Mozannar et al., 2023, Table 1, Human column]. We will clarify this in the final version.\n\nAs mentioned before, most surrogate losses proposed in previous work, except $\\mathsf{L}_ {\\mathrm{general}}$, are in the case of $c(x, y) = 1_{\\mathsf{g}(x) \\neq y}$. This naturally leads to a comparison of these surrogate losses in the context of $c(x, y) = 1_{\\mathsf{g}(x) \\neq y}$.\n\nWe have included an additional experiment involving general cost functions. In the non-realizable case with general cost functions, the additional experimental result (Figure 2 in the global response) shows that our surrogate loss $\\mathsf{L}_ {\\mathrm{RL2D}}$ with $q = 1$ performs comparably to the surrogate loss $\\mathsf{L}_ {\\mathrm{general}}$, as both are supported by $H$-consistency bounds and Bayes-consistency with general cost functions. Our surrogate loss $\\mathsf{L}_ {\\mathrm{RL2D}}$ with $q = 1$ outperforms $\\mathsf{L}_ {\\mathrm{RS}}$ because the latter does not benefit from Bayes-consistency with general cost functions.", "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": "", "extra_scores": {}}, {"review_id": "tvoZHFmiZI", "reviewer": "Reviewer_oVSD", "summary": "This paper considers the problem of learning to defer (L2D),  where a classifier is allowed to defer a decision to an expert (possibly expensive to query) and trained to accurately predict while minimising the expert cost. \n\nA major contribution of this paper is establishing consistency guarantees for surrogate losses. \nSpecifically, the authors derive a loss that encompasses existing surrogate losses. \nThe authors provide sufficient conditions for the proposed surrogate loss to have realisable H consistency and for H consistency bounds. \nFrom the derived H consistency bounds, the authors show that certain choices of the expert cost leads to a surrogate loss that is both Bayes and realisable H consistent.", "questions": "1. Why is H consistency important in L2D?", "limitations": "Yes", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is very well written and does not have major issues in clarity.\n\nThis paper seems to provide a general  framework for analysing surrogate losses for L2D, and the established results appear to be novel. \nI am not actively working on L2D and my evaluation might not be accurate.", "weaknesses": "Due to my lack of experience in the field, I find it challenging to adequately adjudicate the significance of the work. \nRealisable H consistency effectively assumes that there is a perfect classifier that does not need an expert. \nThis preposition seems to be strong and diminishes the point of having an expert.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your appreciation of our work. We will take your suggestions into account when preparing the final version. Below please find responses to specific questions.\n\n**Weaknesses: Due to my lack of experience in the field, I find it challenging to adequately adjudicate the significance of the work. Realizable H consistency effectively assumes that there is a perfect classifier that does not need an expert. This preposition seems to be strong and diminishes the point of having an expert.**\n\n**Response:** The notion of realizable $H$-consistency was first studied by Long and Servedio (2013) and Zhang and Agarwal (2020) in the standard classification setting. There, it means that under the assumption there is a classifier that achieves zero multi-class zero-one loss, minimizing the surrogate loss also leads to a zero-error solution. \n\nThis notion was extended to the Learning to Defer (L2D) setting by Mozannar et al. (2023). Here, it implies that under the assumption that there is a predictor (a standard classifier augmented with a deferral option) and an expert who achieve zero deferral loss, minimizing the surrogate loss also results in a zero-error solution. Note that in the L2D setting, the assumption does not imply \"there is a perfect classifier that does not need an expert.\" Rather, it means that for every instance $x$, either deferral does not occur and the predictor achieves the zero multi-class zero-one loss, or deferral occurs but the expert achieves zero cost $c(x, y) = 0$.\n\n When the cost is defined as the expert’s classification error: $c(x, y) = 1_{\\mathsf{g}(x) \\neq y}$, as in previous work by Mozannar and Sontag (2020), Verma and Nalisnick (2022), and Mozannar et al. (2023), it implies that the expert achieves a zero multi-class zero-one loss solution on the instance $x$ where deferral occurs. This does not diminish the point of having an expert. Instead, it effectively assumes that there is a good balance between a standard classifier, a deferral option, and an expert such that for every instance $x$, the deferral loss is zero.\n\n**Questions: Why is H consistency important in L2D?**\n\n**Response:** Directly optimizing the deferral loss function, which is the target loss in L2D, is generally computationally intractable for complex hypothesis sets $H$. Therefore, a common approach is to optimize a surrogate loss that facilitates the optimization of the deferral loss function. But, what guarantees can we rely on when minimizing a surrogate loss of the deferral loss? This is a fundamental question with significant implications for L2D.\n\nA desirable guarantee often referred to in this context is Bayes-consistency. It means that optimizing the surrogate loss over the family of all measurable functions leads to the minimization of the deferral loss over the same family. However, while Bayes-consistency is valuable, it is not sufficiently informative, as it is established for the family of all measurable functions and disregards the crucial role played by restricted hypothesis sets in learning, such as a family of linear models or neural networks.\n\nAs pointed out by Long and Servedio [2013], in some cases, minimizing Bayes-consistent losses can result in constant expected error, while minimizing inconsistent losses can yield an expected loss approaching zero. To address this limitation, the authors introduced the concept of realizable $H$-consistency, further explored by Zhang and Agarwal [2020] and more recently, by Mozannar et al. (2023) in L2D. Nonetheless, these guarantees are only asymptotic and do not provide guarantees for approximate minimizers.\n\nRecent research by Awasthi et al. [2022b,a] has instead introduced and analyzed $H$-consistency bounds, further explored by Mao et al. [2023a, 2024a] in L2D. These bounds are more informative than Bayes-consistency since they are hypothesis set-specific and non-asymptotic. Crucially, they provide upper bounds on the estimation error of the target loss, for example, the deferral loss, that holds for any predictor $h$ within a hypothesis set $H$. These bounds relate this estimation error to the surrogate loss estimation error.\n\nRealizable $H$-consistency and $H$-consistency bounds were first proposed and extensively studied in standard classification. $H$-consistency bounds imply Bayes-consistency and realizable $H$-consistency in the standard classification setting and represent a state-of-the-art consistency guarantee since it is both non-asymptotic and hypothesis set-dependent. As with Bayes-consistency studied in a variety of scenarios, it is natural to study the stronger $H$-consistency in scenarios including L2D.\n\nAlthough both realizable $H$-consistency and $H$-consistency bounds have been explored in the L2D setting, no existing surrogate loss achieves realizable $H$-consistency and $H$-consistency bounds (including Bayes-consistency) simultaneously. Furthermore, the connection between these consistency notions is not as clear as that in the standard classification.\n\nOur work fills this gap by presenting a comprehensive study of these consistency notions and surrogate loss functions for L2D. We introduce a new family of surrogate losses and establish their realizable $H$-consistency and $H$-consistency bounds under different cases. Our results also resolve an open question raised in previous work [Mozannar et al., 2023] by proving the realizable H-consistency and Bayes-consistency of a specific surrogate loss. We further investigate the relationship between $H$-consistency bounds and realizable $H$-consistency in L2D, highlighting key differences from standard classification.\n\nFurthermore, these $H$-consistency guarantees provide significant *algorithmic benefits* when minimizing our new surrogate loss functions, as illustrated by our experiments. We refer the reviewer to our response to Question 1 of Reviewer Nrap for more details on the superiority of our surrogate losses compared to previous work.", "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": "", "extra_scores": {}}, {"review_id": "m1asXbitGS", "reviewer": "Reviewer_W4md", "summary": "This work studies learning to defer, focusing on the single-stage and single-expert setting. It introduces a family of surrogate losses based on comp-sum losses [Mao et al., 2023b] and establishes their realizable H-consistency (under mild conditions). In addition, when the base loss is the logistic loss $\\Psi_{log}$ or the generalized cross entropy loss $\\Psi_{gce}$, H-consistency bounds are proven (under mild conditions) when the cost function of deferring is classification error. When the base loss is the mean absolute error loss $\\Psi_{mae}$, H-consistency bounds are proven (under mild conditions) when the cost function of deferring is general. Note that H-consistency implies Bayes consistency. The results also close an open question raised by Mozannar et al., 2023. The relationship between realizable H-consistency and H-consistency bounds is then analyzed for learning to defer. Finally, the proposed surrogates are evaluated empirically and compared with existing baselines.", "questions": "Besides my concerns above, here are some other questions:\n\n1. Can constrained losses [1] be used as the base loss?\n\n2. Lines 273-274: Can negative results be proven formally?\n\n\n[1] Y. Lee, Y. Lin, and G. Wahba. Multicategory support vector machines: Theory and application to the classification of microarray data and satellite radiance data. Journal of the American Statistical Association, 99(465):67–81, 2004.", "limitations": "The authors have adequately addressed the limitations.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "**Originality**\n\n- A new family of surrogate losses based on comp-sum losses (focusing on $\\Psi_{log}$, $\\Psi_{gce}$, and $\\Psi_{mae}$) [Mao et al., 2023b] for learning to defer (the single-stage and single-expert setting).\n- Conditions for realizable H-consistency are identified (Theorem 4.1). In particular, $\\Psi_{log}$, $\\Psi_{gce}$, and $\\Psi_{mae}$ all satisfy the conditions. This result is more general than Mozannar et al. [2023]\n- When the cost function of deferring is classification error, H-consistency bounds are proven for base losses $\\Psi_{log}$ and $\\Psi_{gce}$ (Theorem 4.2).\n- When the cost function of deferring is general, an H-consistency bound is proven for base loss $\\Psi_{mae}$ (Theorem 4.3).\n\nThe results also close an open question raised by Mozannar et al., 2023 (Section 4.4). The relationship between realizable H-consistency and H-consistency bounds is then analyzed for learning to defer (Section 5). Related work is adequately cited and compared.\n\n**Quality**\n\nThe submission is technically sound. Claims are well supported by proofs.\n\n**Clarity**\n\nThe submission is generally clearly written and well organized.\n\n**Significance**\n\nThe work closes an open question raised in previous work. Its work to connect both realizable H-consistency and H-consistency bounds might be useful in other learning settings.", "weaknesses": "**Originality**\n\n- The realizable H-consistency result (Theorem 4.1) only applies to a subset of comp-sum losses.\n- The H-consistency results (Theorems 4.2 and 4.3) require case-by-case analysis. Is it possible to prove such results for all comp-sum losses?\n\n**Quality**\n\n- Some experiments in realizable settings can help confirm the realizable H-consistency result.\n\n**Clarity**\n\n- Section 5 is a bit unclear. Lines 300-302: Do you mean that in the realizable setting, all surrogate minimizability gaps vanish? Or is it only for comp-sum losses?\n\n**Significance**\n\n- The applicability of this work might be limited to learning to defer.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your appreciation of our work. We will take your suggestions into account when preparing the final version. Below please find responses to specific questions.\n\n**Weaknesses:**\n\n**1. The realizable H-consistency result (Theorem 4.1) only applies to a subset of comp-sum losses.**\n\n**Response:** We would like to clarify that the assumption regarding the function $\\Phi$ in Theorem 4.1 is mild. The condition that $\\Psi$ is non-increasing, with $\\Psi(\\frac{2}{3}) > 0$ and $\\lim_{t \\to 1} \\Psi(t) = 0$, is satisfied by all common comp-sum losses in practice.\n\n**2. The H-consistency results (Theorems 4.2 and 4.3) require case-by-case analysis. Is it possible to prove such results for all comp-sum losses?**\n\n**Response:** That's a great question. We expect that our proof ideas can potentially be extended to other comp-sum losses. First, we demonstrate that for any hypothesis $h$ and input $x$, if $y_{\\max}$, the label with the highest conditional probability, is not the predicted label $h_{\\max}$, the conditional error of $h$ is lower bounded by a modified hypothesis $\\overline{h}$ (obtained by swapping the scores of $y_{\\max}$ and $h_{\\max}$). Then, we show that for hypotheses where $y_{\\max} = h_{\\max}$, we lower bound their conditional regret in terms of the conditional regret of the deferral loss using a new hypothesis $h_{\\mu}$. \n\nHowever, the proof of establishing lower bounds in each case depends on the forms of the comp-sum losses and indeed requires a case-by-case analysis. Presenting a unified analysis and extending these results to all comp-sum losses is left as future work. Nevertheless, our results have included the most widely used comp-sum losses in practice, such as logistic loss, generalized cross-entropy loss, and mean absolute error loss.\n\n**3. Some experiments in realizable settings can help confirm the realizable H-consistency result.**\n\n**Response:** Thank you for the feedback. We have included the additional experiment in the realizable case. The additional experimental result (Figure 1 in the global response) shows that our surrogate loss $\\mathsf L_{\\mathrm{RL2D}}$ with $q = 0.7$ and $q = 1$ are realizable $H$-consistent, while $\\mathsf L_{\\mathrm{CE}}$, $\\mathsf L_{\\mathrm{OVA}}$ and $\\mathsf L_{\\mathrm{general}}$ are not. This validates our theory.\n\n**4. Section 5 is a bit unclear. Lines 300-302: Do you mean that in the realizable setting, all surrogate minimizability gaps vanish? Or is it only for comp-sum losses?**\n\n**Response:** In standard classification, minimizability gaps vanish under the realizable assumption for common multi-class surrogate losses such as max losses [Crammer and Singer, 2001], sum losses [Weston and Watkins, 1999], and comp-sum losses under mild assumptions. We will further clarify this in the final version.\n\n[1] K. Crammer and Y. Singer. On the algorithmic implementation of multiclass kernel-based vector machines. Journal of machine learning research, 2(Dec):265–292, 2001.\n\n[2] J. Weston and C. Watkins. Support vector machines for multi-class pattern recognition. European Symposium on Artificial Neural Networks, 4(6), 1999.\n\n**5. The applicability of this work might be limited to learning to defer.**\n\n**Response:** While the proof techniques and methods may not extend directly to other settings beyond L2D, we believe our work connecting realizable $H$-consistency, $H$-consistency bounds, and Bayes-consistency could provide valuable insights into these consistency notions in other learning settings. In particular, these connections, along with our approach of constructively replacing indicator functions with smooth loss functions in the novel derivation of new surrogate losses from first principles, could help design loss functions that benefit from strong consistency guarantees in various scenarios.\n\n**Questions:**\n\n**1. Can constrained losses [1] be used as the base loss?**\n\n**Response:** That's an excellent question. We expect that the constrained losses can also be used to replace indicator functions in the deferral loss, based on a similar approach. Briefly, we expect that the first indicator function can be replaced by the standard constrained loss and the second indicator function can be replaced by a modified constrained loss. Establishing realizable $H$-consistency and $H$-consistency bounds for this new family of surrogate losses can be a very interesting future direction. We will elaborate on this insightful point brought up by the reviewer in the final version.\n\n**2. Lines 273-274: Can negative results be proven formally?**\n\n**Response:** We will seek to derive such counterexamples in the final version. This will involve carefully designing the conditional distribution, the expert, and the cost function to violate the more stringent condition for $H$-consistency in the additional cases due to the general cost function.", "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": "", "extra_scores": {}}]

Author rebuttal:
Dear reviewers,

We would like to express our appreciation for all your constructive suggestions and insightful comments. We have attached a PDF that includes additional experimental results for both the realizable case and the non-realizable case with general cost functions.

Figure 1 shows system accuracy versus training samples on a realizable mixture of Gaussian distributions in [Mozannar et al., 2023]. Our surrogate loss $\mathsf L_{\mathrm{RL2D}}$ with $q = 0.7$ and $q = 1$ are realizable $H$-consistent, while $\mathsf L_{\mathrm{CE}}$, $\mathsf L_{\mathrm{OVA}}$ and $\mathsf L_{\mathrm{general}}$ are not. This validates our theory.

Figure 2 shows system accuracy versus coverage on the HateSpeech dataset by varying $\beta$ in the general cost functions $c(x, y) = 1_{\mathsf g(x) \neq y} + \beta$. As $\beta$ increases, deferral algorithms yield solutions with higher coverage and decreased system accuracy. This is because $\beta$ controls the trade-off between expert's inference cost and accuracy. $\mathsf{L}_ {\mathrm{RL2D}}$ with $q = 1$ performs comparably to the surrogate loss $\mathsf{L}_ {\mathrm{general}}$, as both are supported by $H$-consistency bounds and Bayes-consistency with general cost functions. Our surrogate loss $\mathsf{L}_ {\mathrm{RL2D}}$ with $q = 1$ outperforms $\mathsf{L}_ {\mathrm{RS}}$ because the latter does not benefit from Bayes-consistency with general cost functions.

Meta-review: The authors make a strong theoretical contribution for the problem of learning to defer. They propose the first surrogate loss (in fact, multiple of them) that satisfies realizable H-consistency and Bayes-consistency. This resolves an open question from Mozanner et al.’s AISTATS 2023 paper. It should have large impact in the learning to defer community as researchers in this community can move beyond consistency. All reviewers are positive on this work. It deserves to be accepted. Congratulations
Decision: Accept (poster)