In Defense of Softmax Parametrization for Calibrated and Consistent Learning to Defer
Authors: Yuzhou Cao
Hussein Mozannar
Lei Feng
Hongxin Wei
Bo An
Venue: NeurIPS 2023 poster (2023)
Keywords: Classification
Learning to Defer
Probability Estimation
TL;DR: We justify the use of softmax in L2D with probability estimation by studying the cause of invalid probability estimators and then propose an asymmetric softmax that can induce both consistent loss and a valid probability estimator for L2D.

Abstract: Enabling machine learning classifiers to defer their decision to a downstream expert when the expert is more accurate will ensure improved safety and performance. This objective can be achieved with the learning-to-defer framework which aims to jointly learn how to classify and how to defer to the expert. In recent studies, it has been theoretically shown that popular estimators for learning to defer parameterized with softmax provide unbounded estimates for the likelihood of deferring which makes them uncalibrated. However, it remains unknown whether this is due to the widely used softmax parameterization and if we can find a softmax-based estimator that is both statistically consistent and possesses a valid probability estimator. In this work, we first show that the cause of the miscalibrated and unbounded estimator in prior literature is due to the symmetric nature of the surrogate losses used and not due to softmax. We then propose a novel statistically consistent asymmetric softmax-based surrogate loss that can produce valid estimates without the issue of unboundedness. We further analyze the non-asymptotic properties of our proposed method and empirically validate its performance and calibration on benchmark datasets.

In Defense of Softmax Parametrization for Calibrated and Consistent Learning to Defer
Yuzhou Cao
Hussein Mozannar
Lei Feng!*
Hongxin Wei
Bo An²
School of Computer Science and Engineering, Nanyang Technological University, Singapore 2CSAIL and IDSS, Massachusetts Institute of Technology, Cambridge, MA "Department of Statistics and Data Science, Southern University of Science and Technology, China yuzhou0028e. ntu intu.edu.... sg, mozannar gozannar@mit.edee 1 @ com, weihxe sustech.shhh.....o edu. en, boan@ntu.edis edu.
Abstract
Enabling machine learning classifiers to defer their decision to downstream expert when the expert is more accurate will ensure improved safety and performance. This objective can be achieved with the learning-toddefer framework which aims jointly learn how to classify and how to defer to the expert. In recent studies, it has been theoretically shown that popular estimators for learning to defer parameterized with softmax provide unbounded estimates for the likelihood of deferring which makes them uncalibrated. However, remains unknown whether this is due to the widely used softmax parameterization and if we can find softmax-based estimator that is both statistically consistent and possesses valid probability estimator. this work, we first show that the cause of the miscalibrated and unbounded estimator in prior literature is due to the symmetric nature of the surrogate losses used and not due to softmax. We then propose novel statistically consistent asymmetric softmax-bas based surrogate loss that can produce valid estimates without the issue unboundedness.. We further analyze the non-asymptotic properties of our method and empirically validate its performance and calibration on benchmark datasets.
Introduction
As machine learning models get deployed risk-critical tasks such as autonomous driving [18], content moderation [27], and medical diagnosis [20], we have higher urgency to prevent incorrect predictions. To enable a safer and more accurate system, one solution is to allow the model to defer to downstream human expert when necessary. The Learning to Defer (L2D) paradigm achieves this aim [28, 30, 31, 9, 44, 32, 33, 45, 35, 15, 42] and enables models to defer to an expert, i.c., abstain from giving prediction and request downstream expert for answer when needed. L2D aims to train an augmented classifier that can choose to defer to an expert when the expert is more accurate make prediction without the expert. L2D can be formulated a misimiiniiizationn problem that minimizes the 0- 1-e-errra risk [30], which incurs a cost of one when the classifier is incorrect or when we defer an expert who errs and incurs cost of zero otherwise.
Despite being formulated straightforwardly. the risk minimization problem is NP-hard even in simple settings [15, 32] due to the discontinuous and non-convex nature of the 0-1-deferral loss. To make the optimization problem tractable, many efforts have been made to design a continuous surrogate loss for the 0-1-deferral loss while guaranteeing statistical consistency, which means that the minimizer of the surrogate risk is that the O-l-deferral risk. Mozannar and Sontag [30], cross-entropy-line
Coorrspponiing author: Lei Feng.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

9x (z)
g. (a)
(z)
8x (z)
(z)
(z)
(z)
9.
am ( 1
[o.1)
(a.)e(o.11 v(a)e(0011
E A
fractional tanddormtiion
1)" C AA* x|0, +
[[0,1]**
t # 00
(a) Unbounded Estimator [30]
(b) Uncorrelated Estimator [44]
(c) Proposed Estimator
Figure I: Illustration of the proposed and previous estimators. Probability estimation in L2D aims to predict both the class probabilities and the expert's accuracy r) Pr(M Y| x) E E A [0, 1]. while only proposed estimator takes exactly the same range.
surroaate loss is proposed that is statistically consistent. Charusaic et al. [9] further generalized the results in Mozannar and Sontag [30] and showed that all the losses that are consistent for ordinary multi-class classification, i.e., clasification-cclibaaee [38, 43, 6]. are consistent for L.D with certain reformulation, which makes L.D a more comprehensive framework. By minimizing the risk w.r.f. consistent surrogate losses [30,9] 9J. we can obtain model that defers to who between the classifier and expert more accurate on an instance basis. However, we also need assessments of the uncertainty of the classifier when it predicts and the uncertainty of the expert prediction when we defer. This allows us to perform better triaging of samples and provide reliable estimates of uncertainty. Verma and Nalisnick [44] pointed out that the previous estimator in [30] generates highly biased probability estimates for the predictions due to its unboundedness. They then proposed a surrogate based on the One-versus All (OvA) strategy [52] to alleviate this problem, which allows both statistical consistency and improved calibration compared to the previous softmax-based method [30].
Does the difference in performance between OvA and softmax- methods indicate that softmax parameterization a sub-optimal choice in L2D? The cause of the unbounded probability estimation in [30] is in fact still elusive, and we cannot simply attribute it to softmax parameterization. Fur- thermore, notice that the rofumax-based method [30] is only a specific implementation of applying softmax in L.D. Meanwhile, softmax parameterization is also more straightforward modeling of multiclass posterior distributions: while the OvA strategy works by splitting a K K-class classification problem into K independent binary classification problems and thus induces K uncorrelated proba- bility estimators for each class, softmax parameterization works by directly estimating class posterior probabilities as whole. Given the wide use and practical advantages of softmax parameterization in classification tasks and the resemblance between L,D and multiclass classification, it is also promising that the usage of the softmax function can result in competitive methods for L2D. Then natural question arises: can we design a deftmax-based consistent surrogate loss for L2D without triggering unbounded probability estimation enabling calibrated estimates?
In this paper, we give a positive answer to this question by providing novel consistent surrogate loss with asymmetric softmax parameterization. which can be seen the combination of ordinary softmax function and an additional probability estimator. This surrogate can also induce a non- non-trivial bounded probability estimator for prediction probabilities and expert accuracy. To defend the use of softmax parameterization, we show that it not the cause of the failure but rather it the symmetric structure of the surrogates that leads to the unboundedness in probability estimation. Unlike the unbounded estimator [30] that mixes up class probabilities and the expert's accuracy and the OvA estimator that treats each class and expert independently, our method models the class probabilities as a whole with softmax and the expert's accuracy independently with a normalized function, which better reflects the structure of L.2D with probability estimation. The differences between our work and previous works are illustrated in Figure 1. We further analyze the limitation and broader impact of our work in Appendix G. Our contributions are four-fold and summarized below:
In Section 3, we prove that non-trivial bounded probability estimator does not exist as long as we are using symmetric loss functions.
We propose an asymmetric formulation softmax parameterization, and show that it can induce both consistent surrogate loss and non-trivial bounded probability estimator. We further show that the proposed asymmetric softmax-based method and OvA-based method [44] actually benefit from their asymmetric structure.

---

We further study the regret transfer bounds of our proposed asymmetric surrogate and show that it is compatible with both L2D and multi-class classification.
Experiments on datasets with both synthetic experts and real-world experts are conducted to demonstrate the usefulness of our method for both prediction and expert accuracy estimation.
2
Preliminaries
In this section, we review the problem setting of L2D and briefly introduce previous works.
2.1 Problem Setting
In this paper; we study the problem of learning to defer to an expert the K-class classification scenario. Let us denote by X and y = (1..... K} the feature and label space respectively. Denote by X XxYx x M E X' xx) y y the data-label-expert random variable triplet and æ, y, m are their realizations, which obeys an underlying distribution with density p(æ, y. m). We have access to data triplets {( Yi, m,));² that are drawn independently and identically from the distribution. The goal of L2D in the classification scenario is to obtain classifier with deferral option ʃ(-) : + > where is the option of deferral the expert and y is the augmented decision space y {1).
The problem evaluation is the following 0- --deferral loss for 2, which is generalized version of the zero-one loss lo (f (z). .z).)) y) [f())) * y]. which takes the value of if we use the output of the classifier when it predicts an incorrect label ([f(x)= E ) and f(x) + v]) or defer to the expert when they are incorrect (I)( = 1 and m + yl). where [.] is the Iverson bracket notation suggested by Knuth [22]. Then we aim minimize the risk w.r.l to this loss:
min, Roi (J) = Ep(r.m)) [ (f y. m)]
Denote by f the minimizer of the risk Rih (f). i.c. the Bayes optimal solution, and n)x)) (Pr(Y x X x)) ==) Mozannar and Sontag [30] provide characterization of the form of the Bayes optimal solution as:
Definition 1. (Bayes optimality of L2D) A classifier with deferral option f + y is the minimizer of Ry (f) if and only it meets the following condition almost surely:
max, Th (x) < Pr(M = Y = x), f'(x) argmax, (z), else.
The form of the optimal solution is intuitive: we should defer to the expert if they have a higher probability of being correct than the optimal classifier which follows the most likely label class given the input This optimal solution can also be seen as the generalized version of Chow's 's rule in learning to reject [10], where fixed cost [0, serves as the known accuracy of an expert.
2.2 Consistent Surrogate Losses for L2D
Although we know the form of the Bayes optimal solution, practically the risk minimization problem above faces computational difficulties: the minimization of the discontinuous and non-convex problem (1) is NP-hard [32]. A widely used strategy for tackling this difficulty is to substitute the original loss function which is discontinuous with a continuous surrogate, which has been applied in many areas including ordinary classification [52, 6, 43, 39, 16, 37], multi-labe classification [17, 23, 51, 47], AUC optimization [17, 23, 29], cost-sensitive learning [41, 11], top-K classification [25, 48], adversarially robust classification [4, 2, I]. and learning to reject [12, 13, 5, 49, 34, 8, 7]. Denote by g X' > I K++1 the learnable scoring function that induces our decision function for L2D f X y with the following transformation & K+ + +
1,
(x-1(x) > max gy (x) else.
p(g(x))
argmax vey By (2:),
'Though the formulation introduced here is not its most general version, only study this one and its induced surrogates (4) since previous works on the design of surrogate losses for L2D [30, 9, 44J also concentrated on it.

---

We consider continuous surrogate function + 1R*+ xXxX +
R and the surrogate risk below:
ming R (g) g.))...m) (0gg y,))
Assuming we find a surrogate function that overcomes the computational optimization challenges, we need to verify the consistency of & w.r.t for i.e. any minimizer of the surrogate risk also minimizes the original risk: (2):
4p g" argminn Rm (f), Vgg E argming (t(
The first consistent surrogate [30] w.r.t t is proposed by modifying the softmax cross-entropy loss:
Ler(g(z), y. m) = - log v (g(x)) )) - [m = yl log wh+ (g(x)),
(3)
where wpsm is the softmax function (/gg (w) = exp(ux) (uy) E exp(ur)) where is the dimension- ality of the input. Inspired by the risk formulation above, Charusaie et al. [9] further generalized the family of consistent surrogate for for by considering the following consistent surrogate reformulation:
Lø(g(z), y, m) (x) 4) + [m v]o(g(æ), K 1).
(4)
is known from Proposition 2 Charusaie et al. [9] that surrogates take the form above are consistent w.t.t for if á is iitiifiicationccalbrattet multi-class loss [43, 6]. Using this result, we can directly make use any statistically valid surrogate loss ordinary classification with simple modification.
2.3 Problems with Probability Estimation for L2D
While prior literature has established how to construct consistent surrogates for L.D,, it is less well- known whether such surrogates can actually provide calibrated estimates of classifier and deferral probabilities. As mentioned before, we are also interested in the true probability of the correctness of our prediction, i.e., the value of ny(x) (label being Y) and Pr(M- = Y|X x) (expert is correct). To achieve this goal of probability estimation, the commonly used method is to combine the obtained scoring function g" with transformation function & make the composite function & g" probability estimator rj (g(x)). For example, the softmax function is frequently used as & in ordinary multi-class classification to map the scoring function from R. K to A So far, we have not discussed whether these probability estimates are valid.
In the task of L2D for classification, aim estimate both ():) K and Pr(M YJX
æ) E [0, with K - 1-dimensional estimator, where its y-th dimension is the estimate of fy (x) for y E and K + 1-th dimension is the estimate of Pr(M = Y|X æ).. Correspondingly, the transformation v should be from I K++1 to a range P that contains A K x [0, 1]. It was shown in Theorem of Mozannar and Sontag [30] that probability estimator rं sm with the softmax output of scorer function and an extra fractional transformation guarantees to recover class probabilities and expert accuracy at g" E argmin, RLCE (g). which formulated as:
am (g (x) = w (z)) (1 vK+ (g(x)) 1g
Vy WK
(5)
noticeable that the range of this estimator is f E AK [0, +ool: the estimate of expert accuracy + is unbounded above and will approach +oo if K (u) - 1. Verma and Nalisnick [44] pointed out that the unboundedness can hurt the performance of this probability estimator: J/mm (K > 1/2, the estimated expert accuracy will be greater than 1 and thus meaningless. Experimental results also show the frequent occurrence of such meaningless results due to the overconfidence of deep models [19]. We further illustrate such miscalibration in Figure 2.
To mitigate this problem, new OvA-based surrogate loss that can induce a bounded probability estimator while remaining consistent is proposed in [44], which has the following formulation:
LovA (g(x), y, = ( (x)( Σ
y' E(- By (æ)) [m v](E(g--((z)) (((x))))))))))(((()) (x))), (6)
K+1
where is a binary proper composite [46, 40] loss. Its induced probability estimator OvA is:
No (g(x)) (x))), Vy V (K +
where the is mapping to J0, 1] determined by the binary loss, which makes OvA bounded. It is also experimentally shown that the ,vv outperformed jam [30] in the task of probability estimation.

---

Invalid Region
Pexpert
Maspuified Calibration Erroe
Calibration Erroe
P-
Real Value (p. 0.6, Propert 0.7)
Invalid Estimate (p 0.5, Pesper 1.5)
Clipped Estimate
Figure 2: Illustration of the miscalibration of estimator (5) on a binary classification with deferral problem. unbounded estimator (5) estimates (n(=)::Pe(M==1XX
(+++(A)=))X=aa) that takes value in the 2-D probability simplex denoted by the left triangle and then obtain the final estimate with the fractional transformation (5). However, when over-confidence occurs in 2-D simplex, i.e,, softmax output lies in invalid region that 43 1/2, (5) will magnify the calibration error of the estimates and clipping it to a valid estimate cannot solve this problem.
Given the success of the OvA-based loss, can we assert that softmax parameterization inferior to the Ovλ strategy in probability estimation for L2D? We argue in this paper that such conclusion should not be drawn so quickly. We should not discourage the use of softmax parameterization based solely on the specific implementation (3), since there may be other implementations of softmax that can resolve the issues with vfsm. Furthermore, the great success of softmax parameterization in deep learning models suggests that this potential implementation could also achieve outstanding performance. In this paper, we focus on finding such an implementation and show its superiority both theoretically and experimentally.
3 Problem with Symmetric Losses for L2D with Probability Estimation
Before beginning the search for a suitable implementation of softmax parameterization for L2D, important determine the cause of the unboundedness of fyam. Is it due to the of softmax parameterization or some other factor? If the reason is the former one, any attempts to create a bounded probability estimator with softmax function for L.2D will be in vain. Therefore, is crucial to identify the root cause of the unboundedness before proceeding with further efforts.
Surprisingly, we find that such unboundedness is not particular problem of softmax parameterization and is a common one shared by many loss functions. Recall that the loss (3) with unbounded estimator 77 is special case of the consistent surrogate (4) by setting the multi-class loss ò softmax cross-entropy loss. We show that even we use other losses beyond the softmax function and choose other losses such as the standard OvA losses ((14) in Zhang [52]). the induced probability estimators are still inevitably unbounded (or bounded but induced from an unbounded one) as long as we are using e with symmetric structure:
Theorem 1. (Impossibility of non- trivirivial bounded probability estimator with symmetric losses) If surrogate loss T& defined as (4) has probability estimators and is induced from symmetric consistent multi-class loss ø such that that Pő(u) = o( Pu), where P is any permutation matrix, it must have unbounded probability estimator r): let g" argmin RL, (g). we have that Vn)()) where "gg"" (x)) [n(x);; Pr(M Y|X =)], r not bounded above. Furthermore, any bounded probability estimator vj for Ls must be a piecewise modification of the unbounded estimator r):
denote by U Ug argmin, ΣK+ B, ByL v) for all B A x [0, 1]. we have that r/' is equal to on U.
The proof is provided in Appendix A. Intuitively, the existence of such an unbounded estimator is caused by the fact that symmetric loss induced Ls neglects the asymmetric structure of the probabilities to be estimated by modeling 1=PM(==YX==a) ( directly. Furthermore, all potential bounded probability estimators are piecewise modifications of the unbounded estimator sharing same values on 24 with r). which means that they are generated by substituting the invalid values of the unbounded estimator with valid one, e.g., we can obtain bounded estimator based on the unbounded one (5) by clipping it to if its estimated expert accuracy is larger than 1.
5

---

However, such modifications to make an unbounded estimator bounded are not very useful. Due to the training process's complexity and the distribution's is arbitrariness. it is hard design an appropriate modification of an unbounded estimator. For example, though we can bound the expert accuracy of (5) by when it generates an invalid value that is larger than I, it is still an overly confident estimation. Meanwhile, we do not know how to upper bound it by a value lower than 1 without prior knowledge of Pr(M- = Y|X = æ). Overall, training with Ly in Theorem can easily lead to model that generates invalid probability estimation with an unbounded estimator rt, while most modified bounded estimators cannot efficiently solve this problem. We will experimentally verify this point in Section 5.
This result shows that the consistent surrogate framework [9] does not directly provide us a solution for solving the unboundedness problem since most multi-class losses we use, e.g., CE loss, OvA loss, Focal loss [26], are symmetric. This motivates the design of surrogates with bounded probability estimators for I.2D) in our work. Based on Theorem 1, we have the following findings: firstly unboundedness of probability estimators is not necessarily caused by the softmax parameterization, as the induced estimator of any symmetric loss, c.g., standard softmax- free symmetric OvA losses [52], exhibits unboundedness too. Secondly, due to the fact that the OvA strategy for L2D (6) successfully gets rid of the unboundedness issue, we can reasonably deduce that modified softmax function can also present similar outcomes. In the following section, we propose a novel modification of the softmax parameterization that overcomes these issues and reveals that both the previous OvA-based work [44] and our current work benefit from the use of asymmetric losses.
4 Consistent Softmax-Based Surrogate with Bounded Probability Estimator
In this section, we find a softmax parameterization that is feasible solution in L2D for the construc- tion of surrogate loss with a bounded probability estimator. We first propose a cross-entropy surrogate loss but with an asymmetric transformation that resembles the ordinary softmax function for its first K elements but processes the K + 1-th coordinate in a special way. Then we show that such a transformation has useful properties for both classification and probability estimation, and then provide consistency analysis for both the loss function and its induced bounded probability estimator. Finally, we show that our proposed loss and the OvA loss [44] are connected to the consistent surrogate formulation (4) with the use of asymmetric multi-class losses, which indicates the helpfulness of asymmetry and shed light on the future study of consistent surrogates for L2D with bounded estimators.
4.1 Consistent Surrogate Formulation with Asymmetric Bounded Softmax Parameterization
Before searching for softmax- parameterization that is capable of L2D with probability estimation, we need to better understand the failure of (3) for inducing a bounded probability estimator. By inspecting the proof of consistency in Theorem 1 of Mozannar and Sontag [30], we can learn that the
cross-entropy- surrogate (3) works by fitting a K + 1 class posterior distribution: ą/Sl (g") =
ri(x) [=Pr(M=>10)>
(z)
I+Pt(M= Y= Y I+P] Though we can check that the şp gg is
Tie (x))
Pr(M=V|ar)
exactly a Bayes optimal solution of Roj (f) due to the monotonicity of the softmax function and the form of fj, get (n)
(r) Pr(M Y|X æ)] we need to perform an extra inverse transformation should be exerted on yea.. This is caused by the following dichotomy: the class probabilities and expert accuracy we aim to estimate are in the range of A [0, 1], while the standard softmax- parameterization of (3) maps the K + 1 dimensional scoring function g into A+1
To solve this issue, promising approach is to modify the softmax function to make it transformation that can directly cast the scoring function g into the target range A K x [o, 1]. Since the target range is not symmetric, the modified softmax should also be asymmetric. This idea is given concrete form in the following asymmetric softmax parameterization:
Definition 2. (Asymmetric softmax parameterization) Jb is called a asymmetric softmax function that for any K > and u E RK+1,
exp(uy)
U K 11
K =1 exp(u,r)
(2)
(8)
explux+1)
exp(u,r) -aak expla,)) else.

---

At first glance, the proposed asymmetric function appears to be the standard softmax function, which excludes the K + 1-th imput of u for y + K + However, the last coordinate of the function takes on quite different form. This special asymmetric structure is designed to satisfy the following properties:
Proposition 1. (Properties of 3) For any u E RK+1;
(i) (Boundedness) vu()) E A x [0, (ii). (Maxima-preservingg yr K+I vy = yE(," KK1] Mg-
It can be seen that the proposed asymmetric softmax V is not only bounded but also successfully maps g into the desired target range, which indicates that & may directly serve as the probability estimator r (g(x)) (g x)). Furthermore, the maxima- preseerving property guarantees that the estimator also capable of discriminative prediction: if a scoring function g' can recover the true probability, i.e., n (g' (x)) ] = (r(z))P((M = Y|X = æ)), then a g must also be the Bayes optimal solution of Ro (g). Based on the asymmetric softmax function, we propose the following surrogate loss for L2D:
Definition 3. (Asymmetric Softmax-Parameterized Loss) The proposed surrogate for L2D with asymmetric softmax parameterization L.g(u, y. m) : [++ x y x y is formulated as:
L uu, y, m) = - log(dy (u)) [m + y] log(1 (x++ - [m = y] log log(vxx1(u))
(9)
The proposed loss takes an intuitive form, which can be seen as the combination of the cross-entropy loss (the first term) and modified version of binary logistic loss (the last two terms). This formulation is inspired by the structure of our problem, where the expert accuracy is not directly related to class probabilities while the class probabilities should fulfill that n²x)) E A A In fact, the proposed surrogate is not simple summation of two independent losses and they are indirectly related by the asymmetric softmax function: according to Definition 2, the two counterparts share the same elements [91, ... 9K]- This correlation serves as a normalization for + that brings the property of maxima-prees pressering.... which is crucial for the following consistency analysis:
Theorem 2. (Consistency of Lü and bounded probability estimator v)*)
The proposed surrogate L5j a consistent surrogate for L2D, i.e., poo" E argmin, Rih (f), Yg argming g R (g). The bounded probability estimator can also recover the desired class probabilities and expert accuracy: v (g" (x)) = [m(x): Pr(M Y|X = =)], Vo E X. Furthermore, if there exists other probability estimators for L they must also be bounded.
The proof can be found in Appendix C. According the theorem above, we showed that our proposed asymmetric softmax function induces a consistent surrogate and a bounded probability estimator. We also showed that there does not exist an unbounded probability estimator for Lgg, which guarantees that proposed bounded estimator is never the modification of an unbounded one. This result enriches the toolbox for L.2D with probability estimation and theoretically justifies the use of softmax parameterization in L.2D. In fact, we can further substitute the cross-entropy-like counterpart with any strictly proper loss [46] to get the same consistency result. In the following subsection, we will discuss the relationship between our method and the general consistent surrogate framework [9].
4.2 Connection with Consistent Surrogate Framework [9]: Asymmetry Can Help
In the previous section, we showed that there exists an implementation of softmax & that can induce both a consistent loss and a valid probability estimator for L2D. Given the theoretical successes of our proposed boftmax-based method and the previous OvA strategy, we may further expect them to provide more insights into the design of surrogates and probability estimators for L2D. Recalling the consistent surrogate formulation (4) proposed in Charusaie al. [9] that allows the use of all consistent multi-class losses for constructing L2D surrogates, it is an instinctive idea that our proposed consistent surrogates (9) and the previous work [44] can be included this framework. However, this idea may not be easily confirmed: Theorem 1 implies that the two surrogates are not the trivial combinations of commonly used symmetric losses and formulation (4) since they can both induce bounded probability estimators. The following corollary shows that the two surrogates are included in
7

---

Cximated Acceraty
32
Denera
24
37
0.8
68
07
0.5
0.9
0.
0.0
0.8
0.8
Expert Aczuney
Expert Accusetyy
Expert Anoumey
Expert Acouneyy
(a) S-SM
(b) S-OvA
A-OvA
(d) A-SM (Proposed)
Figure 3: Distributions of the true and estimated accuracy of baselines and proposed method on CIFAR 10H.
the family of consistent surrogate formulation (4), but induced from two novel asymmetric multi-class surrogates.
Corollary We can get the consistent surrogates Lg (9) and Lova (6) by setting & in the consistent loss formulation (4) to specific consistent and asymmetric multi-class losses.
Due to page limitations, present the formulation of the asymmetric multi-class losses and the proof in the Appendix D. Although this conclusion reveals the connection between the two consistent surrogates and the general framework (4), it is important to note that it does not necessarily imply that the results in Verma and Nalisnick [44] and this paper are trivial. Since asymmetric losses seldom used in ordinary multi-class classification, it is hard obtain L3 and LovA by simply selecting from known consistent multi-class losses. According to this corollary and theorem 1, can determine that a multi-class loss ó with asymmetric structure is a necessity we aim to design consistent L.2D surrogates with bounded probability estimators based the general formulation (4). Based on this insight, it is promising to discover more surrogates with bounded probability estimators for L.2D by focusing the design of asymmetric multi-class surrogates.
4.3 Regret Transfer Bounds
this section, we further study the regret transfer bounds of our proposed surrogate (9) to characterize the effect of minimizing surrogate risk Rz,: (g) both the target risk Røi (g) and the misclassification error of the classifier. Denoted by Jeless g1-K k the classifier counterpart of our model and Roi (g) is its misclassification error, we can show that:
Theorem 3. max (Roi (gelass) ) Ro1, R - - R
& (22(11,,, (R. (g) - )lr
The proof can be found in Appendix E. This theorem shows that use the excess risk of our proposed surrogate to upper-bound bound those of our concerned targets, and its proof is conducted by applying Pinsker's inequality and zooming.
This theorem shows that as long as we reach a low risk w.rlf the proposed surrogate (approximately optimal), we can obtain model with satisfying performances for both I.2D and classification. This conclusion is not trivial: according to the characterization of R 's Bayes optimality Definition 1, the classifier counterpart not guaranteed to classify accurately the deferred samples. We will further experimentally demonstrate the efficacy of our surrogate for L2D and classification in the next section.
5 Experiments
In this section, we compare our proposed asymmetric softmax estimator and its induced surrogate loss with the estimators and losses in previous works. Detailed setup can be found in Appendix F.
Datasets and Models. We evaluate the proposed method and baselines on widely used benchmarks with both synthetic and real-world experts. For synthetic experts, we conduct experiments on the CIFAR 100 [24]. Following the previous works, the expert has a chance y to generate correct labels on the first k: E {00. 40, 60} classes and at random otherwise. We set p 94% as in Mozannar and Sontag [30] and 75% as in Verma and Nalisnick [44] to simulate experts of high and medium accuracy. For real- world experts, use CIFARIOH, HateSpeech, and ImageNet- 16H [36, 14, 21]

---

Table 1: Experimental results CIFARIO0 with for 5 trials. We report the mean (% Jistaddard enerty)) of related statistics. The best and comparable methods based on I-test significance level 5% are highlighted in boldface.
Budgeted Error
Method
Expert
Error
Coverage
ECE
10%
20%
30%
Expert Accuracy 94%
20
24.58(0.13)
77.72(0.31
4.86(0.11)
31.6((033)
25.00X0.24)
24.59(0.13)
S-SM
40
21.92(0.33)
57.89(0.54)
9.22(0.38)
46.69(0.63)
38.50(0.60)
29.94(0..2))
60
(8.69(0.88)
40.34(6.28)
11.10))77
59.44(4.95)
51.36(5.08)
42.77(5.09)
20
27.00(1.91)
85,40(0.91)
5.15(0.31)
28.42(2.26)
27. 27.00(191)
27.00(1.91)
S-OvA
40
27.33(1.50)
68,47(1.59)
9.38(0.46)
39.95(2.35)
32.93(2.30)
27.92(2.06)
60
18.44(0.64)
58.18(1.55)
7.70(0.24)
42.52(1.74)
33.67(1.72)
25.74(1.75)
20
25.6340.97)
90.40(0.89 89)
4.35().29)
25.65(0.99)
25.63(0.97)
25.63(0.97)
A-OvA
40
23. 23(0.4))
80.46(0.51)
6.81(0.33)
27.44(0.62)
23.23(0.42)
23.23(0.44)
60
19.64(1.00)
70.44(2.73)
7.34(0.38)
31,90(.73)
24.75(2.73)
(1.65().62)
20
24.54(0.06)
98.16(0.033
4.63(0.11)
24.54(0.06)
24.54(0.06)
24.54(0.00)
A-SM
40
22.17(0.36)
92.20(0.32)
6.58(0.22)
22.17(0.36)
22.17(0.36)
22.17(0.36)
(Proposed)
60
19.50(0.58)
84.72(0.30)
5.96(0.44)
22.91(0.42))
19.30(0.58)
19.30(0.58)
Expert Accuracy = 75%
20
25.49(0.20)
86.46(0.52)
5.07(0.21)
26.09(0.23)
25.48(0.20)
25 (9(0.00)
S-SM
40
25.13(0.44)
74.65(0.48)
12.82(0.29)
32.82(0.66)
26.99(0.55)
25.13(0.44)
60
24.05(0.43)
60.25(1.21)
18.70(0.55)
42.30(0.98)
36. 18(0.99)
29.47((.10)
20
26.53(0.86) (6)
90.06(2.92)
5.57(0.54)
26.83(L.20)
26.53(0.86)
26.53(0.86)
S-OvA
(
77.69(5.85 82)
7.14(1.4)
32.30(4.92)
28.33(3.11)
26 26.90())78)
25.29(0.69)
69.08(1.35)
7.47(0.12)
36.67(1.45)
30.44(1.33)
25.70(1.15)
20
25.94((.52))
93.05(0.43)
4.78(0.29)
25.94(0.52)
25.94().52)
25.94(0.52))
A-OvA
40
25.73(1.07)
83.29(2.19) 19)
5.75(0.80)
27.75(L.39)
25.73(L007)
25.73(L.07)
60
(2.81(0.522)
79.76(1.96
6.10())3))
27.19(164))
23.08(0.87)
(2.81(0.52)
20
24.58(0.12)
98.90(0.75)
4.34(0.31)
24.58(0.12)
24.58(0.12)
24.58(0.12)
A-SM
40
(0.35)
96.53(0.21)
5.58(..1))
(4.29(0.35)
24.29(0.35)
(0.29(0.35)
(Proposed)
60
22.48(0.32)
92.63(0.33)
5.58(0.17)
22.48(0.32)
22.48(0.32)
22.48(0.32)
datasets, where the expert's prediction is generated using the provided auxiliary expert information. More experimental results of real-world experts can be found in Appendix F.
For CIFAR-100, HateSpeech, and ImageNet-1611 16H, we report the misclassification error, coverage, and the ECE of the expert accuracy estimates. We also report the error of our model with the deferral budget as in Figure 4 of Verma and Nalisnick [44] to further evaluate the performance of the obtained classifier. For CIFAR 10H, plot the distribution of the true and estimated expert accuracy in Figure 3 to illustrate the performance of basclines and our method on fitting Pr(M = Y|X = x). The experiments on CIFAR- 100 is conducted with 28-layer WideResNet [50] and SGD in previous works [30, 44], and those on datasets with real-world experts are conducted using pre-trained models/embeddiing.
Baselines. We compare our Asymmetric SoftMax based method (A-SM) with the previously proposed Symmetric SoftMax-based (S-SM) method [30] and Asymmetric OvA (A-OvA) based method [44]. We also combined the Symmetric OvA logistic loss (S-OvA) with (4) to further evaluate the effect of symmetric loss and its induced unbounded estimator. For unbounded probability estimators in S-SM and S-OvA, we clip their estimates into [0, 1] to make them valid. We directly use the output of baselines and our method without post-hoc techniques [19, 33] to better reflect their own performance.
Experimental Results. By observing Figure we can find that the distributions of bounded method A-OvA and our proposed A-SM have markedly more overlap with the true distribution compared with the symmetric and unbounded ones, which directly shows that the bounded estimators can better estimate of expert accuracy. As can be seen from the experimental results reported in Table 1 and our proposed A-SM is always better than or comparable to all the baselines w.r.. classification accuracy. We can also see that the coverage of our method is always significantly higher than the baselines, which shows that our surrogate can induce ideal models for I.2D. Though S-SM is comparable to A-SM with high-accuracy expert, it has significantly lower coverage and is

---

Table 2: Experimental results HateSpeech and ImageNet-16i with noise type "095" for 5 trials. We report the mean( & jsaunddd enoo(()) related statistics. The best comparable methods based on I-test at significance level 5% are highlighted in boldface.
Budgeted Error
Method
Error
Coverage
ECE
10%
20%
30%
HateSpeech
S-SM
8.65(0.14)
70.19(1.50)
3.95(0.48)
25.48(0.49)
16.80(0.44)
8.97(0.33)
S-OvA
8.65(0.14)
69.90(0.53)
1.77(0.07)
24.19(0.25)
15.89(0.34)
8.78(0.31)
A-OvA
9.64(0.32)
77.2(0.42)
1.73(0.26)
16.525(0.28)
8.80(0.25)
8.56(0.29)
A-SM
8.06(0.40)
81.98(0.58)
1.53(0.26)
15.07(0.35)
8.06(0.40)
8.06(0.40)
ImageNet-16H
S-SM
15.08(1.19)
26.41(1.78)
22.92(2.59)
68.58(1.30)
60.33(1.19)
51.27(1.94)
S-OvA
15.15(1.50)
23.08(2.39)
11.68(0.53)
68.91(2.51)
60.08(1.82)
51,5002.05)
A-OvA
14.17(0.58)
21.56(2.13)
(1.57(1.50)
71.14(2.10)
62.39(2.10)
53.95(2.27)
A-SM
12.59(0.79)
39.48(2.50)
8.13(1.33)
57.75(1.37)
49.66(1.18)
40.85(1.51)
outperformed by A-SM with an expert of lower accuracy, which indicates that it is suffering from the problem of deferring more samples than necessary. This problem is also observed in learning with rejection [8]. Though S-OvA can mitigate this problem, its coverage is still consistently lower than A-SM. Notice that when there exist deferral budget requirements, all the unbounded baselines outperformed by A-OvA, and A-OvA is further outperformed by A-SM, which indicates that our method can also efficiently generate a classifier. Meanwhile, the ECE of our estimated expert accuracy is also comparable to or better than A-OvA, while those of the unbounded ones all have significantly higher ECE, which further shows the efficacy of our method in estimating expert accuracy.
Conclusion
In this paper, we provide novel consistent surrogate loss based on asymmetric softmax function for learning to defer that can also provide calibrated probability estimates for the classifier and for expert correctness. We reveal that the root cause of the previous unbounded and miscalibrated probability estimators for L.D is not softmax but the intrinsic symmetry of the used loss function. We solve this problem by designing an asymmetric softmax function and using it to induce a consistent surrogate loss and a bounded probability estimator. We further give the regret transfer bounds of method for both L2D and classification tasks. Finally, evaluate method and the baseline surrogate losses and probability estimators on benchmark datasets with both synthetic and real-world experts and show that we outperform prior methods. While we provide consistent multi-expert extension our proposed surrogate in Appendix H, it is still promising future direction to generalize the multi-expert surrogates [45] all the consistent multiclass losses in Charusaie et al. [9].
Acknowledgement
This research/project is supported by the National Research Foundation, Singapore and DSO National Laboratories under the AI Singapore Programme (AISG Award No: AISG2-GC-2023 -C--G2C-2000999 and Ministry of Education, Singapore, under its Academic Research Fund Tier 1 (RG13/22). Lei Feng supported by Chongqing Overseas Chinese Entrepreneurship and Innovation Support Program, CAAI-Huawei MindSpore Open Fund, and Openl Community https://openi.pll.accom Hussein Mozannar thankful for the support of the MIT-IBM Watson Al Lab.
10

---

References
[I] Pranjal Awasthi, Natalie Frank, Anqi Mao, Mehryar Mohri, and Yutao Zhong. Calibration and consistency of adversarial surrogate losses. CoRR, abs/2104.09658, 2021. URL https:
//arxiv. wwwpiv..rgg/aaoeeee /
[2] Pranjal Awasthi, Anqi Mao, Mehryar Mohri, and Yutao Zhong. finer calibration analysis for adversarial robustness. CoRR, abs/2105.01550, 2021. URL URL.httpp//aaxxivvco abs/ 2105. 01550.
[3] Gagan Bansal, Besmira Nushi, Ece Kamar, Eric Horvitz, and Daniel S. Weld. Is the most accurate Al the best teammate? optimizing Al for teamwork. In AAAI, 2021.
[4] Han Bao, Clayton Scott, and Masashi Sugiyama. Calibrated surrogate losses for adversarially robust classification. In COLT, volume 125 of Proceedings of Machine Learning Research, pages 408-48 -51. PMLR, 2020.
[5] Peter L. Bartlett and Marten H. Wegkamp. Classification with reject option using a hinge loss. J. Mach. Learn. Res., 9:1823-1840, 2008.
[6] Peter I. Bartlett, Michael I Jordan, and Jon D McAuliffe. Convexity, classification, and risk bounds. Journal of the American Statistical Association, 101(473):188-15, 2006.
[7] Yuzhou Cao, Tianchi Cai, Lei Feng, Lihong Gu, Jinjie GU, Bo An, Gang Niu, and Masashi Sugiyama. Generalizing consistent multi-class classification with rejection to be compatible with arbitrary losses. In NeurIPS, 2022.
[8] Nontawat Charoenphakdee, Zhenghang Cui, Yivan Zhang, and Masashi Sugiyama. Classifica- tion with rejection based cost-sensitive classification. In ICML, volume 139 of Proceedings of Machine Learning Research, pages 1507-1517. PMLR, 2021.
[9] Mohammad-Amin Charusaie, Hussein Mozannar, David A. Sontag, and Samira Samadi. Sample efficient learning of predictors that complement humans. In ICML, 2022.
[10] C. Chow. On optimum recognition error and reject tradeoff. IEEE Transactions on Information Theory, 16(1):41-46, 1970. doi: 10.1 109/TT9TTTTITT 1970. 1950..0
[11] Scott Clayton. Calibrated asymmetric surrogate losses. Electronic Journal of Stats, 6:238-238. 2012.
[12] Corinna Cortes, Giulia DeSalvo, and Mehryar Mohri. Boosting with abstention. NeurlPS, pages 1660-1668, 2016.
[13] Corinna Cortes, Giulia DeSalvo, and Mehryar Mohri. Learning with rejection. In ALT, volume 9925, pages 67-82, 2016.
[14] Thomas Davidson, Dana Warmsley, Michael W. Macy, and Ingmar Weber. Automated hate speech detection and the problem of offensive language. In ICWSM, 2017.
[15] Abir De, Nastaran Okati, Ali Zarezade, and Manuel Gomez Rodriguez. Classification under human assistance. In AAAI, 2021.
[16] Jessica Finocchiaro, Rafael M. Frongillo, and Bo Waggoner. An embedding framework for consistent polyhedral surrogates. In NeurIPS, pages 10780-10790, 2019.
URL htttps://proceediii .wwnnggnnneeeeee neurips cc/ httpppppr/2111 // / Beci1fee220133133554111133333333
.tmll.
[17] Wei Gao and Zhi-Hua Zhou. On the consistency of multi-label learning. Artif. Intell., 199-200: 22 44, 2013.
[18] Sorin Mihai Grigorescu, Bogdan Trasnea, Tiberiu T. Cocias, and Gigel Macesanu. A survey of deep learning techniques for autonomous driving. Field Robotics, 37(3):362-3888 2020.
[19] Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q. Weinberger. On calibration of modern neural networks. In ICML, 2017.

---

[20] Mohammad Ali Kadampur and Sulaiman Al Riyaee. Skin cancer detection: Applying deep learning based model driven architecture in the cloud for classifying dermal cell images. Informatics in Medicine Unlocked, 18: 18:100282, 2020. ISSN 2352-9148.
[21] Gavin Kerrigan, Padhraic Smyth, and Mark Steyvers. Combining human predictions with model probabilities via confusion matrices and calibration. In NeurlPS, 2021.
[22] Donald E Knuth. Two notes on notation. The American Mathematical Monthly, 99(5):403 422, 1992.
[23] Oluwasanmi Koyejo, Nagarajan Natarajan, Pradeep Ravikumar, and Inderjit Dhillon. Consis- tent multilabel classification. In NeurIPS, pages 3321-3329, 2015.
[24] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[25] Maksim Lapin, Matthias Hein, and Bernt Schiele. Analysis and optimization of loss functions for multiclass, top-k, and multilahel classification. IEEE Trans. Puttern Anal. Mach. Intell., 40 (7):1533-1554, 2018.
[26] Tsung-Yi Yi Lin, Priya Goyal, Ross Girshick, Kaiming He, and Piotr Dollár. Focal loss for dense object detection. IEEE International Conference on Computer Vision (ICCV), 2017.
[27] Daniel Link, Bernd Hellingrath, and Jie Ling. A human-is-the-loop approcca for semi-automated content moderation. ISCRAM, 2016.
[28] David Madras, Toniann Pitassi, and Richard S. Zemel. Predict responsibly: Improving fairnsss and accuracy by learning to defer. In NeurlPS, 2018.
[29] Aditya Krishna Menon and Robert C. Williamson. Bayes-optimal scorers for bipartite ranking. In COLT, volume 35 of JMLR Workshop and Conference Proceedings, pages 68-106. JMLR.org. 2014. URL http: pttp///eoceeeigneeeeee/e/..s..se mlr. press / v35 /enon. html.
[30] Hussein Mozannar and David A. Sontag. Consistent estimators for learning to defer to an expert. In ICML, 2020.
[31] Hussein Mozannar, Arvind Satyanarayan, and David A. Sontag. Teaching humans when to defer to a classifier via exemplars. In AAAI, 2022.
[32] Hussein Mozannar, Hunter Lang, Dennis Wei, Prasanna Sattigeri, Subhro Das, and David A. Sontag. Who should predict? exact algorithms for learning to defer to humans. CoRR, abs/2301.06197, 2023.
[33] Harikrishna Narasimhan, Wittawat Jitkrittum, Aditya Krishna Menon, Ankit Singh Rawat, and Sanjiv Kumar. Post-hoc estimators for learning to defer to an expert. In NeurlPS, 2022.
[34] Chenri Ni, Nontawat Charoenphakdee, Junya Honda, and Masashi Sugiyama. On the calibration of multiclass classification with rejection. NeuriPS, 2019.
[35] Nastaran Okati, Abir De, and Manuel Gomez-Rodriguez. Differentiable learning under triage.
In NeurlPS, 2021.
[36] Joshua C. Peterson, Ruairidh M. Battleday, Thomas Griffiths, and Olga Russakovsky. Human uncertainty makes classification more robust. In ICCV, pages 9616-9625, 2019.
[37] Bernardo Ávila Pires and Csaba Szepesvári. Multiclass classification calibration functions. CoRR, abs/1609.06385, 2016. URL
/1609 06385.
[38] Harish G. Ramaswamy and Shivani Agarwal. Convex calibration dimension for multiclass loss matrices. J. Mach. Learn, Res., 17:14:1-14:45, 2016.
[39] Harish G. Ramaswamy and Shivani Agarwal. Convex calibration dimension for multiclass loss matrices. J. Mach. Learn. Res., 17:14:1-14:45, 2016. URL http::/mmmm r. r..gg/ http:/ppprrrrr///ppppppp/////
v17/14-33 316 html.
12

---

[40] Mark D. Reid and Robert C. Williamson. Composite binary losses. J. Mach. Learn. Res., 11: 2387-2422, 2010.
[41] Clayton Scott. Surrogate losses and regret bounds for cost-sensitive classification with example- dependent costs. In Lise Getoor and Tobias Scheffer, editors, ICML, pages 153-160. Omnipress, 2011. URL https: / http://cc//////////aa/ea /138 1ttpr11811mmmmm icmlpaper pdf.
[42] Eleni Straitouri, Lequn Wang, Nastaran Okati, and Manuel Gomez Rodriguez. Improving expert predictions with prediction sets, 2022.
[43] Ambuj Tewari and Peter Bartlett. On the consistency of multiclass classification methods. J. Mach. Learn. Res., 8:1007-1025, 2007.
[44] Rajeev Verma and Eric T. Nalisnick. Calibrated learning to defer with one-vs-all classifiers, In ICMI., 2022.
[45] Rajeev Verma, Daniel Barrejón, and Eric T. Nalisnick. Learning to defer to multiple experts: Consistent surrogate losses, confidence calibration, and conformal ensembles. In AISTATS, 2023.
[46] Robert C. Williamson, Elodie Vernet, and Mark D. Reid. Composite multiclass losses. J. Mach. Learn. Res., 17:223:1-223:52, 2016.
[47] Guoqiang Wu, Chongxuan Li, Kun Xu, and Jun Zhu. Rethinking and reweighting the univariate losses for multi-label ranking: Consistency and generalization. CoRR, 0ass/205505002 2021.
URL http:: /awxiv.vvvvv.////////..///aaaava wttpaaiwwww.aaaaaaaaaoaaaaaaeaaa httg/bb//... 2105. 05026.
[48] Forest Yang and Sanmi Koyejo. On the consistency of top-k surrogate losses. In ICMI,, volume
119 of Proceedings of Machine Learning Research, pages 10727-10735. PMLR, 2020.
[49] Ming Yuan and Marten H. Wegkamp. Classification methods with reject option based on convex risk minimization. J. Mach. Learn. Res., 11:111-130, 2010.
[50] Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. In BMVC, 2016.
[51] Mingyuan Zhang, Harish Guruprasad Ramaswamy, and Shivani Agarwal. Convex calibrated surrogates for the multi-label f-measure. In ICML, volume 119 of Proceedings of Machine Learning Research, pages 112 11246-11 1255.. PMLR, 2020.
[52] Tong Zhang. Statistical analysis of some multi-category large margin classification methods. J. Mach. Learn, Res., 5:1225-1251. 2004.
13

---

A Proof of Theorem 1
We first prove that if there is an L2D probability estimator v for Lo, then we can reconstruct probability estimator rj for multiclass classification with & if 17 is A which is the collection of all the elements B E A K+1 with 8K+1 2.2 Then show that according to the symmetry of extend this estimator A KK+,, and then construct unbounded L.2D probability estimator for Lg.
Proof. Denote by RI, (u, (2)) Pr(M
- Y|X = =)) E n(x)),( + Pr(M Y|X
z))(u u, K +11 1) the conditional risk for L2D. Denote by a probability estimator for Lg that nj(uu)
(n(;;; Pr(M = Y|X x)] for all u² E argmin, RI (u, m)x), Pr(M Y|X = x)), we can
learn that A x [0, I] is in the range of rj. Then it is easy to verify that rj(u) = 1+ E AK+
5(4)
is valid probability estimator for K + 1-class multiclass classification with if the posterior probabilities [ K+1 is in AK+
Then we construct a valid estimator for A K+1 based on nj. Denote by P a permutation matrix that exchanges the value vector's first and last dimension, then we have the following estimator rj':
(u) = ii(u), uk+1 e maxy ty: (n((Pu) else.
We then prove that it is a valid estimator. Denote by K the set of the B AK+ that 9K+1 # maxy By. we can learn that A K+1 E Á K+1 Then for any B E AK-1, denote by u² the minimizer of conditional risk w.n.f B and ø. we can learn that uk+1 * max, uy due to the consistency of and thus rj' (2") = r7((²) 3.
For any G g A K+1
learn that PB A K+1 Denote by u' the minimizer of conditional risk w.r.t. B and o, then we can learn that Pu" must be the minimizer P3 according to the symmetry of áb Then have that ri ((("")) P3. Furthermore, notice that PP3 = B, then have vj/ "i("") (Pj(Pu") PP3
Combining the two paragraphs above, we can learn that v is valid multiclass probability estimator for Φ Then we can construct an unbounded L2D estimator as in (3), which indicates the existence of an unbounded probability estimator. Furthermore, since the loss function is unchanged, the collection of all the minimizers of Rt, (u, n7x), Pr(M = Y|X = x)) are also unchanged, and thus the all the values should have the same value on U4
B Proof of Proposition 1
Proof. The boundedness of the first K dimensions straightforward. The K + 1th dimension's boundedness can also be directly proved by reformulating
exp(#x+1)
ixp(wk=1++ exp(uy)) max.'c .c) exp(".)))
Then we begin to prove its maxima-preservinn Denote by V1 argmax .K Myy It is easy to verify that vn (u) > (u) for any E (1, KK//nn due to the property of softmax function. Then we focus on the relation between Vay (u) and w (u). We can learn that:
exp(uk=1)
exp(ux+1)+23p -explu)))
2 exple 1 pxxxpt
1+
exp(Uyy) E exp(1)))
14 / saplu,)) expings)
When uk+1 Ug. we learn that Ei -ex(tt))expp(s))))
Σ exp(xx then
exp(#k++1
exp(a))
ΦK+1 (1) Vyn (u). Based on the formulations above, also easy to verify the cases when Uy 2 uK+1- Combining the discussions above and we can conclude the proof.
D
14

---

C Proof of Theorem 2
Proof. The consistency can be directly obtained by recovering the class probability and expert then we first focus on how our proposed estimator
accuracy according to the maxima-preserve recovers the posterior probabilities.
According the property of log loss, it is easy learn that (y = p(ylæ) for y E {1.-.. }. When = K + 1, we can learn from the range of our estimator and the property of binary log loss that (g* Y|X x).
Pr(M = Y|X = z)) Then we can conclude that (x)) = 77))) x Pr(M
Then we begin to prove that there no unbounded probability estimator by contradiction. Suppose there exists an unbounded estimator th. For any 9. it must be the solution of distribution and expert whose posterior probability is (z())) for each point æ. However, for a g that there exists that ())()) & K x [0, IJ. we can learn that it cannot be the solution of any distribution and expert according to the definition of probability estimator. We can learn from this contradiction that a probability estimator as long as its range is not A K x [0,
D Proof of Corollary 1
Proof. We can set the multi-class loss to Φz. to get our proposed loss:
log
exp(u.)
log
Li exp(u,)) expluge)
y # K",
Ey exp(u.))
ma expr..
0 (u, y) =
log
exp(uge)
+ log
exp(uxr)
else.
exp(uy) mawy x11 expuy.
-n' exp(uy) max x! expry
A similar result can be deduced for the OvA-based surrogate by considering the following consistent multi-class loss with strictly proper binary composite loss g:
E(uy) + Ey #y ug u u ((ux)) - ( (x- else.
ΦovA (u, y)
We then begin to prove their consistency. It is easy to verify that 03 minimized when (gg()))) p(y æ) 1-p(K' (m) and we can conclude its consistency using the
property of qb.
For ΦovA, denote by d'OvA the inverse link of g. We can learn that g" (z) = thova ( p(yl())
1-p(K'|ax and
we can learn the consistency since & is strictly proper and thus d'OvA is increasing.
E Proof of Theorem 3
Proof. We first apply Pinsker's inequality. We can learn that:
RI, (g) - Mig 2 Ep(e)) 2 ( (g(x)) - (=))] + 2(xx+1 + - Pr(M- = = = x;)²
We can learn that Rr. (g) R2, Ep(c) (g))) -
immediately and learn that the bound for Roi following the analysis of cross-entropy loss in ordinary classification. Then we move analyze the 0-1 d-eferreraal risk. We can further learn that
RLg (g) - Rig 2 Ep(w)
(=)) 2(xx-1((())) ( Pr(M = Y|X = =x))²
1 2 Bp(on) [1 - ( ())+)((())) - - = x))²
For any æc when g (ax) can induce the Bayes optimal solution for it, the excess risk zero and the
bound holds naturally. When it is not optimal, denote by 7x+1(x) Pr(M = Y|X x). y is the
15

---

Table 2: Experimental results CIFARIOH with for 5 trials. We report the mean % )sstandrd enee)S) of related statistics. The best and comparable methods based on t-test significance level 5% are highlighted in boldface.
Budgeted Error
Method
Error
Coverage
ECE
10%
20%
30%
S-SM
3.82(0.02)
41.28(0.14)
6.64(0.22)
50.25(0.57)
41.00(0.81)
31.47(0..7)
S-OvA
4.30(0.12)
37.08(1.36)
2.46(0.48)
52.75(0.40)
43.31(0.58)
33.23(0.72)
A-OvA
4.00(0.11)
92.75(0.24)
0.95(..16)
4.00(0.11)
4.00(0.11)
4.00(0.11)
A-SM
3.65(0.09)
94.20(0.37)
0.94(0.17)
3.65(0.09)
3.65(0.09)
3.65(0.09)
Table 3: Experimental results ImageNet- 166 with for 5 trials. We report the mean( & Joaundand eneetS)) of related statistics.The best and comparable methods based on I-test significance level 5% highlighted in boldface.
Budgeted Error
Method
Error
Coverage
ECE
10%
20%
30%
Image Noise Type = "080"
S-SM
10.63(1.34)
22.59(1.59
18.31(3.22)
66.58(3.91)
60.41(2.98)
53.33(2.79)
S-OvA
10.48(0.64)
21.88(2.75)
12.79(0.33)
70.50(3.78)
61.58(4.64)
51.22(3.37)
A-OvA
10.36(1.09)
25.86(3.566
8.69(0.63)
70.83(1.25)
61.32(1.70)
52.26(0.95)
A-SM
7.95()
37.32(2.72)
7.39(0.23)
54.24(2.89)
45.33(2.91)
34.11(1.65)
dimension with the largest value of g(x) and that of 17(x) is v². Then we can learn that:
2 IV -
(g(x)) - ( (#x+1(9(z)) Pr(M = YIX = =))²²
(o())) (x) viy (g(x)) (2r) ?
(ny (z) my (x))²
The last step is obtained according to the maxima-preservee property. Further generalizing y and y" to be deeeeneet (y' (æx) and (=)),, we can learn the following inequality using Jensen's inequality:
R (g)
(Bptn)lltr -,y"
which concludes the proof since the second expectation term is Rot (g) R
F
Details of Experiments
Details of Model and Optimizer: For methods on CIFAR-10, we use the 28- Net that is the same as those used in Mozannar and Sontag [30], Charusaie et al. [9]. The optimizer is SGD with cosine anncaling, where the learning rate le-l and weight decay is 5e-4. We conduct the experiments 8 NVIDIA GeForce 3090 GPUs and the batch size is 1024 (128 on each GPU). The training epoch on CIFAR100 is set to 200.
For methods on CIFAR-1OH, we train the same WideResNNt on the fully-label CIFAR-10 10 dataset and then train the linear layer using the CIFAR-10H dataset. The optimizer is AdamW [] and the learning rate, batch size, epoch number are le-4, 128, 200. For methods on HateSpeech, we use 384-dimension embedding and linear model the experiment. The optimizer is SGD with cosine annealing and the learning rate, batch size, epoch number is 0.1, 128, 50. For methods on ImageNet- 16H, we use the embedding generated by the pretrained DenseNet and linear model. The optimizer Adam and the learning rate, batch size, epoch number is 1e-3, le-1, 100.
16

---

The extra result ImageNet with noise type "080" and the exact statistics for CIFAR- 10H are shown in the tables in the appendix.
The reported Error is the sample mean of for and Coverage is the ratio of undeferred samples. The ECE of expert accuracy is defined below:
Details of Evaluation Metrics:
ECE Σ hilps - cal.
where b, is the ratio of predictions whose confidences fall into the ith bin. p; is the average confidence and is the average accuracy in this bin. We set the bin number to 15. The budgeted error is calculated as below: the coverage is lower than 1 x%, we will use the classifier's prediction instead of the expert's for those samples whose estimated expert accuracy is lower to make the coverage equal to x%.
G Limitations and Broader Impact
This work designed for L2D without extra constraints on the number of expert queries. We believe that combining it with selective learning, i.e., adding explicit constraints on the ratio of deferred samples, can be a promising future direction.
Limitations:
Broader Impact:
When applied real-world applications, the frequency expert queries may be imbalanced due to the performance differences of the expert among samples. This is common impact shared by all the L2D methods. believe that introducing fairness targets into L2D can be another promising direction.
H
Consistent Multi-Expert Extension
We provide direct extension of our loss for the multi-expert setting and provide consistency analysis: Denote by the expert advice m (mi,""",m, E y x ... x V. We first define an extended ASM:
Definition 4. (Multi-expert asymmetric softmax parameterization) v is called multi-expert asym- metric softmax function that for any K >> and E IR KM
exp(My)
V K + 1
JM (u)
exp(u,))
(10)
exp(x.)
else.
+exp(( maxy:p "eti.................. ky exp(a,))
We directly extend the property of single-expert ASM this case:
Proposition 2. (Properties giAh For any u E KK+M
(i). (Boundedness) df (u) E
A K x [0,
(ii) (Maxima-preservinggg argmax ye, (I, K+M) J.M (u) = argmax (E,,,-,KKM Ug.
Then we give the following extension: Definition 5. (Multi-cxpert extension)
Lngas (u, y, m) log( (u))
Σ
v k+*(u)) [m, y] log (og(v> (I, + y] log(1
According to the position, can simply give the characterization of Lijar 's optimal solution:
M-m())) = p(y] & 1, K MM, Pr(M x
(11)
else.
According the maxima-presenva directly learn the consistency of our multiclass extension.
17

---

I Estimation Error Bound
In this section, give routine analysis of our method's estimation error bound. Our proof of the estimation error bound is based on Rademacher complexity:
Definition 6. (Rademacher complexity) Let Zi...., Zn be n i.i.d. random variables drawn from probability distribution μu, = {h: + IR be a class of measurable functions. Then the expected Rademacher complexity of H is defined as
R (H) = Ez,
Eg
sup NEA
Σ o (Z,) i=1
where o foI...., On) are Rademacher variables taking the value from [-1,+1} with even probabilities.
First, let X RK+1 be the model class and each of its dimension is constructed by gy & R. Then, we define the following scoring function space for L.2D task:
L g (h (xr, y, m) (g(g( y, m)lg E 9}
So the Rademacher complexity of C 9 given i.i.d. samples drawn from distribution with density p(æ, y, m) can be defined as
o,h(a,, yos mi)
RR (C Ep( B.
sup- DEG m :=1
Denote by Rr. (g) Σ Lz(o(1)), Mi, me) the empirical risk and و the empirical risk mini- mizer. We have the following theorem: Lemma 1.
RE (g) -R2 (g") s sup RR, (g) - RE. (g)
gEg
Proof.
RI (g) Rr, (g") = RR (g) - Rí, (g) + RL, (g) Rı (g")
< RI.g (g) - Rí. (g) + Rí. (g") - Ríg (g
2 sup Nu. (g) Rr. (g)
gEg
which completes the proof.
Then it routing to get the estimation error bound with Rademacher complexity and McDiarmid's inequality:
Theorem Suppose I T,g(g(z),,, m) s M and Lgg L. L.pssite w.r.t. g(x), then with probability least 1 5:
K+1
In ln(2/0)
R1. (g) 10)-R1, Rg < 4V
Rr (G,) + AMV
2n
Proof. We will only discuss one-sided bound on supges (R(gg) R(g) that holds with probabil-
ity at least 2. Altering (zz1), Vi. m.) to (a<1i), 1/. mf) and we can get perturbed empirical risk (g). We can learn that
ssu (K'(g) - R(g)) sup geg
(R(g)) R(g))
< sup gEg
( R(g)
M
gEg
Then we can use Mediarmids' inequality and vector-valued Talagrand inequality to leam:
K+1
In (n(2/)
sup gEg
RLg (g) RR3(2) 22
Σ
R. (G,) + 2M
2n
18

---

Using the lemma 1 and we can conclude our proof.
19


Reviews:
[{"review_id": "iqtLxJaTBy", "reviewer": "Reviewer_Ztxz", "summary": "The paper studies the learning to defer (L2D framework), where one can defer to an expert decision when unsure about the model’s prediction, and a cost is incurred when either the prediction is wrong or when one defers to the expert and the expert makes a mistake.\n\nThe paper builds on top of prior work that shows that softmax parametrization can lead to unbounded probability estimators. While prior work provided a one-vs-all (OvA) formulation to solve this issue, this paper shows that the issue lies in the symmetric nature of the softmax function. The authors then proceed to introduce asymmetry in the softmax function and show that this leads to both bounded probability estimators and improved performance.\n", "questions": "1. How is the learning to defer paradigm comparable to selective classification [1]? In particular, one can integrate the reject option into the classifier. \n2. In the learning to defer problem, a possible generalization is also associating a cost (possibly small) with deferring the prediction, even when the expert is correct, because using an expert instead of the model should be costly and avoided. Curious if any related work has considered this scenario.\n\n\n[1] Yonatan Geifman, Ran El-Yaniv. Selective Classification for Deep Neural Networks. NeurIPS 2017", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The paper is well-written and the idea is somewhat novel.\n2. I enjoyed reading the theoretical analysis in both the main paper and the appendix.\n3. I like how the method do not have a lot of additional hyper-parameters to tune — this makes the method simple and do not feel over-engineered.\n", "weaknesses": "1. Asymmetric softmax functions have studied before, although in a different context. For example, [1] suggests LDAM loss aimed for long-tailed or imbalance datasets. Comparison/discussion with this and possible other asymmetric variation of softmax would be appreciated.\n2. The experiments involve only small-scale datasets like CIFAR-10 and CIFAR-100. While many methods perform well on these, they often do not scale well. Additional datasets would both (1) make the problem setting more appealing and (2) improve the standing of the paper.\n\n[1] Kaidi Cao, Colin Wei, Adrien Gaidon, Nikos Arechiga, Tengyu Ma. Learning Imbalanced Datasets with Label-Distribution-Aware Margin Loss, NeurIPS 2019, https://arxiv.org/abs/1906.07413", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1. The authors should add the comparison/discussion with [1] or any possible other asymmetric variation of softmax.**\n\nA1. Thank you for raising this concern! In this work, the asymmetric softmax is introduced to directly map the scoring function into the desired region $\\Delta^{K}\\cup[0,1]$ while remaining the order of each dimension of the scoring function. In [1], the softmax function is asymmetrized to simulate the trade-off between class margins that exist in imbalanced classification tasks, which can lead to smaller generalization errors if chosen properly. Though the motivations of the two versions of asymmetric softmax are different, they are both based on prior knowledge of the data distribution. In conclusion, introducing asymmetry into the original softmax function can be a promising solution when we are seeking methods to incorporate prior knowledge about data distribution into the learning process.\n\n**Q2. Additional datasets should be added to improve the standing and appealingness of this paper.**\n\nA2. Thank you for your valuable suggestion! To better validate the proposed method, especially on datasets with real-world expert information, we added additional experiments on HateSpeech and ImageNet-16H datasets, which are two datasets with real-world expert annotations, and the detailed information can be found in the one-page attachment.\n\n**Q3. The authors should compare the learning to defer paradigm with selective learning framework.**\n\nA3. Thank you for raising this concern! Learning to defer is a framework that focuses on point-wise rejection: any point whose maximum class-posterior probability is lower than the expert’s accuracy will be rejected. In contrast, the rejection rule in selective learning framework relies on the whole distribution with density $p(x,y)$: given a coverage constraint cov%, the rejection rule should accept the top-cov% samples with the highest maximum class-posterior probability. I think the goals of the two frameworks are not contradictory but complementary, and the combination of the two paradigms can be a promising future direction.\n\n**Q4. The authors are encouraged to give any related work that associates a cost with deferring the prediction.**\n\nA4. Thank you for raising this concern! Associating a cost $c_{0}$ with deferral has been studied in [2, 3], though some of the recent works [4, 5] on the surrogate losses for L2D only focus on the case where $c_{0}=0$. In this case, deferring to an expert will trigger a cost of $c_{0}+[[expert~prediction\\not=y]]$. We find that our proposed method can be generalized to this case where $c_{0}>0$ and we provide the detailed formulation in the answer to question 2 of reviewer jwha. \n\n[1]. Kaidi Cao, Colin Wei, Adrien Gaidon, Nikos Arechiga, Tengyu Ma. Learning Imbalanced Datasets with Label-Distribution-Aware Margin Loss, NeurIPS 2019, https://arxiv.org/abs/1906.07413\n\n[2]. Hussein Mozannar and David A. Sontag. Consistent estimators for learning to defer to an expert. In ICML, 2020.\n\n[3]. Harikrishna Narasimhan, Wittawat Jitkrittum, Aditya Krishna Menon, Ankit Singh Rawat, and Sanjiv Kumar. Post-hoc estimators for learning to defer to an expert. In NeurIPS, 2022.\n\n[4]. Rajeev Verma and Eric T. Nalisnick. Calibrated learning to defer with one-vs-all classifiers. In ICML, 2022.\n\n[5]. Hussein Mozannar, Hunter Lang, Dennis Wei, Prasanna Sattigeri, Subhro Das, and David A. Sontag. Who should predict? exact algorithms for learning to defer to humans. AISTATS 2023: 10520-10545"}, {"review_id": "jQ0Y2c9ApH", "reviewer": "Reviewer_Jwha", "summary": "This paper shows that the miscalibration of the softmax-based surrogate loss for learning to defer is due to its symmetry. Instead, an asymmetric softmax-based surrogate loss is proposed and proved to be both calibrated and consistent. More generally, they reveal the connection between miscalibration and the symmetry of the used loss function and propose to design L2D surrogates based on asymmetric multi-class loss functions.", "questions": "1. Could you give more details on how Definition 3 is derived based on the asymmetric softmax function?\n\nminors:\n1. The notation of the risk is different in Definition 1 from in (1).\n2. At the end of line 97, the transformation should map from R^{K + 1}.\n3. It is better to specify the section when referring to the appendix.", "limitations": "See Weaknesses.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is well-organized and enjoyable to read though the notation is a bit heavy. They not only give a careful analysis of softmax-based loss functions but also provide very interesting insights regarding the miscalibration of surrogate loss functions for learning to defer and the symmetry of the multi-class loss functions they are based on.", "weaknesses": "As stated in the paper, the 0-1 deferral loss studied here is not the most general version. For important settings including where the expert is a bigger model with higher accuracy but larger inference cost than the base model, an additional constant cost is required to reflect the extra inference cost. [31] shows that both [28] and [42] suffer from underfitting if the constant cost is non-zero. I am wondering if the proposed asymmetric softmax-based surrogate loss can be generalized to this setting and if it will have similar issues.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1. Can the proposed asymmetric softmax-based surrogate be generalized to the setting that an additional constant cost will be triggered when the model choose to defer to experts? If such generalization is available, will it have the same issue of underfitting as shown in [1]?**\n\nA1. Thank you for raising this concern! Since our surrogate can be seen as induced from a classification-calibrated multi-class classification surrogate, we can directly generalize it to the case where the additional cost $c_{0}$ is non-zero a based on the Proposition 2 of [1]:   $L_{\\tilde{\\psi}}(u,y,m)=-\\sum_{i\\in[K]}(\\max_{j\\in[K+1]}c(j)-c(i))\\log(\\tilde{\\psi}_{i}(u))-(\\max_{j\\in[K+1]}c(j) -c(K+1))\\log(\\tilde{\\psi}_{K+1}(u)) $. \n\nWhen the expert makes a wrong prediction, i.e., $\\max_{j\\in[K+1]}c(j)=1+c_{0}$, the surrogate can be further written as $L_{\\tilde{\\psi}}(u,y,m)=-\\log(\\tilde{\\psi}_{y}(u))-c_{0}\\sum_{i\\in[K]}\\log(\\tilde{\\psi}_{i}(u)) $. Notice that the second term is exactly a **label smoothing term**, which is potentially the root of underfitting as stated in [1] (in the second paragraph of Section 3.1). Based on this theoretical observation, we can infer that underfitting is likely to occur. I think combining the post-hoc method in [1] and designing surrogates that can be free from such label smoothing terms can be promising future directions.\n\n**Q2. The authors should give more details on how Definition 3 is derived based on the asymmetric softmax function.**\n\nA2. Thank you for raising this concern! To be detailed, we first map the scoring function from $R^{K+1}$ to $\\Delta^{K}\\cup[0,1]$ using the asymmetric softmax function. Then we can train a probability forecaster for classifier and expert accuracy simultaneously by minimizing the risk w.r.t. the sum of a multi-class classification surrogate and a binary classification surrogate, which is exactly Definition 3. The design of $\\tilde{\\psi}_{K+1}$ further binds the score of the deferral function and classifier, which lead to the property of maxima-preserving and ensure the consistency of Definition 3. We will elaborate on this point and add it to the paragraph next to Definition 3 in the future version.\n\n**Q3. There are some minor mistakes to be corrected and the section of appendix should be specified.**\n\nA3. Thank you for your constructive advice! We have revised our manuscript and will correct these clarity problems in the revised version of this manuscript.\n\n[1]. Mohammad-Amin Charusaie, Hussein Mozannar, David A. Sontag, and Samira Samadi. Sample efficient learning of predictors that complement humans. In ICML, 2022.\n"}, {"review_id": "T3ECKeXiAJ", "reviewer": "Reviewer_hiuK", "summary": "This paper studies the learning to defer setup where you have to defer to an expert if the classifier is likely to be wrong. It has been shown that softmax based consistent estimators for the learning to defer losses do not provide calibrated probability estimates for the likelihood of deferring. One other work proposed non-softmax based losses which provided calibrated probability estimates but it is not known if any other softmax based loss can lead to calibrated estimates. This work shows that softmax is not the issue of the lack of calibration but using symmetric loss functions is. This work then proposes a softmax based asymmetric loss function that leads to calibrated and bounded probability estimates. This work also experimentally verifies the effectiveness of using their loss function.", "questions": "In definition 1, R^c loss is not defined?", "limitations": "Yes", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- I find the idea of the paper really interesting. Since softmax based losses are the most commonly used loss functions, it makes sense to be able to use those loss functions for learning to defer framework. Moreover, this work identifies the fundamental issue present in the original loss function which was leading to poorly calibrated probability estimates. I find this insight on using asymmetric loss functions interesting.", "weaknesses": "Right now, the paper sometimes becomes hard to follow as there are a lot of notations used. One thing that could be improved is having a common notation section in the beginning which could be used to look up symbols. Overall, the presentation of the paper could be improved.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1. The presentation should be improved. It is encouraged to add a separated section to introduce the used notations.**\n\nA1. Thank you for your constructive advice! We will summarize the used notations in and add an extra section in the revised manuscript.\n\n**Q2. The R^c loss is not defined in Definition 1.**\n\nA2. Thank you for raising this concern! The $R^{c}_{01}$ should be the0-1-deferral risk instead and we will update it in the revised version of this manuscript.\n"}, {"review_id": "GUx3cYI9C8", "reviewer": "Reviewer_fCzx", "summary": "In this paper, the authors investigate the task of probability forecasting in multi-class classification with an expert deferral option (L2D). They address the issue of unbounded and invalid estimates of experts' accuracy that often arises in probability estimation for L2D. Furthermore, the authors highlight that this problem persists when using a loss function with a symmetric structure, such as the commonly used softmax cross-entropy loss. To overcome the problem of unbounded probability estimates and support the use of softmax parameterization in L2D, the authors introduce a novel asymmetric softmax parameterization. They demonstrate the consistency of the induced loss function and provide theoretical evidence that this loss function will never encounter the issue of unbounded estimation. The authors validate their proposed method through experiments conducted on multiple benchmark datasets, utilizing various evaluation metrics. The experimental results provide justification for the effectiveness of the proposed approach.", "questions": "In Theorem 2, it is proved that the proposed loss will never have an unbounded probability estimator. Though the proof is clear, can you provide a more intuitive explanation of such a positive result?\n\n", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "1.\tThe authors successfully enable the utilization of softmax parameterization in L2D, which is popular but discouraged in previous works. They provide both theoretical and experimental justifications for this approach. The proposed loss formulation is intuitive and straightforward to implement, requiring only the addition of a single output without modifying the scoring outputs of the classifier.\n\n2.\tThe authors present a theoretical analysis highlighting the unbounded nature of symmetric losses in L2D. They demonstrate that the proposed loss function benefits from its asymmetric structure, emphasizing the non-trivial nature of their work.\n\n3.\tThe authors offer theoretical guarantees regarding the proposed loss function, ensuring that it will never produce an unbounded probability estimator. This rigorous analysis eliminates any concerns regarding unbounded behavior in the proposed method.\n\n4.\tThis work includes several figures that effectively compare the proposed method with related approaches. These figures illustrate the issues associated with unbounded probability estimators, providing persuasive evidence to aid readers in understanding the main points of the paper.\n\n5.\tThe authors thoroughly validate the performance of the proposed method using a variety of evaluation metrics and settings. Their results demonstrate that the proposed approach is comparable to, if not superior to, baseline methods not only in the context of probability forecasting but also in predictive tasks without coverage constraints.\n", "weaknesses": "The authors are encouraged to provide a finite sample analysis, specifically an estimation error bound, to complement their theoretical analysis and ensure completeness. Considering that the newly proposed asymmetric softmax parameterization may alter the Lipschitz constant of the score function \"g,\" the estimation error bound becomes a non-trivial aspect worth investigating. Additionally, combining this estimation error bound with the proposed regret transfer bound could potentially yield a more direct and intuitive result.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1. An estimation error bound should be given. The Lipschitzness of the asymmetric softmax w.r.t. g should also be clarified.**\n\nA1. Thank you for your helpful advice! We have derived the estimation error bound of the ERM with our proposed risk and will update it in the revised version of our manuscript. Though our proposed asymmetric softmax takes a different formulation, its Lipshitzness still persists: the absolute value of the partial derivative of $\\tilde{\\psi}_{i}(g)$ w.r.t.gj will not be larger than 1 for any i, j in [1,K+1], which indicates the Lipschitzness of the asymmetric softmax.\n\n**Q2. A more intuitive explanation should be given to Theorem 2.**\n\nA2. Thank you for raising this concern! A more intuitive explanation is that the existence of an unbounded probability estimator will remove some point g(x) from the potential solution. However, since any point can be mapped into the desired probability region with our proposed asymmetric softmax, any point my be the solution of point-wise risk w.r.t. some posterior probability, which leads to a contradiction. This explanation can also be seen as the scratch of the proof for Theorem 2.\n"}, {"review_id": "y8uVlpKO2v", "reviewer": "Reviewer_r3aW", "summary": "This paper considers the problem of learning to defer, and propose a softmax-based surrogate loss for the task, which is consistent and can be well-calibrated. The paper theoretically proves that one needs asymmetric losses for a bounded probability estimate---which in turn leads to a better calibration properties---(Theorem 1), and show the consistency of the proposed loss (Theorem 2). The paper also gives the risk transfer bound to the original zero-one loss (Theorem 3). Empirically, the proposed surrogate function enjoys the best of both worlds, achieving low error rates and good calibration properties.", "questions": "- What is the reason we should prefer softmax-based losses?\n\n- Please provide more experimental results on other datasets.\n\n- Please provide explicit numbers for the CIFAR10H experiments; this is for the sake of checking whether the baselines have been implemented and tuned correctly. ", "limitations": "The limitations are adequately stated in the manuscript, but only in the appendices.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "- Theoretical contributions of the paper is very good. Theorem 1 is a strong result, which may be useful in guiding the design of other softmax-based estimators for nonclassic (e.g., composite) learning tasks. Other two are somewhat standard, but are very essential in guaranteeing that the proposed loss works as desired.\n\n- The proposed asymmetric softmax-parameterized loss is very simply designed. The loss can be implemented very easily and may not introduce too much computational overhead to the training procedure.\n\n- The empirical performance of the proposed loss function is strong, consistently achieving the best performance over the tested setups.\n\n- The paper is very clearly written, especially for a paper that is heavily loaded with various notations.", "weaknesses": "- It is not clear **why** we want to stick to the softmax-based losses from the first place. It is definitely cool that one can give a better calibrated softmax-based loss, but what is the reason that we need one when we have a decent non-softmax loss? We only know post hoc that such estimator has some empirical benefits, but the reason why it works better than non-softmax one is still at mystery. In the manuscript, authors try to justify the effort saying \"Given the wide use and practical advantages of softmax parameterization (...),\" but the reason is never spoken out clearly. For a better understanding of the advantages of the proposed loss, we need a more detailed explanation (or maybe a good reference).\n\n- I find that the empirical validation of the loss function to be somewhat limited. I don't usually ask for more experimental validations for theory papers. However, I think it is quite essential for this paper specifically, because none of the theoretical results actually explain why the proposed loss function should work better than the OvA loss. The main experiments are on the synthetic CIFAR100 dataset, with an additional figure on CIFAR10H (where are the \"error rate\" results for CIFAR10H?). This is very limited; [42] performed experiments on CIFAR10H, Hatespeech, Galaxy-Zoo, and HAM10000; [28] has experiments on CIFAR10H, CheXpert, and Hatespeech. In this sense, having only CIFAR100 results stated explicitly as numbers seems rather inadequate, as we cannot really check whether the baselines have been implemented/tuned correctly.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1. Please provide more experimental results on other datasets.**\n\nA1. Thank you for your constructive advice! We have added more experiments on datasets with real-world expert annotations, including Hatespeech [1] and ImageNet-16H [2] (2 tasks: “080” and “095”). The experimental results are provided in the one-page attachment. According to the results, the performance of our proposed surrogate continues to be comparable to or better than the baselines.\n\nThe detailed experimental setup is provided below. For the model used for Hatespeech and ImageNet-16H, we apply the settings in [3]. The optimizer for Hatespeech is SGD + Cosine annealing is used for all the method for 50 epochs, and the learning rate, momentum, and batch size is 0.1, 0.9, and 1000. For both of the tasks in ImageNet-16H, the optimizer is Adam and the learning rate, batch size, and epoch number are set to be 1e-3, 100, and 100. Training-validation-testing split is set to 7:1:2 for both datasets.\n\n**Q2. Please provide explicit numbers for the CIFAR10H experiments; this is for the sake of checking whether the baselines have been implemented and tuned correctly.**\n\nA2. Thank you for raising this concern! In this main body, we conducted experiments with data from CIFAR-10H only to visualize the result of expert accuracy estimation, and thus the accuracy for all the methods is around 50%, which is far from optimal. To better reflect the ability of expert accuracy estimation of all the methods and evaluate the other abilities at the same time, we conduct additional experiments with both data from CIFAR-10H and CIFAR-10 as in [3]. The new visualization and a table of experimental results are provided in the one-page attachment. The experimental results show that our proposed method still outperformed the baselines. While the new visualization of probability estimation of S-OVA, A-OVA, and A-SM (proposed) remains similar to those in the main body, it can be seen that the estimation of S-SM severely suffers from the problem of unbounded confidence, which again shows the necessity of the study of bounded estimators.\n\nThe detail of the experimental setup is listed below. The choice of model is the same as in [4], while the optimizer is SGD + Cosine annealing. The learning rate, momentum, batch size, and epoch number is 0.1, 0.9, 128, and 200. Training-validation-testing split is 7:1:2.\n\n**Q3. What is the reason we should prefer softmax-based losses?**\n\nA3. Thank you for raising this concern! In the task of ordinary multi-class classification, softmax-based loss functions, e.g., softmax cross-entropy loss, are the most widely used losses to train DNNs due to its superb performance. This is because the softmax parameterization can naturally model the K-dimensional probability simplex. However, the methods based on binary classification reduction, e.g., one-versus-all, fail to achieve this property. According to the resemblance between the task of multi-class classification and learning to defer, it is reasonable to infer that softmax-based losses could persist its advantage in L2D if implemented properly. The additional experimental results also strengthen the validity of this reason. As a result, we conclude that in the field of L2D and its probability estimation, the softmax-based losses should not be discouraged, and it is encouraged to give priority to the use of it as in the multi-class classification task.\n\n[1]. Davidson, T., Warmsley, D., Macy, M., and Weber, I. (2017). Automated hate speech detection and the problem of offensive language. In Eleventh international aaai conference on web and social media.\n\n[2]. Kerrigan, G., Smyth, P., and Steyvers, M. (2021). Combining human predictions with model probabilities via confusion matrices and calibration. Advances in Neural Information Processing Systems, 34.\n\n[3]. Hussein Mozannar, Hunter Lang, Dennis Wei, Prasanna Sattigeri, Subhro Das, and David A. Sontag. Who should predict? exact algorithms for learning to defer to humans . AISTATS 2023: 10520-10545\n"}]

Author rebuttal:
## General Response

We thank all the reviewers for their valuable comments and devoted time. We are glad that all the reviewers praise the insight and theoretical contribution of this work. We are also encouraged that the reviewers find this work easy to use (Reviewers Ztxz, r3aW), and appreciate the clarity of this paper (Reviewers Ztxz, fCzx, jwha, and r3aW).

We respond to each reviewer's comments in details, respectively. An additional pdf file that includes one figure and three tables is provided to further experimentally validate our method and support our claims in the responses. In the revised version, we will update the manustript according to reviewers' suggestions. We believe this will definitely enhance the quality of this work. 

Meta-review: This paper addresses the open problem [42] of if there exists a well-calibrated softmax-based surrogate loss for learning-to-defer.  This paper demonstrates that the problem in the traditional softmax parameterization is due to symmetry, and a reasonable asymmetric version is proposed (that essentially applies a traditional softmax to the class dimensions and a map to [0, 1] to the defer dimension).  All reviewers have positive opinions of the paper, unanimously recommending acceptance.  

Two good criticisms were put forward that the authors should take care to address in the camera-ready version.  The first is the need to have a softmax-based surrogate in the first place, as just because it is the default parameterization in deep learning does not mean it needs to be the default parameterization for multi-class learning-to-defer.  The authors provide a good rebuttal that the softmax can potentially provide probability estimates for all classes, whereas one-vs-all is unconstrained across classes.  I think this point and other motivations could be made more prominent in the draft (while simultaneously not leaving the reader to think the softmax will always dominate one-vs-all).  Secondly, Reviewer r3aW makes the good point that this paper's experiments are lacking compared to peer learning-to-defer papers.  The authors have promised to include experiments on HateSpeech and ImageNet-16H---as they should be sure to do.

My own question: can this loss be straightforwardly extended to the multi-expert setting, as the (symmetric) softmax seems to be an even bigger problem for calibration there [43]?  If so, then the authors should add the result at least to the appendix, as people might also be interested in the proposed fixed for the multi-expert setting.  If it is not obvious, then the authors should state this as an open problem / area for future work.
Decision: Accept (poster)