Generalizing Consistent Multi-Class Classification with Rejection to be Compatible with Arbitrary Losses
Authors: Yuzhou Cao
Tianchi Cai
Lei Feng
Lihong Gu
Jinjie GU
Bo An
Gang Niu
Masashi Sugiyama
Venue: NeurIPS 2022 Accept (2022)
Keywords: classification with rejection
arbitrary losses
multi-class classification

Abstract: \emph{Classification with rejection} (CwR) refrains from making a prediction to avoid critical misclassification when encountering test samples that are difficult to classify. Though previous methods for CwR have been provided with theoretical guarantees, they are only compatible with certain loss functions, making them not flexible enough when the loss needs to be changed with the dataset in practice. In this paper, we derive a novel formulation for CwR that can be equipped with arbitrary loss functions while maintaining the theoretical guarantees. First, we show that $K$-class CwR is equivalent to a $(K\!+\!1)$-class classification problem on the original data distribution with an augmented class, and propose an empirical risk minimization formulation to solve this problem with an estimation error bound. Then, we find necessary and sufficient conditions for the learning \emph{consistency} of the surrogates constructed on our proposed formulation equipped with any classification-calibrated multi-class losses, where consistency means the surrogate risk minimization implies the target risk minimization for CwR. Finally, experiments on benchmark datasets validate the effectiveness of our proposed method. 

Generalizing Consistent Multi-Class Classification with Rejection to be Compatible with Arbitrary Losses
Yuzhou Caol*
Tianchi Cai Lei Feng Lihong Gu
Jinjie Gu Bo An
Gang Niu Masashi Sugiyama
School of Computer Science and Engineering, Nanyang Technological University, Singapore Ant Group, China
College of Computer Science, Chongqing University, China "RIKEN Center for Advanced Intelligence Project, Japan Thhe University of Tokyo, Japan
Abstract
Classification with rejection (CwR) refrains from making a prediction avoid critical misclassification when encountering test samples that are difficult to clas- sify. Though previous methods for CwR have been provided with theoretical guarantees, they are only compatible with certain loss functions, making them not flexible enough when the loss needs be changed with the dataset in practice. In this paper, we derive novel formulation for CwR that can be equipped with arbitrary loss functions while maintaining the theoretical guarantees. First, we show that K-c K-class CwR is equivalent to (K 1-class classification problem on the original data distribution with an augmented class, and propose an em- pirical risk minimization formulation to solve this problem with an estimation error bound. Then, we find necessary and sufficient conditions for the learning consistency of the surrogates constructed on proposed formulation equipped with any classification-caiibee
multi-class losses, where consistency means the surrogate risk minimization implies the target risk minimization for CwR. Finally, experimental results validate the effectiveness of our proposed method.
Introduction
In risk-sensitive multi-class classification applications (e.g., medical diagnosis, healthcare, au- tonomous driving, and product inspections [13, 22, 44]), misclassification can cause serious or even fatal consequences. To alleviate this issue, many studies have been conducted on classification with rejection (CwR) [11, 63, 13, 14, 16, 22, 52, 48, 44, 8J, which can abstain from making an unsure prediction to prevent such critical misclassification.
Most of the previous studies follow the framework that provides the reject option with pre-defined cost e which is lower than the misclassification cost 1. Given cost c, the problem is further formulated risk minimization problem that aims to minimize the expectation of the zero-one-c loss, i.e., the zero-one-c risk. With the risk minimization process, the obtained classifier can balance the cost of rejection and prediction by choosing incur rejection cost c if the misclassification risk is high.
Due to the discontinuous nature surrogates to make the optimization problem tractable. A basic requirement for surrogate losses the consistency [65, 7, 54, 47], i.e., the surrogate risk minimization implies the zero-one-c risk minimization. Moreover, compared with the traditional K K-class classification task where decisions
zero-one-c loss, recent works focused on finding its continuous
Work done when Yuzhou Cao was a research intern at Ant Group.
I Corresponding author: Lei Feng <lfeng equ.edu.en>
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Convergence (Th. 3)
Calibration (655, 54,
Equivalence (83)
Empirical Minimization min, R (g)
Surrogate Minimization
60s Consistency
Consiiseiyy ming Ry o g)
Equality (Th. 2)
ming R&g (g)
ming Rox (p v g)
Figure 1: Overview of the construction of consistent surrogates for classification with rejection in this work.
are normally made from the index of the maximum coordinate of a K -d-dmensional scoring function, the design of decision criteria in the CwR task more elusive due to the existence of reject option. By adopting different classification and rejection criteria, various surrogates of the zero-one-c loss have been proposed with consistency analyses [6, 63, 13, 14, 48, 44, 8].
Classical studies focused on developing confidence- based methods[6, 63, 48, 44], which use the outputs of classifiers as confidence values and set a real-valued threshold the rejection rule. Representative methods [63, 44] used surrogates that depend on class-posterior probability estimation (CPE) [50, 58], which is challenging when using deep models [25]. Though some of them [6, 48, 35, 24] could avoid CPE, most of them applied the modification of non non-differentiable hinge/ramp- surrogates, and their performance was only validated with linear models.
To avoid the use of the confidence threshold, Cortes et al. [13] provided an upper bound of the zero- one-c loss as the surrogate that allows the use of separated rejector and can be trained simultaneously with the classifier, which is regarded as classifter-reeector methods. Though these methods achieved otate-of-the-art performance in binary classification scenarios, they only provided consistency guarantee for hinge-like and exponential losses and cannot be directly generalized to the multi-class scenario as shown in Ni al. [44]. Charoenphakdee et al. [8] showed that K-class CwR can be decomposed into K binary cost-sensitive classification problems [17, 12] and proposed a family of surrogates are the ensembles of arbitrary binary classification losses, which can avoid CPE and the use of confidence threshold with properly chosen losses when the cost function is constant. Mozannar and Sontag [41] provided modified version of the cross entropy loss as the surrogate for the task of learning to defer [41, 42] that can also be used in CwR, while its optimal solution still relies on CPE, In summary, previous works only took limited types of losses into consideration, and there lacks a theoretically grounded framework that can cover all the surrogates used in multi-class classification.
In this paper, we propose a novel framework for CwR that allows the use of arbitrary surrogate losses used in traditional multi-class classification as long as they are classifiation-calibree but not limited the well-known cross entropy loss, mean absolute error, focal loss [33, 9], and the wwwwwii//oeeeerssssssee
including
generalizations of binary margin losses [65]. Thanks to the flexible choices of losses, we are free of the restricted analyses on the consistency of certain surrogates. The access to full range of surrogates also make it possible to custom the loss contingent on the characteristics and actual requirements of different datasets and tasks. An overview of our framework is shown in Figure 1. We summarize the main contributions of this work as follows:
We disclose the equivalence between K -claass CwR and a (K+1)-clas classification problem the original data distribution with an augmented class, by showing the equality between their classification risks.
We propose a formulation of surrogates for tuze that can recover the surrogate risk of a classification task only with the K -laass training distribution, and derive an estimation error bound for its empirical risk minimization.
We find a sufficient condition for the consistency of the proposed family of surrogates w.r.f. the zero-one-c loss that allows the use of any calibrated multi-class surrogates and show its necessity when considering a large family of loss functions.
We for the first time provide analysis the calibration of the generalized cross entropy loss [66] that benefits from both the cross entropy loss and mean absolute error, and experimentally demonstrate that it is suitable for our proposed framework.
2 Preliminaries
In this section, we provide preliminary knowledge of CwR and calibrated surrogate losses, and discuss the consistency in CwR.

---

2.1 Classification with Rejection
The problem setting of CwR is based on the cost-based framework [11]. Let us denote by X' the feature space, 3/ = 21.2..... }} the label space, and ) = 21. K, @ the label space with a reject option. We are given instance-label pairs {(z,, yt) independently and identically drawn from underlying distribution with probability density p(ær, y). The goal of CwR is to train classifier f : X y that can abstain from making a decision, where @ denotes the reject option. The evaluation metric of this task is the zero-one-c loss Lpic. which can be expressed as variant of the traditional zero-one loss for (f()))))))) v) [f(x) fyl:
{ [f((x) + vl.
[(x) = @ f(x) E {1,2..... k}.
(f
where [:] is the Iverson bracket notation suggested by Knuth [29] and the cost can be further extended to an instance-dependent function c(x). Our goal is to train a classifier that can minimize the expectation of loie over the data distribution:
Roie(S) =
Let us denote by f argmin, RRore(f) the Bayes optimal solution and ()x)) {p(y|=)}{ the posterior probabilities. When evaluated by lote. a classifier receives standard classification error in {0. 1} if it makes a prediction and cost of e if it does not make a prediction (i.e., chooses the reject option). Intuitively, an optimal solution f should balance the possibility of misclassification and the rejection cost c. This explanation is theoretically justified by Chow's 's rule [11]:
Definition 1. (Chow's Rule) A classifier f X xx> the optimal solution of (1) if and only if meets the following condition almost surely:
maxy (x) S - c,
f(x)
argmax, (x)), else.
Chow's rule shows that the optimal solution should refrain from making a decision if the most confident prediction of an example is still not confident enough given a rejection cost c.
2.2 Calibrated Surrogate Losses
Most classification problems can be formalized as the minimization of the target risk, which is the expectation of a target loss. Then empirical risk minimization (ERM) is conducted obtain models with performance guarantees. However, most of the target losses are discontinuous, e.g., the zero-one loss in multi-class classification and the Hamming//anking loss in multi-label classification [20]. Therefore, directly optimizing them is usually difficult and even NP-hard [18].
In order optimize the target risk efficiently, surrogate risk minimization is preferred that minimizing the expectation of a continuous surrogate loss instead, e.g., the hinge loss in binary classification and the cross entropy loss in multi-class classification. For the statistical consistency of learning, calibration [53] is considered as a basic requirement for surrogate losses, which is a pointwise version of consistency and means that the minimization of the surrogate loss yields that of the target loss for each possible sample. A commonly adopted definition of the calibration of surrogates in multi-class classification is given as follows:
Definition 2. (Cor -alibbbbroaioonn 54, 47J) For K-class classification problem with target loss cor,
we say +b RKK x y + R4 is for calibrated if for any p e A
inf HERK K gargmin, pd (1))
p (' > inf p ((u),
HERK"
where (u) {u w) )) Loi {foi murgmaxyeey,, v) j y=1
The definition of fuz callibbratto requires that a surrogate loss should be able to distinguish between optimal solutions and non-optimal ones w.s. any potential posterior distribution p. This property is shown to be a necessary and sufficient condition for the statistical consistency of surrogate risk minimization, and fruitful research on the verification of for callibrrat surrogates has been conducted [7, 65, 54, 47, 46, 19].
3

---

Table 1: Comparisons between our proposed method and previous works of multi-class classification with rejection. Since our method induced from a (K+ -classss classification problem, we can render consistent learning guarantee with arbitrary surrogate losses that are calibrated w.tl the zero-one loss. Thanks to the abundant choices of losses, our proposed method can avoid CPE and the use of confidence thresholds.
Methed
CPE-Free
Instance-Dependeed Dependent Cost
Confidence Threshold-Free
Arbitrary Losses
[48]
[44]
[41]
[8]
Proposed
Besides multi-class classification, the calibration of surrogate losses also has been studied in various aspects of statistical learning. including but not limited to, multi-label classification [20, 64, 30, 59], AUC optimization [21, 39], general linear-fractions fractional utility maximization [3], cost-sensitive learning [12, 51], top-K classification [32, 62], and adversarially robust classification [4, 2, 1].
2.3
Consistency in Classification with Rejection
In the field of CwR, we are also interested in the consistency of surrogate losses. Let C IR where d E N and Φ C ) R+ is surrogate loss, the consistency is defined as follows:
Definition 3. (lu--sonssst))c)) A surrogate loss & C y + E, is consissnnttt if there exists function ip : + y for all probability distributions and all the sequences of functions (gi X C:
(g) + Rit + -ooeel o g:) + Hoies
where (g) = Ep(...) ((g(z), y),, R = inf (g). and Riie inf Roie(f). f-x+y
g:X
This definition is inspired by the problem of general multi-class classification [47]. For an lote- consistent surrogate loss b we can safely minimize the surrogate risk R& instead while retaining the consistency guarantee of Rote-
To ensure the consistency of ④, it routine to discuss the calibration of surrogate losses. However, unlike the classical multi-class classification problem, where yo is usually an argmax operator, the design of yp for CwR can be quite complicated and hard to be unified, which makes it difficult to directly do calibration analysis on ④b The flexibility of o also limits the discussions to specific types of surrogate losses. In Ramaswamy et al. [48], the authors considered the multi-class extensions of the hinge-loss with confidence threshold. Ni al. [44] indicated that the confidence-basee baaed method is indispensable and only focuses on class probability estimation via surrogate risk minimization. Both of Mozannar and Sontag [41] and Charoenphakdee al. [8] gave surrogate losses for the zero-one-c loss that does not depend on the accurate estimation of the class probability, while Mozannar and
Sontag [41] focused variant of the cross entropy loss and Charoenphakdee al. [8] constructed calibrated surrogate losses with the ensemble of K calibrated losses for binary classification.
In this paper, instead of directly discussing the calibration of surrogate b show that there is an equivalence between classical multi-class classification and CwR. Based on this equivalence, we show that is sufficient for & be foo-scons by letting it be simple variant of any calibrated surrogate loss w.r.. the traditional zero-one loss for The comparison of the proposed method and related works is shown in Table 1.
3 Equivalence between Classification with Rejection and Ordinary Classification
In this section, we first show that the risk Roie(f) can formalized as (K+1)-class classification problem, and show that we can obtain foie-consistent surrogates with variant of any calibrated surrogate w.r.t. f01, which enables the use of c KK+ and =(())=agmax(( as in the traditional multi-class classification tasks. We also show that such equivalence also holds when the cost

---

depends on sample æ. The proof of the conclusions in this section can be found in Appendix A. We
start by considering the following distribution De over X' y with probability density p(æ: f)):
Definition 4. -Self-Augmented Distribution) A distribution De is called a c-self-augmented distribu- tion w.r.t. D if its probability density meets the following conditions:
pla.v (1-cppte) 2-c
V f1.2...... K}. @.
p(x, 9)
It can be seen that distribution D shares the same marginal density of x as the original distribution DD while De has an augmented class @ with class probability determined by the rejection cost c. further explore the relation between the two Based on the connection between D and D, tasks: classification on ee and CwR on 'D Theorem 1. For any classifier
X + y the following equation holds:
R Role (2 - c) (Ro Rāi)
where Roi(f) = Bp( (f(x)) 7)] and Rū = fxx--- Roi (f).
Theorem reveals the equivalence between the two tasks in straightforward manner. Since the multiplication of the classification risk on Ded with a positive constant is equal to Roie(f), the minimization of Roi (f)) immediately yields the minimization Roic(f) (f) and vice versa. Furthermore, according to the linear correlation between Roi (f) and Rote(J), we can directly quantify the excess error (f) Roie by bounding Roi (f) - Röi. which is an easier work thanks to the existing research of multi-class classification. In conclusion, risk minimization with Roi (f) can also give classifier with a rejection option with the optimality guarantee, and then we can consider a surrogate risk minimization problem for multi-class classification instead of CwR.
When the cost c(æ) an instance-dependent function, we show that such equivalence still holds with minor modification. Considering the reweighted zero-one loss: fo (f(=), v) = (2- (2-c(2) (f) # yl and its expectation Roi(J (f) on D we have the following conclusion:
Corollary 1. For any classifier f X )d the following equation holds:
Roi(f) Ro1 = (f Rije-
It is obvious that Theorem I is a special case of Corollary 1 with constant cost functions. Though here we consider a reweighted classification task, the calibration result of multi-class surrogate losses can still be applied without any modification since the minimization of Roi (f') can be seen as ordinary classification risk minimization with a slightly different marginal density p' (xx), which does not affect the calibration result since the class-posted cusss-pottrrio possibilities remain unchanged. All the conclusions in the rest of this paper can be extended to the scenario of instance-dependent cost (see Appendix G).
Cnie-Consister Surrogates with Arbitrary lo Callbbbbedd Losses
As discussed in Section 3, CwR can be safely replaced by multi-class classification on special distribution _ Following the surrogate risk minimization in multi-class classification, we can replace the zero-one loss Luz with surrogate risk & RK+1 x y PU(K + 1} - R. and minimizing the surrogate risk with a score-based classifier
R K+ +1 instead, which is defined as follows:
Ro (g) = E T (gg(x)) t())),
where t(Ø) = - @ and t(ū) = ÿ otherwise. (3) is a typical formulation of the multi- class classification risk and asymptotically minimize it following the ERM framework [55]. After the risk minimization process, the prediction is generated with the following link function IRK+ + "F
R
argmax uy(x) K + 1, ve>u(K+1) else.
(
argmax uz( (E>U(K+1)
5

---

With a ceatfficattio-ccaibrrate surrogate D, it is sufficient to say that the minimization of (g) can lead to that of Roi (f(g)), which indicates the minimization of Roi ())) according to Theorem 1 and Corollary 1. The theory of how to find such surrogates has been thoroughly studied in the field of the clasifficatonn-calibatiio of multi-class surrogates [65, 54, 47].
However, we do have direct access toward De though it closely related the available data distribution D. In this section, we propose family of surrogate losses based on the conclusions in the previous section, which allows the use of any multi-class classification surrogates. With this formulation of surrogates, we can recover the classification risk of R& (g) without access to D by taking its expectation in 'D. Based on the loss formulation, we also provide the estimation error bound show the validity of ERM.
4.1 Formulation of Surrogates
Here, we begin with the definition of a family of surrogates for the zero-one-c loss, and then show how it can relate D and D With any multi-class classification loss Φ, we have the following formulation of surrogate losses for toie:
Definition 5. Given pre-defined rejection cost c, we have the following formulation of surrogate L R K+ x + R2 for CwR:
L. (u, v) Ou, v) + -1 (1- c) K 1),
where + RK++ x YU + R. and E BRR
The proposed surrogate loss is the linear combination of a (K +1) dimensional multi-class classifica- tion loss with coefficient determined by the predefined cost c. can also be learned from Appendix A.2 of Charoenphakdee et al. [8] that when & is the softmax cross entropy loss, (4) is equivalent to
Mozannar and Sontag [. The following theorem reveals the connection between Rg (g) and the expectation L on D:
Theorem 2. For any g X RK+1 and RL (g) pp(z.)) |4 (g(x). v)]:
R = (g)
The proof is provided in Appendix From Theorem 2, we can obtain the risk (g) without access to De with the use of the proposed surrogate (4). Following the common practice, we can finally conduct ERM [55] that minimizes the unbiased estimator of R1 (g), which is also that of R4 (g) according to Theorem
Ri (1)= ==1
-
TM La (g(x:),
(5)
After minimizing Ri (g) and obtaining the empirically optimal 9, we can use for predicting with the link function o 9. where yp g(x) = =()(x))).
According to the unbiasedness of (3), it is promising that the induced prediction rule 9 can approximate Chow's rule (Definition 1). To quantify such approximation, there remains two questions: what the relation between the minimization of empirical risk RLS (g) and R2 (g); and whether the minimization of R (g) yields that of Roiely o g). We will answer the two problems in Section 4.2 and Section 5, respectively.
4.2 Estimation Error Bound
In Section 4.1, we proposed a family of surrogates that can recover the surrogate risk on D. with only D and provided an ERM framework learn the empirically optimal å mingeg RL (g). Here we further justify the of ERM by showing that the minimization of H2 can also result in that of R1 with the following estimation error bound.
Theorem 3. For any E (0, 1). suppose the model class of 9y is Gy and G. where Gy C + +R
and G X + B K+1 is composed of [ ((,, y) is p-Lipschitz continuous and is bounded

---

by Cp > 0. Assume that the identifiable condition holds, i.e., mingeg R Rig. then the following inequality holds with probability at least 1 - 6:
a (g) - : S 4V2(2 - c)p Σ Nn (9,) + (2 (2- (2 2 log 2/5 where (G,
(6)
(9.) is the Rademacher complexity [5] w.r.t Jy on the distribution with density p(æ) that often decays in the rate of O
We prove this conclusion in Appendix C. From the theorem above, we can learn that with the identifiable condition which is a common assumption with the use of complex models [4, 27, 34], R (g) converges R7 in Op(1/vTi) which is the optimal parametric convergence rate without
additional assumptions [38]. According to Theorem 2, it is straightforward that R4 (g) also holds. Nevertheless, the relation between the minimization of surrogate risk R4g (g) and that of the target risk Roi (f o g) still unknown. According to Theorem 1, the minimization of R0i (fp g) is equivalent to zero-one crro-one-caa risk minimization, which is the goal of CwR. We answer this question in the next section by giving sufficient condition for the consistnyyyy for L
5 Theoretical Analysis
In this section, we first point out the sufficient condition for L to be Calibraiddd and show that also necessary if the candidates of & are permutation-invariant, which consists of large number of commonly used loss functions, including but not limited to cross-entropy loss, focal loss, and mean absolute error. Then further specify the regret transfer bounds for family of CPE-free surrogates [66]. which has not been provided with theoretical analysis before.
5.1 Necessary and Sufficient Conditions for Con-SSnnsyy
Given the loss formulation (4), natural idea is to construct surrogate L with commonly used multi-class loss functions. Here, we justify this idea by showing that we can borrow the calibration analyses of multi-class surrogates and set & to any (K 11lclss fgi-calibrated surrogates according to the following conditions:
Theorem 4. L is fonsicsnn for any E [0. 1] if is an for calbbbabdd surrogate loss. Fur- thermore, if & is permutation-invariian i.e., ((Pg) = (b(g) for permutation matrices P, 4's fol-calibration is also necessary for the foi-cconsyy of T.
The complete proof is shown in Appendix D and here provide its sketch. The equivalence between CwR and multi-class classification on Ded shown in Theorem 1, 2, and Corollary directly yields the sufficiency of this condition. Though the equivalent classification problem is limited on D the permutation-ine -nnvaiaaioonnnaaiinneeee of and the arbitrariness of e require that the minimizers of the expectation of & should be included in that of f0r for any potential distributions, which indicates the necessity of 4's calibration.
As result, only have to check if O is Col-calibrated, which has been studied thoroughly [7, 54, 47], instead of tedious case- based discussions. It is noticeable that when considering multi-class surrogates that not cermutationiinvatii that are not calibrated and not permutation-invartt classfication-caaliraee surrogate t can always be a safe choice given the sufficiency in Theorem and fruitful calibration analyses.
use any & in an off-the-shelf manner, i.e., to the consistency of different -
the calibration of 4 may not be necessary, which indicates that surrogates may also be potential options. Nevertheless,
5.2 Calibration Result for Generalized Cross Entropy Loss
Given the sufficient condition for fone-consss,,n we can construct L with any cal-calibr surrogates. However, it has been shown in Charoenphakdee et al. [8] that it can lead to model that rejects more data than necessary if the cross entropy (CE) loss used as $ which is a popular choice as surrogate. Another common surrogate is the mean absolute error (MAE). Though it can avoid CPE and only focus on the crucial class with the maximum posterior probability, usually takes more training epochs before convergence [66], which can be costly in practical use.
7

---

Here, we consider the generalized cross entropy (GCE) loss [66] that can take the advantages of the CE loss and MAE, which is defined below: Definition 6. (Generalized cross entropy losses) For any 7 (0, 1]. the GCE loss is defined as below:
+ (g(x)) v) = -0))))/
where S()) is the softmaxxtransformaaiion
and is also reported in Zhang and Sabuncu [66] that the GCE loss can approximate the CE loss if - 0. Though the GCE loss has proved be effective in practical use, to the best of our knowledge, its calibration results remain unknown. To justify the combination of GCE loss and L we give the calibration analysis and further show its analytical solution.
can be seen that the loss formulation is equivalent to MAE
Theorem 5. The GCE loss Φ> is fo1-cott calbbbabb for any 7 (0, For the optimal model my for all the a E X almost surely if y E (0,1). If y
g. S(g)), ((g Jargmax, 1.
Thy 1-
The proof can be found in Appendix E. After verifying the calibration result of the GCE loss. we can combine it with the loss formulation L and obtain an fo1. consistett surrogate. We will experimentally demonstrate effectiveness the next section.
Experiments
In this section, we provide the experiment results of CwR with deep models, which are evaluated by the zero-one-c loss following the common practice [44, 8]. We also show the misclassification rate of the accepted data and the ratio of the rejected data. Details of the setup and the experiments for instance-dependent cost can be found in Appendix F and G, respectively.
Datasets and Models. In the experiments, we evaluate the proposed methods and baselines on three widely-used benchmarks Fashion-MNIST [60], SVHN [43], CIFAR-IO [31] with cost e selected from {0.05, 0.06, 0.07, 0.08, 0.09, 0.10} for Fashion-MNIS other two. We conduct data augmentation for CIFAR- 10 and use the original datasets of Fashion- MNIST and SVHN in the experiments. For Mushion-MNISTY we
and {0.05, 0.10, 0.15, 0.20, 0.25, 0.30} the
CNN defined in Charoen- phakdee et al. [8], and ResNet- 18 and ResNet-34 [26] are used for SVHN and CIFAR-10, respectively.
Baselines. We compare method with saate-ofthe-ae methods in CwR, including confidence- based cross entropy loss (CE) [44], learning to defer (DEFER) [41], and cost-sensitive barning-basee method with sigmoid loss (CS) [8]. in which DEFER is a special case of our method that use cross entropy loss as Φ. For CE. we also conduct the temperature scaling [25] to alleviate overconfidence. For the proposed method, and Sabuncu [66] and pairwise-sigmoid (Sigmoid) loss [65] to construct the surrogate L. We implemented all the methods by Pytorch [45], and conducted all the experiments on NVIDIA GeForce 3090 GPUs.
GCE with default parameter 7 0.7 suggested in Zhang
Experimental Results. As can be seen from the experimental results reported in Table 2, our proposed method (i.e., either GCE or Sigmoid) significantly outperforms other compared methods in most cases. Obviously, for all the datasets and cost c, our GCE method outperforms the baseline DEFER method, which indicates that CwR cannot be simply solved by the methods used for learning to defer. It can be also seen that confidence-basee CE is only comparable to the proposed method on FMNIST with a simple CNN. When complex models are used, the effect of overconfidence is inevitable even with the use of temperature scaling, which can be induced from the fact that CE often rejects less data than GCE on SVHN and CIFAR-10. Though CS is comparable to GCE on CIFAR-10 when the rejection cost is high, its performance degrades drastically when the rejection cost decreases, which shows that it is not the best choice in highly error-critcall tasks. When ResNet- 18 and ResNet-34 are used on SVHN and CIFAR- 10 respectively, our GCE method outperforms or is comparable to all the baselines, which shows that GCE is more stable on complex models. Our proposed Sigmoid method performs better than most baselines and is comparable to CE with the use of simple CNN model, which aligns with the existing observations that pairwise losses
8

---

Table 2: The mean and standard error of the zero-one-c losses (0Ic, rescaled 0-100), rejection ratio (Rej), and missclassification rates (01) of the accepted data for trails. The best and comparable methods based on the paired I-test at the significance level 5% are highlighted in boldface.
Mathol
Cost
Cs
DEFER
GCF
Sigunei
Rej
01c
Rej
Rej
Rej
01c
Rej
0.05
(0.17)
2.30
(3.17)
25.17
(0.11)
1.39
(0:25)
2.93
(1.94)
34,95
(0.48)
1.81
(0.25)
3.79
50.66]
(2.51)
(0.40)
2.58
(0.17)
3.22
(2.49)
50.47
(0.30)
1.39
(0.01)
2.23
(0.62)
30.96
(0:05)
0.99
2.58
22:92
1,56
3.37
33.13
2.07
4.63
56.45
2.84
3.78
$0.46
1.53
2.62
26.76
1.37
0.06
(0,77)
(1.45)
(0.09)
(0.15)
(1.27)
(0.25)
(0.10)
(1.69)
(0.42)
(0.17)
(1:34)
(0.30)
(0.08)
(1.37)
(0:21)
FMNIST
0.07
2.73
21.17
1.58
3.45
35.77
1.67
5.18
(6.85)
56.46
2.85
4.25
48.05
1.66
(0.07)
2.91
29,87
1.21
135
4.13
33.08
2:17
5.86
54,08
3.36
1.55
3.14
26.10
(0.11)
(1.68)
(0.07)
(6)
(0.92)
(0:52)
(B.
(3,47)
(0.29)
(0:06)
(2.36)
(0.25)
(0.17)
(0.23)
(0.25)
0.09
(0.21)
3.55
(1,82)
23.64
(0.18)
1.86
(0.21)
4.20
(1.74)
31.90
(0:15)
1.96
(0.40)
6.31
(4.55)
54.62
(0.49)
3.09
(0.16)
4.95
(1.74)
$4.05
(0.25)
1.77
(0.05)
3,50
23.71
(.28)
(0.18)
1.79
0.10
(0.16)
3.59
(1.56)
18,32
(0.32)
2.15
(0.30)
4.45
(0.13)
28.96
(0.44)
2.18
(0.07)
6.72
(0.74)
$2,69
(0.18)
3,08
(0.25)
5.06
(4.87)
39.01
(0.26)
1.89
(0,05)
3.73
23.96
(1.90)
(0.20)
1.76
0.05
(0.14)
14:37
3,05
(0.13)
4.42
12.81
(0.12)
4.53
(0.29)
(1.59)
33.05
(0.72)
19.79
(0.24)
2.10
(0.14)
2.70
(111)
29.56
(0.17)
0.10
(0.20)
4.66
(0.57)
10.91
(0.21)
4.01
(0.14)
4.48
(0.42)
12.85
(0.11)
3.67
(0.56)
5.55
(2.64)
30.73
(0.52)
3.58
(0.11)
4.13
(0.54)
14:83
(0,10)
3.10
(0.39)
4.13
(1.94)
19.16
(0.43)
2.74
SVHN
0.20
0.15
(0.09)
6.16
5,40
(0.15)
7.74
8.52
(0.07)
4.50
4.99
(8.20)
(0.10)
5.51
5.14
(1.03)
(0.62)
12.76
13.21
(0.1
(0.24)
3.19
3.64
(0.21)
6.37
5.99
(0.51)
21,19
(0.94)
12.33
(0.25)
4.05
4.02
(0.06)
(0.04)
5.44
4,66
(0.41)
10.02
11:47
(0.05)
(0.07)
3.82
3.31
(0.44)
4,83
6.39
(1.37)
(0,72)
15.86
18.38
(0.48)
(0/61)
2.54
3.82
0.25
7.08
12.96
8.64
6.74
13.79
(0.32)
(1.06)
(0.26)
(0.16)
(0.97)
(0:18)
(0.16)
(5
(0.16)
(0.14)
(0.30)
(0.12)
(0.13)
(0.33)
(0.14)
0.30
(0.15)
7.12
(0.26)
5:31
(0.18)
5.83
(0:33)
7.26
(1.20)
13:21
(0:41)
80
(0.31)
7.07
(2.51)
12:35
(0.34)
4.55
(0.09)
6.30
(0.11)
8.72
(0.09)
4.04
(0.22)
7.60
(0.76)
10.79
(0.13)
5.00
0.05
(0.25)
4.43
(1.85)
29.93
(0.35)
4,18
(0.27)
6.59
(0.51)
20.20
(0:35)
7.00
(0.47)
4.62
(5.24)
44,97
(0.85)
4,30
(0.20)
3.80
(2.77)
34.52
(0:35)
3.16
(0J03)
3.67
(8.74)
42,69
(0.49)
2.63
0.10
6.35
7:68
(0.26)
26.21
7.74
8.35
21.83
20.39
20.43
8.18
23.39
CIPAR- 10
(0.32)
(0.39)
(0.37)
(0.24)
(0.92)
(0:45)
(0.19)
(1.59)
(0.35)
(0.14)
(0,50)
(0.23)
(0.
(0.82)
(0.18)
0.20
(0.29)
10.45
(0:47)
14.53
(0.38)
5.82
(0.21)
9.32
21.86
(0.46)
(0:33)
6.33
(0.14)
9.65
(1.04)
17.16
(0.11)
7.50
(0.14)
9,09
(1.99)
18:45
(0.42)
6.62
(0.15)
9.69
(1.55)
19.54
(0.07)
7.20
0.25
(0.26)
11.64
(0.30)
11.20
(0.32)
9.56
(0.34)
10.46
(0,40)
22,02
(0.35)
6.35
(0.08)
10.85
(1.35)
14,22
(0.30)
8.50
(0.23)
10.31
(1,47)
15:39
(0.38)
7.64
10.96
11)
(1.71)
14,99
(0.40)
8.48
10.89
12.52
12.14
11.08
9.91
(0.18)
(0.15)
(0.33)
(0.81)
(0.24)
(0.17)
(0.75)
(0.31)
(0.16)
(0.122)
(0.14)
12)
(0.60)
(0.25)
often effective with simple models [57, 15]. These results show that our method can benefit from the flexibility of the choices of loss functions.
7 Conclusion
In this paper, we studied the problem of classification with rejection, which can refrain from making a prediction to avoid critical misclassification. We derived a novel formulation for CwR that can be equipped with arbitrary loss functions while maintaining the theoretical guarantees, making them highly adaptive to the dataset in practical use. First, we showed the equivalence between K-class CwR and (-la)s classification problem, and proposed an empirical risk minimization formulation to solve this problem with an estimation error bound. Then, we pointed out necessary and sufficient conditions for the learning consistency of the surrogates constructed on our proposed formulation equipped with any dassification-calibre results demonstrated the effectiveness of our proposed method.
multi-class losses. Finally, experimental
Acknowledgement
This research is supported by the National Research Foundation, Singapore under its Industry Align- ment Fund- - Pre-positioning (IAF-PP) Funding Initiative. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not reflect the views of National Research Foundation, Singapore. Yuzhou Cao was also supported by Ant Group through Ant Research Intern Program. Lei Feng was supported by the National Natural Science Foundation of China (Grant No. 62 62106028), Chongqing Overseas Chinese Entrepreneurship and Innovation Support Program, and CAAI-Huawei MindSpore Open Fund. MS was supported by JST CREST Grant Number JPMJCR18A2.
9

---

References
[1] 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.
[2] Pranjal Awasthi, Anqi Mao, Mehryar Mohri, and Yutao Zhong. A finer calibration analysis for adversarial robustness. CoRR, abs/2105.01550, 2021. URL 2105. 01550.
/
[3] Han Bao and Masashi Sugiyama. Calibrated surrogate maximization linear-fractional utility in binary classification. In AISTATS, volume 108 of Proceedings of Machine Learning Research, pages 2337-2347. PMLR, 2020.
[4] Han Bao, Clayton Scott, and Masashi Sugiyama. Calibrated surrogate losses for adversarially robust classification. COLT, volume 125 Proceedings of Machine Learning Research, pages 408-451. PMLR, 2020.
[5] Peter L. Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. J. Mach. Learn. Res., 3:463-482, 2002. URL http:://tlr...t html.
[6] Peter L. Bartlett and Marten H. Wegkamp. Classification with reject option using a hinge loss. J. Mach. Learn. Res., 9:1823-1840 2008.
[7] Peter L. Bartlett, Michael I. Jordan, and Jon D. McAuliffe. Convexity, classification, and risk bounds. Journal of the American Statistical Association, 101(473):13- 156, 2006.
[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] Nontawat Charoenphakdee, Jayakorn Vongkulbhisal, Nuttapong Chairatanakul, and Masashi Sugiyama. On focal loss for class- passs-oottrrior probability estimation: A theoretical perspective. In CVPR, pages 5202-5211, 2021.
[10] Mohammad-Ann Aminn Charusaie, Hussein Mozannar, David A. Sontag, and Samira Samadi. Sample efficient learning of predictors that complement humans. In ICML, volume 162, pages 2972- 3005, 2022.
[11] C. Chow. On optimum recognition error and reject tradeoff. IEEE Transactions on Information Theory, 16(1):41-444)) 1970. doi: 10.1 1999//TT.1900105444441
[12] Scott Clayton. Calibrated asymmetric surrogate losses. Electronic Journal of Stats, 6:238-238. 2012.
[13] Corinna Cortes, Giulia DeSalvo, and Mehryar Mohri. Boosting with abstention. In NeurIPS, pages 1660-1668, 2016.
[14] Corinna Cortes, Giulia DeSalvo, and Mehryar Mohri. Learning with rejection. In ALT, volume 9925, pages 67-82, 2016.
[15] Üräi Dogan, Tobias Glasmachers, and Christian Igel. A unified view on multi-class support vector classification. J. Mach. Learn. Res., 17:45:1-45:32, 2016.
[16] Ran El- Yaniv and Yair Wiener. On the foundations of noise-free selective classification. J. Mach. Learn. Res., 11:1605-1641, 2010.
[17] Charles Elkan. The foundations of cost-sensitive learning. IJCA, pages 973-978, Morgan Kaufmann, 2001.
[18] Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra, and Wu. Agnostic learning of monomials by halfspaces is hard. SIAM J. Comput., (166)1155--1590 2012.
10

---

[19] Jessica Finocchiaro, Rafael M. Frongillo, and Bo Waggoner. An embedding framework for consistent polyhedral surrogates. NeurIPS, pages 10780-10790. 2019. URL https: / /ttp://////eoiieeeeoeoooooooe ngs neurips wwtpappr/ccccccccccccccccce. 9/hash/ 9ec51 Feeb240fb33133866eee. 3737bca Abbtrratt................ html.
[20] Wei Gao and Zhi-Hua Zhou. On the consistency multi-label leamning Artif. Intell., 199-200: 22-44, 2013.
[21] Wei Gao and Zhi-Hua Zhou. On the consistency of AUC pairwise optimization. In IJCAI, pages 939-945, AAAI Press, 2015.
[22] Yonatan Geifman and Ran El-Ya.iv. Selective classification for deep neural networks. In NeurlPS, pages 4878-4887, 2017.
[23] Gustavo L. Gilardoni. On pinsker's and vajda's type inequalities for csiszár's f-divergences.
IEEE Trans. Inf. 5hlooyy,6(11)55377-55535 2010. doi: 10. 00.1109911220102226871000
[24] Yves Grandvalet, Alain Rakotomamonjy. Joseph Keshet, and Stéphanc Canu. Support vector machines with a reject option. In NeurIPS, pages 537-544, 2008.
[25] Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q. Weinberger. On calibration of modern neural networks. In ICML, volume 70 of Proceedings of Machine Learning Research, pages 1321-1330. PMLR, 2017.
[26] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In CVPR, pages 463-469, 2016.
[27] Yen-Chang Hsu, Zhaoyang Lv, Joel Schlosser, Phillip Odom, and Zsolt Kira. Multi-class classification without multi-class labels. ICLR, 2019.
[28] Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In ICML, volume 37, pages 448-456. JMLR.org, 2015.
[29] D. E. Knuth. Two notes on notation. American Mathematical Monthly, 99(5):403-44 1992.
[30] Oluwasammi Koyejo, Nagarajan Natarajan, Pradeep Ravikumar, and Inderjit Dhillon. Consis- tent multilabel classification. In NeurlPS, pages 3321-3329, 2015.
[31] Alex Krizhevsky. Learning multiple layers of features from tiny images. University of Toronto,
05 2012.
[32] Maksim Lapin, Matthias Hein, and Bernt Schiele, Analysis and optimization of loss functions for multiclass, top-k, and multilabel classification. IEEE Trans. Pattern Anal. Mach. Intell., 40 (7):1533-1554, 2018
[33] Tsung- Lin, Priya Goyal, Ross Girshick, Kaiming He, and Piotr Dollár. Focal loss for dense object detection. In ICCV, pages 2999-3007, 2017.
[34] Nan Lu, Shida Lei, Gang Niu, Issei Sato, and Masashi Sugiyama. Binary classification from multiple unlabeled datasets via surrogate set classification. In ICML, 2021.
[35] Naresh Manwani, Kalpit Desai, Sanand Sasidharan, and Ramasubramanian Sundararajan. Double ramp loss based reject option classifier. In PAKDD, volume 9077, pages 151-163, 2015,
[36] Andreas Maurer. A vector-contraction inequality for rademacher complexities. Ronald Ortner, Hans Ulrich Simon, and Sandra Zilles, editors, ALT, pages 3-17, 2016.
[37] C. Mcdiarmid. On the method of bounded differences. Surveys in Combinatorics, 1989.
[38] Shahar Mendelson. Lower bounds for the empirical minimization algorithm. IEEE Trans. Inf. Theory, 54(8):3797-3803 2008 doi: 10.11009/1..220089996666 926323. URL https: /doii org/ 10. 10.1119/TT 11119/11TTTT.. 2008 .100889263...
[39] Aditya Krishna Menon and Robert C. Williamson. In COLT, volume 35 of JMLR Workshop and Conference Proceedings, pages 68-106. JMLR.org, 2014. URL http::/procced:
mlr, www.ppresssvvee 3wm3m/onmmnnngg html.

---

[40] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar, Foundations of Machine Learning. Adaptive computation and machine learning. MIT Press, 2012. ISBN 978-0-262-01825-88
[41] Hussein Mozannar and David A. Sontag, Consistent estimators for learning to defer to an expert. In ICML, volume 119 of Proceedings of Machine Learning Research, pages 7076-7087. PMLR,
2020.
[42] Hussein Mozannar, Arvind Sayaaaaayan, and David A. Sontag. Teaching humans when to defer classifier via examplars. CoRR, abs/2111.11297, 2021. URL https: //axxiv. org/ /aaaa//////.lla////./...
[43] Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Ng. Reading digits in natural images with unsupervised feature learning. NeurlPS Workshop on Deep Learning and Unsupervised Feature Learning, 1 2011.
[44] Chenri Ni, Nontawat Charoenphakder, Junya Honda, and Masashi Sugiyama. On the calibration of multiclass classification with rejection. NeurlPS, pages 2582-2592. 2019.
[45] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Edward Yang. Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In NeurlPS, pages 8024 8035, 2019.
[46] Bernardo Ávila Pires and Csaba Szepesvári. Multiclass classificatton calibration functions. CoRR, abs/1609.06388 2016. URL http:
h http:://aaxvvv..ooee abs 1609/66000000 06385.
[47] Harish G. Ramaswamy and Shivani Agarwal. Convex calibration dimension for multiclass loss matrices. J. Mach. Learn. Res., 17:14:1-14:55, 2016. URL http:://mmmr..rrggg/ htrg//////ooooooo/o///////// papers/
v17/14-316 1..3mm........mmmmmm.....m.....m
[48] Harish G Ramaswamy, Ambuj Tewari, and Shivani Agarwal. Consistent algorithms for mul- ticlass classification with an abstain option. Electronic Journal of Statistics, 12(1))530-554 2018.
[49] Alexey E. Rastegin. Bounds of the pinsker and fannes types on the tsallis relative entropy. Mathematical Physics Analysis & Geometry, 16(3):213-228, 2013. 2013.
[50] Mark D. Reid and Robert C. Williamson. Composite binary losses. J. Mach. Learn. Res., 11: 2387-2422, 2010.
[51] Clayton Scott. Surrogate losses and regret bounds for cost-sensitive classification with example- dependent costs. Lise Getoor and Tobias Scheffer, editors, JCML, pages 153-160. Omnipress, 2011. URL https: / /icm1... ce /tce/221//// 1et01//pppera. /1rrrrs/13// 118 icmlpaper. pdf.
[52] Song-Qing Shen, Bin-Bin Yang, and Wei Gao. AUC optimization with reject option. In AAAI, pages 5684-5691, 2020.
[53] Ingo Steinwart. How to compare different loss functions and their risks. Constructive Apprexi- mation, 06:225-2877 2007.
[54] Ambuj Tewari and Peter Bartlett. On the consistency of multiclass classification methods. J. Mach. Learn. Res., 8:1007-1025, 2007.
[55] Vladimir Vapnik. Statisticul learning theory. Wiley, 1998. ISBN 978-0-471-03003-4,
[56] Rajeev Verma and Eric T. Nalisnick. Calibrated learning to defer with one-vs-all classifiers, In ICML, volume 162, pages 22184 14-222002, 2022.
[57] Yutong Wang and Clayton Scott. Weston-watkins hinge loss and ordered partitions. In NeurIPS, 2020.
[58] Robert C. Williamson, Flodie Vernet, and Mark D. Reid. Composite multiclass losses. J. Mach. Learn. Res., 17:223:1-223:55 2016.
12

---

[59] Guoqiang Wu, Chongxuan Li, Kun Xu, and Jun Zhu. Rethinking and reweighting the univariate losses for multi-label ranking: Consistency and generalization. CoRR, abs/2105.05026. 2021. URL htw.s:////// /arxiv org/ absgg//b//// 21 05. 05026.
[60] Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: novel image dataset for benchmarking machine learning algorithms. CoRR, abs/1708.07747.
[61] Y. Yang. Maximum lq-likelihood estimation. Annals of Statistics, 2010.
[62] 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.
[63] Ming Yuan and Marten H. Wegkamp. Classification methods with reject option based on convex risk minimization. J. Mach. Learn. Res., 11:111-130, 2010.
[64] Mingyuan Zhang, Harish Guruprasad Ramaswany, and Shivani Agarwal. Convex calibrated surrogates for the multi-label f-measure. In ICML, volume 119 of Proceedings of Machine Learning Research, pages 11246- 1255. PMLR, 2020.
[65] Tong Zhang. Statistical analysis of some multi multi-category large margin classification methods. Journal of Machine Learning Research, 5(0ct):1225-112 2004.
[66] Zhilu Zhang and Mert R. Sabuncu. Generalized cross entropy loss for training deep neural networks with noisy labels, In NeurlPS, pages 8792-8802, 2018.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Appendix H.
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See Appendix H.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main ex- perimental results (either in the supplemental material as a URL)? [Yes] See the supplemental material.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section 6 and Appendix.
(c) Did you report error bars (e-g., with respect the random seed after running experi- ments multiple times)? [Yes] See Table 2.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Section
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you eite the creators? [Yes] See Section 6.
(b) Did you mention the license of the assets? [N/A] The used datasets are open bench-
marks.
(c) Did you include any assets either in the supplemental material URL? [Yes] Please refer to the supplemental materials.
(d) Did you discuss whether and how consent was obtained from people whose data you'l 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "awWWQfgXnxf", "reviewer": "Reviewer_6EcA", "summary": "The paper considers the consistency of surrogate losses in classification with rejection (CwR) problem. \n\nThe paper first construct an augmented classification without rejection problem, which is equivalent to the CwR problem. Then,  building upon the classical consistency analyses, the paper defines a family of l_{01c} consistent losses in CwR based on arbitrary l_{01} calibrated loss. Further, it proves that such a relation is a necessary and sufficient condition for l_{01c} consistency. \n\nAlthough most of the existing losses are proven consistent, the paper found that the generalized cross-entropy loss has not been investigated before and gives the first proof. \n\nThe GCE induced loss achieves a good performance in practice.", "questions": "I do not have too much to complain about.", "limitations": "This is a theoretical work and I did not see a direct negative societal impact.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The main contribution of the paper is to show that the CwR problem can be reduced to an augmented classification problem without rejection. The theory, as well as the methodology, are insightful. \n\n2. The theory inspires new surrogate losses in CwR that works well in real data.\n\nWeakness:\n1. A very minor concern is that maybe the authors can validate the theory on some synthetic data where everything (e.g, all risks) can be calculated. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "RZ3v0pnJw14", "reviewer": "Reviewer_Nc8b", "summary": "This paper focuses on consistent surrogate losses for multi-class classification with rejection, where consistency means that minimizing the surrogate risk also minimizes the desired target risk. The authors first show that $K$-class classification with rejection is equivalent to a $(K+1)$-class classification problem on a modified probability distribution $\\tilde{p}$. They then show how surrogate losses for multi-class classification, operating on the original data distribution, can be modified to compute the risk on the modified distribution $\\tilde{p}$. It is claimed that ($\\ell_{01}$-)calibration of a surrogate for multi-class classification is a necessary and sufficient condition for consistency of the surrogate for classification with rejection. The paper also provides an estimation error bound for empirical risk minimization (ERM) of surrogates, and establishes the $\\ell_{01}$-calibration of the generalized cross entropy (GCE) loss. Experiments compare the proposed approach using two different surrogates, GCE and pairwise-sigmoid, to recent works on classification with rejection on three datasets.", "questions": "Please respond to my concerns about Theorems 4 and 5 especially. My current score reflects these concerns.\n\nFor curiosity:\n- Theorem 3: If the identifiability condition were dropped, then could we simply replace $R_{L_c^\\Phi}^*$ in (6) with $\\min_{g\\in\\mathcal{G}} R_{L^\\Phi_c} (g)$?\n- Lines 286-288, \"GCE method outperforms the baseline DEFER method, which indicates that CwR cannot be simply solved by the methods used for learning to defer\": I am wondering whether it really indicates that, or rather the advantage of using GCE over CE since that is the difference between the two (see lines 278-279).", "limitations": "OK", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\n+ The equivalence between $K$-class classification with rejection and $(K+1)$-class classification allows a wide range of existing multi-class surrogate losses to be used, where classification calibration in the more usual sense (without rejection) is sufficient for consistency in classification with rejection.\n+ The experiments demonstrate the benefit of this flexibility by showing that the proposed approach with GCE and pairwise-sigmoid losses can outperform existing methods that are restricted in their loss function.\n\n**Weaknesses:**\n\nI have several concerns about the proofs.\n- Theorem 4, proof of necessity\n    - First, should \"suppose there are some $\\mathbf{u} \\in \\Delta^{K+1}$\" be $\\mathbf{p}$ instead? $\\mathbf{u}$ is optimized over in the equation below. If yes, then it would be better to change $\\mathcal{U}$ to $\\mathcal{P}$ as well.\n    - I do not see why \"any re-permutation of $\\mathbf{u}$ ($\\mathbf{p}$) also fulfills the equation above.\" Does this assume that $\\Phi$ is permutation-invariant? Please justify further.\n    - The statement that \"there always exists a distribution $p(y|\\mathbf{x})$ and $c$ that $\\tilde{p}(\\tilde{y}|\\mathbf{x}) \\in \\mathcal{U}$\" also needs further justification in my mind. On the surface, $\\tilde{p}(K+1 | \\mathbf{x})$ can be at most $1/2$ when $c \\to 0$, so this seems like a constraint. Perhaps allowing all permutations in $\\mathcal{U}$ (contingent on the point above being true) resolves this, but this should be clarified.\n- Theorem 5: Two issues between lines 553, 554\n    - In taking the expectation to go from the point-wise excess loss to the excess risk, I think the square root should be on the inside of the expectation, at least to begin with. Perhaps there is then an argument (e.g. Jensen's inequality) to move it to the outside.\n    - In the exponent of $K$, I see that the $2r/(1-r)$ comes from the $\\eta_\\max$ term, but where do the $r + r^2$ terms come from?\n- Theorem 1\n    - Case $f^*(x) \\in \\{1, \\dots, K\\}$, $f(x) = R$ (I am using $R$ for reject because I don't know how to typeset the \"registered\" symbol in OpenReview): I think the right-hand side is missing $-1 + c(\\mathbf{x})$.\n    - The $y$ in $p(\\mathbf{x}, y)$: I think it should be $\\tilde{y}$ since this is the dummy variable being summed over.\n\n**Minor comments:**\n- A major thing I was looking for upon reading the introduction is the benefit of allowing a full range of surrogate losses. As I wrote above, I think the experiments have shown that benefit with the GCE and pairwise-sigmoid losses. So I think the introduction can state the benefit of this flexibility more strongly, to better motivate the paper, and point to the results in Section 6.\n- \"class-posterior possibility\" and elsewhere: I believe \"probability\" is the standard term instead of \"possibility\".\n- Line 48, \"family of surrogates are the ensembles of arbitrary binary classification losses\": This didn't make sense to me, perhaps words are missing.\n- Line 84: \"competent\" --> \"confident\"?\n- Line 116: \"remaining\" --> \"retaining\"\n- Line 159, \"Lemma 1\" : I think this should read \"Theorem 1 is a special case of Corollary 1.\" There seem to be several more broken references to Theorem 1 and/or Corollary 1, e.g. lines 173, 237\n- Theorem 3: It would be good to clearly define $\\hat{\\mathbf{g}}$ as the empirical risk minimizer.\n- I was a bit confused by the statements before Theorem 4 about \"$\\ell_{01c}$-consistency of such surrogates still remaining unchecked.\" It seems that sufficiency follows naturally from the development of the paper and the proof of Theorem 4 does not add anything on sufficiency. Perhaps these statements could be rephrased to say that what remains in question is the necessity of $\\ell_{01}$-calibration (assuming that my concerns about Theorem 4 above can be resolved).\n- Line 238: $D_c$ --> $D_c^R$ ($R$ for reject)?\n- Line 259: $\\Phi^\\gamma$ --> $\\Phi_\\gamma$\n- Line 292: \"classification cost\" --> \"rejection cost\"?\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "LzogwMUATBd", "reviewer": "Reviewer_bLUw", "summary": "This paper studies classification with rejection (CwR) in multiclass problems. The proposed method can utilize any classification-calibrated surrogate losses while maintaining theoretical guarantees (consistency). Specifically, the work establishes the equivalence between K-class CwR problem and a (K+1)-class classification problem by showing the two classification risks are equal. Then, using any multiclass surrogate loss as a building block, a formulation of surrogates is proposed to realize the surrogate risk of the (K+1)-class classification problem, with only the original K-class training data needed. An estimation error bound is derived for its ERM. It is then shown that a necessary and sufficient condition for the proposed surrogate to be consistent is that the underlying multiclass surrogate loss is classification-calibrated. Finally, the calibration analysis of the generalized cross entropy (GCE) loss is provided.", "questions": "- In Section 6, it is mentioned that DEFER is a special case of the proposed method with cross entropy loss as $\\Phi$. However, cross entropy loss is also classification-calibrated. Then why the performance of DEFER is not that good?\n- For FMNIST, CE and Sigmoid outperformed GCE. Any ideas why that's the case?", "limitations": "Yes, in the appendix.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper is a solid piece of work. It is also well-written and well-presented.\n\n**Originality:**\nThe proposed method can utilize any classification-calibrated surrogate losses while maintaining consistency guarantees, by showing the equivalence between K-class CwR problem and a (K+1)-class classification problem. It is novel, simple and effective. Related works have been properly cited and discussed.\n\n**Quality:**\nThe work is sound. Claims are well supported by both the theory and experimental results. Weaknesses and limitations have been discussed.\n\n**Clarity:**\nThe paper is mostly well-written and well-organized. Some minor problems I found are listed below. The authors are encouraged to proofread more carefully.\n- \"Lemma X\" are referred to several times, while the paper only has \"Theorem\" and \"Corollary\" instead of \"Lemma\". Line 159. Line 173. Line 222. Line 237.\n- Line 173: Should be $R_{01c} (c \\circ \\mathbf{g})$.\n- Definition 6 and Theorem 5: inconsistent notations $\\Phi_r$ and $\\Phi^r$.\n- Section 5.2: the flow can be improved. Before Theorem 5, \"..., to the best of our knowledge, its calibration results remain unknown, and thus it is unsafe ...\". Then the calibration of GCE is presented in Theorem 5. The flow of this part seems a bit abrupt.\n- In Table 2, I think 01c, Rej, and 01 correspond to the first paragraph of Section 6, but it would be more clear to include their meanings in the caption of the table.\n\n**Significance:**\nThe paper is a valuable piece of work in the field classification with rejection. The proposed method is simple, general, and effective. It can also be very useful for practitioners.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "8-UV9-jps-Q", "reviewer": "Reviewer_RQPg", "summary": "This work proposes a ERM learning algorithm for Classification with Rejection(CwR) problems. The work reveals the connection between CwR and traditional multi-class classification problem and avoids leveraging the less tractable self- augmented distribution in the proposed model.  Both the learning bound and consistency of the algorithm are provided. For consistency, this work provides the necessary and sufficient conditions when a surrogate and calibrated loss is adopted.", "questions": "In line 162 it says that the minimization of \\bar{R}_{01} can be seen as ordinary classification risk minimization with a different marginal density p'(x) which does not affect the calibration since class posterior possibilities remain unchanged. I am a bit confused here, I thought the minimization of \\bar{R}_{01}  can be seen as ordinary classification risk minimization only if there is no distribution shift between the two problems. But with p(x) changing, could we still treat them as the same?\n", "limitations": "None", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Weakness:\n1. There are some minor mistakes in the manuscript. For example, in line 159 ‘It is obvious that Lemma1 is a special case of Lemma 1….’’ There is no Lemma 1 in the paper and I assume the author means that corollary 1 is a special case of Theorem 1. \nIn line173 ’...indicates the minimization of R01c(\\phi g) according to Lemmas 1 and 1.\nIn line 222 ‘According to Lemma1…’’ again, there is no lemma 1 in the paper.\nI assume all the lemma1 in the paper refer to corollary 1 but even corollary 1 itself is problematic. Its main body states that ‘the following inequalities hold..’ but all it got is single equality. \nThose mistakes (and a few more)  make me confused from time to time during the reading and make the paper a bit harder to follow.\n2. I feel some of the important arguments need to be further elaborated. For example, in line 172 ‘with a properly chosen surrogate \\phi the minimization of \\tilde{R_\\phi}(g) can lead to that of \\tilde{R}_{01}(\\phi(g))’. Although some related works are cited, it would be more helpful for the author to briefly explain how the commonly adopted principles for choosing the proper surrogates and the rationale behind them.\n\n\nStrength\n1. This paper presents an effective ERM algorithm for CwR problems. The learning bound and consistency of the algorithm are both provided.\n2. This paper offers an interesting view to connect multi-class classification and CwR, which is able to leverage calibrated surrogate loss to avoid directly addressing the c-self-augmented distribution during the learning process.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}]

Author rebuttal:

Decision: Accept