Mastering Multiple-Expert Routing: Realizable $H$-Consistency and Strong Guarantees for Learning to Defer
Authors: Anqi Mao
Mehryar Mohri
Yutao Zhong
Venue: ICML 2025 poster (2025)
Keywords: learning to defer
consistency
realizable H-consistency
learning theory
Primary area: theory->learning_theory

Abstract: The problem of learning to defer with multiple experts consists of optimally assigning input instances to experts, balancing the trade-off between their accuracy and computational cost. This is a critical challenge in natural language generation, but also in other fields such as image processing, and medical diagnostics. Recent studies have proposed surrogate loss functions to optimize deferral, but challenges remain in ensuring their consistency properties. This paper introduces novel surrogate loss functions and efficient algorithms with strong theoretical learning guarantees. We address open questions regarding realizable $H$-consistency, $H$-consistency bounds, and Bayes-consistency for both single-stage (jointly learning predictor and deferral function) and two-stage (learning only the deferral function with a fixed expert) learning scenarios. For single-stage deferral, we introduce a family of new realizable $H$-consistent surrogate losses and further prove $H$-consistency for a selected member. For two-stage deferral, we derive new surrogate losses that achieve realizable $H$-consistency, $H$-consistency bounds, and Bayes-consistency for the two-expert scenario and, under natural assumptions, multiple-expert
scenario. Additionally, we provide enhanced theoretical guarantees under low-noise assumptions for both scenarios. Finally, we report the results of experiments using our proposed surrogate losses, comparing their performance against existing baselines.

Mastering Multiple-Experr Routing:
Realizable H- H-Consistency and Strong
Guarantees for Learning to Defer
Anqi Mao
Mehryar Mohri
21
Yutao Zhong
Abstract
1. Introduction
The performance of learning algorithms can be substantially improved by redirecting uncertain predictions to domain spe- cialists or advanced pre-trained systems. These specialists may include individuals with deep expertise in specific areas or highly capable, though computationally intensive, pre- trained models. Selecting the appropriate expert requires careful consideration of both accuracy and computational cost, which may vary depending on the instance or class label in question.
The problem of learning to defer with multiple experts consists of optimally assigning input in- stances to experts, balancing the trade-off between their accuracy and computational cost. This is a critical challenge in natural language generation, but also in other fields such image process- ing. and medical diagnostics. Recent studies have proposed surrogate loss functions to optimize de- ferral, but challenges remain in ensuring their con- sistency properties. This paper introduces novel surrogate loss functions and efficient algorithms with strong theoretical learning guarantees. We address open questions regarding realizable HC- consistency, HH-consistency bounds, and Bayes- consistency for both single-stage (jointly learning predictor and deferral function) and two-stage (learning only the deferral function with fixed expert) learning scenarios. For single-stage de- ferral, we introduce a family of new realizable H(-consistent surrogate losses and further prove H-consistency for selected member. For two- stage deferral, we derive new surrogate losses that achieve realizable H-consistenny,, H-consistency bounds, and consiseen for the two-expert scenario and, under natural assumptions, multiple- expert scenario. Additionally, we provide en- hanced theoretical guarantees under low-noise assumptions for both scenarios. Finally, we re- port the results of experiments using our proposed surrogate losses, comparing their performance against existing baselines.
How can input instances be optimally assigned to the most suitable expert from a diverse set, balancing these consider- ations? Can allocation strategies be learned from past expe- rience? These questions form the core challenge of learning to defer with multiple experts, a problem that comes up across various fields. In natural language generation, partic- ularly with large language models (LLMs), this challenge has been highlighted as critical issue (Wei et al., 2022; Bubeck et al., 2023), essential both for reducing halluci- nations and improving efficiency. However, the problem extends to other domains, including image annotation, med- ical diagnostics, economic forecasting, and computer vision, among others.
The problem of learning to defer accurately has been inves- tigated in number of recent studies (Mozannar & Sontag, 2020; Verma & Nalisnick, 2022; Charusaie et al., 2022; Mozannar et al., 2023; Mao et al., 2024a;i). It is typically formulated using a deferral loss function that incorporates pustance-specingg costs associated with each expert. Direct- ing optimizing this loss function is intractable for the hypoth- esis sets commonly used in applications. Thus, learning-to- defer algorithms rely optimizing surrogate loss function instead, that serves proxy for the original target loss function. Yet, what guarantees can we rely on when opti- mizing such surrogate loss functions?
'Courant Institute of Mathematical Sciences, New York. NY; "Google Research, New York, NY. Corre- spondence to: Angi Mao Sognaa@ccis.nyu.edee Mchryar Mohri imohri@google.com::: Yutao Zhong <yu- taozhong@ @ goog...com>>.
This question, which involves analyzing the consistency guarantees of surrogate losses with respect the defer- ral loss, has been studied under two main scenarios (Mao, 2025): the single-stage scenario, where a predictor and deferral function are jointly learned (Mozannar & Sontag, 2020; Verma & Nalisnick, 2022; Charusaie et al., 2022;
Proceedings of the r2nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Realizable Multiple-Expert Deferral
Mozannar al., 2023; Mao al., 2024a), and a two-stage scenario, where the predictor is pre-trained and fixed as expert, and while only the deferral function is subsequently leamne (Mao et al., 2023a).
multiple-expert case than the single-expert case. In Sec- tion 3, we derive realizable surrogate losses for single-stage multiple-expert deferral. We begin by deriving an alternative formulation for the deferral loss, which serves as the foun- dation for defining a novel family of surrogate losses (Sec- tion 3.1). We then establish the realizable ---onsistency of these loss functions under a mild assumption (Section 3.2). Finally, we prove JC-oonsisenccy bounds for a specific sur- rogate loss within this family (Section 3.3).
In particular, Mozannar& & Sontag (2020). Verma & Nalis- nick (2022), and Charusaie et al. (2022) proposed surrogate loss functions for the single-stage single-expert case by generalizing the cross-entropy loss, the one-versus-all loss, and, more generally, broad family of surrogate losses for multi-class classification in the context of learning to defer. However, Mozannar et al. (2023) later showed that these sur- rogate loss functions do not satisfy realizable -Cconsisttnccy. They suggested an alternative surrogate loss that achieves this property but left open the question of whether it was also Bayes-consistent. This was later resolved by Mao al. (2024i), who introduced broader family of surrogate losses that simultaneously achieve Bayes-consistency, realizable H-consistency, and H-consistency bounds.
In Section 4, we define realizable surrogate losses for two- stage multiple-expert deferral. We first prove that family of surrogate losses is realizable R-consistent, R-consssttnt,, and payes-consistemt in the two-expert case (Section 4. 4.1). Next, we extend this family of surrogate losses and their consistency guarantees to the multiple-expert case under natural assumptions (Section 4.2).
In Section 5, we present enhanced bounds for the intermedi- ate case of distributions satisfying low-noise assumptions. We provide guarantees for both the single-stage (Section and two-stage (Section 5.2) scenarios.
For the single-stage multiple-expert setting, Verma et al. (2023) were the first to extend the surrogate loss proposed in (Verma& & Nalisnick, 2022) and (Mozannar & Sontag, 2020) to accommodate multiple experts. Building on this, Mao et al. (2024a) further generalized the surrogate loss from (Mozannar& & Sontag, 2020), introducing broader family of surrogate losses tailored to the multiple-expert case. Fur- thermore, Mao et al. (2024a) proved that their surrogate losses benefit from H--consistency bounds in the multiple- expert case, thereby ensuring Bayes-consisteng However, these loss functions are not realizable H--consistent even in the single-expert case, as they are extensions of the earlier loss functions. Can surrogate loss functions for single-stage multiple-expert deferral be derived that admit realizable HC- consistency, along with H--consistency bounds and Bayes- consistency?
Finally, in Section 6, we report the results of experiments using the proposed surrogate losses, comparing their perfor- mance against existing baselines.
For a summary of previous work on consistent multiple- expert deferral and a more detailed discussion of related work, see Table and Appendix A, respectively. We begin with a formal introduction to the learning problems and key concepts.
2. Preliminaries
Single-stage multiple-expert deferral. Let X denote an input space, and let y y= [m] == (1,..., nn represent a label space with n 2 labels, as in the standard multi-class classi- fication setting. In the single-stage scenario, the learner has the option to predict the true label defer the prediction to one of ne pre-defined experts. In this scenario, the label space y is augmented with ne additional labels, {n+ +,+1,,.. I,..., n ne). corresponding to the ne experts 91..... In.- Each expert may represent a human expert or a tre-trained model. Specifically, each expert can be expressed as a function mapping x y to R. Let y [n + n.] denote the augmented label set, and let H be hypothesis set of functions mapping X x ÿ to R. Let Hall represent the family of all such measurable functions. The goal of the learne is to select hypothesis h e H that minimizes the following single-stage deferral loss function, Ldef, defined for any h E Hall and (x. v) E xXxx
In the two-stage scenario, Mao et al. (2023a) introduced surrogate losses that are Bayes-consistent and realizable K-cconsitentt for constant costs. However, their realizable K-consistency does not extend to cost functions of inter- est, which are based on classification error. Can we derive surrogate loss functions for two-stage multiple-expert de- ferral that achieve realizable Hocossittyy F-connistencyy bounds, and conessccnns for cost functions based on classification error?
eeettipleeexpert deferral
It is also important to analyze properties beyond realizable H-consistency whose guarantees hold under deterministic assumptions, while HH-consistency bounds extend to arbi- trary distributions. Can we offer guarantees for intermediate cases, particularly for distributions satisfying low-noise as- sumptions?
x y as follows:
Laor (h, v) 1 hx))=y 11 hnx))sm]]* + Σ )) ((==)=+t)>
This work addresses all of these questions. Note that these challenges are more significant and more complex in the
where h2x) = argmax.yentta 1(x, y) is the prediction as- sociated with h H. for an input x e X,, using an arbitrary
2

---

Realizable Multiple-Expert Deferral
Table Summary of Previous Work on Consistent Multiple-xxpert Deferral
Related Work
Deferral Setting
Realizable H-- HCCoonsstencyy
Bayss-Consistency
HC- HCCoonsstt Bounds
(Verma et al., 2023)
Single-stage
No
Yes
Yes
(Mao et al., 2024a)
Single-stage
No
Yes
Yes
(Mao et al., 2023a)
Two-stage
No
Yes
Yes
but fixed deterministic strategy for breaking ties. When the prediction h(z) is in y. the incurred loss coincides with the multi-class zero-one classification loss. When the prediction h(z) equals n j. the incurred loss is the cost of deferring to expert 9z, denoted by ej (z: v). The choice of this cost is highly flexible. A common choice is define it as gj 's clas- sification error (Verma et al., 2023): oj (z, 1 (r)) where gj (x)= argmaxye[n] g3 (x,y) represents the predic- tion made by expert 9j for input x.
stage case, these definitions extend naturally by replacing the hypothesis h with r and the hypothesis set H with R. For clarity, we will introduce these concepts in the single- stage setting as an example, though they also apply to the two-stage case.
A necessary and fundamental property of a surrogate loss is Bayes-consistency (Zhang, 2004a; Bartlett et al., 2006; Zhang, 2004b; Tewari & Bartlett, 2007; Steinwart, 2007; Mozannar & Sontag, 2020; Verma & Nalisnick, 2022), which means that minimizing the excess error of the sur- rogate loss L leads to minimizing the excess error of the deferral loss Laef-
Two-stage multiple-expert deferral. In the Iwo-stage multiple-exper exprrteeeeepttteeeee deferral scenario, a label predictor is as- sumed to have been learned during the first stage. The second stage involves a set of ne predefined experts, denoted 91.....9nz In,, which includes the first-stage label pre- dictor. We define y as [ne] == Re.. In this setup, the learner's 's objective is to select suitable expert 9j for each instance, considering both the expert's accuracy and infer- ence cost. More formally, let R represent a hypothesis set of functions mapping X' x [ne] to IR, and let Rall denote the family of all such measurable functions. The goal is to choose a predictor r e R that minimizes the following two- stage deferral loss function, Lidef, defined for any r Rall and (x. y) E Xx x y as follows:
Definition 2.1. A surrogate loss L. is Bayes-comsistent with respect to Ldef if for any sequence of predictors {(h,)) a Hall such that [EL(h.. - EL (Hau)) con- verges to zero as n + +00, [ELam (lin) - ELaer (Hal)) con- verges to zero too.
Bayes-consistency does not take into account the specific hypothesis set H adopted in practice and assumes that op- timization is performed over the family of all measurable functions. Consequently, a peppthesis-deendeent guarantee, such as realizable JC-consistency (Long & Servedio, 2013; Zhang & Aggrwal, 2020; Mozannar al., 2023; Mao et al., 2024i) and "H-consistency bound (Awasthi et al., 2022a;b; Mao et al., 2023f) (see also (Awasthi et al., 2021a;b; 2023; 2024; Mao et al., 2023b;e; Zheng et al., 2023; Mao et al., 2023c;d; 2024f:g; Cortes et al., 2024; 2025; Mao et al., 2025; Zhong, 2025)), is more informative and relevant.
(T, Σ e (,(,,))
where r(x) argmaxxu(nn_] r(z, v) represents the predic- tion associated with r É R for an input E X. using an arbitrary but fixed deterministic strategy for breaking ties. The cost ej (I, 3) is incurred when the learner chooses to de- fer to expert 9j- As in the single-stage scenario, the choice of the cost is flexible and can be defined as gj 's classification error (Mao al., 2023a): (x.,)) 1 (x)ovr
Definition 2.2. We will say that surrogate loss L is realiz- able H-consistent with respect to Lder if for any realizable distribution (a distribution for which there exists h e H satisfying EL (h*) = 0), if h is in argmin (h) then ELase (h) = O.
Learning with surrogate losses. Minimizing the single- stage or two-stage deferral losses is computationally in- tractable for most hypothesis sets due to their non-conti and non-diiferentiabiiity, as for the multi-class zero-one loss. Instead, we will consider surrogate losses for the deferral loss. Let D be distribution over X y and let L be loss function. The generalization error of a hypothesis h H is defined by & (h)= = (x [L(h, ar, v)] and the best-in- class generalization error by (36) = infrerr (h). We refer to the difference (h) - E (I)) as the estimation error. When H( = Hall we refer to E (HGa) as the Bayes error and E (h) E (Hal) as the excess error, In the two-
Realizable H-consistency is an asymptotic guarantee and is independent of Bayes-consistency. An H-ccossisenncy bound, on the other hand, is non-asymptotic and always implics Bayes Bayes-consistency.
Definition 2.3. surrogate loss L is said to admit an H-- consistency bound, if there exists non-decreasing concave function r: R, R, with [(0) O, such that the following inequality holds for all h E H and all distributions:
ELOA (h) - EEi (3( MLL. (H)
- (3()),
3

---

Realizable Multiple-Expert Deferral
where the minimizability gap My (H) is defined as ML( = (+() - [infneeee (0,, y)]]
where v: [0,1] RR, u [+00} is non-increasing func- tion. A specific choice of v is the family V. defined for all (0, by (n(u) = _ (ll-wi u²) for q O, and q
For convenience, we refer to (h),x)) = BygeeL(h, and ei (HC.a) = inf CL 2) as the conditional enror and best-in-class conditional error, respectively. We refer to the difference, xh) - hnf (L(h, x), as the con- ditional regret and denote it by ACL,X (h. The mini- mizability gap is the difference between the best-in-class generalization error and the expected best-in-class condi- tional error. It can be upper-bounded by the approximation error and vanishes when FC- = Han (Awasthi et al., 2022a;b; Mao et al., 2024d). Thus, an H-consistency bound implies Bayes-consistency, However, in the deferral setting, the min- imizability gap may not vanish for a realizable distribution. Therefore, K--consistnncy bounds do not imply realizable K-consistency (Mao et al., 2024i).
V Vu(u) = =ooo(()) for q= O. For q= 0. V corresponds to the (mulltinoiial) logistic loss (Verhulst, 1838; 1845; Berk- son, 1944; 1951), while q (0, corresponds to the gen- eralized cross-entropy loss (Zhang & Sabuncu, 201 8), and q= 1 to the mean absolute error loss (Ghosh et al., 2017). For the indicator function (h(=))y?/(()))==) we adopt the following modified comp-sum surrogate loss, as in (Mao et al., 2024i): vo e ( (ebl) This leads to the follow- ing new family of surrogate losses for the deferral loss:
Evee chteiss)
Ex, +1 +1 the 1 1=1
Lh,,,,,,
(Mlors) + eb(onnt))
Σ
[1 (x,,)(,,)) w)]
(3)
3. Single-Stage Multiple-Expert Deferral
Σ (care)
j=1
In this section, we derive realizable surrogate losses for single-stage multiple-expert deferral. We begin by proving an alternative formulation for Ldef. which serves as the foundation for defining novel family of surrogate losses. Next, we establish the realizable JC-consistency of these loss functions under a mild assumption. Finally, we establish cf-cossiste bounds for a specific surrogate loss within this family.
where V:: [0. 1] + R. u (+oo) is a decreasing function.
3.2. Realizable J- JC-Consistency
A hypothesis set H is said to be closed under scaling if, (h e EH) implies (ah E H) for any a E IR. This property is satisfied by many broad function classes, including linear functions and various families of neural networks. The following result shows that, under mild assumptions, our proposed surrogate losses are realizable K-consistent when H is closed under scaling.
3.1. New Surrogate Losses
We first prove that the following alternative expression holds for Ldef. The proof is included in Appendix B.I.
Theorem 3.2. Assume n. 2 2 and H closed under scaling. Then, if L satisfies lim (u) =0 and lim V V()) 1, then the surrogate loss L.p is realizuble H-consistent with respect to Ldef.
Lemma 3.1. The deferral loss can be expressed as follows: V Vh,, x) e Han x X y.
Lief (h,
nee
(x -ma -nJlheeeee
The proof is given in Appendix B.2. Note that for ne 1, our surrogate loss formulation (3) coincides with that of LAL2D in the single-expert case by Mao et al. (2024i). In this special case, the following result holds.
[1 c2(2 (z, (nno)
We use this formulation to derive a new family of surro- gate losses by replacing the indicator functions in (1) with smooth loss functions. The first indicator function, ((()))y corresponds to the multi-class zero-one loss. Thus, a nat- ural approach to substitute it with surrogate loss used in standard multi-class classification. In particular, we fo- cus on the broad class of comp-sum losses (Mao et al., 2023f), which includes many well-known loss functions, such as the logistic loss. Comp-sum losses are defined for all (h, x. y) e H. x X y as:
Theorem 3.3 (Theorem 4.1 in (Mao et al., 2024i)). Assume The = 1 and H closed under scaling. Then, if satisfies lim (u) = O, then, the surrogate loss Ly is realizable K-consistent with respect to Laef-
Compared to the single-expert case where n. an addi- tional condition, lim (u) = 1, is required for Ly to be realizable H-consistent with respect to Laef, stated in Theorem 3.2. This condition rules out the case where v (u) log(u)) but is satisfied by functions v = V, when q > O. We will verify in a simulated example in Section 6 that the surrogate loss Ly with v = V. (q > 0) is realizable H-consistent.
M(ay))
V
Eveoy ch(xrrr5
4

---

Realizable Multiple-Experl Deferral
3.3. "f-Consistency Bounds
4. Two-Stage Multiple-Experr Deferral
We now show that in the special case of v = 1, that is (u) =0 u, Ly admits an H-coosistyycyy bound and is Bayes-consistent with respect to Ldef. For this case, the conditions lima-1 (u)) 0 and lima-o (u) 1 also hold. We denote the resulting surrogate loss as Lmae- is defined as follows for any (h, x) E Hall x X x y:
Recall that in the two-stage multiple-expert deferral setting, the goal is find deferral function r:Xx x [n.]] that minimizes the following two-stage deferral loss:
Lider (1,
Σ cg(2,)) 3-1
We denote by E; 2 and Tj 2 0 the lower and upper bounds of the cost cy, for any j ff,,...,1 ne).
Lmaee (, x.
eh(x,2)
(2, v) +1 nee
4.1. Two Experts
We first consider the two-expert case (n. 2). The two- stage deferral loss can be then be written as follows:
(l229)) + cllannn))
(1--((1))))) 1-1
(4)
Lidet (r, xt, y) ea (I.z) ()) c2 ()),)))(()))
A natural surrogate loss admits the following form:
We say that hypothesis set is symmetric if there exists family& F of functions mapping from X to IR such that [[h(z, 1)....,((I,,, ,,,,,, n n.]]:h h 30} g We say that a hypothesis set H is complete if for any (x,y)= E X x y, the set of scores generated by H spans all real numbers: (h(x,y) h e } TR. Commonly used hypothesis sets such as families of neural networks, linear functions, and all measurable functions, are both symmetric and complete.
(r, x, = ci (),,)))(((r,)2)) (((,))
+ (r(())))(((z,,))))))))))))))))))
(5)
where O + R, is a decreasing function that defines a margin- loss binary classification. As an exam- ple, for Φ(t) = log(1 + e-),, Ls can be expressed as the following cost-sensitive logistic loss:
L (r,r,,,)) c1 y) log +2((,)))
Theorem 3.4. Assume that K is symmetric and complete. Then, for all h H and any distribution, the following H-consistency bound holds:
cz((2,)) v) log 1 [ee ((2.))))
(6) Next, show that this surrogate loss is realizable H- consistent with respect to Lidef.
ELacs (1)) ELeer (3) + Mi (H)
Theorem 4.1. Assume that R is closed under scaling and that & satisfies lim, (t) 0 and (t) 2 Lı5o- Then, the surrogate loss L& is realizable R-consistent with respect to Ltdef-
$ (n ne) (ELmuc (h) - ELamc (H)+ ML (H)).
The proof is given in Appendix B.3.2. Theorem 3.4 in- cludes the single-expert case (Theorem 4.3 in (Mao et al., 2024i)) as a special instance when ne = 1. In the proof, we first characterize the conditional regret of the defer- ral loss, which determined by the key quantities Pn-, = Eyey (1 (y)
The proof is provided in Appendix C. The following result further establishes that Lg satisfies an R-consistency bound with respect to Lidets provided that + is associated with an R-consistency bound in binary classification.
(x) for j e [me]- For the multiple- expert case, the proof becomes more complex because argmaxxe[n.] Pn-.j Pne may differ from argmax 1(x2, n j). In contrast, these quantities coincide in the single-expert case. Moreover, the more complicated forms of both the surrogate loss and the deferral loss in the multiple-exper expert setting introduce further layers of complexity to the proof.
Theorem 4.2. Assume that the following R-consistency bound holds in binary classification:
Ero- (h) Etam (R) + MMa (R)
S r(& Eo (R) M²)).
Then, the following R-consistency bound holds in two-stage, two-expert deferral:
When H Han, the family of all measurable functions, the minimizabilityy gaps vanish. In this case, Theorems 3.4 implies the excess error bounds and Bayes-consistency guar- antees of Lmse. Along with Theorem 3.2, we conclude that Lma is both realizable H-consistent and benefits from HC-
ELeses (r) - -Etrcs (R) + Mi (R)
(τ) + +2) ELD (r) EL, (R) Mr, (R)
G + L2
consistency bounds (thus ensuring Bayes-consisteneyy for single-stage multiple-expert deferral.
where constant factors (c, + Cz) and (ō) 22) can be re- moved when linear.
5

---

Realizable Multiple-Expert Deferral
The proof is presented in Appendix C.2. Note that, as shown by Awasthi et al. (2022a), when H. consists of common function classes such as linear models, neural network fam- ilies, or the family of all measurable functions, and for (()) = e- or (t) = log(1 + e I can be chosen as the square-root function. Similarly, for (t) = max(0, O, 1 1--t), t), can be chosen as the identity function, resulting in linear bound. Combining this with Theorem 4. we conclude that Lo is not only realizable R-consistent but also benefits from R-consistency bounds, thereby also ensuring Bayes- consistency, in the two-stage two-expert deferral setting.
consistency bound holds:
ELeaut (r) ELuees (R) + Mi (3)
$ LI(LLO, (r) ELo, (3) Mi,, (8)).
where C (ne- maxxeln, C- 13 [(1) 2())² Vi
when 9 = 0, I(t) 2(n 7) (C)) when q E (0, 1), and
r(1) Al when q =
Appendix C.4 contains the proof. Collectively, Theo- rems 4.3 and 4.4 show that for two-stage multiple-expert deferral, Lv, is both realizable R-consistent, and admits R-consistency bounds, thus ensuring Bayes-consistency.
4.2. Multiple Experts
Next, we consider the general multiple-expert case where
n, 2. Motivated by the formulation of the surrogate loss in the two-expert case and the comp-sum losses (Mao et al., 2023f) in standard multi-class classification, we propose the following surrogate loss for the multiple-expert case:
5. Enhanced Bounds under Low-Noise Assumptions
In the previous sections, we established guarantees for re- alizable H--consistnncy and H-coossitenccy bounds in the context of learning with multiple-expert deferral. Realizable K-consistency provides guarantees under deterministic as- sumptions, while H-consistency bounds extend arbitrary distributions. This raises natural question: can offer guarantees for intermediate cases, particularly for distribu- tions satisfying low-noise assumptions? In what follows, we address this question separately for the single-stage and two-stage scenarios.
Lg (r,
12
(a(a))
Σ
Σ (2,1) - + /
=
1 en(en))
where V: 10 + R, u { is decreasing function, such as (1) = 1- u or V((u) = log(u), as discussed in Section 3.1. Note that when n. = 2, this formulation coincides with the one in the two-expert case, as shown in (5), with t: - v/( ef As an example, in the case where (u) = log( Lo can be expressed as follows:
af+T]
5.1. Single-Stage Scenario
We first characterize the conditional error and conditional regret of the deferral loss. Let Imax = argmax,e p(y]z).
Σ (x(2x - ne + log 1+ Σ (r(ad)) 5z4j
Pymae = p(ymax//z) (z) and Pn+j = Eyey (1
j [m.]. For any h e Hall, define:
When ne = 2, this formulation coincides with the one in the two-expert case, as shown in (6). Next, we show that the surrogate loss Lg is realizable K-consistent with respect to Lider under natural assumptions about the cost functions and the auxiliary function V
Ph(x) = (p(h()))=) h(x) E [n]
Pnusj
h(x) =
Lemma 5.1. Assume that K is symmetric and complete.
Then, for any h H and input E X, the conditional error and conditional regret of the deferral loss are given by:
Theorem 4.3. Assume that R is closed under scaling and E, j [m.]. Further, assume that for any (I, 3). there is at most one expert j* [ma]] for which Cye (a, v) = 0 and that & satisfies lim V (u) 0. Then, the surrogate loss Ly is realizable R-consistent with respect
that ey (2r,
Clact (h, = 11-Ph(x)
Aer 2e (h,, max Pymax max Pitts] Pn(x))
to Lidef-
je[n.]
The proof is included in Appendix C.3. Next, we consider the case where (u) M, which satisfies the conditions lim (u) = 0. The following result shows that Lv, also admits an R-consistency bound with respect to Lidef-
The proof of Lemma 5.1 is included in Appendix B.
The original Tsybakov noise definition was introduced and further studied in the context of standard classification (Mammen & Tsybakov, 1999; Mao et al., 2024c). We ex- tend this definition to the setting of the deferral loss with multiple experts and establish new K-consistency guaran- tees under this noise assumption.
Theorem 4.4. Assume that R is symmetric and complete and that the inequality Eges Cy (2.y) 2 ne - 2 holds for all j [ne] and (v,y) X Y. Then, the following R-
6

---

Realizable Multiple-xxperl Deferral
This extension relies the concept of the Bayes classifier for the deferral loss. By (Mao et al., 2024d, Lemma 2.1), there exists measurable function h* that satisfies (x) max Pumae [a.] p. for all fies h" as the Bayes classifier for the deferral loss. We can now define the minimal margin for point e X as ((:)) (a) yup (z) Py and the single-stgee defernal Tsybakov noise assumption as follows: there exist B > 0 and a [0, 1) such that the following inequality holds:
ELaat (Hal). Assume that the following holds for all h H and x X: Ae T(A ()) with T(x) = x2, some 8 1. Then, for any e H,
I which identi-
ELUe (h) ELLor
S c ([L()) - E](( + ML( -a((-)
The proof is given in Appendix D.1.3. Note that as a 1, where the Tsybakov noise corresponds to Massart's noise assumption, this result yields an H-consistency bound with a linear functional form, improving upon the standard H-consistency bounds, which have the functional form T(x) = 2², when such bounds exist. This shows that for any smooth surrogate losses with an H-consistency bound, under Massart's noise assumption, we can obtain H-- consistency bounds as favorable as those of L Lmae. which always admit a linear dependency, as shown in Theorem 3.4.
vt> O. P[((X) s <t] Btt
Thus, this noise assumption posits that the probability of observing a small margin is relatively low. Note that when + 1, t + O, which corresponds to an analogue of Massart's noise assumption in the deferral setting. The following lemma establishes basic properties of single-stage deferral Tsybakov noise assumption, extending a similar result from the classification setting by Mao et al. (2024e).
For example, in the special case of a single-expert, Mao et al. (2024i, Theorem 4.2) shows that square-root K-consistency bounds hold (s = 1) for = Lv, with E [0. Theo- rem 5.4 provides refined J--consistency bounds for these surrogate losses: linear dependence when Massart's noise assumption holds (a 1) and intermediate rate between linear and square-root for other values of a e (0,1).
Lemma 5.2. The single-stage deferral Tsybakov noise as- sumption implies that there exists a constant c= B 0 >
such that the following inequalities hold for any h e H.
([)n())+h~()) (n)))()))
$ Sc(ELas Eleer (
Furthermore, we know that the realizability assumption can be viewed as a special case of Massart's 's noise assumption. Thus, Theorem 5.4 provides intermediate guarantees be- tween realizable HK-consistency and H-consistency bounds for stgge-stage deferral surrogate losses, such as LL2D con- sidered in (Mao et al., 2024i).
The proof of Lemma 5.2 can be found in Appendix D.1.1. We first derive an K-consistency bound in terms of the quantity (()) which appears on the left-hand side of the statement of Lemma 5.2.
Theorem 5.3. Consider the setting of single-stage multiple- expert deferral. Assume that the following holds for all h H. and x E X: ACtue (h) s T(AEL x)) with I(x)= = xh. for some 2 with conjugate number t 2 1, that is 1
5.2. Two-Stage Scenario
5. 7==1 =1. Then, for any h e K,
We now extend results the two-stage scenario. As in the single-stage case, we begin by characterizing the best-in-class conditional error and the conditional regret of the two-stage deferral loss function Leder (Lemma C. I in Appendix C.4.1). In particular, the Bayes conditional error is Cr (Ral,,))) = minje[m..] Eyey ((
ELeer (h) - Elae (H) Miaa (H()
s (x] ( (EL(h) -I(())++++))))))) M
The proof of Theorem 5.3 is included in Appendix D.1.2. Theorem 5.3 offers a stronger theoretical guarantee compared to standard H-cconistenncy bounds, under the assumption ACL.m.x(hh, < (h, This bound includes the bypothesis-dependen factor Ex (x)]
By (Mao al., 2024d, Lemma 2.1), there exists a measur- able function r" such that
Ep(ola)crcs))tt.)) = min (r,)))) yey!
jc[n.] yey
which more favorable than the constant factor of one in standard bounds.
for all x X. This function r" thus defines a Bayes classifier for the two-stage deferral loss. Define the minimal margin for a point x e <X as follows: ((x)
Next, we assume that the Tsybakov noise assumption holds and also that there is no approximation error, that is Maa (H)) (00)=00 O.
inf Ee(ult))(a - (p(ul)))r)))(..)) 0.
jar (1) yey
yey
Theorem 5.4. Consider the setting of single-stage multiple- expert deferral where the Tsybakov noise assumption holds, and no approximation error occurs, that is, &L (H) =
The awo-stage Tsybakov noise assumption can then be de- fined as follows: there exist B > and a E [0, 1) such that
7

---

Realizable Multiple-xxpert Deferral
the following inequality holds:
Table 2. Comparison of Our Method with Singlc-Stage Baselines.
V O, P(((()) x 1] B
(9)
Ratio of Deferal (%)
Method
Dataset
SA (%)
PRED
EXP
EXP2 2
As in the single-stage setting, Lemma D.2 in Appendix D.2.1 establishes fundamental properties of the Tsybakov noise assumption within the context of the two-stage scenario. We also derive the enhanced bounds (Theorems D.3 and D.4) for the two-stage scenario, with their detailed presentation deferred to Appendix D.2.2 due to space limitations.
Verma et al. (2023)
91.85 +0.008
62.88
11.23
25.89
Mao et al. (2024a)
CIFAR 10
91.98 0.09
66.63
13.65
19.72
Ours
92.21 0.18
38.79
20.45
30.76
Verma al. (2023)
64.13
39.77
35.95
24.28
Mao et al. (2024a)
CIFAR- 100
64.93 0.22
49.19
27.69
23.12
Ours
65,39 a 0.31
34,38
30.52
35.10
Verma et al. (2023)
95,91 :: 0.08
64.66
25.96
9.38
et (2024s)
SVHN
95.78 0.06
78.93
10.09
Ours
96.08 0.11
27.11
43.42
29.47
6. Experiments
Verma et al. (2023)
50.61 0.50
46.96
25.59
27.45
Mao et al. (2024a)
Tiny ImageNet
50.89 0.49
45.56
37.88
16.56
In this section, we evaluate the empirical performance of our proposed surrogate loss, comparing it against existing baselines in both single-stage and two-stage learning-to- tooni defer scenarios with multiple experts. Our objective is to confirm that our loss functions match the best-known results in rea-realizable settings for both single- and two-stage cases while outperforming them in realizable settings, predicted by theoretical analysis.
Ours
51.13 0.56
21.68
32.60
Table 3. Comparison of Our Method with Two-Stage Baselines.
Ratio of Deferral (%)
Method
Dataset
SA (1E)
EXP
EXP
EXP 3
Mao et al. (2023a)
92.92 =: 0.14
30.23
30.49
39,28
Ours
CIFAR-10 10
93.34 = 0.18
29.34
30.90
39.76
Mao et al. (2023a)
67.99 a: 0.19
32.44
34.42
33.14
Experimental setup. For our experiments, we used four widely used datasets: CIFAR-10, CIFAR-100 (Krizhevsky, 2009), SVHN (Netzer et al., 2011) 1), and Tiny ImageNet (Le & Yang, 2015). Each dataset was trained for 200 epochs. We adopted ResNet-16 (He et al., 2016) for the predic- tor/deferral models. The Adam optimizer (Kingma& & Ba, 2015) was used with a weight decay of 1 x 10-3 and a batch size of 1024. Following (Mozannar et al., 2023; Mao et al., 2024a), we define the cost function as the expert's classifi- cation error: c,(x,)) 8) = 1 E; (u)++y in our empirical analysis. We reported the means and standard deviations over five runs. For simplicity, we omitted the standard deviations of the deferral ratios.
Ours
CIFAR-100
68.70 0.23
31.34
29.89
38.77
Mao et (2023a)
96.30 0.06
42.18
29.68
27.94
Ours
SVHN
96.47 + 0.08
42.52
29.70
27.78
Mao et al. (2023x)
45.81 =: 0.17
36.64
28.64
34.72
Ours
Tiny ImageNel
46.62 + 0,24
26.82
38.15
35.03
behavior that is qualitatively different from prior approaches, particularly on the SVHN and Tiny ImageNet datasets.
Two-stage multiple-expert deferral. In the two-stage sce- nario, we compared our proposed surrogate loss Ly (7) with (u) = - -log(w) u) with the baseline surrogate losses proposed in (Mao et al., 2023a). While the baseline sur- rogate losses are Bayes-consistent, they are not realizable H-consistent with cost functions based on classification er- ror: cs cz( 3) (z)))) In our experiments, we used the multinomial logistic loss as the multi-class classification surrogate for the baseline surrogate losses. As in the single- stage scenario, we considered setting where multiple ex- perts are available, each with a clear domain of expertise. We used three experts, with two of them the same those adopted in the single-stage setting. Additionally, we intro- duced a third expert that predicts from the remaining 40% of classes and is accurate if the true label is within this range. As shown in Table 3, our method achieves comparable two- stage system accuracy (SA), defined as the average value of [ider (h, x. })] on the test data, to the baselines. The different deferral ratios it achieves, compared to the baseline, demonstrate the effect of our proposed surrogate loss.
Single-stage multiple-expert deferral. In the single-stage scenario, we compared our proposed surrogate Ly (3) with (u)= = u with the baseline surrogate losses proposed in (Verma et al., 2023) and (Mao et al., 2024a). While these surrogate losses are Bayes-consistent, they are not realizable JC-consistent. For both surrogate losses, we used the logistic loss function as their auxiliary function in our experiments. Building on the setup described in (Mao et al., 2024a), we used two experts, each with a distinct domain of expertise. Expert 1 always predicts from the first 30% of classes and is correct whenever the true label falls within this range. Similarly, Expert 2 predicts from the next 30% of classes, following the same criterion for accuracy. As shown in Table 2, our method achieves comparable single- stage system accuracy (SA), defined as the average value of La- (h, 2r, v)] on the test data, to the baselines. Due to the specific realizable form of our surrogate losses, it also defers significantly more and exhibits a greater tendency to choose expert 2 compared to the baselines. This highlights a key effect of our proposed surrogate: it induces deferral
Realizable multiple-expert deferral. We also conducted an additional experiment in the realizable scenario, by ex- tending the synthetic Mixture-of Cocturr-of-Gaussse Gaussians dataset from (Mozannar et al., 2023) to the multiple-expert setting. This
8

---

Realizable Multiple-xxpert Deferral
unlike the baselines, as illustrated in Figure 1.
0.95
System Accuracy
7. Future Work
0.90
Our paper primarily focuses on theoretically principled sur- rogate losses for learning to defer with multiple experts, grounded realizable K-consistency and H-consistency bounds, within the learning theory framework. While we have empirically shown that minimizing our proposed loss functions outperforms the baselines in realizable set- tings and matches the best-known results in synthetic non- realizable settings, as predicted by our theoretical analysis, we recognize the importance of further empirical explo- ration. Accordingly, we plan to dedicate future work to con- ducting more extensive empirical analysis in worl-world settings, particularly in important scenarios where expert domains overlap and the data is heterogeneous.
0.85
Verma et all. (2023)
0.80
Mao et al. (2024b)
Ours (V* V. with q 11
Ours (v 4/ with 0.71
0.75
1000
2000
3000
4000
5000
Training sample size
Figure 1. System Accuracy vs. Training Sample Size.
extended dataset is realizable by linear functions, as there exists a randomly selected linear hypothesis ht" H that achieves zero single-stage deferral loss, LL (h*) = We set the true label to match the predictor's prediction when deferral does not occur according to h" Otherwise, the true label is generated uniformly at random. We used two experts whose predictions align with the true label only when they are chosen by he' to make the prediction. For our surrogate loss Ly (3), we selected V = Vg with q= 0.7 and q = 1. We compared these surrogate losses to those introduced in (Verma et al., 2023) and (Mao et al., 2024a). Figure 1 shows system accuracy samples on the realizable Mixture-of-Gannt -fa--sssinnaanss distribution, verifying our theoretical results that both choices of Ly are realizable H-consistent, while the two baselines are not.
We also acknowledge the relevance of more realistic and challenging scenarios, such as those where expert predic- tions are unavailable during training. Extending our meth- ods to these scenarios is a promising direction for future work. For example, it would be interesting to adapt our framework to handle previously unseen experts at test time, as studied by Tailor et al. (2024) and to incorporate post- processing frameworks for learning to defer under con- straints such as OOD detection and long-tail classification, as explored by Charusaie & Samadi (2024).
function of training
Our deferral framework also offers promising applications in the context of large language models (LLMs). Given the significant resources required to retrain LLMs,, two- stage method is a practical and scalable solution (Mao et al., 2023a). This does not require modifying LLMs or the loss function used to train them. Our proposed two-stage surro- gate loss is particularly well-suited for use with pre-trained LLMs. In the presence of multiple LLMs (or experts), using our method, uncertain predictions can be deferred to more specialized or domain-specifie pre-trained models, thereby both improving the reliability and accuracy of the overall system and improving efficiency.
The behavior for lower values of q is similar to that ob- served for q = 0.7 and q= Note that for any q > 0, The- orem 3.2 guarantees realizable H-coonistencyy We chose 1 in Figure because they correspond to standard choices in prior work, 9 0.7 is a commonly sug- gested value within the generalized cross- consopy family (e.g., (Zhang& & Sabuneu, 2018); (Mao et al., 2024a)), and q= corresponds to the mean absolute error loss, as used in (GGhosh et al., 2017); (Mao et al., 2024a)). In this real- izable distribution, we observe that our proposed surrogate losses achieve close 100% system accuracy, while all other baselines fail to find a near-zero-error solution. This demonstrates that our surrogates are realizable H-consistent, whereas the compared baselines are not.
q= 0.7 and
8. Conclusion
We presented novel surrogate losses functions and algo- rithms for multiple-expert deferral, offering strong theoreti- cal guarantees for both single- and two-stage scenarios. Our results, including realizable H-consistencyy, H--cosssstnncy bounds, and Eayes-consistency extend to multiple-expert settings and provide enhanced guarantees under low-noise assumptions. Our analysis can be leveraged to study and design algorithms for other routing problems, for example when incorporating constraints, such as limiting the fre- quency with which expert can be used. Experimental re- sults confirm the effectiveness of our principled techniques.
Note that the goal of our experiments on non-realizable data not to claim that our proposed surrogate losses outperform the baselines (Verma et al., 2023; Mao al., 2024a; 2023a) in such settings. Rather, our results show that our surrogate losses match the performance of these ofth--ofthh-artt base- lines in non non-realizable settings in terms of system accuracy, as both are supported by consistency bounds. The strength of our approach lies in the realizable setting, where our sur- rogate losses are guaranteed to be realizable H-consistent,
9

---

Realizable Multiple-Expert Deferral
Acknowledgements
Berkson, J. Application of the logistic function bio-assay.
Journal of the American Statistical Association, 39:357-
thank the anonymous reviewers for their valuable feed- back and constructive suggestions.
365, 1944.
Berkson, J. Why prefer logits to probits. Biometrics, 7(4): 327-339, 1951.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must specifically highlighted here.
Bubeck, S., Chandrasekaran, V., Eldan, R., Gehrke, J., Horvitz, E.. Kamar, E., Lee, P.. Lee, Y. T., Li, Y., Lundberg, S., et al. Sparks artificial general intel- ligence: Early experiments with gpt-4, arXiv preprint arXiv:2303. /2712, 2023.
References
Cao, Y., Cai, T., Feng, L.,, Gu, Gu, An, B., Niu, G., and Sugiyama, M. Generalizing consistent multi-clas clas- sification with rejection to be compatible with arbitrary losses. In Advances in Neural Information Processing Systems, 2022.
Acar, A. E.,, Gangrade, A., and Saligrama, V. Bud- get learning via bracketing. In International Conference Artificial Intelligence and Statistics, pp. 4109-4119, 2020.
Cao, Y., Mozannar, H., Feng, L.., Wei, H., and An, B. In defense of softmax parametrization for calibrated and consistent learning to defer. In Advances in Neural Infor- mation Processing Systems, 2023.
Awasthi, P., Frank, N., Mao, A., Mohri, M., and Zhong, Y. Calibration and consistency of adversarial surrogate losses. Advances in Neural Information Processing Sys- tems, pp. 9804-98155 2021a.
Charoenphakdee, N., Cui. Z., Zhang, Y., and Sugiyama, M. Classification with rejection based on cost-sensitive classification. In International Conference on Machine Learning, pp. 1507-1517, 2021.
Awasthi, P., Mao, A., Mohri, M., and Zhong, Y. A finer calibration analysis for adversarial robustness. arXiv preprint arXiv.2105.01550 2021b.
Awasthi, P., Mao, A., Mohri, M. and Zhong, Y. HC- consistency bounds for surrogate loss minimizers. In International Conference on Machine Learning, 2022a.
Charusaie, M.-A. and Samadi, S. A unifying post- processing framework for multi-objective learn-to-defer problems. In Advances in Neural Information Processing Systems, 2024.
Awasthi, P., Mao, A., Mohri, M., and Zhong, Y. Multi-class H--consistnccy bounds. In Advances in Neural Informa- tion Processing Systems, 2022b.
Charusaie, M.-A., Mozannar, H., Sontag, D., and Samadi, S. Sample efficient learning of predictors that comple- ment humans. In International Conference Machine Learning, pp. 2972-3005, 2022.
Awasthi, P., Mao, A., Mohri, M., and Zhong, Y. Theoreti- cally grounded loss functions and algorithms for adversar- ial robustness. In International Conference on Artificial Intelligence and Statistics, pp. 10077-10094, 2023.
Chen, G., Li, X., Sun, C., and Wang, H. Learning to make adherence-awee aware advice. In International Conference on Learning Representations, 2024.
Awasthi, P., Mao, A., Mohri, M., and Zhong, Y. DC- programming for neural network optimizations. Journal of Global Optimization, 2024.
Cheng, X., Cao, Y., Wang, H.. Wei, H., An, B., and Feng, L. Regression with cost-based rejection. In Advances in Neural Information Processing Systems, 2023.
Bartlett, P. L. and Wegkamp, M. H. Classification with reject option using hinge loss. Journal of Machine Learning Research, 9()), 2008
Chow, C. An optimum character recognition system using decision function. IEEE Transactions Computers, 1957.
Bartlett, P. L., Jordan, M. I., and McAuliffe, J. D. Convexity, classification, and risk bounds. Journal of the American Statistical Association, 101(473):138-155 2006.
Chow, C. On optimum recognition error and reject tradeoff. IEEE Transactions on Information Theory, 16(1):41-46. 1970.
Benz, N. L. C. and Rodriguez, M. G. Counterfactual in- ference of second opinions. In Uncertainty in Artificial Intelligence, pp. 453-463, 2022.
Cortes, C., DeSalvo, G., and Mohri, M. Learning with rejection. In International Conference on Algorithmic Learning Theory, pp. 67-82, 20.6a.
10

---

Realizable Multiple-Experl Deferral
Cortes, C., DeSalvo, G., and Mohri, M. Boosting with ab- stention. In Advances in Neural Information Processing Systems, pp. 1660-1668, 2016b.
He, K., Zhang, X., Ren, S., and Sun, J. Deep residual learn- ing for image recognition. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pp. 770-778, 200 2016.
Cortes, C., DeSalvo, G., and Mohri, M. Theory and algo- rithms for learning with rejection in binary classification. Annals of Mathematics and Artificial Intelligence, pp. 1-39, 2023.
Hemmer, P., Schellhammer, S., Vössing, M., Jakubik, J., and Satzger, G. Forming effective human-ai teams: Building machine learning models that complement the capabilities of multiple experts. In International Joint Conference on Artificial Intelligence, pp. 2478, 2022.
Cortes, C., Mao, A., Mohri, C., Mohri, M., and Zhong, Y. Cardinality- set prediction and top-k classification. In Advances in Neural Information Processing Systems, 2024.
Hemmer, P., Thede, L.., Vössing, M., Jakubik, J., and Küihl, N. Learning defer with limited expert predictions. In Proceedings of the AAAI Conference Artificial Intelli- gence, pp. 6002-6011, 2023.
Cortes, C., Mao, A., Mohri, M., and Zhong, Y. Balancing the scales: A theoretical and algorithmic framework for learning from imbalanced data. International Confer- ence on Machine Learning, 2025.
Jiang, W., Zhao, Y., and Wang, Z. controont selective prediction for regression deep neural network models. In International Joint Conference on Neural Networks, pp. 1-8, 2020.
De, A., Koley, P., Ganguly, N., and Gooeez-Rodriguez, M. Regression under human assistance, In Proceedings of the AAAI Conference on Artificial Intelligence, pp. 2611 2620, 2020.
Jitkrittum, W., Gupta, N., Menon, A. K., Narasimhan, H., Rawat, A., and Kumar, S. When does confidence-biae based cascade deferral suffice? In Advances in Neural Informa- tion Processing Systems, 2023.
De, A., Okati, N., Zarezade, A., and Rodriguez, M. G. Classification under human assistance. In Proceedings of the AAAI Conference on Artificial Intelligence, pp. 5905- 5913, 2021.
Joshi, S., Parbhoo, S., and Doshi-Vedt F. Learning Searning-to-defer for sequential medical decision-making under uncertainty. Transactions on Machine Learning Research, 2023.
EI- Yaniv, R. and Wiener, Y. Active learning via perfect selective classification. Journal of Machine Learning Research, 13(2), 2012.
Kerrigan, G., Smyth, P., and Steyvers, M. Combining human predictions with model probabilities via confusion matri- ces and calibration. In Advances in Neural Information Processing Systems, pp. 4421-4434, 2021.
El-vaniv, R. et al. On the foundations of noise-free selective classification. Journal of Machine Learning Research, 11 (5), 2010.
Keswani, V., Lease, M., and Kenthapadi, K. Towards un- biased and accurate deferral multiple experts. In Pro- ceedings of the AAAI/ACM Conference AI, Ethics, and Society, pp. 154-165, 2021.
Gangrade, A., Kag, A., and Saligrama, V. Selective classi- fication via sided prediction. In International Con- ference on Artificial Intelligence and Statistics, pp. 2179- 2187, 2021.
Kingma, D. P. and Ba, J. Adam: A method for stochastic optimization. In International Conference on Learning Representations, 2015.
Gao. R., S Tsechansky, M., Dr-Arteaga, M., Han, L., Lee, M. K., and Lease, M. Human-ai collaboration with bandit feedback. In International Joint Conference on Artificial Intelligence, 2021.
Krizhevsky, A. Learning multiple layers of features from tiny images. Technical report, Toronto University, 2009.
Geifman, Y. and Yaniv, R. Selective classification for deep neural networks. In Advances in Neural Information Processing Systems, 2017.
Le, Y. and Yang. X. Tiny imagenet visual recognition chal- lenge. CS 23/N, 7(7):3, 2015.
Geifman, Y. and El- Yaniv, R. Selectivenet: A deep neural network with an integrated reject option. In International Conference on Machine Learning, pp. 2151-2159, 2019.
Li, X., Liu, S., Sun, C., and Wang, H. When no-rejection learning is optimal for regression with rejection. arXiv preprint wrXiv:2307.09933 2023.
Ghosh, A., Kumar, H., and Sastry, P. S. Robust loss func- tions under label noise for deep neural networks. In Proceedings of the AAAI Conference on Artificial Intelli- gence, 2017.
Liu, S., Cao, Y., Zhang, Q., Feng. L., and An, B. Mitigating underfitting in learning to defer with consistent losses. In International Conference on Artificial Intelligence and Statistics, pp. 481 4816-4824, 2024.

---

Realizable Multiple-Experl Deferral
Long, P. and Servedio, R. Consistency versus realizable H- consistency for multiclass classification. In International Conference Machine Learning, pp. 801-809, 2013.
Mao, A., Mohri, M., and Zhong, Y. Enhanced H-- consisteney bounds. In International Conference Al- gorithmic Learning Theory, 2024c.
Madras, D., Creager, E., Pitassi, T., and Zemel, R. Learning adversarially fair and transferable representations. In International Conference Machine Learning, pp. 3384- 2018.
Mao, A., Mohri, M., and Zhong, Y. H-consistency guar- antees for regression. In International Conference on Machine Learning, pp. 34712-34737, 2024f.
2018.
Mao, A., Mohri, M., and Zhong, Y. Multi-label learning with stronger consistency guarantees. In Advances in Neural Information Processing Systems, 2024g.
Mammen, and Tsybakov. A. B. Smooth discrimina- tion analysis. The Annals of Statistics, 27(6):1808-1839) 1999.
Mao, A., Mohri, M., and Zhong, Y. Regression with multi- expert deferral. In International Conference on Machine Learning, 2024h.
Mao, A. Theory and Algorithms for Learning with Multi- Class Abstention and Mulli-Expert Deferral. PhD thesis, New York University, 2025.
Mao, A., Mohri, M., and Zhong, Realizable H-consistent and Bayes-consistent loss functions for learning to defer. In Advances in Neural Information Processing Systems, 2024i.
Mao, A.,
Mohri, C., Mohri, M., and Zhong, Y. Two-stage learning defer with multiple experts. In Advances in Neural Information Processing Systems, 2023a.
Mao, A., Mohri, M., and Zhong, Y. H-consistency bounds: Characterization and extensions. In Advances in Neural Information Processing Systemx, 2023b.
Mao, A., Mohri, M., and Zhong, Y. Principled algorithms for optimizing generalized metrics in binary elassification. In International Conference on Machine Learning. 2025.
Mao, A., Mohri, M., and Zhong, Y. H-consistency bounds for pairwise misranking loss surrogates. In International conference on Machine learning, 2023c.
Mohri, C., Andor, D., Choi, E., Collins, M., Mao, A., and Zhong, Y. Learning to reject with fixed predictor: Ap- plication to decontextualization. International Confer- ence on Learning Representations, 2024.
Mao, A., Mohri, M., and Zhong, Y. Ranking with abstention.
In ICML 2023 Workshop The Many Facets of Preference- Based Learning, 2023d.
Mohri, M., Rostamizadeh, A., and Talwalkar, A. Founda- tions of Machine Learning. MIT Press, second edition, 2018.
Mao, A., Mohri, M., and Zhong, Y. Structured prediction with stronger consistency guarantees. In Advances in Neural Information Processing Systems, 2023e.
Montreuil, Y., Yeo, S. H., Carlier, A., Ng, L. X., and Ooi, W. T. Optimal query allocation in extractive QA with LLMs: A tearning-to-defer framework with theoretical guarantees. arXiv preprint 1rXiv:2410.157611 2024.
Mao, A., Mohri, M., and Zhong, Y. Cross-entropy loss functions: Theoretical analysis and applications. In Inter- national Conference on Machine Learning, 2023f.
Montreuil, Y., Carlier, A., Ng. L. X., and Ooi, W. T. Ad- versarial robustness in two-stage learning-to-defer: Algo- rithms and guarantees. In International Conference Machine Learning, 2025a.
Mao, A.,
Mohri, M., and Zhong, Y. Principled approaches for learning to defer with multiple experts. In Interna- tional Symposium on Artificial Intelligence and Mathe- matics, 2024a.
Montreuil, Y., Carlier, A., Ng. L. X., and Ooi, W. T. Why ask one when you can ask k? two-stage learning-to-ded to-defer the top-k experts. arXiv preprint arXiv:2504.1290 12988. 2025b.
Mao, A., Mohri, M.. and Zhong, Y. Predictor-rejector multi- class abstention: Theoretical analysis and algorithms. In International Conference on Algorithmic Learning Theory, pp. 222-867, 2024b.
Montreuil, Y., Carlier, A., Ng, L. X., and Ooi, W. T. One-stage top-k learning-to-defer. Score-based sur- rogates with theoretical guarantees. arXiv preprint arXiv:2505.10166 10160, 2025c.
Mao, A., Mohri, M., and Zhong, Y. Theoretically grounded loss functions and algorithms for score-based multi-class abstention. International Conference on Artificial In- telligence and Statistics, pp. 4753 4753-4761, 2024c.
Montreuil, Y., Yeo, S. H., Carlier, A., Ng. L. X., and Ooi, W. T. A two-stage soamiiggto--defe approach for multi- task learning. In International Conference on Machine Learning, 2025d.
Mao, A., Mohri, M., and Zhong, Y. A universal growth rate for learning with smooth surrogate losses. In Advances in Neural Information Processing Systems, 2024d.
12

---

Realizable Multiple-Experl Deferral
Mozannar, H. and Sontag, D. Consistent estimators for learning to defer to expert. In International Conference Machine Learning, pp. 7076-7087, 2020.
Raghu, M., Blumer, K., Corrado, G., Kleinberg, J., Ober- meyer, Z.,, and Mullainathan, S. The algorithmic automa- tion problem: Prediction, triage, and human effort. arXiv preprint arXiv: 12220, 2019.
Mozannar, H., Satyanarayan, A., and Sontag, Teaching humans when to defer classifier via exemplars. In Proceedings of the AAAI Conference on Artificial Intelli- gence, pp. 5323 5331, 2022.
Ramaswamy, H. G., Tewari, A., and Agarwal, S. Consistent algorithms for multiclass classification with an abstain option. Electronic Journal of Statistics, 12( 12(1):530-554 2018.
Mozannar, H., Lang, H., Wei, D., Sattigeri, P., Das, S., and Sontag, D. Who should predict? exact algorithms for learning to defer to humans. In International Conference Artificial Intelligence and Statistics, pp. 10520-10545, 2023.
Shah, A., Bu, Y., Lee, J. K., Das, S., Panda, R., Sattigeri, P., and Wornell, G. W. Selective regression under fair- ness criteria. In International Conference on Machine Learning, pp. 19598 19615, 2022.
Steinwart, I. How to compare different loss functions and their risks. Constructive Approximation, 26(2):225-255 2007.
Narasimhan, H., Jitkrittuum, W., Menon, A. K., Rawat, A. S., and Kumar, S. Post-hoc estimators for learning defer to an expert. In Advances in Neural Information Processing Systems, pp. 29292-299302 2022.
Straitouri, E., Singla, A., Meresht, V. B., and Gomez- Rodriguez, M. Reinforcement learning under algorithmic triage. arXiv preprint arXiv:2109.11322 2021.
Narasimhan, H., Menon, A. K., Jitkrittum, W., Gupta, N., and Kumar, S. Learning to reject meets long-tai taig learning. In International Conference on Learning Representations, 2024.
Straitouri, E., Wang, L., Okati, N., and Rodriguez, M. G. Provably improving expert predictions with conformal prediction. arXiv preprint arXiv:2201. 12000 2022.
Netzer, Y., Wang, T., Coates, A., Bissacco, A., Wu, B., and Ng, A. Reading digits in natural images with unsupervised feature learning. In Advances Neural Information Processing Systems, 2011.
Tailor, D., Patra, A., Verma, R., Manggala, P., and Nalisnick, Learning defer to a population: A meta-learning approach. In International Conference on Artificial Intel- ligence and Statistics, pp. 3475 1475-3483, 2024.
Neyman, J. and Pearson, E. S. Ix. on the problem of the most efficient tests of statistical hypotheses. Philosophi- cal Transactions of the Royal Society of London. Series A, Containing Papers of a Mathematical or Physical Char- acter, 231 (69 233-3 1933.
Tewari, A. and Bartlett, P. L. On the consistency of multi- class classification methods. Journal of Machine Learn- ing Research, 8(36): (036):107-10000 002-1005, 2007.
Verhulst, P. F. Notice sur la loi que la population suit dans son accroissement. Correspondance mathématique et physique, 10:1 13-121, 1838.
Ni, C., Charoenphakdee, N., Honda, J., and Sugiyama, M. On the calibration of multiclass classification with re- jection. In Advances in Neural Information Processing Systems, pp. 2582-2592, 2019.
Verhulst, P. F. Recherches mathématiques la loi d' l'accroisssement de la population. Nouveaux Mémoires de I' l'Académie Royale des Sciences et Belles-Lettres de Bruxelles, 18: 18:1-42, 1845.
Okati, N., De, A., and Rodriguez, M. Differentiable learn- ing under triage. In Advances Neural Information Processing Systems, pp. 9140-9151, 2021.
Verma, R. and Nalisnick, E. Calibrated learning defer with one-vs-all classifiers. In International Conference Machine Learning, pp. 22184-22202, 2022.
Palomba, F., Pugnana, A., Alvarez, J. M., and Ruggieri, S. A causal framework for evaluating deferring systems. In International Conference on Artificial Intelligence and Statistics, 2024.
Verma, R., Barrejón, D., and Nalisnick, E. Learning to defer to multiple experts: Consistent surrogate losses, confidence calibration, and conformal ensembles. In International Conference on Artificial Intelligence and Statistics, pp. 11415-11455 2023.
Pradier, M. F., Zazo, J., Parbhoo, S., Perlis, R. H., Zazzi, M., and Doshi-Velcz. F. Preferential mixture-of-experts: In- terpretable models that rely on human expertise as much as possible. AMIA Summits on Translational Science Proceedings, 2021:525, 2021.
Wei, J., Tay, Y., Bommasani, R., Raffel, C., Zoph, B., Borgeaud, S., Yogatama, D., Bosma, M., Zhou, D., Met- zler, D., Chi, H., Hashimoto, T., Vinyals, O., Liang,
13

---

Realizable Multiple-Experl Deferral
P., Dean, J., and Fedus, W. Emergent abilities of large language models. Transactions Machine Learning Research, 2022.
Zheng, C., Wu, G., Bao, E,, Cao. Y., Li, C., and Zhu, J. Revisiting discriminative generative classifiers: The- ory and implications. In International Conference Machine Learning, pp. 22420-42477, 2023.
Wei, Z., Cao, Y., and Feng, L. Exploiting human-ai depen- dence for learning to defer. In International Conference on Machine Learning, 2024.
Zhong, Y. Fundamental Novel Consistency Theory: HI- Consistency Bounds. PhD thesis, New York University, 2025.
Wiener, Y. and EI- -l-anivv, R. Agnostic selective classification. In Advances in Neural Information Processing Systems, 2011.
Wiener, and Elniv,,,, R. Pointwise tracking the optimal regression function. In Advances in Neural Information Processing Systems, 2012.
Wiener, Y. and El-Yaniv, R. Agnostic pointwise-competinee selective classification. Journal of Artificial Intelligence Research, 52:171-200 2015.
Wilder, B., Horvitz, E., and Kamar, E. Learning to com- plement humans. International Joint Conferences on Artificial Intelligence, pp. 1526-1533, 2021.
Yuan, M. and Wegkamp, M. Classification methods with reject option based on convex risk minimization. Journal of Machine Learning Research, 11(1), 2010.
Yuan, M. and Wegkamp, M. SVMs with a reject option. In Bermoulli, 2011.
Zaoui, A., Denis, C., and Hebiri, M. Regression with reject
option and application to knn. In Advances in Neural Information Processing Systems, pp. 20073-20082, 2020.
Zhang, M. and Agarwal, S. Bayes consistency vs. H- consistency: The interplay between surrogate loss fune- tions and the scoring function class. In Advances in Neural Information Processing Systems, 2020.
Zhang, T. Statistical behavior and consistency of classifi- cation methods based on convex risk minimization. The Annals of Statistics, 32(1 32(1):56--8)) 366885555 2004a.
Zhang. T. Statistical analysis of some multi-category large margin classification methods. Journal of Machine Learn- ing Research, 5(Oct): 12:c)-1222212:::: 1251, 2004b.
Zhang, Z. and Sabuncu, M. Generalized cross entropy loss for training deep neural networks with noisy labels. In Advances in Neural Information Processing Systems, 2018.
Zhao, J., Agrawal, M., Razavi, P., and Sontag, D. Directing human attention in event localization for clinical timeline creation. In Machine Learning for Healthcare Confer- ence, pp. 80-102, 2021.
14

---

Realizable Multiple-Expert Deferral
Contents of Appendix
Related work
16
Single-stage multiple-expert deferral: proofs.
17
B.1 Proof of Lemma 3.1
17
B.2 Proof of Theorem 3.2...
17
B.3 Proof of H-coonistenccy bounds
18
B.3.1 Simplified notation and proof of Lemma 5.1
18
B.3.2 Proof of Theorem 3.4
19
Two-stage multiple-expert deferral: proofs.
22
C.1 Proof of Theorem 4.1
22
C.2 Proof of Theorem 4.2
23
C33 Proof of Theorem 4.3
24
C.4 Proof of H-consistencyy bounds
24
C.4.1 Simplified notation and Lemma C.I
24
C.4.2 Proof of Theorem 4.4
25
D Enhanced bounds under low-noise assumptions: proofs
28
D.1 Single-stage: proofs
28
D.1.1 Proof of Lemma 5.2
28
D.1.2 Proof of Theorem 5.3
29
D.1.3 Proof of Theorem 5,4
29
D.2 Two-stage: proofs..
30
D.2.1 Lemma D.2 and Proof
30
D.2.2 Enhanced bounds in two-stage stage scenario (Theorem D.3 and Theorem D.4)
30
D.2.3 Proof of Theorem D.3
D.2.4
Proof of Theorem D.4
32
15

---

Realizable Multiple-xxpert Deferral
A. Related work
Single-stage learning to defer, where a predictor and a deferral function are jointly trained, was pioneered by Cortes, DeSalvo, and Mohri 62016a;b; 2023) and further developed in subsequent work. This includes studies on abstention with constant costs (Charoenphakdee et al., 2021; Cao et al., 2022; Li et al., 2023; Cheng et al., 2023; Mao et al., 2024c:b; Mohri et al., 2024; Narasimhan et al., 2024) and deferral with instance- and label-dependent costs (Mozannar & Sontag, 2020; Verma& & Nalisnick, 2022; Mozannar et al., 2023; Verma et al., 2023; Cao et al., 2023; Mao et al., 2024a; Wei et al., 2024; Mao et al., 2024i). In this paradigm, the deferral function decides how imput instances should be optimally assigned to the most suitable expert from a diverse set. This method has demonstrated advantages over confidence-based approaches, which rely solely on the predictor's 's output magnitude (Chow, 1957; 1970; Bartlett & Wegkamp, 2008; Yuan & Wegkamp, 2010; 2011; 1; Ramaswamy et al., 2018; Ni et al., 2019; Jitkrittum et al., 2023); and selective classification methods, which use a fixed selection rate and cannot incorporate expert-modeled cost functions (EI-Yanir et al., 2010; El-Yaniv & Wiener, 2012; Wiener & El- Yaniv, 201 1; 2012; 2015; Geifman & EI- El-Yaniv, 2017; 2019; Acar et al., 2020; Gangrade et al., 2021; Zaoui et al., 2020; Jiang et al., 2020; Shah et al., 2022).
The learning to defer (L2D) problem, which incorporates human expert decisions into the cost function, was introduced by Madras et al. (2018) and further studied by Raghu et al. (2019); Wilder et al. (2021); Pradier et al. (2021); Mozannar & Sontag (2020); Verma& & Nalisnick (2022); Charusaic ct al. (2022); Mozannar et al. (2023); Mao et al. (2023a; 2024a;i). is typically formulated using a deferral loss function that incorporates instance-specific costs associated with each expert. Directing optimizing this loss function is intractable for the hypothesis sets commonly used in applications. Thus, soaming-to-defer algorithms rely on optimizing surrogate loss function instead, that serves a proxy for the original target loss function. Yet, what guarantees can we rely when optimizing such surrogate loss functions?
This question, which involves analyzing the consistency guarantees of surrogate losses with respect to the deferral loss, has been studied under two main scenarios (Mao, 2025): the single-stage scenario, where a predictor and a deferral function are jointly learned (Mozannar & Sontag, 2020; Verma & Nalisnick, 2022; Charusaie et al., 2022; Mozannar et al., 2023; Mao et al., 2024a), and a two-stage scenario, where the predictor is pre-trained and fixed as an expert, and while only the deferral function is subsequently learned (Mao et al., 2023a).
In particular, Mozannar & Sontag (2020), Verma & Nalisnick (2022), and Charusaie et al. (2022) proposed surrogate loss functions for the single-stage single-expert case by generalizing the cross-entrope loss, the one-versus all loss, and, more generally, a broad family of surrogate losses for multi-class classification in the context of learning to defer. However, Mozannar et al. (2023) later showed that these surrogate loss functions do not satisfy realizable H--consistency. They suggested an alternative surrogate loss that achieves this property but left open the question of whether was also Bayes- consistent. This was later resolved by Mao et al. (2024i), who introduced a broader family of surrogate losses that simultaneously achieve Bayes-consistency, realizable K-consistency, and K-consistency bounds. For the single-stage mulriple-expert (Hemmer et al., 2022; Keswani et al., 2021; Kerrigan et al., 2021; Straitouri et al., 2022; Benz & Rodriguez, 2022) case, Verma et al. (2023) were the first to extend the surrogate loss proposed in ( (Verma & Nalisnick, 2022) and (Mozannar& & Sontag, 2020) to accommodate multiple experts. Building on this, Mao et al. (2024a) further generalized the surrogate loss from (Mozannar& & Sontag, 2020), introducing a broader family of surrogate losses tailored to the multiple- expert case. Furthermore, Mao et al. (2024a) proved that their surrogate losses benefit from H-consistency bounds in the multiple-expert case, thereby ensuring Bayes-consistenge However, these loss functions are not realizable H-consistent even in the single-expert case, as they are extensions of the earlier loss functions. In the two-stage scenario, Mao et al. (2023a) introduced surrogate losses that are Bayes-consister and realizable 3(-consistent for constant costs. However, their realizable K-consistency does not extend to cost functions of interest, which are based on classification error. Other extensions include single-stage and two-stage multiple-expert deferral in regression (Mao et al., 2024h), single-stage learning to defer to a population (Tailor et al., 2024), and two-stage multi-expert deferral in multi-task learning (Montreuil et al., 2025d), adversarial robustness (Montreuil et al., 2025a), query optimization and allocation (Montreuil et al., 2024), and top-k prediction (Montreuil et al., 2025b;c).
Further research has explored post-hoc methods. Okati et al. (2021) proposed an alternative optimization approach for the predictor and rejector, while Narasimhan et al. (2022) offered corrections for underfitting surrogate losses (Liu et al., 2024). Charusaie & Samadi (2024) developed a unified post-processing framework for multi-objective L2D based on a generalized Neyman-Pearson Lemma (Neyman& & Pearson. 1933). Additionally, Cao et al. (2023) introduced an asymmetric softmax function for deriving valid probability estimates in L.2.. Wei et al. (2024) explored dependent Bayes optimality, which elucidates the dependencies involved in deferral decisions within the L2D framework. The L2D framework and its variants
16

---

Realizable Multiple-Experl Deferral
have been applied in various domains, including regression, multi-task learning, adversarial robustness, top-k prediction, query optimization and allocation, human-in-the-lope systems and reinforcement learning (De et al., 2020; 2021; Zhao et al., 2021; Mozannar et al., 2022; Straitouri et al., 2021; Joshi et al., 2023; Gao al., 2021; Hemmer et al., 2023; Chen et al., 2024;
Palomba et al., 2024).
B. Single-stage multiple-expert deferral: proofs.
B.1. Proof of Lemma 3.1
Lemma 3.1. The deferral loss can be expressed as follows: (h,,
x. y) Hall x Xx y.
Lder Σ (x, 11-10 ne [n(a)ey
1 - c2(2, 1) (b (no))mne
Proof. Observe that for any (z, X x y, we have In(z)=nt 1n(=)=y h(s)=n+j+ since h(x) n implies h(z)
Thus, using additionally An(x)<[n] [ In(a)an-j> the deferral loss can be rewritten as follows for all (z, v) e X x y:
Lder(h, (hss)(m)
Σ 9 (x, h())=++s
Fl
The = =l(a))y
T1e
In(s))nn)
Σ
9j (I, y) ((c)))))
j=1
j-1
=n())en
II
In(m))n+)
Σ
Cj (I. In(a)an (11()())n)))))
j=1
j=1
Σ (( + In(x)=y
Σ (x, (cle
3-1
1-1
j-1
Σ (c + Σ
1 - oj (, 4) (x, haaaen) In(x)y
Inx))nns
In(x)ents)
F=1
5-1
3=1
(add and subtract Σド= (n())an))(()))me)
Σ (x,
+
1 - Cy (z. y) (n) In(=)enes + In(=)= (1 11 nne)
1=1
h(z)) E [n]
nh
h(x) [n]]
(154 In(a)anns
and En In(a)anns
otherwise
mr
otherwise
Σ (x(,)) +1 ne In(x)=y
Σ
[1 (x, v) ( (oo)ontt
j=1
This completes the proof.
B.2. Proof of Theorem 3.2
Theorem 3.2. Assume ne and HC closed under scaling. Then, if V satisfies lim ((u) = 0 and lim (u) = 1 then the surrogate loss Ly is realizable K-consistent with respect to Laet-
Proof. Let h² be a best-in-class predictor such that ELAst (h*) O. Note that
(3() s lim EL(hn')
a+
= lim B[L(ah" x. v) h" (x) a-++00
lim B[[(ah" v. h (z) =n AJP(h" n k)
a0+000
17

---

Realizable Euleiple-Expert Deferral If (xx))) [n], then, must have h* (x) = for any (x.y) X y. In this case,
lim
[[L(ah", hx)x E [n]]
a-+000
(u,y) (x.y)
E
e (1, The
lim v
Eyeoy eato eahigeaaaien (2:00
1+0000
Rgg
(1)2)) eaat (wrm))))
Σ 1-1
1 - (2(
lim a+000
E Eyerr eati (x:00)
E[0] + [[
0.
If h" (x) =n k, then, we must have (2 y) = 0 for any (z. E X x y. In this case,
lim
E[L(ah" ,r,0) (x)) n k.
(ah"(x (x.1))
s E
Σ (r( 3) + 1- ne
lim y 100000
Eyeor eati (2.20)
eakt (u.w) + gath (a,n+)))
E
Σ
1 c,(2,,)]]
lim V
Every (z,00 (x.0))
5=1
E
Σ (x(,)) +1 ne
Σ [1- [1-c)(208)] j-k
J+k
0.
Therefore, we have E((H) 0.
B.3. Proof of H-consistencc bounds
B.3.1. SIMPLIFIED NOTATION AND PROOF OF LEMMA 5.1
Let p()))) P(Y y X x) be the conditional probability of Y y given X Let Vmax argmax P(y)z), e [n.]. We denote by Ph(x)
[(h(x))xx)
h(x) [n] We
Pyias =P(ymax /z)) and Pa+j
- c,(x,)))) Eyey (1
Pntt
h(x) = n
first characterize the conditional error and conditional regret of the deferral loss as follows.
Lemma 5.1. Assume that H is symmetric and complete. Then, for any h H and input e X, the conditional error and conditional regret of the deferral loss are given by:
CLa (h, -P((r):
ACT or (h) max Pymoxx
max Puts - Ph(z))- je[me]
Proof. By definition,
CLa (h,x)= Σ (oe
way
Σ Σ ((ylx)) | (x, Ince)=oos
yey
1=1 j=l
R2
(1 (1-p(h(=)]<))haoeel))
Σ p(n + 4
3-1
1 -PP(z))
18

---

Realizable Multiple-Experl Deferral
Therefore, the best-in-class conditional error and conditional regret can be expressed follows:
Ciar (H, = max Pymax max jo(no]
Phtsj. ACt sc (h, = max Pyemx'
max Pn+s Ph(x))
se[ne]
For convenience, in the following sections, we will omit the dependency on in the notation: hy h(x, v) for any y. and Py = p(ylz) for any E y. We let hmax argmaxyey fy and dj.y ((, for any e y. We also let y" anggaxje(n.] Patj and h" arggax je[m.] hats-
B.3.2. PROOF OF THEOREM 3.4
Theorem 3.4. Assume that H is symmetric and complete. Then, for all h H and any distribution, the following H-consistency bound holds:
ELas (h) Eee (H) Ma (H) $ (n (ELma (h) Em (3) Memoo (H)).
Proof. The conditional error of the surrogate loss can be expressed as follows:
LLmaa (h
Σ plukk))mmo (h,
ycy
eh(x)))
c(a.s) eb(ennt)) Eyegy ch(o,))
Σ
Σ (((ll))c
1 Σ wey eheers)
Σ -p(ul)((--c(0,,))
Dey
yey
(1 nee) Σ E(1122)
1
En Eyyer ch((x)r))
yell
nx Σ
c
cy clinss E Every ehio
ena Every eliv
Σ
Viss
1
Eyeeger
ehovr
(Pg (in)
(1- - nz) Σ Py.
Σ
1=1
y
yely
yey
By Lemma 5.1, we can write the conditional regret of the deferral loss as
AC (h, max Pymax
max Pu+j Ph(w)) je(m.)]
Next, we show that the surrogate conditional regret can be lower bounded by the target one:
AC x) = Clime (h) e (H) 2
(AC (A
(10)
We first prove that for any hypothesis and x. X,, ymux # Amaxx then the conditional error of h can be lower bounded by
19

---

Realizable Multiple-Experl Deferral
y Mmax
that of h, which satisfies that hxz,00 v)
Bymax
y mmax otherwise.
Indeed,
by
Mummax
Bymax ethinss
Ci CLaac (h) Clamc (hi)
=
UisMmax j-1
Ever ela
(Pymmx
Ujsthaax
Ever ene
Nh
Uj.bwax
Evey e'tv
(Dhrnax Ojjhranx
Exeyy ehv
Atmaa
Nemax eminss
(P (5.8mane
yj.ymax
Eyey e'vy
Eyegge env
vvmax
vmmax e
-jj.maxx
1
Eyege
(Phmax )j.hhmne
Eyegg elaor
@dmax
(1 Te Pelan
+ (1 ne Phomae
Σ Eyegye em e elmmax
Σ Eye Eyegee e
(1 The P
The Phoax
1
Egyege eh
Eyeey ena
Meanas M O.
Egrey ey Pymaxx Phomae
We then prove that for any hypothesis h and E X,, if 4 h², then the conditional error of l can be lower bounded by that of h, which satisfies that h(.zz) =
Knth*
= 12 y" y == h" Indeed, otherwise.
haty
hy
CL (l1) Cluae (h) Puty
Eveyy ehe )
+ Pnnn
Eyeey e/v
cMaus.
Pnay 1 Exegerv
Eyeg ehar
Evey ehv (Prey Pmn (c - enrree) 200 0.
Therefore, we only need lower bound the conditional regret of hypothesis h satisfying both Vmax hmax and h² Note that if (Pymex PPutt" (hymax -haty) ) O, then, Ce O. Next, will analyze by case.
1. Case I: If Pymax log
Pnty' O and hymax - -ntt" S O: we define new hypothesis h such that (z, y Vmax
(log(e chaoe 11) log( log(e"umax hemmaxx p)) 11
y n v², where hnvmus 2 24200 0. Then, we can lower bound the conditional regret of Lyme by otherwise.
20

---

Realizable Multiple-Expert Deferral
using AC 26 (1) CLmac (1) Cm (h2z) for any emumaxx 4 0:
AC AL xe
sup
(eL (1) Cimaac (Rxw)
elummax 2y22
BA
+ (Pymae 9.. ) ehuma + chinss
2 sup
Σ Wistmace 1
Evreyet elty
Exeey otly
NMmaax 2n20
Jay
elaore +
1 eluuro + + ehann
IisSmmxx
Every chior
(Pymas Distmox
Eveyy chvv
e.ummux
emuman + eliouu
Qy
Eyegge ePwy
(Pymax 4y* -ymax Eyeg e
1 eMnive +
Mnsot + Mumax
-Qy", Mmaax
Eyreg e/v
(Pumae 9y* stmase
Eyege
envv + eltnsse
1 chv + envanu
Σ (Pu Qy wr) 1
Σ
(py (r
E Eyeey elty
E Eyery c/v
yFuumax
(1- - ne)
Evey e (Ehness + E. Mremmx)
Pulms
1
Σ
(Pu - (0) (e Mvmmar)
Σ y e
sup
By sManx
e 2020
y-Vnox
(Pymax Pmngg))
(1 Mamor achieves the maximum)
Eyee cha
Tee 2
(Pymex Dmogr))
(by the assumption Anayy = Anno Myyaas 1
(AeL 2))
(by the assumption Pymax -Prty* 0 and 1yaau -naty" $ 0)
12 ne
2. Case II: If Pysmase Pnay" 0 and hymax hnty" 2 0: we define a new hypothesis h2 such that h (x.
log( log(e! chaerr 11) y Vmax log( (gg(ehmaxx + 11) 11
== n= where cnnutt 2 0. Then, we can lower bound the conditional regret of Line
otherwise.
21

---

Realizable Multiple-Experl Deferral
by using A Le (h) CLmac (1)) Cn (hia) for any en 2 1 0:
AC (1)
(Elmao (1) Cimmn (kw))
sup c'nis" 2p20
Avmax
e Ammox + Bnnss
2 sup "att"" 2p20
Σ
Pisimux 1
(Poraxx Ib.
Evey ellvr
Eyeeg elly
j4y
e 14
ennour - 1o elonrs
(Pymax Bissmox
+j.gmmxx
Σ Vee elt
Σ Eyegeh env
@mvamax
emuma + chnisr
qy* ymax
Eyeey ethy
+ (P - qy yymax)
Exreyehu
emmuue 1
emmove elumaxx
Quj Manax
Eyeer ento
(Primux Oup Mlmaa
Every ehlv
envy EMange
c + chvman +
E (Pu qu* w))
)
E
(Py - (r
Eyeyy eboo
Eveey exla
ye9mmax
yeVMaax
(1 - ne)
Pymax Eyege' t
(Ehnes* - --- (amax
E (py - qu .r) qo Ummax (dlwmaee + f elinss")
sup
Eyeeg envy
venus 3020 Lyggmar
Mamma
-Pnngy* Pymox) Eyeggehv
(μ = an achieves the maximum)
(Paty* Pymmaa)
(by the assumption Nyamax hh Maaty hnth*) (by the assumption Pymaa Pn and hyams Mo 2 0)
12 The
(AC (ACL 2))
n + ne
This proves the inequality (10). By taking the expectation on both sides of (10), we complete the proof.
C. Two-stage multiple-expert deferral: proofs.
C.1. Proof of Theorem 4.1
Theorem 4.1. Assume that R is closed under scaling and that tp satisfies lim,-.oo +(t) and @ 2 1,50- Then, the surrogate loss La is realizable R-consistent with respect to Lidef-
Proof. Let x best-in-class predictor such that El (r*) = Note that
2* L.
(R) S lim EL (ar*)
a000
lim E[Lo(ar" ,2, (x) ([)( =1)
+ ELLa "aaarr"x,,,) 24,0) (1( 2))(("()) =2)
22

---

Realizable Exxeeple-Experl Deferral If (1) then, must have ej (z, y) for any (2, Xx y. In this case,
lim E[Lo(ar ..,) (z)= =]
$ R
(x. lim ((((((2, 1) rx 2))) 0-4400
[[
0.
If r' (x) = then, must have cy y) for any (z, Xx x y. In this case,
lim E|Lx(ar" v. r' (x) 2]
< E
c (z,z) y)
lim (((((2z, r(z,,)))) a
E[0]
0.
Therefore, we have غig (R) O.
C.2. Proof of Theorem 4.2
Theorem 4.2. Assume that the following R-consistency bound holds in binary classification:
Eto (h) Eto (R) Mes (R) s (() Eg (i
Then, the following R-consistency bound holds in two-stage, two-expert deferral:
(La(r) ELo (R) + ML, (R)
ELidot (r) - ELiser (R) + Mistor (R) s (τ) + +22)1
C1 C2
where constant factors (ci C2) and (7) +22) can be removed when I is linear.
Proof. Let ()))= P(Y = =1
= x) be the conditional probability o given x. The conditional error of LL
can be expressed follows:
Cheyer (r,z) hoo
M
The conditional error of L4 can be expressed as follows:
CLa (r, = (ulnr///hhooccceeerrr------)(44d
Consider new distribution which satisfies that
π()) (1C)) +
23

---

Realizable Multiple-Experl Deferral
Then, under the assumption, have
7(x) (0)==1++++++
< I (ooo
-1 t2, we obtain
Using the fact that 1x, (ct
Clirde (r, inf CL cded (r, +2) CL. (r, inf CL. (r,
C +
where constant factors (g + (2) and (o) + ō2) can be removed when I is linear. By taking the expectation on both sides and applying Jensen's 's inequality, we conclude the proof.
C.3. Proof of Theorem 4.3
Theorem 4.3. Assume that R is closed under scaling and that (a))eyy e [ne]] Further, assume that for any (z,y),, there is at most one expert j* с [me] for which oz (x.yy 0 and that W satisfies lim V(u) = 0. Then, the surrogate loss Ly is realizable R-consistent with respect to Lidef-
for
Proof. Let rr be best-in-class predictor such that ELa (r*) = Since R is closed under scaling, for any a, ar in R, and we have EL,, (R) ELv (ar*) This implies the following inequality:
EL. (R) lim EL (ar")
Σ lim ((Lv(ar",,,)) ,2,8) (1) =).
a+++00
If (x) = i, then, we must have as (x,,) and ea (x,,y)) 1, for all # and all (æ, v) X x y. Thus, we can write
lim [[L x.3) (x) [ i]]
(ar") (x.s)
E
Cy (I, v) nue +
lim y a
=i
(B)
Eyee(me) (x,d))
car"(1n)))
E
lim V
(G(x. v) and cx(x,)) Vk
Eyjemo)) cart (ar")
[[]]
(r" (x) = = (r,,t)>> (x, Vj + lim (()) = 0)
0.
Therefore, we have Ei, (R) = 0.
C.4. Proof of Ji-consistency bounds
C.4.1. SIMPLIFIED NOTATION AND LEMMA C.1
Let p(y] P(Y y X .)) be the conditional probability Y given X We first characterize the best-in class conditional error and the conditional regret of the two-stage deferral loss function Lidef, which will be used in the analysis of "K-coosistency bounds.
Lemma C.I. Assume that R is symmetric and complete. Then, for any E K and x e X, the best-in class conditional error and the conditional regret of the two-stage deferral loss function are given by:
ei (R,z) min Σ (p(,))))((E,)), ACL,)..e(T, je[m..gge yey
E((gle)) =
min Ep(g)=)((HE.)) je[me]
yc
24

---

Realizable Multiple-Experl Deferral
Proof. By definition, for any r R and X. the conditional error of the two-stage deferral loss function can be written
Cliar (r, Σ (x.
ye
Since R is symmetric and complete, we have
CL (R, inf Ep( retk yey
min (p()))),(e,.)) je[na] yey
Furthermore, the conditional regret be expressed
L & (T, = Cleast (r,x) ei (R, = Σ (z)1))
min (z.))) je[nel yey
yey
which completes the proof.
C.4.2. PROOF OF THEOREM 4.4
For convenience, we let C = (ne - 1) max ja[ee[nn]] Cj. ne 2, (3()))) = Es'ss (x, - ne + 2 [0, ((x,)) c((r)))
Eyey ((ey(())))) [0, C) and {(x,j) Eye(ne) E erto:py. We also let juin (x) argming((n.) Evey ((,)a)c,(x,
Theorem 4.4. Assume that R is symmetric and complete and that the inequality Σド+r ej (2,y) ne holds for all jE [me] and (2, y) Xx x y. Then, the following R-consistency bound holds:
ELeses (r) ELidor (R) Miaae (3)) 1 (EL,, (1) (R) + Miee (3))
where C. (ne 1) maxje(n.] C3- + 2, l(t) =((C) Vt when q 0, l(t)) 2(n. ( VZ when e (0, 1). and T(t) = n & when q 1.
Proof. Case I: O. In this case, for the surrogate loss Lv,, the conditional error can be written as follows:
(((,))
CLU, (r,z) =- E(yle) Σ 2, v) log jo[ne]
Σ log(8(z,)))7(z..))
Eye(n.]eraass)) cx(a.g)) jo[nc]
yEM
The conditional regret can be written as
ACLo (r,
Σ lzg()
inf
Σ log(8(z;)))(z.5))
jt[ne]
reR
je[ne]
Σ log(8(z,)))gzz..) je[nc]
inf wel- (mnn (=)))
Σ (0 Je[me]
where for any x E X and j [ne].
8(x,)),
j (m)
(x,
8(x,Jmin (x)) P
j r(x)
8(z,r(x)) -p j Jmin (m)n(x).
Note that with such a choice of 8,, leads to the following equality holds:
Σ (og(
Σ
(m))
jeir())..mmm++))
25

---

Realizable Multiple-Experl Deferral
Therefore, the conditional regret of the surrogate loss can be lower bounded as follows:
A AL x(,
2 wel-8(a.mmmn) (e))
sup
g(c.:hmm(())---bbg((44n..... log(8(x; [1)]
7(
+
By leveraging the concavity of the function, we differentiate it with respect to μ and set the differential equal to zero to find the maximizing value
n² [( ((),,
q(21 Jmin ( (m)))((())(
(12 (2) (z)) ( r2))
Plugging in the expression of n², we obtain
AC AC (1,
( Jmin (x)) log r(:)) 8 Juin (1))))nnnnn))))))))))))))))))) ( Juin (1))
8(x, (z) (Z) (2) + ((,,(()))) (())))
(8(2, r (I) 8 Jmin (z)) (z)))
r(xx; log
8(x, r( x (7 (min x (((,
27( r, Jmin (z)
(((x)((z))
Jmin (x)) log
( (x)) log
7( (min)mi(())) 7( ((x,
7( (x)) q(,, r(x)
(minimum achieved when ((x,r(x)) 8(x, Jmin (min()))
Juin (z)))²
2a lalog a-b
blog
2h (a-b)²
Va [0, 1] (Mohri et al., 2018, Proposition E.7))
2(7(21, ((x) g( (2 Jmin (x)))
o+5
[a=b)
(()xr(()) 7( Jmin (z)
(0 s q(<,,(()))))))))()))))))))(()(() g Jmin (x)) s 20)
4C
Therefore, by Lemma C.I, the conditional regret of the two-stage deferral loss function can be upper bounded as follows:
A AC x (r, ((. (()))
2(()) xx,
By the concavity, taking expectations on both sides of the preceding equation, we obtain
s 22( (ELO, (r) ELv, (R) Mi, (R))
ELYSer (r) Eiedes (R) Minder (R)
Case II: e (0, 1). In this case, for the surrogate loss Lu,, the conditional error can be written as follows:
Eye(nn.) Ey ))= Σ (1 (I.)
gCie, (r,z) = Σ((u))
Σ 35(2,1)
yey
je[m.]
je[na]
The conditional regret can be written as
xACLo,xx115 ((,xx)
Σ (1 (2-)(())))))..) inf Σ (1 (1-8 (1-s"(Z,)) jd[m.]
[j[[m)]
2 Σ (1 (z,)))( je[n.]
inf ((BB(s.iiat(())
(1-8((
26

---

Realizable Multiple-Expert Deferral
where for any X andd] j [ne].
8(x,)),
j {Jmin (z). rx))
8 (x.
Smz, (x))
((x)
((xx)((x) -p
j Jmin (z)).
Note that with such a choice of Sn leads the following equality holds:
Σ (1 (1- (1,))(
E
(1-8% (1.8((a))))(
(((r()))Jmin<>))
jelr(s))Juin<z))
Therefore, the conditional regret of the surrogate loss can be lower bounded as follows:
1 (r,
2
sup ne( (e(-K(assma(t))).Mcc((()
(((2) -n]
+() (* + ml)
By leveraging the concavity of the function, we differentiate it with respect to μ and set the differential equal to zero find the maximizing value
7( Jmin (x)) r F Jmi (x)) Imin (x)) 1o r(x,r(x)))
Plugging in the expression of n², we obtain
qdeLo, 2 (r,
(((x, ((x)) + 8(1 Juin (r))) (T(z, (1) +(x,)))))))))))))))))))))
( Jmin (8)) (I. Juin (z)) ( 7( (()))
1
2 Jmin (x)) -- (1 (())
Imn (2)) ((x)
n.
(minimum is achieved when 8(x; r(x)) 81 (2)) n
1
((q(x,(<))) g1, )m)n
1-g
tb
2 2 Va,be be [0. saabbbbs)
4C
Therefore, by Lemma C.I, the conditional regret of the two-stage deferral loss function can be upper bounded as follows:
A Celaaee.er 7(,, Jmin r(x)) s 2())) ( (AL
By the concavity, taking expectations on both sides of the preceding equation, we obtain
ELaue (r) Ex Etedet (R) Mi (R) s 2) (ELO, (r) - ELo, (R) ML,, (2)
Proof. Case III: g 1. In this case, for the surrogate loss Lv., the conditional error can be written follows:
CLO, (1,x)= E((l))) Σ (0,,10111
Eve[ne) cx(o.))) )
et(,,))
Σ (1 (1=8
yey
je[me]
jr[ne]
27

---

Realizable Multiple-Expert Deferral
The conditional regret can be written as
AC ((,,
Σ (1-8(1,
inf reR
Σ (1- (1-S(z,,)))z,,)
je[ne]
je((me]
(1- (1-8, (1-8,((,,)))( 8yl0,.)000
Σ (1 - 8(1,,)))((z;) jc
inf ve(8(=simn()))
je[me]
where for any X and] j [ne].
8(x,j),
j (m) r()))
s (x,
8(z, (x)) 1
j r(x)
8(z,r(x)) p jmin (z).
Note that with such a choice of Sn leads the following equality holds:
Σ
(1 (I-((x,)))(x..))) Jmin))) Jmin(
Σ
(1- (1-8,(c,,))TT.,)
Jmin
Therefore, the conditional regret of the surrogate loss can lower bounded as follows:
ACLo ACLo, (r)
q (2)) (z)))+(()))))))) +8(x,r(x)) [
sup (=(-)te.jmin(()).88c.cc..
(()(,,( Jmi, (x)) ml)
By leveraging the concavity of the function, we differentiate it with respect to μ and set the differential equal to zero find the maximizing value
μ¹ --(x,, (x)).
Plugging in the expression of 4², we obtain
ACL,, R (r,2)
7 v Jmin (x (())
1 (q(2, r (x) (I,, (miu))))))))
(minimum is achieved when 8(x, r(x)(
ne
Therefore, by Lemma C.I, the conditional regret of the two-stage deferral loss function be upper bounded as follows:
A & (r, jmin 7(2, (x)) s ne (
By the concavity, taking expectations on both sides the preceding equation, we obtain
Eae (r) Eirder (R) Mi (R) no (ELo (r) ELo, (R) Mi (R)
D. Enhanced bounds under low-noise assumptions: proofs
D.I. Single-stage: proofs
D.1.1. PROOF OF LEMMA 5.2
Lemma 5.2. The single-stage deferral Tsybakov noise assumption implies that there exists a constant that the following inequalities hold for any e K:
Bi-a
0 such
a
E[DDne)) & (
o[ELser (h) ELLor (h²))aa
28

---

Realizable Multiple-Experl Deferral
Proof. The second inequality follows directly from the definition of ((x) and Lemma 5.1. The proof of the first inequality follows the same steps the first part of the proof of Lemma 18 in (Mao al., 2024e).
1.1.2. PROOF OF THEOREM 5.3
We will leverage the following result of Mao al. (2024e), which serves as general tool for obtaining enhanced bounds under low-noise assumptions.
Theorem D.I. Assume that there exist two positive functions o: - IR_ and B:Hx - RR with supze? (1, < too and xx (h,, [ x)] +o0 for all h H such that the following holds for all h E H and x X. 4C2 (h. Ex [3(h,a)]
3(h,a))
(a(h, x) (h, for some s 2 1 with conjugate number t z 1, that 1 + = 1. Then, for (())
a (h,,) 3x [((haa)))
Ex
the following inequality holds for any E H.
EL, (h) (3) + (3) s <1h) (3(( + Mr, (H0)²
Theorem 5.3. Consider the setting of single-stage multiple-expert deferral. Assume that the following holds for all e H and é X: AC H (h.x) S (h,,L,((h, with T(z) x², for some 2 1 with conjugate number t 1, that
1. Then, for any h E K,
ELaer (l)) - Eian (H) Misec (H) & E (()c))) ( MLH))
Proof. Fix e > 0 and define ((h, = In(z)ah+(()) +e. By Lemma 5.1,
A ACLan 36 (h,x)) max Phemas
max Puaj) Ph(x) (h) Ph(x): jo[nc]
we have
DC (x, S (h, (L) B(3(h, x(,,2)
thus the following inequality holds
AC AC or (h, x) Ex Ex[ [3(,
s EE
3(h,z) x)
By Theorem D.I, with a(h, 2) Ex[3(h, )" we have
ELL (h) Ei.. (Ht) + Ma (30) s
Since the inequality holds for any 0, it implies:
X (x -(((())))((0))M)())) [,
ELa (h) Ei (3() + Ma.. (3f) s
= E x (n - + +t())++
( ((x)x)))<()))=== = (x))
This completes the proof.
D.1.3. PROOF OF THEOREM 5.4
Theorem 5.4. Consider the setting of single-stage multiple-expert deferral where the Tsybakov noise assumption holds, and no approximation error occurs, that is, EL (H) = Ein (Hau). Assume that the following holds for all e H and x e X: A A xx (h, s T(AEL:X (h, with [(x) x ", for some Then, for any E K.
ELa (h) E (H) & C [EL(h) - - MM)) (3
29

---

Realizable Multiple-Expert Deferral
Proof. Fix > and define 2(,,2) In(())ah*(a) e. By Lemma 5.1,
AC H6 (k, max Poymar
max Putj] Ph(x) (x) Ph(a): je(men]
we have
Ae (k, Ex s se bl
x(h
thus the following inequality holds
AC AC 34 (h, x) Tx [x [3),
((,,2))
By Theorem D.I, with ahh, 2)) Ex[33(h, )) we have
LLan (l) ELL (H)
(( (
Since the inequality holds for any 0, it implies:
(EL(h) - (EL))) ELat (h) Eisce (H) E (x))
+ (H))
=n -E[(H) Mr (3)))
(Ixx))))(x)))= (m())sh((a))
s (ELac (h) EL (36) (E)
((L))((E(())) EI(()) + M (30)*
(Tsybakov noise assumption)
The result follows after dividing both sides by [ELier Ein (H)]
D.2. Two-stage: proof's
D.2.1. LEMMA D.2 AND PROOF
B1- > 0 such that the
Lemma D.2. The two-stage Tsybakov noise assumption implies that there exists a constant c= a following inequalities hold for any h E R:
(((()))) sc ((X(() s cfEe (r) Eliaa (r*))
Proof. The second inequality follows directly from the definition of (xx and Lemma 5.1. The proof of the first inequality follows the same steps the first part of the proof of Lemma 18 in (Mao al., 2024e).
D.2.2. ENHANNCED BOUNDS IN TWO-STAGE SCENARIO (THEOREM D.3 AND THEOREM D.4)
The following result gives an R-consistency bound based on the quantity (x)
Theorem D.3. Consider the setting of two-stage multiple-expe expert deferral. Assume that the following holds for all h e R and Je X: AL ()) & (r;))). with I(x) = for some s 1 with conjugate number t 2 1, that is 1 = 1. Then, for any r R,
ELese (r) - Eie (R) + ML (R) s BBsBBLLCC
The proof of Theorem D.3 is included in Appendix D.2.3. As noted for a similar result in the single-stage scenario, Theorem D.3 offers more favorable theoretical guarantee than standard K-ccosiitency bounds, assuming AC (r, (r,z).
Next, we assume that the Tsybakov noise assumption holds and also that there no approximation error, that Misa (H)
30

---

Realizable Multiple-Experl Deferral
Theorem D.4. Consider the setting of two-stage multiple-exper deferral where the Tsybakov noise assumption holds, and approximation error occurs, i.e., ELado (R) ELato (Ran)- Assume that the following holds for all R and X: AC ( T(AeL, x)), with [x)) I for some 1. Then, for any R.
ELeeer (r) ELntor (R)
(E((r) (EL())-(((8)) + ML (R) v-
The proof can be found in Appendix D.1.3. As in the single-stage scenario, in the case of a - 1, where Tsybakov noise corresponds to Massart's noise assumption, this provides an H-coonsisenccy bound with a linear functional form, improving upon the standard H-consistency bounds, which have the functional form I'(x) x², they exist. This demonstrates that for any smooth surrogate loss with an HCconsisty bound, under Massart's 's noise assumption, we can obtain c-consiity bounds as favorable those of L Lv, with q 1, which always admits linear dependency, shown in Theorem 4.4.
For example, Theorem 4.4 shows that square-root He-oonisstnney bounds hold (s 2)) for Lv, with g [0,1). Thus, Theorem D.4 provides refined H--conistencyy bounds for these surrogate losses: linear dependence when Massart's noise assumption holds (a 1) and an intermediate rate between linear and square-root for other values of within the range 10.
Furthermore, the realizability assumption can he viewed as a special case Massart's noise assumption. Thus, Theorem D.4 provides intermediate guarantees between realizable H-cconsisenccy and HC-consistency bounds for two-stage deferral surrogate losses, such as La (5) for the two-expert case and Lv in (7) for the multiple-expert case.
D.2.3. PROOF OF THEOREM D.3
Theorem D.3. Consider the setting of two-stage multiple-esye deferral. Assume that the following holds for all h e R and I X: AC R (T, (T, with I'xx)= for for some 1 with conjugate number t 2 1, that is 1 + 1 = 1. Then, for any r R,
ELeter (r)) - E Elreet (R) Miste (R) El E (L (x))
Proof. Fix e 0 and define ((r,x) ((())ur((s) + By Lemma C.I,
((( A (1,
Σ
- Ep(ule)er(ss(tt.)
yey
yEy
we have
< A x (1.=))
B(r,z)
thus the following inequality holds
ACL R
(r, (T,
Ex((r,))
3(r,z)
By Theorem D.I. with xrr, =)= Ex[3(r,x)] we have
ELeao (r) Eirane (R) + Mi s (1))=)))
Since the inequality holds for any 0, implies:
ELeae (r) Ei (R) + Mi (R) s (1(x)))r -())))))))))))))-)(0))))))-----)
-L0 (xxx)rrx))'== (xx))
This completes the proof.
31

---

Realizable Multiple-Expert Deferral
D.2.4. PROOF OF THEOREM D.4
Theorem D.4. Consider the setting of two-stage multiple-expent deferral where the Tsybakov noise assumption holds, and approximation error occurs, i.e., ELeat (R) ELeded (Ran). Assume that the following holds for all r R and X: ( T(ACL,)(T) x)), with [(x) x for some 1. Then, for any r R.
ELeaes (r) ELetar (R) S c (orra----ELL E[( ML (R)) --
Proof.
Fix E > 0 and define ((r,x) ((())an(() + By Lemma 5.1,
(((()))(())((11))) Ex(sle)ercssttt.) A AC xT,
yeyl
yey
we have
x Bx [x(x)r)))] x(r,z)
& (1, B(
thus the following inequality holds
AC L x Ex(
3(r,z)
By Theorem D.I, with x) Ex [r) we have
E (r) - Elaee (R) s x - ML
Since the inequality holds for any 0, it implies:
(1x)) ( (EL()))))))) ((R))
ELeaet (r) - &iwee (R) s x
(ex (X) MX))
(Lu(),))oo'' ()(r)))=o)
sot -
Ela (R)] (EL(r) E[(R) My (2))*
(Tsybakov noise assumption)
The result follows after dividing both sides by &Eee (r) - E Ei (R) ?
32


Reviews:
[{"review_id": "7VG9zZw3v6", "reviewer": "Reviewer_wQs7", "summary": "In the paper  _Mastering Multiple-Expert Routing: Realizable-Consistency and Strong Guarantees for Learning to Defer_, authors propose surrogate losses for learning to defer that satisfy the following oints: realizable H-consistency, H-consistency bounds, and Bayes consistency\nfor both single-stage and two-stage learning scenarios. The authors mathematically prove that their claims and compare their proposed solution to some baselines for a few common datasets.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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**1. Claims regarding Verma et al. (2023):** Thank you for pointing this out. We agree with the reviewer that Verma et al. (2023) was the first to extend the surrogate losses proposed in (Verma & Nalisnick, 2022) and (Mozannar & Sontag, 2020) to the multiple-expert setting in L2D. We will definitely revise the claims accordingly throughout the paper.\n\n**2. Experiments:** Thank you for the suggestions. As recommended by Reviewer m1gt, we will aim to include experiments involving real-world experts, such as those considered in (Mozannar et al., 2023) and (Palomba et al., 2024), in the final version.\n\nOur paper primarily focuses on theoretically principled surrogate losses for learning to defer with multiple experts, grounded in realizable $H$-consistency and $H$-consistency bounds, within the learning theory framework. While we have empirically shown that minimizing our proposed loss functions outperforms the baselines in realizable settings and matches the best-known results in synthetic non-realizable settings—as predicted by our theoretical analysis—we recognize the importance of further empirical exploration. Accordingly, we plan to dedicate future work to conducting a more extensive empirical analysis in real-world settings, particularly in important scenarios where expert domains overlap (as suggested by Reviewer wQs7) and the data is heterogeneous (as suggested by Reviewer 798e).\n\nWe will also include a more detailed discussion of the limitations of our empirical analysis and outline potential directions for future work in the final version. Nevertheless, we believe our theoretical contributions are significant and well-suited for acceptance in the theory track of the ICML conference.\n\n**3. Relation To Broader Scientific Literature:** Thank you for the suggestion. As recommended by the reviewer, we will incorporate and discuss literature on the application of deferral-based mechanisms in real-world machine-collaboration scenarios in the final version.\n\n**4. Introduction:** Thank you for the suggestion, we will seek to revise the introduction accordingly.\n\n**5. Figure 1:** The behavior for lower values of $q$ is similar to that observed for $q = 0.7$ and $q = 1$. Note that for any $q > 0$, Theorem 3.2 guarantees realizable $H$-consistency. We chose $q = 0.7$ and $q = 1$ because they correspond to standard choices in prior work—$q = 0.7$ is a commonly suggested value within the generalized cross-entropy family (e.g., Zhang & Sabuncu, 2018; Mao et al., 2024b), and $q = 1$ corresponds to the mean absolute error loss, as used in (Ghosh et al., 2017; Mao et al., 2024b).\n\nIn this realizable distribution, we observe that our proposed surrogate losses achieve close to 100% system accuracy, while all other baselines fail to find a near-zero-error solution. This demonstrates that our surrogates are realizable $H$-consistent, whereas the compared baselines are not.\n\n**6. Table 1:** That's a good observation. We are not claiming that our proposed surrogate losses outperform baselines such as Verma et al. (2023) on non-realizable distributions. Rather, our results show that our surrogate losses match the performance of these state-of-the-art baselines in non-realizable settings, as both are supported by consistency bounds.\n\nThe strength of our approach lies in the realizable setting, where our surrogate losses are guaranteed to be realizable $H$-consistent, unlike the baselines—as illustrated in Figure 1. Due to the specific realizable form of our surrogate losses, our model also defers significantly more and shows a greater tendency to select expert 2 compared to the baselines of Verma et al. (2023) and Mao et al. (2024b). This highlights a key effect of our proposed surrogate: it induces deferral behavior that is qualitatively different from prior approaches, particularly on the SVHN and Tiny ImageNet datasets.", "claims_and_evidence": "In Lines 70-74, first column, the authors claim that  in  ‘*multiple-expert case, Verma et al.(2023) extended the surrogate loss proposed in (Verma & Nalisnick, 2022), and Mao et al. (2024b) extended the surrogate loss introduced in (Mozannar & Sontag, 2020) to the multiple-expert setting’.* Verma et al.(2023) also extended (Mozannar & Sontag, 2020) to the multiple expert setup, proving Bayes consistency. This claim from the authors throughout this paragraph is quite strong, and the authors are failing to acknowledge the contributions from Verma et al.(2023), the first work to extend *(Verma* & Nalisnick, 2022) and (*Mozannar & Sontag, 2020*) surrogate losses in L2D to multiple experts (single stage). \n\nThis claim is also repeated in Appendix A, lines 750 - 755.", "methods_and_evaluation_criteria": "# \n\n1. The new proposed surrogate losses for the multiple-expert setup are tested only with a few number of experts (up to three experts). \n2. So far in the experiments, the authors only addressed the case where the knowledge of the experts is complementary. That is, each expert has a specific expertise w.r.t to some classes,e.g. in the single-stage multiple expert deferral one expert is oracle on the first 30% classes, and wrong otherwise. Second expert is the complement of the first, predicting always correct for the next 30% of the classes, and wrong otherwise. As studied in Verma et al., 2023, the application of deferral-based mechanisms as studied here becomes more challenging when the experts’ domains overlap. I think this case is not yet addresses in this paper. How would the proposed solution work under experts’ domain overlap?\n\n---\n\nVerma, R., Barrejón, D. and Nalisnick, E., 2023, April. Learning to defer to multiple experts: Consistent surrogate losses, confidence calibration, and conformal ensembles. In *International Conference on Artificial Intelligence and Statistics* (pp. 11415-11434). PMLR.", "theoretical_claims": "All claims seem to be mathematically grounded, although I didn't dive too deep into the proofs and derivations in the Appendix.", "experimental_designs_or_analyses": "The experimental analysis seems very concise. While the authors compare to a few baselines using three different datasets, I think the authors limit the experimentation to a very ideal scenario where experts’ domain are independent. \n\nWhile this assumption could make sense when using pretrained ML models as predictors (for example), for a real use case with actual human experts, it’s rarely the case that experts predict completely independent. That is, even if a doctor is an expert in a set of classes in CIFAR-10 (e.g. bird, cat), that expert most likely would also predict with a high probability for other classes (e.g. dog, deer, frog, etc., because these are also animals). This results in a more difficult scenario which has not been explored in this work.", "relation_to_broader_scientific_literature": "The work is mainly related to learning to defer literature and deferral-based methods. The paper does not really mention or emphasize the importance of such deferral-based mechanisms in real world machine-collaboration scenarios. It excels in its mathematical contributions.", "essential_references_not_discussed": "All main references for learning to defer are mentioned.", "other_strengths_and_weaknesses": "It’s clear that the authors of the paper are aware of the recent papers in the learning to defer literature, and are worried about proposing actual consistent surrogate losses. Because of this, the proposed solutions are theoretically proved and guaranteed. \n\nRegarding the weaknesses, I think the expert domain probabilities definition for the synthetical experts is quite ideal, where the expert domain is independent among experts. This is not commented in the paper, and hence not addressed, when this is an actual real scenario that would happen in real life.", "other_comments_or_suggestions": "I think introduction section is quite long - specially the enumeration of the different sections and its content. This could be shortened. But just a suggestion. Maybe leave more space for real-life use case and motivating examples to allow non-experts on the field to understand the learning to defer paradigm. ƒ", "questions_for_authors": "1. In Figure 1, the authors show the outperformance of the proposed solution choosing $q=0.7$ and $q=1$. How would it behave for lower values? Could you include such results? Even if results are worse, it would show the limitations of the work. \n    1. How does the contribution actually defer from previous works (e.g. Verma et al., 2023, Mao et al., 2024b) in terms of performance, i.e. system accuracy? \n2. From Table 1, it seems that for single-stage baseline, the proposed solution is not so far from the compared baselines. It’s also quite surprising that for Verma et al., 2023, the deferral ratio for the two experts for SVHN, for the second expert is rather low. Could you comment why it’s that the case?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "kZAQlfMz4n", "reviewer": "Reviewer_798e", "summary": "This work introduces a family of surrogate losses functions for the learning to defer. The authors discussed methods for achieving H-consistent loss for single-stage deferral, and H-consistency and Bayes consistency for two-/multi-expert scenarios. The authors propose to surrogate the undifferentiable indicator functions in classic learning to defer losses with a family of comp-sum losses (a general case of the loss proposed by Sontag et al. [1]). The authors then discuss the the realizable H-consistency and H-consistency bounds for special cases of comp-sum losses for single-stage multi-expert deferral and two-stage multiple-expert deferrals. The authors then discuss the assumptions with which H-consistency bounds can be achieved. The empirical performance of the proposed family of surrogate loss are evaluated four public datasets.The proposed method yields improved system accuracy compared to existing works.\n\n[1] Consistent Estimators for Learning to Defer to an Expert\n\n## update after rebuttal\n\nI would like to thank the authors for the clarifications. While I am still not fully convinced on the realism of problem setting, I would like to increase the score in light of the contributions over existing learning to defer works.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful comments. We will take your suggestions into account when preparing the final version. Below please find responses to specific questions.\n\n**1. Experimental Designs Or Analyses:** Thank you for the suggestions. As recommended by Reviewer m1gt, we will aim to include experiments involving real-world experts, such as those considered in (Mozannar et al., 2023) and (Palomba et al., 2024), in the final version.\n\nOur paper primarily focuses on theoretically principled surrogate losses for learning to defer with multiple experts, grounded in realizable $H$-consistency and $H$-consistency bounds, within the learning theory framework. While we have empirically shown that minimizing our proposed loss functions outperforms the baselines in realizable settings and matches the best-known results in synthetic non-realizable settings—as predicted by our theoretical analysis—we recognize the importance of further empirical exploration. Accordingly, we plan to dedicate future work to conducting a more extensive empirical analysis in real-world settings, particularly in important scenarios where expert domains overlap (as suggested by Reviewer wQs7) and the data is heterogeneous (as suggested by Reviewer 798e).\n\nWe will also include a more detailed discussion of the limitations of our empirical analysis and outline potential directions for future work in the final version. Nevertheless, we believe our theoretical contributions are significant and well-suited for acceptance in the theory track of the ICML conference.\n\n**2. Relation To Broader Scientific Literature:** As the reviewer suggests, we are happy to include an additional discussion of methods based on uncertainty estimation. Previous work has shown that some of these methods can be suboptimal compared to those based on deferral or abstention, as studied in our paper. The reviewer references “uncertainty estimation” and “anomaly detection” methods multiple times; if there are specific publications they recommend, we would gladly discuss them in the final version.\n\n**3. Problem Setting:** We would like to point out that the same problem setting has been considered in several notable previous works on learning to defer (Mozannar & Sontag, 2020; Verma & Nalisnick, 2022; Charusaie et al., 2022; Mozannar et al., 2023; Verma et al., 2023; Mao et al., 2024b, among others). Within this setting, our paper introduces novel surrogate loss functions and efficient algorithms with strong theoretical learning guarantees. We address open questions regarding realizable $H$-consistency, $H$-consistency bounds, and Bayes consistency for both the single-stage setting (jointly learning the predictor and deferral function) and the two-stage setting (learning only the deferral function with a fixed expert).\n\nWe acknowledge that more realistic settings—such as those where experts may not be available during training, as mentioned by the reviewer—are also important. Extending our methods to these scenarios is a promising direction for future work. For example, it would be interesting to adapt our framework to handle previously unseen experts at test time, as studied by Tailor et al. (2024, AISTATS), and to incorporate post-processing frameworks for learning to defer under constraints such as OOD detection and long-tail classification, as explored by Charusaie et al. (2024, NeurIPS). We will further elaborate on this potential direction in the paper.\n\n[1] Tailor et al. (2024). Learning to Defer to a Population: A Meta-Learning Approach. AISTATS 2024.\n\n[2] Charusaie et al. (2024). A Unifying Post-Processing Framework for Multi-Objective Learn-to-Defer Problems. NeurIPS 2024.\n\n**4. Application to Large Language Models:** Our deferral solution can indeed provide a useful solution in the context of LLMs. Given the significant resources required to retrain LLMs, a two-stage method is a practical and scalable solution. This does not require modifying LLMs or the loss function used to train them.\n\nOur proposed two-stage surrogate loss framework is particularly well-suited for use with pre-trained LLMs. In the presence of multiple LLMs (or experts), using our method, uncertain predictions can be deferred to more specialized or domain-specific pre-trained models, thereby both improving the reliability and accuracy of the overall system and improving efficiency. We will further elaborate on this in the final version.\n\nWe have in fact carried out preliminary experiments demonstrating the effectiveness of our deferral method in enhancing LLM performance. However, these results are currently not reported publicly due to IP restrictions.", "claims_and_evidence": "The authors claim improved results compared with some existing baselines, which can be partly verified in the experiments in terms of SA.\nThe authors claim to have achieved H-consistency for single-stage deferral and realizable H-consistency, H-consistency bounds, and Bayes-consistency for the two-/multiple-expert scenario. This is presented with the derivations in the manuscript and supplementary results.", "methods_and_evaluation_criteria": "The methodology is straightforward (essentially an extension to [1]) and the use of SA for assessing the deferral performance seems to be reasonable.", "theoretical_claims": "I have not identified significant issues with theoretical claims.", "experimental_designs_or_analyses": "Although improved SA's are achieved, I have concerns on the realism of experiments: The employed datasets are mostly toy datasets which may not represent the complexity of real world heterogeneous data (e.g., more complicated tasks, coupling with class imbalance and OOD scenarios). Therefore, the real-world value of the proposed work is unclear to me when compared with previous learning to defer methods.\nIn terms of realism another issue is that getting sufficient samples on characterizing the correctness of experts at the system building stage a may be difficult -- it is often hindered by data / expert availability.", "relation_to_broader_scientific_literature": "This work belongs to the family of learning to defer problems. However, in practice, methods for allowing a model deferring decisions to external experts are many, e.g., those based on uncertainty estimation or anomaly detection. Many of them have the advantage that they do not to need to take experts (and their prediction examples) into consideration when a predictor is built, which bestow them significantly more practical value compared to the learning to defer methods.", "essential_references_not_discussed": "In practice, methods for allowing a model deferring decisions to external experts are many, e.g., those based on uncertainty estimation or anomaly detection. The authors are encouraged to briefly talk about these related problems.", "other_strengths_and_weaknesses": "Strengths: \n- The manuscript is built on substantial theoretical derivation.\n- The methodology is simple.\n- Improved SA has been achieved on four datasets.\n\nWeaknesses:\n- Realism in problem setting: In practice it is often very unlikely for a system to be able to incorporate deferral mechanism to a set of fixed experts (not to mention that sample predictions of experts or experts themselves are often unavailable at the time a predictor is built). Often times, human experts are even not always stationary. In this sense methods based on uncertainty estimation / anomaly detection are way more practical (especially for post-hoc ones).\n\n- Realism in datasets: The experimented datasets seem to be over-simplistic compared to real-world heterogeneous data, which are way more difficult to learn and are often inevitably noisy, class-imbalanced, and may contain OOD samples (which can easily overshadow the advantage brought by having H-consistent training losses).\n\n- Despite the authors hint a few times the significance of learning to defer for large language models, throughout the paper, there is little discussions on how the proposed loss would be integrated to LLMs nor are there experiments supporting it.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "While I appreciate the efforts on pushing forward in approaching H-consistency of losses, my major question is on the realism of the problem setting and over-simplified experiment substantiations. These issues may incur doubts on the real-world value of the proposed work.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "N/A"}}, {"review_id": "P3Ujv9czD2", "reviewer": "Reviewer_A5VC", "summary": "This paper studies 1. single-stage multiple-expert deferral, which is the deferral problem where the learner has the option to predict or defer the prediction to one of pre-defined experts, and 2. two-stage multiple-expert deferral, which assumes a label predictor have been learned in first stage and the learner select one from a set of pre-defined experts. The authors proposed realizable H-consistent surrogate loss for single stage and realizable H-consistent surrogate loss, H-consistency bounds surrogate loss for two stages. The properties of surrogate loss are proposed in a line of previous work.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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**1. Questions: Are there any other interesting properties or improvements the authors want to achieve for their loss family besides those already mentioned in the paper? It would be nice if the authors could discuss a few sentences about future directions.**\n\n**Response:** As suggested by Reviewer 798e, extending our methods to more realistic settings—such as those where experts may not be available during training—is a promising direction for future work. For example, it would be interesting to adapt our framework to handle previously unseen experts at test time, as studied by Tailor et al. (2024, AISTATS), and to incorporate post-processing frameworks for learning to defer under constraints such as OOD detection and long-tail classification, as explored by Charusaie et al. (2024, NeurIPS). We will further elaborate on this potential direction in the paper.\n\nWe also plan to conduct a more extensive empirical analysis in real-world settings, particularly in important scenarios where expert domains overlap (as suggested by Reviewer wQs7) and where the data is heterogeneous (as suggested by Reviewer 798e).\n\n[1] Tailor et al. (2024). Learning to Defer to a Population: A Meta-Learning Approach. AISTATS 2024.\n\n[2] Charusaie et al. (2024). A Unifying Post-Processing Framework for Multi-Objective Learn-to-Defer Problems. NeurIPS 2024.", "claims_and_evidence": "The paper provides proof for their claims.", "methods_and_evaluation_criteria": "N/A", "theoretical_claims": "N/A", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "This seems to be a very interesting learning setting and a good problem to study the properties of loss families.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "The paper is well written and discusses from both theoretical and practical perspectives. The authors show good properties regarding the loss families they proposed in two problem settings and provide complete analysis under low-noise assumptions.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "Are there any other interesting properties or improvements the authors want to achieve for their loss family besides those already mentioned in the paper? It would be nice if the authors could discuss a few sentences about future directions.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "mvmKhLpmo3", "reviewer": "Reviewer_m1gt", "summary": "The paper presents a novel surrogate loss for both single-stage and two-stage learning to defer. The authors show several theoretical guarantees, including $H$-consistency, Bayes consistency and $H$-consistency bounds for both the single and multiple expert settings.\nEmpirical results showcase the effectiveness of the approach.\n\n\n### Update after the Rebuttal\n\nI am satisfied with the authors' answers. I keep my positive score.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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**1. Empirical Evaluation:** Thank you for the suggestions. As recommended by the reviewer, we will aim to include experiments involving real-world experts, such as those considered in (Mozannar et al., 2023) and (Palomba et al., 2024), in the final version.\n\nBut, as you have mentioned, our paper primarily focuses on theoretically principled surrogate losses for learning to defer with multiple experts, grounded in realizable $H$-consistency and $H$-consistency bounds, within the learning theory framework. While we have empirically shown that minimizing our proposed loss functions outperforms the baselines in realizable settings and matches the best-known results in synthetic non-realizable settings—as predicted by our theoretical analysis—we recognize the importance of further empirical exploration. Accordingly, we plan to dedicate future work to conducting a more extensive empirical analysis in real-world settings, particularly in important scenarios where expert domains overlap (as suggested by Reviewer wQs7) and the data is heterogeneous (as suggested by Reviewer 798e).\n\nWe will also include a more detailed discussion of the limitations of our empirical analysis and outline potential directions for future work in the final version. Nevertheless, we believe our theoretical contributions are significant and well-suited for acceptance in the theory track of the ICML conference.\n\n**2. Deferring More to Experts:** We agree with the reviewer that deferring more to experts may not always be preferred in real-world applications, where querying experts can be more costly than relying on an ML model. We would like to clarify that the goal of our experiments on non-realizable data is not to claim that our proposed surrogate losses outperform the baselines in such settings. Rather, our results demonstrate that our surrogate losses match the performance of these state-of-the-art baselines in non-realizable scenarios in terms of system accuracy, as both are supported by consistency bounds.\n\nThe strength of our approach lies in the realizable setting, where our surrogate losses are guaranteed to be realizable $H$-consistent—unlike the baselines—as illustrated in Figure 1. Due to the specific realizable form of our surrogate losses, our model also defers significantly more and exhibits a greater tendency to select expert 2 compared to the baselines of Verma et al. (2023) and Mao et al. (2024b). This highlights a key effect of our proposed surrogate: it induces a deferral behavior that is qualitatively different from prior approaches.\n\n**3. Theoretical Claims:** Thank you for the suggestions. We will revise the notation for the conditional distribution and add further commentary on the proof based on your feedback.\n\n**4. Other Comments Or Suggestions:** Thank you for the suggestion. We will double-check the arXiv references and update them with their accepted versions, if available, in the final version.", "claims_and_evidence": "The theoretical contribution is strong, with several new results for Learning to Defer losses.", "methods_and_evaluation_criteria": "The empirical evaluation is limited, considering only a couple of baselines and the multi-expert case.\nThe choice of datasets could be improved. For example, the authors could look at the empirical evaluations of (Mozannar et al., 2023) or (Palomba et al., 2024), where they consider datasets with real human labels, rather than simulated ones.\nMoreover, the authors state that:\n> It also defers significantly more and exhibits a greater tendency to choose expert 2 or expert 3 compared to the baselines, demonstrating the effect of our proposed surrogate loss.\n\n I am not entirely convinced that deferring more to experts is desirable in real-life applications, where querying experts is typically more costly than using an ML model. \nFor instance, in both references mentioned before, the authors provide accuracy - coverage curves, to show how performance is affected when limiting the ability to defer.", "theoretical_claims": "I checked most of the proofs, and they seem correct.\nHowever, I have a few observations regarding the notation and how the proofs are presented:\n1) some notation choices that are uncommon and a bit cumbersome: e.g., for Theorem 3.1 and Theorem 4.1, denoting the conditional distribution $P(Y=y | X=x)$ as $p(x,y)$  is in my view just misleading as $p(x,y)$ recalls more naturally the joint distribution. I would propose the authors to change notation into something like $p(y|x)$, which is more natural in my opinion;\n2) In my opinion, several passages of the proofs are just not adequately commented on. Adding more comments is a courtesy to the reader, which can help make the whole proof more accessible. For example, the equation lines 4 to 6 in the proof of  Lemma 3.1 could be better presented, by adding a bit of comment on the fact you add and subtract $ \\sum_{j=1}^{n_e} \\mathbb{I}[(h(x) \\neq y)] \\mathbb{I}[h(x)\\neq n+j] $ and then explain why $(1-n_e) = (\\prod_{j=1}^{n_e}\\mathbb{I}[h(x)\\neq n+j] - \\sum_{j=1}^{n_e} \\mathbb{I}[h(x)\\neq n+j]) $.", "experimental_designs_or_analyses": "See the evaluation criteria shortcomings.", "relation_to_broader_scientific_literature": "The related work is adequately discussed in the Appendix section.", "essential_references_not_discussed": "To the best of my knowledge, the paper discusses the most relevant works in the area of learning to defer.", "other_strengths_and_weaknesses": "The paper advances the Learning to Defer literature with a novel surrogate loss family. Therefore, it is incremental in novelty but rigorous and sound in terms of theoretical aspects.\n\nI argue that the paper's main weakness is its limited empirical evaluation (see detailed comments in the other sections here).\n\nHowever, the merits of the paper still outweigh the current shortcomings, so I am prone to suggesting a weak acceptance.", "other_comments_or_suggestions": "Please double-check the arXiv papers in the references to see if they have an accepted version of the paper.", "questions_for_authors": "Can the authors briefly comment on my comments in the Theoretical Claims sections and the Methods And Evaluation Criteria?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper examines the problem of multi-expert learning to defer (single stage).  While previous work has derived consistent surrogate losses for the problem [Verma et al., 2023], they are not realizable H-consistent.  This paper addresses the issue, proving realizable H-consistency, H-consistency bounds, and Bayes-consistency.  All reviewers are in favor of acceptance, with the prominent criticisms being the reviewers found the contribution somewhat incremental and that the experiments could be made more real-world.  After reading the authors' rebuttal, I am convinced that these are not significant issues, especially as the paper's contribution is mostly about the learning theory.  

As for my own small recommendation, the paper could do a better job of summarizing / organizing the contributions / limitations of previous multi-expert work (e.g. H-consistent or not, two-stage vs single stage, etc); maybe a table (with rows being related work, columns being L2D settings) could do this effectively.
Decision: Accept (poster)