Two-Stage Learning to Defer with Multiple Experts
Authors: Anqi Mao
Christopher Mohri
Mehryar Mohri
Yutao Zhong
Venue: NeurIPS 2023 poster (2023)
Keywords: learning to defer
learning theory

Abstract: We study a two-stage scenario for learning to defer with multiple experts, which is crucial in practice for many applications.  In this scenario, a predictor is derived in a first stage by training with a common loss function such as cross-entropy.  In the second stage, a deferral function is learned to assign the most suitable expert to each input.  We design a new family of surrogate loss functions for this scenario both in the score-based and the predictor-rejector settings and prove that they are supported by $H$-consistency bounds, which implies their Bayes-consistency.  Moreover, we show that, for a constant cost function, our two-stage surrogate losses are realizable $H$-consistent. While the main focus of this work is a theoretical analysis, we also report the results of several experiments on CIFAR-10 and SVHN datasets.

Two-Stage Learning to Defer with Multiple Experts
Anqi Mao Courant Institute
Christopher Mohri Stanford University Stanford, CA 94305 smohri@stanford. edu
New York, NY 10012
aqmaoεcims nyu...... edu
Mehryar Mohri
Yutao Zhong Courant Institute New York, NY 10012 yutaoucims .ommmmmsyyyy nyu edu
Google Research & CIMS New York, NY 10011
mohri@google.co
Abstract
We study two-stage scenario for learning to defer with multiple experts, which is crucial in practice for many applications. In this scenario, a predictor is derived in a first stage by training with common loss function such as cross-entropy. In the second stage, a deferral function is learned to assign the most suitable expert to each input. We design a new family of surrogate loss functions for this scenario both in the bcsse-based and the predictor-rejector settings and prove that they are supported by H--consistnncy bounds, which implies their chyess-onssstency. Moreover, we show that, a constant cost function, our two-stage surrogate losses are realizable H-cconistent. While the main focus of this work is a theoretical analysis, we also report the results of several experiments on CIFAR-10 and SVHN datasets.
Introduction
Large language models (LLMs) have achieved remarkable performance diverse tasks across multiple domains, as reported in recent surveys [Wei et al., 2022, Bubeck et al., 2023]. However, their practical application faces two critical challenges: the occurrence of hallucinations, that is the generation of incorrect or misleading content, and an inefficient inference. Leveraging multiple experts can address both issues. To reduce hallucinations, predictor in uncertain instances and defer to one of the more complex and more accurate experts. To enhance efficiency, one can derive models of difffrrnnt sizes distilled from the original complex model and use one of these more streamlined versions, while deferring to the more complex and less efficient ones for suitable contexts. Both problems require assigning each instance the most suitable expert. This motivates the problem of learning to defer in the presence of multiple experts.
refrain from using the original
The scenario of single-stage learning to defer has been studied by several publications, starting with the foundational framework introduced by Cortes, DeSalvo, and Mohri [2016a,b, 2023] for learning reject and followed by series of studies on abstention and deferral [Madras et al., 2018, Raghu et al., 2019, Mozannar and Sontag, 2020, Wilder et al., 2021, Pradier et al., 2021, Keswani et al., 2021, Raman and Yee, 2021, Liu et al., 2022, Verma and Nalisnick, 2022, Charusaie et al., 2022, Cao et al., 2022, Verma et al., 2023, Mao et al., 2023f,b,c, Mozannar et al., 2023]. In the single-stage scenario, predictor and deferral function determining the best expert assigned to each input instance. However, in practice, a predictor such LLM is already available and retraining one in conjunction with a deferral function could be prohibitively costly: depending on its size and the amount of data used, retraining could take several weeks or months. Thus, the single-stag stage learning to defer scenario and its solutions often do not align with the practical challenges encountered in real-world applications.
learned simultaneously, with the deferral function
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Alternative post-hoc methods have been proposed to address the learning to defer problem. Okati al. [2021] proposed an iterative approach optimizing a predictor and a rejector over multiple epochs. Within each epoch, first the predictor is trained on points where its loss is lower than that of human expert; second, the rejector is fitted to predict which of the predictor or the human expert has a lower loss. Narasimhan et al. [2022] suggested a post-hoc correction to the single-stage learning to defer surrogate losses, specifically the cost-sensitive softmax cross-entropy (CSS) surrogate loss in [Mozannar and Sontag, 2020] and the one-versus-all (OvA) surrogate loss in [Verma and Nalisnick, 2022] for cases where they suffer from underfitting. However, as with the single-stage learning to defer solutions, post-hoc approaches do not apply to scenarios where an existing predictor, pre-trained using a standard classification loss function such as eross-entropy, is already available.
Can we derive principled algorithm for learning to defer with multiple experts in such scenarios? Which surrogate loss should we adopt and what consistency guarantee can we rely on? This paper deals precisely with these questions.
key criterion for surrogate losses in learning to defer is Bayss-consi [Zhang. 2004, Bartlett et al., 2006, Steinwart, 2007], that is minimizing the surrogate loss over the family of measurable functions leads to the minimization of the deferral loss. The surrogate losses proposed in [Mozannar and Sontag, 2020, Verma and Nalisnick, 2022] have been shown to be Bayes-consisterd for defer- ral. However,
is not relevant in learning tasks since the hypothesis set used, for example that of some family of linear functions or neural networks, never includes all measurable functions. Long and Servedio [2013] proposed a notion of realizable H-consistency, that is consis- tency associated with specific hypothesis set in the realizable scenario. Mozannar et al. [2023] recently showed that existing Bayes-consistent surrogate losses in [Mozannar and Sontag, 2020, Verma and Nalisnick, 2022] are not realizable KCcconistentt for learning with deferral, which can pose significant challenges when learning with a restricted hypothesis set H. even for simple linear models. Instead, they proposed new surrogate loss that is realizable H-consistent when H is closed under scaling. However, they also observed that the loss function of Madras et al. [2018], which is not Bayes-consistent, is actually realizable K-consistent. They acknowledged their inability to prove or disprove whether their proposed surrogate loss is sayes-consistent. Consequently, it has remained an open problem to identify surrogate loss that is both consistent and realizable-consistent.
In recent work, Verma et al. [2023] proposed the first Bayes-consistent surrogate losses in the scenario of single-stage learning to defer with multiple experts [Hemmer et al., 2022, Keswani et al., 2021, Kerrigan et al., 2021, Straitouri et al., 2022, Benz and Rodriguez, 2022]. This scenario is more attractive and significant in applications such as large language models, where multiple models are often available for deferral. However, the surrogate losses proposed by the authors do not benefit from realizable H--consistnccy, even in the single-expert setting, since they are straightforward generalization of those of Mozannar and Sontag [2020] and Verma and Nalisnick [2022].
Bayes- coyyss-onnsstennyy. or even realizable F--consistnncy for a specific hypothesis set HC, is an asymptotic property, and provides no guarantee for approximate minimizers since convergence could be arbitrarily slow. More favorable guarantees, known as H-coosistency bounds, were recently introduced for standard classification settings [Awasthi, Mao, Mohri, and Zhong, 2022b,a] These guarantees are upper bounds on the target estimation loss expressed in terms of the surrogate estimation loss. They are stronger and more informative guarantees than soyye--consisenccy and H-consistency because they are both hypothesis set-specific and non-asymptotic. More recently. Mao et al. [2023b] introduced new family of surrogate losses and algorithms for the general problem of single-stage learning to defer with multiple experts that benefit from strong H-consistency bounds.
Our contributions. We study two-stage scenario for learning to defer with multiple experts that is crucial in practice for many applications. In this scenario, a predictor is derived in a first stage by training with common loss function such as cross-entropy. In the second stage, deferral function is learned to assign the most suitable expert to each input. We design a new family of surrogate loss functions for this scenario both in the score-based setting (Section 3) and the predictor-rejecton setting (Section 4) and prove that they are supported by H--conistency bounds, which implies their Bayes-consistency. Moreover, we show that, for a constant cost function, our two-stage surrogate losses are realizable H-consistent, While the main focus of this work is a theoretical analysis, we also report the results of several experiments on CIFAR-10 and SVHN datasets (Section 5). We give comprehensive discussion of related work in Appendix A. We begin by providing some basic definitions and notation (Section 2).

---

2
Preliminaries
We consider the standard multi-class classification setting with an imput space X and a set of 2 2 labels y = [n]] where we use the notation [n]] to denote the set {1.....,.)) We study the scenario of learning defer with multiple experts, where the label set y is augmented with ne additional labels {n + 1,...,77 7 + ne corresponding to ne pre-defined experts hi...., In this scenario, the learner has the option of returning label y e y, which represents the category predicted, or a label y + j. j 2 1, in which case it is deferring to expert hj. This setting is referred to as the score-based setting [Mozannar and Sontag, 2020, Cao et al., 2022, Mao al., 2023f], since the deferral corresponds to extra ne scoring functions. An alternative setting is the predictor-vejector setting [Cortes et al., 2016a, 2023, Mohri al., 2023, Mao al., 2023c], where the deferral function selected from separate family of functions R. We introduce that setting and include the corresponding results in Section 4 for completeness.
We denote by [n ne] the augmented label set and consider hypothesis set H of functions mapping from X y to R. The prediction associated by h H to input X is denoted by h(x) and defined as the element in y with the highest score, h(x) argmax [e[nnn.] h(r, y). with an arbitrary but fixed deterministic strategy for breaking ties. We denote by Hall the family of all measurable functions.
The deferral loss function Laef is defined as follows for any h E H and (2,0) E xx
The Σ (x
(h, xr, 8) = on [n())([]
(1)
Thus, the loss incurred coincides with the standard zero-one classification loss when hxx), the label predicted, is y. Otherwise, when hxx) is equal to n +jj the loss incurred is (x(,))) y). the cost of deferring to expert hy. Let (x, v) = 11 - ec (r,y). We will denote by C 0 and 23 1 finite lower and upper bounds the cost cy. that is (x, y) E [c ē, for all (x, Xxx x y. There possible choices for these costs. Our analysis for Theorem 1, Corollary 2, Theorem 6 is general and requires assumption other than their boundedness. One natural choice is to define cost Cj function of expert hy's inaccuracy, for example cz y) = a, (n))= + Bj. with aty, Bj O, where (x) is the prediction made by 1yth for input x. Typically, the hyperparameter oj has two potential values: zero one. When og is set one, the first term of the formulation pertains to the inaccuracy of expert expert hy. Conversely, with Og set to zero, the first term vanishes, focusing solely on the inference cost. Theorems 5 and 7 are analyzed under this assumption. The By in the second term corresponds to the inference cost incurred by expert h.j.
many
Given distribution D over X y, we will denote by EL (h) the expected deferral loss of hypothesis E H. EL... (h) E( LaLeee (h, x. y)], and by Er... (HC) = inf &L... (h) its infimum best-in-class expected loss. We will adopt similar definitions for other loss functions.
Given a hypothesis set H., an K-consistency bound [Awasthi et al., 2021a,b, 2022b,a, 2023a,b, Mao et al., 20, Zheng et al., 2023, Mao et al., 2023a.g] for surrogate loss & of a target loss function & an inequality of the form
vh E H. Eeg (h) E)) Me, (H) s T(Ee, (h) Et, (3)) Me, (H)),
where I: RR + R. is non-decreasing function with ((0) = 0 and where Mc( is the minimizability gap for the hypothesis set H and loss function E. (H) is defined as the difference of the best-in-class expected loss and that of the expected pointwise infimum loss: Mc(H)) (H)) Ey [infAee [(,, x. y)]] - By the super-additivity of the infimum, the minimizability gap is always non-negative. The minimizability gap vanishes when the best-in-class error E (H) coincides with the Bayes error E (Han), in particular when H(= HAn [Awasthi et al., 2022a.b].
Thus, the H-coonistency bound (2) relates the minimization of the estimation error for the surrogate loss & to that of the target loss lg in quantitative way. It a stronger and more informative guarantee than Bayss-con which implies Bayes-consistency, as can be seen by setting H( = Han-
3

---

Table 1: Common surrogate losses standard multi-clase classification.
Name
Formulation
Sum exponential loss
eexp (h, n. v) Egy Ma Ma..)))F((z..)))
Multinomial logistic loss
flog (h, 2., = log Ev Eveyutor (b(n)))((a))))))
B(r,00
Generalized cross-entropy loss
Roe (1, ,.,y)
. (0,1).
Evtrurro chicars/) cl(eav))
Mean absolute error loss
Euae (,, x. x)
3 Two-stage H-consistent surrogate loss
In this section, we consider an important two-stage scenario for learning defer with multiple experts. This is critical scenario in practice for many applications where predictor is already available, as a result of training with a loss function l supported by H-consistency bounds, such as the logistic loss (first stage). The logistic loss coincides with the cross-entropy loss when softmax activation is applied to the output of neural network. The problem then consists of learning deferral function (second stage) to assign the most suitable expert to each input instance.
We first design show that our surrogate losses benefit from H--consisencyy bounds (Section 3.2). As a by-product, we prove H-consistency bounds in standard multi-class classification, where H denotes hypothesis sets with fixed scoring function (Section 3.3). These bounds have not been studied before and can be of independent interest in other consistency studies. Moreover, we show that, for a constant cost function, our two-stage surrogate losses are realizable H-coonistent (Section 3.4).
family of surrogate losses for this two-stage scenario (Section 3.1). Next,
3.1 General surrogate losses
hypothesis set H of functions mapping from X [n ne] to I can decomposed as H HGp x HCa, where Hpp denotes the hypothesis set spanned by the first n scores, used for prediction, and H. the hypothesis set spanned by the final ne scores, used for deferral. Thus, any h e H can be written as a pair h (hp: ha) with hp e Hp and ha H(g
Let f be surrogate loss for standard multi-class classification with n classes. We consider the following two-stage scenario: in the first stage, hp is learned using the surrogate loss f in the second stage, ha is learned using a surrogate loss Lt,. that depends on the prediction function hy learned in the first stage.
To any ha E Ha. we associate a hypothesis ha defined over (n, 1) classes (0, 1,.., nee) by ha(x, 0) maxgey hep (x, y), that is the maximal score assigned by hp to its predicted label, and Ta)(r = ha(a,)) for [ne]. We can then define our suggested surrogate loss for the second stage as follows:
The Lng (ha. = (2 0) Σ (a(()))))(haa,, 3=1
where (z(Fs, x. is surrogate loss for standard multi-class classification with (ng + 1) categories (0, 1...., me... Intuitively, the indicator term Ix(z))n= in the deferral loss (1) penalizes ha(x, when it has a small value. Similarly, for standard surrogate loss (2 (,,, such as the logistic loss, it penalizes ha when it has small value well. In Table 2, we present summary of examples of such second-stage surrogate losses, where & is selected from common surrogate losses in standard multi-class classification defined in Table 1. A detailed derivation is presented in Appendix B.
From the point of view of the second stage, x + ha(2 (z. 0) max,ey (x, B) is a fixed function. We will denote by H. the family of hypotheses X {0, 1,... ... n.) + RR whose first scoring function, Ta 0). is fixed and not to be learned in the second stage.
Our formulation bears some similarity with the design of a surrogate loss function for rejectors in [Cortes et al., 2016a, 2023] for learning with rejection in binary classification, where the cost is

---

constant. However, our surrogate loss is tailored to accommodate a general cost function depending on both and y for deferral, in contrast with constant one, and it allows for multiple deferral options, as opposed to only one rejection option.
3.2 H- C-consistynyyy bounds for two-stage surrogate losses
In this section, we provide strong guarantees for two-stage surrogate losses, provided that the first- stage loss function & admits an -o-consistency bound, and the second-stage surrogate lz admits an Ha-consistency bound.
Theorem (H-consistencyy bounds for score-based two-stage surrogates). Assume that & admits an Ho-conniiy bound and l2 admits an Ha-consistency bound with respect to the multi-class zero-one classification loss fo-1 respectively. Thus, there are non-decreasing concave functions I' and 22 such that, for all ltp HHp and has H.d have
Elg (hp) Eio (IGp) Mia- (H₂) s (EC,
Me, (3Gp) Eia- (Fa) Eto (Ha) Mi (F(a) s 12 (e,, (ha) E (Ha)) + Mr, (T(.)
Then, the following holds for all 6 HC:
ELA (h)
(I() (
Etatt
Me (H)
ELAP (ha) EL., (Ha) + Menn (Ha))
<TI(EE, (hpp Eú (H₂) + Me, (Hp)) 1
Cj D2
Σラ 2z
Furthermore, pocttont (1 Eド=1 2i)
and
can be removed when 22 linear.
Σ 2
The proof is given in Appendix D. It consists of expressing the conditional regret of the deferral loss as the sum of two regrets, first by minimizing ha for fixed hg and then by minimizing hp- Subsequently,
show how each regret can be upper-bounded in terms of the conditional regret of each stage's s surrogate loss, leveraging the Kp-consistency bound of l, and Ha-coosisteneyy bound of l2 with respect to the zero-one loss. This, in conjunction with the concavity of functions T1 and T2, establishes our H-consistency bounds.
Thus, the theorem provides a strong guarantee for the two-stage surrogate losses. A specific instance of Theorem I holds for the case where Eú, (Hpp) Ex (Han) and et., (Ha) = Ei,,, (Han), ensuring that the Bayes-error coincides with the best-in-class error and, consequently, Me, (HGp) = ML.,, (H2) = 0. Given Theorem and the non-negativity property of Ma (H), we can derive the following corollary.
Corollary 2. Assume that f satisfies the same assumption as in Theorem 1. Then, for all h H and any distribution such that E7, (H₂) E72 (Han) and ET.,, (Ha) EL,, (Han), we have
2j EL,, (ha) EiAp (H.d)
ELas (h) - Ei (3)) s (EE, (hip) )- E7, (H₂))
1
Σ j-1
T2
Ejs
where the constant factors E1 3j) and Ens can be removed when P2 is linear.
Corollary 2 implies that when the estimation error of the first-stage surrogate loss, &e, (hpp - Eú, (Hp). is reduced to e and the estimation error of the second-stage surrogate loss, EL,,, (ha) - Ein, (Ha)), reduced to c2, the estimation error of the deferral loss, EL (h) Ei (H), is upper-bound by
(i(61)
1
Cj j-1
Σ
T2
The common surrogate losses mentioned earlier all satisfy the first-stage requirement; however; was unclear if they would meet the second-stage criterion since the Ha-consistency bound for hypothesis sets H. with a fixed first scoring function. This has not been previously studied in the literature. In the next section, prove for the first time that common multi-class surrogate losses,
5

---

Table 2: Examples for score-based second stage surrogate losses (3).
22
Lng
foxp
(,,(()) Dxe) é cha, maxyer M(x.))
E (1) Ei
eh(en h(an-))) + emassee b(2.)) (acesaa--((aaan))
flog
-Ily(t))-y log
man Mei))
Σnn C( 9) log
shloress)
min Menn +2n4 ehternnts guatyyy A(x.))
2gee
1n,(4)=0
Ejn (a.
gely Men ch(cnees)
fmae
1n,(4))0
such as the logistic loss, satisty this requirement and can be incorporated into both the first and second stage. Hence, based on [Mao et al., 2023h, Theorem I] and Theorem 3 in Section 3.3, when using
logistic loss in both stages, the concave functions are [t) = (t) = 22t, and thus Corollary 2
yields the following FC-consist bound:
ELA (ha) ELap (Hd)
ELAer - (30) V2(E E7 (3G))
2
1
Σ j-1
3
E
In particular, the bound implies the Bayes-consistency of the two-stage surrogate loss when Ej lg llog. Similarly, for other choices of & and Eg defined in Table 1, the two-stage surrogate loss benefits from an H-coonsistncy bound and also Bayes-consistent.
3.3 H-consistency bounds for standard surrogate loss functions
In this section, we seek to derive H-consistency bounds for common surrogate losses defined in Table I in the standard multi-class classification scenario. Recall that the first scoring function of hypotheses in H.g is the function max (, ()) Here, for any given function À mapping from X to I. we define the hypothesis set H augmented by À in similar way, that is any h H we associate hypothesis T H defined by T( 0) = X(x) and 5) h) for j 2 1. These H-consistency bounds offer strong guarantees when the loss functions in Table are used in the second stage of We believe that these results are of independent interest and can admit other applications in the study of H-cconsistnccy bounds. As with [Mao et al., 2023h], we assume that the hypothesis
the two-stage learning to defer surrogate losses (3) instantiated in Table
H is symmetric and complete. A hypothesis set is said to be symmetric if there exists a family F of functions f mapping from X to I such that {[h(z. 1)....,h((,,,... n)]: h e H{} = (x) ........ fn fi...... fn F). for any x E X. A hypothesis set H is said to be complete if the set of scores it generates spans R, that is, (h(x,y): e H} = IR, for any (x. y) X x y.
Note that for a symmetric and complete H, the associated H. is not symmetric and complete. Therefore, the proof of Mao et al. [2023h] cannot be generalized to our setting. Our proofs are presented in Appendix zero-one loss by that of a surrogate loss. To achieve this, we upper bound the minimal conditional surrogate loss by the conditional loss of a carefully constructed hypothesis in H( denoted by hy. The resulting softmax Sr of this hypothesis only differs from the original softmax 8 corresponding to h on exactly two of the labels.
We give a new method for upper bounding the conditional regret of the
Theorem 3 (H-consistency bounds). Assume that H. is symmetric and complete. Then, for any function X mapping from X to TR, hypothesis in the associated hypothesis set H and any distribution, the following inequality holds:
Eto (T)) Eia. (H) S (TEE((T) (H) Mc(H)) Me, .H).
where r(() 21 for & bing or loxpi T(1)= /2(n + 1)a for & = Egrei and r(l) (n 1) for L L Lmac-
Let us underscore that our proof technique is novel and distinct from the approach used in [Mao et al., 2023h]. Their method is tailored for hypothesis sets where each score can span across R. This is not applicable in context where the hypothesis set adheres predefined scoring function.

---

In their proof, to set an upper bound on the estimation error of the zero-one loss using that of the surrogate loss, they select an auxiliary function hi for any hypothesis h. This function is contingent on the distinct scores of h. Subsequently, the authors choose an optimal μ to set these bounds. Nevertheless, if any of h's scores are fixed, an optimal 1 does not exist, preventing the establishment of a meaningful bound. Instead, our new proof method overcomes this limitation by choosing dp based on the softmax, as the softmax corresponding the label zero can still vary due the influence of changes in other scores, even when the scoring function on label zero is fixed.
3.4 Realizable H--oonisttnncy
Recently, Mozannar al. [2023] showed that even in the straightforward single-expert setting, existing Bayes-consistent single-stage surrogate losses [Mozannar and Sontag, 2020, Verma and Nalisnick, 2022] not realizable H-consistent [Long and Servedio, 2013, Zhang and Agarwal, 2020] for learning with deferral. This can pose significant challenges when learning with a restricted hypothesis set HC, even for simple linear models. Instead, they proposed a new surrogate loss that is realizable H--consistent when H is closed under scaling, meaning that it satisfies the condition é H( Th JC for all in the set of real numbers. However, they stated that they could not prove or disprove whether their proposed surrogate loss is Bayes-consistent Consequently, it has become crucial identify a surrogate loss that is both consistent and realizable-consisten,, which has remained an open problem.
Definition (Realizable H-cconsitenccy). ). A surrogate loss L is considered a realizable H-consistent loss function for the deferral loss Laet if. for any distribution that is K-realizable, that is, there exists a zero loss solution h H with ELa (h") )- = O, optimizing the surrogate loss results in obtaining the zero-error solution:
E
12
(Lace((1,))) -
Eiaet (F)
DO
0.
In the following result, we show that our two-stage surrogate losses are realizable K-consistent. Combined with their Bayes-consistency properties, which have already been established in Section 3.2, we effectively find surrogate losses that are both Bayes-consistent and realizable consistent in the multi-expert setting, including the single-expert setting as a special case. For simplicity, here, we study the case where E = l2 flog. similar proof holds for other choices of l and &z defined in Table 1. The proof is included in Appendix F.
Theorem (Realizable H-consistency for score-based two-stage surrogates). Assume that H. is closed under scaling and cy (x = 33, V y) E X x y. Let & and lg be the logistic loss. Let ha be the minimizer of Ee, and ha be the minimizer of ELi, such that ELA, (ha) ming EL,, (ha). Then, the following equality holds for any (H, 3.) -realizable distribution,
ELat (h) = 0, where h h
Theorem 5 suggests that when the estimation error of the first-stage surrogate loss, E,, (h
e7, (Hp)) 1-+000
0, and the estimation error of the second-stage surrogate loss, EL.p (h2)
EL,, (H())
71++0000
O, the estimation error of the deferral loss, &L (h") EL (H) n 0.
This result demonstrates that our two-stage surrogate losses are not only Bayes- but also realizable H--consistent when only the inference cost (3,) exists.
4 Predictor-rejector setting
The results of the previous sections were all given for the score-based setting. We note that another popular setting in learning with deferral/abstention is the predictor-rejector setting [Cortes et al., 2016a, 2023], where the deferral corresponds to a separate function R instead of extra scores. For completeness, we introduce this setting well. Here too, design family of two-stage surrogate losses benefiting from both connsisccyy bounds and realizable consistency. For simplicity, we overload the notation with score-based setting based on the context.
Let H. be a hypothesis set of prediction functions mapping from y to IR. The label predicted for x X using hypothesis f HC is denoted by h(z) and defined as one with the highest score,
7

---

Table Examples for predictor-rejector second-stage surrogate losses (5).
Ln,
lexp
In(x)-y DEi e e-T((a) + Zj-1
(x,,1) [ (((())r((m)) + c
gT)(())
foog
-Ih(z)=0 log
Σラー Cj (2, log
1+ 1+ (
1+ (-r()))
1+ (y
lzce
Ih(x)=y
Σnn (1,
1+ 1+ ex((())
lma In(w)=y
Ens (z v)
1-20 c (15)
1+2.01 C-T
h(x) argmax yey h(x, with an arbitrary but fixed deterministic strategy for breaking ties. Let
R be family of deferring functions mapping from X to IR"', where ne is the number of experts. e R is used defer the prediction (1,ū(z, - (2, 3j.33 3 > 0 and hy is the prediction of the jth expert. The 33 in the second term corresponds to the inference cost incurred by expert hj. Let ro 0 and define r(z) 0 if (o( mmijee[..] Ty (z); otherwise, r(x) argminga[m.]] (x)), with arbitrary but fixed deterministic strategy for breaking ties. The learning defer loss Ldet with ne experts is defined follows for any (h,r) H x R and (x, v) E Xxx x y:
input to the jth expert h2 if ry (x) & 0 and (z) < min (-1,ee ra()), in which case a cost ey (T, =
A deferral
(r1.-.., Tun) the
(1- 1-
is incurred with 0 < e $ S S 1. A natural choice of the cost is ey [z, y) = a, (a))ay + 33, where
Laet (h,r,2,0) = In(e) ( + Σ (x( ((()=--- j=1
(4)
Given a distribution D over X x y, we will denote by EL (h, r) the expected deferral loss of a predictor h E H and deferral r R, E (h, ((r.)) Lie (h, ( r, 1, and by EL (H. infret ELa r), its infimum best-in class expected loss. We will adopt similar definitions for other loss functions. We denote by ML(K, the minimizability gap for hypothesis sets (H, and a loss function L.
& (H,,)) Eg [iifffee,, Bajer [h,, (,,,,,,,
Let & be surrogate loss for standard multi-class classification with classes. We consider the following two-stage scenario: in the first stage, a predictor h is learned using the surrogate loss f in the second stage, is learned using surrogate loss L,, that depends the prediction function learned in the first stage.
To any e R, we associate hypothesis 7 defined over (n. + 1) classes 1, n by F(z, 0) 0. that is zero scoring function, and F(x,j) (x) for je e [ne]. We can then define our suggested surrogate loss for the second stage:
(r,r, x. v) = (2 0) + Σ (x,
Here, x),) is surrogate loss for standard multi-class classification with (n + 1) categories (0, 1..1....,7 me]. Intuitively, the indicator term 1,(=)); in the deferral loss penalizes (z) when it has a large value. However, a standard surrogate loss (F,,,,, such as the logistic loss penalizes F(x,j) when it has a small value. This is why we use a negative sign in the definition of maintain consistency between the definitions of Ln and Laef. In Table 3, we present summary of examples of such second-stage surrogate losses, where lg is selected from common surrogate losses in standard multi-class classification defined in Table 1. A detailed derivation is presented in Appendix C.
From the point of view of the second stage, we will denote by R the family of hypotheses 7:X (0, 1,...., n..) R whose first scoring function, 7(; 0). is zero function and will not be learned in the second stage. We will provide strong guarantees for two-stage surrogate losses, provided that the first-stage loss function & admits an H-consistency bound, and the second-stage loss function & admits an R-consistency bound.
Theorem
connisseeyy bounds for predictor-rejector two-stage surrogates). Assume that y admits an H--oonistencyy bound and &g admits an R-consistency bound with respect to the clati- zero-one classification loss Eo-1 respectively. Thus, there non- non-decreasing concave
8

---

functions 11 and 122 such that, for all h é H and F R, we have
E (h) Eo. (Ht) + Me.. (9)) s (rriii (h) 22 Mr, (3C)
1 (7) Eig (R) Me. (R) s (E (T) (R) MM, (R)
Then, the following holds for all h E HC and e R:
ELSer (h, r) EL (H, + Maaa (H.
EL ET, (R) + MLL., (R)
$ sTi(Ee, (h) E7, (H) Me, (H)) 1+
Σ oj j=1
P2
E--1 Sz
where the constant factors (1 ددز Cj) and 2
can be removed when T is linear.
As with the score-based setting, specific instance of Theorem 6 holds for the case where & (H) Et, (Hau) and et, (R) = Ei, (Ran), ensuring that the Bayes-error coincides with the best-in-class error and, consequently, Mr, (HO) = M,,,(.. = O. In these cases, when the estimation error of the first-stage surrogate loss, ετ, (h) Et, (H(), is reduced 61, and the estimation error of the second-stage surrogate loss, ε (r) EL, (R), is reduced to 62, the estimation error of the deferral
loss, ELaor (h,r) EL (H, is upper bounded by
Ti(e)) +
Σ J=1
P2
E2
The 2ー
Next, show that two-stage surrogate losses are realizable RHonssccnsittent, We say that the distribution is -eela)-realiz,,be,, there exists zero error solution (h",r*) e H x R with ELa (hi rr*) ++ =0. O.
Theorem 7 (Realizable (H, -.).nss-oosssseeec for predictor-rejector two-stage surrogates). As- sume that H and R is closed under scaling and cx(x,)) By. (xx eX y. Let l and E be the logistic loss. Let h be the minimizer of Ee, and i be the minimizer of ELg- Then, the following holds for any (H, R) -realizable distribution,
ELast (h, 0.
The proof is included in Appendix H. Theorem 7 suggests that the two-stage surrogate loss is realizable consistent: when the estimation error of the first-stage surrogate loss E,, - Ej (H( -2-
0, and
the estimation error of the second stage surrogate loss L,, (rn) Et (R) +2 0, the estimation
error of the deferral loss, &Le (hm, Ei (H, n-++00 By Theorem 6 and Theorem 7, in the predictor-rejector setting, we also effectively find both Bayes-consistent and realizable consistent surrogate losses with multiple experts when only the inference cost (3,) exists.
Note that while Sections 3 and 4 both propose new two-stage algorithms based on H-consistent surrogate losses, they differ in an important way. Section learns with deferral in a score-based framework, where deferral is associated with extra scores, In contrast, Section 4 learns with deferral predictor-rejector setting, where deferral corresponds to a separate function. These represent two distinct learning frameworks that have been studied in the literature. Deriving consistent surrogate losses in the predictor-rejector setting has historically been challenging for traditional single-stage scenarios, leading many opt for the score-based approach.
We should also highlight that our F--ooniittecyy bounds in Theorems and can be used derive finite sample estimation bounds for the minimizer of the surrogate loss over a hypothesis set H. This is achieved by upper bounding the estimation error of the minimizer of the surrogate loss using standard Rademacher complexity bounds (see [Mao et al., 2023h]).
5 Experiments
In this section, we report the results of our experiments on CIFAR-10 [Krizhevsky, 2009] and SVHN [Netzer et al., 2011] datasets to test the effecttivness of our proposed algorithms for two-stage

---

Table 4: Accuracy of deferral with multiple experts: mean standard deviation over three runs.
Dataset
Base cost
Base model
Single expert
Two experts
Three experts
SVHN
X
91.12 70.56
91.85 + 0.01%
92.77 * 0.02%
93.30 # 0.02%
CIFAR-10
X
72.63 + 0.20%
75.84 # 0.35%
77.68 # 0.07%
SVHN V
91.12
91.66 + 0.01% %
92.05 # 0.10%
92.19 + 0.03%
CIFAR-10
V
70.56
71.73 + 0.06%
72.31 # 0.31%
72.42 # 0.12%
learning to defer with multiple experts. We evaluated the overall accuracy of the learned pairs of predictor and deferral model across different scenarios involving varying the number of experts, where the predictor is pre-learned in the first stage and the deferral is subsequently learned using our proposed surrogate loss. We find that as the number of experts increases, the overall accuracy of the learned pairs also increases, in both scenarios with zero and non-zero base costs. This observation highlights the significance of using a multiple expert framework in our approach and the effectiveness of our surrogate loss within the framework.
We used ResNet architectures [He et al., 2016] for the prediction model, the deferral model and expert models. More precisely. we used ResNet-4 for both the predictor and the deferral. We adopted three expert models: ResNet-10, ResNet-16. 16, ResNet-28 with increasing capacity. For training, used the Adam optimizer [Kingma and Ba, 2014] with a batch size of 128 and weight decay 1 x 10"4. Training was run for 15 epochs for SVHN and 50 epochs for CIFAR-10 10 with the default learning rate. No data augmentation was used in our experiments. We used our two-stage surrogate loss (3) with the logistic loss é fog to train the deferral model ResNet-4, with a pre-learned predictor ResNet-4 trained using logistic loss. A check mark indicates the presence of base cost in the cost function, whereas cross mark signifies its absence. We first set the cost function to be 1l, (#)ay without base cost. Next, for the experimental results shown in the last two row of Table 4, we chose base costs f3 associated with each expert model as: 0.1, 0.12, 0.14 increasing with model capacity for SVHN and 0.3, 0.32, 0.34 increasing with model capacity for CIFAR-10. A base cost value that is close to the misclassification loss can strike a balance between improving accuracy and maintaining the ratio of deferral. We observed that other neighboring values lead to similar results. Note that the accuracy here refers to the overall accuracy of the learned pairs of predictor and deferral model. is related to the deferral loss. Specifically, in the absence of the base cost, the accuracy aligns precisely with one minus the expected deferral loss. The results of Table 4 demonstrate the effectiveness of our proposed algorithms for two-stage learning to defer with multiple experts.
To the best of our knowledge, our study pioneers the exploration of a two-stage learning approach for deferral, a framework that is essential in numerous practical applications. Thus, we are unaware of any established baselines within this context.
is important to underscore the differences between our learning scenario and those presented in [Okati et al., 2021, Narasimhan et al., 2022]. While both of them involve two phases, their methodolo- gies are considerably different from ours. Okati et al. [2021] required conditional probabilities paired with loss estimates from the expert-a component not available our framework, as emphasized by Mozannar et al. [2023]. On the other hand, Narasimhan et al. [2022] proposed a post-hoc correction for single-stage learning to defer surrogate losses. This approach, however, is not applicable to pre-trained predictor from the standard multi-class classification. In contrast, our work focuses on enhancing the pre-trained predictor within the standard framework.
A limitation of our study is that the cost function used within the deferral loss is not fixed, and is typically determined through cross- moss-validation in practice. There exists potential introduce principled method for selecting the cost function, which we have reserved for future research.
Conclusion
We introduced novel family of surrogate loss functions and algorithms for a crucial two-stage learning to defer approach with multiple experts. We proved that these surrogate losses are supported by H--consitenccy bounds and established their realizable JC-consistnncy properties for constant cost function. This work paves the way for comparing different surrogate losses and cost functions within our framework. Further exploration, both theoretically and empirically, holds the potential to identify optimal choices for these quantities across diverse tasks.
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 in Neural Information Processing Systems, 2021a
Awasthi, A. Mao, M. Mohri, and Zhong. A finer calibration analysis for adversarial robustness. arXiv preprint arXiv:2105.0 2021
P. Awasthi, A. Mao, M. Mohri, and Y. Zhong. Multi-class J[-consisteney bounds. In Advances in neural information processing systems, 2022a.
Awasthi, A. Mao, M. Mohri, and Y. Zhong. H-consistency bounds for surrogate loss minimizers. In International Conference on Machine Learning, 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, 2023a.
P. Awasthi, A. Mao, M. Mohri, and Y. Zhong. DC-programming for neural network optimizations. Journal of Global Optimization, 2023b.
G. Bansal, B. Nushi, E. Kamar, E. Horvitz, and D. S. Weld. Is the most accurate ai the best teammate? optimizing ai for teamwork. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 1 11405-1 1414, 2021.
P. L. Bartlett and M. H. Wegkamp. Classification with reject option using hinge loss. Journal of Machine Learning Research, 9(8), 2008.
L. Bartlett, M. Jordan, and J. D. McAuliffe. Convexity, classification, and risk bounds. Journal of the American Statistical Association, 101(473):138-155 2006.
N. L. C. Benz and M. G. Rodriguez. Counterfactual inference of second opinions. In Uncertainty in Artificial Intelligence, pages 453-463. PMLR, 2022.
S. Bubeck, V. Chandrasekaran, R. Eldan, J. Gehrke, 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. 12712, 2023.
Y. Cao, T. Cai, L. Feng. L. Gu, Gu, B. An, 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.
N. Charoenphakdee, Z. Cui. Y. Zhang, and M. Sugiyama. Classification with rejection based on cost-sensitive classification. In International Conference on Machine Learning, pages 1507-1517, 2021.
M.-A. Charusaie, H. Mozannar, D. Sontag, and S. Samadi. Sample efficient learning of predictors that complement humans. In International Conference on Machine Learning, pages 2972-3005, 2022.
C. Chow. An optimum character recognition system using decision function. IEEE C., 1957.
C. Chow. On optimum recognition and reject tradeoff. IEEE Transactions information theory, 16(1) 1:41-46, 1970.
C. Cortes, G. DeSalvo, and M. Mohri. Learning with rejection. International Conference on Algorithmic Learning Theory, pages 67-82, 2016a.
C. Cortes, G. DeSalvo, and M. Mohri. Boosting with abstention. In Advances in Neural Information Processing Systems, pages 1660-1668, 2016b.
C. Cortes, G. DeSalvo, and Mohri. Theory and algorithms for learning with rejection in binary classification. Annals of Mathematics and Artificial Intelligence, to appear, 2023.
11

---

A. De, P. Koley, N. Ganguly, and M. Gomez Nomez-Rodriguez Regression under human assistance. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 2611-2620, 2020.
R. El- Yaniv et 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 Artificial Intelligence and Statistics, pages 2179-2187, 2021.
R. Gao, M. Saar-Tsec,,nsky, M. De-Arteaga, L. Han, M. K. Lee, and M. Lease. Human-ai collabora- tion with bandit feedback. arXiiv preprint arXiv:2105. 10674, 2021.
Y. Geifman and R. Yaniv.. Selective classification for deep neural networks. In Advances in neural information processing systems, 2017.
Y. Geifman and R. El-Yaniv. Selectivenet: A deep neural network with an integrated reject option. In International conference on machine learning, pages 2151-2159, 2019.
Y. Grandvalet, A. Rakotomamoniy. J. Keshet, and S. Canu. Support vector machines with a reject option. In Advances in neural information processing systems, 2008.
K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
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 arXiv:2206.07900 2022.
Hemmer, L. Thede, M. Vössing, J. Jakubik, and N. Kühl. Learning to defer with limited expert predictions. arXiv preprint arXiv:2.30..77366 2023.
R. Herbei and M. Wegkamp. Classification with reject option. Can. Stat., 2005.
S. Joshi, S. Parbhoo, and Doshi Velez. Pre-emptive learning-to-defer for sequential medical decision-making under uncertainty. arXiv preprint arXiv:2109.0633 2021.
A. T. Kalai, V. Kanade, and Y. Mansour. Reliable agnostic learning. Journal of Computer and System Sciences, 18851194,, 2012.
E. Kamar, S. Hacker, and E. Horvitz. Combining human and machine intelligence in large-scale crowdsourcing. In AAMAS, pages 467-474, 2012.
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 Al, Ethics, and Society, pages 154-165, 2021.
D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv: 1412.6980. 2014.
J. Kleinberg, H. Lakkaraju, J. Leskovec, J. Ludwig, and S. Mullainathan. Human decisions and machine predictions. The quarterly journal of economics, 133(1):237-29) 2018.
A. Krizhevsky. Learning multiple layers of features from tiny images. Technical report, Toronto University, 2009.
V. Kuznetsov, M. Mohri, and U. Syed. Multi-class deep boosting. Advances in Neural Information Processing Systems, pages 2501-2509, 2014.
Liu, B. Gallego, and Barbieri. Incorporating uncertainty in learning to defer algorithms for safe computer-aided diagnosis. Scientific reports, 12(1):1762, 2022.
12

---

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, Pitassi, and R. Zemel. Learning adversarially fair and transferable representations. arXiv preprint arXiv: 1802.000233330 2018.
A. Mao, M. Mohri, and Y. Zhong. H-consistency bounds: Characterization and extensions. In Advances in Neural Information Processing Systems, 2023a.
A. Mao, M. Mohri, and Y. Zhong. Principled approaches for learning to defer with multiple experts. arXiv preprint arXiv:2310.1477 2023b.
A. Mao, M. Mohri, and Y. Zhong. Predictor-rejector multi-class abstention: Theoretical analysis and algorithms. arXiv preprint mxXi:2310.11772,,20
A. Mao, M. Mohri, and Y. Zhong. H-consistency bounds for pairwise misranking loss surrogates, In International conference on Machine learning, 2023d.
A. Mao, M. Mohri, and Y. Zhong. Ranking with abstention. In JCML 2023 Workshop The Many Facets of Sefference-Bassedr Learning, 2023e.
A. Mao, M. Mohri, and Y. Zhong. Theoretically grounded loss functions and algorithms for score- based multi-class abstention. arXiv preprint 0rXiv:3310.1470,, 2023f.
A. Mao, M. Mohri, and Y. Zhong. Structured prediction with stronger consistency guarantees. In Advances in Neural Information Processing Systems, 2023g.
A. Mao, M. Mohri, and Y. Zhong. Cross-entropy loss functions: Theoretical analysis and applications. In International Conference on Machine Learning, 2023h.
C. Mohri, D. Andor, E. Choi, M. Collins, A. Mao, and Y. Zhong. Learning to reject with fixed predictor: Application decontextualization. arXiv preprint arXiv:2301.09044, 2023.
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 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 defer to humans. International Conference on Artificial Intelligence and Statistics, pages 10520-10555 2023.
H. Narasimhan, W. Jitkrittum, A. K. Menon, A. S. Rawat, and S. Kumar. Post-hoc estimators for learning to defer to an expert. In Advances Neural Information Processing Systems, 2022.
H. Narasimhan, A. K. Menon, W. Jitkrittum, and Kumar. Learning to reject meets ood detection: Are all abstentions created equal? arXiv preprint 23X1:2301111386 2023.
Y. Netzer, T. Wang, A. Coates, A. Bissacco, B. Wu, and A. Y. Ng. Reading digits in natural images with unsupervised feature learning. In Advances in Neural Information Processing Systems, 2011.
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 14:9140-9151, 2021.
M. F. Pradier, J. Zazo, S. Parbhoo, R. H. Perlis, M. Zazzi, and F. Doshi-Velez. Preferential mixture- -f-experts: Interpretable models that rely on human expertise as much as possible. AMIA Summits on Translational Science Proceedings, 2021:525, 2021.
13

---

M. Raghu, K. Blumer, G. Corrado, J. Kleinberg, Z. Obermeyer, and S. Mullainathan. The algorithmic automation problem: Prediction, triage, and human effort. arXiv preprint arXiv:1903. 2019.
N. Raman and M. Yee, Improving beaninngtt-deffe algorithms through fine-tuning. arXiv preprint 12X7:22112.1078,, 2021.
H. G. Ramaswamy, A. Tewari, and S. Agarwal. Consistent algorithms for multiclass classification with an abstain option. Electronic Journal of Statistics,
2018.
I. Steinwart. How to compare different loss functions and their risks. Constructive Approximation, 26(2):225-277, 2007.
E. Straitouri, A. Singla, V. Meresht, and M. Gomez- Rodriguzz Reinforcement learning under algorithmic triage. arXiv preprint arXiv:2109. 2021.
E. Straitouri, L. Wang, N. Okati, and M. G. Rodriguez. Provably improving expert predictions with conformal prediction. arXiv preprint arXiv:2201.12006, 2022.
S. Tan, J. Adebayo, K. Inkpen, and E. Kamar. Investigating human+ machine complementarity for recidivism predictions. arXiv preprint arXiv: 09103, 2018.
R. Verma and F. Nalisnick. Calibrated learning defer with one-vs-all classifiers. In International Conference on Machine Learning, pages 22184-22202 2022.
R. Verma, D. Barrejón, and E. Nalisnick. Learning to defer to multiple experts: Consistent surrogate losses, confidence calibration, and conformal ensembles. In International Conference on Artificial Intelligence and Statistics, pages 11115-1434, 2023.
J. Wei, Y. Tay, R. Bommasani, C. Raffel, B. Zoph, S. Borgeaud, D. Yogatama, M. Bosma, D. Zhou, D. Metzler, E. H. Chi, Hashimoto, O. Vinyals, Liang, J. Dean, and 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.
B. Wilder, E. Horvitz, and E. Kamar. Learning to complement humans. In International Joint Conferences on Artificial Intelligence, pages 1526-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. In Bernoulli, 2011.
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-85, 2004.
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, Bao, Y. Cao, C. Li, and Zhu. Revisiting discriminative vs. generative classifiers: Theory and implications. arXiv preprint 23X2:22302.02334 2023.
L. Ziyin, Z. Wang, P. P. Liang, R. Salakhutdinov, L.-P. Morency, and M. Ueda. Deep gamblers: Learning to abstain with portfolio theory. arXiv preprint arXiv:1907.00208, 2019.
14

---

Contents of Appendix
Related work
16
B Examples of two-stage score-based surrogate losses
17
Examples of two-stage predictor-rejector surrogate losses
18
D Proof of H-coonistencyy bounds for score-hased two-stage surrogate losses (Theorem 1)
19
E Proof of H-consistency bounds for standard surrogate loss functions (Theorem 3)
21
E.1 Multinomial logistic loss
21
E,2 Sum exponential loss
E,3 Generalized cross-entropy loss
24
E,4 Mean absolute error loss
26
Proof of realizable consistency for score-based two-stage surrogate losses (Theorem 5) 27
G Proof of (H, -conssittns bounds for predictor-rejector two-stage surrogate losses (Theorem 6)
27
H Proof of realizable consistency for predictor-rejector two-stage surrogate losses (Theo- rem 7)
29
15

---

A Related work
The scenario of single-stage learning to defer has been extensively explored in previous research. The initial studies focused on the problem of abstention and introduced various approaches such as confidence-busee abstention [Chow, 1957, 1970, Herbei and Wegkamp. 2005, Bartlett and Wegkamp, 2008, Grandvalet et al., 2008, Yuan and Wegkamp, 2010, 2011, Ramaswamy et al., 2018, Ni et al., 2019], selective classification [EI-Yante Yaniv et al., 2010, Wiener and EI- Yaniv, 2011, Kalai et al., 2012, Geifman and El-Yaniv, 2017, 2019, Ziyin et al., 2019, Acar et al., 2020, Gangrade et al., 2021]. predictor-reeector framework for abstention [Cortes et al., 201 6a.b, Charoenphakdee et al., 2021, Cortes et al., 2023, Mohri et al., 2023, Mao et al., 2023c], and a score-based setting for abstention [Mzannar and Sontag, 2020, Raman and Yee, 2021, Liu et al., 2022, Verma and Nalismick, 2022, Charusaic et al., 2022, Cao et al., 2022, Mao et al., 2023f, Verma et al., 2023, Mao et al., 2023b, Mozannar et al., 2023].
Another line of research is centered around the joint learning of prediction and deferral functions. Several publications by Madras et [2018], Raghu et al. [2019], Wilder al. [2021], Pradier et al. [2021], Keswani et al. [2021] delve into this topic, considering single-stage learning to defer and its variants. Additionally, the concept of learning to defer has been explored in different scenarios, including combining human and machine predictions, investigating human preferences, regression problems, reinforcement learning, and more [Kamar et al., 2012, Tan et al., 2018, Kleinberg et al., 2018, Bansal et al., 2021, De et al., 2020, Straitouri et al., 2021, Zhao et al., 2, Joshi et al., 2021, Gao et al., 2021, Mozannar et al., 2022, Hemmer et al., 2023, Narasimhan et al., 2023]. However, in practice, predictor such as LLM is already available and retraining one in conjunction with deferral function could be prohibitively costly: depending on its size and the amount of data used, retraining could take several weeks months. Thus, the single-stage learning to defer scenario and its solutions often do not align with the practical challenges encountered in real-world applications.
Alternative post-hoc methods have been proposed to address the learning to defer problem. Okati et al. [2021] proposed an iterative approach optimizing a predictor and a rejector over multiple epochs. Within each epoch, first the predictor is trained on points where its loss is lower than that of human expert: second, the rejector is fitted to predict which of the predictor or the human expert has a lower loss. Narasimhan et al. [2022] suggested post-hoc correction to the single-stage learning to defer surrogate losses, specifically the cost-sensitive softmax cross-entropy (CSS) surrogate loss in [Mozannar and Sontag, 2020] and the one-versus-all (OvA) surrogate loss in [Verma and Nalisnick, 2022] for cases where they suffer from underfitting. However, as with the single-stage learning to defer solutions, post-hoc approaches do not apply scenarios where an existing predictor, pre-trained using a standard classification loss function such as cross-entropy, is already available.
A key criterion for surrogate losses in the scenario of learning to defer is Bayes-consistency (also known as consistency) [Zhang, 2004, Bartlett et al., 2006, Steinwart, 2007, Mohri et al., 2018]. This property guarantees that minimizing the surrogate loss over the family of measurable functions leads to the minimization of the deferral loss. The surrogate losses proposed in [Mozannar and Sontag, 2020, Verma and Nalisnick, 2022] have shown to be Bayes- for deferral. However, Bayes- consistency is a property associated with the family of all measurable functions, which of course is considerably broader than the hypothesis sets typically used in learning algorithms, including linear hypothesis sets and the family of neural networks.
Instead, Long and Servedio [2013], Kuznetsov al. [2014], Zhang and Agarwal [2020] proposed notion of realizable K-consistency, that consistency associated with a specific hypothesis set the realizable scenario. Mozannar et al. [2023] recently showed that existing Bayes-consistent surrogate losses in [Mozannar and Sontag, 2020, Verma and Nalisnick. 2022] are not realizable J[-consistent for learning with deferral, which can pose significant challenges when learning with restricted hypothesis set HC, even for simple linear models. Instead, they proposed a new surrogate loss that is realizable K--consistent when H is closed under scaling. However, they also observed that the loss function of Madras et al. [2018]. which is not conessconssttent, is actually realizable HC-consistent. They acknowledged their inability prove disprove whether their proposed surrogate loss is Bayes-consistent. Consequently, it has remained an open problem to identify a surrogate loss that is both consistent and realizable-consisten..
In recent work, Verma et al. [2023] proposed the first Bayes-consistent surrogate losses in the scenario of learning to defer with multiple experts [Hemmer et al., 2022, Keswani et al., 2021, Kerrigan et al.,
16

---

2021. Straitouri et al., 2022, Benz and Rodriguez, 2022]. This scenario is more attractive and significant in applications such as large language models, where multiple models are often available for deferral. However, the surrogate losses proposed by the authors do not benefit from realizable H-consistency, even in the single-expert setting, since they are straightforward generalization of those of Mozannar and Sontag [2020] and Verma and Nalisnick [2022].
In summary, the problem of learning defer in single-stage scenario has been extensively studied, but it is often impractical in real-world applications. Post-hoc methods and surrogate losses have been explored, but the challenge remains to find surrogate loss that both consistent and realizable- consistent. Recent research has made progress in the scenario of learning to defer with multiple experts but has achieved realizable H-consistency even single-expert setting.
B Examples of two-stage score-based surrogate losses
Example: lz Loxps For lo (2(,,, (ha, Ev'oy - by (3), have
Ln, (ha,
Σ The (1
= = l2( 0) +
1=1
=1n,(x)=y Σ
Fa(s.//)) -F.(,,)) + Σ (z, Σ (
8'00
j-1
1/4j
= =1),(1)
"y E (a,,at)) max ((x,)) + ne
Σ (2,
Σ
ny
M(nnt)))((sattt)) + max h(x.g) -(x,))))((
Liml,se)
Example: lg loog. For 2,,,, = blog (ha, = log Everugos eaalass)) ). by (3), we have
La, (ha,)r,
= = 22(
j-1
(a)y log
Σ
Σ (2,
Σ
max Mxxy)
n1e
Memn-))
= =-In,(2)=g log
Σ
(5( v) log
emaxyryhaxy h(z,9) Eie ch(
emaxyyy 1(2,8) Eie ch(
f=1
Falini))
Example: lg = lzee- For (e x, v) = lzce (Fr, x. y)
a E (0,1),
Evenuoo oFala.)))
(3), we have
Ln, 2ha)
(n, (a +)+ Σ (z)
Tu((z,))
11,, a
+
1
Σ Egretuiis chu(
J-1
α
Everuios chhela.)))
1
max M(.w))
1 1-
=1
1
(x,
eaxx Ma.y) + En, (((,))))))
emaxyu k(z,0) + Em eh(z,tti)
a
17

---

Example: lo Emaes For (ha (ha, 2,
cholo,y)) Eveenooo cFatzsos by (3), we have
La, (h
= 22, 0)+ + (c,
cha(n.0)
chalto)
=o),(a)-y
1
Σ /=1
1-
EyetHufoy chelows))
Everupos challwa))
maxyyy h(x.1/)
= =1n,(1))=
Σ (, 1 j=1
emaxycy M(2291) + Din eh(z),tt)
eaxxcy Ma.s)) + Eni el(an)+))
C Examples of two-stage predictor-rejectrr surrogate losses
Example: l2 = loxp- For E2 (Tx Ey (22)) by (5), we have
Lx(r,a,y)
=2 Σ
-I((x)-y Σ (e
Σ
(x,
E (((n)))((a))
5+0
3=1
-I((a) e -x())
de Σ
+
The
(x,
Σ
(2(0))r())
1=1
j=l
Li=l,taj
Example: lo llog. For (2(F,2,0) flog (F, log Eyyeuioo -(x.)))(E)))) by (5), we have
Ln(r,,,))
Tee = =y (2(
Σ (F
-1(0)-y log
Σ -(anN\)-(xx1))
Σ
(,( log
Σ (add)
j-1
(EHHU(())
()))
=-1n(r)-y log
Σ (x, log
Ene e-ri(a)
1 En (<)(
j=l
Example: 6g lyco- For (2(F,x,,)) (F,
((,,))
ya a (0, 1), by (5),
Evesusos af(x.st
we have
Lr,r,,y))
(2F,,,00) Σ (1,0))
(a,0)
n
((a))
=Ila()=
1
Σ ((
Σ (x,)))
1-
Eyeryuoo (F(aN)) (t))
= 0
Σ
Eg (2,
nh r-((())
Σd, (-)((s)
j-l
a
18

---

((( Eoo enayy' by (5), have
Example: 82 Emac- For (2(r, em, =1
(,(r,2,))
- (( Σ [0
eP(2,0)
=II((o> (1- Eyeyutoo
Σ E 1-
E ef
Eyenuroo EyesuropeTTass)) eless) ers(x)
- 1 Ex (-)(
Σ (2,2) 1-1
1+ E+ EtE em(())
D Proof of H-consistency bounds for score-based two-stage surrogate losses (Theorem 1)
Theorem 1 (JC-consistencyy bounds for score-based two-stage surrogates). Assume that & admits an H consissestt bound and l2 admits an Ha-consistenccy bound with respect to the multi-class zero-one classification loss fg-1 respectively. Thus, there are den-eecrgg concave functions I and 22 such that. for all hp E K.pp and ha Ha, we have
Elo (hp) Eio (HG) Mia- (H₂) T2 (E,, (hp) E (H2) Me, (H(p) Eign (Fa)) Et. (Ha)) Mini (Ht)) s I2 Er, (ha) - E7 (Ha) + Mr, (T(
Then, the following holds for all H.
ELaa (h) - -Eiaas (H) Ma (H)
ELO, (ha) Ln, (Ha) + Minn (HCr)
The
sT <TI(Ee (hpp) E2 (JG,) + Me Me, (IG))) 1+
Σ j=l
ej
12
Σn- Cj
Furthermore, constant (1 Eiii 2i)
and
can be removed when 122 linear.
Proof. hf)) [n], then h(x) hx))). Thus, the learning to defer loss can be expressed follows:
Laet (aet(h, x, (h,
v) 1 nx))) In())<[m] Σ (x, In
= =I,,(
Σ c (2, Ln())=an
Let Co (x(xx)) u) = 1 (x))== Since h = (hm, ha), we can rewrite Elses (h) Eia (H) + Misa (H) as
ELLO (h) ELnn (3() MMais (H()
Ex CL (1, -)-- - -i (H,
Ex CLaw (h, inf CLia (h, + inf (Lan eLn (H, haedia
(6)
= Ex CLaar (h,
inf CLa (1, hacDla
+ Ex
inf CLio (h, - Ciac (H,
heeHfa
By (x.(x)))))
Let (Λ,
for any j (O...., ne). Note that p(r,)) :) is the probability vector on
3, Ejio (a.)))
the label space {0.... ne). For any h H. we define h as its augmented hypothesis: T((z.))
19

---

myx h(x,,))F((z, 1) 1), h(r,ne) = ne), By the assumptions, we have
Caa (h,
inf CLaar (h) hgetfa
E
(no(o)=y=<(a>44) [n(x))[[]
Cg(2,
inf E (n(())> [n(x)<[m]]
haeSla y
5=1
Σ ())
Σ Fa, () la- (1,
inf (e haeDfa j-0
$
(x,
x1
Σ ( a. )2 (2, inf haeSKa j-0
(2(
1-0
(By Ro-cossistency bounds of & under assumption, X maxyey (),,))
E Lop (ha, 2, v) infn Ey (Lnp (ha, 2,, v)
(1 8)
1'2
yy Ef=o Cg (z.
(T(1,))) Fsz En50 (1(2)1))
F. (a..))
Txx,,) max (xx and formulation (3))
CLIP (hd5
CLo, (H)
12
Σ (1:1)) T2 E=U
[E]=0 C (x,
T2 CLa, (ha,
Ciop (H(;
when P2 is linear
<
CLop (ha.ar) Cinp (Har.)
(1 Ent. 2z 2/22
otherwise
E
(E Ey Ef= (x [(r,))] s Σja 2j and I'2 is non-decreasing)
T2 (CLL He Te (ha,)
when 12 is linear
AC Deg (haia))
(1+ 2, 21'
otherwise
2j-1
and
inf CLoer (h, eraw (H)
haekaa
inf Claer haeDla
inf MeHK
Clas (1,
inf haelka
(n +
Tee
inf I "ppaC InG Σ (I, [((
inf E (no (I
haella y
inf inf ( NyE
Σ 1-1
hatHa
-min B (c)ce min E[c,(,,)]] je(r]
min
inf E EE[ (n,())))=) min Eles(a. AgEDA y
jobo y
E [[I)n<a))=]] inf E [[In,,ww= HEE
Cia. (hpp x) er,,, xH)
ACto- (hp,
I' (ACE, 2))
(By Hy-consistency bounds of l under assumption)
20

---

Therefore, by (6), we obtain
Laee (h) E + Mi (3()
Ex To CALL ace C scaa (ha,
] Ex [T (A (hp,
when 72 is linear
Seap, 2e (hara)
(1 2-=1 Ex 12
Ex (TCC, (hp, otherwise
T2 Fx ACL, sta Hea (h) +T (xx (BX(ACE, (hps
when I2 is linear
(1 Enار ra'
Ex ACen (ha (Bxx AC Mr, (hp, x)))
otherwise
E
(I' and 12 are concave)
(1p) (Hp) Mr, (Hp)) T22 (ELL (hd) - Ei,p (H() + MLn, (Ha))
when F2 linear
(lyy (ha) (9Ga)+Dran, (9Ga)
Ti TT(eE, - ( Me (Hp)) (1+ دزニ Cij [2
otherwise,
2
which completes the proof.
E Proof of H-ccossisenccy bounds for standard surrogate loss functions (Theorem 3)
Recall that for hypothesis h: x RR define ìt as its augmented hypothesis: T(:-0) X, 1,,(; M(2, (),,..,)((,1)))) h(r,,, n) with some constant À IR. We define H the hypothesis set that consists all such augmented hypotheses of K: H ( h e H}. The prediction associated by Te E H. to input x e X is denoted by h(z)) and defined as the element in y u (0) with the highest score, h(x) (r ((x, 3). with an arbitrary but fixed deterministic strategy for breaking ties. For any x e X and label space y U {0), we will denote, by H(x) the set of labels generated by hypotheses in H. H(x)= (h(z): h e H}. By [Awasthi et al., 2022a, Lemma 3] with label space y (0} and a conditional probability vector p(x,,) on y U {0), the minimal conditional floss and the corresponding calibration gap can be characterized as follows.
Lemma 8. For any X. the minimal conditional fo-1-rish and the calibration gap for fo-1 can be expressed as follows:
Cia (x) = max p(r 9)
yeH(z)
ACta (h,x) max p(z, v) - (x., h(z)). yeH(xx)
E.1 Multinomial logistic loss
Theorem (F-consistency bound for multinomial logistic loss). Assume that H is symmetric and complete. Then, for any X RR, hypothesis To K and any distribution,
E1o (h) 8% (K) s V2 E (h))
E
(H) Mewu (H))² -Mo (H).
Proof. For the multinomial logistic loss llog. the conditional bog-risk can be expressed follows:
-(aas'))((z2))) )-- )
Cene (h,x)) Σ p(z, y) log
Σ
Σ yEBu(O)
p(z. y) log(S)z, v))
yEyofot
[0. 1] for any y y (0) with the constraint that where we choose the label with the same deterministic strategy for breaking ties as that of h(x)). For any T such that h(x)) Mmnax and z X, by the symmetry and completeness of H, we can always find a family of hypotheses
where we let 8(x,y) Ev-nuto e Eyeyu(o) 8(I,g) = 1. Let Vmax = ye p(x,y),
21

---

(Tyy u (maxx)))))) ((z, H such that (,(x,,)=
Exicucos Fiueanrs take the following
values:
8(2,y)
y {ylmax h(x2)
S (x, =
8(x, Vmuxx) +
if y h(x)
8(x, h(x))(()+
if y Vmax.
Note that Sp satisfies the constraint:
Σ
(T
Σ s(x,y) = Vu [-S(x, Mmax),, h(x))] yeMuio}
yE
Let h H be hypothesis such that h(x=) Vmaxx-
By the definition and using the fact that
H(x) ( (0} when H. is symmetric, we obtain
AC A (h,
Cioo (1,z) Eis (H,z)
Cluu (Tr
inf J. (.8(c,((()))
Clow (T))ar)
p(z, Mmax) [- [-loo(S log(S(z ((xx, Vmax)) log( - =]]
sup Bel-8(E.Ninxxx.88
+ - h(x))) + log(S(x; ymmxx m)]
Differentiating with respect to a yields the optimum value μ² Plugging that value in the inequality gives:
pam. (tt--mmm)xpp((h((e00 +p(x,h(w))
8((x, h(xx)) + 8(x, Umnxx) Ip Fmnxx
ACtime Fe (h, 2 p(x, Mmax log
8(x, Vnuax) ) [p( Vrnax) aa,, h(x))]
8(r, h(x)(())))))))))())) S(x, Imaxx) p( h(z))
p(x h(x))()))))))))))())) log
8(x, (g,hh()))))) p(2, Vmaxx) p(1, h( h(x))
Differentiating with respect 8 to show that the minimum is attained for 8(x; h(x))())))))))))()))) 8(x, Mmax), which implies
2p( F. Mrnxx)
2p h(x))
AC tre Tr x), 2 p(x, Mmax) log p(a, Fmax) p(x h(x))
+ p(z, h(x)) log
p(z, Mmax) + p(x, h(x))
By Pinsker's inequality, we have, a b [0, 1]. log 20 we obtain:
a-b
+ bog 26 a+d
(a-b)² 2(a+8]
Using this inequality,
(p(x, h(x)))(()) p( Mmaxx) )) (p((x, h(xx)) + p(x,, Fmax))
A A Fi (x,
(p(z, h(x))) p(x,, yrnax)
(0 (s((,h(x)) p(x, Imax) $ 1)
Acc SCee....e 2. (T,,)))
(by Lemma 8 and H(x)) y (0))
Since the function distribution,
e is convex, by Jensen's 's inequality, we obtain for any hypothesis Fe H and any
2
Ae (4,
Ae to-1 3o (h,,))
2
$ E X
2
S
X
AC (T,
Fing .r
which leads to
) x0)²= -Mea. (T)).
Elo (1) - -Ei, (IC) s
Eloo
(1) -
(
Mema
22

---

By the definition and using the fact that E.2 Sum exponential loss
Theorem 10 (J-coonisttenyy bound for exponential loss). Assume that HC is symmetric and complete. Then, for any X R. hypothesis h H and any distribution,
Eig (h)
Eo H V2((E
Elexp
h1)
87 Eloxs
H
Meaxs
H(
Men-1 (H).
-exp-risk Proof. For the sum exponential loss lexp, the conditional eep -risk can be expressed as follows:
Mlay')) )
p(r,y) yeMufo) S(x,y)
(h,
Σ p(,y Σ
Σ
yeyufo)
y'EMu(0}
where let 8(x,y) Eytenuroo chilew
[0, for any y ( with the constraint that Egezu(o) 8(x, = 1. Let Umax = yeyu(o p(r,y) where we choose the label with the highest index under the natural ordering of labels as the tie-breaking strategy. For any h H such that h(x) # Vmax and ir X, by the symmetry and completeness of H, always find family of hypotheses ( [=8(2, Vmax). 8 h(z))]] H such that S,,(z,)) Eytesuro chu(e,0) following values:
Falon))
take the
8(x,y)
if y É {Umaxx h(x)}
(z.
8(z, Vmaxx) +
if y h(z)
8(z, h(x))
y Fmax.
Note that S, satisfies the constraint:
(x, S(r,,))= = Vu ( (mmax) 8(r, ((r,(())))) yeyy
Σ
yey
Let h e H be hypothesis such that h(x))
Vmax H(x) = yu (0} when H is symmetric, we obtain
AC S.r.epp.. (T,,5))
Cloup (h, e. Cr (H,z)
2 Claup (h,x)-
inf
Clavp (hrr
ue[-8(u (((. 8(a.h(a:))
sup ue[- 8(x Mmmux ((,(,,(())))
p(2, Vmaax)
8(x, Vmnax)
8(x, h(x)((()))))))))))))) u
p(z,h(z))
8(I,h(x))
8(x, Vmaxx p
Differentiating with respect to μ yields the optimal value
(((2, h(x)) Vplx, Mmmax ) (I, Vmaxx)
Vp(z, Vmaxx v h(xxh(())
Plugging that value in the inequality gives:
(Vp(e, (Vp(z,Mmax))
(mnx)) + V h(x))
toxp. F (2, p(2, Fmax)
(x,h()))
AC; ACt
8(x, Umax)
8(x h(x))
8(I,y vmmax) )+ 8(x, h(x))))))
23

---

Differentiating with respect to 8 to show that the minimum is attained for S(x, (())) = 6(x, Fmax) 2. which implies
2
A
Feopp Jf (h,
V (rnax) Var, (2(x)h((z))
(p(2, (())) - p(2:, ymmax)
2"
(Vp(z,h(z)) vp(x,, Vmaxx
By the concavity of the square-root function, for all a, b [0, 1]. we have 1/[ā VD) s = thus we can write
(p(2, h(x)) pl Mrmax))
AC
(1,x)
Loop
2(((x,, h(z)) + pl x Vmaxx)
(1(2, h(x))(()))))))))())))) - p( Umnax)
2
(p(2, h(x))()))))))))))())) p(x, ymax) $ 1)
2
1 2/2 (ee to .. x),
(by Lemma 8 and H(x) (0))
Since the function distribution.
12 convex, by Jensen's 's inequality, we obtain for any hypothesis h JC and any
Ex AC, 1o (C (
AC t n (7,
s B Ae Lexp J( (,,
X
2
which leads
Eig- (h) Eig (H) (E(Eemmp (h)-E% Eopp (I) + Menrr (I())² Men. (HH).
E.3
Generalized cross-entropy loss
Theorem 11 (K-consistency bound for generalized cross-entropy loss). Assume that K. is sym- metric and complete. Then, for any R. hypothesis h H and any distribution,
Ej (H) Me (Jt) 4 M (H).
Eto Ft)
E% (K) s 2(1 1)a(E,,
Proof. For the generalized cross-entropy loss laee: the conditional fgce-risk can be expressed as follows:
(h(w
17-1
etgo (h,z)) Σ p(a,v) v) yeyu(n) a
Σ p(a, p(x,,)(1-88) yeyu(n)
E Everuo eleees)) e
where we let 8(x,y) Exteysro e.il
[0, for any y Y {0} with the constraint that Eyeyu(o) 8(1,y) Let Fmax argmax, p(r,y), where choose the label with the same deterministic strategy for breaking ties as that of h(x). For any h e H such that h(x:) # ymax and x X, by the symmetry and completeness of H. we can always find a family of hypotheses (h, e [-8(x, ymax). ((x,h())))
such that (x,,)) Eycyutoo chalarr take the following
values:
8(x, Vmnax) + S(z,y)
if y & {Ymaxx h(x)) if y h(x) 8(x, h(xhh(xx)))))))))()))))) y = Imax.
(x.y)
24

---

Note that Sp satisfies the constraint:
Σ ye
(x(r,y)
Σ ,(x,z) = Ay [-8(xr Mmax) S(x, h(x))]
yeMuio}
Let h H be hypothesis such that h(z) Ymax
By the definition and using the fact that
H(z) yo (0) when H is symmetric, we obtain
= Ceo (T1,2) ex (H,
2 Ceaon (T1
inf ((x,h(())
Cegr (R)
Mmax)) p(a,, p(x, (lax))a))(-(( Bm) (8(2,)))))))
sup a (el-8(2 (ecee/800)))8((((()0 8({2,(())))
+ (8(x, Umaxx + (4) 10)
+ ((=,h(<))(-S(<<Hit))
Differentiating with respect to μ yields the optimal value
/ p(,,h(z)) (t 8(2 h(xxx(()))))))))))) p(x, Umax) - (xx, Mmaxx
pl x. Mlmax) I-a p(,, h(xr)) --
Plugging that value in the inequality gives:
AC, A iggnn. 36 (h, (((x,(())) S(x, ymaxx) (p(ppp(()))p ymax)
ymax ihn + +p(x,h(x)) 2t 1-a
1 p(z, Imax 8((z ymmax) - ((.
Differentiating with respect to to show that the minimum is attained for ((r)) (xx Mmax) x+T. which implies
AC
to Fi 2h)
(((xx) Umax) th + ((I))((z)))) 1..
p2( Mmax ((x;(((x))) h(x))
a(n+ 1)rx
(ara+blio 1-a
By using the fact that for all a, be [0, 0sabbs 1, we have thus we can write
2 2 1/4 (a (()))) b) 2+b
(((,h(x:)) p(=,, Fmmxx)
AC ACtran Bonn 26 (T,2)) 2
2(n + 1)a
se to .r (h.
(by Lemma 8 and H(x) = (0))
2(n 1)a
Since the function any distribution,
e 2(n+1)> is convex, by Jensen's inequality, we obtain for any hypothesis h H and
Ex Ae to Je 2))
Ae
x2
21
S E Ae x
(T.
2(n 1)aa
X
2( n 1)aa
which leads to
Elo. (h) -0 (3() S 2(n+ 1) (7) -Eioe (HC) Me (J)) -Me.. (J)..
25

---

E.4 Mean absolute error loss
Theorem 12 (HC-consistency bound for mean absolute error loss). Assume that H is symmetric and complete. Then, for any R. hypothesis h E H and any distribution,
Ela.s (h) E (3C) s (n & (h) E Emmmm (3C Me (Jt) Men. (H().
Proof. For the mean absolute error loss fmae, the conditional mae-risk can be expressed as follows:
Ci mnne (T))))
E p(Z:1)
E p(x,)) - 8(x,y))
yEHufo)
DEbUEO)
where we let 8(x,1) Enrouuro ehco. [0, 1] for any Y (0) with the constraint that Eyeyo(o) 8(x, 3) Let Mmax argmax p(x,y), where we choose the label with the same deterministic strategy for breaking ties that of f((:). For any Ti H such that h(x)) # ymaax and x E X. by the symmetry and completeness of H. we can always find a family hypotheses TTp μ e [-8(2, Umaxx, )
H such that (x, y f {ymax: h(x))
take the following
Eytouueo cuttr
values:
8(2,y) y)
S (z. 8) =
8(x, Umax) +
y = h(x)
(())) if y Vmax
Note that Sy satisfies the constraint:
Σ (I,
Σ 8(x,y) = 1, Vu Vlmax) ((,, ye)u(())
ge (O)
Let h e H be a hypothesis such that h(x) * Ymaxx
By the definition and using the fact that
H(x) = y {0} when H is symmetric, we obtain
Ae, / J. ())
= Claaa (T1,x)
C2 HH
Claa (h,x)
inf pe[- vel-B((. ((x,
Claan (Tyr
px Vmnxx) ( -88(1, vmnax) (8xx,h(()) - -1o
sup
4el=8(2, 8(xh(()))
p(x, p(r,,(())(-S((((())) + 8(x, Mmax) ue]
Differentiating with respect to a yields the optimum value μr" S((x, ymax). Plugging that value in the inequality gives:
AC A
h1,
p(,, Vmax )((r h(x)) p(a, ((chh(()((())))) h(x))))
Differentiating with respect to 8 to show that the minimum is attained for 8(x, h(x))()))))))))))())))) = m+1 which implies
AC Eman. Fr (1, 2
(p(x, Mmmax) ) p(.; h(x)))
Ae to-1 (h,
(by Lemma 8 and H(x) (0))
n
Therefore, obtain for any hypothesis To H and any distribution,
E
AC b0-
F ())
AC
mane ग [.
n
which leads to
Eig. (h) (T) s (n (){
(h)
Ei (H) + Me (J)) Mea (H).
26

---

F Proof of realizable consistency for score-based two-stage surrogate losses (Theorem 5)
Theorem (Realizable H-consisteney for score-based two-stage surrogates). Assume that H. is closed under scaling and cy(x,y) 83, ()) E x.Xx y. Let & and E2 be the logistic loss. Let hy be the minimizer of Et, and ha be the minimizer of EL,, such that ELiP (ha) = ming CLUp (ha). Then, the sollowing equality holds for any (H, R) rrealizable distribution,
Laat (h) 0, where h (hp.h.))
Proof. First, by definition, it is straightforward to see that for any h, y. Ln, (ha, v. upper bounds the deferral loss Ldef- Consider a data distribution and costs under which there exists h² H such that EL (ht) 0.
Let hp be the minimizer of ε,, and ha the minimizer of ELi, Then, using the fact that Ln upper bounds the deferral loss Ldef, we have ELac (h) ELi, (ha).
Next we analyze two cases. If for a point x, deferral occurs, that is there exists j" e [me]]. such that h2 (x:)
j", then must have Cy. for all since the data is realizable and cg+ is constant. Therefore, there exists an optimal h²* deferring all the points to the j "h expert. Then, by the assumption that H closed under scaling and the Lebesgue dominated convergence theorem, for &g being the logistic loss, LLa (h) S ELA, (ha) S lim,-+00 EL, (Th²²) ) O, where we used the fact
that in the limit of +o the logistic loss term 82 (2 J) corresponding to joj j is zero.
On the other hand, no deferral occurs for any point, that h* (x) [n] for any x, then we must have (n)) = 0 for all (x, y) since the data is realizable. Using the fact that H is closed under scaling and that the logistic loss is realizable H-consistent in the standard classification, we obtain (ūx())e 0
for (x,,). Then, by the assumption that is closed under scaling and the Lebesgue dominated convergence theorem, for & being the logistic loss, ELTer (h) s ELe,p (ha) s lim EL,g (rh3) = 0.
where we used the fact that in the limit of +oo the logistic loss term (2( j) corresponding to # 0 is zero.
Therefore, the optimal solution from minimizing score-based two-stage surrogates leads to error solution of the deferral loss, which proves that the score-based two-stage surrogate loss is realizable consistent.
G Proof of (H, -oonsisecyy bounds for predictor-rejector two-stage surrogate losses (Theorem 6)
bounds for predictor-rejector two-stage surrogates). Assume that E admits an H-consistency bound and 62 admits an R-consistency bound with respect the multi-class zero-one classification loss fo-1 respectively. Thus, there are non non-decreasing concave functions 1 and I'2 such that, for all h H and r R, we have
Theorem 6
Eio., (h) E7 (H) + Me.. (3C) s Ti (E,, (h) - E7 (3I) Eio. (T) Et, (3) M (R) s (E (F) ( -8,
+ Me, (IC)
+ Mes (R)).
Then, the following holds for all E HC and R:
ELa (h, r) Ei (IC + Meaa R3C
+ 1+ ne
EL, (r) - (R) + Men (3)
< <T, (h) 87, (IC) My, (I()
(1+
Σ 3j T2
Σns C3
1=1
where the constant factors (1+ T and
Σ can be removed when Fg is linear.
27

---

Proof. By definition,
(h, (c(r)ey (x)==0 Σ (x, (())=}-
5=1
Let (o( h(x)==y- We can rewrite ELg (h,r) - ELanr (H, Miaas (H, as ELaa (h2 - Elaer R) Ma RH,
Ex Claer (1, (HC (H, x)
Ex Clase (,, inf Claes (h, r,,) x) inf CLae (h,, r;,) Ciao (H, (H, rel
relt
-Ex Clac (,,
inf C Clas (h, (,, + Ex inf Clas (,) CLow (H, (H,
rell
ree
Let p(x,)) [y(e:(w,v)]
Enj0 E, (x.3)] for any (0, (0,...,ne)) ne). Note that p(x,,) is the probability vector
the label space {0,... ne). For any R, define its augmented hypothesis: r(z,0)
0, F2x -r) F(E, T( -Tn. (x). By the assumptions, we have
CL r,)) - inf CL. (h,
reR
ng (x (z
Re
In(a)yy 1(=)==
inf re3k
Iy (0)==0 Σ (5(2,))
1=1
1=1
Re Σ
Σ
C (z.
x
p( (] (0- (F,2.)) inf Σ
p(x: ()
1-0
FER j-0
E
Σ (2,
x
inf Σ ((z, Σ p (2 (2,,
1
PeR
(By R-consistency bounds of Eg under assumption)
E (r,,,,,,,,,)) infrex Ly
Σ (x,
T2
Ey [E (x,
0
E, (p(I,)) = Ens (,le,( and formulation (5))
T2 CL. (r. - et, (R,x)
when Ig is linear
Cip (x,x)- ei, (R.,r)
(1 Ens 22
otherwise
(E/=1 Sj Ey Ef= (z,8)) s1+ Σj=r 2y and I'2 is non non-decreasing)
P2(SeL, (r, (1 Ef=1 23 r2
when 12 is linear
sei, (1.z) Σ
otherwise
and
inf CLAer (b,, r,,)) Ciree (H, retR
inf CLiar (,,) rel
inf heRK,eER
CLae (h, (h,
1 1r)) Σ (2, (2(x))) 1 iin E
inf B NEDE
reR
=min E
( Bl E[
((c
min inf E (. weet "
[[(In=))v]] inf E [n(
Cla (h, ej (H,
ACC (h1x))
ST (h).
(By H-consistency bounds of & under assumption)
28

---

Therefore, by (7), we obtain
ELaer (h, Etant (H, R)
MLoa (H,
(x xe (r,
Ex (AC, (ACx(h,
when T2 is linear
$
(1 Eg=1 (3) Ex T2
A , (n
otherwise
2 S
(2 ( x(,
when T2 is linear
<
(1+ (1+ 8g T2
Ex
ACL, (1,0))
(Ex((((),
otherwise
Σ
(I' and I2 are concave)
(T(E((h) - (J() + +c(()))) (12(EEL -E,, (R) + ML, (R)
when Fg is linear otherwise,
(i(E,(h) (1666)-87,,00) (M(()++G(()))) (I+ 212 E4 (r) (r) (R) My, (R)
The
which completes the proof.
H Proof of realizable consistency for predictor-rejector two-stage surrogate losses (Theorem 7)
Theorem 7 (Realizable (H, R.,,R)-cconnstene for predictor-rejector two-stage surrogates). As- sume that H and R is closed under scaling and cg(xr,) Bj, V (xx v) X Let & and &2 be the logistic loss. Let h the minimizer of &e, and f be the minimizer of EL.- Then, the following holds for any (H, R) -realizable distribution,
ELAT (h, (1,
Proof. First, by definition, it is straightforward to see that for any h, r. 2. (r, v) upper bounds deferral loss Laet- Consider data distribution and costs under which there exists hi H and r" E R such that E (h'
O.
Let be the minimizer of Ee, and the minimizer of EL, Then, using the fact that LA upper bounds the deferral loss Laef, we have EL (h, f) s &L,, (f).
Next we analyze two cases. If for a point x, deferral occurs, that is there exists j e [me.]. such that r (xx) j", then we must have Cy. 0 for all since the data is realizable and Cy- is constant. Therefore, there exists an optimal y** deferring
the points to the j'th expert. Then, by the assumption that R is closed under scaling and the Lebesgue dominated convergence theorem, for l being the logistic loss, ELL (h, EL, (f) lim εL, (rr**)= 0, where used the fact that in the limit of
the logistic loss term (2(F"*, corresponding to # #j" is zero.
On the other hand, if no deferral occurs any point, that r" (xx) for any x. then we must have (z) 0 for all (x., y) since the data is realizable. Using the fact that H is closed under scaling and that the logistic loss is realizable H-consistent in the standard classification, we obtain 1 Li(z)=y for all (x. v). Then, by the assumption that R is closed under scaling and the Lebesgue dominated convergence theorem, for la being the logistic loss, LLas (h f) E (f) lim ÊL, (Tr*) 0, where we used the fact that in the limit of to j # is zero.
the logistic loss term (2 ,x,)) corresponding
Therefore, the optimal solution from minimizing predictor-rejector two-stage surrogates leads to zero error solution of the deferral loss, which proves that the predictor-rejector two-stage surrogate loss is realizable consistent.
29


Reviews:
[{"review_id": "2VBX51fpAi", "reviewer": "Reviewer_fJtW", "summary": "The paper proposes two stage learning algorithms for learning to defer framework. Learning to defer framework consists of two components, a rejector and a classifier. Previous literature has focussed on jointly training both the classifier and the rejector. This paper, instead, focuses on the two stage setup in designing learning to defer systems where a pre-trained classifier is provided and the rejector is to be trained in the second stage. This is a promising and more practical use case scenario of the deferral systems. To this end, the paper makes a series of contributions: 1. a simple and elegant formulation of the the said two stage setup 2. Proposing a family of surrogate loss functions for this setup as well as providing risk control guarantees based on $\\mathcal{H}$-consistency bounds that builds upon the consistency bounds for the loss employed in both the stages. 3. The paper then prove a more general result on the $\\mathcal{H}$ consistency bounds for general surrogate losses for classification problem which is augmented with some additional instance dependent hypothesis. 4. The paper uses this result to establish $\\mathcal{H}$ consistency as well as the Bayes consistency of the proposed two stage surrogates. Additionally, the paper also establishes the realizable $\\mathcal{H}$ consistency of the two stage surrogates which is a more stronger property. The focus of the paper is general where multiple experts are possible.", "questions": "1. $\\mathcal{H}$ realizable consistent surrogates have not been proposed in the literature for single stage learning to defer with multiple experts. Is it possible to utilise the results in this paper for that? For example, maybe using iterative training procedure.", "limitations": "No glaring limitations.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper investigates a question of practical relevance to the machine learning community. Deferral systems have appealing properties as they foster trust and transparency, as well as monitoring behaviour by introducing experts into the system. However, it was not possible based on the prior work how to adapt any pre-trained system to experts. This paper fills this gap by devising theoretically sound algorithms.\n\n2. While the paper builds heavily on the previous works on rejection learning, the proposed algorithms are sufficiently novel. The paper also fills a gap in the literature for deriving $\\bar{\\mathcal{H}}$-consistency bounds for a general rejection learning problem. As a plus point, the proposed surrogates are simple and intuitive which makes it easier for adoption in the community. \n\n3. The paper proposes first of its kind $\\mathcal{H}$-realizable consistent algorithms for learning to defer with multiple experts. I believe this is a significant contribution as generally building deferral systems considering multiple experts from scratch would be prohibitively expensive. \n\n4. Although there are some minor typos in the text, the paper is clearly written and is super easy to read. \n\n", "weaknesses": "1. While theoretical results is the main focus of this paper, I believe experimental section could have been more insightful. Currently, the experimental section says that the overall system performance gets better on inclusion of more experts. However, this is intuitive and already known. Could authors add one more column in Table 4 to mention the performance of the originally trained classifier? I am curious to learn how the second stage adoption affects the originally trained classifier. While one can lower the estimation error of the first classifier by $\\epsilon_{1}$, it is not clear (to me) where such bound still holds True after the adoption in the second stage. I agree that this is certainly not the focus of the paper, I believe it is important to know if this second-stage training degrades the already trained classifier. I assume not, right?\n\n2. This might be a misunderstanding on my side, but I believe the proposed formulation can only work when $\\alpha_{j}, \\beta_{j} > 0,  \\forall j$ (line 104). However, there are no guidelines on how to define these two quantities, or what is their nature. \n\n3. One of the most promising appeal of the two stage training is preventing costly design from scratch. However, it is not clear whether it also has some disadvantages or not. Consider a single stage training approach where one wants to bound the estimation error by $\\epsilon$? Would it be cheaper / expensive to achieve the same bound using the two-stage approach? Could some quantitative results be given to this end to guide the practitioners?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your encouraging review. 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. While theoretical results is the main focus of this paper, I believe experimental section could have been more insightful. Currently, the experimental section says that the overall system performance gets better on inclusion of more experts. However, this is intuitive and already known. Could authors add one more column in Table 4 to mention the performance of the originally trained classifier? I am curious to learn how the second stage adoption affects the originally trained classifier. While one can lower the estimation error of the first classifier by $\\epsilon_1$, it is not clear (to me) where such bound still holds True after the adoption in the second stage. I agree that this is certainly not the focus of the paper, I believe it is important to know if this second-stage training degrades the already trained classifier. I assume not, right?**\n\n**Response:** The accuracy of the originally trained classifier on SVHN is 91.12% and that on CIFAR-10 is 70.56%. We will add them to Table 4 in the final version. \n\nThat’s right. The second-stage training does not degrade the performance of the already trained classifier.\n\n**2. This might be a misunderstanding on my side, but I believe the proposed formulation can only work when $\\alpha_j, \\beta_j>0, \\forall j$ (line 104). However, there are no guidelines on how to define these two quantities, or what is their nature.**\n\n**Response:** Our analysis for Theorem 1, Corollary 2, Theorem 6 is general and only requires the cost to be bounded. This formulation is one natural choice to define the cost. Typically, the hyperparameter $\\alpha_j$ has two potential values: zero or one. When $\\alpha_j$ is set to one, the first term of the formulation pertains to the inaccuracy of expert expert $h_j$. Conversely, with $\\alpha_j$ set to zero, the first term vanishes, focusing solely on the inference cost. Theorems 5 and 7 are analyzed under this assumption. The $\\beta_j$ in the second term, for example, can correspond to the inference cost incurred by expert $h_j$. We will further clarify and elaborate on these in the final version.\n\n**3. One of the most promising appeal of the two stage training is preventing costly design from scratch. However, it is not clear whether it also has some disadvantages or not. Consider a single stage training approach where one wants to bound the estimation error by $\\epsilon$? Would it be cheaper / expensive to achieve the same bound using the two-stage approach? Could some quantitative results be given to this end to guide the practitioners?**\n\n**Response:** Great question! Intuitively, the drawback of a two-stage approach lies in the potential accumulation of errors across both the first and second stages. In contrast, the single-stage approach sidesteps this problem, allowing for a more streamlined optimization. However, in some cases, a direct single-stage loss might be harder to optimize computationally. A finer theoretical comparison between single-stage and two-stage approaches would certainly be interesting and we intend to further investigate that.\n\n**Questions:**\n\n**1. $\\mathcal{H}$-realizable consistent surrogates have not been proposed in the literature for single stage learning to defer with multiple experts. Is it possible to utilise the results in this paper for that? For example, maybe using iterative training procedure.**\n\n**Response:** Great question! This is in fact a research direction we've recently embarked upon exploring. \n"}, {"review_id": "lJ4waiWXRk", "reviewer": "Reviewer_Z2p9", "summary": "This paper provides bounds on the difference between the target loss and its surrogate loss, for two-stage learning to defer to multiple experts. The bounds guarantee that a small surrogate risk leads to a small target risk. The authors also show that in realizable cases, achieving the minimum surrogate risk results in the zero target risk, which affirmatively answers an open question. The paper studies two setups of two-stage learning to defer with multiple experts and provides similar theoretical results for both. Finally, the paper presents experiments using CIFAR-10 and SVHN, showing that having more experts improves performance.", "questions": "- In line 21, the paper says, \"However, this is not relevant in practice: the cost of retraining the predictor would be prohibitive for many applications.\" I think saying it is \"not relevant\" is a bit too strong if there are still some scenarios to which it is applicable.\n- For the minimizability gap $\\mathcal{R}^*_l - \\mathbb{E}\\_{x}[\\inf\\_{h\\in \\mathcal{H}} \\mathbb{E}\\_{y | x}[\\texttt{L}(h, x, y)]]$, why do we want to consider the point-wise infimum for the second term? I think it is more natural to consider $\\inf\\_{h\\in \\mathcal{H}} \\mathbb{E}\\_{x, y}[\\texttt{L}(h, x, y)]$.\n- In lines 137-140, it is strange to \"decompose\" $\\mathcal{H}$ as $\\mathcal{H} = \\mathcal{H}_p \\times \\mathcal{H}_d$ when $\\mathcal{H}$ is a set of functions. ($\\mathcal{H}_p \\times \\mathcal{H}_d$ is a set of function pairs.)\n- I think it's nicer to express, e.g., Eq. (3) as $L_{h_p}(h_d, x, y) = \\sum\\_{j=0}^{n_e} c\\_j(x, y) \\ell_2(\\bar{h}\\_d, x, j)$, with $c_j$ extended by $c_0(x, y) = \\mathbb 1\\_{h\\_p(x) \\neq y}$. Equations are unnecessarily long and hard to read especially in Table 2.\n- Is Definition 4 correct? (I think there is something wrong with the organization of the sentences.)\n- What do the symbols in the \"Base cost\" column in Table 4 mean?\n- What does Accuracy in Table 4 mean? They are not related to the deferral loss?\n- In ll. 231-234, I could not understand this part: \"In their proof, the authors choose $\\bar h\\_{\\mu}$ based on individual scores $h(x, y)$, rather than the softmax. Consequently, if $h(x)$ or the label $y_{\\text{max}}$ that achieves the maximum conditional probability corresponds to the label zero, $\\mu$ cannot be optimized since the score $h(x, 0)$ is fixed at $\\lambda$.\"", "limitations": "This paper focuses on bounds regarding population quantities. The results do not directly apply to empirical risk minimization although this extension does not seem very hard.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper studies the practically important task of learning to defer to experts.\n- The results seem to be non-trivial and critical theoretical guarantees for the approach studied.\n- The writing is overall well-written and easy to follow, except for some technical parts.\n- The paper provides a good review of previous work and clearly explains the contributions.\n- The experiment is interesting and shows the usefulness of the approach of learning to defer.", "weaknesses": "- Some technical parts were a little unclear. (See the questions below.)\n- Section 3 and Section 4 are repetitive. I don't know how much the setups are different from each other.\n- I think some math expressions could be simplified. (See the Questions section below.)\n- The experiments are not extensive. I expected to see some experiments confirming the theoretical results, but the focus of the experiments presented in the paper seems to be the improvement by increasing the number of experts, which is quite independent of the theory part.\n- The paper stresses the novelty of the proof technique and there are brief explanations, but it is difficult for me to understand them without reading the appendix. (Unfortunately, I did not have time to read the appendix.)", "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. Some technical parts were a little unclear. (See the questions below.)**\n\n**Response:** Thank you for highlighting those points. We value your feedback and will certainly consider your suggestions. Below, you'll find our detailed responses to your specific questions.\n\n**2. Section 3 and Section 4 are repetitive. I don't know how much the setups are different from each other.**\n\n**Response:** Section 3 delves into learning with deferral within a score-based framework, wherein the deferral is associated with extra scores. In contrast, Section 4 explores learning with deferral in the predictor-rejector setting, with the deferral corresponding to a separate function. These represent two separate learning frameworks that have been studied in the literature. Historically, for traditional single-stage scenarios, deriving consistent surrogate losses in the predictor-rejector setting has been challenging, leading many to opt for the score-based approach. We will further clarify this distinction and provide a detailed explanation in the final version.\n\n**3. I think some math expressions could be simplified. (See the Questions section below.)**\n\n**Response:** Thank you for highlighting those points. We will take into account your suggestions to refine and streamline the expressions. Below, you'll find our detailed responses to your specific questions.\n\n**4. The experiments are not extensive. I expected to see some experiments confirming the theoretical results, but the focus of the experiments presented in the paper seems to be the improvement by increasing the number of experts, which is quite independent of the theory part.**\n\n**Response:** Thank you for the suggestion. While the main focus of this work is a theoretical analysis of a two-stage scenario for learning to defer, we will seek to present a more comprehensive set of experiments in the final version. Specifically, we intend to incorporate comparisons with other single-stage surrogate losses in the literature, which has also been suggested by other reviewers.\n\n**5. The paper stresses the novelty of the proof technique and there are brief explanations, but it is difficult for me to understand them without reading the appendix. (Unfortunately, I did not have time to read the appendix.)**\n\n**Response:** Thank you for the suggestion. We will leverage the extra page allowed for the final version to include a more detailed discussion of the technical novelty in the main body.\n\n**Questions:**\n\n**1. In line 21 ...**\n\n**Response:** Thank you for the suggestion, we will refine it in the final version.\n\n**2. For the minimizability gap ...**\n\n**Response:** The first term $\\mathcal{R}^*_{\\mathsf L}(H)$ is the infimum of the expectation loss $\\inf_{h \\in H} \\mathbb{E}_{x,y} [\\mathsf L(h,x,y) ]$. Thus, the minimizability gap measures the difference of the best-in-class expected loss and that of the expected pointwise infimum loss. We will clarify it in the final version.\n\n**3. In lines 137-140 ...**\n\n**Response:** The decomposition here means that any function $h$ within $H$ is composed of the first $n$ scores $h_p$, used for prediction, alongside the final $n_{e}$ scores $h_d$, used for deferral. Thus, any $h\\in H$ can be written as a pair $h=(h_p, h_d)$. We will further clarify that in the final version.\n\n**4. I think it's nicer to express ...**\n\n**Response:** Thank you for the feedback. We will enhance the presentation in line with your suggestions for the final version.\n\n**5. Is Definition 4 correct ...**\n\n**Response:** Sorry for the confusion. We will restructure the sentences in the final version. In short, Definition 4 says that if a surrogate loss is realizable $H$-consistent if, optimizing the surrogate loss results in the minimization of the deferral loss for any $H$-realizable distribution. \n\n**6. What do the symbols ...**\n\n**Response:** A check mark indicates the presence of a base cost in the cost function, whereas a cross mark signifies its absence. This will be made clearer in the final version.\n\n**7. What does Accuracy ...**\n\n**Response:** The accuracy refers to the overall accuracy of the learned pairs of predictor and deferral model. It is related to the deferral loss. Specifically, in the absence of the base cost, the accuracy aligns precisely with one minus the expected deferral loss.\n\n**8. In ll. 231-234 ...**\n\n**Response:** This mainly highlights that their method is tailored for hypothesis sets where each score can span across $\\mathbb{R}$. This is not applicable in our context where the hypothesis set adheres to a predefined scoring function. In their proof, to set an upper bound on the estimation error of the zero-one loss using that of the surrogate loss, they select an auxiliary function $\\overline{h}_{\\mu}$ for any hypothesis $h$. This function is contingent on the distinct scores of $h$. Subsequently, the authors choose an optimal $\\mu$ to set these bounds. Nevertheless, if any of $h$'s scores are fixed, an optimal $\\mu$ doesn't exist, preventing the establishment of a meaningful bound. We will further clarify and detail these explanations in the final version.\n\n**Limitations: This paper focuses on bounds regarding population quantities. The results do not directly apply to empirical risk minimization although this extension does not seem very hard.**\n\n**Response:** Indeed, while our primary focus is on the infinite sample bound, our $H$-consistency bounds can be leveraged to derive finite sample learning bounds for a hypothesis set $H$. This can be achieved by upper bounding the estimation error of the surrogate loss using the standard Rademacher complexity bound associated with the hypothesis set and the loss function. We will add these to the final version.\n\n"}, {"review_id": "cZxuGIje0j", "reviewer": "Reviewer_yH2K", "summary": "This paper studies a two-stage scenario for learning to defer with multiple experts. For both the score-based setting and the predictor-rejector setting, the authors design a new family of surrogate loss function . The authors show that the surrogate losses are realizable H-consistent and  Bayes-consistency of our surrogate losses. The authors provide theoretical analysis and empirical results to justify the proposed framework. ", "questions": "See weakness part above.", "limitations": "I do not see the discussion of limitations, but I think this is not a major problem. I do not see potential negative societal impact as this paper mainly focuses on the theoretical side.", "rating": 7, "confidence": 1, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. The problem setup is interesting and realistic. The two stage deferring scenario is suitable when predictor is a pretrained LLM, and has promising real applications.\n\n2. The surrogate loss function is well-motivated and new as far as I am concerned. The theoretical results are strong and comprehensive. I do not fully check the proof, but the results seem reasonable to me.", "weaknesses": "I am satisfied with the theoretical part. However, I would like to remark that I am not an expert in this field. I will be happy to follow up in the discussion period, if there is any additional questions raised up by other reviewers. \n\nFor the experiments, the accuracy on CIFAR10 and SVHN is significantly lower than the standard results of ResNet. Moreover, the authors only implement the proposed loss function. I would be better to compare with different baselines in previous works. ", "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: I am satisfied with the theoretical part. However, I would like to remark that I am not an expert in this field. I will be happy to follow up in the discussion period, if there are any additional questions raised by other reviewers. For the experiments, the accuracy on CIFAR10 and SVHN is significantly lower than the standard results of ResNet. Moreover, the authors only implement the proposed loss function. It would be better to compare with different baselines in previous works.**\n\n**Response:** We did not aim to achieve high accuracy for each expert, which is not the focus of this paper. No data augmentation was used and the hyperparameters were not specifically tuned for each expert in our experiments. In the final version, we can report results for experts with higher accuracy.\n\nTo the best of our knowledge, our work is the pioneer in examining a two-stage scenario for learning to defer—a framework we argue is crucial in practice for many applications. Presently, we're unaware of any established baselines within this context. While the main focus of this work is a theoretical analysis, in the final version, we are happy to compare our novel surrogate losses with the existing single-stage surrogate losses in the literature, thereby enriching our experiments in line with the reviewer's suggestions.\n\n**Limitations: I do not see the discussion of limitations, but I think this is not a major problem. I do not see potential negative societal impact as this paper mainly focuses on the theoretical side.**\n\n**Response:** Thank you for pointing it out, we will make sure to add a separate discussion on the limitation in the final version.\n"}, {"review_id": "CBkutQCAQD", "reviewer": "Reviewer_Jgi5", "summary": "This paper studies generalization bounds for learning to defer, with its main focus on \"two-stage\" algorithms that first fit a classifier using a surrogate classification loss, then separately fit a rejector that decides which expert, if any, to defer the classification to.\nBy and large, these two-stage algorithms have less theory than _joint_ algorithms that fit the classifier and rejector together, so this paper fills a gap in the theory literature for these algorithms. Bounds are provided for both score-based methods and the more general predictor/rejector setting.", "questions": "- If I'm mistaken about the above (if so, I will increase my score), how do the results of Theorem 5 and 7 avoid examples where two-stage optimization is very suboptimal and joint optimization is required, like the one I presented above? Can the authors provide more verbose and rigorous proofs of Theorems 5 and 7?\n\n- It might be useful to see if/how the proposed surrogate reduces to other ones in the literature in the single-expert case, depending on the choices of $l$.", "limitations": "I could not find a discussion of the limitations of the work.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "- Relatively well-presented and explained theoretical results\n- Fills a gap in the existing theory literature for learning to defer, especially in the multi-expert setting.", "weaknesses": "- The empirical results are missing baselines / comparisons to other surrogate methods in the literature.\n\n- I'm unable to follow the proofs of Theorems 5 and 7, which seem to be missing several steps (perhaps they're obvious?). In any case, the conclusions of these theorems seem to contradict the following simple 2D counterexample based on XOR.\nSuppose $\\mathcal{D}$ is uniform over $[-1,1] \\times [-1,1]$. Set the label $Y=1$ when $X_1 \\cdot X_2 \\ge 0$, and set $Y=-1$ elsewhere (i.e., the label is positive in quadrants 1 and 3, and negative in quadrants 2 and 4). Suppose there is just one human expert, and the human is always correct when $X_1 < 0$ and always incorrect when $X_1 \\ge 0$. This is clearly $(\\mathcal{H},\\mathcal{R})$-realizable for $\\mathcal{H}$ and $\\mathcal{R}$ both linear: $r^*$ chooses the human whenever $X_1 < 0$, and $h^*$ predicts $\\mathrm{sign}(X_2)$, which is the correct classification whenever $X_1 \\ge 0$.\nHowever, the conclusion of the theorem seems false in this case. There is no halfspace that achieves a nontrivial accuracy on all of $\\mathcal{D}$. However, we can still find an $h$ where $\\varepsilon_{l_1}(h) - \\varepsilon^*_{l_1}(\\mathcal{H})$ is arbitrarily small. For a fixed $h$ (which will have a poor loss $l_1(h)$), we can still fit an optimal deferrer, i.e., we can still reduce $\\varepsilon_{L_h}(r) - \\varepsilon^*_{L_h}(\\mathcal{R})$ towards 0. In this case, the RHS of the theorem statement can approach 0, but clearly, this combination has a poor loss $L_{def}$.\nEssentially, the issue is that the right-hand-side of the theorem statement is not sensitive to whether two-stage optimization is suboptimal, but $(\\mathcal{H}, \\mathcal{R})$-realizability allows for the case where it is.\n\n- Without the above, the results are still fairly interesting, since they provide some theory for two-stage methods, but the paper can't claim to resolve the open problem of Mozannar et al. 2023.", "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**1. The empirical results are missing baselines / comparisons to other surrogate methods in the literature.**\n\n**Response:** To the best of our knowledge, our work is the pioneer in examining a two-stage scenario for learning to defer—a framework we argue is crucial in practice for many applications. Presently, we're unaware of any established baselines within this context. While the main focus of this work is a theoretical analysis, in the final version, we are happy to compare our novel surrogate losses with the existing single-stage surrogate losses in the literature, thereby enriching our experiments in line with the reviewer's suggestions.\n\n**2. Theorems 5 and 7.**\n\n**Response:** Thank you for your careful comments. Theorems 5 and 7 are analyzed under the assumption that the cost functions remain constant, thus $\\alpha_j = 0$ in the cost function $c_j(x, y) = \\alpha_j 1_{\\mathsf h_j(x) \\neq y} + \\beta_j$. Regrettably, we omitted to indicate this assumption in the statements, and we apologize for the confusion this has caused. In contrast, our analysis for Theorem 1, Corollary 2, Theorem 6 is general and only requires the cost to be bounded. We will clarify these assumptions of our main results in the final version. \n\nHere is an alternative proof for the realizable consistency of our predictor-rejector two-stage surrogates with constant costs $c_j$, following the realizable consistency proof format in the recent work by Mozannar et al. [2023, Appendix D.4]. A similar proof applies to our score-based two-stage surrogates. Please let us know if these are sufficiently verbose as requested by the reviewer and if more clarification is needed.\n\n-------------------------------------------------------------------------\nAssume that $H$ and $R$ are closed under scaling. Let $\\ell_1$ and $\\ell_2$\nbe the logistic loss.\nFirst, by definition, it is straightforward to see that for any $h,r,x,y$, $\\mathsf L_{h}(r,x,y)$ upper bounds the deferral loss $\\mathsf L_{\\text{def}}(h,r,x,y)$. Consider a data distribution and costs under which there exists $h^*\\in H$ and $r^*\\in R$ such that $\\mathcal{E} _ {\\mathsf L _ {\\text{def}}}(h^*,r^*)=0$. \n\nLet $\\hat h$ be the minimizer of $\\mathcal{E} _ {\\ell_1}$ and $\\hat r$ the minimizer of $\\mathcal{E} _ {\\mathsf L_{\\hat h}}$\nThen, using the fact that $\\mathsf L_{h}$ upper bounds the deferral loss $\\mathsf L_{\\text{def}}$, we have $\\mathcal{E} _ {\\mathsf L _ {\\text{def}}}(\\hat h, \\hat r)\\leq \\mathcal{E} _ {\\mathsf L_{\\hat h}}(\\hat r)$.\n\nNext we analyze two cases. If for a point $x$, deferral occurs, that is there exists $j^*\\in [n_e]$, such that $\\mathsf r^*(x)=j^*$, then we must have $c_{j^*} = 0$ for all $x$ since the data is realizable and $c_{j^*}$ is constant. Therefore, there exists an optimal $r^{\\*\\*}$ deferring all the points to the $j^*$th expert. Then, by the assumption that $R$ is closed under scaling and the Lebesgue dominated convergence theorem, for $\\ell_2$ being the logistic loss, $\\mathcal{E} _ {\\mathsf L _ {\\text{def}}}(\\hat h, \\hat r)\\leq\\mathcal{E} _ {\\mathsf L _ {\\hat h}}(\\hat r) \\leq \\lim _ {\\tau \\to +\\infty} \\mathcal{E} _ {\\mathsf L _ {\\hat h}}(\\tau r^{**})=0$, where we used the fact that in the limit of $\\tau \\to +\\infty$ the logistic loss term $\\ell_2(\\overline r^{\\*\\*},x,j)$ corresponding to $j \\neq j^*$ is zero.\n\nOn the other hand, if no deferral occurs for any points, that is $\\mathsf r^*(x)=0$ for any $x$, then we must have $1_{\\mathsf h^*(x) \\neq y}=0$ for all $(x,y)$ since the data is realizable. Using the fact that $H$ is closed under scaling and that the logistic loss is realizable $H$-consistent in the standard classification, we obtain $1_{\\hat{\\mathsf h}(x) \\neq y}=0$ for all $(x,y)$. Then, by the assumption that $R$ is closed under scaling and the Lebesgue dominated convergence theorem, for $\\ell_2$ being the logistic loss, $\\mathcal{E} _ {\\mathsf L _ {\\text{def}}}(\\hat h, \\hat r)\\leq\\mathcal{E} _ {\\mathsf L _ {\\hat h}}(\\hat r) \\leq \\lim_{\\tau \\to+\\infty} \\mathcal{E} _ {\\mathsf L _ {\\hat h}}(\\tau r^{*})=0$, where we used the fact that in the limit of $\\tau \\to +\\infty$ the logistic loss term $\\ell_2(\\overline r^{\\*},x,j)$ corresponding to $j \\neq 0$ is zero.\n\nTherefore, the optimal solution from minimizing predictor-rejector two-stage surrogates leads to a zero error solution of the deferral loss, which proves that the predictor-rejector two-stage surrogate loss is realizable consistent.\n\n-------------------------------------------------------------------------\n\nWe concur, however, that for a more general cost function where $\\alpha_j$ is not zero, our two-stage surrogate losses may lack realizable consistency, a point well illustrated by your example. Furthermore, we acknowledge that, in that respect, our claim about resolving the open problem from (Mozannar et al., 2023) is overstated and we will rectify that in the final version.\n\nNonetheless, as the reviewer rightly notes, even if our realizable consistency results don't extend to the general cost function scenarios, we remain confident in the novelty and significance of our results related to two-stage learning to defer with multiple experts.\n\n**3. It might be useful to see if/how the proposed surrogate reduces ... choices of $\\ell$.**\n\n**Response:** To the best of our knowledge, even in the context of the single-expert scenario, our family of two-stage surrogate losses are novel. However, we concur that showcasing the single-expert case can illuminate the uniqueness of our formulation. We will certainly incorporate a detailed discussion on this in the final version.\n\n\n**Limitations: I could not find a discussion of the limitations of the work.**\n\n**Response:** Thank you for pointing it out, we will make sure to add a separate discussion on the limitation in the final version.\n"}]

Author rebuttal:

Meta-review: This paper analyzes the realizability of two-stage learning-to-defer algorithms, providing new insights to previous results that suggested the superiority of one-stage / joint algorithms.  The reviewers are unanimously in favor of acceptance.  The most critical stance was presented by Reviewer Jgi5, who questioned the realizability of the consistent surrogates in cases and claimed the paper overstates its resolution of the the open problem from (Mozannar et al., 2023).  While this critique has merits, I find the authors successfully rebutted the former theoretical point.  For the latter point, the authors should be sure to temper their claim about resolving the open problem(s) from (Mozannar et al., 2023) in the camera-ready version, as they promised to do in their reply to Reviewer Jgi5.
Decision: Accept (poster)